Fraction interpolation walking a Farey tree
- 作者：Marc Mosko and J.J. Garcia-Luna-Aceves
- 关键词：Algorithms ; Graph algorithms ; Farey
- 刊名：Information Processing Letters
- 出版年：2006
- 期刊代码：61_00200190
- 类别：cp
- 出版时间：15 April 2006
- 卷：98
- 期：1
- 页码：19-23
- 文件大小：94 K
摘要
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 m<n and n>1. A fraction m/n is simpler than p/q if mp and nq, 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 [D.W. Matula, P. Kornerup, Foundations of finite precision rational arithmetic, Computing 2 (Suppl.) (1980) 85–111] 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.