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 |