© April
2014, Darrell Cox
The Farey series Fn of order n is the ascending series of irreducible fractions between 0 and 1 whose denominators do not exceed n. For example, F5 is 0/1, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 1/1. The Farey series is not evenly distributed between 0 and 1, but as n increases, the distribution becomes more even. This suggests that the rational numbers close to a given real number less than 1.0 can be found by multiplying the real number by the number of fractions in the Farey series and using this quantity as an index into the Farey series (the operations would be a floating-point multiply, a floating-point add of 0.5 [to round], a floating-point to fixed-point conversion, and a table look-up). An appreciation of the accuracy of the estimated index can be had by generating the histogram of the deviations between the estimated and actual indices of the fractions in the series. For a Farey series consisting of 304193 fractions (corresponding to an order of 1000), 91.8 percent of the fractions had an estimated index that deviated from the actual index by 10 or less. The Farey series need be computed only once and thereafter the rational numbers close to a given real number less than 1.0 can be looked up in the Farey series table. The main restriction to this approach is computer memory; the number of fractions in a Farey series is one plus the sum of φ(i) from i=1 to n where φ(i) is Euler's totient function. (φ(i) equals the number of positive integers not greater than i and relatively prime to i. The sum of φ(i) from i=1 to n is approximately equal to 3n2/π2.) The memory requirement can be cut in half by using the property that the fractions in a Farey series are complementary about the fraction 1/2 (that is, if 1/2 is the ith fraction in the series, then the (i+1)th fraction equals 1 minus the (i-1)th fraction, etc.). The continued fraction algorithm is commonly used to approximate given real numbers with rational numbers. The continued fraction algorithm rapidly converges can be efficiently implemented. An advantage of the continued fraction algorithm over the Farey series look-up is that it provides a way to approximate given real numbers with rational numbers with large numerators and denominators (the memory requirement makes generating Farey series of large orders impractical.) The disadvantage of the continued fraction algorithm is that it gives only the best approximations of the given real number; in some applications, other rational numbers in the vicinity of the real number need to be found. However, if used with Lagrange's algorithm for finding solutions of the Diophantine equation kx-hy=1 and an algorithm for generating the fractions in a Farey series before and after two given successive fractions in the series, the rational numbers in the vicinity of the convergents of the continued fraction can be found. The procedure is as follows. The convergents of the continued fraction are computed until the denominator of the convergent exceeds the specified upper bound of the denominators (of rational numbers used to approximate real numbers). Denote this upper bound by n and denote the preceding convergent by h/k. Lagrange's algorithm is then used to find the successive fraction h'/k' in a Farey series of order n. An algorithm for generating Farey series starting with two successive fractions in the series is then used to find the fractions in the vicinity of h/k. Efficient algorithms for generating Farey series are then of interest. In 1802, Haros proved the following two theorems;
(1) If h/k and h'/k' are two successive terms in Fn, then kh'-hk'=1.
(2) If h/k, h'/k', and h''/k'' are three successive terms in Fn, then h'/k'=(h+h'')/(k+k'').
Two simpler properties of Fn (proved in G. H. Hardy and E. M. Wright's book "An Introduction to the Theory of Numbers") are;
(3) If h/k and h'/k' are two successive terms of Fn, then k+k'>n.
(4) If n>1, then no two successive terms of Fn have the same denominator.
(5) If h/k and h'/k' are successive fractions in a Farey series, then the line between the points (h, k) and (h', k') splits the lattice in such a way that all the fractions in the series defined by points to the left of the line are less than h/k and all the fractions in the series defined by points to the right of the line are greater than h/k. If k'>k, the fractions in the series defined by points on the line are less than h/k if their denominators are less than k, or greater than h/k if their denominators are greater than k. If k>k', the fractions in the series defined by points on the line are greater than h/k if their denominators are less than k, or less than h/k if their denominators are greater than k.
A program for generating a Farey series using theorems (1), (3), and (5) is farey1.
(6) Suppose h/k and h'/k' are successive fractions in a Farey series of order n where k'>k and denote [(n-k')/(k'-k)] by l. If l≠0, the next l fractions in the Farey series correspond to the remaining lattice points on the line through (h, k) and (h', k') and are (h'+(h'-h)i)/(k'+(k'-k)i), i=1, 2, 3, ..., l.
(7) If h/k and h'/k' are successive fractions in a Farey series and k'>k, the fraction in the Farey series after the fractions corresponding to the lattice points on the line through (h, k) and (h', k') is (h'-h)/(k'-k).
(8) Suppose h/k and h'/k' are successive fractions in a Farey series of order n where k>k' and denote [{(2k'-n-1)/(k-k')}/2] by l. ({A} denotes the smallest integer greater than A.) If l>0, the next l fractions in the Farey series correspond to the next l lattice points on the line through (h, k) and (h', k') and are (h'-(h-h')i)/(k'-(k-k')i), i=1, 2, 3, ..., l.
(9) The fraction after the successive fractions h/k and h'/k' in a Farey series of order n is (jh'-h)/(jk'-k) where j=[(n+k)/k']. (Also, if h/k, h'/k', and h''/k'' are successive fractions in a Farey series of order n where k>k', k'<k'', and 2k'≥n, then h''=3h'-h and k''=3k'-k.)
If the denominators of the given successive fractions are increasing, the first two theorems can be used to find the next pair of successive fractions where the denominators are decreasing. The last two theorems can then be used to find the next pair of successive fractions where the denominators are increasing. Similar logic applies when the denominators of the given successive fractions are decreasing. A program for generating a Farey series using this algorithm is harfar.
Mém. Acad. Berlin, 23, année 1767, 1769, 7; Oeuvres, 2, 1868, 386-8.
C. Haros
Jour. de l'école polyt., cah. 11, t. 4, 1802, 364-8.
Software
Use expand1 to approximate a given real number with a rational number using the continued-fraction algorithm. Use test1f, test2f, test3f, and test4f to test the above programs. Readers may copy and modify the above software.
The Farey series Fn of order n is the ascending series of irreducible fractions between 0 and 1 whose denominators do not exceed n. For example, F5 is 0/1, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 1/1. The Farey series is not evenly distributed between 0 and 1, but as n increases, the distribution becomes more even. This suggests that the rational numbers close to a given real number less than 1.0 can be found by multiplying the real number by the number of fractions in the Farey series and using this quantity as an index into the Farey series (the operations would be a floating-point multiply, a floating-point add of 0.5 [to round], a floating-point to fixed-point conversion, and a table look-up). An appreciation of the accuracy of the estimated index can be had by generating the histogram of the deviations between the estimated and actual indices of the fractions in the series. For a Farey series consisting of 304193 fractions (corresponding to an order of 1000), 91.8 percent of the fractions had an estimated index that deviated from the actual index by 10 or less. The Farey series need be computed only once and thereafter the rational numbers close to a given real number less than 1.0 can be looked up in the Farey series table. The main restriction to this approach is computer memory; the number of fractions in a Farey series is one plus the sum of φ(i) from i=1 to n where φ(i) is Euler's totient function. (φ(i) equals the number of positive integers not greater than i and relatively prime to i. The sum of φ(i) from i=1 to n is approximately equal to 3n2/π2.) The memory requirement can be cut in half by using the property that the fractions in a Farey series are complementary about the fraction 1/2 (that is, if 1/2 is the ith fraction in the series, then the (i+1)th fraction equals 1 minus the (i-1)th fraction, etc.). The continued fraction algorithm is commonly used to approximate given real numbers with rational numbers. The continued fraction algorithm rapidly converges can be efficiently implemented. An advantage of the continued fraction algorithm over the Farey series look-up is that it provides a way to approximate given real numbers with rational numbers with large numerators and denominators (the memory requirement makes generating Farey series of large orders impractical.) The disadvantage of the continued fraction algorithm is that it gives only the best approximations of the given real number; in some applications, other rational numbers in the vicinity of the real number need to be found. However, if used with Lagrange's algorithm for finding solutions of the Diophantine equation kx-hy=1 and an algorithm for generating the fractions in a Farey series before and after two given successive fractions in the series, the rational numbers in the vicinity of the convergents of the continued fraction can be found. The procedure is as follows. The convergents of the continued fraction are computed until the denominator of the convergent exceeds the specified upper bound of the denominators (of rational numbers used to approximate real numbers). Denote this upper bound by n and denote the preceding convergent by h/k. Lagrange's algorithm is then used to find the successive fraction h'/k' in a Farey series of order n. An algorithm for generating Farey series starting with two successive fractions in the series is then used to find the fractions in the vicinity of h/k. Efficient algorithms for generating Farey series are then of interest. In 1802, Haros proved the following two theorems;
(1) If h/k and h'/k' are two successive terms in Fn, then kh'-hk'=1.
(2) If h/k, h'/k', and h''/k'' are three successive terms in Fn, then h'/k'=(h+h'')/(k+k'').
Two simpler properties of Fn (proved in G. H. Hardy and E. M. Wright's book "An Introduction to the Theory of Numbers") are;
(3) If h/k and h'/k' are two successive terms of Fn, then k+k'>n.
(4) If n>1, then no two successive terms of Fn have the same denominator.
Farey Series and the Integer Lattice
Fractions can be mapped to a two-dimensional coordinate system. In the integer lattice, let the numerators of fractions be along the x axis and the denominators be along the y axis. Another property of a Farey series is;(5) If h/k and h'/k' are successive fractions in a Farey series, then the line between the points (h, k) and (h', k') splits the lattice in such a way that all the fractions in the series defined by points to the left of the line are less than h/k and all the fractions in the series defined by points to the right of the line are greater than h/k. If k'>k, the fractions in the series defined by points on the line are less than h/k if their denominators are less than k, or greater than h/k if their denominators are greater than k. If k>k', the fractions in the series defined by points on the line are greater than h/k if their denominators are less than k, or less than h/k if their denominators are greater than k.
A program for generating a Farey series using theorems (1), (3), and (5) is farey1.
Lagrange's Algorithm for Solving the Diophantine Equation kx-hy=1
A Farey series can be generated using Lagrange's algorithm for solving the Diophantine equation kx-hy=1. To find integers p1 and q1 satisfying pq1-qp1=1 or -1 where p and q are relatively prime, Lagrange reduced p/q to a continued fraction. A series of fractions converging towards p/q, alternately less than and greater than p/q, is obtained. If p1 is taken to equal the numerator and q1 is taken to equal the denominator of the convergent immediately preceding p/q, then pq1-qp1=1 if p1/q1<p/q or -1 if p1/q1>p/q. Euclid's greatest common divisor algorithm is used to compute the partial quotients of the continued fraction. An embellishment to the algorithm is that a solution of pq1-qp1=1 is given if the number of partial quotients is even. Note that if pq1-qp1=-1, then p(q-q1)-q(p-p1)=1 so that a solution of pq1-qp1 is given by setting q1 to q-q1 and p1 to p-p1. A necessary condition that h'/k' be the fraction in the Farey series of order n following the fraction h/k is that kh'-hk'=1 (by Haros' theorem). Solving kh'-hk'=1 using Lagrange's algorithm does not necessarily give the next fraction in the series. Necessary and sufficient conditions that h'/k' be the next fraction in the series are that kh'-hk'=1, k+k'>n (by the theorem that the sum of the denominators of two successive fractions in a Farey series is greater than the order of the series), and 1≤k'≤n (since k≥h, k'≥h', and hence h'≤n when k'≤n). Note that if kh'-hk'=1, then k(h'+hr)-h(k'+kr)=1 for every integer r. If an r can be found such that k+(k'+kr)>n and 1≤k'+kr≤n, then h'+hr and k'+kr are the numerator and denominator of the next fraction in the Farey series. Solving these conditions gives (n-k')/k≥r>(n-k')/k-1. r then equals the greatest integer in (n-k')/k. (The greatest integer in A will be denoted by [A].) This is not a very efficient algorithm, but it illustrates Lagrange's algorithm. A program for generating a Farey series using Lagrange's algorithm is lagrange.A Fast Algorithm for Generating a Farey Series Using One of Haros' Theorems
A fast algorithm for generating a Farey series uses the theorem that if h/k, h'/k', and h''/k'' are three successive fractions in a Farey series, then h'/k'=(h+h'')/(k+k''). The fraction following the successive fractions h/k and h'/k' in a Farey series is then (jh'-h)/(jk'-k) where j is some positive integer. Using the theorem that the sum of the denominators of two successive fractions in a Farey series is greater than the order of the series gives j=[(n+k)/k']. (([(n+k)/k']k'-k)+k' is greater than n since [(n+k)/k']k'+k' is greater than n+k. Also, note that [(n+k)/k']k'-k is less than or equal to n.) The execution time of the algorithm is proportional to the number of fractions in the series and the algorithm requires no more memory than that required to hold the fractions. An advantage of this algorithm is that the fractions in a Farey series can be computed starting with any two given successive fractions in the series. The algorithm can also be modified to give the fractions in a Farey series before any two given successive fractions in the series . A fixed-point reciprocal look-up table (consisting of n entries) can be used to perform the exact integer divides. (Each reciprocal in the look-up table is rounded up. Enough bits of precision are maintained so that nδ [where δ is the maximum error due to the rounding] is less than 1. The fractional portion of the product can then be discarded.) A program for generating a Farey series using this algorithm is haros.Generating Farey Series Using Integer Lattice Theorems
Another fast algorithm for computing the fractions in a Farey series after two given successive fractions uses the following theorems;(6) Suppose h/k and h'/k' are successive fractions in a Farey series of order n where k'>k and denote [(n-k')/(k'-k)] by l. If l≠0, the next l fractions in the Farey series correspond to the remaining lattice points on the line through (h, k) and (h', k') and are (h'+(h'-h)i)/(k'+(k'-k)i), i=1, 2, 3, ..., l.
(7) If h/k and h'/k' are successive fractions in a Farey series and k'>k, the fraction in the Farey series after the fractions corresponding to the lattice points on the line through (h, k) and (h', k') is (h'-h)/(k'-k).
(8) Suppose h/k and h'/k' are successive fractions in a Farey series of order n where k>k' and denote [{(2k'-n-1)/(k-k')}/2] by l. ({A} denotes the smallest integer greater than A.) If l>0, the next l fractions in the Farey series correspond to the next l lattice points on the line through (h, k) and (h', k') and are (h'-(h-h')i)/(k'-(k-k')i), i=1, 2, 3, ..., l.
(9) The fraction after the successive fractions h/k and h'/k' in a Farey series of order n is (jh'-h)/(jk'-k) where j=[(n+k)/k']. (Also, if h/k, h'/k', and h''/k'' are successive fractions in a Farey series of order n where k>k', k'<k'', and 2k'≥n, then h''=3h'-h and k''=3k'-k.)
If the denominators of the given successive fractions are increasing, the first two theorems can be used to find the next pair of successive fractions where the denominators are decreasing. The last two theorems can then be used to find the next pair of successive fractions where the denominators are increasing. Similar logic applies when the denominators of the given successive fractions are decreasing. A program for generating a Farey series using this algorithm is harfar.
A Complex Algorithm for Generating a Farey Series Starting with Two Given Successive Fractions
The fastest algorithm (on some microprocessors) for generating the fractions in a Farey series after two given successive fractions is farsec. A subroutine used is frank. The algorithm uses repeated applications of the functions A=A(mod B) and B=B(mod A). (The slowest converging initial (A, B) values are two successive Fibonacci numbers.) A detailed explanation of the algorithm is given in the header of the program.References
J. L. LagrangeMém. Acad. Berlin, 23, année 1767, 1769, 7; Oeuvres, 2, 1868, 386-8.
C. Haros
Jour. de l'école polyt., cah. 11, t. 4, 1802, 364-8.
Software
Use expand1 to approximate a given real number with a rational number using the continued-fraction algorithm. Use test1f, test2f, test3f, and test4f to test the above programs. Readers may copy and modify the above software.