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

Initial commit after migrating from CVS.

 1 dashley 4 %$Header: /home/dashley/cvsrep/e3ft_gpl01/e3ft_gpl01/dtaipubs/esrgubka/c_fry0/c_fry0.tex,v 1.7 2004/03/17 01:37:52 dtashley Exp$ 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 27 \label{eq:cfry0:sint:eq0001a} 28 F_1 = \left\{ {\frac{0}{1},\frac{1}{1}} \right\} 29 30 31 32 \label{eq:cfry0:sint:eq0001b} 33 F_2 = \left\{ {\frac{0}{1},\frac{1}{2},\frac{1}{1}} \right\} 34 35 36 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 41 42 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 49 50 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 57 58 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 68 69 70 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 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 241 \frac{h}{k} + i = \frac{h + ik}{k} 242 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 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 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 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 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 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 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 344 \frac{h+h'}{k+k'} . 345 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 375 \frac{a}{b} < \frac{ia + jc}{ib + jd} < \frac{c}{d} , 376 377 378 or, equivalently, 379 380 381 \frac{ia + jc}{ib + jd} \in \left( { \frac{a}{b} , \frac{c}{d} } \right) . 382 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 414 \label{eq:cfry0:spfs:02baa} 415 \frac{h + h'}{k + k'} \in \left( { \frac{h}{k}, \frac{h'}{k'}} \right) . 416 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 456 \label{eq:cfry0:spfs:thm02aa} 457 h'k - h k' = 1. 458 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 478 \label{eq:cfry0:spfs:thm02ab} 479 \frac{a}{b}-\frac{h}{k} = \frac{ak-bh}{bk} \geq \frac{1}{bk} . 480 481 482 Similarly, the distance from $a/b$ to $h'/k'$ is 483 484 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 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 498 \label{eq:cfry0:spfs:thm02ac} 499 \frac{h'}{k'}-\frac{h}{k} = \frac{h'k-hk'}{kk'} = \frac{1}{kk'} . 500 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 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 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 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 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 545 h'k-hk' = h''k'-h'k''=1 , 546 547 548 549 (k'>k'') \vworkhimp 550 \left( { 551 \frac{h'}{k'}-\frac{h}{k}<\frac{h''}{k''}-\frac{h}{k} 552 } \right) . 553 554 \end{vworklemmastatement} 555 \begin{vworklemmaproof} 556 557 \frac{h'}{k'}-\frac{h}{k} = \frac{1}{kk'} 558 559 560 \frac{h''}{k''}-\frac{h}{k} = \frac{1}{kk''} 561 562 563 (k' > k'') \vworkhimp \left( { 564 \frac{1}{kk'} < \frac{1}{kk''} 565 } \right) 566 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 582 \frac{h'}{k'} = \frac{h+h''}{k+k''}. 583 584 \end{vworktheoremstatement} 585 \begin{vworktheoremproof} 586 Starting from Theorem \ref{thm:cfry0:spfs:02}: 587 588 h'k-hk' = h''k' - h'k''=1 589 590 591 h'(k+k'')=k'(h+h'') 592 593 594 \frac{h'}{k'} = \frac{h+h''}{k+k''}. 595 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 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 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 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 646 647 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 652 653 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 658 659 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 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 677 \label{eq:cfry0:sgfs0:thm:01:eq05} 678 h_{j-1} k_{j-2} - h_{j-2} k_{j-1} = 1 679 680 681 and 682 683 684 \label{eq:cfry0:sgfs0:thm:01:eq06} 685 h_{j} k_{j-1} - h_{j-1} k_{j} = 1 . 686 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 696 \label{eq:cfry0:sgfs0:thm:01:eq07} 697 h_j = i h_{j-1} - h_{j-2} 698 699 700 and 701 702 703 \label{eq:cfry0:sgfs0:thm:01:eq08} 704 k_j = i k_{j-1} - k_{j-2} , 705 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 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 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 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 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 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 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 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 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 834 C(N) = 1 + \sum_{k=1}^{N} \phi (k) , 835 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 842 C(N) \sim{} \frac{3 N^2}{\pi{}^2} \approx 0.3040 N^2 . 843 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 % 900 \label{eq:cfry0:prs0:01} 901 \rho_N(\alpha) = \min_{h/k \in F_N} \left|\alpha - h/k\right|\, , 902$$ 903 % 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 913 \label{eq:cfry0:prs0:02} 914 \max_{\alpha \in [0,1]} \rho_N(\alpha) = \frac{1}{2N}\, . 915 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 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 937 938 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 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 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 984 985 This means that 986 for all $a,A$ 987 such that 988 $01$ } 1039 \end{array} 1040 \right. 1041 1042 1043 In particular, the average of the approximation error $\rho_N 1044 (\alpha)$ asymptotically equals 1045 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 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 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 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 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 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 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 1314 1315 Third, the terms of $F_3$ are reversed in order, and the reciprocal of each term is 1316 calculated, yielding 1317 1318 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 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 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 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 1419 \left| 1420 \frac{h}{k} - r_I 1421 \right| 1422 \leq 1423 \frac{1}{2 k_{MAX}} , 1424 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 1438 \frac{p'}{q'} - \frac{p}{q} = 1439 \frac{p'q - pq'}{q q'} = \frac{1}{qq'} . 1440 1441 1442 By Thm. \ref{thm:cfry0:spfs:02ba}, $q+q' > k_{MAX}$, therefore 1443 1444 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 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 1457 \frac{1}{q q'} < \frac{1}{q_{MIN} \; max (q_{MIN}, k_{MAX} - q_{MIN})} . 1458 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 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 1520 1521 Solving (\ref{eq:cfry0:schk0:ifselection01}), the smallest integral 1522 value of $i$ that will suffice is 1523 1524 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 1530 1531 Similarly, for $k$ odd, the sequence is increasing, 1532 and the inequality and solution are 1533 1534 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 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 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 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 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 1641 1642 and the maximum distance from $r_I$ to a neighboring term is 1643 given by 1644 1645 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 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 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 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 $RCSfile: c_fry0.tex,v$ 1785 $Source: /home/dashley/cvsrep/e3ft_gpl01/e3ft_gpl01/dtaipubs/esrgubka/c_fry0/c_fry0.tex,v$ 1786 $Revision: 1.7$ 1787 $Author: dtashley$ 1788 $Date: 2004/03/17 01:37:52$ 1789 \end{verbatim} 1790 \end{tiny} 1791 \noindent\rule[0.25in]{\textwidth}{1pt} 1792 \end{figure} 1793 1794 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 1795 % $Log: c_fry0.tex,v$ 1796 % Revision 1.7 2004/03/17 01:37:52 dtashley 1797 % Edits. 1798 % 1799 % Revision 1.6 2004/03/12 11:20:03 dtashley 1800 % Erroneous math mode command commented out to silence LaTeX warning. 1801 % 1802 % Revision 1.5 2003/11/30 01:22:17 dtashley 1803 % References changed to follow standard format. 1804 % 1805 % Revision 1.4 2002/08/22 00:33:33 dtashley 1806 % Have made aesthetic changes in CFRY0 and CCFR0. Checking in all before 1807 % rebuild of book. 1808 % 1809 % Revision 1.3 2001/07/11 18:42:05 dtashley 1810 % Safety check-in. Beginning work now on using GNU GMP in the tool set 1811 % and must cease work on book temporarily. 1812 % 1813 % Revision 1.2 2001/07/01 19:37:42 dtashley 1814 % Move out of binary mode for use with CVS. 1815 % 1816 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 1817 % $History: c_fry0.tex$ 1818 % 1819 % ***************** Version 18 ***************** 1820 % User: Dashley1 Date: 3/07/01 Time: 12:17a 1821 % Updated in $/uC Software Multi-Volume Book (A)/Chapter, FRY0, Farey Series 1822 % Edits. 1823 % 1824 % ***************** Version 17 ***************** 1825 % User: Dashley1 Date: 2/10/01 Time: 2:02a 1826 % Updated in$/uC Software Multi-Volume Book (A)/Chapter, FRY0, Farey Series 1827 % Completion of Farey series chapter. 1828 % 1829 % ***************** Version 16 ***************** 1830 % User: Dashley1 Date: 1/31/01 Time: 4:20p 1831 % Updated in $/uC Software Multi-Volume Book (A)/Chapter, FRY0, Farey Series 1832 % Edits. 1833 % 1834 % ***************** Version 15 ***************** 1835 % User: Dashley1 Date: 12/22/00 Time: 12:55a 1836 % Updated in$/uC Software Multi-Volume Book (A)/Chapter, FRY0, Farey Series 1837 % Tcl automated method of build refined. 1838 % 1839 % ***************** Version 14 ***************** 1840 % User: David T. Ashley Date: 8/19/00 Time: 5:03p 1841 % Updated in $/uC Software Multi-Volume Book (A)/Chapter, FRY0, Farey Series 1842 % Edits. 1843 % 1844 % ***************** Version 13 ***************** 1845 % User: David T. Ashley Date: 8/13/00 Time: 3:17p 1846 % Updated in$/uC Software Multi-Volume Book (A)/Chapter, FRY0, Farey Series 1847 % Edits. 1848 % 1849 % ***************** Version 12 ***************** 1850 % User: David T. Ashley Date: 8/12/00 Time: 9:45p 1851 % Updated in $/uC Software Multi-Volume Book (A)/Chapter, FRY0, Farey Series 1852 % Edits. 1853 % 1854 % ***************** Version 11 ***************** 1855 % User: David T. Ashley Date: 8/06/00 Time: 8:50a 1856 % Updated in$/uC Software Multi-Volume Book (A)/Chapter, FRY0, Farey Series 1857 % Work on Prime Number and Farey Series chapters. 1858 % 1859 % ***************** Version 10 ***************** 1860 % User: David T. Ashley Date: 8/05/00 Time: 1:31a 1861 % Updated in $/uC Software Multi-Volume Book (A)/Chapter, FRY0, Farey Series 1862 % Minor edit--test check-in. 1863 % 1864 % ***************** Version 9 ***************** 1865 % User: David T. Ashley Date: 8/02/00 Time: 11:21p 1866 % Updated in$/uC Software Multi-Volume Book (A)/Chapter, FRY0, Farey Series 1867 % Edits of Farey series chapter. 1868 % 1869 % ***************** Version 8 ***************** 1870 % User: David T. Ashley Date: 7/29/00 Time: 11:50p 1871 % Updated in $/uC Software Multi-Volume Book (A)/Chapter, FRY0, Farey Series 1872 % Edits, addition of solutions manual volume. 1873 % 1874 % ***************** Version 7 ***************** 1875 % User: David T. Ashley Date: 7/24/00 Time: 6:59p 1876 % Updated in$/uC Software Multi-Volume Book (A)/Chapter, FRY0, Farey Series 1877 % Add'l work on Farey series chapter. 1878 % 1879 % ***************** Version 6 ***************** 1880 % User: David T. Ashley Date: 7/22/00 Time: 3:24p 1881 % Updated in $/uC Software Multi-Volume Book (A)/Chapter, FRY0, Farey Series 1882 % Addition of opening quote from Hardy. May want to eventually change 1883 % the quote to something less negative. 1884 % 1885 % ***************** Version 5 ***************** 1886 % User: David T. Ashley Date: 7/16/00 Time: 2:10p 1887 % Updated in$/uC Software Multi-Volume Book (A)/Chapter, FRY0, Farey Series 1888 % Edits. 1889 % 1890 % ***************** Version 4 ***************** 1891 % User: David T. Ashley Date: 7/15/00 Time: 1:30p 1892 % Updated in $/uC Software Multi-Volume Book (A)/Chapter, FRY0, Farey Series 1893 % Edits of Farey series chapter. 1894 % 1895 % ***************** Version 3 ***************** 1896 % User: Dashley1 Date: 7/13/00 Time: 7:14p 1897 % Updated in$/uC Software Multi-Volume Book (A)/Chapter, FRY0, Farey Series 1898 % Edits for introduction to Farey series. 1899 % 1900 % ***************** Version 2 ***************** 1901 % User: David T. Ashley Date: 7/09/00 Time: 11:16p 1902 % Updated in $/uC Software Multi-Volume Book (A)/Chapter, FRY0, Farey Series 1903 % Addition of new chapters, enhancements to preface. 1904 % 1905 % ***************** Version 1 ***************** 1906 % User: David T. Ashley Date: 7/09/00 Time: 9:26p 1907 % Created in$/uC Software Multi-Volume Book (A)/Chapter, FRY0, Farey Series 1908 % Initial check-in. 1909 % 1910 %End of file C_FRY0.TEX