Farey Series
Created | Updated Dec 19, 2008
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 limit as n approaches infinity of the sum of φ(i) from i=1 to n is 3n2/π2 [proved by Dirichlet in 1849].) 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.
(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.
unsigned int rank(unsigned int N, unsigned int M, unsigned int *R, unsigned int NUM, unsigned int DEN, unsigned int SP, unsigned int *STACK) {
//
// check for an increase in denominator
//
L100: J=(N-STACK[2*SP+1])/DEN;
if (J==0) goto L500;
//
// increase in denominator
//
if (J==1) goto L300;
DELNUM=NUM;
DELDEN=DEN;
NUM=STACK[2*SP]+NUM*J;
DEN=STACK[2*SP+1]+DEN*J;
M=M+1;
R[2*M]=NUM;
R[2*M+1]=DEN;
NUM=STACK[2*SP]+DELNUM;
DEN=STACK[2*SP+1]+DELDEN;
if (J==2) goto L200;
//
// push fractions on the stack
//
K=J-2;
for (I=0; I<K; I++) {
SP=SP+1;
STACK[2*SP]=NUM;
STACK[2*SP+1]=DEN;
NUM=NUM+DELNUM;
DEN=DEN+DELDEN;
}
//
// decrease in denominator
//
L200: M=M+1;
R[2*M]=NUM;
R[2*M+1]=DEN;
goto L100;
//
// increase in denominator
//
L300: DELNUM=STACK[2*SP];
DELDEN=STACK[2*SP+1];
NUM=DELNUM+NUM;
DEN=DELDEN+DEN;
K=(N-DEN)/DELDEN;
if (K==0) goto L400;
for (I=0; I<K; I++) {
M=M+1;
R[2*M]=NUM;
R[2*M+1]=DEN;
NUM=NUM+DELNUM;
DEN=DEN+DELDEN;
}
L400: M=M+1;
R[2*M]=NUM;
R[2*M+1]=DEN;
//
// decrease in denominator, pop a fraction off the stack
//
L500: NUM=STACK[2*SP];
DEN=STACK[2*SP+1];
SP=SP-1;
M=M+1;
R[2*M]=NUM;
R[2*M+1]=DEN;
if (SP>0) goto L100;
//
STACK[0]=NUM;
STACK[1]=DEN;
return(M);
}
//
// GENERATE A FAREY SERIES
//
/* This C subroutine generates the fractions in a Farey series after two given successive fractions in the series. The calling sequence of the subroutine is; */
//
// "N" is the order of the Farey series
// "M" is the index of the previous fraction
// "R" is the output array (large enough to hold the Farey series)
// "NUM" is the numerator of the current fraction
// "DEN" is the denominator of the current fraction
// "OLDNUM" is the numerator of the previous fraction
// "OLDDEN" is the denominator of the previous fraction
// "STACK" is a temporary array (having 2N elements)
//
void farey(unsigned int N, unsigned int M, unsigned int *R, unsigned int NUM, unsigned int DEN, unsigned int OLDNUM, unsigned int OLDDEN, unsigned int *STACK) {
unsigned int I,J,K,SP,DELNUM,DELDEN;
//
// store last fraction and current fraction
//
R[2*M]=OLDNUM;
R[2*M+1]=OLDDEN;
M=M+1;
R[2*M]=NUM;
R[2*M+1]=DEN;
if (DEN==1) goto L500;
if (DEN<OLDDEN) goto L300;
//
// increase in denominator
//
DELNUM=NUM-OLDNUM;
DELDEN=DEN-OLDDEN;
K=(N-DEN)/DELDEN;
if (K!=0) goto L100;
if (DELDEN<OLDDEN) goto L200;
goto L400;
L100: for (I=0; i<K; I++) {
NUM=NUM+DELNUM;
DEN=DEN+DELDEN;
M=M+1;
R[2*M]=NUM;
R[2*M+1]=DEN;
}
L200: NUM=DELNUM;
DEN=DELDEN;
M=M+1;
R[2*M]=NUM;
R[2*M+1]=DEN;
if (DEN==1) goto L500;
//
// decrease in denominator
//
L300: J=OLDDEN/DEN;
OLDNUM=OLDNUM-J*NUM;
OLDDEN=OLDDEN-J*DEN;
L400: J=DEN/OLDDEN;
if (OLDNUM==0) J=J-1;
//
// push fractions on the stack
//
NUM=NUM-J*OLDNUM;
DEN=DEN-J*OLDDEN;
SP=0;
for (I=0; I<J; I++) {
SP=SP+1;
STACK[2*SP]=NUM;
STACK[2*SP+1]=DEN;
NUM=NUM+OLDNUM;
DEN=DEN+OLDDEN;
}
M=rank(N,M,R,NUM,DEN,SP,STACK);
NUM=STACK[0];
DEN=STACK[1];
if (DEN!=1) goto L300;
L500: return;
}
An explanation of the algorithm is as follows. The numerator and denominator of the current fraction are denoted by "NUM" and "DEN" respectively and the numerator and denominator of the previous fraction are denoted by "OLDNUM" and "OLDDEN" respectively. Denote NUM-OLDNUM and DEN-OLDDEN by "DELNUM" and "DELDEN" respectively. If the denominators are increasing (DELDEN>0), the next K=(N-DEN)/DELDEN fractions in the Farey series correspond to the remaining lattice points on the line between (OLDNUM,OLDDEN) and (NUM,DEN) and the numerator and denominator of the fraction following these fractions are DELNUM and DELDEN respectively. If K≠0, these fractions are stored in the Farey series array ("R") and the current fraction set to the last fraction (DELNUM/DELDEN). If K≠0, DELDEN is less than OLDDEN, so that the current fraction has been adjusted so that OLDDEN>DEN. If K=0 and DELDEN is less than OLDDEN, the current fraction is set to the last fraction (DELNUM/DELDEN) and the current fraction stored in the R array. If K=0 and OLDDEN<DEN, then OLDDEN is less than the denominator of the previous fraction in the Farey series so that (OLDNUM,OLDDEN) is an inflection point in the lattice of points corresponding to the fractions in the Farey series. OLDNUM and OLDDEN are adjusted (in a loop) so that (OLDNUM,OLDDEN) is an inflection point by taking OLDNUM modulo NUM and OLDDEN modulo DEN (computing OLDNUM/NUM is not necessary since OLDNUM/NUM equals OLDDEN/DEN). NUM and DEN are then adjusted so that (NUM,DEN) is a following inflection point by taking NUM modulo OLDNUM (when OLDNUM>1) and DEN modulo OLDDEN. (When OLDNUM≥2, NUM/OLDNUM equals DEN/OLDDEN and when OLDNUM=1, NUM/OLDNUM-1 equals DEN/OLDDEN.) When OLDNUM<2, NUM is set to NUM-(DEN/OLDDEN)*OLDNUM. The fractions corresponding to the lattice points on the line between (NUM, DEN) (before adjustment) and the adjusted (NUM,DEN) values are pushed on the stack beginning with the fraction corresponding to the adjusted (NUM,DEN) value and ending with the fraction corresponding to the point after (NUM,DEN). If OLDNUM=0, the number of fractions to be pushed on the stack is decreased by one to avoid pushing the fraction 1/0 on the stack. The fractions in the Farey series between NUM/DEN and the adjusted NUM/DEN value are then computed using the unadjusted NUM/DEN value and the fractions pushed on the stack. For each iteration of the loop, (OLDNUM,OLDDEN) becomes an inflection point further back in the Farey series and (NUM,DEN) becomes an inflection point further forward in the Farey series so that (OLDNUM,OLDDEN) eventually becomes the first fraction in the Farey series ((0,1)) and (NUM,DEN) eventually becomes the last fraction in the Farey series ((1,1)). Since OLDDEN is set to OLDDEN modulo DEN, and DEN is set to DEN modulo OLDDEN, (NUM,DEN) and (OLDNUM,OLDDEN) rapidly converge to their final values. For repeated applications of the functions B=B modulo A, and A=A modulo B, the slowest converging initial values (A,B) are two consecutive Fibonacci numbers. For Farey series of orders less than 1000, fewer than 17 iterations of the loop would be required. This technique can be used to compute the fractions in a Farey series before two given successive fractions by complementing the given successive fractions and computing the fractions after the complements.
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.
(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.
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 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.)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 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 as follows;unsigned int rank(unsigned int N, unsigned int M, unsigned int *R, unsigned int NUM, unsigned int DEN, unsigned int SP, unsigned int *STACK) {
//
// check for an increase in denominator
//
L100: J=(N-STACK[2*SP+1])/DEN;
if (J==0) goto L500;
//
// increase in denominator
//
if (J==1) goto L300;
DELNUM=NUM;
DELDEN=DEN;
NUM=STACK[2*SP]+NUM*J;
DEN=STACK[2*SP+1]+DEN*J;
M=M+1;
R[2*M]=NUM;
R[2*M+1]=DEN;
NUM=STACK[2*SP]+DELNUM;
DEN=STACK[2*SP+1]+DELDEN;
if (J==2) goto L200;
//
// push fractions on the stack
//
K=J-2;
for (I=0; I<K; I++) {
SP=SP+1;
STACK[2*SP]=NUM;
STACK[2*SP+1]=DEN;
NUM=NUM+DELNUM;
DEN=DEN+DELDEN;
}
//
// decrease in denominator
//
L200: M=M+1;
R[2*M]=NUM;
R[2*M+1]=DEN;
goto L100;
//
// increase in denominator
//
L300: DELNUM=STACK[2*SP];
DELDEN=STACK[2*SP+1];
NUM=DELNUM+NUM;
DEN=DELDEN+DEN;
K=(N-DEN)/DELDEN;
if (K==0) goto L400;
for (I=0; I<K; I++) {
M=M+1;
R[2*M]=NUM;
R[2*M+1]=DEN;
NUM=NUM+DELNUM;
DEN=DEN+DELDEN;
}
L400: M=M+1;
R[2*M]=NUM;
R[2*M+1]=DEN;
//
// decrease in denominator, pop a fraction off the stack
//
L500: NUM=STACK[2*SP];
DEN=STACK[2*SP+1];
SP=SP-1;
M=M+1;
R[2*M]=NUM;
R[2*M+1]=DEN;
if (SP>0) goto L100;
//
STACK[0]=NUM;
STACK[1]=DEN;
return(M);
}
//
// GENERATE A FAREY SERIES
//
/* This C subroutine generates the fractions in a Farey series after two given successive fractions in the series. The calling sequence of the subroutine is; */
//
// "N" is the order of the Farey series
// "M" is the index of the previous fraction
// "R" is the output array (large enough to hold the Farey series)
// "NUM" is the numerator of the current fraction
// "DEN" is the denominator of the current fraction
// "OLDNUM" is the numerator of the previous fraction
// "OLDDEN" is the denominator of the previous fraction
// "STACK" is a temporary array (having 2N elements)
//
void farey(unsigned int N, unsigned int M, unsigned int *R, unsigned int NUM, unsigned int DEN, unsigned int OLDNUM, unsigned int OLDDEN, unsigned int *STACK) {
unsigned int I,J,K,SP,DELNUM,DELDEN;
//
// store last fraction and current fraction
//
R[2*M]=OLDNUM;
R[2*M+1]=OLDDEN;
M=M+1;
R[2*M]=NUM;
R[2*M+1]=DEN;
if (DEN==1) goto L500;
if (DEN<OLDDEN) goto L300;
//
// increase in denominator
//
DELNUM=NUM-OLDNUM;
DELDEN=DEN-OLDDEN;
K=(N-DEN)/DELDEN;
if (K!=0) goto L100;
if (DELDEN<OLDDEN) goto L200;
goto L400;
L100: for (I=0; i<K; I++) {
NUM=NUM+DELNUM;
DEN=DEN+DELDEN;
M=M+1;
R[2*M]=NUM;
R[2*M+1]=DEN;
}
L200: NUM=DELNUM;
DEN=DELDEN;
M=M+1;
R[2*M]=NUM;
R[2*M+1]=DEN;
if (DEN==1) goto L500;
//
// decrease in denominator
//
L300: J=OLDDEN/DEN;
OLDNUM=OLDNUM-J*NUM;
OLDDEN=OLDDEN-J*DEN;
L400: J=DEN/OLDDEN;
if (OLDNUM==0) J=J-1;
//
// push fractions on the stack
//
NUM=NUM-J*OLDNUM;
DEN=DEN-J*OLDDEN;
SP=0;
for (I=0; I<J; I++) {
SP=SP+1;
STACK[2*SP]=NUM;
STACK[2*SP+1]=DEN;
NUM=NUM+OLDNUM;
DEN=DEN+OLDDEN;
}
M=rank(N,M,R,NUM,DEN,SP,STACK);
NUM=STACK[0];
DEN=STACK[1];
if (DEN!=1) goto L300;
L500: return;
}
An explanation of the algorithm is as follows. The numerator and denominator of the current fraction are denoted by "NUM" and "DEN" respectively and the numerator and denominator of the previous fraction are denoted by "OLDNUM" and "OLDDEN" respectively. Denote NUM-OLDNUM and DEN-OLDDEN by "DELNUM" and "DELDEN" respectively. If the denominators are increasing (DELDEN>0), the next K=(N-DEN)/DELDEN fractions in the Farey series correspond to the remaining lattice points on the line between (OLDNUM,OLDDEN) and (NUM,DEN) and the numerator and denominator of the fraction following these fractions are DELNUM and DELDEN respectively. If K≠0, these fractions are stored in the Farey series array ("R") and the current fraction set to the last fraction (DELNUM/DELDEN). If K≠0, DELDEN is less than OLDDEN, so that the current fraction has been adjusted so that OLDDEN>DEN. If K=0 and DELDEN is less than OLDDEN, the current fraction is set to the last fraction (DELNUM/DELDEN) and the current fraction stored in the R array. If K=0 and OLDDEN<DEN, then OLDDEN is less than the denominator of the previous fraction in the Farey series so that (OLDNUM,OLDDEN) is an inflection point in the lattice of points corresponding to the fractions in the Farey series. OLDNUM and OLDDEN are adjusted (in a loop) so that (OLDNUM,OLDDEN) is an inflection point by taking OLDNUM modulo NUM and OLDDEN modulo DEN (computing OLDNUM/NUM is not necessary since OLDNUM/NUM equals OLDDEN/DEN). NUM and DEN are then adjusted so that (NUM,DEN) is a following inflection point by taking NUM modulo OLDNUM (when OLDNUM>1) and DEN modulo OLDDEN. (When OLDNUM≥2, NUM/OLDNUM equals DEN/OLDDEN and when OLDNUM=1, NUM/OLDNUM-1 equals DEN/OLDDEN.) When OLDNUM<2, NUM is set to NUM-(DEN/OLDDEN)*OLDNUM. The fractions corresponding to the lattice points on the line between (NUM, DEN) (before adjustment) and the adjusted (NUM,DEN) values are pushed on the stack beginning with the fraction corresponding to the adjusted (NUM,DEN) value and ending with the fraction corresponding to the point after (NUM,DEN). If OLDNUM=0, the number of fractions to be pushed on the stack is decreased by one to avoid pushing the fraction 1/0 on the stack. The fractions in the Farey series between NUM/DEN and the adjusted NUM/DEN value are then computed using the unadjusted NUM/DEN value and the fractions pushed on the stack. For each iteration of the loop, (OLDNUM,OLDDEN) becomes an inflection point further back in the Farey series and (NUM,DEN) becomes an inflection point further forward in the Farey series so that (OLDNUM,OLDDEN) eventually becomes the first fraction in the Farey series ((0,1)) and (NUM,DEN) eventually becomes the last fraction in the Farey series ((1,1)). Since OLDDEN is set to OLDDEN modulo DEN, and DEN is set to DEN modulo OLDDEN, (NUM,DEN) and (OLDNUM,OLDDEN) rapidly converge to their final values. For repeated applications of the functions B=B modulo A, and A=A modulo B, the slowest converging initial values (A,B) are two consecutive Fibonacci numbers. For Farey series of orders less than 1000, fewer than 17 iterations of the loop would be required. This technique can be used to compute the fractions in a Farey series before two given successive fractions by complementing the given successive fractions and computing the fractions after the complements.
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.
