Parent Directory | Revision Log

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

*Thu Oct 6 03:15:02 2016 UTC*
(6 years, 3 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 | 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 | \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 |