Paria, Biswajit;Pratihar, Sanjoy;Bhowmick, Partha

Math. Appl. (Brno)5, No. 2, 123-145 (2016).

Summary: Farey sequences, introduced by such renowned mathematicians as John Farey, Charles Haros, and Augustin-L. Cauchy over 200 years ago, are quite well- known by today in theory of fractions, but its computational perspectives are possibly not yet explored up to its merit. In this paper, we present some novel theoretical results and efficient algorithms for representation of a Farey sequence through a Farey table. The ranks of the fractions in a Farey sequence are stored in the Farey table to provide an efficient solution to the rank problem, thereby aiding in and speeding up any application frequently requiring fraction ranks for computational speed-up. As the size of the Farey sequence grows quadratically with its order, the Farey table becomes inadvertently large, which calls for its (lossy) compressionup to a permissible error. We have, therefore, proposed two compression schemes to obtain a compressed Farey table (CFT). The necessary analysis has been done in detail to derive the error bound in a CFT. As the final step towards space optimization, we have also shown how a CFT can be stored in a 1-dimensional array. Experimental results have been furnished to demonstrate the characteristics andefficiency of a Farey table and its compressed form.

Keywords:

Farey sequence;Farey table;fraction rank;fraction error;rank problem;digital geometry;digital image processing