Fraction interpolation walking a Farey tree We present an
algorithm to find a proper fraction in simplest reduced terms
between two reduced proper fractions. A proper fraction is a
rational number m/n with m1. A fraction m/n is simpler than p/q
if m <= p and n <= q, with at least one inequality strict. The
algorithm operates by walking a Farey tree in maximum steps down
each branch. Through monte carlo simulation, we find that the
present algorithm finds a simpler interpolation of two fractions
than using the Euclidean-Convergent [Matula 1980] walk of a
Farey tree and terminating at the first fraction satisfying the
bound. Analysis shows that the new algorithms, with very high
probability, will find an interpolation that is simpler than at
least one of the bounds, and thus take less storage space than
at least one of the bounds. - download PDF (150K) Mosko, M. ;
Garcia-Luna-Aceves, J. J. Fraction interpolation walking a Farey
tree. Information Processing Letters. 2006 April 15; 98 (1):
19-23.