/[dtapublic]/pubs/books/ucbka/trunk/c_fry0/c_fry0.tex
ViewVC logotype

Annotation of /pubs/books/ucbka/trunk/c_fry0/c_fry0.tex

Parent Directory Parent Directory | Revision Log Revision Log


Revision 277 - (hide annotations) (download) (as text)
Tue Aug 13 02:35:39 2019 UTC (3 years, 5 months ago) by dashley
File MIME type: application/x-tex
File size: 69134 byte(s)
Change keyword substitution (migration from cvs to svn).
Add quotation.
1 dashley 140 %$Header$
2    
3     \chapter{\cfryzerolongtitle{}}
4    
5     \label{cfry0}
6    
7     \beginchapterquote{``\ldots{} Beauty is the first test: there is no permanent
8     place in the world for ugly mathematics.''}
9     {G. H. Hardy \cite[p.85]{bibref:b:mathematiciansapology:1940}}
10     \index{Hardy, G. H.}
11    
12     \section{Introduction}
13     %Section Tag: INT
14     \label{cfry0:sint}
15    
16     The \emph{Farey series
17     of order $N$},\index{Farey series} denoted $F_{N}$,\index{F@$F_N$}
18     is the ordered set of all irreducible
19     rational numbers $h/k$ in the interval
20     [0,1]
21     with denominator $k\leq N$.
22     As examples, the Farey series of
23     orders 1 through 7, $F_1$ through $F_7$, are shown
24     in (\ref{eq:cfry0:sint:eq0001a}) through (\ref{eq:cfry0:sint:eq0001g}).
25    
26     \begin{equation}
27     \label{eq:cfry0:sint:eq0001a}
28     F_1 = \left\{ {\frac{0}{1},\frac{1}{1}} \right\}
29     \end{equation}
30    
31     \begin{equation}
32     \label{eq:cfry0:sint:eq0001b}
33     F_2 = \left\{ {\frac{0}{1},\frac{1}{2},\frac{1}{1}} \right\}
34     \end{equation}
35    
36     \begin{equation}
37     \label{eq:cfry0:sint:eq0001c}
38     F_3 = \left\{ {\frac{0}{1},\frac{1}{3},\frac{1}{2},
39     \frac{2}{3},\frac{1}{1}} \right\}
40     \end{equation}
41    
42     \begin{equation}
43     \label{eq:cfry0:sint:eq0001d}
44     F_4 = \left\{ {\frac{0}{1},\frac{1}{4},
45     \frac{1}{3},\frac{1}{2},
46     \frac{2}{3},\frac{3}{4},
47     \frac{1}{1}} \right\}
48     \end{equation}
49    
50     \begin{equation}
51     \label{eq:cfry0:sint:eq0001e}
52     F_5 = \left\{ {\frac{0}{1},\frac{1}{5},\frac{1}{4},
53     \frac{1}{3},\frac{2}{5},\frac{1}{2},
54     \frac{3}{5},\frac{2}{3},\frac{3}{4},
55     \frac{4}{5},\frac{1}{1}} \right\}
56     \end{equation}
57    
58     \begin{equation}
59     \label{eq:cfry0:sint:eq0001f}
60     F_6 = \left\{ {\frac{0}{1},\frac{1}{6},\frac{1}{5},
61     \frac{1}{4},
62     \frac{1}{3},\frac{2}{5},\frac{1}{2},
63     \frac{3}{5},\frac{2}{3},
64     \frac{3}{4},
65     \frac{4}{5},
66     \frac{5}{6},\frac{1}{1}} \right\}
67     \end{equation}
68    
69    
70     \begin{equation}
71     \label{eq:cfry0:sint:eq0001g}
72     F_7 = \left\{ {\frac{0}{1},\frac{1}{7},\frac{1}{6},\frac{1}{5},
73     \frac{1}{4},\frac{2}{7},
74     \frac{1}{3},\frac{2}{5},\frac{3}{7},\frac{1}{2},
75     \frac{4}{7},\frac{3}{5},\frac{2}{3},
76     \frac{5}{7},\frac{3}{4},
77     \frac{4}{5},
78     \frac{5}{6},\frac{6}{7},\frac{1}{1} } \right\}
79     \end{equation}
80    
81    
82     The distribution of Farey rational numbers in
83     [0,1] is repeated
84     in any
85     $[i,i+1]$, $i\in \vworkintset$; so that the distribution of
86     Farey rationals in [0,1] supplies complete
87     information about the distribution in
88     all of $\vworkrealset$. We
89     occasionally abuse the proper nomenclature by referring
90     to sequential rational numbers outside the
91     interval [0,1] as Farey terms or as part of
92     $F_N$, which, technically, they are not.
93     All of the results presented in
94     this chapter, with the exception of results concerning the number
95     of terms, can be shown to apply
96     everywhere in $\vworkrealsetnonneg$, so this abuse
97     is not harmful.
98    
99     The study of the Farey series is a topic from number theory
100     (a branch of mathematics). The Farey series finds application
101     in microcontroller work because very often it is economical
102     to linearly scale an integer $x$ using a rational approximation
103     of the form $\lfloor hx/k \rfloor$, $h \in \vworkintsetnonneg$,
104     $k \in \vworkintsetpos$ (a single integer multiplication followed by
105     a single integer division with the remainder discarded).
106     The economy of this type of linear scaling comes about because
107     many microcontrollers have integer multiplication and division
108     instructions. However, the technique requires that we be
109     able to choose $h$ and $k$ so as to place $h/k$ as close
110     as possible to the real number $r_I$ that we wish to
111     approximate; always subject to the constraints
112     $h \leq{} h_{MAX}$ and $k \leq k_{MAX}$ (since microcontroller
113     multiplication and division instructions are constrained in
114     the size of the operands they can accomodate).
115    
116     Without the relevant results from number theory, it is
117     very difficult to find the rational numbers $h/k$:
118     $h \in \vworkintsetnonneg, \leq{} h_{MAX}$, $k \in \vworkintsetpos, \leq k_{MAX}$
119     closest to
120     an arbitrary $r_I \in \vworkrealsetnonneg$, even for moderate
121     choices of $h_{MAX}, k_{MAX}$ (see Example \ref{ex:cfry0:sint:01}).
122     A poorly-written brute-force
123     algorithm might iterate over all $h$ and all $k$ to find the
124     rational numbers closest to $r_I$; and thus might be
125     approximately $O(h_{MAX} k_{MAX})$. A refined brute-force
126     algorithm might refine the search and be approximately
127     $O(min(h_{MAX}, k_{MAX}))$. However, for implementation on powerful
128     computers which have machine instructions to multiply and
129     divide large integers, or for extended-precision integer arithmetic, even algorithms
130     which are $O(min(h_{MAX}, k_{MAX}))$ are not practical. The best
131     algorithm presented in this work (utilizing the
132     framework of continued fractions), is $O(log \; max(h_{MAX}, k_{MAX}))$,
133     and so is practical even for very large $h_{MAX}$ and $k_{MAX}$.
134    
135     \begin{vworkexamplestatement}
136     \label{ex:cfry0:sint:01}
137     Find the rational numbers
138     $h/k$ which enclose $1/e \approx 0.3678794412$
139     subject to the constraint $k \leq 2^{16} - 1 = 65\vworkthousandsdigsepinmathmode{}535$.%
140     \footnote{This example is intended to demonstrate the difficulty of
141     finding suitable rational numbers near an arbitrary $r_I$ without the
142     relevant results from number theory.}
143     \end{vworkexamplestatement}
144     \begin{vworkexampleparsection}{Solution}
145     $1/e$ is irrational, and so has left and right neighbors in
146     the Farey series of any order. Using algorithms that will be presented later in the
147     work, these two enclosing rational numbers subject to the
148     constraint $k \leq 2^{16}-1$ are
149     $18\vworkthousandsdigsepinmathmode{}089/49\vworkthousandsdigsepinmathmode{}171$
150     and
151     $9\vworkthousandsdigsepinmathmode{}545/25\vworkthousandsdigsepinmathmode{}946$.
152     \end{vworkexampleparsection}
153     \vworkexamplefooter{}
154    
155     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
156     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
157     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
158     \section{History Of The Farey Series}
159     %Section tag: HFS
160    
161     \index{Farey series!history of}
162     The Farey series owes its name to John Farey,
163     \index{Farey, John} a British geologist who in 1816
164     published the statement to the effect that in the Farey series the middle
165     of any three consecutive terms is the mediant of the other two
166     \cite{bibref:w:CutTheKnotMainPage}\footnote{\label{fn:cfry0:hfs01}Exact URL:
167     \texttt{http://www.cut-the-knot.com/blue/FareyHistory.html}.} (Thm.
168     \ref{thm:cfry0:spfs:03} in this work).
169     However, many mathematicians
170     believe that credit for the Farey series is misplaced, and that the
171     series should not have been named after Farey. In
172     \emph{A Mathematician's Apology}
173     \cite[pp. 81-82]{bibref:b:mathematiciansapology:1940},
174     Hardy cites the Farey series as one of the rare examples in scientific
175     history where credit is misplaced:
176    
177     \begin{indentedquote}
178     ``\ldots{} Farey is immortal because he failed to understand a theorem
179     which Haros had proved perfectly fourteen years
180     before \ldots{} but on the whole the history of science is fair, and
181     this is particularly
182     true in mathematics \ldots{} and the men who are remembered are almost
183     always the men who merit it.''
184     \end{indentedquote}
185    
186     Hardy and Wright also provide a footnote about the history
187     of the Farey series, \cite[pp. 36-37]{bibref:b:HardyAndWrightClassic}:
188    
189     \begin{indentedquote}
190     ``The history of the Farey series is very curious.
191     Theorems 28 and 29\footnote{Theorems
192     \ref{thm:cfry0:spfs:02} and \ref{thm:cfry0:spfs:03},
193     respectively, in this chapter.} seem to have been stated and proved first by
194     Haros in 1802; see Dickson, \emph{History}, i. 156.
195     Farey did not publish anything on the subject until
196     1816, when he stated Theorem 29 in a note in the
197     \emph{Philosophical Magazine}. He gave no proof, and it is unlikely that he
198     had found one, since he seems to have been at the best an
199     indifferent mathematician.
200    
201     Cauchy, however, saw Farey's statement, and supplied the
202     proof (\emph{Exercices de math\'ematiques}, i. 114-116). Mathematicians
203     generally have followed Cauchy's example in attributing the results to
204     Farey, and the results will no doubt continue to bear his name.''
205     \end{indentedquote}
206    
207     \cite{bibref:w:CutTheKnotMainPage}$^{\ref{fn:cfry0:hfs01}}$ contains the best
208     account of the history of the Farey series on the Web (and contains
209     information on many other
210     interesting topics related to mathematics and number theory, as well). At this
211     site, Dr. Alexander Bogomolny
212     \index{Bogomolny, Alexander} has included John Farey's
213     original letter to the \emph{Philosophical Magazine}, and much historical
214     and human perspective. This site is highly recommended for anyone who has
215     an interest in mathematics, number theory, and history.
216    
217    
218     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
219     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
220     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
221    
222     \section{Properties Of Terms Of The Farey Series}
223     %Section tag: PFS
224    
225     \index{Farey series!properties of}
226     In Section \ref{cfry0:sint}, we hinted that the properties
227     of the Farey series (which, technically,
228     consists of irreducible rational numbers $h/k$
229     only in $[0,1]$) hold in any interval $[n,n+1]$,
230     $n \in \vworkintsetpos$. We would first like to show
231     that if $h/k \in [0,1]$ is irreducible, then
232     any of its corresponding rational numbers $(h+ik)/k$ in
233     $[i,i+1]$, $i \in \vworkintsetpos$ are also irreducible.
234    
235     \begin{vworktheoremstatement}
236     \label{thm:cfry0:spfs:01}
237     Iff $h/k$, $k \in \vworkintsetpos$, $h \in \{0, 1, \ldots{}, k\}$
238     is irreducible, then
239    
240     \begin{equation}
241     \frac{h}{k} + i = \frac{h + ik}{k}
242     \end{equation}
243    
244     is also irreducible for $i \in \vworkintsetnonneg$.
245     \end{vworktheoremstatement}
246     \begin{vworktheoremproof}
247     Let $\{p_k^{a_k}\} = p_1^{a_1} p_2^{a_2} \ldots{} p_M^{a_M}$ be the prime
248     factorization of $h$.
249     Let $\{q_k^{b_k}\} = q_1^{b_1} q_2^{b_2} \ldots{} q_M^{b_M}$ be the prime
250     factorization of $k$. The coprimality of $h$ and $k$ ensures that
251     $\{p_k^{a_k}\} \bigcap \{q_k^{b_k}\} = \oslash$. We are interested in the
252     irreducibility (or lack thereof) of
253    
254     \begin{equation}
255     \label{eq:cfry0:spfs:01}
256     \frac{h}{k} + i =
257     \frac{p_1^{a_1} p_2^{a_2} \ldots{} p_M^{a_M} +
258     i(q_1^{b_1} q_2^{b_2} \ldots{} q_N^{b_N})}
259     {q_1^{b_1} q_2^{b_2} \ldots{} q_N^{b_N}}
260     \end{equation}
261    
262     In order for the expression in (\ref{eq:cfry0:spfs:01}) to be reducible,
263     it is necessary for at least one $q_k \in \{q_1, q_2, \ldots{}, q_N\}$
264     to divide the numerator, which is possible only if
265     $\{p_k\} \bigcap \{q_k\} \neq \oslash$. (The degenerate cases
266     of $h=1$ or $k=1$ are left for the reader as
267     Exercise \ref{exe:cfry0:sexe0:01}.)
268     \end{vworktheoremproof}
269     \begin{vworktheoremparsection}{Remarks}
270     On the other hand, if $h/k$ is reducible, let
271     $\{p_k^{a_k}\} = p_1^{a_1} p_2^{a_2} \ldots{} p_M^{a_M}$
272     be the prime factors of $h$ which do not appear in $k$, let
273     $\{q_k^{b_k}\} = q_1^{b_1} q_2^{b_2} \ldots{} q_N^{b_N}$
274     be the prime factors of $k$ which do not appear in $h$,
275     and let
276     $\{s_k^{c_k}\} = s_1^{c_1} s_2^{c_2} \ldots{} s_L^{c_L}$
277     be the prime factors which appear in both $h$ and $k$.
278     We are interested in the irreducibility (or lack thereof)
279     of
280    
281     \begin{equation}
282     \label{eq:cfry0:spfs:02}
283     \frac{h}{k} + i =
284     \frac{ \{ s_k^{c_k} \} \{ p_k^{a_k} \} + i \{ s_k^{c_k} \} \{ q_k^{b_k} \} }
285     { \{ s_k^{c_k} \} \{ q_k^{b_k} \} }.
286     \end{equation}
287    
288     It is clear that any choice of
289     $i \in \vworkintsetnonneg$ will allow $\{s_k^{c_k}\}$
290     to divide both the numerator and the denominator.
291     \end{vworktheoremparsection}
292     \vworktheoremfooter{}
293    
294     \index{rational number!comparison of}
295     Very frequently, it is necessary to compare rational numbers
296     to determine if they are equal; and if not, which is larger.
297     This need occurs both in symbolic manipulation (derivations and
298     proofs), and in calculations. We present a property which is
299     useful for comparison of non-negative rational numbers.
300    
301     \begin{vworklemmastatement}
302     \label{lem:cfry0:spfs:02b}
303     For $a,c \geq 0$ and $b,d > 0$,
304    
305     \begin{equation}
306     \begin{array}{lr}
307     \displaystyle{\frac{a}{b} < \frac{c}{d}}, & iff \;\; ad < bc \\
308     & \\
309     \displaystyle{\frac{a}{b} = \frac{c}{d}}, & iff \;\; ad = bc \\
310     & \\
311     \displaystyle{\frac{a}{b} > \frac{c}{d}}, & iff \;\; ad > bc
312     \end{array}
313     \end{equation}
314     \end{vworklemmastatement}
315     \begin{vworklemmaproof}
316     Assume $a,c \geq 0$ and $b,d > 0$.
317     Under these assumptions, $a/b < c/d \vworkequiv a < bc/d \vworkequiv ad < bc$.
318     Similarly, under the same assumptions,
319     $a/b = c/d \vworkequiv a = bc/d \vworkequiv ad = bc$ and
320     $a/b > c/d \vworkequiv a > bc/d \vworkequiv ad > bc$.
321     \end{vworklemmaproof}
322     \begin{vworklemmaparsection}{Remarks}
323     Note it is not required that
324     $a, b, c, d \in \vworkintset$, although this is the way in which
325     the lemma is used exclusively in this work. Note also that the lemma does
326     not cover the case when any of the components $a,b,c,d$ are $<0$.
327     For comparing rational numbers
328     \index{rational number!comparison of}
329     with non-negative components, this lemma presents
330     the most convenient method.
331     \end{vworklemmaparsection}
332     \vworklemmafooter{}
333    
334     Some properties and results concerning the Farey series rely
335     on the \emph{mediant}\index{mediant}\index{rational number!mediant of}
336     of two rational numbers,
337     which is defined now.
338    
339     \begin{vworkdefinitionstatementpar}{Mediant}
340     \label{def:cfry0:spfs:02}
341     The \emph{mediant} of two [irreducible] rational numbers
342     $h/k$ and $h'/k'$ is the [reduced form of the] fraction
343     \begin{equation}
344     \frac{h+h'}{k+k'} .
345     \end{equation}
346     \end{vworkdefinitionstatementpar}
347     \begin{vworkdefinitionparsection}{Remarks}
348     Note that the mediant of two rational numbers---even
349     irreducible rational numbers---is not necessarily irreducible.
350     For example, the mediant of 1/3 and 2/3 is 3/6, which is
351     not irreducible. Note also that the mediant of two rational
352     numbers is ambiguously defined if we don't require that the
353     rational numbers be irreducible. For example,
354     the mediant of 1/3 and 2/3 is 3/6 = 1/2, but the
355     mediant of 2/6 and 2/3 is 4/9 (a different number than
356     1/2). Normally, in this work, we will calculate the mediant
357     only of irreducible rational numbers, and we will define
358     the result to be the reduced form of the fraction calculated.
359     \end{vworkdefinitionparsection}
360     \vworkdefinitionfooter{}
361    
362     The mediant of two rational numbers always lies between them in value (but
363     is not necessarily the midpoint). A somewhat stronger
364     statement about mediants can be made, and is
365     presented as Lemma \ref{lem:cfry0:spfs:02c}, below.
366    
367     \begin{vworklemmastatement}
368     \label{lem:cfry0:spfs:02c}
369     For
370     $a,c \geq 0$,
371     $b,d,i,j > 0$, and
372     $a/b < c/d$,
373    
374     \begin{equation}
375     \frac{a}{b} < \frac{ia + jc}{ib + jd} < \frac{c}{d} ,
376     \end{equation}
377    
378     or, equivalently,
379    
380     \begin{equation}
381     \frac{ia + jc}{ib + jd} \in \left( { \frac{a}{b} , \frac{c}{d} } \right) .
382     \end{equation}
383    
384     \end{vworklemmastatement}
385     \begin{vworklemmaproof}
386     Under the restrictions on $a,b,c,d,i$, and $j$;
387     $ad < bc \vworkhimp ijad < ijbc \vworkhimp i^2ab+ijad < i^2ab + ijbc$
388     $\vworkhimp ia(ib+jd) < ib(ia+jc) \vworkhimp ia/ib < (ia+jc)/(ib+jd)$
389     (employing Lemma \ref{lem:cfry0:spfs:02b}). A similar implication
390     can be used to show that $(ia+jc)/(ib+jd) < jc/jd$.
391     \end{vworklemmaproof}
392     \begin{vworklemmaparsection}{Remarks}
393     A special case of this lemma is the result that the mediant of two
394     rational numbers is always between them ($i=j=1$). This lemma gives
395     some insight into the arrangement of
396     intermediate fractions\index{intermediate fraction}\index{continued fraction!intermediate fraction}
397     between
398     two convergents\index{continued fraction!convergent}
399     (see \ccfrzeroxrefcomma{}\ccfrzeromcclass{} \ref{ccfr0},
400     \emph{\ccfrzeroshorttitle{}}).
401     \end{vworklemmaparsection}
402     %\vworklemmafooter{}
403    
404     \begin{vworktheoremstatement}
405     \label{thm:cfry0:spfs:02ba}
406     If $h/k$ and $h'/k'$ are two successive terms
407     of $F_N$, then $k + k' > N$.
408     \end{vworktheoremstatement}
409     \begin{vworktheoremproof}
410     By Lemma \ref{lem:cfry0:spfs:02c},
411     the mediant of $h/k$ and $h'/k'$ lies between them, i.e.
412    
413     \begin{equation}
414     \label{eq:cfry0:spfs:02baa}
415     \frac{h + h'}{k + k'} \in \left( { \frac{h}{k}, \frac{h'}{k'}} \right) .
416     \end{equation}
417    
418     Note that if $k+k' \leq N$, the denominator of the mediant, $k+k'$, is less than
419     $N$, so that either the fraction specified by (\ref{eq:cfry0:spfs:02baa}) or its
420     reduced form is in $F_N$; hence there is another term between $h/k$ and
421     $h'/k'$ in $F_N$. (See \cite[Thm. 30, p. 23]{bibref:b:HardyAndWrightClassic}.)
422     \end{vworktheoremproof}
423     %\vworktheoremfooter{}
424    
425     \begin{vworktheoremstatement}
426     \label{thm:cfry0:spfs:02c}
427     For $N > 1$, no two consecutive terms of $F_N$ have the
428     same denominator.
429     \end{vworktheoremstatement}
430     \begin{vworktheoremproof}
431     Assume that $h/k$ and $h'/k$ are the two consecutive terms with
432     the same denominator. Note that the only choice of $h'$ which
433     could be the numerator of a consecutive term is $h'=h+1$; otherwise
434     we would have $h/k < (h+1)/k < h'/k$, which implies that $h/k$
435     and $h'/k'$ are not consecutive, a contradiction. With
436     $h'=h+1$ (the only possibility), let's examine the inequality $h/k < h/(k-1) < (h+1)/k$.
437     $h/k < h/(k-1)$ is always true for any choice of $k>1$.
438     It can be shown using Lemma \ref{lem:cfry0:spfs:02b}
439     that $h/(k-1) < (h+1)/k$ is true iff $h < k -1$. So,
440     for any $h \in \{2, \ldots{} , k - 2 \}$, we can always use
441     the fraction $h/(k-1)$ as an intermediate term to show that
442     $h/k$ and $(h+1)/k$ are not consecutive in $F_N$.
443     If $h=k-1$, then we are considering the two fractions
444     $(k-1)/k$ and $k/k$, and $k/k$ cannot be in lowest
445     terms---after reducing $k/k$ the two fractions
446     being considered no longer have the
447     same denominator. (See \cite[Thm. 31, p. 24]{bibref:b:HardyAndWrightClassic}.)
448     \end{vworktheoremproof}
449     %\vworktheoremfooter{}
450    
451     \begin{vworktheoremstatement}
452     \label{thm:cfry0:spfs:02}
453     If $h/k$ and $h'/k'$ are two successive terms of $F_N$, then
454    
455     \begin{equation}
456     \label{eq:cfry0:spfs:thm02aa}
457     h'k - h k' = 1.
458     \end{equation}
459     \end{vworktheoremstatement}
460    
461     \begin{vworktheoremproof}
462     For any $h/k$, Lemma \cprizeroxrefhyphen\ref{lem:cpri0:ppn0:00a} guarantees
463     that an $h'/k'$ satisfying (\ref{eq:cfry0:spfs:thm02aa}) exists.
464     If $h'=x_0, k'=y_0$ is a solution, then
465     $h'=x_0 + r h, k'=y_0 + r k, r \in \vworkintset$ is also
466     a solution, and Lemma \cprizeroxrefhyphen\ref{lem:cpri0:ppn0:000p}
467     guarantees that any $h', k'$ so chosen will be coprime.
468     Note that $r$ can be chosen so that $0 \leq N-k < k' \leq N$, and
469     that h'/k' will be $\in F_N$.
470    
471     However, it still needs to be established that $h'/k'$ is the
472     \emph{next} term in $F_N$ (i.e. that there can be no intervening
473     terms). To show this, assume that an intervening term
474     $a/b$ exists, so that $h/k < a/b < h'/k'$, with $b \leq N$.
475     In this case, the distance from $h/k$ to $a/b$ is
476    
477     \begin{equation}
478     \label{eq:cfry0:spfs:thm02ab}
479     \frac{a}{b}-\frac{h}{k} = \frac{ak-bh}{bk} \geq \frac{1}{bk} .
480     \end{equation}
481    
482     Similarly, the distance from $a/b$ to $h'/k'$ is
483    
484     \begin{equation}
485     \label{eq:cfry0:spfs:thm02ab2}
486     \frac{h'}{k'}-\frac{a}{b} = \frac{h'b-k'a}{k'b} \geq \frac{1}{k'b} .
487     \end{equation}
488    
489     (The inequalities in Eqns. \ref{eq:cfry0:spfs:thm02ab}
490     and \ref{eq:cfry0:spfs:thm02ab2} come
491     about through Lemma \ref{lem:cfry0:spfs:02b}---the numerator
492     in each case must be at least $1$ if it is assumed
493     $h/k < a/b < h'/k'$.)
494    
495     The distance from $h/k$ to $h'/k'$ is
496    
497     \begin{equation}
498     \label{eq:cfry0:spfs:thm02ac}
499     \frac{h'}{k'}-\frac{h}{k} = \frac{h'k-hk'}{kk'} = \frac{1}{kk'} .
500     \end{equation}
501    
502     The distance from $h/k$ to $h'/k'$ must be the sum of the distances
503     from $h/k$ to $a/b$ and from $a/b$ to $h'/k'$:
504    
505     \begin{equation}
506     \label{eq:cfry0:spfs:thm02ad}
507     \left( { \frac{h'}{k'} - \frac{h}{k} } \right)
508     =
509     \left( { \frac{a}{b} - \frac{h}{k} } \right)
510     +
511     \left( { \frac{h'}{k'} - \frac{a}{b} } \right) .
512     \end{equation}
513    
514     Substituting (\ref{eq:cfry0:spfs:thm02ab}),
515     (\ref{eq:cfry0:spfs:thm02ab2}),
516     and (\ref{eq:cfry0:spfs:thm02ac})
517     into (\ref{eq:cfry0:spfs:thm02ad}) leads
518     to
519    
520     \begin{equation}
521     \label{eq:cfry0:spfs:thm02ae}
522     \frac{1}{kk'}
523     \geq
524     \frac{1}{bk}+\frac{1}{k'b}
525     =\frac{k'}{bkk'}+\frac{k}{bkk'}
526     =\frac{k'+k}{bkk'}
527     >
528     \frac{N}{bkk'}
529     >
530     \frac{1}{kk'} ,
531     \end{equation}
532    
533     a contradiction. Therefore, $a/b$ must be $h'/k'$ and
534     $h'k-hk'=1$. (See \cite{bibref:b:HardyAndWrightClassic}, Thm. 28, p. 23,
535     and the second proof on pp. 25-26.)
536     \end{vworktheoremproof}
537     %\vworktheoremfooter{}
538    
539     \begin{vworklemmastatement}
540     \label{lem:cfry0:spfs:03b}
541     For $h/k$, $h'/k'$ and $h''/k''$; $h, h', h'' \in \vworkintsetnonneg$,
542     $k, k', k'' \in \vworkintsetpos$, with
543    
544     \begin{equation}
545     h'k-hk' = h''k'-h'k''=1 ,
546     \end{equation}
547    
548     \begin{equation}
549     (k'>k'') \vworkhimp
550     \left( {
551     \frac{h'}{k'}-\frac{h}{k}<\frac{h''}{k''}-\frac{h}{k}
552     } \right) .
553     \end{equation}
554     \end{vworklemmastatement}
555     \begin{vworklemmaproof}
556     \begin{equation}
557     \frac{h'}{k'}-\frac{h}{k} = \frac{1}{kk'}
558     \end{equation}
559     \begin{equation}
560     \frac{h''}{k''}-\frac{h}{k} = \frac{1}{kk''}
561     \end{equation}
562     \begin{equation}
563     (k' > k'') \vworkhimp \left( {
564     \frac{1}{kk'} < \frac{1}{kk''}
565     } \right)
566     \end{equation}
567     \end{vworklemmaproof}
568     \begin{vworklemmaparsection}{Remarks}
569     This lemma essentially says that if more than one potential successor to
570     $h/k$ in $F_N$, $h'/k'$ and $h''/k''$, both meet the necessary test
571     provided by Theorem \ref{thm:cfry0:spfs:02}, the potential successor
572     with the largest denominator is the successor, because it is closer to
573     $h/k$. This lemma is used in proving Theorem \ref{thm:cfry0:sgfs0:01}.
574     \end{vworklemmaparsection}
575     %\vworklemmafooter{}
576    
577     \begin{vworktheoremstatement}
578     \label{thm:cfry0:spfs:03}
579     If $h/k$, $h'/k'$, and $h''/k''$ are three successive terms of $F_N$, then
580    
581     \begin{equation}
582     \frac{h'}{k'} = \frac{h+h''}{k+k''}.
583     \end{equation}
584     \end{vworktheoremstatement}
585     \begin{vworktheoremproof}
586     Starting from Theorem \ref{thm:cfry0:spfs:02}:
587     \begin{equation}
588     h'k-hk' = h''k' - h'k''=1
589     \end{equation}
590     \begin{equation}
591     h'(k+k'')=k'(h+h'')
592     \end{equation}
593     \begin{equation}
594     \frac{h'}{k'} = \frac{h+h''}{k+k''}.
595     \end{equation}
596     \end{vworktheoremproof}
597     \vworktheoremfooter{}
598    
599    
600     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
601     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
602     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
603     \section{Generation Of Terms Of The Farey Series}
604     \label{cfry0:sgfs0}
605     %Section tag: GFS0
606    
607    
608     \index{Farey series!generation of terms}
609     Earlier sections of this chapter have enumerated important properties of the
610     Farey series. However, these properties are of limited practical value
611     because they don't help to solve practical problems in microcontroller
612     work---one would like to be able to generate (in order, of course) all of
613     the terms of a Farey series so that one can choose suitable terms
614     near some $r_I \in \vworkrealsetnonneg$ that one wishes to approximate
615     with $r_A = h/k$.
616    
617     Fortunately, the properties presented in earlier sections do allow the
618     generation of successive Farey terms, as the following theorem shows.
619    
620     \begin{vworktheoremstatement}
621     \label{thm:cfry0:sgfs0:01}
622     For a Farey series of order $N$,
623    
624     \begin{equation}
625     F_N = \left\{ {
626     \frac{h_0}{k_0},
627     \frac{h_1}{k_1},
628     \frac{h_2}{k_2},
629     \frac{h_3}{k_3},
630     \ldots
631     } \right\} ,
632     \end{equation}
633    
634     the recursive relationships in
635     (\ref{eq:cfry0:sgfs0:thm:01:eq01}),
636     (\ref{eq:cfry0:sgfs0:thm:01:eq02}),
637     (\ref{eq:cfry0:sgfs0:thm:01:eq03}), and
638     (\ref{eq:cfry0:sgfs0:thm:01:eq04}) apply.
639     \index{Farey series!recursive formulas}
640    
641     \begin{equation}
642     \label{eq:cfry0:sgfs0:thm:01:eq01}
643     h_{j} = \left\lfloor {\frac{{k_{j-2}
644     + N}}{{k_{j - 1} }}} \right\rfloor h_{j - 1} - h_{j-2}
645     \end{equation}
646    
647     \begin{equation}
648     \label{eq:cfry0:sgfs0:thm:01:eq02}
649     k_{j} = \left\lfloor {\frac{{k_{j-2} + N}}{{k_{j
650     - 1} }}} \right\rfloor k_{j - 1} - k_{j-2}
651     \end{equation}
652    
653     \begin{equation}
654     \label{eq:cfry0:sgfs0:thm:01:eq03}
655     h_j = \left\lfloor {\frac{{k_{j + 2} + N}}{{k_{j + 1} }}}
656     \right\rfloor h_{j + 1} - h_{j + 2}
657     \end{equation}
658    
659     \begin{equation}
660     \label{eq:cfry0:sgfs0:thm:01:eq04}
661     k_j = \left\lfloor {\frac{{k_{j + 2} + N}}{{k_{j + 1} }}}
662     \right\rfloor k_{j + 1} - k_{j + 2}
663     \end{equation}
664     \end{vworktheoremstatement}
665     \begin{vworktheoremproof}
666     Only (\ref{eq:cfry0:sgfs0:thm:01:eq01}) and
667     (\ref{eq:cfry0:sgfs0:thm:01:eq02}) are
668     proved---(\ref{eq:cfry0:sgfs0:thm:01:eq03}) and
669     (\ref{eq:cfry0:sgfs0:thm:01:eq04}) come by symmetry.
670    
671     Assume that $h_{j-2}/k_{j-2}$ and $h_{j-1}/k_{j-1}$ are known and we wish
672     to find $h_{j}/k_{j}$.
673    
674     Note that by Theorem \ref{thm:cfry0:spfs:02},
675    
676     \begin{equation}
677     \label{eq:cfry0:sgfs0:thm:01:eq05}
678     h_{j-1} k_{j-2} - h_{j-2} k_{j-1} = 1
679     \end{equation}
680    
681     and
682    
683     \begin{equation}
684     \label{eq:cfry0:sgfs0:thm:01:eq06}
685     h_{j} k_{j-1} - h_{j-1} k_{j} = 1 .
686     \end{equation}
687    
688     We desire to identify the set of rational numbers $\{ h_j / k_j \}$ that satisfy
689     (\ref{eq:cfry0:sgfs0:thm:01:eq06}). If this set is identified, by Lemma
690     \ref{lem:cfry0:spfs:03b}, we can simply choose the member of the set that has the
691     largest denominator.
692    
693     Choose as trial solutions
694    
695     \begin{equation}
696     \label{eq:cfry0:sgfs0:thm:01:eq07}
697     h_j = i h_{j-1} - h_{j-2}
698     \end{equation}
699    
700     and
701    
702     \begin{equation}
703     \label{eq:cfry0:sgfs0:thm:01:eq08}
704     k_j = i k_{j-1} - k_{j-2} ,
705     \end{equation}
706    
707     where $i \in \vworkintset$ is an integer parameter; i.e. define
708     as the trial set of solutions all $h_j /k_j$ that can be formed
709     by $i \in \vworkintset$ substituted into
710     (\ref{eq:cfry0:sgfs0:thm:01:eq07}) and
711     (\ref{eq:cfry0:sgfs0:thm:01:eq08}). Substitution of this trial
712     solution into (\ref{eq:cfry0:sgfs0:thm:01:eq06}) yields
713    
714     \begin{equation}
715     \label{eq:cfry0:sgfs0:thm:01:eq09}
716     (i h_{j-1} - h_{j-2}) k_{j-1} - h_{j-1} (i k_{j-1} - k_{j-2} )
717     = h_{j-1} k_{j-2} - h_{j-2} k_{j-1} = 1.
718     \end{equation}
719    
720     Thus, any solution in the form of
721     (\ref{eq:cfry0:sgfs0:thm:01:eq07}, \ref{eq:cfry0:sgfs0:thm:01:eq08})
722     will meet the necessary test posed
723     by Theorem \ref{thm:cfry0:spfs:02}.
724    
725     However, we must also demonstrate that solutions of the form
726     suggested by
727     (\ref{eq:cfry0:sgfs0:thm:01:eq07}, \ref{eq:cfry0:sgfs0:thm:01:eq08})
728     are the \emph{only} solutions which meet
729     the necessary test posed by Theorem \ref{thm:cfry0:spfs:02}, and
730     also demonstrate how to pick the solution of this form
731     with the largest denominator $k_{j} \leq N$.
732    
733     To demonstrate that
734     (\ref{eq:cfry0:sgfs0:thm:01:eq07}, \ref{eq:cfry0:sgfs0:thm:01:eq08})
735     are the only solutions, solve (\ref{eq:cfry0:sgfs0:thm:01:eq06})
736     for $h_j$, yielding
737    
738     \begin{equation}
739     \label{eq:cfry0:sgfs0:thm:01:eq10}
740     h_j = \frac{h_{j-1}}{k_{j-1}} k_j + \frac{1}{k_{j-1}} .
741     \end{equation}
742    
743     Since $h_{j-1}$ and $k_{j-1}$ are known, it is clear that
744     (\ref{eq:cfry0:sgfs0:thm:01:eq10}) defines a required linear relationship
745     between $h_j$ and $k_j$, and that the only solutions are the values of
746     $h_j$ and $k_j$ meeting
747     (\ref{eq:cfry0:sgfs0:thm:01:eq10})
748     which are integers. Assume that a particular integer
749     solution $\overline{h_j}, \overline{k_j}$ to
750     (\ref{eq:cfry0:sgfs0:thm:01:eq10}) is known
751     and that a second integer solution
752     $\widehat{h_j}, \widehat{k_j}$ is sought. In order for
753     $\widehat{h_j}$ to be an integer, it must
754     differ from $\overline{h_j}$ by an
755     integer, implying
756    
757     \begin{equation}
758     \label{eq:cfry0:sgfs0:thm:01:eq11}
759     \frac{h_{j-1}}{k_{j-1}} ( \widehat{k_j} - \overline{k_j} ) \in \vworkintset{} .
760     \end{equation}
761    
762     It is easy to see from the form of (\ref{eq:cfry0:sgfs0:thm:01:eq11}) that
763     because $h_{j-1}$ and $k_{j-1}$ are coprime, in order for
764     (\ref{eq:cfry0:sgfs0:thm:01:eq11}) to be met,
765     $\widehat{k_j} - \overline{k_j}$
766     must contain every prime factor of $k_{j-1}$ in at least
767     equal multiplicity, implying
768     $| \widehat{k_j} - \overline{k_j} | \geq k_{j-1}$. It follows
769     that
770     (\ref{eq:cfry0:sgfs0:thm:01:eq07}, \ref{eq:cfry0:sgfs0:thm:01:eq08})
771     are the only solutions
772     which meet
773     the necessary test posed by Theorem \ref{thm:cfry0:spfs:02}. We only
774     need find the solution with the largest denominator.
775    
776     Solving $i k_{j-1} - k_{j-2} \leq N$ for the largest integral
777     value of $i$ leads to
778    
779     \begin{equation}
780     \label{eq:cfry0:sgfs0:thm:01:eq12}
781     i = \left\lfloor {
782     \frac{k_{j-2} + N}{k_{j-1}}
783     } \right\rfloor
784     \end{equation}
785    
786     and directly to (\ref{eq:cfry0:sgfs0:thm:01:eq01})
787     and (\ref{eq:cfry0:sgfs0:thm:01:eq02}).
788     \end{vworktheoremproof}
789     \vworktheoremfooter{}
790    
791     Given two consecutive Farey terms, Theorem \ref{thm:cfry0:sgfs0:01} suggests
792     a way to generate as many neighboring terms as desired in either the
793     descending or ascending direction. Note that at an integer $i$,
794     $(iN-1)/N$, $i/1$, and $(iN+1)/N$ are always consecutive terms
795     in $F_N$; thus it is typically convenient to build the Farey series
796     starting at an integer. This method is presented as
797     Algorithm \ref{alg:cfry0:sgfs0:02}.
798    
799     \begin{vworkalgorithmstatementpar}{\mbox{\boldmath $O(N^2)$} Exhaustive
800     Construction
801     Algorithm For Finding Enclosing
802     Neighbors To \mbox{\boldmath $r_I$}
803     In \mbox{\boldmath $F_N$}}
804     \label{alg:cfry0:sgfs0:02}
805     \begin{itemize}
806     \item Choose $i = \lfloor r_I + 1/2 \rfloor$ as the integer from which
807     to construct consecutive Farey terms (i.e. the nearest integer
808     to $r_I$).
809    
810     \item Choose $i/1$ and $(iN+1)/N$ as the two consecutive Farey terms from
811     which to start construction.
812    
813     \item Use (\ref{eq:cfry0:sgfs0:thm:01:eq01}) and
814     (\ref{eq:cfry0:sgfs0:thm:01:eq02}) or
815     (\ref{eq:cfry0:sgfs0:thm:01:eq03}) and
816     (\ref{eq:cfry0:sgfs0:thm:01:eq04}) to construct Farey terms
817     in the increasing or decreasing direction until $r_I$ is
818     enclosed.
819     \end{itemize}
820     \end{vworkalgorithmstatementpar}
821     \vworkalgorithmfooter{}
822    
823     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
824     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
825     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
826     \section{Number Of Terms In The Farey Series}
827     %Section tag: NTM0
828    
829     The number of terms\footnote{In the interval $[0,1]$ only.}
830     \index{Farey series!number of terms}
831     $C(N)$ in the Farey series of order $N$, $F_N$, is
832    
833     \begin{equation}
834     C(N) = 1 + \sum_{k=1}^{N} \phi (k) ,
835     \end{equation}
836    
837     \noindent{}where $\phi(\cdot{})$ is Euler's totient
838     function \cite{bibref:w:PkuCnFareyPage}. The
839     asymptotic limit for this function $C(N)$ is
840    
841     \begin{equation}
842     C(N) \sim{} \frac{3 N^2}{\pi{}^2} \approx 0.3040 N^2 .
843     \end{equation}
844    
845     Because the number of terms in $F_N$ is approximately
846     $O(N^2)$, the method presented in the previous section
847     (Algorithm \ref{alg:cfry0:sgfs0:02}) is
848     only practical for moderate $N$ (a few hundred or less). For Farey
849     series of large order, building the Farey series until $r_I$ is
850     enclosed is not a practical method.
851    
852     For example, $F_{2^{32}-1}$ (a Farey series of interest for
853     computer work, because many processors can multiply 32-bit integers)
854     contains about $1.8 \times 10^{19}$ elements. Even using a computer
855     that could generate $10^{9}$ Farey terms per second (an unrealistic
856     assumption at the time of this writing), building
857     $F_{2^{32}-1}$ between two consecutive integers would require over 500
858     years. It is also noteworthy that certainly $2^{32}-1$ is not an upper
859     bound on the order of Farey series that are useful in practice---with
860     scientific computers, it may be advantageous to be able to find best
861     approximations in $F_{2^{64}-1}$, $F_{2^{128}-1}$, or Farey series
862     of even higher order.
863    
864     Algorithm \ref{alg:cfry0:sgfs0:02} is useful to illustrate concepts, or
865     to find best approximations in Farey series of moderate order. However,
866     for Farey series of large order, this algorithm isn't usable.
867     \ccfrzeroxrefcomma{}\ccfrzeromcclass{} \ref{ccfr0},
868     \emph{\ccfrzeroshorttitle{}}, presents algorithms based on the framework
869     of continued fractions which are suitable for finding best rational
870     approximations in Farey series of large order.
871    
872    
873     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
874     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
875     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
876     \section[Probabilistic Results Surrounding $| r_I - r_A |$]
877     {Probabilistic Results Surrounding \mbox{\boldmath $| r_I - r_A |$}}
878     %Section tag: PRS0
879    
880     \index{Farey series!probabilistic results surrounding rI-rA@probabilistic results
881     surrounding $"|r_I-r_A"|$}
882     If rational numbers of the form $r_A = h/k$, subject to the constraint
883     $k \leq k_{MAX}$, are used to approximate arbitrary real numbers
884     $r_I$, it might not be clear how close we can ``typically'' choose
885     $r_A$ to an aribtrary $r_I$ under the constraint.
886     We consider different asymptotics for
887     the precision of the approximation of an arbitrary $r_I$ by a
888     rational number
889     $r_A=h/k$ with $k \leq k_{MAX}$. For simplicity of notation
890     we
891     denote $\alpha= r_I$ and $N=k_{ \rm MAX }$ and assume, without
892     loss of generality, that
893     $ \alpha \in [0,1]$.
894    
895     We are thus interested in the asymptotic behaviour, when $N
896     \rightarrow \infty$,
897     of the quantity
898     $$
899     %\begin{equation}
900     \label{eq:cfry0:prs0:01}
901     \rho_N(\alpha) = \min_{h/k \in F_N} \left|\alpha - h/k\right|\, ,
902     $$
903     %\end{equation}
904     which is the distance between $\alpha$ and $F_N$, the Farey
905     series of order $N$.
906    
907     The worst--case scenario is not very interesting: from the
908     construction of the Farey series
909     we observe that for a fixed $N$ the longest intervals between the
910     neighbours of $F_N$
911     are $[0,1/N]$ and $[1-1/N,1]$ and therefore for all $N$,
912     \begin{equation}
913     \label{eq:cfry0:prs0:02}
914     \max_{\alpha \in [0,1]} \rho_N(\alpha) = \frac{1}{2N}\, .
915     \end{equation}
916     (This supremum is achieved at the points $1/(2N)$ and $1-1/(2N)$.)
917    
918     However, such behaviour of $\rho_N(\alpha)$ is not typical: as
919     is shown below,
920     typical values of the approximation error $\rho_N(\alpha)$ are
921     much smaller.
922    
923     First consider the behaviour of $\rho_N(\alpha)$ for almost all
924     $\alpha \in [0,1]$.\footnote{ A statement is true
925     for almost all $\alpha \in [0,1]$ if the measure of the set where this
926     statement is wrong has measure zero.}
927     We then have (see \cite{bibref:b:Harman}, \cite{bibref:p:KargaevZ})
928     that for almost all $\alpha \in [0,1]$ and any $\varepsilon >0$,
929     (\ref{eq:cfry0:prs0:03}) and (\ref{eq:cfry0:prs0:04}) hold.
930    
931     \begin{equation}
932     \label{eq:cfry0:prs0:03}
933     \lim_{N\rightarrow\infty}\rho_N(\alpha) N^2 \log^{1+\varepsilon} N =
934     + \infty, \quad
935     \liminf_{N\rightarrow\infty} \rho_N(\alpha) N^2 \log N = 0
936     \end{equation}
937    
938     \begin{equation}
939     \label{eq:cfry0:prs0:04}
940     \limsup_{N\rightarrow\infty} \frac{ \rho_N(\alpha) N^2 }{ \log N } = +
941     \infty, \quad
942     \lim_{N\rightarrow\infty} \frac{ \rho_N(\alpha) N^2 }{
943     \log^{1+\varepsilon} N } = 0
944     \end{equation}
945    
946     Even more is true: in (\ref{eq:cfry0:prs0:03}) and (\ref{eq:cfry0:prs0:04})
947     one can replace $\log N$ by $\log N \log \log N $, $\log N \log \log
948     N \log \log \log N$, and so on.
949     Analogously, $\log^{1+\varepsilon} N$ could be replaced by
950     $\log N (\log \log N)^{1+\varepsilon} $, $\log N \log \log N (\log \log
951     \log N)^{1+\varepsilon}$, and so on.
952    
953     These statements are analogues of Khinchin's metric theorem,
954     the classic result
955     in metric number theory, see e.g. \cite{bibref:b:Harman}.
956    
957     The asymptotic distribution of the suitably normalized
958     $\rho_N(\alpha)$
959     was derived in \cite{bibref:p:KargaevZ1}. A main result of this
960     paper is that
961     the sequence of functions
962     $N^2\rho_N(\alpha)$ converges in distribution, when $N\rightarrow
963     \infty$,
964     to the probability measure on $[0, \infty)$ with the density given
965     by (\ref{eq:cfry0:prs0:04b}).
966    
967     \begin{equation}
968     \label{eq:cfry0:prs0:04b}
969     {p}(\tau) =
970     \left\{\begin{array}{l}
971     6/\pi^2, \hfill\mbox{ if $0 \leq \tau \leq \frac{1}{2}$ }\\
972     \\
973     \frac{6}{\pi^2 \tau} \left(1 + \log \tau - \tau
974     \right), \hfill\mbox{ if $\frac{1}{2}\leq \tau\leq 2 $ } \\
975     \\
976     \frac{ 3}{\pi^2 \tau}\left(2\log(2 \tau)\!
977     -\!4\log(\sqrt{\tau}\!+\!\sqrt{\tau\!-\!2})\!
978     -\! (\sqrt{\tau}\!-\!\sqrt{\tau\!-\!2})^2 \right),
979     \\
980     \hfill \mbox{ if $2 \leq \tau < \infty $ } \\
981     \end{array}
982     \right.
983     \end{equation}
984    
985     This means that
986     for all $a,A$
987     such that
988     $0<a<A<\infty$,
989     (\ref{eq:cfry0:prs0:05}) applies,
990     where
991     {\rm `meas'} denotes for the standard Lebesgue measure on $[0,1]$.
992    
993     \begin{equation}
994     \label{eq:cfry0:prs0:05}
995     {\rm meas} \{ \alpha \in [0,1]: \;a < N^2 \rho_N(\alpha) \leq A \}
996     \rightarrow
997     \int_a^A {p}(\tau) d \tau\,
998     \;\;{\rm as}\; N \rightarrow \infty
999     \end{equation}
1000    
1001     Another result in \cite{bibref:p:KargaevZ1} concerns the asymptotic
1002     behavior
1003     of the moments of the approximation error $\rho_N(\alpha) $. It
1004     says that
1005     for any $\delta\neq 0$ and $N \rightarrow \infty$,
1006     (\ref{eq:cfry0:prs0:06}) applies,
1007     where $\zeta(\cdot)$ and B$(\cdot,\cdot)$
1008     are the Riemann zeta--function and the Beta--function,
1009     respectively.
1010    
1011     \begin{equation}
1012     \label{eq:cfry0:prs0:06}
1013     %\hspace{-8mm}
1014     {
1015     %\textstile
1016     %\small
1017     \frac{\delta+1}{2}
1018     }
1019     \int_0^1 \rho_N^{\delta} (\alpha) d \alpha =
1020     \left\{\begin{array}{l}
1021     \infty{}, \hfill\mbox{if $ \delta \leq -1 $}\\
1022     \\
1023     % \frac{6}{\delta^2 (\delta+1)\pi^2 } \left(2^{-\delta} +
1024     \frac{3}{\delta^2 \pi^2 } \left(2^{-\delta} +
1025     \delta 2^{\delta+2} {\rm B}(\!-\delta,\frac{1}{2}) \right)
1026     N^{-2\delta}\left(1\! +\! o(1)\right), \\
1027     \hfill\mbox{if $-1\!<\!\delta\!<\!1, \delta\! \neq\! 0$ }\\
1028     \\
1029     \frac{3}{\pi^2} N^{-2} \log N +
1030     O\left( N^{-2} \right),
1031     \hfill\mbox{if $\delta =1 $ }\\
1032     \\
1033     %\frac{2^{1-\delta}}{1+\delta}
1034     2^{-\delta}
1035     \frac{\zeta(\delta)}{ \zeta(\delta+1)}
1036     N^{-\delta-1}+
1037     O\left( N^{-2\delta} \right),
1038     \hfill \mbox{if $\delta >1$ }
1039     \end{array}
1040     \right.
1041     \end{equation}
1042    
1043     In particular, the average of the approximation error $\rho_N
1044     (\alpha)$ asymptotically equals
1045     \begin{equation}
1046     \label{eq:cfry0:prs0:07}
1047     \int_{0}^1 \rho_N(\alpha) d\alpha = \frac{3}{\pi^2} \frac{\log N}{N^2} +
1048     O\left(\frac{1}{N^2}\right),
1049     \;\;\;\; N\rightarrow \infty \,.
1050     \end{equation}
1051    
1052     Comparison of (\ref{eq:cfry0:prs0:07})
1053     with (\ref{eq:cfry0:prs0:04}) shows that the
1054     asymptotic behavior of the average approximation error $\int
1055     \rho_N(\alpha) d\alpha$
1056     resembles the behavior of the superior limit of $\rho_N(\alpha)$.
1057     Even this limit
1058     decreases much faster than the maximum error $\max_{\alpha }
1059     \rho_N(\alpha)$, see
1060     (\ref{eq:cfry0:prs0:02}): for typical $\alpha$ the rate of decrease of
1061     $\rho_N(\alpha)$, when $ N\rightarrow \infty ,$
1062     is, roughly speaking, $1/N^2$ rather than $1/N$, the error for the
1063     worst combination of $\alpha$ and $N$.
1064    
1065     These results show that there is a significant advantage to using the Farey series
1066     as the set from which to choose rational approximations, rather than
1067     more naively using only rational numbers with the maximum
1068     denominator $k_{MAX}$ (as is often done in practice).
1069    
1070    
1071     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1072     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1073     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1074     \section[Integer Lattice Interpretation]
1075     {Integer Lattice Interpretation Of The Farey Series}
1076     %Section tag: ILI0
1077    
1078     The Farey series has a convenient and intuitive graphical interpretation
1079     involving the integer lattice\index{integer lattice}\index{lattice}%
1080     \index{Farey series!integer lattice interpretation}
1081     (see Fig. \ref{fig:cfry0:ili0:00},
1082     which illustrates this interpretation, but with $h$
1083     also restricted).
1084     (By integer lattice, we mean the $\vworkrealset{}^2$ plane
1085     with each point $(x,y)$, $x,y \in \vworkintset$, marked.)
1086     In such an interpretation, each rational number $h/k$ corresponds to
1087     a point $(k,h)$ which is $h$ units above and $k$ units
1088     to the right of the origin.
1089    
1090     \begin{figure}
1091     \centering
1092     \includegraphics[width=4.6in]{c_fry0/farey01a.eps}
1093     \caption{Graphical Interpretation Of Rational Numbers
1094     $h/k$ That Can Be Formed With $h \leq h_{MAX}=3$, $k \leq k_{MAX}=5$}
1095     \label{fig:cfry0:ili0:00}
1096     \end{figure}
1097    
1098     From the graphical interpretation suggested by Fig. \ref{fig:cfry0:ili0:00},
1099     the following properties are intuitively clear.
1100    
1101     \begin{itemize}
1102     \item The angle of a ray drawn from the origin to the point
1103     $(k,h)$ corresponding to the rational number $h/k$ is
1104     $\theta = tan^{-1} \; h/k$.
1105    
1106     \item Any integer lattice point on a line from
1107     the origin drawn at the angle $\theta$
1108     has the value $h/k = tan \; \theta$. All points corresponding
1109     to rational numbers with the same value will be on such a line,
1110     and thus form an equivalence class.
1111    
1112     \item A rational number $h/k$ is irreducible iff its corresponding
1113     point $(k,h)$ is ``directly'' visible from the origin with
1114     no intervening points.
1115    
1116     \item The Farey series of order $N$, $F_N$, can be
1117     formed graphically by starting with the
1118     set of integer lattice points
1119     $(k,h): \; h \in \vworkintsetnonneg \wedge 1 \leq k \leq N$,
1120     then sweeping
1121     a line extended from the origin, starting with
1122     angle $\theta = 0$, through
1123     $0 \leq \theta < \pi{}/2$, and recording
1124     in order each point directly visible from
1125     the origin.\footnote{Note that Fig. \ref{fig:cfry0:ili0:00},
1126     because it illustrates the case when $h$ is constrained
1127     as well, does not show integer lattice points for
1128     $h > h_{MAX}$. In principle, if the integer lattice shown
1129     in Fig. \ref{fig:cfry0:ili0:00} were extended indefinitely
1130     ``upward'', every positive irreducible rational number with
1131     $k \leq k_{MAX} = 5$ could be found graphically.}
1132     \end{itemize}
1133    
1134     Fig. \ref{fig:cfry0:chk0:01} illustrates the graphical construction method
1135     of $F_5$. Note that only integer lattice points which are directly
1136     visible from the origin (with no intervening points) are selected.
1137     (Fig. \ref{fig:cfry0:chk0:01}, like Fig. \ref{fig:cfry0:ili0:00},
1138     shows the case of constrained $h$---the integer lattice should be
1139     continued ``upward'' to construct the Farey series.)
1140    
1141     \begin{figure}
1142     \centering
1143     \includegraphics[width=4.6in]{c_fry0/farey01b.eps}
1144     \caption{Graphical Interpretation Of Irreducible Rational Numbers
1145     $h/k$ That Can Be Formed With $h \leq h_{MAX}=3$, $k \leq k_{MAX}=5$}
1146     \label{fig:cfry0:chk0:01}
1147     \end{figure}
1148    
1149    
1150     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1151     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1152     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1153     \section[Generating $F_{k_{MAX}, \overline{h_{MAX}}}$ In A Rectangular Region]
1154     {Generating \mbox{\boldmath $F_{k_{MAX}, \overline{h_{MAX}}}$}
1155     Over A Rectangular Region Of The Integer Lattice}
1156     %Section tag: CHK0
1157     \label{cfry0:schk0}
1158    
1159     \index{FKMAXHMAX@$F_{k_{MAX}, \overline{h_{MAX}}}$}
1160     In practice, $F_N$ does not represent the set of
1161     rational numbers that may be used for rational approximation in an
1162     application; hence it isn't usually appropriate to choose a
1163     rational number from $F_N$ strictly as
1164     the theory of numbers defines it.
1165     An actual application is parameterized not just by
1166     $k_{MAX}$ (the maximum denominator that may be chosen, which is considered
1167     in the definition of the Farey series),
1168     but also by $h_{MAX}$ (the maximum numerator
1169     that may be chosen). Typically, $h_{MAX}$ exists as a constraint
1170     because a machine multiplication instruction is limited in the size of the
1171     operands it can accomodate; and $k_{MAX}$ exists as a constraint because
1172     a machine division instruction is limited in the size of the divisor
1173     it can accomodate.
1174    
1175     In practice, the rational numbers that may be used for rational
1176     approximation represent a rectangular region of the integer
1177     lattice---all $(k,h):$ $h \leq h_{MAX} \wedge k \leq k_{MAX}$
1178     (Figs. \ref{fig:cfry0:ili0:00}, \ref{fig:cfry0:chk0:01}).
1179    
1180     Fig. \ref{fig:cfry0:ili0:00} supplies a graphical
1181     interpretation of all rational numbers
1182     that can be formed with constraints $h \leq h_{MAX} = 3$
1183     and $k \leq k_{MAX} = 5$. Each point of the integer lattice
1184     shown in the figure is a rational number, not necessarily
1185     irreducible. Because under this graphical interpretation
1186     a rational number is irreducible iff it can be reached
1187     by a ray from the origin with no intervening rational numbers,
1188     it is clear that the complete ordered set of irreducible
1189     rational numbers that can be formed under the
1190     constraints $h \leq h_{MAX}$ and $k \leq k_{MAX}$
1191     can be obtained graphically by sweeping a ray from
1192     the origin through the angles $0 \leq \theta < \pi/2$,
1193     recording each point directly visible from the origin.
1194     This graphical construction process is illustrated
1195     in Fig. \ref{fig:cfry0:chk0:01}.
1196    
1197     From the graphical construction process shown in
1198     Fig. \ref{fig:cfry0:chk0:01}, it can be seen that the
1199     set of irreducible rational numbers that can be formed
1200     subject to the constraints
1201     $h \leq h_{MAX} \wedge k \leq k_{MAX}$ is:
1202    
1203     \begin{equation}
1204     \left\{ { \frac{0}{1}, \frac{1}{5}, \frac{1}{4},
1205     \frac{1}{3}, \frac{2}{5}, \frac{1}{2},
1206     \frac{3}{5},
1207     \frac{2}{3}, \frac{3}{4}, \frac{1}{1},
1208     \frac{3}{2}, \frac{2}{1}, \frac{3}{1} } \right\} .
1209     \end{equation}
1210    
1211     We denote the ordered set of irreducible rational
1212     numbers that can be formed subject to the
1213     constraints $h \leq h_{MAX} \wedge k \leq k_{MAX}$ as
1214     $F_{k_{MAX}, \overline{h_{MAX}}}$.\footnote{Notationally,
1215     in general,
1216     we use an overbar on the order of a Farey series to
1217     denote that the terms are inverted and reversed in order.
1218     For example, $F_3 = \{ 0/1, 1/3, 1/2, \ldots \}$, but
1219     $F_{\overline{3}} = \{ \ldots , 2/1, 3/1 \}$. Notation
1220     such as $F_{A, \overline{B}}$ is an extension of that convention.}
1221    
1222     There are three important questions to be asked about
1223     the series $F_{k_{MAX}, \overline{h_{MAX}}}$:
1224    
1225     \begin{itemize}
1226     \item What are the smallest and largest rational numbers in
1227     $F_{k_{MAX}, \overline{h_{MAX}}}$?
1228     (This question is easy: the smallest two rational numbers
1229     in $F_{k_{MAX}, \overline{h_{MAX}}}$ are $0/1$
1230     and $1/k_{MAX}$, and the largest rational number
1231     is $h_{MAX}/1$.)
1232    
1233     \item How do we construct $F_{k_{MAX}, \overline{h_{MAX}}}$?
1234    
1235     \item If we desire to approximate a real number
1236     $r_I$, $r_{IMIN} \leq r_I \leq r_{IMAX}$,
1237     using a rational number selected from
1238     $F_{k_{MAX}, \overline{h_{MAX}}}$, how large might
1239     the error $| h/k - r_I |$ be?
1240     \end{itemize}
1241    
1242    
1243     \subsection[Construction Of $F_{k_{MAX},\overline{h_{MAX}}}$]
1244     {Construction Of \mbox{\boldmath $F_{k_{MAX},\overline{h_{MAX}}}$}}
1245    
1246     \index{FKMAXHMAX@$F_{k_{MAX}, \overline{h_{MAX}}}$!construction of}
1247     To construct $F_{k_{MAX}, \overline{h_{MAX}}}$, for
1248     $0 \leq \theta \leq \tan^{-1} (h_{MAX}/k_{MAX})$---the
1249     region of the series where $k_{MAX}$ is the dominant constraint,
1250     i.e. below the ``corner point'' in Figs. \ref{fig:cfry0:ili0:00}
1251     and \ref{fig:cfry0:chk0:01}---note
1252     that these terms are simply
1253     $F_{k_{MAX}}$ up to $h_{MAX}/k_{MAX}$ or its reduced
1254     equivalent.\footnote{If this is not intuitively clear,
1255     note in Figs. \ref{fig:cfry0:ili0:00} and \ref{fig:cfry0:chk0:01}
1256     that all of the terms of $F_{k_{MAX}}$---that is, all rational
1257     numbers, both reducible and irreducible, with $k \leq k_{MAX}$---are
1258     available for selection
1259     until the ``corner point'' is reached.}
1260     To construct $F_{k_{MAX}, \overline{h_{MAX}}}$ for
1261     $\tan^{-1} (h_{MAX}/k_{MAX}) < \theta < \pi/2$---the
1262     region of the series where $h_{MAX}$ is the dominant constraint,
1263     i.e. above the ``corner point'' in Figs. \ref{fig:cfry0:ili0:00}
1264     and \ref{fig:cfry0:chk0:01}---note that by a graphical argument
1265     of symmetry, these terms are the reciprocals of ascending terms of $F_{h_{MAX}}$.
1266     For example, in Fig. \ref{fig:cfry0:chk0:01}, if the $h$- and $k$-
1267     axes are transposed, it is easy to see that $3/1$ in the original integer lattice
1268     would correspond to $1/3$ in the transposed integer lattice. This argument of
1269     symmetry immediately suggests a procedure for constructing
1270     $F_{k_{MAX},\overline{h_{MAX}}}$.
1271    
1272     \begin{itemize}
1273     \item Construct $F_{k_{MAX}}$ from $0/1$ up through $h_{MAX}/k_{MAX}$ or its
1274     reduced equivalent.
1275     \item Construct $F_{h_{MAX}}$ from $1/h_{MAX}$ up to $k_{MAX}/h_{MAX}$ or
1276     its reduced equivalent; then reverse the order of the
1277     terms and take the reciprocal of
1278     each term.
1279     \item Concatenate the results from the two steps above.
1280     \end{itemize}
1281    
1282     \begin{vworkexamplestatement}
1283     \label{ex:cfry0:schk:00}
1284     Construct $F_{5,\overline{3}}$, the set of
1285     all irreducible rational numbers $h/k$
1286     that can be formed with $h \leq h_{MAX}=3$ and
1287     $k \leq k_{MAX}=5$.\footnote{Note that $F_{5,\overline{3}}$
1288     is the series depicted in Fig. \ref{fig:cfry0:chk0:01}, and
1289     this example can be verified against the figure.}
1290     \end{vworkexamplestatement}
1291     \begin{vworkexampleparsection}{Solution}
1292     (Using the method of construction presented above.)
1293     First, $F_5$ up through $h_{MAX}/k_{MAX} = 3/5$ or its reduced
1294     equivalent should be constructed. This series is
1295    
1296     \begin{equation}
1297     \label{eq:cfry0:schk:ex00:eq00}
1298     F_5 =
1299     \left\{ { \frac{0}{1}, \frac{1}{5}, \frac{1}{4},
1300     \frac{1}{3}, \frac{2}{5}, \frac{1}{2},
1301     \frac{3}{5}, \ldots{} } \right\} .
1302     \end{equation}
1303    
1304     Second, $F_3$ is constructed from $1/3$ up to $k_{MAX}/h_{MAX} = 5/3$ or
1305     its reduced equivalent (not including the
1306     final term, $5/3$). This series is
1307    
1308     \begin{equation}
1309     \label{eq:cfry0:schk:ex00:eq01}
1310     F_3 =
1311     \left\{ { \ldots , \frac{1}{3}, \frac{1}{2}, \frac{2}{3},
1312     \frac{1}{1}, \frac{4}{3}, \frac{3}{2}, \ldots{} } \right\} .
1313     \end{equation}
1314    
1315     Third, the terms of $F_3$ are reversed in order, and the reciprocal of each term is
1316     calculated, yielding
1317    
1318     \begin{equation}
1319     \label{eq:cfry0:schk:ex00:eq02}
1320     F_{\overline{3}} =
1321     \left\{ { \ldots{}, \frac{2}{3}, \frac{3}{4}, \frac{1}{1},
1322     \frac{3}{2}, \frac{2}{1}, \frac{3}{1} } \right\} .
1323     \end{equation}
1324    
1325     Finally, concatenating (\ref{eq:cfry0:schk:ex00:eq00})
1326     and
1327     (\ref{eq:cfry0:schk:ex00:eq02}) yields $F_{5,\overline{3}}$, below.
1328    
1329     \begin{equation}
1330     \label{eq:cfry0:schk:ex00:eq03}
1331     F_{5,\overline{3}} =
1332     \left\{ { \frac{0}{1}, \frac{1}{5}, \frac{1}{4},
1333     \frac{1}{3}, \frac{2}{5}, \frac{1}{2},
1334     \frac{3}{5},
1335     \frac{2}{3}, \frac{3}{4}, \frac{1}{1},
1336     \frac{3}{2}, \frac{2}{1}, \frac{3}{1} } \right\}
1337     \end{equation}
1338    
1339     \end{vworkexampleparsection}
1340     \vworkexamplefooter{}
1341    
1342     It is clear that Thm. \ref{thm:cfry0:sgfs0:01}
1343     and (\ref{eq:cfry0:sgfs0:thm:01:eq01}) through
1344     (\ref{eq:cfry0:sgfs0:thm:01:eq04}) can be used to construct
1345     $F_{k_{MAX}, \overline{h_{MAX}}}$. However, such algorithms
1346     are not discussed because---even with refinements---they
1347     can be no better than $O(N)$ and are not
1348     fruitful to develop. Instead, an $O(log N)$
1349     algorithm is presented in
1350     \ccfrzeroxrefcomma{}\ccfrzeromcclass{} \ref{ccfr0},
1351     \emph{\ccfrzeroshorttitle{}}.
1352    
1353    
1354     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1355     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1356     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1357     \subsection[Distance Between Terms Of $F_{h_{MAX},k_{MAX}}$]
1358     {Distance Between Terms Of \mbox{\boldmath $F_{h_{MAX},k_{MAX}}$}}
1359    
1360     \index{FKMAXHMAX@$F_{k_{MAX}, \overline{h_{MAX}}}$!distance between terms}
1361     \index{Farey series!distance between terms}
1362     The maximum \emph{distance} between terms of $F_{h_{MAX},k_{MAX}}$ also establishes
1363     what we call the maximum \emph{placement error}, $|r_A - r_I|$, in choosing
1364     $r_A = h/k$. Specifically, the maximum distance is twice the maximum placement
1365     error. Clearly, with a maximum distance specified, choosing $r_I = (x+y)/2$ for
1366     two successive terms $x$ and $y$ separated by the maximum distance is
1367     the most antagonistic
1368     choice of $r_I$ possible.
1369     We use the two notions (maximum distance and maximum placement error)
1370     interchangeably and don't bother to convert between them, as they are
1371     the same notion and differ only by a factor of two.
1372    
1373     It is clear from the earlier discussion of the Farey series that the maximum
1374     distance between terms in $F_{k_{MAX}}$ is $1/k_{MAX}$, and that this maximum
1375     distance occurs only adjacent to an integer. It is also clear from the
1376     discussion of $F_{\overline{h_{MAX}}}$ that the maximum distance between terms
1377     is 1.
1378    
1379     Thus, when we use $F_{k_{MAX}, \overline{h_{MAX}}}$ to approximate real numbers,
1380     in general the worst-case distance between terms is 1.
1381    
1382     In practical applications when rational approximation is used,
1383     the approximation tends to be used over a restricted interval
1384     $[l \gg 0, r \ll h_{MAX}]$ rather than over the full range of the rational numbers that
1385     can be formed, $[0, h_{MAX}]$. This section develops novel upper bounds on
1386     the distance between terms of $F_{k_{MAX}, \overline{h_{MAX}}}$ in an interval
1387     $[l,r]$. For simplicity, assume $l,r \in F_{k_{MAX}, \overline{h_{MAX}}}$.
1388    
1389     Three distinct cases are developed (Figure \ref{fig:cfry0:schk0:threecases}).
1390     The upper bound developed from Case III is always larger than the upper
1391     bound developed from Case II, which is always larger than the upper bound developed
1392     from Case I; so if only the absolute maximum error over
1393     the interval $[l,r]$ is of interest, only the
1394     highest-numbered case which applies needs to be evaluated. However, some
1395     applications may have different error requirements in different regions
1396     of the interval $[l,r]$, and for these applications it may be beneficial
1397     to analyze more than one case.
1398    
1399     \begin{figure}
1400     \centering
1401     \includegraphics[width=4.6in]{c_fry0/errreg01.eps}
1402     \caption{Three Cases For Bounding Distance Between Terms In
1403     $F_{k_{MAX}, \overline{h_{MAX}}}$}
1404     \label{fig:cfry0:schk0:threecases}
1405     \end{figure}
1406    
1407    
1408     \subsubsection[Case I: $r_I < h_{MAX}/k_{MAX}$]
1409     {Case I: \mbox{\boldmath $r_I < h_{MAX}/k_{MAX}$}}
1410    
1411     With $r_I < h_{MAX}/k_{MAX}$, $k \leq k_{MAX}$ is the dominant
1412     constraint, and the neighbors available to $r_I$ are simply the
1413     terms of $F_{k_{MAX}}$. If $[l, r] \cap [0, h_{MAX}/k_{MAX}]$
1414     includes an integer, clearly the maximum distance from $r_I$ to the
1415     nearest available term of $F_{k_{MAX}, \overline{h_{MAX}}}$ is given
1416     by
1417    
1418     \begin{equation}
1419     \left|
1420     \frac{h}{k} - r_I
1421     \right|
1422     \leq
1423     \frac{1}{2 k_{MAX}} ,
1424     \end{equation}
1425    
1426     which is the same result for the Farey series in general.
1427    
1428     If $[l, r] \cap [0, h_{MAX}/k_{MAX}]$ does
1429     not include an integer, it can be shown that the
1430     maximum distance between Farey terms is driven by the
1431     rational number with the smallest denominator in the
1432     interval $[l, r]$.
1433    
1434     For two consecutive terms $p/q$ and $p'/q'$ in $F_{k_{MAX}}$,
1435     $p'q - pq' = 1$ (Thm. \ref{thm:cfry0:spfs:02}), so that
1436    
1437     \begin{equation}
1438     \frac{p'}{q'} - \frac{p}{q} =
1439     \frac{p'q - pq'}{q q'} = \frac{1}{qq'} .
1440     \end{equation}
1441    
1442     By Thm. \ref{thm:cfry0:spfs:02ba}, $q+q' > k_{MAX}$, therefore
1443    
1444     \begin{equation}
1445     \label{eq:cfry0:schk0:minqplacementupperbound}
1446     \frac{1}{q k_{MAX}} \leq
1447     \frac{1}{q q'} <
1448     \frac{1}{q (k_{MAX}-q)}.
1449     \end{equation}
1450    
1451     Let $q_{MIN}$ be the smallest denominator of any rational number
1452     $\in F_{k_{MAX}}$ in the interval $[l,r]$. It is then easy to show
1453     that for any consecutive denominators $q, q'$ which occur in
1454     $F_{k_{MAX}}$ in the interval $[l,r]$,
1455    
1456     \begin{equation}
1457     \frac{1}{q q'} < \frac{1}{q_{MIN} \; max (q_{MIN}, k_{MAX} - q_{MIN})} .
1458     \end{equation}
1459    
1460     Thus, the upper bound on the distance between consecutive terms of $F_{k_{MAX}}$
1461     in an interval $[l,r]$ is tied to the minimum denominator of any
1462     rational number $\in F_{k_{MAX}}$ in $[l,r]$.
1463    
1464     Note that clearly
1465     $q_{MIN} \leq 1/(r-l)$, so for most practical intervals $[l,r]$,
1466     the search for $q_{MIN}$ would not be computationally expensive.
1467     However, applications could arise where an approximation is used
1468     in an \emph{extremely} narrow interval, and having an algorithm available that
1469     is computationally viable for such cases is advantageous. For example,
1470     locating the rational number $\in F_{2^{20,000}}$ with the smallest denominator
1471     in an interval of width $2^{-10,000}$ could be a serious computational
1472     problem.
1473    
1474     To locate $q_{MIN}$ in $[l,r]$, note that at least one rational number
1475     with $q_{MIN}$ as a denominator in $[l,r]$ is the best approximation
1476     of order $q_{MIN}$ to the midpoint of the interval,
1477     $(l+r)/2$.\footnote{Thanks to David M. Einstein \cite{bibref:i:davidmeinstein}
1478     and David Eppstein \cite{bibref:i:davideppstein}
1479     for this observation, contributed via the \texttt{sci.math} newsgroup
1480     \cite{bibref:n:scimathnewsgroup},
1481     which is the linchpin of Algorithm \ref{alg:cfmindenominator}.}
1482     By theorem (\cite{bibref:b:KhinchinClassic}, Theorem 15), every best approximation
1483     of a number is a convergent or intermediate fraction of the
1484     continued fraction representation of the number. We seek the
1485     convergent or intermediate fraction of $(l+r)/2$ with the smallest
1486     denominator that is in the interval $[l,r]$.\footnote{Regrettably,
1487     at this point the cart comes before the horse---the insight and
1488     algorithms which follow are based on continued fractions, which
1489     are not covered until \ccfrzeroxrefcomma{}\ccfrzeromcclass{} \ref{ccfr0},
1490     \emph{\ccfrzeroshorttitle{}}. We apologize for the potential necessity
1491     of reading this work out of order.}
1492    
1493     The convergents and intermediate fractions of $(l+r)/2$ are naturally
1494     arranged in order of increasing denominator. However, it would be
1495     inefficient to test \emph{every} intermediate fraction
1496     for membership in $[l,r]$, as partial quotients $a_k$ are unlimited in
1497     size and such an algorithm may not be $O(log \; k_{MAX})$. Instead,
1498     since intermediate fractions are formed using the parameterized
1499     expression $(i p_k + p_{k-1})/(i q_k + q_{k-1})$,
1500     and since intermediate fractions are ever-increasing
1501     or ever-decreasing with respect to the parameter $i$, the
1502     smallest value of $i$ which will create an intermediate
1503     fraction potentially within $[l,r]$ can be directly
1504     calculated. Only the intermediate fraction formed with
1505     this calculated value of $i$ needs to be tested for membership in
1506     $[l,r]$.
1507    
1508     Let $l_N$ and $l_D$ be the numerator and denominator of $l$, and
1509     let $r_N$ and $r_D$ be the numerator and denominator of $r$.
1510     In the case of $k$ even; $s_k < l < (l+r)/2$ (otherwise $s_k$
1511     would have been identified as $\in [l,r]$, see Algorithm
1512     \ref{alg:cfmindenominator}); $s_{k+1} \geq (l+r)/2$;
1513     with increasing $i$, $(i p_k + p_{k-1})/(i q_k + q_{k-1})$
1514     forms a decreasing sequence; and the inequality we seek to solve is
1515    
1516     \begin{equation}
1517     \label{eq:cfry0:schk0:ifselection01}
1518     \frac{i p_k + p_{k-1}}{i q_k + q_{k-1}} \leq \frac{r_N}{r_D}.
1519     \end{equation}
1520    
1521     Solving (\ref{eq:cfry0:schk0:ifselection01}), the smallest integral
1522     value of $i$ that will suffice is
1523    
1524     \begin{equation}
1525     \label{eq:cfry0:schk0:ifselection02}
1526     i = \left\lceil {
1527     \frac{r_N q_{k-1} - r_D p_{k-1}}{r_D p_k - r_N q_k}
1528     } \right\rceil .
1529     \end{equation}
1530    
1531     Similarly, for $k$ odd, the sequence is increasing,
1532     and the inequality and solution are
1533    
1534     \begin{equation}
1535     \label{eq:cfry0:schk0:ifselection03}
1536     \frac{i p_k + p_{k-1}}{i q_k + q_{k-1}} \geq \frac{l_N}{l_D}
1537     \to
1538     i = \left\lceil {
1539     \frac{l_N q_{k-1} - l_D p_{k-1}}{l_D p_k - l_N q_k}
1540     } \right\rceil .
1541     \end{equation}
1542    
1543     (\ref{eq:cfry0:schk0:ifselection01}),
1544     (\ref{eq:cfry0:schk0:ifselection02}),
1545     and (\ref{eq:cfry0:schk0:ifselection03}) suggest the following continued fraction
1546     algorithm for finding
1547     a rational number with the smallest denominator in an
1548     interval $[l,r]$.
1549    
1550     \begin{vworkalgorithmstatement}\label{alg:cfmindenominator}\end{vworkalgorithmstatement}
1551     \begin{alglvl0}
1552     \item Calculate all partial quotients $a_k$ and all convergents
1553     $s_k = p_k/q_k$ of the midpoint of the interval,
1554     $(l+r)/2$.
1555    
1556     \item For each convergent $s_k=p_k/q_k$, in order of increasing $k$:
1557    
1558     \begin{alglvl1}
1559    
1560     \item If $s_k = p_k/q_k \in [l,r]$, $s_k$ is a rational number with
1561     the lowest denominator, STOP.
1562    
1563     \item If $k$ is even,
1564    
1565     \begin{alglvl2}
1566    
1567     \item Calculate $i$ according to (\ref{eq:cfry0:schk0:ifselection02}).
1568     If $i < a_{k+1}$ and the intermediate fraction
1569     $(i p_k + p_{k-1})$ $/$ $(i q_k + q_{k-1})$ $\geq$ $l$, this intermediate
1570     fraction is
1571     a rational number with the lowest denominator, STOP.
1572    
1573     \end{alglvl2}
1574    
1575     \item Else if $k$ is odd,
1576    
1577     \begin{alglvl2}
1578    
1579     \item Calculate $i$ according to (\ref{eq:cfry0:schk0:ifselection03}).
1580     If $i < a_{k+1}$ and the intermediate fraction
1581     $(i p_k + p_{k-1})$ $/$ $(i q_k + q_{k-1})$ $\leq$ $r$, this intermediate
1582     fraction is
1583     a rational number with the lowest denominator, STOP.
1584    
1585     \end{alglvl2}
1586    
1587     \end{alglvl1}
1588    
1589     \end{alglvl0}
1590    
1591     Algorithm \ref{alg:cfmindenominator} is approximately $O(log \; k_{MAX})$,
1592     since there are a fixed number of steps per convergent, and the maximum number
1593     of convergents is $O(log \; k_{MAX})$. Once a rational number with the smallest
1594     denominator $q_{MIN}$ is located, (\ref{eq:cfry0:schk0:minqplacementupperbound})
1595     can be applied to bound $|r_A - r_I|$; namely,
1596    
1597     \begin{equation}
1598     \label{eq:qminmaxplacementerror}
1599     \left| {\frac{h}{k} - r_I} \right|
1600     <
1601     \frac{1}{2q_{MIN} \; max(q_{MIN}, k_{MAX} - q_{MIN})} .
1602     \end{equation}
1603    
1604    
1605     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1606     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1607     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1608     \subsubsection[Case II: $h_{MAX}/k_{MAX} < r_I < 1$]
1609     {Case II: \mbox{\boldmath $h_{MAX}/k_{MAX} < r_I < 1$}}
1610    
1611     If $h_{MAX}/k_{MAX} < r_I < 1$, a graphical argument
1612     (Figure \ref{fig:cfry0:schk0:caseii}) can be used
1613     to more tightly bound the maximum distance between terms of
1614     $F_{k_{MAX}, \overline{h_{MAX}}}$.
1615    
1616     \begin{figure}
1617     \centering
1618     \includegraphics[height=2.0in]{c_fry0/errcase2.eps}
1619     \caption{Graphical Interpretation Of Case II: $h_{MAX}/k_{MAX} < r_I < 1$}
1620     \label{fig:cfry0:schk0:caseii}
1621     \end{figure}
1622    
1623     In this case, a formable term at or to the left\footnote{To the left on the
1624     number line, but to the right in Figure \ref{fig:cfry0:schk0:caseii}.}
1625     of $r_I$ is represented by the point $(\lfloor h_{MAX}/r_I \rfloor + 1, h_{MAX} )$
1626     in the integer lattice,
1627     and a formable term at or to the right of $r_I$ is
1628     represented by the point $(\lfloor h_{MAX}/r_I \rfloor, h_{MAX} )$
1629     in the integer lattice. Thus, the maximum distance between
1630     neighboring terms in $F_{k_{MAX}, \overline{h_{MAX}}}$
1631     is given by the difference of these two terms,
1632    
1633     \begin{equation}
1634     \frac{h_{MAX}}{\left\lfloor {\frac{h_{MAX}}{r_I}} \right\rfloor}
1635     -
1636     \frac{h_{MAX}}{\left\lfloor {\frac{h_{MAX}}{r_I}} \right\rfloor + 1}
1637     =
1638     \frac{h_{MAX}}{{\left\lfloor {\frac{h_{MAX}}{r_I}} \right\rfloor}^2
1639     + \left\lfloor {\frac{h_{MAX}}{r_I}} \right\rfloor},
1640     \end{equation}
1641    
1642     and the maximum distance from $r_I$ to a neighboring term is
1643     given by
1644    
1645     \begin{equation}
1646     \label{eq:cfry0:schk0:caseiimaxplacementerror}
1647     \left|
1648     \frac{h}{k} - r_I
1649     \right|
1650     \leq
1651     \frac{h_{MAX}}{2 \left( { {\left\lfloor {\frac{h_{MAX}}{r_I}} \right\rfloor}^2
1652     + \left\lfloor {\frac{h_{MAX}}{r_I}} \right\rfloor } \right) }.
1653     \end{equation}
1654    
1655     Note that Case II will exist only if $h_{MAX}/k_{MAX} < 1$.
1656    
1657    
1658     \subsubsection[Case III: $1 < h_{MAX}/k_{MAX} < r_I$]
1659     {Case III: \mbox{\boldmath $1 < h_{MAX}/k_{MAX} < r_I$}}
1660    
1661     It can be established graphically, using the coordinate system of
1662     Figure \ref{fig:cfry0:ili0:00}, Figure \ref{fig:cfry0:chk0:01},
1663     or Figure \ref{fig:cfry0:schk0:threecases},
1664     that the line $h=r_I k$ intercepts the
1665     line $h=h_{MAX}$ at the point $(h_{MAX}/r_I, h_{MAX})$. It is clear
1666     from a graphical argument that all of the terms of the Farey series
1667     of order $\lfloor h_{MAX}/r_I \rfloor$ are available as neighbors
1668     of $r_I$. Therefore,
1669    
1670     \begin{equation}
1671     \label{eq:cfry0:schk0:caseiiiplacementerror}
1672     \left|
1673     \frac{h}{k} - r_I
1674     \right|
1675     \leq
1676     \frac{1}{2 \left\lfloor \frac{h_{MAX}}{r_I} \right\rfloor}.
1677     \end{equation}
1678    
1679    
1680     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1681     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1682     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1683     \section{Acknowledgements}
1684     %Section tag: ACK0
1685    
1686     This chapter is the result of work on inexpensive microcontroller
1687     arithmetic (and a paper) undertaken in 2000.
1688     We would like to gratefully acknowledge the assistance
1689     of
1690     \index{Bachelis, Greg} Greg Bachelis \cite{bibref:i:gregbachelis},
1691     \index{Berman, Robert} Robert Berman \cite{bibref:i:robertberman},
1692     \index{Lin, Feng} Feng Lin \cite{bibref:i:fenglin},
1693     \index{Sahinidis, Nick} Nick Sahinidis \cite{bibref:i:nicksahinidis},
1694     \index{Van Tuyl, Adam} Adam Van Tuyl \cite{bibref:i:adamvantuyl},
1695     \index{Schweiger, Carl} Carl Schweiger \cite{bibref:i:carlschweiger},
1696     \index{Tindell, Ken} Ken Tindell \cite{bibref:i:kentindell},
1697     \index{Vestal, Steve} Steve Vestal \cite{bibref:i:stevevestal},
1698     \index{Whitinger, Bob} Bob Whitinger \cite{bibref:i:bobwhitinger},
1699     and
1700     \index{Stewart, David B.} David B. Stewart \cite{bibref:i:davidbstewart}
1701     in finding the areas of
1702     mathematics relevant to the rational number selection
1703     problem. We would also like to
1704     thank
1705     \index{Bengtsson, Johan} Johan Bengtsson \cite{bibref:i:johanbengtsson},
1706     \index{Burke, Michael J.} Michael J. Burke \cite{bibref:i:michaeljburke},
1707     \index{Endicott, Mark} Mark Endicott \cite{bibref:i:markendicott},
1708     \index{Eppstein, David} David Eppstein \cite{bibref:i:davideppstein},
1709     \index{Munteanu, Mircea} Mircea Munteanu \cite{bibref:i:mirceamunteanu},
1710     \index{Gibson, Adam} Adam Gibson \cite{bibref:i:adamgibson},
1711     and \index{Virgil} Virgil \cite{bibref:i:virgil}
1712     (of the \index{sci.math.num-analysis@\texttt{sci.math.num-analysis} newsgroup}%
1713     \texttt{sci.math.num-analysis} newsgroup
1714     \cite{bibref:n:scimathnumanalysis})
1715     for insight into this problem;
1716     \index{Stallings, Cliff} Cliff Stallings \cite{bibref:i:cliffstallings}
1717     and
1718     \index{Kakos, Robert} Robert Kakos \cite{bibref:i:robertkakos}
1719     for support from Wayne State
1720     University's College Of Engineering;
1721     \index{Groen, Paulette} Paulette Groen \cite{bibref:i:paulettegroen}
1722     and
1723     \index{Smith, Paula} Paula Smith \cite{bibref:i:paulasmith}
1724     for support from \index{Visteon}Visteon;
1725     \index{Crosby, Bob} Bob Crosby \cite{bibref:i:bobcrosby}
1726     for support
1727     from \index{Texas Instruments}Texas Instruments;
1728     \index{Zauner, Klaus-Peter} Klaus-Peter Zauner \cite{bibref:i:klauspeterzauner},
1729     \index{Blome, Andrea} Andrea Blome \cite{bibref:i:andreablome},
1730     \index{Smith, Una} Una Smith \cite{bibref:i:unasmith},
1731     \index{Tinnefeld, Karsten} Karsten Tinnefeld \cite{bibref:i:karstentinnefeld},
1732     and
1733     \index{Franke, Axel} Axel Franke \cite{bibref:i:axelfranke}
1734     for other tool
1735     and logistical support; and the management
1736     team at Visteon for allowing us to pursue this
1737     effort in the workplace.
1738    
1739    
1740     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1741     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1742     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1743     \section{Exercises}
1744     %Section tag: EXE0
1745    
1746     \begin{vworkexercisestatement}
1747     \label{exe:cfry0:sexe0:01}
1748     Prove that Theorem \ref{thm:cfry0:spfs:01}
1749     holds in the degenerate cases where $h=1$ and where $k=1$.
1750     \end{vworkexercisestatement}
1751     \vworkexercisefooter{}
1752    
1753     \begin{vworkexercisestatement}
1754     \label{exe:cfry0:sexe0:02}
1755     Prove that Theorem \ref{thm:cfry0:spfs:01} holds $\forall i \in \vworkintset$
1756     (rather than $\forall i \in \vworkintsetnonneg$) using
1757     the slightly amended notion of reducibility that $h/k$ is irreducible iff
1758     $\lfloor h \rfloor / k$ is irreducible.
1759     \end{vworkexercisestatement}
1760     \vworkexercisefooter{}
1761    
1762     \begin{vworkexercisestatement}
1763     In Section \ref{cfry0:sgfs0} and Algorithm \ref{alg:cfry0:sgfs0:02}
1764     it is stated that for $i \in \vworkintsetnonneg$,
1765     $(iN-1)/N$, $i/1$, and $(iN+1)/N$ are consecutive terms in the Farey series
1766     or order $N$, $F_N$. Prove that $(iN-1)/N$ and $(iN+1)/N$ are irreducible,
1767     and the left and right Farey neighbors to $i/1$.
1768     \end{vworkexercisestatement}
1769     \vworkexercisefooter{}
1770    
1771     \begin{vworkexercisestatement}
1772     Prove that in $F_N$ the maximum distance between terms $1/N$ can occur
1773     only adjacent to an integer.
1774     \end{vworkexercisestatement}
1775     \vworkexercisefooter{}
1776    
1777    
1778     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1779    
1780     \noindent\begin{figure}[!b]
1781     \noindent\rule[-0.25in]{\textwidth}{1pt}
1782     \begin{tiny}
1783     \begin{verbatim}
1784 dashley 277 $HeadURL$
1785     $Revision$
1786     $Date$
1787     $Author$
1788 dashley 140 \end{verbatim}
1789     \end{tiny}
1790     \noindent\rule[0.25in]{\textwidth}{1pt}
1791     \end{figure}
1792    
1793 dashley 277 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1794 dashley 140 %
1795     %End of file C_FRY0.TEX

Properties

Name Value
svn:eol-style native
svn:keywords Author Date Id Revision URL Header

dashley@gmail.com
ViewVC Help
Powered by ViewVC 1.1.25