Parent Directory | Revision Log

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

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

File MIME type: application/x-tex

File size: 174877 byte(s)

File MIME type: application/x-tex

File size: 174877 byte(s)

Initial commit after migrating from CVS.

1 | dashley | 4 | %$Header: /home/dashley/cvsrep/e3ft_gpl01/e3ft_gpl01/dtaipubs/esrgubka/c_cfr0/c_cfr0.tex,v 1.18 2004/03/12 11:12:35 dtashley Exp $ |

2 | |||

3 | \chapter{\ccfrzerolongtitle{}} | ||

4 | |||

5 | \label{ccfr0} | ||

6 | |||

7 | \beginchapterquote{``I began by saying that there is probably less difference | ||

8 | between the positions of a mathematician and a physicist | ||

9 | than is generally supposed, and that the most important | ||

10 | seems to me to be this, that the mathematician is in much | ||

11 | more direct contact with reality \ldots{} mathematical | ||

12 | objects are so much more what they seem. A chair or a | ||

13 | star is not in the least what it seems to be; the more we think | ||

14 | of it, the fuzzier its outlines become in the haze of sensation | ||

15 | which surround it; but `2' or `317' has nothing to do with | ||

16 | sensation, and its properties stand out the more clearly the more | ||

17 | closely we scrutinize it.''} | ||

18 | {G. H. Hardy \cite{bibref:b:mathematiciansapology:1940}, pp. 128-130} | ||

19 | \index{Hardy, G. H.} | ||

20 | |||

21 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

22 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

23 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

24 | \section{Introduction} | ||

25 | %Section tag: INT0 | ||

26 | \label{ccfr0:sint0} | ||

27 | \index{continued fraction} | ||

28 | \index{continued fraction!definition} | ||

29 | |||

30 | A \emph{finite simple continued fraction} is a fraction of the form | ||

31 | |||

32 | \begin{equation} | ||

33 | \label{eq:ccfr0:int0:00} | ||

34 | a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 | ||

35 | + \cfrac{1}{\;\;\;\;\;\;\;\;\;\;\;\;\;\;\ldots + \cfrac{1}{a_n}}}} | ||

36 | = | ||

37 | [a_0; a_1, a_2, \ldots , a_n] , | ||

38 | \end{equation} | ||

39 | |||

40 | \noindent{}where $a_0 \in \vworkintsetnonneg$ and | ||

41 | $a_i \in \vworkintsetpos$, $i > 0$. Each integer | ||

42 | $a_i$ is called an \index{continued fraction!element}\emph{element} or | ||

43 | \index{continued fraction!partial quotient}\emph{partial quotient} | ||

44 | of the continued fraction. | ||

45 | We require, except in the case of | ||

46 | the continued fraction representation of an integer, | ||

47 | that the final element $a_n$ not be equal | ||

48 | to 1.\footnote{\label{footnote:ccfr0:sint0:00}The reason for | ||

49 | this restriction is discussed later.} | ||

50 | |||

51 | Continued fractions are quite unwieldly to write and typeset, | ||

52 | and so a continued fraction in the form of (\ref{eq:ccfr0:int0:00}) | ||

53 | is written as $[a_0; a_1, a_2, \ldots , a_n]$. Note that the | ||

54 | separator between $a_0$ and $a_1$ is a semicolon (`;'), and that all other | ||

55 | separators are commas (`,'). In some works, commas are used exclusively; and in | ||

56 | other works, the first element is $a_1$ rather than $a_0$. Throughout this | ||

57 | work, the notational conventions illustrated in (\ref{eq:ccfr0:int0:00}) are | ||

58 | followed. | ||

59 | |||

60 | In this chapter, the framework of continued fractions is presented in the | ||

61 | context of finding rational numbers in $F_N$, the Farey series of order $N$, | ||

62 | enclosing an arbitrary $r_I \in \vworkrealsetnonneg$. The continued fraction | ||

63 | algorithm presented (Algorithm \ref{alg:ccfr0:scba0:cfenclosingneighborsfn}) | ||

64 | is $O(log N)$, and so is suitable for finding the best rational | ||

65 | approximations in $F_N$ even when $N$ is very large. Because our emphasis | ||

66 | is on practical applications rather than number theory, we don't include more | ||

67 | information than is necessary to understand the applications we have in | ||

68 | mind. | ||

69 | |||

70 | The study of continued | ||

71 | fractions is a topic from number theory (a branch of mathematics). It may be | ||

72 | counterintuitive to anyone but a number theorist that continued fractions | ||

73 | can be used to economically find best rational approximations, | ||

74 | or that continued fractions are anything but | ||

75 | a parlor curiosity. C.D. Olds (\cite{bibref:b:OldsClassic}, p. 3) comments: | ||

76 | |||

77 | \index{Olds, C. D.} | ||

78 | |||

79 | \begin{quote} | ||

80 | At first glance, nothing seems simpler or less significant than writing a number, | ||

81 | for example $\frac{9}{7}$, in the form | ||

82 | |||

83 | \begin{equation} | ||

84 | \frac{9}{7} = 1 + \frac{2}{7} = 1 + \frac{1}{\cfrac{7}{2}} | ||

85 | = 1 + \cfrac{1}{3 + \cfrac{1}{2}} | ||

86 | = 1 + \cfrac{1}{3 + \cfrac{1}{1 + \cfrac{1}{1}}}. | ||

87 | \end{equation} | ||

88 | |||

89 | It turns out, however, that fractions of this form, called ``continued | ||

90 | fractions'', provide much insight into mathematical problems, particularly into | ||

91 | the nature of numbers. | ||

92 | |||

93 | Continued fractions were studied by the great mathematicians of the seventeenth | ||

94 | and eighteenth centuries and are a subject of active investigation today. | ||

95 | \end{quote} | ||

96 | |||

97 | |||

98 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

99 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

100 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

101 | \section{History Of Continued Fractions} | ||

102 | %Section tag: HST0 | ||

103 | \label{cfr0:hst0} | ||

104 | \index{continued fraction!history of} | ||

105 | |||

106 | The only work we are aware of that explicitly treats the history | ||

107 | of continued fractions is \cite{bibref:b:HistoryCfPadeApproxBrezinski}. | ||

108 | Although the history of continued fractions is complex, | ||

109 | two points are clear. First, it is clear that Euclid's \index{Euclid} | ||

110 | GCD algorithm \index{Euclid!GCD algorithm} | ||

111 | (Algorithm \ref{alg:ccfr0:sega0:euclidsgcdalgorithm}), | ||

112 | which was known no later than around 300 B.C., | ||

113 | represents the historical origin of the continued fraction. Second, | ||

114 | it is clear that the utility of the apparatus of continued fractions | ||

115 | in finding best rational approximations---specifically the properties | ||

116 | of convergents---was understood by the 17th century. | ||

117 | |||

118 | In this section, we present some excerpts from | ||

119 | \cite{bibref:b:HistoryCfPadeApproxBrezinski} | ||

120 | which show the very early use of continued fractions to obtain best rational | ||

121 | approximations with a numerator and denominator less than certain | ||

122 | prescribed limits. | ||

123 | We simply demonstrate that the technique we present was known by | ||

124 | the 17th century (with the possible exception of the | ||

125 | second component of Theorem \ref{thm:ccfr0:scba0:cfenclosingneighbors}), | ||

126 | and we don't attempt to describe the other uses | ||

127 | of continued fractions or the significance of continued fractions | ||

128 | in mathematics or number theory. | ||

129 | |||

130 | Although we present best rational | ||

131 | approximations in the context of being able to effectively use | ||

132 | processor integer multiplication and division instructions, | ||

133 | earlier historical work was aimed at either | ||

134 | providing rational approximations to irrational numbers ($\sqrt{2}$ or $\pi$, | ||

135 | for example), or at determining optimal numbers of gear teeth | ||

136 | (in mechanical systems). Naturally, the need for best rational approximations | ||

137 | in the context of computer arithmetic is a relatively recent | ||

138 | development. | ||

139 | |||

140 | In the introduction of \cite{bibref:b:HistoryCfPadeApproxBrezinski}, | ||

141 | Brezinski \index{Brezenski, Claude} hints at the broad application and importance | ||

142 | of continued fractions: | ||

143 | |||

144 | \begin{quote} | ||

145 | The history of continued fractions is certainly one of the longest | ||

146 | among those of mathematical concepts, since it begins with | ||

147 | Euclid's algorithm \index{Euclid!GCD algorithm} for the greatest common divisor at least | ||

148 | three centuries B.C. As it is often the case and like | ||

149 | Monsieur Jourdain in Moli\`ere's ``le bourgeois gentilhomme'' | ||

150 | (who was speaking in prose though he did not know he was doing so), | ||

151 | continued fractions were used for many centuries before their real | ||

152 | discovery. | ||

153 | |||

154 | The history of continued fractions and Pad\'e approximants is also | ||

155 | quite important, since they played a leading role in the development | ||

156 | of some branches of mathematics. For example, they were the basis | ||

157 | for the proof of the transcendence of $\pi$ in 1882, an open | ||

158 | problem for more than two thousand years, and also for our modern | ||

159 | spectral theory of operators. Actually they still are of great | ||

160 | interest in many fields of pure and applied mathematics and in | ||

161 | numerical analysis, where they provide computer approximations to | ||

162 | special functions and are connected to some convergence acceleration | ||

163 | methods. Continued fractions are also used in number theory, | ||

164 | computer science, automata, electronics, etc. \ldots{} | ||

165 | \end{quote} | ||

166 | |||

167 | Notice that Theorem \ref{thm:ccfr0:scba0:cfenclosingneighbors} | ||

168 | has two components. First, it is shown that the highest-order | ||

169 | convergent with an acceptable denominator is closer to $a/b$ than | ||

170 | any Farey neighbor to this convergent (thus, this convergent must be | ||

171 | either a left or right Farey neighbor of $a/b$). Second, it is shown | ||

172 | what the other Farey neighbor must be. It is historically clear | ||

173 | that the properties of convergents as best rational approximations were | ||

174 | understood by the 17th century (this is the \emph{first} part of | ||

175 | Theorem \ref{thm:ccfr0:scba0:cfenclosingneighbors}). However, it | ||

176 | is not historically clear when the \emph{second} part of | ||

177 | Theorem \ref{thm:ccfr0:scba0:cfenclosingneighbors} was discovered. | ||

178 | |||

179 | Even in Khinchin's \index{Khinchin, A. Ya.} classic work, | ||

180 | \cite{bibref:b:KhinchinClassic}, Theorem 15, p. 22, Khinchin stops | ||

181 | just short of the result presented as the second part of | ||

182 | Theorem \ref{thm:ccfr0:scba0:cfenclosingneighbors}. Khinchin writes: | ||

183 | |||

184 | \begin{quote} | ||

185 | THEOREM 15. \em Every best approximation of a number is a convergent | ||

186 | or an intermediate fraction of the continued fraction representing | ||

187 | that number. | ||

188 | \end{quote} | ||

189 | |||

190 | \noindent{}Theorem \ref{thm:ccfr0:scba0:cfenclosingneighbors} goes | ||

191 | slightly farther than Khinchin's \emph{THEOREM 15}, above. | ||

192 | Khinchin \index{Khinchin, A. Ya.} states | ||

193 | that a best approximation will be a convergent or an intermediate | ||

194 | fraction---but Theorem \ref{thm:ccfr0:scba0:cfenclosingneighbors} | ||

195 | goes slightly farther to indicate \emph{exactly which} intermediate fraction | ||

196 | is potentially the best approximation. Khinchin's \emph{THEOREM 15} | ||

197 | is correct, but could be strengthened. Khinchin's work | ||

198 | was first published in 1935. This raises the [unlikely] possibility | ||

199 | that the second part of Theorem \ref{thm:ccfr0:scba0:cfenclosingneighbors} | ||

200 | had not been published even as recently as 1935, although | ||

201 | we (the authors) don't have the ability to confirm or | ||

202 | refute this. | ||

203 | |||

204 | In \cite{bibref:b:HistoryCfPadeApproxBrezinski}, p. 70, Brezinski | ||

205 | \index{Brezenski, Claude} | ||

206 | writes: | ||

207 | |||

208 | \begin{quote} | ||

209 | In the same period, algorithms equivalent to continued fractions were | ||

210 | still used to find approximate values for ratios and to simplify | ||

211 | fractions. We have already mentioned Albert Girard. | ||

212 | |||

213 | Among the other authors who treated the subject, the most prominent | ||

214 | is Daniel SCHWENTER \index{Schwenter, Daniel} | ||

215 | (N\"urnberg, 31.1.1585 - Altdorf, 19.1.1636), | ||

216 | who wrote two books ``\emph{Geometriae practicae novae et auctae | ||

217 | tractatus}'' published in 1627 and ``\emph{Delicae | ||

218 | Physico-mathematicae}'' which appeared in 1636 followed by a | ||

219 | second edition in 1651. | ||

220 | |||

221 | In his first book, Schwenter found approximations of 177/233 by | ||

222 | finding their g.c.d. and gave the successive convergents | ||

223 | 79/104, 19/25, 3/4, 1/1, and 0/1. His calculations were arranged | ||

224 | in a table\footnote{The table is reproduced in | ||

225 | \cite{bibref:b:HistoryCfPadeApproxBrezinski}, | ||

226 | but is omitted here.} \ldots{} although he gave no explanation of the method. | ||

227 | \end{quote} | ||

228 | |||

229 | On p. 84, Brezenski \index{Brezenski, Claude} writes: | ||

230 | |||

231 | \begin{quote} | ||

232 | Wallis \index{Wallis, John} also made use of continued fractions in his book | ||

233 | ``\emph{A treatise of algebra both historical and practical}'' | ||

234 | (published in 1685), to approximate ratios with large | ||

235 | numerators and denominators: | ||

236 | |||

237 | \emph{``Before I leave the business of Decimal Parts, and the | ||

238 | advantages which in practice may there cause; I have thought fit | ||

239 | here to insert a Process Of Reducing Fractions or Proportions to | ||

240 | smaller termes, retaining as near as may be, the just value.} | ||

241 | |||

242 | \emph{It was occasion'd by a Problem sent me (as I remember) about the | ||

243 | Year 1663 or 1664, by Dr. Lamplugh the present Bishop of Exeter from | ||

244 | (his Wives Father) Dr. Davenant then one of the Prebends | ||

245 | Residentaries of the Church of Salisbury, a very worthy Person, of | ||

246 | great Learning and Modesty; as I mire inderstand from persons | ||

247 | well acquainted with him, and by divers Writings of his which I have seen, | ||

248 | though I never had the opportunity of being personally acquainted with him, | ||

249 | otherwise than by Letter. And amongst | ||

250 | his other Learning, he was very well skilled the Mathematicks, | ||

251 | and a diligent Proficient therein.} | ||

252 | |||

253 | \emph{He sent me (as it abovesaid) a Fraction (which what it was I | ||

254 | do not now particulary remember) who's Numerator and Denominator | ||

255 | were, each of them of about six or seven places; and Proposed to | ||

256 | find the nearest Fraction in value to it, whose Denominator should | ||

257 | not be greater than 999.''} | ||

258 | |||

259 | \begin{center} | ||

260 | \rule{3in}{0.3mm} \\\ | ||

261 | \end{center} | ||

262 | |||

263 | \begin{center} | ||

264 | \emph{The Problem} \\ | ||

265 | \end{center} | ||

266 | |||

267 | \emph{A Fraction (or Proportion) being assigned, to sind one as near as | ||

268 | may be equal to it, in Numbers non exceeding a Number given, and in | ||

269 | the smallest Terms.} | ||

270 | |||

271 | \emph{As (for instance), the Fraction $\frac{2684769}{8376571}$ (or the | ||

272 | Proportion of 2684769 to 8376571) being assigned, to sind one equal to it | ||

273 | (if it may be) or at least the next Greater, or the next Lesser, | ||

274 | which may be expressed in Numbers not greater than 999; that is, in numbers | ||

275 | not exceeding three places.} | ||

276 | |||

277 | \begin{center} | ||

278 | \rule{3in}{0.3mm} \\ | ||

279 | \end{center} | ||

280 | |||

281 | \emph{If the Fraction sought (whose terms are not to be greater than | ||

282 | a Number given) be the Next Greater than a Fraction Proposed; divide the | ||

283 | proposed Fractions Denominator by its Numerator: If the Next-Lesser, then | ||

284 | the Numerator by the Denominator, continuing the Quotient in Decimal | ||

285 | Parts, to such an Accuracy as shall be sufficient; which Quotient | ||

286 | for the Next-Greater, is to be the Denominator answering to the | ||

287 | Numerator 1: But for the next Lesser, it is to be | ||

288 | the Numerator answering to the Denominator 1: Completing a Fraction | ||

289 | as near as shall be necessary to that Proposed, which Fraction I | ||

290 | call to First Fraction Compleat: And the same wanting the Appendage of | ||

291 | Decimal parts, I call, the First Fraction Cartail'd.} | ||

292 | |||

293 | \emph{Khen by this Appendage of the First Fraction, | ||

294 | divide 1 Integer, and by the Integer Number which is Next-Less then | ||

295 | the sull Quotient, (that is, in case such Quotient be just an | ||

296 | Interger Number, by the Integer Next-Less than it; but is it be an Interger | ||

297 | with Decimal parts annexed, than by that Integer | ||

298 | without those} | ||

299 | |||

300 | \emph{Decimal parts;) multiply both Terms of the first Fraction Compleat, | ||

301 | (the Numerator and the Denominator;) And the Products of such | ||

302 | Multiplication, I call the Continual Increments of those Terms respectively. | ||

303 | And so much as the Appendage of Decimal parts in such Continual Increment | ||

304 | wants of 1 Integer, I call the Complements of the Appendage of the | ||

305 | continual Increment.} | ||

306 | |||

307 | \emph{Then both to the Numerator and the Denominator of the First | ||

308 | Fraction, add (respectively) its continual Increment, which make the Terms | ||

309 | of the Second Fraction; and these again (respectively) | ||

310 | increased by the same Continual | ||

311 | Increment, make the Terms of the Third Fraction: And so onward, | ||

312 | as long as the Fraction so arising hath an Appendage, which is not less | ||

313 | than the Complement of the Appendage of the Continual Increment.} | ||

314 | |||

315 | \emph{But where such Appendage becomes less than that Complement, | ||

316 | that Fraction I call the Last of the First Order; which also is to | ||

317 | be the First of the Second Order.''} | ||

318 | \end{quote} | ||

319 | |||

320 | Although Wallis' archaic English above is difficult to decipher, | ||

321 | it appears that Wallis is describing the process of | ||

322 | obtaining the convergents and intermediate fractions of | ||

323 | the continued fraction representation of a rational number. | ||

324 | |||

325 | On p. 86, Brezenski writes: | ||

326 | |||

327 | \begin{quote} | ||

328 | We have already mentioned the Dutch mathematician and astronomer | ||

329 | Christiaan HUYGENS \index{Huygens, Christiaan} (The Hague, 14.4.1629 - The Hague, 8.6.1695). | ||

330 | He made several contributions to continued fractions and related | ||

331 | matters. | ||

332 | |||

333 | In 1682, Huygens built an automatic planetarium. To this end, | ||

334 | he used continued fractions, as described in his book | ||

335 | ``\emph{Descriptio automati planetarii}'', which was published | ||

336 | after his death (The Hague, 1698). In one year the earth | ||

337 | covers 359$^{\circ}$ $45'$ $40''$ $30'''$ and Saturn 12$^{\circ}$ | ||

338 | $13'$ $34''$ $18'''$, which gives the ratio 77708431/2640858. | ||

339 | |||

340 | For finding the smallest integers whose ratio is close to the preceding | ||

341 | one, he divided the greatest number by the smallest, then the smallest | ||

342 | by the first remainder, and so on, which is Euclid's algorithm. | ||

343 | He thus got | ||

344 | |||

345 | \begin{equation} | ||

346 | 29 + \cfrac{1}{2 + \cfrac{1}{2 + \cfrac{1}{1 + | ||

347 | \cfrac{1}{5 + \cfrac{1}{1 + \cfrac{1}{4 + \ldots{}}}}}}} | ||

348 | \nonumber | ||

349 | \end{equation} | ||

350 | |||

351 | for the ratio. | ||

352 | |||

353 | The fourth convergent of this continued fraction is 206/7, which | ||

354 | gave him the number of teeth for the gears of his planetarium, only | ||

355 | producing an error of $40'$ in a century! [H. 177], [H. 272]. | ||

356 | |||

357 | In a work, undated but not after 1687, he treats the general problem: | ||

358 | |||

359 | \emph{``Etant donn\'es deux grands nombres ayant entr'eux un | ||

360 | certain rapport, en trouver d'autres plus petits pour les dents | ||

361 | des roues qui ne soient pas incommodes par leurs grandeurs et qui | ||

362 | aient entr'eux \`a peu pr\`es le m\^eme rapport, | ||

363 | de telle facon qu'aucun couple de nombres plus petits ne | ||

364 | fournisse un rapport plus approchant de la vraie | ||

365 | valeur.''}\footnote{English translation \index{Raspide, Sandrine@de Raspide, Sandrine} | ||

366 | \cite{bibref:i:sandrinederaspide}: | ||

367 | \emph{If we consider two large numbers forming a given ratio, | ||

368 | we need to find another set of smaller numbers for the teeth of the gearwheels, | ||

369 | which are not inconvenient in their size and which bear the very same ratio | ||

370 | between them, in such a way that no other pair of smaller numbers | ||

371 | brings a ratio closer to the actual value.}} | ||

372 | |||

373 | Thus Huygens was conscious of the property of best approximation | ||

374 | exhibited by continued fractions. He explained his method | ||

375 | as follows: | ||

376 | |||

377 | \emph{``Pour trouver donc des nombres plus petits qui expriment | ||

378 | approximativement ce rapport, je divise le plus grand des nombres | ||

379 | par le plus petit, puis le plus petit par le reste de la premi\`ere | ||

380 | division et ensuite ce reste par le noveau reste \ldots{} | ||

381 | Poursuivant ce calcul aussi longtemps que possible, on parvient | ||

382 | enfin par la division \`a un reste 1.''}\footnote{English | ||

383 | translation \index{Raspide, Sandrine@de Raspide, Sandrine} | ||

384 | \cite{bibref:i:sandrinederaspide}: \emph{Thus to find some smaller numbers that | ||

385 | approximately express this ratio, I divide the largest of | ||

386 | the numbers by the smallest, then the smallest by the | ||

387 | remainder of the first division and then this remainder by | ||

388 | the new remainder, continuing this calculation as long as possible, | ||

389 | we finally end up with a division into a remainder of 1.}} | ||

390 | |||

391 | Then he makes the following comments: | ||

392 | |||

393 | \emph{``Or, lorsqu'on n\'eglige \`a partir d'une fraction | ||

394 | quelconque les derniers termes de la s\'erie et celles qui | ||

395 | la suivent, et qu'on r\'eduit les autres plus le | ||

396 | nombre entier \`a un commun d\'enominateur, le rapport de ce | ||

397 | dernier au num\'erateur, sera voisin de celui du plus | ||

398 | petit nombre donn\'e au plus grand; et la diff\'erence | ||

399 | sera si faible qu'il serait impossible d'obtenir un meilleur accord | ||

400 | avec des nombres plus petits.''}\footnote{English | ||

401 | translation \index{Raspide, Sandrine@de Raspide, Sandrine} | ||

402 | \cite{bibref:i:sandrinederaspide}: | ||

403 | \emph{However, when, from an ordinary fraction, we neglect | ||

404 | the last terms of the run and the ones that follow, and when | ||

405 | we reduce the others plus the integer to a common denominator, | ||

406 | the ratio of the latter to the numerator will be in the neighborhood | ||

407 | of the smallest given number to the largest; and the difference will | ||

408 | be so small that it would be impossible to obtain a better | ||

409 | approximation with smaller numbers.}} | ||

410 | |||

411 | He proves this result and applies it to the continued fraction | ||

412 | for $\pi$. | ||

413 | |||

414 | Let us give the opinion of the French astronomer | ||

415 | \index{Delambre, Jean Baptiste Joseph}Jean Baptiste | ||

416 | Joseph DELAMBRE (Amiens, 19.9.1749 - Paris, 19.8.1822), about | ||

417 | this part of Huygens' work. It is quite interesting [H. 108]: | ||

418 | |||

419 | \emph{`` \ldots{}; enfin il d\'ecrit son plan\'etaire.}\footnote{English | ||

420 | translation \index{Raspide, Sandrine@de Raspide, Sandrine} | ||

421 | \cite{bibref:i:sandrinederaspide}: | ||

422 | \emph{\ldots{}; finally, he describes his planetarium.}} | ||

423 | |||

424 | \emph{Ces sortes de machines ne sont que des objets de | ||

425 | curiosit\'e pour les amateurs, ils sont absolument inutiles | ||

426 | \`a l'Astronomie; celle \index{Huygens, Christiaan}d'Huygens | ||

427 | \'etait destin\'ee \`a montrer | ||

428 | les mouvements elliptiques des plan\`etes, suivant les id\'ees | ||

429 | de \index{Kepler, Johannes}K\'epler. Le probl\`eme \`a r\'esoudre \'etait celui-ci: | ||

430 | Etant donn\'e deux grands nombres, trouver deux autres nombres plus | ||

431 | pitits et plus commodes, qui soient \`a peu pr\`es dans la m\^eme raison. | ||

432 | Il y emploie les fractions continues, et sans donner la | ||

433 | th\'eorie analytique de ces fractions, il les applique \`a des | ||

434 | exemples. Il trouve ainsi le nombre des dents qui'il convient de donner | ||

435 | aux roues.}\footnote{English translation \index{Raspide, Sandrine@de Raspide, Sandrine} | ||

436 | \cite{bibref:i:sandrinederaspide}: \emph{These kinds of machines are | ||

437 | mere objects of curiosity for the amateurs, completely useless to astronomy; | ||

438 | Huygens' machine was meant to demonstrate the elliptic movements of the | ||

439 | planets, following Kepler's ideas. The problem to solve was the following: | ||

440 | given two large numbers, we need to find two other numbers, smaller and | ||

441 | more convenient, which are more or less in the same ratio. To achieve | ||

442 | this, Huygens uses continued ratios, and, without giving the analytic | ||

443 | theory of these ratios, he applies it to some examples. Thus, he is able | ||

444 | to determine the number of teeth needed for the gearwheels.}} | ||

445 | |||

446 | \emph{Cette propri\'et\'e des fractions continues, para\^{\i}t \`a | ||

447 | \index{Lagrange, Joseph-Louis}Lagrange, une des principales d\'ecouvertes | ||

448 | d'Huygens. Cet \'eloge | ||

449 | un peu exag\'er\'e fut sans doute dict\'e \`a | ||

450 | Lagrange par l'usage qu'il a su faire de ces fractions dans l'Analyse. | ||

451 | Quelques g\'eom\`etres ont paru douter des avantages de ces fractions et | ||

452 | de l'utilit\'e | ||

453 | qu'elles peuvent avoir dans les recherches analytiques. Quant au | ||

454 | probl\`eme des rouages, il nous semble qu'on peut le r\'esoudre d'une | ||

455 | mani\`ere plus simple et plus commode par l'Arithm\'etique ordinaire. | ||

456 | Nous avons d\'ej\`a appliqu\'e notre m\'ethode | ||

457 | aux intercalations du calendrier. Nous allons l'appliquer aux deux | ||

458 | exemples choisis par Huyhens.''}\footnote{English | ||

459 | translation \index{Raspide, Sandrine@de Raspide, Sandrine} | ||

460 | \cite{bibref:i:sandrinederaspide}: | ||

461 | \emph{The property of continued fractions seems, to Lagrange, | ||

462 | one of the main discoveries of Huygens. This slightly overdone | ||

463 | praise was probably induced in Lagrange for the use that he made of | ||

464 | the fractions in his Analysis. Some surveyors seemed to have questioned | ||

465 | the advantages of these fractions and their use in analytical research. | ||

466 | As far as the gearing problem is concerned, it seems to us that we can | ||

467 | solve it in a simpler and easier way with ordinary arithmetic. | ||

468 | We have already applied our methodology to the intercalation of the calendar. | ||

469 | We are going to apply it to the two examples chosen by Huygens.}} | ||

470 | |||

471 | Delambre concludes: | ||

472 | |||

473 | \emph{``Les fractions continues ne m'ont jamais paru qu'une chose | ||

474 | curieuse qui, au reste, ne servait qu'\`a obscurcir et compliquer et je | ||

475 | n'en ai jamais fait d'usage que pour m'en d\'emontrer | ||

476 | l'inutilit\'e.''}\footnote{English translation | ||

477 | \index{Raspide, Sandrine@de Raspide, Sandrine} | ||

478 | \cite{bibref:i:sandrinederaspide}: | ||

479 | \emph{Continued fractions never appeared to me as something more | ||

480 | than a mere curiosity that, at the end of the day, only serves | ||

481 | to darken and complicate matters, and I only used them to | ||

482 | demonstrate their uselessness.}} | ||

483 | |||

484 | This was not a prophetic view! | ||

485 | \end{quote} | ||

486 | |||

487 | Thus, it is clear that the use of continued fraction convergents | ||

488 | as best rational approximations dates back to at least the | ||

489 | 17th century (this is the first part of | ||

490 | Theorem \ref{thm:ccfr0:scba0:cfenclosingneighbors}). However, | ||

491 | the details of the historical appearance of the second part of | ||

492 | Theorem \ref{thm:ccfr0:scba0:cfenclosingneighbors} (the formula | ||

493 | for the other Farey neighbor, Eq. \ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01}) | ||

494 | are not known to the authors. | ||

495 | |||

496 | |||

497 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

498 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

499 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

500 | \section{Overview Of The Apparatus} | ||

501 | %Section tag: PAR0 | ||

502 | |||

503 | The apparatus of continued fractions is best viewed as | ||

504 | an alternate apparatus for representing real numbers. | ||

505 | Knowledge of the first $n$ partial quotients of | ||

506 | the continued fraction representation of a real number | ||

507 | $x$ is equivalent to the knowledge that the number lies | ||

508 | in a certain partition (Eqns. | ||

509 | \ref{eq:ccfr0:spar0:01}, | ||

510 | \ref{eq:ccfr0:spar0:02}, and \ref{eq:ccfr0:spar0:03}). With additional | ||

511 | partial quotients, the partitions become more restrictive. | ||

512 | |||

513 | \begin{equation} | ||

514 | \label{eq:ccfr0:spar0:01} | ||

515 | (x=[a_0] \vee x=[a_0; \ldots ] ) \leftrightarrow (a_0 \leq x < a_0 + 1) | ||

516 | \end{equation} | ||

517 | |||

518 | \begin{equation} | ||

519 | \label{eq:ccfr0:spar0:02} | ||

520 | (x=[a_0; a_1] \vee x=[a_0; a_1, \ldots ] ) \leftrightarrow | ||

521 | \left( | ||

522 | { | ||

523 | a_0 + \frac{1}{a_1 + 1} < x \leq a_0 + \frac{1}{a_1} | ||

524 | } | ||

525 | \right) | ||

526 | \end{equation} | ||

527 | |||

528 | \begin{equation} | ||

529 | \label{eq:ccfr0:spar0:03} | ||

530 | \begin{array}{c} | ||

531 | (x=[a_0; a_1, a_2] \vee x=[a_0; a_1, a_2, \ldots ] ) \vspace{0.05in}\\ | ||

532 | \updownarrow \vspace{0.0in}\\ | ||

533 | \left( | ||

534 | { | ||

535 | a_0+\cfrac{1}{a_1 + \cfrac{1}{a_2}} \leq x < a_0+\cfrac{1}{a_1 + \cfrac{1}{a_2+1}} | ||

536 | } | ||

537 | \right) | ||

538 | \end{array} | ||

539 | \end{equation} | ||

540 | |||

541 | Algorithms for finding the continued fraction representation | ||

542 | of a real number are best viewed as algorithms for | ||

543 | determining in which partition a real number lies. However, what is | ||

544 | special (for our purposes) is that the partitions imposed by the | ||

545 | apparatus of continued fractions have a special relationship | ||

546 | with best rational approximations---namely, that all numbers (both | ||

547 | rational and irrational) with the same partial quotients up to a | ||

548 | point also have the same Farey neighbors up to a certain order. | ||

549 | Stated more colloquially, the apparatus of continued fractions | ||

550 | hacks up the real number line in a way that is especially meaningful | ||

551 | for finding best rational approximations. | ||

552 | |||

553 | |||

554 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

555 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

556 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

557 | \section[CF Representation Of Rationals] | ||

558 | {Continued Fraction Representation Of Rational Numbers} | ||

559 | %Section tag: CRN0 | ||

560 | |||

561 | Without proof, we present the following algorithm, Algorithm | ||

562 | \ref{alg:ccfr0:scrn0:akgenalg}, for | ||

563 | determining the continued fraction representation (i.e. the partial | ||

564 | quotients) of a non-negative | ||

565 | rational number $a/b$. | ||

566 | |||

567 | \begin{vworkalgorithmstatementpar}{Continued Fraction Representation Of | ||

568 | A Rational Number \mbox{\boldmath $a/b$}} | ||

569 | \label{alg:ccfr0:scrn0:akgenalg} | ||

570 | \begin{alglvl0} | ||

571 | \item $k:=-1$. | ||

572 | \item $divisor_{-1} := a$. | ||

573 | \item $remainder_{-1} := b$. | ||

574 | |||

575 | \item Repeat | ||

576 | |||

577 | \begin{alglvl1} | ||

578 | \item $k := k + 1$. | ||

579 | \item $dividend_k := divisor_{k-1}$. | ||

580 | \item $divisor_k := remainder_{k-1}$. | ||

581 | \item $a_k := dividend_k \; div \; divisor_k$. | ||

582 | \item $remainder_k := dividend_k \; mod \; divisor_k$. | ||

583 | \end{alglvl1} | ||

584 | |||

585 | \item Until ($remainder_k = 0$). | ||

586 | \end{alglvl0} | ||

587 | \end{vworkalgorithmstatementpar} | ||

588 | %\vworkalgorithmfooter{} | ||

589 | |||

590 | \begin{vworkexamplestatement} | ||

591 | \label{ex:ccfr0:scrn0:01} | ||

592 | Find the continued fraction partial quotients of | ||

593 | $67/29$.\footnote{This example is reproduced from | ||

594 | Olds \cite{bibref:b:OldsClassic}, p. 8.} | ||

595 | \end{vworkexamplestatement} | ||

596 | \begin{vworkexampleparsection}{Solution} | ||

597 | \begin{table} | ||

598 | \caption{Continued Fraction Partial Quotients Of $67/29$ (Example \ref{ex:ccfr0:scrn0:01})} | ||

599 | \label{tbl:ccfr0:scrn0:01} | ||

600 | \begin{center} | ||

601 | \begin{tabular}{|c|c|c|c|c|} | ||

602 | \hline | ||

603 | \small{Index} & \small{$dividend_k$} & \small{$divisor_k$} & \small{$a_k$} & \small{$remainder_k$} \\ | ||

604 | \small{($k$)} & & & & \\ | ||

605 | \hline | ||

606 | \hline | ||

607 | \small{-1} & \small{N/A} & \small{67} & \small{N/A} & \small{29} \\ | ||

608 | \hline | ||

609 | \small{0} & \small{67} & \small{29} & \small{2} & \small{9} \\ | ||

610 | \hline | ||

611 | \small{1} & \small{29} & \small{9} & \small{3} & \small{2} \\ | ||

612 | \hline | ||

613 | \small{2} & \small{9} & \small{2} & \small{4} & \small{1} \\ | ||

614 | \hline | ||

615 | \small{3} & \small{2} & \small{1} & \small{2} & \small{0} \\ | ||

616 | \hline | ||

617 | \end{tabular} | ||

618 | \end{center} | ||

619 | \end{table} | ||

620 | Table \ref{tbl:ccfr0:scrn0:01} shows the application of | ||

621 | Algorithm \ref{alg:ccfr0:scrn0:akgenalg} to find the | ||

622 | continued fraction partial quotients of $67/29$. From | ||

623 | Table \ref{tbl:ccfr0:scrn0:01}, the continued fraction | ||

624 | representation of $67/29$ is $[2;3,4,2]$. | ||

625 | \end{vworkexampleparsection} | ||

626 | \vworkexamplefooter{} | ||

627 | |||

628 | The process of obtaining the continued fraction representation of | ||

629 | a rational number is a | ||

630 | process of obtaining each partial quotient $a_i$, and then processing the | ||

631 | remainder at each step to obtain further partial quotients. Noting that | ||

632 | the dividend and divisor at each step come from previous remainders | ||

633 | (except for $k=0$ and $k=1$) allows us to simplify notation from | ||

634 | Algorithm \ref{alg:ccfr0:scrn0:akgenalg}. If $r_i$ is used to | ||

635 | denote the remainder from the division that produced $a_i$, the following | ||

636 | recursive equations come immediately. | ||

637 | |||

638 | \begin{equation} | ||

639 | \label{eq:ccfr0:scrn0:00a} | ||

640 | \frac{a}{b} | ||

641 | = | ||

642 | a_0 + \frac{r_0}{b} | ||

643 | = | ||

644 | a_0 + \frac{1}{\frac{b}{r_0}} | ||

645 | , \; 0 < r_0 < b | ||

646 | \end{equation} | ||

647 | |||

648 | \begin{equation} | ||

649 | \label{eq:ccfr0:scrn0:00b} | ||

650 | \frac{b}{r_0} | ||

651 | = | ||

652 | a_1 + \frac{r_1}{r_0} | ||

653 | , \; 0 < r_1 < r_0 | ||

654 | \end{equation} | ||

655 | |||

656 | \begin{equation} | ||

657 | \label{eq:ccfr0:scrn0:00c} | ||

658 | \frac{r_0}{r_1} | ||

659 | = | ||

660 | a_2 + \frac{r_2}{r_1} | ||

661 | , \; 0 < r_2 < r_1 | ||

662 | \end{equation} | ||

663 | |||

664 | \noindent{}Finally, nearing the termination of | ||

665 | Algorithm \ref{alg:ccfr0:scrn0:akgenalg}: | ||

666 | |||

667 | \begin{equation} | ||

668 | \label{eq:ccfr0:scrn0:00d} | ||

669 | \frac{r_{n-3}}{r_{n-2}} | ||

670 | = | ||

671 | a_{n-1} + \frac{r_{n-1}}{r_{n-2}} | ||

672 | , \; 0 < r_{n-1} < r_{n-2} | ||

673 | \end{equation} | ||

674 | |||

675 | \begin{equation} | ||

676 | \label{eq:ccfr0:scrn0:00e} | ||

677 | \frac{r_{n-2}}{r_{n-1}} | ||

678 | = | ||

679 | a_n | ||

680 | \end{equation} | ||

681 | |||

682 | A natural question to ask is whether Algorithm \ref{alg:ccfr0:scrn0:akgenalg} | ||

683 | will always terminate---that is, whether we can always find a continued | ||

684 | fraction representation of a rational number. We present this result | ||

685 | as Lemma \ref{lem:ccfr0:scrn0:alwaysterminates}. | ||

686 | |||

687 | \begin{vworklemmastatement} | ||

688 | \label{lem:ccfr0:scrn0:alwaysterminates} | ||

689 | Algorithm \ref{alg:ccfr0:scrn0:akgenalg} will always terminate: that is, | ||

690 | every rational number has a finite continued fraction representation | ||

691 | $[a_0; a_1, \ldots{} , a_n]$. | ||

692 | \end{vworklemmastatement} | ||

693 | \begin{vworklemmaproof} | ||

694 | Note in Algorithm \ref{alg:ccfr0:scrn0:akgenalg} and in | ||

695 | (\ref{eq:ccfr0:scrn0:00a}) through (\ref{eq:ccfr0:scrn0:00e}) | ||

696 | that the remainder of one round becomes the divisor of the | ||

697 | next round, hence the remainders must form a decreasing sequence | ||

698 | |||

699 | \begin{equation} | ||

700 | \label{eq:lem:ccfr0:scrn0:alwaysterminates} | ||

701 | r_0 > r_1 > r_2 > \ldots{} > r_{n-2} > r_{n-1} , | ||

702 | \end{equation} | ||

703 | |||

704 | because in general a remainder must be less than the divisor in | ||

705 | the division that created it. | ||

706 | \end{vworklemmaproof} | ||

707 | \vworklemmafooter{} | ||

708 | |||

709 | |||

710 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

711 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

712 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

713 | \section{Convergents And Intermediate Fractions} | ||

714 | %Section tag: CNV0 | ||

715 | \label{ccfr0:scnf0} | ||

716 | |||

717 | Lemma \ref{lem:ccfr0:scrn0:alwaysterminates} shows that every | ||

718 | rational number has a finite continued fraction representation. A second | ||

719 | reasonable question to ask is whether every finite simple continued | ||

720 | fraction corresponds to a rational number. The most convincing way | ||

721 | to answer that question would be to devise a concrete procedure for | ||

722 | [re-]constructing a rational number from its continued fraction | ||

723 | representation. | ||

724 | |||

725 | Given a finite continued fraction $[a_0; a_1, \ldots{}, a_n]$, it is | ||

726 | obvious that a rational number can be constructed using the same | ||

727 | algebraic technique that would be applied by hand. Such a technique | ||

728 | involves ``reconstruction from the right'' because we would begin | ||

729 | by using $a_n$ and then work backwards to $a_0$. We illustrate | ||

730 | the most obvious technique with an example. | ||

731 | |||

732 | \begin{vworkexamplestatement} | ||

733 | \label{ex:ccfr0:scnv0:abreconstructionfromright:01} | ||

734 | Find a rational number $a/b$ corresponding to the | ||

735 | continued fraction $[2;3,4,2]$. | ||

736 | \end{vworkexamplestatement} | ||

737 | \begin{vworkexampleparsection}{Solution} | ||

738 | The most obvious technique is to write out the continued fraction and then to | ||

739 | algebraically simplify the continued fraction from the bottom up (this | ||

740 | is what we call ``working from the right'', as we begin with $a_n$). | ||

741 | (\ref{eq:ccfr0:scnv0:ex:abreconstructionfromright:00}) through | ||

742 | (\ref{eq:ccfr0:scnv0:ex:abreconstructionfromright:02}) | ||

743 | illustrate this technique. | ||

744 | |||

745 | \begin{equation} | ||

746 | \label{eq:ccfr0:scnv0:ex:abreconstructionfromright:00} | ||

747 | [2;3,4,2] = | ||

748 | 2 + \cfrac{1}{3 + \cfrac{1}{4 + \cfrac{1}{2}}} | ||

749 | \end{equation} | ||

750 | |||

751 | \begin{equation} | ||

752 | \label{eq:ccfr0:scnv0:ex:abreconstructionfromright:01} | ||

753 | [2;3,4,2] = | ||

754 | 2 + \cfrac{1}{3 + \cfrac{2}{9}} | ||

755 | \end{equation} | ||

756 | |||

757 | \begin{equation} | ||

758 | \label{eq:ccfr0:scnv0:ex:abreconstructionfromright:02} | ||

759 | [2;3,4,2] = | ||

760 | 2 + \frac{9}{29} = \frac{67}{29} | ||

761 | \end{equation} | ||

762 | |||

763 | \end{vworkexampleparsection} | ||

764 | \vworkexamplefooter{} | ||

765 | |||

766 | Although converting a continued fraction $[a_0; a_1, \ldots{}, a_n]$ | ||

767 | to a rational number working ``from the right'' is the most | ||

768 | intuitively obvious technique because it mirrors how a | ||

769 | continued fraction would most naturally be simplified by | ||

770 | hand, it is also possible to convert a continued fraction to | ||

771 | a rational number ``from the left''. In all subsequent | ||

772 | discussions we embrace the ``from the left'' technique because | ||

773 | it allows us to more economically calculate \emph{convergents}, which | ||

774 | have special properties, and which we now describe. | ||

775 | |||

776 | \index{continued fraction!convergent} | ||

777 | The \emph{kth order convergent} of a continued fraction | ||

778 | $[a_0; a_1, \ldots{}, a_n]$ is the irreducible rational number | ||

779 | corresponding to $[a_0; a_1, \ldots{}, a_k]$, $k \leq n$. | ||

780 | In other words, the $k$th order convergent is the irreducible rational number | ||

781 | corresponding to the first $k+1$ partial quotients of a | ||

782 | continued fraction.\footnote{``$k+1$'' because the notational | ||

783 | numbering | ||

784 | for partial quotients starts at 0 rather than 1.} | ||

785 | |||

786 | An $n$th order continued fraction $[a_0; a_1, \ldots{}, a_n]$ | ||

787 | has $n+1$ convergents, $[a_0]$, | ||

788 | $[a_0; a_1]$, \ldots{}, and $[a_0; a_1, \ldots{}, a_n]$. | ||

789 | We denote the $k$th order convergent as $s_k$, with numerator | ||

790 | $p_k$ and denominator $q_k$. | ||

791 | |||

792 | \begin{vworkexamplestatement} | ||

793 | \label{ex:ccfr0:scnv0:convergentexample:01} | ||

794 | Find all convergents of $[2;3,4,2]$. | ||

795 | \end{vworkexamplestatement} | ||

796 | \begin{vworkexampleparsection}{Solution}\hspace{-0.4em}\footnote{Canonically, it is | ||

797 | required that all convergents be irreducible. Any valid method can be used to | ||

798 | calculate convergents---including algebraic simplification---so long as the | ||

799 | rational numbers obtained are irreducible.} | ||

800 | \begin{equation} | ||

801 | s_0 = [a_0] = [2] = 2 = \frac{2}{1} = \frac{p_0}{q_0} | ||

802 | \end{equation} | ||

803 | |||

804 | \begin{equation} | ||

805 | s_1 = [a_0;a_1] = [2;3] = 2 + \frac{1}{3} = \frac{7}{3} = \frac{p_1}{q_1} | ||

806 | \end{equation} | ||

807 | |||

808 | \begin{equation} | ||

809 | s_2 = [a_0;a_1,a_2] = | ||

810 | [2;3,4] = | ||

811 | 2 + \cfrac{1}{3 + \cfrac{1}{4}} = \frac{30}{13} = \frac{p_2}{q_2} | ||

812 | \end{equation} | ||

813 | |||

814 | \begin{equation} | ||

815 | s_3 = [a_0;a_1,a_2,a_3] = [2;3,4,2] = | ||

816 | 2 + \cfrac{1}{3 + \cfrac{1}{4 + \cfrac{1}{2}}} = \frac{67}{29} = \frac{p_3}{q_3} | ||

817 | \end{equation} | ||

818 | \end{vworkexampleparsection} | ||

819 | \vworkexamplefooter{} | ||

820 | |||

821 | We now move on to the question of how to convert a continued fraction | ||

822 | to a rational number ``from the left''. We present the | ||

823 | canonical algorithm for construction of convergents ``from the left''. | ||

824 | In addition | ||

825 | to producing irreducible rational numbers (we prove this property | ||

826 | later), the algorithm is | ||

827 | convenient because it is economical---lower-order convergents | ||

828 | are used in the calculation of higher-order convergents and there | ||

829 | are no wasted calculations. | ||

830 | |||

831 | \begin{vworktheoremstatementpar}{Rule For Canonical Construction Of Continued Fraction | ||

832 | Convergents} | ||

833 | \label{thm:ccfr0:scnv0:canonicalconvergentconstruction} | ||

834 | The numerators $p_i$ and the denominators $q_i$ of the $i$th | ||

835 | convergent $s_i$ of the continued fraction | ||

836 | $[a_0;a_1, \ldots{} , a_n]$ satisfy the equations | ||

837 | |||

838 | \begin{eqnarray} | ||

839 | \label{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:01} | ||

840 | p_i & = & a_i p_{i-1} + p_{i-2} \\ | ||

841 | \label{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:02} | ||

842 | q_i & = & a_i q_{i-1} + q_{i-2} | ||

843 | \end{eqnarray} | ||

844 | |||

845 | \noindent{}with the initial values | ||

846 | |||

847 | \begin{eqnarray} | ||

848 | \label{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:03} | ||

849 | p_0 = a_0, & & p_1 = a_0 a_1 + 1, \\ | ||

850 | \label{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:04} | ||

851 | q_0 = 1, & & q_1 = a_1 . | ||

852 | \end{eqnarray} | ||

853 | \end{vworktheoremstatementpar} | ||

854 | \begin{vworktheoremproof}\hspace{-0.4em}\footnote{Reproduced nearly | ||

855 | verbatim from \cite{bibref:b:OldsClassic}, Theorem 1.3, pp. 21-23.} | ||

856 | The proof is inductive. First, the case of $i=2$ is verified, | ||

857 | then an inductive step is used to show that the theorem applies | ||

858 | for $i \geq 3$. | ||

859 | |||

860 | To create a canonical form, we assign | ||

861 | $s_0 = [a_0] = p_0/q_0 = a_0/1$. Thus, in all cases, $p_0 = a_0$ | ||

862 | and $q_0 = 1$. Similarly, to create a unique canonical form, | ||

863 | |||

864 | \begin{equation} | ||

865 | \label{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:05} | ||

866 | s_1 = [a_0;a_1] = a_0 + \frac{1}{a_1} = \frac{a_0 a_1 + 1}{a_1} = \frac{p_1}{q_1} , | ||

867 | \end{equation} | ||

868 | |||

869 | \noindent{}and canonically, $p_1 = a_0 a_1 + 1$ and $q_1 = a_1$. | ||

870 | |||

871 | For $i=2$, we need to verify that the algebraic results coincide with the | ||

872 | claims of the theorem. Simplifying $s_2$ algebraically leads to | ||

873 | |||

874 | \begin{equation} | ||

875 | \label{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:06} | ||

876 | \begin{array}{c} | ||

877 | s_2 = [a_0;a_1,a_2] = | ||

878 | a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2}} = | ||

879 | a_0 + \cfrac{1}{\cfrac{a_1 a_2 + 1}{a_2}} = a_0 + \cfrac{a_2}{a_1 a_2 + 1} \\ | ||

880 | \\ | ||

881 | =\cfrac{a_0 (a_1 a_2 + 1) + a_2}{a_1 a_2 + 1} | ||

882 | =\cfrac{a_2(a_0 a_1 + 1) + a_0}{a_2 a_1 + 1} . | ||

883 | \end{array} | ||

884 | \end{equation} | ||

885 | |||

886 | \noindent{}On the other hand, applying the recursive formula | ||

887 | claimed by the theorem (Eqns. | ||

888 | \ref{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:01}, | ||

889 | \ref{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:02}) yields | ||

890 | |||

891 | \begin{equation} | ||

892 | \label{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:07} | ||

893 | s_2 = \frac{a_2 p_1 + p_0}{a_2 q_1 + q_0} | ||

894 | = \frac{a_2(a_0 a_1 + 1) + a_0}{a_2 (a_1) + 1} , | ||

895 | \end{equation} | ||

896 | |||

897 | which, on inspection, is consistent with the results of | ||

898 | (\ref{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:06}). | ||

899 | |||

900 | We now prove the inductive step. Assume that | ||

901 | the recursive relationships supplied as | ||

902 | (\ref{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:01}) | ||

903 | and (\ref{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:02}) | ||

904 | hold up through some $s_k = p_k/q_k$. We would like to show that | ||

905 | (\ref{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:01}) | ||

906 | and (\ref{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:02}) | ||

907 | then hold for $s_{k+1}$. | ||

908 | |||

909 | $s_k$ is a fraction of the form | ||

910 | |||

911 | \begin{equation} | ||

912 | \label{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:07b} | ||

913 | s_k | ||

914 | = | ||

915 | [a_0; a_1, a_2, \ldots , a_k] | ||

916 | = | ||

917 | a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 | ||

918 | + \cfrac{1}{\;\;\;\;\;\;\;\;\;\;\;\;\;\;\ldots + | ||

919 | \cfrac{1}{a_{k-1} + \cfrac{1}{a_k}}}}} . | ||

920 | \end{equation} | ||

921 | |||

922 | In order to form $s_{k+1}$, note that we can replace $a_k$ by | ||

923 | $a_k + 1/a_{k + 1}$. (Note that there is no requirement | ||

924 | in Eqns. \ref{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:01}, | ||

925 | \ref{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:02}, | ||

926 | \ref{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:06}, | ||

927 | \ref{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:07}, | ||

928 | or \ref{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:07b} | ||

929 | that the partial quotients $a_i$ be integers.) | ||

930 | In other words, we can form a | ||

931 | $k$th order continued fraction having the same value as a | ||

932 | $k+1$th order continued fraction by substituting | ||

933 | $a_k := a_k + \frac{1}{a_{k + 1}}$. Using this substitution | ||

934 | we can calculate $s_{k+1}$ using the same recursive | ||

935 | relationship shown to be valid in calculating $s_k$: | ||

936 | |||

937 | \begin{equation} | ||

938 | \label{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:08} | ||

939 | \begin{array}{c} | ||

940 | s_{k+1} = | ||

941 | \cfrac | ||

942 | {\left( {a_k+\cfrac{1}{a_{k+1}} } \right) p_{k-1} + p_{k-2}} | ||

943 | {\left( {a_k+\cfrac{1}{a_{k+1}} } \right) q_{k-1} + q_{k-2}} | ||

944 | = | ||

945 | \cfrac | ||

946 | {(a_k a_{k+1} + 1) p_{k-1} + a_{k+1} p_{k-2}} | ||

947 | {(a_k a_{k+1} + 1) q_{k-1} + a_{k+1} q_{k-2}} \\ | ||

948 | \\ | ||

949 | = | ||

950 | \cfrac | ||

951 | {a_{k+1} (a_k p_{k-1} + p_{k-2}) + p_{k-1}} | ||

952 | {a_{k+1} (a_k q_{k-1} + q_{k-2}) + q_{k-1}} | ||

953 | \end{array} | ||

954 | \end{equation} | ||

955 | |||

956 | Now, we can use the assumption that the recursive relationships | ||

957 | hold for $s_k$, i.e. | ||

958 | |||

959 | \begin{eqnarray} | ||

960 | \label{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:09} | ||

961 | p_k = a_k p_{k-1} + p_{k-2} \\ | ||

962 | \label{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:10} | ||

963 | q_k = a_k q_{k-1} + q_{k-2} | ||

964 | \end{eqnarray} | ||

965 | |||

966 | Substituting | ||

967 | (\ref{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:09}) and | ||

968 | (\ref{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:10}) into | ||

969 | (\ref{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:08}) yields | ||

970 | |||

971 | \begin{equation} | ||

972 | \label{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:11} | ||

973 | s_{k+1} = \frac{p_{k+1}}{q_{k+1}} | ||

974 | = \frac{a_{k+1} p_k + p_{k-1}}{a_{k+1} q_k + q_{k-1}} . | ||

975 | \end{equation} | ||

976 | |||

977 | \noindent{}This completes the inductive step and the proof. | ||

978 | \end{vworktheoremproof} | ||

979 | \begin{vworktheoremparsection}{Remarks} | ||

980 | Note that this algorithm gives a way to convert a continued fraction | ||

981 | $[a_0;a_1,\ldots{},a_n]$ to a rational number $a/b$, as the value of | ||

982 | a continued fraction is the value of the final convergent $s_n$. | ||

983 | Note also that it is possible to convert a continued fraction to | ||

984 | a rational number starting from $a_n$ (i.e. working ``from | ||

985 | the right''), and that starting with $a_n$ is probably the | ||

986 | more intuitive approach. | ||

987 | \end{vworktheoremparsection} | ||

988 | \vworktheoremfooter{} | ||

989 | |||

990 | It is sometimes convenient to consider a convergent of order | ||

991 | $-1$ (\cite{bibref:b:KhinchinClassic}, p. 5), and for | ||

992 | algebraic convenience to adopt the convention that | ||

993 | $p_{-1} = 1$ and $q_{-1} = 0$. If this is done, the recursive | ||

994 | relationships of Theorem \ref{thm:ccfr0:scnv0:canonicalconvergentconstruction} | ||

995 | apply for $k \geq 1$ rather than for $k \geq 2$. All of the subsequent | ||

996 | theorems and proofs assume this convention. | ||

997 | |||

998 | We now prove several properties of convergents. | ||

999 | |||

1000 | \begin{vworktheoremstatement} | ||

1001 | \label{thm:ccfr0:scnv0:crossproductminusone} | ||

1002 | For all $k \geq 0$, | ||

1003 | |||

1004 | \begin{equation} | ||

1005 | \label{eq:ccfr0:scnv0:thm:crossproductminusone:00} | ||

1006 | q_k p_{k-1} - p_k q_{k-1} = (-1)^k | ||

1007 | \end{equation} | ||

1008 | \end{vworktheoremstatement} | ||

1009 | \begin{vworktheoremproof}\hspace{-0.4em}\footnote{From | ||

1010 | \cite{bibref:b:KhinchinClassic}, Theorem 2, p. 5.} | ||

1011 | Multiplying (\ref{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:01}) | ||

1012 | by $p_{k-1}$, multiplying | ||

1013 | (\ref{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:02}) by | ||

1014 | $q_{k-1}$, then subtracting the equations yields | ||

1015 | |||

1016 | \begin{equation} | ||

1017 | \label{eq:ccfr0:scnv0:thm:crossproductminusone:01} | ||

1018 | q_k p_{k-1} - p_k q_{k-1} = -(q_{k-1} p_{k-2} - p_{k-1} q_{k-2}) , | ||

1019 | \end{equation} | ||

1020 | |||

1021 | and since $q_0 p_{-1} - p_0 q_{-1} = 1$, the theorem is | ||

1022 | proved. | ||

1023 | \end{vworktheoremproof} | ||

1024 | \begin{vworktheoremparsection}{Corollary I} | ||

1025 | For all $k \geq 1$, | ||

1026 | |||

1027 | \begin{equation} | ||

1028 | \label{eq:ccfr0:scnv0:thm:crossproductminusone:02} | ||

1029 | \frac{p_{k-1}}{q_{k-1}} - \frac{p_k}{q_k} = \frac{(-1)^k}{q_k q_{k-1}} . | ||

1030 | \end{equation} | ||

1031 | \end{vworktheoremparsection} | ||

1032 | \begin{vworktheoremproof} | ||

1033 | (\ref{eq:ccfr0:scnv0:thm:crossproductminusone:02}) can be obtained | ||

1034 | in a straightforward way by algebraic operations on | ||

1035 | (\ref{eq:ccfr0:scnv0:thm:crossproductminusone:00}). | ||

1036 | \end{vworktheoremproof} | ||

1037 | %\vworktheoremfooter{} | ||

1038 | |||

1039 | \begin{vworktheoremstatement} | ||

1040 | \label{thm:ccfr0:scnv0:crossproductminusonebacktwo} | ||

1041 | For all $k \geq 1$, | ||

1042 | |||

1043 | \begin{equation} | ||

1044 | q_k p_{k-2} - p_k q_{k-2} = (-1)^{k-1} a_k . | ||

1045 | \end{equation} | ||

1046 | \end{vworktheoremstatement} | ||

1047 | \begin{vworktheoremproof}\hspace{-0.4em}\footnote{From | ||

1048 | \cite{bibref:b:KhinchinClassic}, Theorem 3, p. 6.} | ||

1049 | By multiplying (\ref{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:01}) | ||

1050 | by $q_{k-2}$ and | ||

1051 | (\ref{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:02}) | ||

1052 | by $p_{k-2}$ and then subtracting the first from the | ||

1053 | second, we obtain, on the basis of Theorem | ||

1054 | \ref{thm:ccfr0:scnv0:crossproductminusone}, | ||

1055 | |||

1056 | \begin{equation} | ||

1057 | q_k p_{k-2} - p_k q_{k-2} | ||

1058 | = a_k (q_{k-1} p_{k-2} - p_{k-1} q_{k-2}) = (-1)^{k-1} a_k , | ||

1059 | \end{equation} | ||

1060 | which completes the proof. | ||

1061 | \end{vworktheoremproof} | ||

1062 | \vworktheoremfooter{} | ||

1063 | |||

1064 | The results in Theorems \ref{thm:ccfr0:scnv0:crossproductminusone} | ||

1065 | and \ref{thm:ccfr0:scnv0:crossproductminusonebacktwo} allow us | ||

1066 | to establish the relative ordering of convergents. | ||

1067 | Theorems \ref{thm:ccfr0:scnv0:crossproductminusone} and | ||

1068 | \ref{thm:ccfr0:scnv0:crossproductminusonebacktwo} demonstrate that | ||

1069 | even-ordered convergents form an increasing sequence and that odd-ordered | ||

1070 | convergents form a decreasing sequence, and that every odd-ordered convergent | ||

1071 | is greater than every even-ordered convergent. | ||

1072 | |||

1073 | \begin{vworktheoremstatement} | ||

1074 | \label{thm:ccfr0:scnv0:irreducibility} | ||

1075 | For all $k \geq 0$, $s_k = p_k/q_k$ is | ||

1076 | irreducible. | ||

1077 | \end{vworktheoremstatement} | ||

1078 | \begin{vworktheoremproof} | ||

1079 | This proof comes immediately from the form | ||

1080 | of (\ref{eq:ccfr0:scnv0:thm:crossproductminusone:00}). | ||

1081 | Without coprimality of $p_k$ and $q_k$, the difference | ||

1082 | of $\pm 1$ is impossible (see | ||

1083 | \cprizeroxrefcomma{}Lemma \ref{lem:cpri0:ppn0:000p}). | ||

1084 | \end{vworktheoremproof} | ||

1085 | %\vworktheoremfooter{} | ||

1086 | |||

1087 | \begin{vworkexamplestatement} | ||

1088 | \label{ex:ccfr0:scrn0:abreconstruction:01} | ||

1089 | Find an irreducible rational number $a/b$ corresponding to the | ||

1090 | continued fraction $[2;3,4,2]$. | ||

1091 | \end{vworkexamplestatement} | ||

1092 | \begin{vworkexampleparsection}{Solution} | ||

1093 | Application of Theorem \ref{thm:ccfr0:scnv0:canonicalconvergentconstruction} | ||

1094 | yields the following convergents. The final convergent $s_3$ is the | ||

1095 | value of the continued fraction $[2;3,4,2]$ and Theorem | ||

1096 | \ref{thm:ccfr0:scnv0:irreducibility} assures us that each convergent is | ||

1097 | irreducible. | ||

1098 | |||

1099 | \begin{equation} | ||

1100 | \label{eq:ccfr0:scrn0:02a} | ||

1101 | p_{-1} = 1, \; q_{-1} = 0 | ||

1102 | \end{equation} | ||

1103 | |||

1104 | \begin{equation} | ||

1105 | \label{eq:ccfr0:scrn0:02b} | ||

1106 | s_0 = \frac{p_0}{q_0} = \frac{a_0}{1} = \frac{2}{1} | ||

1107 | \end{equation} | ||

1108 | |||

1109 | \begin{equation} | ||

1110 | \label{eq:ccfr0:scrn0:02c} | ||

1111 | s_1 = \frac{p_1}{q_1} = \frac{a_1 p_0 + p_{-1}}{a_1 q_0 + q_{-1}} | ||

1112 | = \frac{(3)(2) + (1)}{(3)(1)+(0)} | ||

1113 | = \frac{7}{3} | ||

1114 | \end{equation} | ||

1115 | |||

1116 | \begin{equation} | ||

1117 | \label{eq:ccfr0:scrn0:02d} | ||

1118 | s_2 = \frac{p_2}{q_2} = \frac{a_2 p_1 + p_{0}}{a_2 q_1 + q_{0}} | ||

1119 | = \frac{(4)(7) + (2)}{(4)(3)+(1)} | ||

1120 | = \frac{30}{13} | ||

1121 | \end{equation} | ||

1122 | |||

1123 | \begin{equation} | ||

1124 | \label{eq:ccfr0:scrn0:02e} | ||

1125 | s_3 = \frac{p_3}{q_3} = \frac{a_3 p_2 + p_{1}}{a_3 q_2 + q_{1}} | ||

1126 | = \frac{(2)(30) + (7)}{(2)(13)+(3)} | ||

1127 | = \frac{67}{29} | ||

1128 | \end{equation} | ||

1129 | |||

1130 | Note that this result coincides with | ||

1131 | Example \ref{ex:ccfr0:scrn0:01}. | ||

1132 | \end{vworkexampleparsection} | ||

1133 | \vworkexamplefooter{} | ||

1134 | |||

1135 | We've shown in Algorithm \ref{alg:ccfr0:scrn0:akgenalg} | ||

1136 | that any rational number can be expressed as a continued fraction, and | ||

1137 | with Theorem \ref{thm:ccfr0:scnv0:canonicalconvergentconstruction} | ||

1138 | that any finite continued fraction can be converted to a rational | ||

1139 | number. Although we don't say more until Section \ref{ccfr0:scin0}, | ||

1140 | it follows directly that any irrational number results in | ||

1141 | an \emph{infinite} (or non-terminating) continued fraction, and that | ||

1142 | any infinite continued fraction represents an irrational number. | ||

1143 | In the theorems that follow, we don't treat infinite continued | ||

1144 | fractions with mathematical rigor, because our emphasis is on | ||

1145 | specific applications of continued fractions. | ||

1146 | |||

1147 | \begin{vworktheoremstatement} | ||

1148 | \label{thm:ccfr0:scnv0:evenslessthanoddsgreaterthan} | ||

1149 | For a finite continued fraction representation of | ||

1150 | the [rational] number $\alpha$, every even-ordered convergent | ||

1151 | is less than $\alpha$ and every odd-ordered convergent is | ||

1152 | greater than $\alpha$, with the exception of the final convergent | ||

1153 | $s_n$, which is equal to $\alpha$. | ||

1154 | For an infinite continued fraction corresponding to the | ||

1155 | [irrational] real | ||

1156 | number $\alpha$, every even-ordered convergent is less than | ||

1157 | $\alpha$, and every odd-ordered convergent is greater than | ||

1158 | $\alpha$. | ||

1159 | \end{vworktheoremstatement} | ||

1160 | \begin{vworktheoremparsection}{Proof (Informal)} | ||

1161 | In the case of a finite continued fraction, the proof is obvious | ||

1162 | and immediate. Since $s_n$, the final convergent, is equal | ||

1163 | to the rational number $\alpha$, Theorems \ref{thm:ccfr0:scnv0:crossproductminusone} | ||

1164 | and \ref{thm:ccfr0:scnv0:crossproductminusonebacktwo} demonstrate this | ||

1165 | unequivocally. | ||

1166 | |||

1167 | In the case of an infinite continued fraction, | ||

1168 | note the form of the proof of Theorem | ||

1169 | \ref{thm:ccfr0:scnv0:canonicalconvergentconstruction}, | ||

1170 | where the substitution of $a_k := a_k + 1/a_{k+1}$ | ||

1171 | is made. It can be demonstrated that for any even-ordered | ||

1172 | convergent $s_k$, additional partial quotients (except | ||

1173 | $a_{k+1} = a_n = 1$, which isn't allowed in general or even | ||

1174 | possible with an infinite continued fraction) can only | ||

1175 | increase the value. It can similarly be demonstrated that | ||

1176 | additional partial quotients can only decrease the value | ||

1177 | of an odd-ordered convergent. Because the continued fraction | ||

1178 | is infinite, any particular even-ordered convergent will be | ||

1179 | increased if more partial quotients are allowed, and any particular | ||

1180 | odd-ordered convergent will be decreased in value if more | ||

1181 | partial quotients are allowed. Thus, we can conclude that | ||

1182 | all even-ordered convergents are less than the value of | ||

1183 | $\alpha$, and all odd-ordered convergents are greater | ||

1184 | than the value of $\alpha$.\footnote{To make this proof more | ||

1185 | formal would require the discussion of \emph{remainders}, | ||

1186 | which wouldn't contribute to the applications discussed in this | ||

1187 | work.} | ||

1188 | \end{vworktheoremparsection} | ||

1189 | %\vworktheoremfooter{} | ||

1190 | |||

1191 | \begin{vworktheoremstatement} | ||

1192 | \label{thm:ccfr0:scnv0:minimumrateofconvergentdenominatorincrease} | ||

1193 | For $k \geq 2$, | ||

1194 | |||

1195 | \begin{equation} | ||

1196 | q_k \geq 2^{\frac{k-1}{2}} . | ||

1197 | \end{equation} | ||

1198 | \end{vworktheoremstatement} | ||

1199 | \begin{vworktheoremproof}\hspace{-0.4em}\footnote{From | ||

1200 | \cite{bibref:b:KhinchinClassic}, Theorem 12, p. 13.} | ||

1201 | For $k \geq 2$, | ||

1202 | |||

1203 | \begin{equation} | ||

1204 | q_k = a_k q_{k-1} + q_{k-2} \geq q_{k-1} + q_{k-2} \geq 2 q_{k-2} . | ||

1205 | \end{equation} | ||

1206 | |||

1207 | Successive application of this inequality yields | ||

1208 | |||

1209 | \begin{equation} | ||

1210 | q_{2k} \geq 2^k q_0 = 2^k, \; q_{2k+1} \geq 2^k q_1 \geq 2^k , | ||

1211 | \end{equation} | ||

1212 | |||

1213 | which proves the theorem. Thus, the denominators of convergents | ||

1214 | increase at least as rapidly as the terms of a geometric | ||

1215 | progression. | ||

1216 | \end{vworktheoremproof} | ||

1217 | \begin{vworktheoremparsection}{Remarks} | ||

1218 | (1) This minimum geometric rate of increase of denominators of convergents is how | ||

1219 | we make the claim that Algorithms | ||

1220 | \ref{alg:ccfr0:scba0:cfenclosingneighborsfn} and | ||

1221 | \ref{alg:ccfr0:scba0:cffareyneighborfn} are $O(log \; N)$ and | ||

1222 | that Algorithms | ||

1223 | \ref{alg:ccfr0:scba0:cfenclosingneighborsfab} | ||

1224 | and \ref{alg:ccfr0:scba0:cffareyneighborfab} are | ||

1225 | $O(log \; max(h_{MAX}, k_{MAX}))$. | ||

1226 | (2) This theorem supplies the \emph{minimum} rate of increase, | ||

1227 | but the demonominators of convergents can increase much faster. To achieve | ||

1228 | the minimum rate of increase, every $a_k$ must be 1, which occurs | ||

1229 | only with the continued fraction representation of | ||

1230 | $\sqrt{5}/2 + 1/2$ (the famous \index{golden ratio}golden ratio). | ||

1231 | (See also Exercise \ref{exe:cfr0:sexe0:c01}.) | ||

1232 | \end{vworktheoremparsection} | ||

1233 | \vworktheoremfooter{} | ||

1234 | |||

1235 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

1236 | |||

1237 | Since Theorem \ref{thm:ccfr0:scnv0:canonicalconvergentconstruction} | ||

1238 | provides a concrete | ||

1239 | procedure for going from a continued fraction $[a_0; a_1, \ldots{} , a_n]$ | ||

1240 | to a rational number $a/b$ that, when Algorithm \ref{alg:ccfr0:scrn0:akgenalg} | ||

1241 | is applied, will again result in $[a_0; a_1, \ldots{} , a_n]$, we have | ||

1242 | successfully demonstrated that every continued fraction | ||

1243 | $[a_0; a_1, \ldots{} , a_n]$ corresponds to [at least one] | ||

1244 | rational number $a/b$. | ||

1245 | |||

1246 | The next natural questions to ask are questions of representation | ||

1247 | uniqueness and the nature of the mapping between the set of rational numbers | ||

1248 | and the set of continued fractions. For example, will 32/100 and 64/200 have | ||

1249 | the same continued fraction representation $[a_0; a_1, \ldots{} , a_n]$? | ||

1250 | Do two different continued fractions ever correspond | ||

1251 | to the same rational number? We answer these questions now. | ||

1252 | |||

1253 | Algorithm \ref{alg:ccfr0:scrn0:akgenalg} will produce the | ||

1254 | same $[a_0; a_1, \ldots{} , a_n]$ for any $ia/ib$, i.e. all rational numbers | ||

1255 | which are equivalent in value will generate the same continued fraction | ||

1256 | representation (see Lemma \ref{lem:ccfr0:scrn0:aoverbneednotbeirreducible}). | ||

1257 | |||

1258 | It was hinted in the introduction (Section | ||

1259 | \ref{ccfr0:sint0}, Footnote \ref{footnote:ccfr0:sint0:00}) | ||

1260 | that, except in the case of representing an integer, it is | ||

1261 | not allowed for the final partial quotient $a_n$ to be 1. | ||

1262 | We now explain the reasons why this must be disallowed. First, | ||

1263 | if $a_n = 1$, then $a_{n-1}$ can be increased by 1 and | ||

1264 | the continued fraction can be reduced in order | ||

1265 | by 1 and while still preserving its value. For example, it | ||

1266 | can easily be verified that $[1;2,3,3,1]$ and $[1;2,3,4]$ | ||

1267 | represent the same number. However, this observation alone | ||

1268 | is not enough to recommend a canonical form---this observation | ||

1269 | does not suggest that $[1;2,3,4]$ should be preferred | ||

1270 | over $[1;2,3,3,1]$. However, what \emph{can} be noted is that | ||

1271 | that a continued fraction representation with $a_n=1$, $n>0$ | ||

1272 | cannot be attained using Algorithm \ref{alg:ccfr0:scrn0:akgenalg} or | ||

1273 | (\ref{eq:ccfr0:scrn0:00a}) through (\ref{eq:ccfr0:scrn0:00e}), | ||

1274 | because a form with $a_n=1$, $n>0$ violates the assumption that | ||

1275 | successive remainders are ever-decreasing (see Eq. | ||

1276 | \ref{eq:lem:ccfr0:scrn0:alwaysterminates}). The property that | ||

1277 | remainders are ever-decreasing is a necessary condition in | ||

1278 | proofs of some important properties, and so requiring | ||

1279 | that $a_n \neq{} 1$, $n>0$ | ||

1280 | is the most natural convention for a canonical form. | ||

1281 | |||

1282 | \begin{vworklemmastatement} | ||

1283 | \label{lem:ccfr0:scrn0:aoverbneednotbeirreducible} | ||

1284 | Algorithm \ref{alg:ccfr0:scrn0:akgenalg} will | ||

1285 | produce the same result | ||

1286 | $[a_0; a_1, \ldots{} , a_n]$ for any | ||

1287 | $ia/ib$, i.e. $a/b$ need not be reduced before the algorithm | ||

1288 | is applied. | ||

1289 | \end{vworklemmastatement} | ||

1290 | \begin{vworklemmaproof} | ||

1291 | Assume that $a/b$ is irreducible, and that $ia/ib$, | ||

1292 | $i \in \{ 2, 3, \ldots \}$ is used as input to | ||

1293 | the algorithm. By definition, any rational number | ||

1294 | with the same value as $a/b$ is of the form $ia/ib$, | ||

1295 | $i \in \vworkintsetpos$. | ||

1296 | Note that (\ref{eq:ccfr0:scrn0:00a}) through | ||

1297 | (\ref{eq:ccfr0:scrn0:00e}) ``scale up'', while still producing | ||

1298 | the same partial quotients $[a_0; a_1, \ldots{} , a_n]$. | ||

1299 | Specifically: | ||

1300 | |||

1301 | \begin{equation} | ||

1302 | \label{eq:ccfr0:scrn0:10a} | ||

1303 | \frac{ia}{ib} | ||

1304 | = | ||

1305 | a_0 + \frac{ir_0}{ib} | ||

1306 | = | ||

1307 | a_0 + \frac{1}{\frac{ib}{ir_0}} | ||

1308 | \end{equation} | ||

1309 | |||

1310 | \begin{equation} | ||

1311 | \label{eq:ccfr0:scrn0:10b} | ||

1312 | \frac{ib}{ir_0} | ||

1313 | = | ||

1314 | a_1 + \frac{ir_1}{ir_0} | ||

1315 | \end{equation} | ||

1316 | |||

1317 | \begin{equation} | ||

1318 | \label{eq:ccfr0:scrn0:10c} | ||

1319 | \frac{ir_0}{ir_1} | ||

1320 | = | ||

1321 | a_2 + \frac{ir_2}{ir_1} | ||

1322 | \end{equation} | ||

1323 | |||

1324 | \noindent{}Finally, nearing the termination of | ||

1325 | Algorithm \ref{alg:ccfr0:scrn0:akgenalg}: | ||

1326 | |||

1327 | \begin{equation} | ||

1328 | \label{eq:ccfr0:scrn0:10d} | ||

1329 | \frac{ir_{n-3}}{ir_{n-2}} | ||

1330 | = | ||

1331 | a_{n-1} + \frac{ir_{n-1}}{ir_{n-2}} | ||

1332 | \end{equation} | ||

1333 | |||

1334 | \begin{equation} | ||

1335 | \label{eq:ccfr0:scrn0:10e} | ||

1336 | \frac{ir_{n-2}}{ir_{n-1}} | ||

1337 | = | ||

1338 | a_n | ||

1339 | \end{equation} | ||

1340 | |||

1341 | Thus, it is easy to show that Algorithm \ref{alg:ccfr0:scrn0:akgenalg} | ||

1342 | will produce the same continued fraction representation regardless of whether | ||

1343 | the input to the algorithm is reduced. It is also easy to show that the | ||

1344 | last non-zero remainder as the algorithm is applied ($r_{n-1}$, in | ||

1345 | Eqns. \ref{eq:ccfr0:scrn0:10d} and \ref{eq:ccfr0:scrn0:10e}) | ||

1346 | is the greatest common divisor of $ia$ and $ib$ (this is done | ||

1347 | in the proof of Algorithm \ref{alg:ccfr0:sega0:euclidsgcdalgorithm}). | ||

1348 | \end{vworklemmaproof} | ||

1349 | %\vworklemmafooter{} | ||

1350 | |||

1351 | \begin{vworklemmastatement} | ||

1352 | \label{lem:ccfr0:scrn0:cfrepresentationisunique} | ||

1353 | So long as $a_n \neq 1$, $n>0$, a rational number $a/b$ has only | ||

1354 | one [unique] continued fraction representation | ||

1355 | $[a_0; a_1, \ldots{} , a_n]$. | ||

1356 | \end{vworklemmastatement} | ||

1357 | \begin{vworklemmaproof} | ||

1358 | Assume that two different continued fractions, | ||

1359 | $[a_0; a_1, \ldots{} , a_m]$ and | ||

1360 | $[\overline{a_0}; \overline{a_1}, \ldots{} , \overline{a_n}]$, | ||

1361 | correspond to the same rational number $a/b$. By | ||

1362 | \emph{different}, we mean either that $m=n$ but | ||

1363 | $\exists i, a_i \neq \overline{a_i}$, or that $m \neq n$. | ||

1364 | |||

1365 | Note that Theorem \ref{thm:ccfr0:scnv0:canonicalconvergentconstruction} | ||

1366 | will map from any continued fraction to an irreducible rational | ||

1367 | number $a/b$. Assume we apply | ||

1368 | Theorem \ref{thm:ccfr0:scnv0:canonicalconvergentconstruction} to | ||

1369 | $[a_0; a_1, \ldots{} , a_m]$ to produce $a/b$, and | ||

1370 | to $[\overline{a_0}; \overline{a_1}, \ldots{} , \overline{a_n}]$ | ||

1371 | to produce $\overline{a}/\overline{b}$. Because two irreducible | ||

1372 | rational numbers are equal iff their components are | ||

1373 | equal, | ||

1374 | $[(a/b) = (\overline{a}/\overline{b})] \vworkhimp{} % | ||

1375 | [(a = \overline{a}) \wedge (b = \overline{b})]$. Because | ||

1376 | $a/b = \overline{a}/\overline{b}$, we denote both of these | ||

1377 | numbers simply as $a/b$. | ||

1378 | |||

1379 | By (\ref{eq:ccfr0:scrn0:11a}), | ||

1380 | $a = a_0 b + r_0 = \overline{a_0} b + \overline{r_0}$, | ||

1381 | $0 < r_0, \overline{r_0} < b$. Because | ||

1382 | $r_0, \overline{r_0} < b$, there is only one combination | ||

1383 | of $a_0$ and $r_0$ or of $\overline{a_0}$ and | ||

1384 | $\overline{r_0}$ that can result in $a$. Thus, we can conclude | ||

1385 | that $a_0 = \overline{a_0}$ and | ||

1386 | $r_0 = \overline{r_0}$. This type of reasoning, can be | ||

1387 | carried ``downward'' inductively, each time fixing | ||

1388 | $a_{i}$ and $r_{i}$. Finally, we must conclude | ||

1389 | that $(a/b = \overline{a}/\overline{b}) \vworkhimp % | ||

1390 | [a_0; a_1, \ldots{} , a_m] = % | ||

1391 | [\overline{a_0}; \overline{a_1}, \ldots{} , \overline{a_n}]$ | ||

1392 | and that $m=n$. | ||

1393 | \end{vworklemmaproof} | ||

1394 | \begin{vworklemmaparsection}{Remarks} | ||

1395 | The case of $a_n=1$, $n>0$ deserves further discussion. | ||

1396 | Theorem \ref{thm:ccfr0:scnv0:canonicalconvergentconstruction} will produce | ||

1397 | an irreducible rational number even if | ||

1398 | $a_n = 1$, $n>0$. How is it that uniqueness of representation can | ||

1399 | be claimed when clearly, for example, $[2;3,4,2]$ and $[2;3,4,1,1]$ | ||

1400 | are the same number? The answer is that $a_n = 1$, $n>0$ requires | ||

1401 | that $r_{n-2}=r_{n-1}=1$, which violates the ``uniqueness'' assumption | ||

1402 | used in fixing $a_i$ and $r_i$ in the proof above---specifically note | ||

1403 | that the condition $0<r_{n-1}<r_{n-2}$ in (\ref{eq:ccfr0:scrn0:11d}) | ||

1404 | is violated. If one is allowed to violate the required | ||

1405 | ever-decreasing remainders, then $a_i$ and $r_i$ cannot | ||

1406 | be uniquely fixed at each step of the proof, above. | ||

1407 | \end{vworklemmaparsection} | ||

1408 | \vworklemmafooter{} | ||

1409 | |||

1410 | \index{continued fraction!intermediate fraction} | ||

1411 | An \emph{intermediate fraction} is a fraction represented | ||

1412 | by the continued fraction representation of a $k$-th order | ||

1413 | convergent with the final partial quotient $a_k$ reduced | ||

1414 | (this can naturally only be done when $a_k > 1$). As Khinchin | ||

1415 | points out (\cite{bibref:b:KhinchinClassic}, p. 14): | ||

1416 | ``\emph{In arithmetic applications, these intermediate | ||

1417 | fractions play an important role (though not as important | ||

1418 | a role as the convergents)}''. | ||

1419 | |||

1420 | The intermediate fractions (of a $k$-th order convergent) | ||

1421 | form a monotonically increasing or decreasing sequence of | ||

1422 | fractions (\cite{bibref:b:KhinchinClassic}, p. 13): | ||

1423 | |||

1424 | \begin{equation} | ||

1425 | \label{eq:ccfr0:scrn0:intermediatefrac01} | ||

1426 | \frac{p_{k-2}}{q_{k-2}}, | ||

1427 | \frac{p_{k-2} + p_{k-1}}{q_{k-2} + q_{k-1}}, | ||

1428 | \frac{p_{k-2} + 2 p_{k-1}}{q_{k-2} + 2 q_{k-1}}, | ||

1429 | \ldots{} , | ||

1430 | \frac{p_{k-2} + a_k p_{k-1}}{q_{k-2} + a_k q_{k-1}} | ||

1431 | = | ||

1432 | \frac{p_k}{q_k} . | ||

1433 | \end{equation} | ||

1434 | |||

1435 | Note in (\ref{eq:ccfr0:scrn0:intermediatefrac01}) that the | ||

1436 | first and last fractions are not intermediate fractions (rather, they are | ||

1437 | convergents). | ||

1438 | |||

1439 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

1440 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

1441 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

1442 | \section{Euclid's GCD Algorithm} | ||

1443 | %Section tag: EGA0 | ||

1444 | \index{Euclid!GCD algorithm} | ||

1445 | |||

1446 | The apparatus of continued fractions is closely related to Euclid's GCD | ||

1447 | algorithm (in fact, historically, Euclid's GCD algorithm is considered | ||

1448 | a precursor of continued fractions). It was noted in | ||

1449 | Lemma \ref{lem:ccfr0:scrn0:aoverbneednotbeirreducible} that the last non-zero | ||

1450 | remainder when Algorithm \ref{alg:ccfr0:scrn0:akgenalg} is applied | ||

1451 | is the greatest common divisor of $a$ and $b$. In this section, we | ||

1452 | present Euclid's algorithm, prove it, and show it similarity to | ||

1453 | Algorithm \ref{alg:ccfr0:scrn0:akgenalg}. | ||

1454 | |||

1455 | Knuth (\cite{bibref:b:knuthclassic2ndedvol2}, p. 335) presents some background | ||

1456 | information about Euclid's GCD algorithm: | ||

1457 | |||

1458 | \begin{quote} | ||

1459 | Euclid's algorithm is found in Book 7, Propositions 1 and 2 of his | ||

1460 | \emph{Elements} (c. 300 B.C.), but it probably wasn't his own | ||

1461 | invention. Some scholars believe that the method was known up to | ||

1462 | 200 years earlier, at least in its subtractive form, and it | ||

1463 | was almost certainly known to Eudoxus (c. 375 B.C.); see | ||

1464 | K. von Fritz, \emph{Ann. Math.} (2) \textbf{46} 1945, 242-264. | ||

1465 | Aristotle (c. 330 B.C.) hinted at it in his \emph{Topics}, 158b, | ||

1466 | 29-35. However, very little hard evidence about such early history | ||

1467 | has survived [see. W. R. Knorr, \emph{The Evolution of the Euclidian | ||

1468 | Elements} (Dordrecht: 1975)]. | ||

1469 | |||

1470 | We might call Euclid's method the granddaddy of all algorithms, because | ||

1471 | it is the oldest nontrivial algorithm that has survived to the present day. | ||

1472 | (The chief rival for this honor is perhaps the ancient Egyptian method | ||

1473 | for multiplication, which was based on doubling and adding, and which forms | ||

1474 | the basis for efficient calculation of \emph{n}th powers as explained | ||

1475 | in section 4.6.3. \ldots{}) | ||

1476 | \end{quote} | ||

1477 | |||

1478 | \begin{vworkalgorithmstatementpar} | ||

1479 | {Euclid's GCD Algorithm For Greatest Common Divisor Of Positive | ||

1480 | Integers \mbox{\boldmath $a$} | ||

1481 | And \mbox{\boldmath $b$}}\hspace{-0.4em}\footnote{Knuth | ||

1482 | (\cite{bibref:b:knuthclassic2ndedvol2}, pp. 336-337) distinguishes between the \emph{original} | ||

1483 | Euclidian algorithm and the \emph{modern} Euclidian algorithm. The algorithm presented here | ||

1484 | is more closely patterned after the \emph{modern} Euclidian algorithm.} | ||

1485 | \label{alg:ccfr0:sega0:euclidsgcdalgorithm} | ||

1486 | \begin{alglvl0} | ||

1487 | \item If ($a < b$), swap $a$ and $b$.\footnote{This step isn't strictly necessary, but is usually done | ||

1488 | to save one iteration.} | ||

1489 | \item Repeat | ||

1490 | \begin{alglvl1} | ||

1491 | \item $r := a \; mod \; b$. | ||

1492 | \item If ($r = 0$), STOP. | ||

1493 | \item $a := b$. | ||

1494 | \item $b := r$. | ||

1495 | \end{alglvl1} | ||

1496 | \item \textbf{Exit condition:} $b$ will be the g.c.d. of $a$ and $b$. | ||

1497 | \end{alglvl0} | ||

1498 | \end{vworkalgorithmstatementpar} | ||

1499 | \begin{vworkalgorithmproof} | ||

1500 | Olds (\cite{bibref:b:OldsClassic}, pp. 16-17) shows the | ||

1501 | relationship between Algorithm | ||

1502 | \ref{alg:ccfr0:scrn0:akgenalg} and Euclid's algorithm, and presents | ||

1503 | a proof, which is reproduced nearly verbatim here. | ||

1504 | |||

1505 | First, note that $d$ is the GCD of $a$ and $b$ iff: | ||

1506 | |||

1507 | \begin{itemize} | ||

1508 | \item (Necessary Condition I) $d$ divides both $a$ and $b$, and | ||

1509 | \item (Necessary Condition II) any common divisor $c$ of $a$ and $b$ divides $d$. | ||

1510 | \end{itemize} | ||

1511 | |||

1512 | Essentially, we will prove that the final non-zero remainder | ||

1513 | when the algorithm is applied meets the two criteria above, | ||

1514 | and hence must be the GCD of $a$ and $b$. | ||

1515 | |||

1516 | Note that (\ref{eq:ccfr0:scrn0:00a}) through | ||

1517 | (\ref{eq:ccfr0:scrn0:00e}) can be rewritten as | ||

1518 | (\ref{eq:ccfr0:scrn0:11a}) through | ||

1519 | (\ref{eq:ccfr0:scrn0:11e}), which make them | ||

1520 | consistent with the form Olds' presents. | ||

1521 | |||

1522 | \begin{eqnarray} | ||

1523 | \label{eq:ccfr0:scrn0:11a} | ||

1524 | a = a_0 b + r_0, && 0 < r_0 < b \\ | ||

1525 | \label{eq:ccfr0:scrn0:11b} | ||

1526 | b = a_1 r_0 + r_1, && 0 < r_1 < r_0 \\ | ||

1527 | \label{eq:ccfr0:scrn0:11c} | ||

1528 | r_0 = a_2 r_1 + r_2, && 0 < r_2 < r_1 \\ | ||

1529 | \ldots{}\hspace{-1.67em}&& \nonumber \\ | ||

1530 | \label{eq:ccfr0:scrn0:11d} | ||

1531 | r_{n-3} = a_{n-1} r_{n-2} + r_{n-1}, && 0 < r_{n-1} < r_{n-2} \\ | ||

1532 | \label{eq:ccfr0:scrn0:11e} | ||

1533 | r_{n-2} = a_n r_{n-1} + 0, && 0 = r_n | ||

1534 | \end{eqnarray} | ||

1535 | |||

1536 | First, we will show that \emph{Necessary Condition I}, above, is met. | ||

1537 | Note from (\ref{eq:ccfr0:scrn0:11e}) that $r_{n-1} \vworkdivides r_{n-2}$, | ||

1538 | since $r_{n-2}$ is an integer multiple of $r_{n-1}$. Note from | ||

1539 | (\ref{eq:ccfr0:scrn0:11d}) that $r_{n-1} \vworkdivides r_{n-3}$, since | ||

1540 | $r_{n-3}$ is also an integer multiple of $r_{n-1}$. This logic can | ||

1541 | be carried ``upward'' in the set of equations represented | ||

1542 | by (\ref{eq:ccfr0:scrn0:11a}) through (\ref{eq:ccfr0:scrn0:11e}), | ||

1543 | and we can finally conclude that $r_{n-1} \vworkdivides b$ and | ||

1544 | $r_{n-1} \vworkdivides a$. This proves \emph{Necessary Condition I}. | ||

1545 | |||

1546 | Second, we will show that \emph{Necessary Condition II}, above, is met. | ||

1547 | This time, in (\ref{eq:ccfr0:scrn0:11a}) through (\ref{eq:ccfr0:scrn0:11e}), | ||

1548 | we work top-down rather than bottom-up. Assume that $c$ is a divisor | ||

1549 | of $a$ and a divisor of $b$. Then, from the form of (\ref{eq:ccfr0:scrn0:11a}), | ||

1550 | $c$ divides $r_0$.\footnote{This implication may be counterintuitive | ||

1551 | at first glance. It concerns "reachability" of linear combinations | ||

1552 | of integers with a common divisor. Specifically, if | ||

1553 | $a$ and $b$ have a common divisor $c$, any linear combination | ||

1554 | $ia + jb$, ($i,j \in \vworkintset$), can ``reach'' only multiples of $c$. | ||

1555 | In (\ref{eq:ccfr0:scrn0:11a}), $(1)(a)+(-a_0)(b)=r_0$, thus | ||

1556 | $r_0$ must be a multiple of $c$. An identical argument applies for | ||

1557 | (\ref{eq:ccfr0:scrn0:11a}) through (\ref{eq:ccfr0:scrn0:11e}).} | ||

1558 | Similarly, from the form of (\ref{eq:ccfr0:scrn0:11b}), | ||

1559 | $c$ divides $r_1$. This rationale can be carried ``downward'' to finally | ||

1560 | conclude that $c$ divides $r_{n-1}$. Thus, | ||

1561 | $(c \vworkdivides a) \wedge (c \vworkdivides b) \vworkhimp (c \vworkdivides r_{n-1})$, | ||

1562 | where $r_{n-1}$ is the last non-zero remainder. This proves | ||

1563 | \emph{Necessary Condition II}. | ||

1564 | |||

1565 | Thus, $r_{n-1}$ is the GCD of $a$ and $b$. | ||

1566 | \end{vworkalgorithmproof} | ||

1567 | \begin{vworkalgorithmparsection}{Remarks} | ||

1568 | It is easy to observe that the only difference between | ||

1569 | Algorithm \ref{alg:ccfr0:scrn0:akgenalg} and | ||

1570 | Algorithm \ref{alg:ccfr0:sega0:euclidsgcdalgorithm} is | ||

1571 | that Algorithm \ref{alg:ccfr0:scrn0:akgenalg} records the | ||

1572 | quotient of each division, whereas | ||

1573 | Algorithm \ref{alg:ccfr0:sega0:euclidsgcdalgorithm} | ||

1574 | does not. | ||

1575 | \end{vworkalgorithmparsection} | ||

1576 | %\vworkalgorithmfooter{} | ||

1577 | |||

1578 | \begin{vworkexamplestatement} | ||

1579 | \label{ex:ccfr0:sega0:01} | ||

1580 | Use Euclid's algorithm to find the greatest common divisor | ||

1581 | of 1,736,651 and 26,023. | ||

1582 | \end{vworkexamplestatement} | ||

1583 | \begin{vworkexampleparsection}{Solution} | ||

1584 | \begin{table} | ||

1585 | \caption{Euclid's Algorithm Applied To Find Greatest Common Divisor Of 1,736,651 and 26,023 | ||

1586 | (Example \ref{ex:ccfr0:sega0:01})} | ||

1587 | \label{tbl:ex:ccfr0:sega0:01} | ||

1588 | \begin{center} | ||

1589 | \begin{tabular}{|c|c|c|c|} | ||

1590 | \hline | ||

1591 | \small{Iteration} & \small{$a$} & \small{$b$} & \small{$r : = a \; mod \; b$} \\ | ||

1592 | \hline | ||

1593 | \hline | ||

1594 | \small{1} & \small{1,736,651} & \small{26,023} & \small{19,133} \\ | ||

1595 | \hline | ||

1596 | \small{2} & \small{26,023} & \small{19,133} & \small{6,890} \\ | ||

1597 | \hline | ||

1598 | \small{3} & \small{19,133} & \small{6,890} & \small{5,353} \\ | ||

1599 | \hline | ||

1600 | \small{4} & \small{6,890} & \small{5,353} & \small{1,537} \\ | ||

1601 | \hline | ||

1602 | \small{5} & \small{5,353} & \small{1,537} & \small{742} \\ | ||

1603 | \hline | ||

1604 | \small{6} & \small{1,537} & \small{742} & \small{53} \\ | ||

1605 | \hline | ||

1606 | \small{7} & \small{742} & \small{53} & \small{0} \\ | ||

1607 | \hline | ||

1608 | \end{tabular} | ||

1609 | \end{center} | ||

1610 | \end{table} | ||

1611 | Table \ref{tbl:ex:ccfr0:sega0:01} shows the application of | ||

1612 | Algorithm \ref{alg:ccfr0:sega0:euclidsgcdalgorithm} (Euclid's | ||

1613 | GCD algorithm) to find the greatest common divisor | ||

1614 | of 1,736,651 and 26,023. The last non-zero remainder (and hence | ||

1615 | the greatest common divisor) is 53. | ||

1616 | \end{vworkexampleparsection} | ||

1617 | \begin{vworkexampleparsection}{Remarks} | ||

1618 | The prime factorization of 1,736,651 is $151 \times 53 \times 31 \times 7$, and | ||

1619 | the prime factorization of 26,023 is $491 \times 53$, which is consistent | ||

1620 | with the result in Table \ref{tbl:ex:ccfr0:sega0:01}. | ||

1621 | \end{vworkexampleparsection} | ||

1622 | \vworkexamplefooter{} | ||

1623 | |||

1624 | |||

1625 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

1626 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

1627 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

1628 | \section[CF Representation Of Irrationals] | ||

1629 | {Continued Fraction Representation Of Irrational Numbers} | ||

1630 | %Section tag: CIN0 | ||

1631 | \label{ccfr0:scin0} | ||

1632 | |||

1633 | \index{continued fraction!irrational numbers@of irrational numbers} | ||

1634 | \index{irrational number!continued fraction representation of}Irrational | ||

1635 | numbers (such as $\sqrt{2}$ or $\pi$) necessarily have infinite continued | ||

1636 | fraction representations (i.e. the representations do not terminate). This is clear, since | ||

1637 | Theorem \ref{thm:ccfr0:scnv0:canonicalconvergentconstruction} gives a concrete procedure | ||

1638 | for constructing a rational number from any \emph{finite} continued fraction; | ||

1639 | therefore a continued fraction corresponding to an irrational number | ||

1640 | cannot be finite. | ||

1641 | |||

1642 | The algorithm for determining the partial quotients of an irrational number is | ||

1643 | awkward, because it is a symbolic (rather than a numerical) algorithm. | ||

1644 | We present the algorithm here for perspective and completeness, although it | ||

1645 | is not often useful in practical engineering work. In practical work, an | ||

1646 | ordinary handheld calculator will supply a real number to far more precision | ||

1647 | than necessary, and the displayed real number can be converted to a rational | ||

1648 | number for the application of Algorithm \ref{alg:ccfr0:scrn0:akgenalg}. | ||

1649 | For practical work, it is rarely necessary to apply a Algorithm | ||

1650 | \ref{alg:ccfr0:scin0:symboliccfalgorithm}. | ||

1651 | |||

1652 | The symbolic algorithm for determining the continued fraction partial quotients | ||

1653 | of a real number is a recursive process very similar to the algorithm for | ||

1654 | determining the continued fraction partial quotients of a rational number. | ||

1655 | The essential activity is choosing the largest possible integer $a_i$ in each | ||

1656 | iteration. | ||

1657 | |||

1658 | Algorithm \ref{alg:ccfr0:scin0:symboliccfalgorithm} begins by choosing | ||

1659 | the largest integer $a_0$ not larger than $x$, then expressing $x$ as | ||

1660 | |||

1661 | \begin{equation} | ||

1662 | x = a_0 + \frac{1}{x_1} . | ||

1663 | \end{equation} | ||

1664 | |||

1665 | \noindent{}With $a_0$ chosen, $x_1$ can then be expressed as | ||

1666 | |||

1667 | \begin{equation} | ||

1668 | x_1 = \frac{1}{x - a_0} . | ||

1669 | \end{equation} | ||

1670 | |||

1671 | \noindent{}$x_1$ can then be expressed as | ||

1672 | |||

1673 | \begin{equation} | ||

1674 | x_1 = a_1 + \frac{1}{x_2} , | ||

1675 | \end{equation} | ||

1676 | |||

1677 | \noindent{}and $a_1$, the largest integer not larger than $x_1$, | ||

1678 | can be chosen. | ||

1679 | This process can be continued indefinitely (with an irrational $x$, it won't terminate) | ||

1680 | to determine as many partial quotients as desired. | ||

1681 | |||

1682 | \begin{vworkalgorithmstatementpar} | ||

1683 | {Symbolic Algorithm For Obtaining | ||

1684 | Continued Fraction Representation Of An Irrational Number | ||

1685 | \mbox{\boldmath $x$}} | ||

1686 | \label{alg:ccfr0:scin0:symboliccfalgorithm} | ||

1687 | \begin{alglvl0} | ||

1688 | \item $x_0 := x$ (the real number whose partial quotients are desired). | ||

1689 | \item $k := -1$. | ||

1690 | \item Repeat | ||

1691 | \begin{alglvl1} | ||

1692 | \item $k := k + 1$. | ||

1693 | \item $a_k := \lfloor x_k \rfloor$. | ||

1694 | \item $x_{k+1} := \displaystyle{\frac{1}{x_k - a_k}}$. | ||

1695 | \end{alglvl1} | ||

1696 | \item Until (as many partial quotients as desired are obtained). | ||

1697 | \end{alglvl0} | ||

1698 | \end{vworkalgorithmstatementpar} | ||

1699 | %\vworkalgorithmfooter{} | ||

1700 | |||

1701 | \begin{vworkexamplestatement} | ||

1702 | \label{ex:ccfr0:scin0:symboliccfalgorithmexample} | ||

1703 | Find the first several continued fraction partial quotients of $\sqrt{3}$. | ||

1704 | \end{vworkexamplestatement} | ||

1705 | \begin{vworkexampleparsection}{Solution} | ||

1706 | Applying Algorithm \ref{alg:ccfr0:scin0:symboliccfalgorithm}: | ||

1707 | |||

1708 | \begin{equation} | ||

1709 | x_0 := x = \sqrt{3} | ||

1710 | \end{equation} | ||

1711 | |||

1712 | \begin{equation} | ||

1713 | k := -1 | ||

1714 | \end{equation} | ||

1715 | |||

1716 | \begin{equation} | ||

1717 | k := k+1 = 0 | ||

1718 | \end{equation} | ||

1719 | |||

1720 | \begin{equation} | ||

1721 | a_0 := \lfloor x_0 \rfloor = \lfloor \sqrt{3} \rfloor = 1 | ||

1722 | \end{equation} | ||

1723 | |||

1724 | \begin{equation} | ||

1725 | x_1 := \frac{1}{x_0 - a_0} | ||

1726 | = \frac{1}{\sqrt{3}-1} | ||

1727 | = \frac{\sqrt{3}+1}{2} | ||

1728 | \end{equation} | ||

1729 | |||

1730 | \begin{equation} | ||

1731 | k := k + 1 = 1 | ||

1732 | \end{equation} | ||

1733 | |||

1734 | \begin{equation} | ||

1735 | a_1 := \lfloor x_1 \rfloor = | ||

1736 | \left\lfloor {\frac{\sqrt{3}+1}{2}} \right\rfloor = 1 | ||

1737 | \end{equation} | ||

1738 | |||

1739 | \begin{equation} | ||

1740 | x_2 := \frac{1}{x_1 - 1} | ||

1741 | = \frac{1}{\frac{\sqrt{3}+1}{2}-1} | ||

1742 | = \sqrt{3}+1 | ||

1743 | \end{equation} | ||

1744 | |||

1745 | \begin{equation} | ||

1746 | k := k + 1 = 2 | ||

1747 | \end{equation} | ||

1748 | |||

1749 | \begin{equation} | ||

1750 | a_2 := \lfloor x_2 \rfloor = \lfloor \sqrt{3}+1 \rfloor = 2 | ||

1751 | \end{equation} | ||

1752 | |||

1753 | \begin{equation} | ||

1754 | x_3 := \frac{1}{(\sqrt{3}+1)-2} = \frac{\sqrt{3}+1}{2} | ||

1755 | \end{equation} | ||

1756 | |||

1757 | Note that $x_3 = x_1$, so the algorithm will repeat with | ||

1758 | $a_3=1$, $a_4=2$, $a_5=1$, $a_6=2$, etc. Thus, the continued | ||

1759 | fraction representation of $\sqrt{3}$ is | ||

1760 | $[1;1,2,1,2,1,2, \ldots{}]$ = $[1;\overline{1,2}]$. | ||

1761 | \end{vworkexampleparsection} | ||

1762 | \begin{vworkexampleparsection}{Remarks} | ||

1763 | \index{continued fraction!repeating} | ||

1764 | It can be proved that all continued fractions that repeat or repeat | ||

1765 | from some point onward | ||

1766 | represent real numbers of the form $\frac{P \pm \sqrt{D}}{Q}$, | ||

1767 | where $D \in \vworkintsetpos$ is not the square of an integer. | ||

1768 | It can also be shown | ||

1769 | that all numbers of this form result in continued fractions that | ||

1770 | repeat or repeat from some point onward. (See Olds | ||

1771 | \cite{bibref:b:OldsClassic}, Chapter 4.) It is beyond the scope | ||

1772 | of our interest in continued fractions to develop these properties. | ||

1773 | \end{vworkexampleparsection} | ||

1774 | \vworkexamplefooter{} | ||

1775 | |||

1776 | |||

1777 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

1778 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

1779 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

1780 | \section{Convergents As Best Approximations} | ||

1781 | %Section tag: CBA0 | ||

1782 | |||

1783 | Up until this point, we've presented general properties of continued | ||

1784 | fractions and convergents without regard for practical applications. | ||

1785 | In this section, we present results and algorithms to use the | ||

1786 | apparatus of continued fractions to obtain best rational approximations. | ||

1787 | |||

1788 | Although we don't dwell on other algorithms for locating best | ||

1789 | rational approximations (we present only the single best | ||

1790 | algorithm), it is worth noting that there are many naive algorithms | ||

1791 | for locating best rational approximations. These include: | ||

1792 | |||

1793 | \begin{itemize} | ||

1794 | |||

1795 | \item Exhaustive search of the integer lattice | ||

1796 | [$O(h_{MAX} k_{MAX})$]. | ||

1797 | |||

1798 | \item Building the Farey series starting at an | ||

1799 | integer [$O(max(h_{MAX}, k_{MAX})^2)$] | ||

1800 | (see Algorithm \cfryzeroxrefhyphen{}\ref{alg:cfry0:sgfs0:02}). | ||

1801 | |||

1802 | \item Building the Farey series starting at a rational number with | ||

1803 | a large prime denominator [$O(max(h_{MAX}, k_{MAX}))$]. | ||

1804 | |||

1805 | \item Building the Stern-Brocot tree (see Section \ref{ccfr0:ssbt0}) | ||

1806 | [$O(max(h_{MAX}, k_{MAX}))$]. | ||

1807 | |||

1808 | \end{itemize} | ||

1809 | |||

1810 | Although we don't justify it formally, | ||

1811 | the continued fraction algorithms presented here are | ||

1812 | $O(log \; max(h_{MAX}, k_{MAX}))$.\footnote{Well, | ||

1813 | not exactly. In the classical computer science | ||

1814 | sense (speaking only in terms of number of operations), | ||

1815 | the algorithms are $O(log \; max(h_{MAX}, k_{MAX}))$. However, | ||

1816 | if $h_{MAX}$ and $k_{MAX}$ are increased beyond the sizes | ||

1817 | of integers that a computer can inherently accomodate, one must | ||

1818 | use long integer calculation software, which requires more time for | ||

1819 | each integer operation than is required for machine native | ||

1820 | integer sizes. As $h_{MAX}$ and $k_{MAX}$ are increased far | ||

1821 | beyond integer sizes accomodated inherently by the computer, | ||

1822 | the relationship surely is not $O(log \; max(h_{MAX}, k_{MAX}))$.} | ||

1823 | The basis on which we | ||

1824 | make that assertion is the geometric rate of | ||

1825 | increase of convergents (see Theorem | ||

1826 | \ref{thm:ccfr0:scnv0:minimumrateofconvergentdenominatorincrease}), | ||

1827 | which means that the number of steps required is tied to the | ||

1828 | logarithm of the maximum denominator involved, as it is | ||

1829 | necessary to obtain partial quotients and convergents only until | ||

1830 | $q_k \geq max(h_{MAX},k_{MAX})$. | ||

1831 | |||

1832 | \begin{vworktheoremstatement} | ||

1833 | \label{thm:ccfr0:scba0:convergentcloseness} | ||

1834 | In the case of an infinite continued fraction for $k \geq 0$ or in the | ||

1835 | case of a finite continued fraction for $0 \leq k < n-1$, a convergent | ||

1836 | $s_k = p_k/q_k$ to a [rational or irrational] number | ||

1837 | $\alpha \in \vworkrealsetnonneg$ satisfies | ||

1838 | |||

1839 | \begin{equation} | ||

1840 | \left| {\alpha - \frac{p_k}{q_k}} \right| | ||

1841 | < | ||

1842 | \frac{1}{q_k q_{k+1}} . | ||

1843 | \end{equation} | ||

1844 | |||

1845 | In the case of a finite continued fraction with $k = n-1$, | ||

1846 | |||

1847 | \begin{equation} | ||

1848 | \left| {\alpha - \frac{p_k}{q_k}} \right| | ||

1849 | = | ||

1850 | \frac{1}{q_k q_{k+1}} . | ||

1851 | \end{equation} | ||

1852 | \end{vworktheoremstatement} | ||

1853 | \begin{vworktheoremproof} | ||

1854 | The proof comes directly from Theorem | ||

1855 | \ref{thm:ccfr0:scnv0:crossproductminusone} (Corollary I) | ||

1856 | and Theorem | ||

1857 | \ref{thm:ccfr0:scnv0:evenslessthanoddsgreaterthan}. | ||

1858 | \end{vworktheoremproof} | ||

1859 | \begin{vworktheoremparsection}{Remarks} | ||

1860 | Khinchin describes this result (\cite{bibref:b:KhinchinClassic}, p. 9) | ||

1861 | as playing a basic role in the arithmetic | ||

1862 | applications of continued fractions. In fact, this theorem is used | ||

1863 | in the proof of Theorem | ||

1864 | \ref{thm:ccfr0:scba0:cfenclosingneighbors}. | ||

1865 | \end{vworktheoremparsection} | ||

1866 | \vworktheoremfooter{} | ||

1867 | |||

1868 | |||

1869 | We now present and prove the fundamental theorem of this chapter, which gives an | ||

1870 | $O(log \; N)$ algorithm for finding the enclosing neighbors in $F_N$ to an arbitrary | ||

1871 | rational number $a/b$.\footnote{\label{footnote:ccfr0:scba0:rationalitynotrequired}Theorem | ||

1872 | \ref{thm:ccfr0:scba0:cfenclosingneighbors} | ||

1873 | applies to irrational numbers as well, | ||

1874 | so long as one can obtain enough partial quotients, but we don't highlight this | ||

1875 | fact because it is rare in engineering applications that one uses symbolic methods | ||

1876 | to obtain best rational approximations. | ||

1877 | As emphasized by (\ref{eq:ccfr0:spar0:01}), (\ref{eq:ccfr0:spar0:02}), and | ||

1878 | (\ref{eq:ccfr0:spar0:03}), | ||

1879 | the process of obtaining partial quotients is essentially a process of determining in which | ||

1880 | partition a number lies. All numbers in the same partition---rational or | ||

1881 | irrational---have the same Farey neighbors in all Farey series up to a certain order. | ||

1882 | If the partial quotients of | ||

1883 | an irrational number can be obtained up through $a_k$ s.t. $s_k = p_k/q_k$ is the | ||

1884 | highest-order convergent with $q_k \leq N$, then this theorem can be applied. | ||

1885 | Knowledge of all $a_0, \ldots{} , a_k$ is equivalent | ||

1886 | to the knowledge that the number is in a partition where all numbers in that partition have | ||

1887 | the same Farey neighbors in all Farey series up through at least order $q_k$.} | ||

1888 | |||

1889 | |||

1890 | \begin{vworktheoremstatementpar}{Enclosing Neighbors Of \mbox{\boldmath $x \notin F_N$} | ||

1891 | In \mbox{\boldmath $F_N$}} | ||

1892 | \label{thm:ccfr0:scba0:cfenclosingneighbors} | ||

1893 | For a non-negative rational | ||

1894 | number $a/b$ not in | ||

1895 | $F_N$ which has a | ||

1896 | continued fraction representation | ||

1897 | $[a_0;a_1,a_2,\ldots{} ,a_n]$, the | ||

1898 | highest-order convergent $s_k = p_k/q_k$ with $q_k \leq N$ is one | ||

1899 | neighbor\footnote{By neighbors in $F_N$ we mean the rational numbers | ||

1900 | in $F_N$ immediately to the left and immediately to the right | ||

1901 | of $a/b$.} | ||

1902 | to $a/b$ in $F_N$, and the other neighbor in | ||

1903 | $F_N$ is\footnote{Theorem \ref{thm:ccfr0:scba0:cfenclosingneighbors} | ||

1904 | is a somewhat stronger statement about best approximations | ||

1905 | than Khinchin makes in \cite{bibref:b:KhinchinClassic}, Theorem 15. | ||

1906 | We were not able to locate | ||

1907 | this theorem or a proof in print, | ||

1908 | but this theorem is understood within the number theory community. | ||

1909 | It appears on the Web | ||

1910 | page of David Eppstein \cite{bibref:i:davideppstein} in the form of a | ||

1911 | `C'-language computer program, | ||

1912 | \texttt{http://www.ics.uci.edu/\~{}{}eppstein/numth/frap.c}. | ||

1913 | Although | ||

1914 | Dr. Eppstein phrases the solution in terms of modifying | ||

1915 | a partial quotient, his approach is equivalent to | ||

1916 | (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01}).} | ||

1917 | |||

1918 | \begin{equation} | ||

1919 | \label{eq:ccfr0:scba0:thm:cfenclosingneighbors:01} | ||

1920 | \frac{{\displaystyle{\left\lfloor {\frac{{N - q_{k - 1} }}{{q_k }}} \right\rfloor} | ||

1921 | p_k + p_{k - 1} }}{{\displaystyle{\left\lfloor {\frac{{N - q_{k - 1} }}{{q_k }}} | ||

1922 | \right\rfloor} q_k + q_{k - 1} }}. | ||

1923 | \end{equation} | ||

1924 | \end{vworktheoremstatementpar} | ||

1925 | \begin{vworktheoremproof} | ||

1926 | First, it is proved that the highest-order | ||

1927 | convergent $s_k = p_k/q_k$ with $q_k \leq N$ is one of the two | ||

1928 | neighbors to $a/b$ in $F_N$. $s_k \in F_N$, since $q_k \leq N$. | ||

1929 | By Theorem \ref{thm:ccfr0:scba0:convergentcloseness}, the upper bound on the | ||

1930 | difference between $a/b$ and arbitrary $s_k$ is given by | ||

1931 | |||

1932 | \begin{equation} | ||

1933 | \label{eq:ccfr0:scba0:thm:cfenclosingneighbors:02} | ||

1934 | \left| {\frac{a}{b} - \frac{{p_k }}{{q_k }}} \right| < \frac{1}{{q_k q_{k + 1} }}. | ||

1935 | \end{equation} | ||

1936 | |||

1937 | For two consecutive terms in $F_N$, $Kh-Hk=1$ | ||

1938 | (\cfryzeroxrefcomma{}Theorem \ref{thm:cfry0:spfs:02}). | ||

1939 | For a Farey neighbor $H/K$ to $s_k$ in $F_N$, | ||

1940 | (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:03}) must hold. | ||

1941 | |||

1942 | \begin{equation} | ||

1943 | \label{eq:ccfr0:scba0:thm:cfenclosingneighbors:03} | ||

1944 | \frac{1}{q_k N} \leq \left| {\frac{H}{K} - \frac{p_k}{q_k}} \right| | ||

1945 | \end{equation} | ||

1946 | |||

1947 | $q_{k+1}>N$, because $q_{k+1}>q_k$ and $p_k/q_k$ was chosen to be the | ||

1948 | highest-order convergent with $q_k\leq N$. Using this knowledge and | ||

1949 | combining (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:02}) and | ||

1950 | (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:03}) leads to | ||

1951 | (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:04}). | ||

1952 | |||

1953 | \begin{equation} | ||

1954 | \label{eq:ccfr0:scba0:thm:cfenclosingneighbors:04} | ||

1955 | \left| {\frac{a}{b} - \frac{{p_k }}{{q_k }}} \right| < \frac{1}{{q_k q_{k + 1} }} | ||

1956 | < | ||

1957 | \frac{1}{q_k N} \leq \left| {\frac{H}{K} - \frac{p_k}{q_k}} \right| | ||

1958 | \end{equation} | ||

1959 | |||

1960 | This proves that $s_k$ is one neighbor to $a/b$ in $F_N$. | ||

1961 | The apparatus of continued fractions ensures that the | ||

1962 | highest order convergent $s_k$ with $q_k\leq N$ is closer to $a/b$ than | ||

1963 | to any neighboring term in $F_N$. Thus, there is | ||

1964 | no intervening term of $F_N$ between $s_k$ and $a/b$. | ||

1965 | If $k$ is even, $s_k<a/b$, and if $k$ is | ||

1966 | odd, $s_k>a/b$. | ||

1967 | |||

1968 | It must be proved that (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01}) is the other Farey | ||

1969 | neighbor. For brevity, only the case of $k$ even is proved: the | ||

1970 | case of $k$ odd is symmetrical. (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01}) | ||

1971 | is of the form (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:05}), | ||

1972 | where $i \in \vworkintsetnonneg$. | ||

1973 | |||

1974 | \begin{equation} | ||

1975 | \label{eq:ccfr0:scba0:thm:cfenclosingneighbors:05} | ||

1976 | \frac{{ip_k + p_{k - 1} }}{{iq_k + q_{k - 1} }} | ||

1977 | \end{equation} | ||

1978 | |||

1979 | $k$ is even, $s_k < a/b$, and the two Farey terms enclosing $a/b$, in | ||

1980 | order, are | ||

1981 | |||

1982 | \begin{equation} | ||

1983 | \label{eq:ccfr0:scba0:thm:cfenclosingneighbors:06} | ||

1984 | \frac{p_k }{q_k },\frac{ip_k + p_{k - 1} }{iq_k + q_{k - 1} }. | ||

1985 | \end{equation} | ||

1986 | |||

1987 | Applying the $Kh - Hk = 1$ test, (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:07}), \ | ||

1988 | gives the | ||

1989 | result of 1, since by Theorem | ||

1990 | \ref{thm:ccfr0:scnv0:crossproductminusone}, | ||

1991 | $q_kp_{k-1}-p_kq_{k-1}=(-1)^k$. | ||

1992 | |||

1993 | \begin{equation} | ||

1994 | \label{eq:ccfr0:scba0:thm:cfenclosingneighbors:07} | ||

1995 | \begin{array}{*{20}c} | ||

1996 | {(q_k )(ip_k + p_{k - 1} ) - (p_k )(iq_k + q_{k - 1} ) = 1} | ||

1997 | \end{array} | ||

1998 | \end{equation} | ||

1999 | |||

2000 | Thus, every potential Farey neighbor of the form (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:05}) | ||

2001 | meets the $Kh - Hk = 1$ test. It is also straightforward | ||

2002 | to show that \emph{only} potential Farey neighbors of the | ||

2003 | form (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:05}) can meet the $Kh-Hk=1$ test, using the | ||

2004 | property that $p_k$ and $q_k$ are coprime. | ||

2005 | |||

2006 | It must be established that a | ||

2007 | rational number of the form (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:05}) | ||

2008 | is irreducible. This result comes directly from | ||

2009 | (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:07}), | ||

2010 | since if the numerator | ||

2011 | and denominator of (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01}) or | ||

2012 | (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:05}) are not coprime, the difference of 1 is | ||

2013 | not possible. | ||

2014 | |||

2015 | The denominator of (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01}) | ||

2016 | can be rewritten as | ||

2017 | |||

2018 | \begin{equation} | ||

2019 | \label{eq:ccfr0:scba0:thm:cfenclosingneighbors:08} | ||

2020 | N - \left[ {\left( {N - q_{k - 1} } \right)\bmod q_k } \right] \in \left\{ {N - q_k + 1,...,N} \right\}. | ||

2021 | \end{equation} | ||

2022 | |||

2023 | It must be shown that if one irreducible | ||

2024 | rational number---namely, the rational number given by | ||

2025 | (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01})---with a denominator | ||

2026 | $\in \{ N-q_k+1,\ldots{} ,N \}$ meets the $Kh - Hk = 1$ | ||

2027 | test, there can be no other irreducible rational number | ||

2028 | in $F_N$ with a larger | ||

2029 | denominator which also meets this test. | ||

2030 | |||

2031 | Given (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:07}), | ||

2032 | and given that \emph{only} rational numbers of the form | ||

2033 | (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:05}) | ||

2034 | can meet the $Kh-Hk=1$ test, and given that any number of the | ||

2035 | form (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:05}) | ||

2036 | is irreducible, the irreducible number meeting the | ||

2037 | $Kh-Hk=1$ test with the next larger denominator after the denominator of | ||

2038 | (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01}) | ||

2039 | will have a denominator $\in \{ N+1, \ldots, N+q_k \}$. Thus, | ||

2040 | no other irreducible rational number in $F_N$ besides that given | ||

2041 | by (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01}) with a larger denominator | ||

2042 | $\leq N$ and which meets the $Kh - Hk = 1$ test can exist; therefore | ||

2043 | (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01}) is the other enclosing Farey neighbor to | ||

2044 | $a/b$ in $F_N$. | ||

2045 | \end{vworktheoremproof} | ||

2046 | \vworktheoremfooter{} | ||

2047 | |||

2048 | Theorem \ref{thm:ccfr0:scba0:cfenclosingneighbors} establishes that | ||

2049 | the two neighbors in $F_N$ to a rational number $a/b$ will be the highest-order | ||

2050 | convergent with a denominator not exceeding $N$, and the number | ||

2051 | specified by (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01}). | ||

2052 | An interesting and worthwhile question to ask about | ||

2053 | Theorem \ref{thm:ccfr0:scba0:cfenclosingneighbors} is which of the | ||

2054 | two neighbors will be \emph{closer} to $a/b$---the convergent or the | ||

2055 | number specified by (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01})? | ||

2056 | Can we make any strong, simple, and easy-to-remember statements | ||

2057 | about the relative distance? We answer this question and some related | ||

2058 | questions now. | ||

2059 | |||

2060 | We are not aware of any rules that decisively predict which of the two | ||

2061 | Farey neighbors in Theorem \ref{thm:ccfr0:scba0:cfenclosingneighbors} | ||

2062 | will be closer to $a/b$\footnote{We should qualify this by saying that | ||

2063 | we mean a rule which uses only partial quotients up through | ||

2064 | $a_k$ or at most $a_{k+1}$, which is the same information used | ||

2065 | by the theorem. We should also add that although Theorem | ||

2066 | \ref{thm:ccfr0:scba0:cfenclosingneighbors} is worded to only consider | ||

2067 | non-negative rational numbers, the theorem and the results here | ||

2068 | apply to non-negative irrational numbers as well, so long as enough partial | ||

2069 | quotients can be obtained.}, although Lemma | ||

2070 | \ref{lem:ccfr0:scba0:enclosingneighborstheoremfurtherresult} is able | ||

2071 | to predict that the highest-ordered convergent $s_k$ with a denominator | ||

2072 | not exceeding $N$ will be closer in many cases. | ||

2073 | In general, either neighbor may be closer. | ||

2074 | The most straightforward approach that we | ||

2075 | are aware of is to calculate both Farey neighbors and to calculate | ||

2076 | their respective distances from $a/b$. The difficulty in devising a simple rule | ||

2077 | to predict which neighbor | ||

2078 | is closer is compounded by that fact that knowledge of | ||

2079 | $[a_0; a_1, \ldots{} , a_k]$ such that $s_k$ is the highest-ordered | ||

2080 | convergent with $q_k \leq N$ is incomplete knowledge of $a/b$ and can | ||

2081 | only confine $a/b$ to an inequality in the sense suggested by | ||

2082 | (\ref{eq:ccfr0:spar0:01}) through | ||

2083 | (\ref{eq:ccfr0:spar0:03}). Note that the | ||

2084 | value specified by (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01}) | ||

2085 | is an intermediate fraction, and that the statement of Theorem | ||

2086 | \ref{thm:ccfr0:scba0:cfenclosingneighbors} | ||

2087 | coincides with Khinchin's Theorem 15 | ||

2088 | (\cite{bibref:b:KhinchinClassic}, p. 22). | ||

2089 | |||

2090 | However, even in the absence of a rule to decisively | ||

2091 | predict which of the | ||

2092 | two Farey neighbors specified by Theorem | ||

2093 | \ref{thm:ccfr0:scba0:cfenclosingneighbors} is closer to $a/b$, | ||

2094 | there are other useful properties of convergents | ||

2095 | as best approximations which we present | ||

2096 | now. | ||

2097 | |||

2098 | It has been stated earlier that even-ordered convergents form an | ||

2099 | increasing sequence and that odd-ordered convergents also form a | ||

2100 | decreasing sequence. However, up to this point, we have not made | ||

2101 | a statement about the relationship between even- and odd-ordered | ||

2102 | convergents. We present such a statement as Lemma | ||

2103 | \ref{lem:ccfr0:scba0:convergenterrordecreases}, | ||

2104 | below. | ||

2105 | |||

2106 | \begin{vworklemmastatement} | ||

2107 | \label{lem:ccfr0:scba0:convergenterrordecreases} | ||

2108 | In the case of a finite or infinite continued fraction representation | ||

2109 | of a non-negative rational or irrational | ||

2110 | number $\alpha \in \vworkrealsetnonneg$, for all $k$, | ||

2111 | |||

2112 | \begin{equation} | ||

2113 | \label{eq:lem:ccfr0:scba0:convergenterrordecreases:01} | ||

2114 | \left| {\alpha - \frac{p_k}{q_k}} \right| < | ||

2115 | \left| {\alpha - \frac{p_{k-1}}{q_{k-1}}} \right| . | ||

2116 | \end{equation} | ||

2117 | In other words, convergents get ever-closer to $\alpha$, without | ||

2118 | respect to whether they are even- or odd-ordered convergents. | ||

2119 | \end{vworklemmastatement} | ||

2120 | \begin{vworklemmaproof} | ||

2121 | In this proof, we show that for all $k$, | ||

2122 | |||

2123 | \begin{equation} | ||

2124 | \label{eq:lem:ccfr0:scba0:convergenterrordecreases:02} | ||

2125 | | s_{k-2} - s_{k-1} | > 2 | s_{k-1} - s_k | . | ||

2126 | \end{equation} | ||

2127 | |||

2128 | To understand why the proof is valid, consider the case of $k$ even, | ||

2129 | in which case $s_k < \alpha$, so that $s_{k-1} - \alpha < s_{k-1} - s_k$. | ||

2130 | If $s_{k-1} - s_{k-2} > 2 (s_{k-1} - s_k)$, then | ||

2131 | $s_{k-2}$ is further to the left of $\alpha$ than $s_{k-1}$ is to the | ||

2132 | right of $\alpha$; thus (\ref{eq:lem:ccfr0:scba0:convergenterrordecreases:01}) | ||

2133 | applies. A symmetrical argument holds for $k$ odd. | ||

2134 | |||

2135 | By Theorem \ref{thm:ccfr0:scnv0:crossproductminusone}, | ||

2136 | |||

2137 | \begin{equation} | ||

2138 | \label{eq:lem:ccfr0:scba0:convergenterrordecreases:03} | ||

2139 | s_{k-2} - s_{k-1} | ||

2140 | = \frac{p_{k-2}}{q_{k-2}} | ||

2141 | - \frac{p_{k-1}}{q_{k-1}} | ||

2142 | = \frac{(-1)^{k-1}}{q_{k-2} q_{k-1}} , | ||

2143 | \end{equation} | ||

2144 | |||

2145 | and similarly | ||

2146 | |||

2147 | \begin{equation} | ||

2148 | \label{eq:lem:ccfr0:scba0:convergenterrordecreases:04} | ||

2149 | s_{k-1} - s_{k} | ||

2150 | = \frac{p_{k-1}}{q_{k-1}} | ||

2151 | - \frac{p_{k}}{q_{k}} | ||

2152 | = \frac{(-1)^{k}}{q_{k-1} q_{k}} . | ||

2153 | \end{equation} | ||

2154 | |||

2155 | In order for (\ref{eq:lem:ccfr0:scba0:convergenterrordecreases:02}) | ||

2156 | to be met, it must be true that | ||

2157 | $2 q_{k-2} q_{k-1} < q_{k-1} q_k$, or equivalently that | ||

2158 | $2 q_{k-2} < q_k$. Since canonically $q_k = a_k q_{k-1} + q_{k-2}$ | ||

2159 | (Eq. \ref{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:10}), | ||

2160 | the requirement is that $2 q_{k-2} < a_k q_{k-1} + q_{k-2}$. | ||

2161 | Since $a_k \geq 1$ and convergents are ever-increasing, | ||

2162 | (\ref{eq:lem:ccfr0:scba0:convergenterrordecreases:02}) is met and the | ||

2163 | lemma is proved. | ||

2164 | \end{vworklemmaproof} | ||

2165 | \vworklemmafooter{} | ||

2166 | |||

2167 | Theorem \ref{thm:ccfr0:scba0:convergentcloseness} establishes a | ||

2168 | maximum distance from a number $\alpha$ that we wish to approximate | ||

2169 | to a convergent. We now provide a second result that establishes | ||

2170 | a \emph{minimum} distance. (This result is Theorem 13, p. | ||

2171 | 15, from \cite{bibref:b:KhinchinClassic}.) | ||

2172 | |||

2173 | \begin{vworktheoremstatement} | ||

2174 | \label{thm:ccfr0:scba0:convergentfarness} | ||

2175 | In the case of an infinite continued fraction representation | ||

2176 | $[a_0; a_1, a_2, \ldots]$ of | ||

2177 | a non-negative irrational number $\alpha \in \vworkrealsetnonneg$, | ||

2178 | for all $k \geq 0$; or in the case of a [necessarily finite] | ||

2179 | continued fraction representation $[a_0; a_1, a_2, \ldots , a_n]$ | ||

2180 | of a non-negative rational number | ||

2181 | $\alpha \in \vworkrealsetnonneg$, for all $0 \leq k \leq n-1$, | ||

2182 | |||

2183 | \begin{equation} | ||

2184 | \label{eq:thm:ccfr0:scba0:convergentfarness:01} | ||

2185 | \left| {\alpha - \frac{p_k}{q_k}} \right| > \frac{1}{q_k(q_{k+1}+q_k)} . | ||

2186 | \end{equation} | ||

2187 | \end{vworktheoremstatement} | ||

2188 | \begin{vworktheoremproof} | ||

2189 | We've already established (Lemma \ref{lem:ccfr0:scba0:convergenterrordecreases}) | ||

2190 | that each convergent $s_{k+1}$ is nearer to | ||

2191 | a number $\alpha$ to be approximated than the previous | ||

2192 | convergent, $s_k$, i.e. for all $k$, | ||

2193 | |||

2194 | \begin{equation} | ||

2195 | \label{eq:thm:ccfr0:scba0:convergentfarness:02} | ||

2196 | \left| {\alpha - \frac{p_{k+1}}{q_{k+1}}} \right| < | ||

2197 | \left| {\alpha - \frac{p_{k}}{q_{k}}} \right| . | ||

2198 | \end{equation} | ||

2199 | |||

2200 | Since the mediant of two fractions always lies between | ||

2201 | them (Lemma \cfryzeroxrefhyphen{}\ref{lem:cfry0:spfs:02c}), it | ||

2202 | follows directly that | ||

2203 | |||

2204 | \begin{equation} | ||

2205 | \label{eq:thm:ccfr0:scba0:convergentfarness:03} | ||

2206 | \left| {\alpha - \frac{p_{k}}{q_{k}}} \right| > | ||

2207 | \left| {\frac{p_k + p_{k+1}}{q_k + q_{k+1}} - \frac{p_k}{q_k}} \right| = | ||

2208 | \frac{1}{q_k ( q_k + q_{k+1})} . | ||

2209 | \end{equation} | ||

2210 | \end{vworktheoremproof} | ||

2211 | \begin{vworktheoremparsection}{Remark I} | ||

2212 | This theorem can be combined with Theorem \ref{thm:ccfr0:scba0:convergentcloseness} | ||

2213 | to give the following combined inequality: | ||

2214 | |||

2215 | \begin{equation} | ||

2216 | \label{eq:thm:ccfr0:scba0:convergentfarness:04} | ||

2217 | \frac{1}{q_k ( q_k + q_{k+1})} < | ||

2218 | \left| {\alpha - \frac{p_{k}}{q_{k}}} \right| \leq | ||

2219 | \frac{1}{q_k q_{k+1}} . | ||

2220 | \end{equation} | ||

2221 | \end{vworktheoremparsection} | ||

2222 | \vworktheoremfooter{} | ||

2223 | |||

2224 | We now supply an interesting and sometimes useful property of | ||

2225 | convergents used as best approximations. Note that we later show that | ||

2226 | Lemma \ref{lem:ccfr0:scba0:convergentbetterappthanlesserdenominator} | ||

2227 | is a weak statement (a stronger statement can be made, Lemma | ||

2228 | \ref{lem:ccfr0:scba0:morecomplexconvergentbapprule}), but this lemma | ||

2229 | has the advantage of being extremely easy to remember. | ||

2230 | |||

2231 | \begin{vworklemmastatement} | ||

2232 | \label{lem:ccfr0:scba0:convergentbetterappthanlesserdenominator} | ||

2233 | A convergent $s_k = p_k/q_k$ to a non-negative [rational or irrational] number | ||

2234 | $\alpha \in \vworkrealsetnonneg$ is closer to $\alpha$ | ||

2235 | than any other rational number with the same or a smaller | ||

2236 | denominator. | ||

2237 | \end{vworklemmastatement} | ||

2238 | \begin{vworklemmaproof} | ||

2239 | Let $\alpha$ be the non-negative real number, rational or irrational, | ||

2240 | that we wish to approximate. | ||

2241 | |||

2242 | If there is a number (let's call it $c/d$) | ||

2243 | closer to $\alpha$ than $s_k = p_k / q_k$, with the same or a smaller denominator | ||

2244 | than $s_k$, then by definition it must be in the Farey series of order | ||

2245 | $q_k$, which we denote $F_{q_k}$. | ||

2246 | |||

2247 | Theorem \ref{thm:ccfr0:scba0:cfenclosingneighbors} | ||

2248 | assures us that the two Farey neighbors to $\alpha$ in $F_{q_k}$ will be | ||

2249 | $s_k$ and the number given by (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01}). | ||

2250 | Note that Theorem \ref{thm:ccfr0:scba0:cfenclosingneighbors} | ||

2251 | applies to irrational numbers as well (although the theorem statement | ||

2252 | does not indicate this), so we interpret | ||

2253 | Theorem \ref{thm:ccfr0:scba0:cfenclosingneighbors} | ||

2254 | in that sense. | ||

2255 | |||

2256 | Note in (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01}) that the | ||

2257 | expression involving the $floor(\cdot{})$ function will evaluate | ||

2258 | to be zero, since $N=q_k$. Thus, the other Farey neighbor to | ||

2259 | $\alpha$ in $F_{q_k}$ will be $s_{k-1} = p_{k-1}/q_{k-1}$. | ||

2260 | |||

2261 | We have already shown in Lemma \ref{lem:ccfr0:scba0:convergenterrordecreases} | ||

2262 | that $|\alpha - s_{k-1}| > |\alpha - s_{k}|$, therefore | ||

2263 | $s_k$ is closer to $\alpha$ than the other Farey neighbor given | ||

2264 | by (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01}). | ||

2265 | Furthermore, because any $c/d$ which is closer to $\alpha$ than | ||

2266 | $s_k$ must be present in $F_{q_k}$, such a $c/d$ does not exist. | ||

2267 | \end{vworklemmaproof} | ||

2268 | \begin{vworklemmaparsection}{Remark I} | ||

2269 | In practice, this lemma is little more than parlor trivia | ||

2270 | (it is not mathematically significant), but it is useful | ||

2271 | information and very easy to remember. For example, $355/113$ is a convergent to | ||

2272 | $\pi$, and it is sometimes useful to know that no better rational approximation | ||

2273 | can exist with the same or a smaller denominator. | ||

2274 | \end{vworklemmaparsection} | ||

2275 | \begin{vworklemmaparsection}{Remark II} | ||

2276 | A stronger statement can be made (see | ||

2277 | Lemma \ref{lem:ccfr0:scba0:morecomplexconvergentbapprule}). | ||

2278 | \end{vworklemmaparsection} | ||

2279 | \vworklemmafooter{} | ||

2280 | |||

2281 | We now | ||

2282 | present a stronger statement about convergents as best approximations that | ||

2283 | is not as easy to remember as | ||

2284 | Lemma \ref{lem:ccfr0:scba0:convergentbetterappthanlesserdenominator}. | ||

2285 | |||

2286 | \begin{vworklemmastatement} | ||

2287 | \label{lem:ccfr0:scba0:morecomplexconvergentbapprule} | ||

2288 | A convergent $s_k = p_k/q_k$ to a non-negative | ||

2289 | [rational or irrational] number | ||

2290 | $\alpha \in \vworkrealsetnonneg$ is closer to $\alpha$ | ||

2291 | than any other rational number with a denominator | ||

2292 | less than $q_k + q_{k-1}$. | ||

2293 | \end{vworklemmastatement} | ||

2294 | \begin{vworklemmaproof} | ||

2295 | Let $N$ be the denominator of a rational number which is | ||

2296 | potentially closer to $\alpha$ than $s_k$. If | ||

2297 | $N < q_k + q_{k+1}$, then | ||

2298 | (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01}) | ||

2299 | evaluates to $s_{k-1}$, and Lemma | ||

2300 | \ref{lem:ccfr0:scba0:convergenterrordecreases} has established that | ||

2301 | $s_k$ is closer to $\alpha$ than $s_{k-1}$. If, on the other | ||

2302 | hand, $N \geq q_k + q_{k+1}$, then the intermediate fraction specified by | ||

2303 | (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01}) \emph{may} be | ||

2304 | closer to $\alpha$ than $s_k$. | ||

2305 | \end{vworklemmaproof} | ||

2306 | \begin{vworklemmaparsection}{Remark I} | ||

2307 | This statement is harder to remember, but a stronger statement | ||

2308 | than Lemma \ref{lem:ccfr0:scba0:convergentbetterappthanlesserdenominator}. | ||

2309 | \end{vworklemmaparsection} | ||

2310 | \begin{vworklemmaparsection}{Remark II} | ||

2311 | Note that the only valid implication is $N < q_k + q_{k+1} \rightarrow$ | ||

2312 | (convergent is closer). Note that | ||

2313 | $N \geq q_k + q_{k+1} \nrightarrow$ (intermediate fraction is closer)! | ||

2314 | If $N \geq q_k + q_{k+1}$, either the convergent or the intermediate fraction | ||

2315 | may be closer. | ||

2316 | This statement is harder to remember, but a stronger statement | ||

2317 | than Lemma \ref{lem:ccfr0:scba0:convergentbetterappthanlesserdenominator}. | ||

2318 | \end{vworklemmaparsection} | ||

2319 | \vworklemmafooter{} | ||

2320 | |||

2321 | Finally, we present a result about Theorem | ||

2322 | \ref{thm:ccfr0:scba0:cfenclosingneighbors} that will predict | ||

2323 | in some circumstances that the highest-ordered convergent | ||

2324 | $s_k$ with a denominator not exceeding $N$ must be closer | ||

2325 | to $a/b$ than the intermediate fraction specified by | ||

2326 | (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01}). | ||

2327 | |||

2328 | \begin{vworklemmastatement} | ||

2329 | \label{lem:ccfr0:scba0:enclosingneighborstheoremfurtherresult} | ||

2330 | In Theorem \ref{thm:ccfr0:scba0:cfenclosingneighbors}, | ||

2331 | if $N < q_k + q_{k-1}$, the highest ordered convergent | ||

2332 | $s_k$ with a denominator not exceeding $N$ is closer to | ||

2333 | $a/b$\footnote{Note that this result is also valid for | ||

2334 | convergents to an irrational number, although | ||

2335 | Theorem \ref{thm:ccfr0:scba0:cfenclosingneighbors} is | ||

2336 | not worded in this way.} then the intermediate fraction specified by | ||

2337 | (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01}). | ||

2338 | If $N \geq q_k + q_{k-1}$, either $s_k$ or the intermediate | ||

2339 | fraction specified by (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01}) | ||

2340 | may be closer. | ||

2341 | \end{vworklemmastatement} | ||

2342 | \begin{vworklemmaproof} | ||

2343 | See the proof of Lemma | ||

2344 | \ref{lem:ccfr0:scba0:morecomplexconvergentbapprule}. | ||

2345 | \end{vworklemmaproof} | ||

2346 | \vworklemmafooter{} | ||

2347 | |||

2348 | Theorem \ref{thm:ccfr0:scba0:cfenclosingneighbors} immediately suggests | ||

2349 | an algorithm for obtaining the enclosing rational numbers in $F_N$ | ||

2350 | to a rational number $a/b \notin F_N$, which we present as | ||

2351 | Algorithm \ref{alg:ccfr0:scba0:cfenclosingneighborsfn}. Although | ||

2352 | we don't formally show it, the algorithm is $O(log \; N)$, due to | ||

2353 | the minimum geometric rate of increase of convergents | ||

2354 | (Theorem \ref{thm:ccfr0:scnv0:minimumrateofconvergentdenominatorincrease}). | ||

2355 | Note that the algorithm will proceed only until $q_k > N$, not necessarily | ||

2356 | until all partial quotients of $a/b$ are obtained. Note also that the | ||

2357 | algorithm can be applied to irrational numbers with minor | ||

2358 | modification (all that matters is that we can obtain enough | ||

2359 | partial quotients). | ||

2360 | |||

2361 | \begin{vworkalgorithmstatementpar}{Enclosing Neighbors Of \mbox{\boldmath $a/b \notin F_N$} | ||

2362 | In \mbox{\boldmath $F_N$}} | ||

2363 | \label{alg:ccfr0:scba0:cfenclosingneighborsfn} | ||

2364 | \begin{alglvl0} | ||

2365 | \item $k := -1$. | ||

2366 | \item $divisor_{-1} := a$. | ||

2367 | \item $remainder_{-1} := b$. | ||

2368 | \item $p_{-1} := 1$. | ||

2369 | \item $q_{-1} := 0$. | ||

2370 | |||

2371 | \item Repeat | ||

2372 | |||

2373 | \begin{alglvl1} | ||

2374 | \item $k := k + 1$. | ||

2375 | \item $dividend_k := divisor_{k-1}$. | ||

2376 | \item $divisor_k := remainder_{k-1}$. | ||

2377 | \item $a_k := dividend_k \; div \; divisor_k$. | ||

2378 | \item $remainder_k := dividend_k \; mod \; divisor_k$. | ||

2379 | \item If $k=0$ then $p_k := a_k$ else $p_k := a_k p_{k-1} + p_{k-2}$. | ||

2380 | \item If $k=0$ then $q_k := 1$ else $q_k := a_k q_{k-1} + q_{k-2}$. | ||

2381 | \end{alglvl1} | ||

2382 | |||

2383 | \item Until ($q_k > k_{MAX}$). | ||

2384 | \item $s_{k-1} = p_{k-1}/q_{k-1}$ will be one Farey neighbor to $a/b$ in $F_{k_{MAX}}$. | ||

2385 | Apply (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01}) | ||

2386 | to obtain the other Farey neighbor. | ||

2387 | \end{alglvl0} | ||

2388 | \end{vworkalgorithmstatementpar} | ||

2389 | %\vworkalgorithmfooter{} | ||

2390 | |||

2391 | \begin{vworkexamplestatement} | ||

2392 | \label{ex:ccfr0:scba0:bestrapapptoratnum} | ||

2393 | Find the members of $F_{100}$ which enclose the conversion factor | ||

2394 | from kilometers-per-hour to miles-per-hour. Assume that | ||

2395 | one mile is 1.6093 kilometers (exactly). | ||

2396 | \end{vworkexamplestatement} | ||

2397 | \begin{vworkexampleparsection}{Solution} | ||

2398 | The conversion factor from KPH to MPH is the reciprocal of 1.6093. As a rational | ||

2399 | number, 1.6093 is 16,093/10,000, so 10,000/16,093 is its exact reciprocal. | ||

2400 | Applying Algorithm \ref{alg:ccfr0:scba0:cfenclosingneighborsfn} | ||

2401 | with $a/b = 10,000/16,093$ and $k_{MAX} = 100$ yields Table | ||

2402 | \ref{tbl:ex:ccfr0:scba0:bestrapapptoratnum}. | ||

2403 | |||

2404 | \begin{table} | ||

2405 | \caption{Application Of Algorithm \ref{alg:ccfr0:scba0:cfenclosingneighborsfn} | ||

2406 | To Find Members Of $F_{100}$ Which Enclose 10,000/16,093 | ||

2407 | (Example \ref{ex:ccfr0:scba0:bestrapapptoratnum})} | ||

2408 | \label{tbl:ex:ccfr0:scba0:bestrapapptoratnum} | ||

2409 | \begin{center} | ||

2410 | \begin{tabular}{|c|c|c|c|c|c|c|} | ||

2411 | \hline | ||

2412 | \small{Index} & \small{$dividend_k$} & \small{$divisor_k$} & \small{$a_k$} & \small{$remainder_k$} & \small{$p_k$} & \small{$q_k$} \\ | ||

2413 | \small{($k$)} & & & & & & \\ | ||

2414 | \hline | ||

2415 | \hline | ||

2416 | \small{-1} & \small{N/A} & \small{10,000} & \small{N/A} & \small{16,093} & \small{1} & \small{0} \\ | ||

2417 | \hline | ||

2418 | \small{0} & \small{10,000} & \small{16,093} & \small{0} & \small{10,000} & \small{0} & \small{1} \\ | ||

2419 | \hline | ||

2420 | \small{1} & \small{16,093} & \small{10,000} & \small{1} & \small{6,093} & \small{1} & \small{1} \\ | ||

2421 | \hline | ||

2422 | \small{2} & \small{10,000} & \small{6,093} & \small{1} & \small{3,907} & \small{1} & \small{2} \\ | ||

2423 | \hline | ||

2424 | \small{3} & \small{6,093} & \small{3,907} & \small{1} & \small{2,186} & \small{2} & \small{3} \\ | ||

2425 | \hline | ||

2426 | \small{4} & \small{3,907} & \small{2,186} & \small{1} & \small{1,721} & \small{3} & \small{5} \\ | ||

2427 | \hline | ||

2428 | \small{5} & \small{2,186} & \small{1,721} & \small{1} & \small{465} & \small{5} & \small{8} \\ | ||

2429 | \hline | ||

2430 | \small{6} & \small{1,721} & \small{465} & \small{3} & \small{326} & \small{18} & \small{29} \\ | ||

2431 | \hline | ||

2432 | \small{7} & \small{465} & \small{326} & \small{1} & \small{139} & \small{23} & \small{37} \\ | ||

2433 | \hline | ||

2434 | \small{8} & \small{326} & \small{139} & \small{2} & \small{48} & \small{64} & \small{103} \\ | ||

2435 | \hline | ||

2436 | \end{tabular} | ||

2437 | \end{center} | ||

2438 | \end{table} | ||

2439 | |||

2440 | Note from Table \ref{tbl:ex:ccfr0:scba0:bestrapapptoratnum} | ||

2441 | that the 7-th order convergent, $s_7 = 23/37$, | ||

2442 | is the highest-ordered convergent with $q_k \leq 100$, so | ||

2443 | by Theorem \ref{thm:ccfr0:scba0:cfenclosingneighbors}, 23/37 | ||

2444 | is one neighbor in $F_{100}$ to 10,000/16,093. Because $s_7$ | ||

2445 | is an odd-ordered convergent, it will be the right | ||

2446 | Farey neighbor. | ||

2447 | By (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01}), the | ||

2448 | other Farey neighbor is 41/66, and it will be the left | ||

2449 | Farey neighbor. | ||

2450 | \end{vworkexampleparsection} | ||

2451 | %\vworkexamplefooter{} | ||

2452 | |||

2453 | |||

2454 | \begin{vworkexamplestatement} | ||

2455 | \label{ex:ccfr0:scba0:bestrapapptoirratnum} | ||

2456 | Find the members of $F_{200}$ which | ||

2457 | enclose $\sqrt{3}$. | ||

2458 | \end{vworkexamplestatement} | ||

2459 | \begin{vworkexampleparsection}{Solution} | ||

2460 | We demonstrated in Example | ||

2461 | \ref{ex:ccfr0:scin0:symboliccfalgorithmexample} | ||

2462 | that the continued fraction representation of | ||

2463 | $\sqrt{3}$ is $[1;\overline{1,2}]$. | ||

2464 | As is highlighted in Footnote | ||

2465 | \ref{footnote:ccfr0:scba0:rationalitynotrequired}, it isn't required | ||

2466 | that a number be rational to apply Theorem | ||

2467 | \ref{thm:ccfr0:scba0:cfenclosingneighbors}, so long as | ||

2468 | enough partial quotients can be obtained. | ||

2469 | Using knowledge of the partial quotients of | ||

2470 | $\sqrt{3}$ and applying Algorithm \ref{alg:ccfr0:scba0:cfenclosingneighborsfn} | ||

2471 | yields Table \ref{tbl:ex:ccfr0:scba0:bestrapapptoirratnum} (note that it isn't necessary | ||

2472 | to track remainders, as we already have all of the partial quotients for | ||

2473 | $\sqrt{3}$). | ||

2474 | |||

2475 | \begin{table} | ||

2476 | \caption{Application Of Algorithm \ref{alg:ccfr0:scba0:cfenclosingneighborsfn} | ||

2477 | To Find Members Of $F_{100}$ Which Enclose $\sqrt{3}$ | ||

2478 | (Example \ref{ex:ccfr0:scba0:bestrapapptoirratnum})} | ||

2479 | \label{tbl:ex:ccfr0:scba0:bestrapapptoirratnum} | ||

2480 | \begin{center} | ||

2481 | \begin{tabular}{|c|c|c|c|} | ||

2482 | \hline | ||

2483 | \hspace{0.15in}\small{Index ($k$)}\hspace{0.15in} & \hspace{0.15in}\small{$a_k$}\hspace{0.15in} & | ||

2484 | \hspace{0.15in}\small{$p_k$}\hspace{0.15in} & \hspace{0.15in}\small{$q_k$}\hspace{0.15in} \\ | ||

2485 | \hline | ||

2486 | \hline | ||

2487 | \small{-1} & \small{N/A} & \small{1} & \small{0} \\ | ||

2488 | \hline | ||

2489 | \small{0} & \small{1} & \small{1} & \small{1} \\ | ||

2490 | \hline | ||

2491 | \small{1} & \small{1} & \small{2} & \small{1} \\ | ||

2492 | \hline | ||

2493 | \small{2} & \small{2} & \small{5} & \small{3} \\ | ||

2494 | \hline | ||

2495 | \small{3} & \small{1} & \small{7} & \small{4} \\ | ||

2496 | \hline | ||

2497 | \small{4} & \small{2} & \small{19} & \small{11} \\ | ||

2498 | \hline | ||

2499 | \small{5} & \small{1} & \small{26} & \small{15} \\ | ||

2500 | \hline | ||

2501 | \small{6} & \small{2} & \small{71} & \small{41} \\ | ||

2502 | \hline | ||

2503 | \small{7} & \small{1} & \small{97} & \small{56} \\ | ||

2504 | \hline | ||

2505 | \small{8} & \small{2} & \small{265} & \small{153} \\ | ||

2506 | \hline | ||

2507 | \small{9} & \small{1} & \small{362} & \small{209} \\ | ||

2508 | \hline | ||

2509 | \end{tabular} | ||

2510 | \end{center} | ||

2511 | \end{table} | ||

2512 | |||

2513 | Note from Table \ref{tbl:ex:ccfr0:scba0:bestrapapptoirratnum} | ||

2514 | that the 8-th order convergent, $s_8 = 265/153$, | ||

2515 | is the highest-ordered convergent with $q_k \leq 200$, so | ||

2516 | by Theorem \ref{thm:ccfr0:scba0:cfenclosingneighbors}, 265/153 | ||

2517 | is one neighbor in $F_{100}$ to $\sqrt{3}$. Because $s_8$ | ||

2518 | is an even-ordered convergent, it will be the left | ||

2519 | Farey neighbor. | ||

2520 | By (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01}), the | ||

2521 | other Farey neighbor is 97/56, and it will be the right | ||

2522 | Farey neighbor. | ||

2523 | \end{vworkexampleparsection} | ||

2524 | \vworkexamplefooter{} | ||

2525 | |||

2526 | |||

2527 | It is clear that Algorithm \ref{alg:ccfr0:scba0:cfenclosingneighborsfn} | ||

2528 | can be trivially modified to find enclosing neighbors | ||

2529 | in $F_{k_{MAX},\overline{h_{MAX}}}$, and we present this | ||

2530 | trivial modification as Algorithm | ||

2531 | \ref{alg:ccfr0:scba0:cfenclosingneighborsfab}. | ||

2532 | |||

2533 | \begin{vworkalgorithmstatementpar}{Enclosing Neighbors Of | ||

2534 | \mbox{\boldmath $x \notin F_{k_{MAX},\overline{h_{MAX}}}$} | ||

2535 | In \mbox{\boldmath $F_{k_{MAX},\overline{h_{MAX}}}$}} | ||

2536 | \label{alg:ccfr0:scba0:cfenclosingneighborsfab} | ||

2537 | \begin{alglvl0} | ||

2538 | \item If $a/b < h_{MAX}/k_{MAX}$, apply Algorithm | ||

2539 | \ref{alg:ccfr0:scba0:cfenclosingneighborsfn} directly; | ||

2540 | |||

2541 | \item Else if $a/b > h_{MAX}/k_{MAX}$, apply Algorithm | ||

2542 | \ref{alg:ccfr0:scba0:cfenclosingneighborsfn} using $b/a$ rather | ||

2543 | than $a/b$ as the input to the algorithm, using $h_{MAX}$ | ||

2544 | rather than $k_{MAX}$ as $N$, and | ||

2545 | using the reciprocals of the results of the algorithm.\footnote{The | ||

2546 | basis for taking the reciprocals of input and output and | ||

2547 | using $h_{MAX}$ rather than $k_{MAX}$ are explained | ||

2548 | in \cfryzeroxrefcomma{}Section \ref{cfry0:schk0}.} | ||

2549 | |||

2550 | \end{alglvl0} | ||

2551 | \end{vworkalgorithmstatementpar} | ||

2552 | %\vworkalgorithmfooter{} | ||

2553 | |||

2554 | \begin{vworkexamplestatement} | ||

2555 | \label{ex:ccfr0:scba0:bestratapptoirratnum2d} | ||

2556 | Find the members of $F_{200,\overline{100}}$ which | ||

2557 | enclose $\sqrt{3}$. | ||

2558 | \end{vworkexamplestatement} | ||

2559 | \begin{vworkexampleparsection}{Solution} | ||

2560 | It was shown in Example \ref{ex:ccfr0:scba0:bestrapapptoirratnum} | ||

2561 | that the two enclosing neighbors to $\sqrt{3}$ in | ||

2562 | $F_{200}$ are 265/153 and 97/56. Note that the first of | ||

2563 | these neighbors, 265/153, violates the constraint on the | ||

2564 | numerator. | ||

2565 | As explained in Section \cfryzeroxrefhyphen{}\ref{cfry0:schk0}, | ||

2566 | because $\sqrt{3} > 100/200$, the constraint on the | ||

2567 | numerator is the dominant constraint, and the necessary | ||

2568 | approach is to find the neighbors of $1/\sqrt{3}$ in | ||

2569 | $F_{100}$, then invert the results. | ||

2570 | Although we don't explain it in this work, | ||

2571 | the reciprocal of a continued fraction can be formed by | ||

2572 | ``right-shifting'' or ``left-shifting'' the continued fraction one position. | ||

2573 | Thus, if $[1;1,2,1,2,1,2, \ldots{}]$ = $[1;\overline{1,2}]$ | ||

2574 | is the continued fraction representation of $\sqrt{3}$, then | ||

2575 | $[0;1,1,2,1,2,1, \ldots{}]$ = $[0;1,\overline{1,2}]$ is the | ||

2576 | continued fraction representation of $1/\sqrt{3}$. Using | ||

2577 | this result and constructing the convergents until | ||

2578 | $q_k \geq 100$ yields Table \ref{tbl:ex:ccfr0:scba0:bestratapptoirratnum2d}. | ||

2579 | |||

2580 | \begin{table} | ||

2581 | \caption{Application Of Algorithm \ref{alg:ccfr0:scba0:cfenclosingneighborsfab} | ||

2582 | To Find Members Of $F_{100}$ Which Enclose $1/\sqrt{3}$ | ||

2583 | (Example \ref{ex:ccfr0:scba0:bestratapptoirratnum2d})} | ||

2584 | \label{tbl:ex:ccfr0:scba0:bestratapptoirratnum2d} | ||

2585 | \begin{center} | ||

2586 | \begin{tabular}{|c|c|c|c|} | ||

2587 | \hline | ||

2588 | \hspace{0.15in}\small{Index ($k$)}\hspace{0.15in} & \hspace{0.15in}\small{$a_k$}\hspace{0.15in} & | ||

2589 | \hspace{0.15in}\small{$p_k$}\hspace{0.15in} & \hspace{0.15in}\small{$q_k$}\hspace{0.15in} \\ | ||

2590 | \hline | ||

2591 | \hline | ||

2592 | \small{-1} & \small{N/A} & \small{1} & \small{0} \\ | ||

2593 | \hline | ||

2594 | \small{0} & \small{0} & \small{0} & \small{1} \\ | ||

2595 | \hline | ||

2596 | \small{1} & \small{1} & \small{1} & \small{1} \\ | ||

2597 | \hline | ||

2598 | \small{2} & \small{1} & \small{1} & \small{2} \\ | ||

2599 | \hline | ||

2600 | \small{3} & \small{2} & \small{3} & \small{5} \\ | ||

2601 | \hline | ||

2602 | \small{4} & \small{1} & \small{4} & \small{7} \\ | ||

2603 | \hline | ||

2604 | \small{5} & \small{2} & \small{11} & \small{19} \\ | ||

2605 | \hline | ||

2606 | \small{6} & \small{1} & \small{15} & \small{26} \\ | ||

2607 | \hline | ||

2608 | \small{7} & \small{2} & \small{41} & \small{71} \\ | ||

2609 | \hline | ||

2610 | \small{8} & \small{1} & \small{56} & \small{97} \\ | ||

2611 | \hline | ||

2612 | \small{9} & \small{2} & \small{153} & \small{265} \\ | ||

2613 | \hline | ||

2614 | \end{tabular} | ||

2615 | \end{center} | ||

2616 | \end{table} | ||

2617 | |||

2618 | Note from Table \ref{tbl:ex:ccfr0:scba0:bestratapptoirratnum2d} | ||

2619 | that the 8-th order convergent, $s_8 = 56/97$, | ||

2620 | is the highest-ordered convergent with $q_k \leq 100$, so | ||

2621 | by Theorem \ref{thm:ccfr0:scba0:cfenclosingneighbors}, 56/97 | ||

2622 | is one neighbor in $F_{100}$ to $1/\sqrt{3}$. Because $s_8$ | ||

2623 | is an even-ordered convergent, it will be the left | ||

2624 | Farey neighbor. | ||

2625 | By (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01}), the | ||

2626 | other Farey neighbor is 41/71, and it will be the right | ||

2627 | Farey neighbor. Taking the reciprocal of these neighbors (and | ||

2628 | reversing their order) yields $97/56 < \sqrt{3} < 41/71$ | ||

2629 | as the two members of $F_{200, \overline{100}}$ which enclose | ||

2630 | $\sqrt{3}$. | ||

2631 | \end{vworkexampleparsection} | ||

2632 | \vworkexamplefooter{} | ||

2633 | |||

2634 | |||

2635 | A natural question to ask is whether, given only a \emph{single} | ||

2636 | rational number $a/b \in F_N$, the apparatus of continued fractions | ||

2637 | can be used to economically find its neighbors in $F_N$. Examining | ||

2638 | the proof of Theorem \ref{thm:ccfr0:scba0:cfenclosingneighbors}, | ||

2639 | we see that the entire proof applies even if the denominator of the | ||

2640 | highest-order convergent, $q_n$, is less than or equal to $N$---that is, | ||

2641 | the number specified by (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01}) | ||

2642 | is a left or right Farey neighbor in $F_N$ of $a/b$. If $n$ is even, | ||

2643 | $s_{n-1} > s_n$, and the number specified by | ||

2644 | (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01}) will be the right Farey neighbor | ||

2645 | of $s_n$, and | ||

2646 | (\cfryzeroxrefhyphen{}\ref{eq:cfry0:sgfs0:thm:01:eq03}) and | ||

2647 | (\cfryzeroxrefhyphen{}\ref{eq:cfry0:sgfs0:thm:01:eq04}) | ||

2648 | can be used to find the left Farey neighbor. | ||

2649 | On the other hand if $n$ odd, $s_{n-1} < s_n$, (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01}) | ||

2650 | will be the left Farey neighbor of $s_n$, and | ||

2651 | (\cfryzeroxrefhyphen{}\ref{eq:cfry0:sgfs0:thm:01:eq01}) | ||

2652 | and | ||

2653 | (\cfryzeroxrefhyphen{}\ref{eq:cfry0:sgfs0:thm:01:eq02}) | ||

2654 | can be used to find the | ||

2655 | right Farey neighbor. We summarize these observations as Algorithm | ||

2656 | \ref{alg:ccfr0:scba0:cffareyneighborfn}. | ||

2657 | |||

2658 | \begin{vworkalgorithmstatementpar}{Neighbors Of | ||

2659 | \mbox{\boldmath $a/b \in F_N$} | ||

2660 | In \mbox{\boldmath $F_N$}} | ||

2661 | \label{alg:ccfr0:scba0:cffareyneighborfn} | ||

2662 | \end{vworkalgorithmstatementpar} | ||

2663 | \begin{alglvl0} | ||

2664 | |||

2665 | \item Apply the first part of Algorithm | ||

2666 | \ref{alg:ccfr0:scba0:cfenclosingneighborsfn} to obtain | ||

2667 | all of the partial quotients and convergents of $a/b$. | ||

2668 | The final convergent, $s_n = p_n/q_n$, will be | ||

2669 | $a/b$ in reduced form. | ||

2670 | |||

2671 | \item Use (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01}) | ||

2672 | (with $k = n$) to obtain the right Farey neighbor | ||

2673 | (if $n$ is even) or the left Farey neighbor (if $n$ | ||

2674 | is odd). | ||

2675 | |||

2676 | \item If $n$ is even, $s_{n-1} > s_n$, and the number specified by | ||

2677 | (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01}) will be | ||

2678 | the right Farey neighbor of $s_n$. Use | ||

2679 | (\cfryzeroxrefhyphen{}\ref{eq:cfry0:sgfs0:thm:01:eq03}) and | ||

2680 | (\cfryzeroxrefhyphen{}\ref{eq:cfry0:sgfs0:thm:01:eq04}) | ||

2681 | to find the left Farey neighbor. | ||

2682 | On the other hand if $n$ is odd, $s_{n-1} < s_n$, | ||

2683 | (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01}) | ||

2684 | will be the left Farey neighbor of $s_n$. Use | ||

2685 | (\cfryzeroxrefhyphen{}\ref{eq:cfry0:sgfs0:thm:01:eq01}) | ||

2686 | and (\cfryzeroxrefhyphen{}\ref{eq:cfry0:sgfs0:thm:01:eq02}) | ||

2687 | to find the right Farey neighbor. | ||

2688 | |||

2689 | \end{alglvl0} | ||

2690 | %\vworkalgorithmfooter{} | ||

2691 | |||

2692 | \begin{vworkexamplestatement} | ||

2693 | \label{ex:ccfr0:scba0:fnneighborsaoverbinfn} | ||

2694 | Find the neighbors of 5/7 in $F_{1,000,000}$. | ||

2695 | \end{vworkexamplestatement} | ||

2696 | \begin{vworkexampleparsection}{Solution} | ||

2697 | As per Algorithm \ref{alg:ccfr0:scba0:cffareyneighborfn}, the first | ||

2698 | step is to obtain the partial quotients and convergents of 5/7 | ||

2699 | (these partial quotients and convergents are shown in | ||

2700 | Table \ref{tbl:ex:ccfr0:scba0:fnneighborsaoverbinfn}). | ||

2701 | |||

2702 | \begin{table} | ||

2703 | \caption{Partial Quotients And Convergents Of 5/7 | ||

2704 | (Example \ref{ex:ccfr0:scba0:fnneighborsaoverbinfn})} | ||

2705 | \label{tbl:ex:ccfr0:scba0:fnneighborsaoverbinfn} | ||

2706 | \begin{center} | ||

2707 | \begin{tabular}{|c|c|c|c|c|c|c|} | ||

2708 | \hline | ||

2709 | \small{Index ($k$)} & \small{$dividend_k$} & \small{$divisor_k$} & \small{$a_k$} & \small{$remainder_k$} & \small{$p_k$} & \small{$q_k$} \\ | ||

2710 | \hline | ||

2711 | \hline | ||

2712 | \small{-1} & \small{N/A} & \small{5} & \small{N/A} & \small{7} & \small{1} & \small{0} \\ | ||

2713 | \hline | ||

2714 | \small{0} & \small{5} & \small{7} & \small{0} & \small{5} & \small{0} & \small{1} \\ | ||

2715 | \hline | ||

2716 | \small{1} & \small{7} & \small{5} & \small{1} & \small{2} & \small{1} & \small{1} \\ | ||

2717 | \hline | ||

2718 | \small{2} & \small{5} & \small{2} & \small{2} & \small{1} & \small{2} & \small{3} \\ | ||

2719 | \hline | ||

2720 | \small{3} & \small{2} & \small{1} & \small{2} & \small{0} & \small{5} & \small{7} \\ | ||

2721 | \hline | ||

2722 | \end{tabular} | ||

2723 | \end{center} | ||

2724 | \end{table} | ||

2725 | |||

2726 | Since the final convergent, $s_{3}$, is an odd-ordered convergent, $s_{k-1} < s_k$, and | ||

2727 | (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01}) will supply the left Farey neighbor | ||

2728 | of 5/7. Applying (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01}) with | ||

2729 | $N=1,000,000$, $k=3$, $k-1=2$, $p_k = 5$, $q_k = 7$, $p_{k-1}=2$, and $q_{k-1}=3$ | ||

2730 | yields $\frac{714,282}{999,995}$ as the left Farey neighbor of 5/7 in $F_{1,000,000}$. | ||

2731 | Application of (\cfryzeroxrefhyphen{}\ref{eq:cfry0:sgfs0:thm:01:eq01}) | ||

2732 | and (\cfryzeroxrefhyphen{}\ref{eq:cfry0:sgfs0:thm:01:eq02}) | ||

2733 | yields $\frac{714,283}{999,996}$ as the right Farey neighbor. | ||

2734 | \end{vworkexampleparsection} | ||

2735 | %\vworkexamplefooter{} | ||

2736 | |||

2737 | |||

2738 | \begin{vworkalgorithmstatementpar}{Neighbors Of | ||

2739 | \mbox{\boldmath $x \in F_{k_{MAX},\overline{h_{MAX}}}$} | ||

2740 | In \mbox{\boldmath $F_{k_{MAX},\overline{h_{MAX}}}$}} | ||

2741 | \label{alg:ccfr0:scba0:cffareyneighborfab} | ||

2742 | \begin{alglvl0} | ||

2743 | \item If $a/b < h_{MAX}/k_{MAX}$, apply Algorithm | ||

2744 | \ref{alg:ccfr0:scba0:cffareyneighborfn} directly; | ||

2745 | |||

2746 | \item Else if $a/b > h_{MAX}/k_{MAX}$, apply Algorithm | ||

2747 | \ref{alg:ccfr0:scba0:cffareyneighborfn} using $b/a$ rather | ||

2748 | than $a/b$ as the input to the algorithm, using $h_{MAX}$ | ||

2749 | rather than $k_{MAX}$ as $N$, and | ||

2750 | using the reciprocals of the results of the algorithm.\footnote{The | ||

2751 | basis for taking the reciprocals of input and output and | ||

2752 | using $h_{MAX}$ rather than $k_{MAX}$ are explained | ||

2753 | in \cfryzeroxrefcomma{}Section \ref{cfry0:schk0}.} | ||

2754 | \end{alglvl0} | ||

2755 | \end{vworkalgorithmstatementpar} | ||

2756 | \vworkalgorithmfooter{} | ||

2757 | |||

2758 | |||

2759 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

2760 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

2761 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

2762 | \section{The Stern-Brocot Tree} | ||

2763 | %Section tag: SBT0 | ||

2764 | \label{ccfr0:ssbt0} | ||

2765 | |||

2766 | In this chapter, we've developed continued fraction techniques of best | ||

2767 | rational approximation without reference to any other models or theory. | ||

2768 | Because the algorithms presented in this chapter are $O(log \; N)$, | ||

2769 | the results so far are completely satisfactory and usable in practice. | ||

2770 | It is not necessary to go further or to present additional information. | ||

2771 | |||

2772 | However, there is a second model of best rational approximation (and a second | ||

2773 | set of algorithms), involving | ||

2774 | the Stern-Brocot tree. In fact, when reviewing the material in this | ||

2775 | chapter, some readers have inquired why the Stern-Brocot tree was not | ||

2776 | used.\footnote{In brief, the Stern-Brocot tree was not used because | ||

2777 | the resulting algorithms are $O(N)$, and so will introduce practical | ||

2778 | computational difficulties when used with large integers.} In this | ||

2779 | section, we introduce the Stern-Brocot tree, demonstrate how to construct it, | ||

2780 | mention its major properties, show its correspondence with the apparatus of | ||

2781 | continued fractions, and finally show why we \emph{must} use the apparatus | ||

2782 | of continued fractions to find best rational approximations. | ||

2783 | |||

2784 | |||

2785 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

2786 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

2787 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

2788 | \subsection{Definition And Properties Of The Stern-Brocot Tree} | ||

2789 | %Section tag: DPT0 | ||

2790 | \label{ccfr0:ssbt0:sdpt0} | ||

2791 | |||

2792 | \index{Stern-Brocot tree}The Stern-Brocot tree | ||

2793 | (Figure \ref{fig:ccfr0:ssbt0:sdpt0:00}), is | ||

2794 | an infinite binary tree which contains all positive rational numbers. | ||

2795 | |||

2796 | \begin{figure} | ||

2797 | \centering | ||

2798 | \includegraphics[width=4.6in]{c_cfr0/sbtdpt01.eps} | ||

2799 | \caption{The Stern-Brocot Tree} | ||

2800 | \label{fig:ccfr0:ssbt0:sdpt0:00} | ||

2801 | \end{figure} | ||

2802 | |||

2803 | To construct the tree, one begins with the two fractions $\frac{0}{1}$ | ||

2804 | and $\frac{1}{0}$, and forms the mediant (see Definition | ||

2805 | \cfryzeroxrefhyphen{}\ref{def:cfry0:spfs:02}) | ||

2806 | of two adjacent fractions as many | ||

2807 | times as desired to generate additional fractions. | ||

2808 | Figure \ref{fig:ccfr0:ssbt0:sdpt0:00} illustrates the construction process. | ||

2809 | Note in Figure \ref{fig:ccfr0:ssbt0:sdpt0:00} that the adjacent fractions | ||

2810 | are always above and to the left and above and to the right of the fraction | ||

2811 | being constructed, and that in the construction of the Stern-Brocot | ||

2812 | tree, one of the adjacent fractions can be many levels upwards in the tree | ||

2813 | from the fraction being constructed. For example, in | ||

2814 | Figure \ref{fig:ccfr0:ssbt0:sdpt0:00}, when constructing the fraction | ||

2815 | 4/5, the left adjacent fraction (3/4) is nearby in the figure, but | ||

2816 | the right adjacent fraction (1/1) is three levels up to the left and | ||

2817 | one level up to the right. Note when constructing the fraction 4/5 that | ||

2818 | its right adjacent fraction is \emph{not} 4/3. | ||

2819 | |||

2820 | Note that it is also possible to maintain the Stern-Brocot tree as an | ||

2821 | ordered list, rather than a tree, starting with the list | ||

2822 | $\{0/1, 1/0\}$. An additional element may be inserted | ||

2823 | between any two existing elements in the list by forming their mediant, | ||

2824 | and this process may be repeated indefinitely. Note also that two | ||

2825 | elements $s_L$ and $s_R$ are Farey neighbors to any number $\alpha$ | ||

2826 | if $s_L < \alpha < s_R$ and the mediant of $s_L$ and $s_R$ has a | ||

2827 | denominator larger than the order of the Farey series. This gives a convenient | ||

2828 | procedure for forming best rational approximations using only the Stern-Brocot | ||

2829 | tree, as the following example shows. | ||

2830 | |||

2831 | \begin{vworkexamplestatement} | ||

2832 | \label{ex:ccfr0:ssbt0:sdpt0:01} | ||

2833 | Find the members of $F_{10}$ which enclose $\pi$. | ||

2834 | \end{vworkexamplestatement} | ||

2835 | \begin{vworkexampleparsection}{Solution} | ||

2836 | By repeatedly calculating mediants, terms can be added to the list | ||

2837 | $\{\frac{0}{1}, \frac{1}{0} \}$ until $\pi$ is enclosed and it is not | ||

2838 | possible to generate additional enclosing terms whose denominator does not | ||

2839 | exceed 10. This process is carried out below. | ||

2840 | |||

2841 | \begin{equation} | ||

2842 | \left\{ {\frac{0}{1}, \frac{1}{0} } \right\}, | ||

2843 | \left\{ {\frac{0}{1}, \frac{1}{1}, \frac{1}{0} } \right\}, | ||

2844 | \left\{ {\frac{0}{1}, \frac{1}{1}, \frac{2}{1}, \frac{1}{0} } \right\}, | ||

2845 | \left\{ {\frac{0}{1}, \frac{1}{1}, \frac{2}{1}, \frac{3}{1}, \frac{1}{0} } \right\}, | ||

2846 | \end{equation} | ||

2847 | |||

2848 | \begin{equation} | ||

2849 | \left\{ {\frac{0}{1}, \frac{1}{1}, \frac{2}{1}, \frac{3}{1}, | ||

2850 | \frac{4}{1}, \frac{1}{0} } \right\}, | ||

2851 | \left\{ {\frac{0}{1}, \frac{1}{1}, \frac{2}{1}, \frac{3}{1}, \frac{7}{2}, | ||

2852 | \frac{4}{1}, \frac{1}{0} } \right\}, | ||

2853 | \left\{ {\frac{0}{1}, \frac{1}{1}, \frac{2}{1}, \frac{3}{1}, \frac{10}{3}, \frac{7}{2}, | ||

2854 | \frac{4}{1}, \frac{1}{0} } \right\}, | ||

2855 | \end{equation} | ||

2856 | |||

2857 | \begin{equation} | ||

2858 | \left\{ {\frac{0}{1}, \frac{1}{1}, \frac{2}{1}, | ||

2859 | \frac{3}{1}, \frac{13}{4}, \frac{10}{3}, \frac{7}{2}, | ||

2860 | \frac{4}{1}, \frac{1}{0} } \right\}, | ||

2861 | \left\{ {\frac{0}{1}, \frac{1}{1}, \frac{2}{1}, | ||

2862 | \frac{3}{1}, \frac{16}{5}, \frac{13}{4}, \frac{10}{3}, \frac{7}{2}, | ||

2863 | \frac{4}{1}, \frac{1}{0} } \right\}, | ||

2864 | \end{equation} | ||

2865 | |||

2866 | \begin{equation} | ||

2867 | \left\{ {\frac{0}{1}, \frac{1}{1}, \frac{2}{1}, | ||

2868 | \frac{3}{1}, \frac{19}{6}, \frac{16}{5}, \frac{13}{4}, \frac{10}{3}, \frac{7}{2}, | ||

2869 | \frac{4}{1}, \frac{1}{0} } \right\}, | ||

2870 | \end{equation} | ||

2871 | |||

2872 | \begin{equation} | ||

2873 | \left\{ {\frac{0}{1}, \frac{1}{1}, \frac{2}{1}, | ||

2874 | \frac{3}{1}, \frac{22}{7}, \frac{19}{6}, | ||

2875 | \frac{16}{5}, \frac{13}{4}, \frac{10}{3}, \frac{7}{2}, | ||

2876 | \frac{4}{1}, \frac{1}{0} } \right\}, | ||

2877 | \end{equation} | ||

2878 | |||

2879 | \begin{equation} | ||

2880 | \left\{ {\frac{0}{1}, \frac{1}{1}, \frac{2}{1}, | ||

2881 | \frac{3}{1}, \frac{25}{8}, \frac{22}{7}, \frac{19}{6}, | ||

2882 | \frac{16}{5}, \frac{13}{4}, \frac{10}{3}, \frac{7}{2}, | ||

2883 | \frac{4}{1}, \frac{1}{0} } \right\}. | ||

2884 | \end{equation} | ||

2885 | |||

2886 | Note that 25/8 and 22/7 are the left and right neighbors to | ||

2887 | $\pi$ in $F_{10}$, since $25/8 < \pi < 22/7$, and since the | ||

2888 | mediant of 25/8 and 22/7 (49/15) has a denominator which is | ||

2889 | too large for the Farey series being considered. | ||

2890 | |||

2891 | Note also that the construction process above could be | ||

2892 | trivially amended to treat the case of a constrained numerator | ||

2893 | rather than a constrained denominator. | ||

2894 | \end{vworkexampleparsection} | ||

2895 | \vworkexamplefooter{} | ||

2896 | |||

2897 | The Stern-Brocot tree has many remarkable properties (especially in view of the | ||

2898 | simplicity of its construction). We mention the following properties | ||

2899 | without proof. | ||

2900 | |||

2901 | \begin{itemize} | ||

2902 | \item Each rational number in the tree is irreducible. | ||

2903 | |||

2904 | \item Each rational number appears in the tree only once. | ||

2905 | |||

2906 | \item Every positive rational number appears in the tree (i.e. there are no rational | ||

2907 | numbers absent). | ||

2908 | \end{itemize} | ||

2909 | |||

2910 | A more detailed discussion of the Stern-Brocot tree and proof of its | ||

2911 | properties is provided | ||

2912 | in \cite{bibref:b:concretemathematics}, pp. 116-123. | ||

2913 | |||

2914 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

2915 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

2916 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

2917 | \subsection{The Correspondence Between The Stern-Brocot Tree And The | ||

2918 | Apparatus Of Continued Fractions} | ||

2919 | %Section tag: DPT0 | ||

2920 | \label{ccfr0:ssbt0:sdpt1} | ||

2921 | |||

2922 | The Stern-Brocot tree, on examination, bears a clear resemblence to | ||

2923 | the apparatus of continued fractions. For example, in examining | ||

2924 | Figure \ref{fig:ccfr0:ssbt0:sdpt0:00} and following leftmost branches in | ||

2925 | the tree, the rational numbers 1/2, 1/3, 1/4, and 1/5 correspond respectively | ||

2926 | to the continued fractions [0;2], [0;3], [0;4], and [0;5]. Similarly, | ||

2927 | following | ||

2928 | the right branches down from 1/2 yields, in order, [0;1,2], [0;1,3], and | ||

2929 | [0;1,4]. Clearly, a relationship between the Stern-Brocot tree and the | ||

2930 | apparatus of continued fractions may exist. | ||

2931 | |||

2932 | Suspicions of a simple relationship may also arise by noting that the | ||

2933 | way in which the Stern-Brocot tree is constructed when only left branches | ||

2934 | or only right branches are pursued is of the same form as the rule for | ||

2935 | the formation of continued fraction convergents (Eqns. | ||

2936 | \ref{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:01} | ||

2937 | and \ref{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:02}). For example, | ||

2938 | the $n$th successor to the right of 1/3 has the form | ||

2939 | |||

2940 | \begin{equation} | ||

2941 | \label{eq:ccfr0:ssbt0:sdpt1:01} | ||

2942 | \frac{n + 1}{2n+3}, | ||

2943 | \end{equation} | ||

2944 | |||

2945 | \noindent{}which is suspiciously similar to | ||

2946 | (\ref{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:01}) and | ||

2947 | (\ref{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:02}). | ||

2948 | |||

2949 | There is, in fact, an intimate relationship between the Stern-Brocot | ||

2950 | tree and the apparatus of continued fractions. We present | ||

2951 | this relationship as | ||

2952 | Lemma \ref{lem:ccfr0:ssbt0:sdpt1:sbtcfcorrespondence}, | ||

2953 | below. | ||

2954 | |||

2955 | \begin{vworklemmastatement} | ||

2956 | \label{lem:ccfr0:ssbt0:sdpt1:sbtcfcorrespondence} | ||

2957 | Let $R^{z_0}L^{z_1} \ldots{} L^{z_{j-2}} R^{z_{j-1}} L^{z_{j}}$ | ||

2958 | or $R^{z_0}L^{z_1} \ldots{} R^{z_{j-2}} L^{z_{j-1}} R^{z_{j}}$ | ||

2959 | (depending on whether the final leg of the path is towards the | ||

2960 | left or towards the right, respectively) be the path in the | ||

2961 | Stern-Brocot tree from the fraction 1/1 to the fraction $a/b$, where | ||

2962 | $L^N$ denotes traveling downward and to the left in the tree | ||

2963 | $N$ nodes, and $R^N$ denotes traveling downward and to the right | ||

2964 | in the tree $N$ nodes. Then the continued fraction representation | ||

2965 | of $a/b$ is $[z_0; z_1, \ldots{}, z_{j-2}, z_{j-1}, z_j + 1]$. | ||

2966 | \end{vworklemmastatement} | ||

2967 | \begin{vworklemmaproof} | ||

2968 | The proof is inductive. First note that the constraints of the path | ||

2969 | require that $z_0 \geq 0$, and that $z_k \geq 1$, $k > 0$. In other | ||

2970 | words, only the first rightward leg of the path can have zero steps. | ||

2971 | |||

2972 | If the path is $R^{z_0}$, $z_0 = 0$, then the lemma predicts that the continued fraction | ||

2973 | representation will be $[z_0 + 1]$ = $[1]$, which is the correct continued | ||

2974 | fraction representation of the fraction 1/1. Note that the rational number | ||

2975 | 1/1 has no ancestor in the tree. | ||

2976 | |||

2977 | If the path is $R^{z_0}$, $z_0 \neq 0$, then the lemma predicts that the | ||

2978 | continued fraction representation will be $[z_0 + 1]$, which is correct | ||

2979 | on inspection since the most rightward path in the Stern-Brocot tree | ||

2980 | traverses the non-negative integers. Note that the immediate ancestor of | ||

2981 | the fraction $[z_0 + 1]$ is $[z_0]$. | ||

2982 | |||

2983 | If the path is $R^{z_0}, L^{z_1}$, $z_0 = 0$, then the | ||

2984 | fraction $a/b$ will be the weighted mediant of | ||

2985 | 1/1 and 0/1, | ||

2986 | |||

2987 | \begin{equation} | ||

2988 | \label{eq:ccfr0:ssbt0:sdpt1:02} | ||

2989 | \frac{1}{z_1 + 1} | ||

2990 | = | ||

2991 | [0; z_1 + 1], | ||

2992 | \end{equation} | ||

2993 | |||

2994 | \noindent{}which argrees with the lemma. Note that the | ||

2995 | immediate ancestor ancestor of $[0; z_1 + 1]$ in the | ||

2996 | tree is $[0; z_1]$. | ||

2997 | |||

2998 | If the path is $R^{z_0}, L^{z_1}$, $z_0 \neq 0$, then the | ||

2999 | fraction $a/b$ will be the weighted mediant of | ||

3000 | $(z_0 + 1)/1$ and $z_0/1$, i.e. | ||

3001 | |||

3002 | \begin{equation} | ||

3003 | \label{eq:ccfr0:ssbt0:sdpt1:03} | ||

3004 | \frac{(z_0 + 1) + (z_0 z_1)}{(1) + (z_1)} | ||

3005 | = z_0 + \frac{1}{z_1 + 1} | ||

3006 | = [z_0; z_1 + 1], | ||

3007 | \end{equation} | ||

3008 | |||

3009 | \noindent{}which is consistent with the lemma. Note also that | ||

3010 | the immediate ancestor of the rational number specified by | ||

3011 | (\ref{eq:ccfr0:ssbt0:sdpt1:03}) is | ||

3012 | |||

3013 | \begin{equation} | ||

3014 | \label{eq:ccfr0:ssbt0:sdpt1:03b} | ||

3015 | \frac{(z_0 + 1) + z_0 (z_1 - 1)}{(1) + (z_1 - 1)} | ||

3016 | = z_0 + \frac{1}{z_1} | ||

3017 | = [z_0; z_1]. | ||

3018 | \end{equation} | ||

3019 | |||

3020 | The cases with two or fewer path components have been | ||

3021 | proved above. It remains to prove all cases with three | ||

3022 | or more path components. | ||

3023 | |||

3024 | Let $s_k = p_k/q_k$ denote the $k$th-ordered convergent | ||

3025 | of the continued fraction $[z_0; z_1, \ldots{}, z_{j-1}, z_j]$ | ||

3026 | (note that the final partial quotient is \emph{not} adjusted upwards by one). | ||

3027 | For $k \geq 2$, we can establish a relationship between | ||

3028 | $[z_0; z_1, \ldots{}, z_{k-1}, z_k]$ | ||

3029 | and | ||

3030 | $[z_0; z_1, \ldots{}, z_{k-1}, z_k + 1]$ | ||

3031 | as follows: | ||

3032 | |||

3033 | \begin{equation} | ||

3034 | \label{eq:ccfr0:ssbt0:sdpt1:04} | ||

3035 | [z_0; z_1, z_2, \ldots{}, z_{k-2}, z_{k-1}, z_k + 1] | ||

3036 | = | ||

3037 | \frac{(z_k + 1)p_{k-1} + p_{k-2}}{(z_k + 1)q_{k-1} + q_{k-2}} | ||

3038 | = | ||

3039 | \frac{p_k + p_{k-1}}{q_k + q_{k-1}}. | ||

3040 | \end{equation} | ||

3041 | |||

3042 | If we agree for convenience, as was mentioned in | ||

3043 | Section \ref{ccfr0:scnf0}, that we will define $s_{-1} = p_{-1}/q_{-1} = 1/0$, | ||

3044 | then (\ref{eq:ccfr0:ssbt0:sdpt1:04}) holds for $k \geq 1$. | ||

3045 | |||

3046 | \textbf{(Inductive Step):} Assume that the lemma holds | ||

3047 | up through $k-1$. For a path in the Stern-Brocot tree | ||

3048 | $R^{z_0}L^{z_1} \ldots{} L^{z_{k-2}} R^{z_{k-1}} L^{z_{k}}$ | ||

3049 | or $R^{z_0}L^{z_1} \ldots{} R^{z_{k-2}} L^{z_{k-1}} R^{z_{k}}$, | ||

3050 | $k \geq 2$, the ``reversal'' fraction above (i.e. the fraction where the path changes | ||

3051 | directions) is | ||

3052 | |||

3053 | \begin{equation} | ||

3054 | \label{eq:ccfr0:ssbt0:sdpt1:05} | ||

3055 | [z_0; \ldots{}, z_{k-2}, z_{k-1} + 1] = | ||

3056 | \frac{p_{k-1} + p_{k-2}}{q_{k-1} + q_{k-2}} | ||

3057 | \end{equation} | ||

3058 | |||

3059 | \noindent{}(this is established by the lemma on the path through $k-1$ and by | ||

3060 | Eqn. \ref{eq:ccfr0:ssbt0:sdpt1:04}). | ||

3061 | |||

3062 | The immediate ancestor of the fraction specified in | ||

3063 | (\ref{eq:ccfr0:ssbt0:sdpt1:05}) is | ||

3064 | |||

3065 | \begin{equation} | ||

3066 | \label{eq:ccfr0:ssbt0:sdpt1:06} | ||

3067 | [z_0; \ldots{}, z_{k-2}, z_{k-1}] = | ||

3068 | \frac{z_{k-1}p_{k-2} + p_{k-3}}{z_{k-1}q_{k-2} + q_{k-3}} , | ||

3069 | \end{equation} | ||

3070 | |||

3071 | \noindent{}as was shown to hold in (\ref{eq:ccfr0:ssbt0:sdpt1:03b}) and | ||

3072 | in the inductive step. | ||

3073 | |||

3074 | The rational number corresponding to the path | ||

3075 | $R^{z_0}L^{z_1} \ldots{} L^{z_{k-2}} R^{z_{k-1}} L^{z_{k}}$ | ||

3076 | or $R^{z_0}L^{z_1} \ldots{} R^{z_{k-2}} L^{z_{k-1}} R^{z_{k}}$ | ||

3077 | is a weighted mediant of (\ref{eq:ccfr0:ssbt0:sdpt1:05}) | ||

3078 | and (\ref{eq:ccfr0:ssbt0:sdpt1:06}): | ||

3079 | |||

3080 | \begin{eqnarray} | ||

3081 | \label{eq:ccfr0:ssbt0:sdpt1:07} | ||

3082 | \hspace{-0.35in} | ||

3083 | \frac{z_k(z_{k-1}p_{k-2} + p_{k-3}) + p_{k-1} + p_{k-2}} | ||

3084 | {z_k(z_{k-1}q_{k-2} + q_{k-3}) + q_{k-1} + q_{k-2}} | ||

3085 | & = & | ||

3086 | \frac{(z_k + 1)p_{k-1} + p_{k-2}}{(z_k + 1)q_{k-1} + q_{k-2}} \\ | ||

3087 | \label{eq:ccfr0:ssbt0:sdpt1:08} | ||

3088 | & = & \frac{p_k + p_{k-1}}{q_k + q_{k-1}} \\ | ||

3089 | & = & [z_0; z_1, \ldots{}, z_{k-1}, z_{k} + 1], | ||

3090 | \end{eqnarray} | ||

3091 | |||

3092 | \noindent{}which establishes the main result of the lemma in the | ||

3093 | inductive step. Note also that the immediate ancestor of the | ||

3094 | fraction specified in (\ref{eq:ccfr0:ssbt0:sdpt1:07}) is | ||

3095 | $[z_0; \ldots{}, z_{k-1}, z_{k}]$ (which is necessary for | ||

3096 | the inductive step). This proves the lemma. | ||

3097 | \end{vworklemmaproof} | ||

3098 | \begin{vworklemmaparsection}{Remarks} | ||

3099 | This lemma provides a straightforward method to go from a | ||

3100 | fraction's position in the Stern-Brocot tree to its continued | ||

3101 | fraction representation, or vice-versa. | ||

3102 | |||

3103 | To go from a fraction's position in the Stern-Brocot tree to its | ||

3104 | continued fraction representation: | ||

3105 | |||

3106 | \begin{itemize} | ||

3107 | \item Starting with moves downward and to the right from the | ||

3108 | fraction 1/1 ($z_0$), observe the length of the alternating | ||

3109 | rightward and leftward node traversals required to reach | ||

3110 | the desired fraction. | ||

3111 | |||

3112 | \item Adjust the final length upward by one. | ||

3113 | |||

3114 | \item These lengths in order are then the successive partial quotients | ||

3115 | of the fraction. | ||

3116 | \end{itemize} | ||

3117 | |||

3118 | To go from the continued fraction representation of a fraction | ||

3119 | to its position in the Stern-Brocot tree: | ||

3120 | |||

3121 | \begin{itemize} | ||

3122 | \item Reduce the final partial quotient by one. | ||

3123 | |||

3124 | \item Use the partial quotients, in order, in an alternating fashion, | ||

3125 | to go rightward and downward | ||

3126 | and leftward and downward in the Stern-Brocot tree. The fraction | ||

3127 | reached on the final leg will be the fraction of interest. | ||

3128 | \end{itemize} | ||

3129 | \end{vworklemmaparsection} | ||

3130 | \vworklemmafooter{} | ||

3131 | |||

3132 | It is clear from the lemma above that the Stern-Brocot tree and the | ||

3133 | apparatus of continued fractions are intimately related. Specifically, | ||

3134 | the Stern-Brocot tree provides a model for the formation and arrangement | ||

3135 | of rational numbers, but the apparatus of continued fractions provides | ||

3136 | a much more efficient way to navigate the Stern-Brocot tree and to find | ||

3137 | best rational approximations. | ||

3138 | |||

3139 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

3140 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

3141 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

3142 | \subsection{Using The Stern-Brocot Tree To Find Best Rational Approximations} | ||

3143 | %Section tag: USB0 | ||

3144 | \label{ccfr0:ssbt0:susb0} | ||

3145 | |||

3146 | It is clear from Example \ref{ex:ccfr0:ssbt0:sdpt0:01} that the Stern-Brocot | ||

3147 | tree can be used to find best rational approximations in the Farey series | ||

3148 | of any order, simply by forming mediants until the number of interest | ||

3149 | is enclosed. It is also clear that an algorithm of repeatedly forming | ||

3150 | mediants in order to find a best rational approximation in | ||

3151 | $F_{k_{MAX}, \overline{h_{MAX}}}$ can be devised. | ||

3152 | |||

3153 | However, the sole drawback of such a procedure is that building the Stern-Brocot | ||

3154 | tree from the top in order to find neighbors in $F_N$ is an | ||

3155 | $O(N)$ procedure, which renders it unsuitable for use with large | ||

3156 | $N$. For this reason, the continued fraction algorithms presented | ||

3157 | earlier in the chapter, which are $O(log \; N)$ (due to the | ||

3158 | guaranteed minimum exponential rate of increase of convergent | ||

3159 | denominators, Theorem \ref{thm:ccfr0:scnv0:minimumrateofconvergentdenominatorincrease}), | ||

3160 | are the only practical algorithms. | ||

3161 | |||

3162 | |||

3163 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

3164 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

3165 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

3166 | \section{Practical Techniques} | ||

3167 | %Section tag: PTQ0 | ||

3168 | |||

3169 | Although this chapter has presented rather theoretical results and techniques | ||

3170 | from number theory, our emphasis is on practical applications (which is why | ||

3171 | we've concentrated on finding Farey neighbors of \emph{rational} numbers). | ||

3172 | Practicing engineers would be more likely to use the digits from a calculator | ||

3173 | as the starting point to obtain a rational approximation than to use | ||

3174 | a symbolic irrational constant, such as $\pi$. | ||

3175 | |||

3176 | In this section, we present \emph{practical} techniques---those most likely | ||

3177 | to be used in practice by microcontroller software developers. | ||

3178 | |||

3179 | |||

3180 | |||

3181 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

3182 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

3183 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

3184 | \subsection{Practical Aspects Of Beginning With A Rational Approximation} | ||

3185 | %Subsection tag: PAS0 | ||

3186 | \label{ccfr0:sptq0:sspas0} | ||

3187 | |||

3188 | In practical applications, one often begins with a rational approximation | ||

3189 | to a irrational number. | ||

3190 | For example, one might use 3.14159265359 (from | ||

3191 | a calculator) as the value of $\pi$ for the application of | ||

3192 | Algorithm \ref{alg:ccfr0:scrn0:akgenalg}. This naturally raises the | ||

3193 | question of how accurate the rational approximation used | ||

3194 | as a starting point must be to avoid identifying the wrong | ||

3195 | rational numbers as Farey neighbors. We illustrate the possibility | ||

3196 | of identifying the wrong rational number with an example. | ||

3197 | |||

3198 | \begin{vworkexamplestatement} | ||

3199 | \label{ex:ccfr0:sptq0:01} | ||

3200 | Find the members of $F_{255}$ which enclose $\pi$, using | ||

3201 | 3.1416 as the value of $\pi$. | ||

3202 | \end{vworkexamplestatement} | ||

3203 | \begin{vworkexampleparsection}{[Erroneous] Solution And Remarks} | ||

3204 | It can be shown using the methods presented earlier that | ||

3205 | the members of $F_{255}$ which enclose 3.1416 are | ||

3206 | 355/113 and 732/333, i.e. | ||

3207 | |||

3208 | \begin{equation} | ||

3209 | \frac{355}{113} < 3.1416 < \frac{732}{333} . | ||

3210 | \end{equation} | ||

3211 | |||

3212 | However, in fact, 688/219 and 355/113 are the actual enclosing | ||

3213 | neighbors of $\pi$ in $F_{255}$: | ||

3214 | |||

3215 | \begin{equation} | ||

3216 | \frac{688}{219} < \pi < \frac{355}{113} < 3.1416 < \frac{732}{333} . | ||

3217 | \end{equation} | ||

3218 | |||

3219 | Thus by using an imprecise approximation of $\pi$, we have incorrectly | ||

3220 | identified the neighbors to $\pi$ in $F_{255}$. | ||

3221 | \end{vworkexampleparsection} | ||

3222 | \vworkexamplefooter{} | ||

3223 | |||

3224 | How do we avoid incorrectly identifying the rational | ||

3225 | numbers which enclose an irrational number when a | ||

3226 | rational approximation of the irrational number is | ||

3227 | used as the starting point for the selection algorithm? | ||

3228 | There are three practical approaches to the problem. | ||

3229 | |||

3230 | Observe that when we know | ||

3231 | the first several decimal digits of an irrational number, | ||

3232 | the actual value of the irrational number is confined | ||

3233 | to an interval. For example, if a calculator displays | ||

3234 | ``3.1416'' as the value of $\pi$, we might safely | ||

3235 | assume that $3.14155 \leq \pi \leq 3.14165$, if the | ||

3236 | digits that the calculator displays were | ||

3237 | obtained by rounding. | ||

3238 | |||

3239 | As a first approach to dealing with a rational approximation | ||

3240 | to an irrational number, | ||

3241 | we might simply determine the | ||

3242 | Farey neighbors of both endpoints of the interval of | ||

3243 | uncertainty. For example, if | ||

3244 | 314,155/100,000 and 314,165/100,000 have the same | ||

3245 | Farey neighbors in a Farey series of interest (which we can | ||

3246 | easily determine using the algorithms presented earlier | ||

3247 | in this chapter), we could | ||

3248 | correctly deduce that these Farey neighbors are the | ||

3249 | Farey neighbors of $\pi$. On the other hand, | ||

3250 | if 314,155/100,000 and 314,165/100,000 have different | ||

3251 | enclosing Farey neighbors, then there are Farey | ||

3252 | terms in the interval [3.14155, 3.14165], | ||

3253 | and more information about $\pi$ | ||

3254 | would be required to determine its true Farey neighbors. | ||

3255 | |||

3256 | A second approach to this same problem would be to devise an | ||

3257 | algorithm to process | ||

3258 | the endpoints of the interval of uncertainty simultaneously and note | ||

3259 | when their partial quotients diverge. | ||

3260 | |||

3261 | A third approach, which is | ||

3262 | perhaps the most direct, is to apply | ||

3263 | Algorithm \cfryzeroxrefhyphen{}\ref{alg:cfmindenominator} to determine | ||

3264 | the rational number with the minimum denominator in the interval of uncertainty. | ||

3265 | We would thus know that we have enough information to determine uniquely the | ||

3266 | enclosing rational numbers in any Farey series up to one less than this | ||

3267 | minimum denominator. | ||

3268 | |||

3269 | \begin{vworkexamplestatement} | ||

3270 | \label{ex:ccfr0:sptq0:02} | ||

3271 | Assume that 3.142 is the only value for $\pi$ available. What is the maximum | ||

3272 | order of the Farey series where the enclosing rational numbers to $\pi$ can | ||

3273 | be unambiguously determined? | ||

3274 | \end{vworkexamplestatement} | ||

3275 | \begin{vworkexampleparsection}{Solution} | ||

3276 | Assume that the constant ``3.142'' was obtained by rounding of digits, rather than | ||

3277 | by truncation of digits: thus $3.1415 \leq \pi \leq 3.1425$. Applying | ||

3278 | Algorithm \cfryzeroxrefhyphen{}\ref{alg:cfmindenominator} yields 333/106 | ||

3279 | as the rational number with the smallest denominator in the interval | ||

3280 | [3.1415, 3.1425]. Thus, no rational number with a smaller denominator exists | ||

3281 | in the interval, and the enclosing rational numbers of $\pi$ in the Farey series of | ||

3282 | up to order 105 can be determined with the limited information available. | ||

3283 | \end{vworkexampleparsection} | ||

3284 | \vworkexamplefooter{} | ||

3285 | |||

3286 | |||

3287 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

3288 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

3289 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

3290 | \subsection{Obtaining Irrational Numbers To High Precision} | ||

3291 | %Subsection tag: OIN0 | ||

3292 | \label{ccfr0:sptq0:ssoin0} | ||

3293 | |||

3294 | It may happen in practice that one desires more information about an | ||

3295 | irrational number than can be easily obtained. As a practical example, | ||

3296 | a typical scientific calculator treats $\pi$ as 3.14159265359, implying that | ||

3297 | $3.141592653585 \leq \pi \leq 3.141592653595$. Application of | ||

3298 | Algorithm \cfryzeroxrefhyphen{}\ref{alg:cfmindenominator} to this | ||

3299 | interval yields 1,146,408/364,913 as the rational number with the | ||

3300 | smallest denominator in this interval: implying that we cannot determine the | ||

3301 | enclosing rational approximations to $\pi$ even in $F_{2^{32}-1}$ using | ||

3302 | the information most readily available. How do we obtain more digits of $\pi$? | ||

3303 | And even if we can obtain more digits of $\pi$, how do we manipulate rational | ||

3304 | numbers with such large integer components? (We discuss the problem of obtaining | ||

3305 | more digits below, but discuss manipulation in Section \ref{ccfr0:sptq0:smhp0}.) | ||

3306 | |||

3307 | There are two approaches to determining $\pi$ or other numbers to | ||

3308 | high precision. | ||

3309 | |||

3310 | \begin{enumerate} | ||

3311 | |||

3312 | \item Locate information about the number on the Web or in a reference | ||

3313 | book. (Note that decimal digits of the number, partial quotients | ||

3314 | of the number, or convergents of the number can all be used; and it | ||

3315 | is typical for all of these to be somewhere on the Web. However, | ||

3316 | convergents are the most useful form for obtaining best rational | ||

3317 | approximations.) | ||

3318 | |||

3319 | \item Use commercial symbolic manipulation software (\index{Mathematica@\emph{Mathematica}}\emph{Mathematica} | ||

3320 | \cite{bibref:s:wolframmathematica}, | ||

3321 | for example) to | ||

3322 | obtain the number of interest to arbitrary | ||

3323 | precison.\footnote{\label{footnote:ccfr0:sptq0:ssoin0:mathematicaexpensive}\emph{Mathematica} | ||

3324 | \cite{bibref:s:wolframmathematica} is quite expensive (version 4.1 | ||

3325 | for Windows, as of March 2001, is \$1,495), | ||

3326 | and something that a microcontroller software developer | ||

3327 | would very rarely use, so we assume that most microcontroller software | ||

3328 | developers would search for a less expensive solution.} | ||

3329 | |||

3330 | \end{enumerate} | ||

3331 | |||

3332 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

3333 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

3334 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

3335 | \subsection{Manipulating High-Precision Rational Numbers} | ||

3336 | %Subsection tag: MHP0 | ||

3337 | \label{ccfr0:sptq0:smhp0} | ||

3338 | |||

3339 | Assuming that one is able to determine a [rational or irrational] number | ||

3340 | of interest to high-precision (either a large number of decimal digits or a rational | ||

3341 | number with large integer components), how does | ||

3342 | one manipulate rational numbers with large integer components? | ||

3343 | In this section, we list software alternatives. | ||

3344 | |||

3345 | The first alternative we should mention is \emph{The Iju Tool Set}, distributed | ||

3346 | with this book. Starting with version 1.05, this tool set contains | ||

3347 | a subset of the GNU MP Library \cite{bibref:s:gnumultipleprecisionarithmeticlibrary}, | ||

3348 | and will manipulate | ||

3349 | large integers and rational numbers with large integer components. To provide | ||

3350 | more flexibility for the user, this tool set is embedded as extensions to | ||

3351 | the Tcl scripting language; so that any of the functionality provided can be | ||

3352 | used either interactively or from within a Tcl script. | ||

3353 | |||

3354 | \begin{figure} | ||

3355 | \centering | ||

3356 | \includegraphics[width=4.6in]{c_cfr0/ijt_ss01.eps} | ||

3357 | \caption{Large Integer Arithmetic And Best Rational Approximations Using \emph{IjuConsole} | ||

3358 | From \emph{The Iju Tool Set}} | ||

3359 | \label{fig:ccfr0:sptq0:smhp0:00} | ||

3360 | \end{figure} | ||

3361 | |||

3362 | Figure \ref{fig:ccfr0:sptq0:smhp0:00} shows a screen snapshot\footnote{By | ||

3363 | the way, \emph{IjuConsole} will handle \emph{much} larger integers, but | ||

3364 | small examples were used so that all of the information would fit | ||

3365 | in a single screen snapshot.} of | ||

3366 | \emph{IjuConsole} (the \emph{Wish}-like Tcl | ||

3367 | interpreter from \emph{The Iju Tool Set}) being used interactively | ||

3368 | to provide the answers to several questions involving large integers and | ||

3369 | rational numbers with large integer components. The first command | ||

3370 | shown,\\ | ||

3371 | |||

3372 | \texttt{arbint intmul 218643832695416243621 13254215384521848},\\ | ||

3373 | |||

3374 | \noindent{}illustrates integer multiplication. The second command shown,\\ | ||

3375 | |||

3376 | \texttt{arbint intfac 55},\\ | ||

3377 | |||

3378 | \noindent{}illustrates calculating the factorial of | ||

3379 | 55. The third command shown, \\ | ||

3380 | |||

3381 | \texttt{arbint cfbrapab [arbint const pi 500] 65535 65535},\\ | ||

3382 | |||

3383 | \noindent{}illustrates calculating the best rational approximation to | ||

3384 | $\pi$ with numerator and denominator not exceeding | ||

3385 | 65,535, and using the first 500 digits of $\pi$ as | ||

3386 | the value of $\pi$. The fourth command shown,\\ | ||

3387 | |||

3388 | \texttt{arbint cfbrapab 1.609344 1023 1023},\\ | ||

3389 | |||

3390 | \noindent{}illustrates finding the best rational approximation to | ||

3391 | the conversion factor from MPH to KPH with numerator and denominator | ||

3392 | not exceeding 1,023. The last command shown,\\ | ||

3393 | |||

3394 | \texttt{arbint rnadd 78/2976 342/2763},\\ | ||

3395 | |||

3396 | \noindent{}illustrates the addition of | ||

3397 | two rational numbers. | ||

3398 | |||

3399 | Many other potential solutions for dealing with large | ||

3400 | integers have been submitted by newsgroup | ||

3401 | posters, and are listed below. (Please note that these alternatives haven't actually been | ||

3402 | tried, and we can't say whether they are viable.) | ||

3403 | |||

3404 | \begin{enumerate} | ||

3405 | |||

3406 | \item \index{Mathematica@\emph{Mathematica}}\emph{Mathematica} | ||

3407 | \cite{bibref:s:wolframmathematica} (by Wolfram Research) will easily operate on large integers and | ||

3408 | rational numbers with large integer components (see | ||

3409 | Footnote \ref{footnote:ccfr0:sptq0:ssoin0:mathematicaexpensive}). | ||

3410 | (Suggested by \index{Lutus, Paul} Paul Lutus \cite{bibref:i:paullutus} and | ||

3411 | \index{Taylor, Don} Don Taylor \cite{bibref:i:dontaylor}.) | ||

3412 | |||

3413 | \item \index{GNU!Multiple Precision Arithmetic Library (GMP)}The | ||

3414 | \emph{GNU Multiple Precision Arithmetic | ||

3415 | Library (GMP)} \cite{bibref:s:gnumultipleprecisionarithmeticlibrary}. | ||

3416 | This library, which is free and on the Web, can be linked into | ||

3417 | `C' and `C++' programs, and allows fast integer calculations of | ||

3418 | any size that do not exceed the memory available in the computer. | ||

3419 | This library could be used to quickly construct a program to | ||

3420 | process rational numbers with very large integer components. | ||

3421 | |||

3422 | \item \index{UBASIC@\emph{UBASIC}}\emph{UBASIC} \cite{bibref:s:ubasic} | ||

3423 | (\index{Kida, Yuji}by Yuji Kida \cite{bibref:i:yujikida}) | ||

3424 | is an extended-precision version of the BASIC | ||

3425 | language which will handle integers up to 2,600 digits and | ||

3426 | exact rational arithmetic. (Suggested by \index{Schorn, Richard} Richard Schorn | ||

3427 | \cite{bibref:i:richardschorn}.) | ||

3428 | |||

3429 | \item \index{Derive 5@\emph{Derive 5}}\emph{Derive 5} \cite{bibref:s:derive5} (by Texas Instruments). | ||

3430 | The exact capabilities of this software are not known, but the Web page indicates | ||

3431 | it can perform exact rational arithmetic. (Suggested by \index{Schorn, Richard} Richard Schorn | ||

3432 | \cite{bibref:i:richardschorn} and \index{Taylor, Don} Don Taylor \cite{bibref:i:dontaylor}.) | ||

3433 | |||

3434 | \item \index{Maple@\emph{Maple}}\emph{Maple} \cite{bibref:s:maple} (by Waterloo | ||

3435 | Maple, Inc.). The exact capabilities of this software are not known. | ||

3436 | (Suggested by | ||

3437 | \index{Lutus, Paul} Paul Lutus \cite{bibref:i:paullutus} and | ||

3438 | \index{Taylor, Don} Don Taylor \cite{bibref:i:dontaylor}.) | ||

3439 | |||

3440 | \item \index{MuPAD@\emph{MuPAD}}\emph{MuPAD} \cite{bibref:s:mupad} (from | ||

3441 | the University Of Paderborn, Germany). The capabilities of this | ||

3442 | software are not known. (Suggested by \index{Schorn, Richard} Richard Schorn | ||

3443 | \cite{bibref:i:richardschorn}.) | ||

3444 | |||

3445 | \end{enumerate} | ||

3446 | |||

3447 | %http://www.csc.fi/math_topics/Mail/FAQ/msg00015.html | ||

3448 | |||

3449 | In addition to the large integer resources above, a | ||

3450 | much longer list of resources is maintained | ||

3451 | at the URL | ||

3452 | |||

3453 | \begin{quote} | ||

3454 | \texttt{http://www.csc.fi/math\_topics/Mail/FAQ/msg00015.html}, | ||

3455 | \end{quote} | ||

3456 | |||

3457 | \noindent{}and is reproduced below. Because this URL was apparently last updated | ||

3458 | in 1994, it is not known which of the resources listed are still | ||

3459 | available. | ||

3460 | |||

3461 | \begin{quote} | ||

3462 | \begin{scriptsize} | ||

3463 | \begin{verbatim} | ||

3464 | -------------------------------------------------------------------------------- | ||

3465 | Subject: List of Arbitrary Precision C packages | ||

3466 | From: mrr@scss3.cl.msu.edu (Mark Riordan) | ||

3467 | Date: 27 Jan 1994 16:06:01 GMT | ||

3468 | Newsgroups: sci.math | ||

3469 | -------------------------------------------------------------------------------- | ||

3470 | This is the file BIGNUMS.TXT from ripem.msu.edu, last updated January 1994. | ||

3471 | |||

3472 | In response to Email requests, I have assembled this list of | ||

3473 | large-integer arithmetic packages of which I have heard. | ||

3474 | Most of these are C function libraries, available in source form. | ||

3475 | A few also deal with floating point numbers. | ||

3476 | |||

3477 | For your convenience, I have placed copies of | ||

3478 | some of these on ripem.msu.edu (35.8.1.178). They are | ||

3479 | available for anonymous FTP in the directory "pub/bignum". | ||

3480 | However, what I have may not be the most current version in all cases. | ||

3481 | |||

3482 | Here they are, in no particular order: | ||

3483 | |||

3484 | mp | ||

3485 | Multiple Precision package that comes with some Unixes | ||

3486 | |||

3487 | Multiple precision package accessed via -lmp flag on your | ||

3488 | compiler. Provides +, -, *, /, gcd, exponentiation, | ||

3489 | sqrt. Comes with SunOS, NeXT Mach, BBN Mach 1000, | ||

3490 | and probably a few others. See "man 3 mp". | ||

3491 | Object code only, of course. | ||

3492 | |||

3493 | PARI | ||

3494 | Henri Cohen, et al., Universite Bordeaux I, Paris, FRANCE | ||

3495 | |||

3496 | Multiple precision desk calculator and library routines. | ||

3497 | Contains optimized assembly code for Motorola 68020, | ||

3498 | semi-optimized code for SPARC, and apparently rather slow | ||

3499 | generic C version. Does both integers and reals. | ||

3500 | Does vectors and matrices as well as scalars. | ||

3501 | Contains a number of advanced functions, some of which I've | ||

3502 | never heard of. ("Weber's function"?) | ||

3503 | Has a factorization function, primality test, & other related stuff. | ||

3504 | Plenty of TEX documentation. | ||

3505 | Public domain, but you can't distribute modified versions. | ||

3506 | Available via anonymous FTP from ftp.inria.fr:lang/ and | ||

3507 | math.ucla.edu. The ucla site has Mac, MSDOS, OS/2, and | ||

3508 | NeXT-specific versions there in addition to: | ||

3509 | Filename: pari-1.37.tar.Z (There are now more recent versions) | ||

3510 | |||

3511 | Arithmetic in Global Fields (Arith) | ||

3512 | Kevin R. Coombes, David R. Grant | ||

3513 | |||

3514 | Package of routines for arbitrary precision integers or | ||

3515 | polynomials over finite fields. Includes basic +, -, *, / | ||

3516 | and a few others like gcd. Source code in C. | ||

3517 | Distributed under the terms of the GNU public license. | ||

3518 | Includes man pages and TEX documentation. | ||

3519 | Filename: arith.tar.Z | ||

3520 | |||

3521 | Arbitrary Precision Math Library | ||

3522 | Lloyd Zusman Los Gatos, CA | ||

3523 | |||

3524 | C package which supports basic +, -, *, /. Provides for radix | ||

3525 | points (i.e., non-integers). Not as polished as the others here. | ||

3526 | Posted to comp.sources.misc in October 1988. | ||

3527 | Filename: apml.tar.Z | ||

3528 | |||

3529 | BigNum | ||

3530 | J. Vuillemin, INRIA, FRANCE, and others. | ||

3531 | Distributed by Digital Equipment Paris Research Lab (DECPRL) | ||

3532 | |||

3533 | A "portable and efficient arbitrary-precision integer" package. | ||

3534 | C code, with generic C "kernel", plus assembly "kernels" for | ||

3535 | MC680x0, Intel i960, MIPS, NS32032, Pyramid, and of course VAX. | ||

3536 | This is probably one of the better-known packages of this type. | ||

3537 | Implements +, -, *, /, mod, plus logical operations OR, AND, XOR. | ||

3538 | Both signed and unsigned arithmetic available. | ||

3539 | Available via email from librarian@decprl.dec.com. | ||

3540 | You will receive 5 shell archives. Give your postal address | ||

3541 | and you will also receive printed documentation from France. | ||

3542 | Package includes TEX documentation. | ||

3543 | Publicly available for non-commercial use. | ||

3544 | I removed this from my archive when I heard a rumor that PRL | ||

3545 | doesn't like others to distribute it. However, BIGNUM *is* | ||

3546 | distributed as part of ecpp (see below). | ||

3547 | |||

3548 | Lenstra's LIP package | ||

3549 | Arjen Lenstra Bellcore | ||

3550 | |||

3551 | Portable unsigned integer package written entirely in C. | ||

3552 | Includes +, -, *, /, exponentiation, mod, primality testing, | ||

3553 | sqrt, random number generator, and a few others. | ||

3554 | An earlier version of this package is the only of these packages | ||

3555 | I have actually used. It works well and is very portable. | ||

3556 | I haven't done any benchmarks against the others, but the code | ||

3557 | looks clever & Lenstra is an accomplished number theorist. | ||

3558 | |||

3559 | LIP replaces lenstra-3.1.c. The package now includes encrypted | ||

3560 | source code; to obtain the decryption key, you must send a | ||

3561 | signed license agreement to Bellcore. See the documentation. | ||

3562 | Filename: lenstra-LIP-package.tar This is a collection of | ||

3563 | all the files in flash.bellcore.com:/pub/lenstra | ||

3564 | |||

3565 | bmp (Brent's Multiple Precision?) | ||

3566 | R. P. Brent | ||

3567 | |||

3568 | 1981 vintage FORTRAN code to do extended precision floating & | ||

3569 | fixed point arithmetic. Includes most of the mathematical | ||

3570 | functions you'd find in a FORTRAN run-time library. | ||

3571 | This code is an ACM algorithm, number 524. | ||

3572 | To obtain, send a mail message to netlib@ornl.gov | ||

3573 | containing the line "send mp.f from bmp" or better yet, perhaps | ||

3574 | just start with "help". | ||

3575 | |||

3576 | SPX | ||

3577 | Kannan Alagappan & Joseph Tardo, DEC | ||

3578 | |||

3579 | This is a huge prototype public key authentication system | ||

3580 | based on RSA. I mention it here because those who have heard | ||

3581 | of SPX have probably correctly guessed that it contains a large | ||

3582 | integer package and I want to inform you that the large integer | ||

3583 | package it contains is indeed DEC's BigNum from France. | ||

3584 | You can get a beta test copy of SPX from crl.dec.com (192.58.206.2). | ||

3585 | Use it only for testing, as it "may" expire on a certain date. | ||

3586 | (I don't know whether this has expired yet.) | ||

3587 | |||

3588 | amp (Antti's Multiple Precision?) | ||

3589 | Antti Louko alo@kampi.hut.fi | ||

3590 | |||

3591 | Multiple precision integer package in C. Includes +, -, *, /, %, | ||

3592 | pow, mod, 1/x mod y, random, sqrt, gcd. Available for non-commercial | ||

3593 | use. The package includes "share-secret", a public key system based | ||

3594 | on the Diffie-Hellman algorithm. | ||

3595 | This is normally part of the well-known "des-dist.tar.Z", | ||

3596 | but I have removed the DES part to avoid having to deal with | ||

3597 | cryptographic export laws, and have named the result: | ||

3598 | Filename: amp.tar.Z | ||

3599 | |||

3600 | gennum | ||

3601 | Per Bothner U of Wisconsin-Madison | ||

3602 | |||

3603 | C++ routines and classes to do generic arithmetic, both | ||

3604 | integer and rational. Part of the "Q" programming system. | ||

3605 | Distributed under the terms of the GNU public license. | ||

3606 | Obtained from cygnus.com. | ||

3607 | Filename: gennum.tar.Z | ||

3608 | |||

3609 | MIRACL | ||

3610 | (Shamus Software, Dublin, Ireland) | ||

3611 | |||

3612 | Integer and fractional multiple precision package. | ||

3613 | MIRACL is a portable C library. Full C/C++ source code included | ||

3614 | (In-line assembly support for 80x86). Number theoretic primitives | ||

3615 | needed to support PK Cryptography are supplied. | ||

3616 | C++ classes for Multiprecision Integers, Modular arithmetic, and | ||

3617 | Chinese Remainder Thereom. Implementation in C/C++ of all modern | ||

3618 | methods of Integer Factorisation, viz Brent-pollard, p-1, p+1, | ||

3619 | Elliptic Curve, MPQS. Includes TEX manual and some DOS .EXEs. | ||

3620 | Not public domain, but free for academic and non-commercial use. | ||

3621 | Obtained from ftp.compapp.dcu.ie. | ||

3622 | Filename: /pub/crypt/other/miracl-3.23.zip and miracl.tar.Z (older) | ||

3623 | |||

3624 | precision | ||

3625 | Dave Barrett barrettd@tigger.colorado.edu | ||

3626 | |||

3627 | Multiple precision integer package in C with +,-,*,/, sqrt, rand, | ||

3628 | mod, pow, log. Simple vector support. Does dynamic allocation of memory. | ||

3629 | Free as long as you don't sell it or any program that uses it. | ||

3630 | Filename: precision.tar.Z | ||

3631 | |||

3632 | UBASIC | ||

3633 | Prof. Yuji Kida, Rikkyo University, Nishi-Ikebukuro 3, Tokyo 171, Japan | ||

3634 | kida@rkmath.rikkyo.ac.jp | ||

3635 | |||

3636 | Multiple-precision version of the BASIC programming language, | ||

3637 | for MS-DOS. Includes floating point. Said (by Keith Briggs) | ||

3638 | to be pretty fast. Object only, I think. ervin@morekypr.bitnet | ||

3639 | says: "This is the best package that I know of for | ||

3640 | fast arithmetic. Has a version optimized for 386 machines. Includes | ||

3641 | routines to do MPQS, the fastest currently known general factoring | ||

3642 | algorithm. An additional file is at both sites to allow MPQS to use | ||

3643 | hard drives so that it can factor up to 80 digits. Many number | ||

3644 | theoretical functions are included in UBASIC. It allows over 2500 | ||

3645 | digits of precision." | ||

3646 | Available via anonymous FTP from shape.mps.ohio-state.edu, | ||

3647 | or simtel20.army.mil, or wuarchive.wustl.edu. | ||

3648 | |||

3649 | calc_v22 | ||

3650 | Unknown | ||

3651 | |||

3652 | MS-DOS C-like language that allows "infinite" precision. | ||

3653 | Nice intrinsic functions. ervin@morekypr.bitnet reports problems | ||

3654 | when changing precision on the fly. | ||

3655 | See simtel20 or wuarchive. | ||

3656 | |||

3657 | briggs_arith | ||

3658 | Keith Briggs (kbriggs@maths.adelaide.edu.au) | ||

3659 | |||

3660 | Turbo Pascal 5 source for routines that do multiple-precision | ||

3661 | +, -, *, /, sqrt, gcd, factoring, rand for integers; also includes | ||

3662 | +, -, *, / and rand for rational numbers. | ||

3663 | Filename: briggs_arith.pas | ||

3664 | |||

3665 | Institute fur Experimentelle Mathematik | ||

3666 | Dr Gerhard Schneider (?) | ||

3667 | |||

3668 | Fast C multiple-precision subroutine library. | ||

3669 | I don't know anything about it; sl25@ely.cl.cam.ac.uk says | ||

3670 | to contact MAT420@DE0HRZ1A.BITNET for more info. | ||

3671 | Postal Address: | ||

3672 | Institute fur Experimentelle Mathematik | ||

3673 | EllernStr 29 | ||

3674 | D4300 Essen-12 GERMANY | ||

3675 | |||

3676 | LongInt | ||

3677 | Markus Mueller (mueller@komsys.tik.ethz.ch) | ||

3678 | |||

3679 | "Multi precision arithmetic written in MODULA-2, with the most time critical | ||

3680 | parts written in Assembler. Includes basic arithmetics (+, -, *, /, %) as | ||

3681 | well as arithmetics MODULO a number. An additional module provides a | ||

3682 | collection of procedures for primality testing, gcd, multiplicative | ||

3683 | inverse and more. The package is part of a Privacy Enhanced Mail (PEM) | ||

3684 | package which includes a PEM mailer, RSA key generator and Certificate | ||

3685 | generation tools." | ||

3686 | |||

3687 | Source is in Modula-2, C, and assembler for Sun 3. LongInt has | ||

3688 | also been ported to MS-DOS under Logitech Modula-2 and Turbo | ||

3689 | Assembler. Availability: free for university use (research and | ||

3690 | education); otherwise, a source license is required. To obtain, | ||

3691 | write or email to: | ||

3692 | |||

3693 | Markus Mueller | ||

3694 | Bertastrasse 7 | ||

3695 | CH-8953 Dietikon | ||

3696 | Switzerland | ||

3697 | email: mueller@komsys.tik.ethz.ch | ||

3698 | |||

3699 | bignum-1.2 | ||

3700 | Henrik.Johansson@Nexus.Comm.SE | ||

3701 | |||

3702 | Bignum package written in portable C. Will in the future | ||

3703 | conform to the Common Lisp functions that handles integers. | ||

3704 | Currently includes +, -, *, /, exponentiation, "exptmod", | ||

3705 | comparison, random numbers, and gcd. | ||

3706 | Filename: bignum-1.2 | ||

3707 | |||

3708 | ACM algorithm 567 | ||

3709 | D.W. LOZIER and J.M. SMITH | ||

3710 | |||

3711 | FORTRAN subroutines to do extended-precision floating point | ||

3712 | and normalized Legendre polynomials. | ||

3713 | ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE 7,1 (MARCH, 1981) | ||

3714 | Obtained from research.att.com:netlib/toms/567.Z | ||

3715 | Filename: acm-algorithm-567-floating-point.fortran.Z | ||

3716 | |||

3717 | range | ||

3718 | O. Aberth and M. J. Schaefer | ||

3719 | |||

3720 | C++ package to do extended-precision floating point arithmetic | ||

3721 | with programmer-defined precision. Uses decimal representations | ||

3722 | internally. Contains basic +, -, *, /, relational operators, | ||

3723 | ++, and a few functions like sin, cos, sqrt, log. Documentation | ||

3724 | a trifle confusing. | ||

3725 | Obtained from math.tamu.edu:pub/range/range.tar.Z | ||

3726 | Filename: range.tar.Z | ||

3727 | |||

3728 | bsint | ||

3729 | Author unknown. | ||

3730 | |||

3731 | Pre-alpha release of C++ big integer package. | ||

3732 | Implements basic math operators, exponentiation, and modular | ||

3733 | exponentiation. Very skimpy documentation. | ||

3734 | See milton.u.washington.edu:/pub/user-supported/tzs/bsint.tar.Z | ||

3735 | |||

3736 | GNU Multiple Precision (GMP) | ||

3737 | GNU (Free Software Foundation) multiple precision package. | ||

3738 | I haven't looked at it yet. This is current as of April 1992, | ||

3739 | but there may be a more recent version by the time you read | ||

3740 | this. This package is very widely available on FTP sites. | ||

3741 | Filename: gmp-1.3.2.tar.Z | ||

3742 | |||

3743 | libg++ - GNU's C++ class library | ||

3744 | Free Software Foundation | ||

3745 | |||

3746 | Includes Integer and Rational classes. Integer provides | ||

3747 | the usual C++ operators, plus exponentiation, gcd, lcm. | ||

3748 | Limited functionality, but documentation is better than most. | ||

3749 | Look for libg++-2.4.tar.gz on an FTP server near you. | ||

3750 | |||

3751 | Elliptic Curve Primality Proving | ||

3752 | Francois Morain, France. | ||

3753 | |||

3754 | Large package to prove the primality of any prime. | ||

3755 | Includes Inria's BIGNUM package. | ||

3756 | Obtained from ftp.inria.fr (128.93.1.26). | ||

3757 | Filename: ecpp.V3.4.1.tar.Z | ||

3758 | |||

3759 | PGP (Pretty Good Privacy) | ||

3760 | Philip Zimmermann prz@sage.cgd.ucar.EDU | ||

3761 | |||

3762 | Crypto package that includes bignum routines in C. | ||

3763 | Assembly implementations available for several processors; | ||

3764 | said to be quite fast for numbers around 1000 bits in size. | ||

3765 | The crypto package violates RSA patents, but the bignum routines | ||

3766 | can be used without fear of legal repercussions. | ||

3767 | |||

3768 | Bell's Arbitrary Precision Calculator | ||

3769 | David I. Bell, Australia (dbell@pdact.pd.necisa.oz.au) | ||

3770 | |||

3771 | Arbitrary-precision calculator with good online help, C-like | ||

3772 | language, many builtin functions, support for integers, | ||

3773 | rational numbers (they work like floating point), complex numbers, | ||

3774 | matrices, strings, lists, files, "objects". Includes | ||

3775 |