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

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

Parent Directory Parent Directory | Revision Log Revision Log


Revision 277 - (show annotations) (download) (as text)
Tue Aug 13 02:35:39 2019 UTC (2 years, 10 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 %$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 $HeadURL$
1785 $Revision$
1786 $Date$
1787 $Author$
1788 \end{verbatim}
1789 \end{tiny}
1790 \noindent\rule[0.25in]{\textwidth}{1pt}
1791 \end{figure}
1792
1793 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1794 %
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