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.