Parent Directory | Revision Log

Revision **4** -
(**show annotations**)
(**download**)
(**as text**)

*Thu Oct 6 03:15:02 2016 UTC*
(7 years, 9 months ago)
by *dashley*

File MIME type: application/x-tex

File size: 75978 byte(s)

File MIME type: application/x-tex

File size: 75978 byte(s)

Initial commit after migrating from CVS.

1 | %$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 | \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 | $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 |

dashley@gmail.com | ViewVC Help |

Powered by ViewVC 1.1.25 |