Parent Directory | Revision Log

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

*Mon Aug 12 00:47:10 2019 UTC*
(3 years, 3 months ago)
by *dashley*

File MIME type: application/x-tex

File size: 167063 byte(s)

File MIME type: application/x-tex

File size: 167063 byte(s)

Change keyword substitution (migration from cvs to svn).

1 | %$Header$ |

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 | gcd, primality testing, even trig functions. Recommended. |

3776 | (Large package, though.) Obtained from comp.sources.unix. |

3777 | Filename: calc-1.24.7.tar.Z |

3778 | |

3779 | Calc for GNU Emacs |

3780 | Dave Gillespie (daveg@synaptics.com) |

3781 | |

3782 | Advanced calculator written in Emacs Lisp. Includes arbitrary |

3783 | precision integers and floating point, bitwise operations, |

3784 | log and trig functions, financial functions, number theoretic |

3785 | functions including prime factorization, symbolic calculus, |

3786 | and an interface to GNUPLOT. |

3787 | Filename: calc-2.02a.tar.Z |

3788 | |

3789 | MPFUN: A Multiple Precision Floating Point Computation Package |

3790 | David H. Bailey (dbailey@nas.nasa.gov) |

3791 | |

3792 | Package of Fortran subroutines to perform multiprecision |

3793 | floating point arithmetic. Also includes a program that |

3794 | can automatically convert ordinary Fortran-77 code into code |

3795 | that calls the MPFUN routines. |

3796 | Keith Briggs says: "It's a masterpiece, and the state of the art |

3797 | as far as Fortran goes." |

3798 | Documentation in TeX format. Unrestricted distribution |

3799 | allowed at no cost. |

3800 | Filenames: mpfun_fortran.tar.Z & mpfun_tex_papers.tar.Z |

3801 | |

3802 | MPQS |

3803 | Mark S. Manasse (msm@src.dec.com) and Arjen Lenstra |

3804 | |

3805 | C program to factor numbers on a distributed network of |

3806 | heterogeneous machines. June 1993 version. |

3807 | Filename: mpqs-distributed-factoring.shar |

3808 | |

3809 | GNU bc |

3810 | Author: Philip A. Nelson (phil@cs.wwu.edu) |

3811 | GNU bc is an interactive algebraic language with arbitrary precision. |

3812 | GNU bc is almost the same as bc & dc in some Unixes. |

3813 | Filename: bc-1.02.tar.z (for example, in GNU prep.ai.mit.edu:pub/gnu/) |

3814 | |

3815 | bc & dc |

3816 | bc is an interactive processor for an arbitrary precision arithmetic |

3817 | language or just compiler/preprocessor for dc calculator with arbitrary |

3818 | precision; they comes with some Unixes. |

3819 | |

3820 | Built-in support in other languages |

3821 | Various |

3822 | |

3823 | Multiple precision arithmetic is available in a number of |

3824 | programming languages, such as Lisp and ABC (cf. mcsun.eu.net). |

3825 | Version 8 of the programming language Icon (Griswold's successor |

3826 | to SNOBOL4 available from cs.arizona.edu) has large integers. |

3827 | Perl (by Larry Wall, available from devvax.jpl.nasa.gov) |

3828 | includes source, in Perl, for such a package, but it's probably |

3829 | not suitable for serious use. |

3830 | For some of these, source code may be available. This list is |

3831 | long enough, so I'm not going to pursue it aggressively. |

3832 | |

3833 | Thanks to Keith Briggs and several others who contributed to this list. |

3834 | |

3835 | See also other sites, such as nic.funet.fi:pub/sci/math/multiplePrecision/. |

3836 | |

3837 | Mark Riordan mrr@ripem.msu.edu |

3838 | -------------------------------------------------------------------------------- |

3839 | \end{verbatim} |

3840 | \end{scriptsize} |

3841 | \end{quote} |

3842 | |

3843 | |

3844 | |

3845 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |

3846 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |

3847 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |

3848 | \section{Authors And Acknowledgements} |

3849 | %Section tag: ACK0 |

3850 | This chapter was primarily written by \index{Ashley, David T.}David T. Ashley |

3851 | \cite{bibref:i:daveashley}, and is based on a paper originally |

3852 | authored by |

3853 | David T. Ashley \cite{bibref:i:daveashley}, |

3854 | Joseph P. DeVoe \cite{bibref:i:joedevoe}, |

3855 | Karl Perttunen \cite{bibref:i:karlperttunen}, |

3856 | Cory L. Pratt \cite{bibref:i:corypratt}, |

3857 | and Anatoly Zhigljavsky \cite{bibref:i:anatolyzhigljavsky}. |

3858 | |

3859 | We would like to gratefully acknowledge the assistance of |

3860 | \index{Davidson, Iain} Iain Davidson \cite{bibref:i:iaindavidson}, |

3861 | \index{Edgar, Gerald A.} Gerald A. Edgar \cite{bibref:i:geraldaedgar}, and |

3862 | \index{Smiley, Len} Len Smiley \cite{bibref:i:lensmiley} |

3863 | in locating works related to the history of continued fractions. |

3864 | We would also like to acknolwedge the assistance of |

3865 | \index{Davidson, Iain} Iain Davidson \cite{bibref:i:iaindavidson} |

3866 | in providing insight into algorithms and other assistance. |

3867 | |

3868 | For translating the remarks of Huygens and Delambre (Section |

3869 | \ref{cfr0:hst0}) from French |

3870 | to English, we are grateful to Sandrine de Raspide\index{Raspide, Sandrine@de Raspide, Sandrine} \cite{bibref:i:sandrinederaspide} |

3871 | and Danil Hiridjee\index{Hiridjee, Danil} \cite{bibref:i:danilhiridjee}. |

3872 | |

3873 | We would also like to acknowledge the assistance of \texttt{sci.math} |

3874 | \cite{bibref:n:scimathnewsgroup} |

3875 | newsgroup posters in suggesting software which can manipulate |

3876 | high-precision numbers, including |

3877 | \index{Lutus, Paul} Paul Lutus \cite{bibref:i:paullutus}, |

3878 | \index{Schorn, Richard} Richard Schorn \cite{bibref:i:richardschorn}, |

3879 | and |

3880 | \index{Taylor, Don} Don Taylor \cite{bibref:i:dontaylor}. |

3881 | |

3882 | Special thanks to |

3883 | \index{Eastham, Chip} Chip Eastham \cite{bibref:i:chipeastham}, |

3884 | \index{Kolker, Robert} Robert Kolker \cite{bibref:i:robertkolker}, |

3885 | and |

3886 | \index{Reichert, Jan-Hinnerk} Jan-Hinnerk Reichert \cite{bibref:i:janhinnerkreichert} |

3887 | for locating and assisting in the correction of typographic |

3888 | and mathematical errors. |

3889 | |

3890 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |

3891 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |

3892 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |

3893 | \section{Exercises} |

3894 | %Section tag: EXE0 |

3895 | |

3896 | \subsection{Algorithms} |

3897 | |

3898 | \begin{vworkexercisestatement} |

3899 | \label{exe:cfr0:sexe0:a01} |

3900 | Develop an algorithm to convert a continued fraction $[a_0;a_1, \ldots{}, a_n]$ |

3901 | to a rational number $a/b$ ``from the right'' (starting with $a_n$), and prove |

3902 | that the $a/b$ generated will be irreducible. (Hint: the ordinary algorithm |

3903 | often applied by hand---working ``from the bottom up'' as shown in |

3904 | Example \ref{ex:ccfr0:scnv0:abreconstructionfromright:01} |

3905 | will always generate a coprime $a/b$.) |

3906 | \end{vworkexercisestatement} |

3907 | |

3908 | \subsection{Calculation Of Best Rational Approximations} |

3909 | |

3910 | \begin{vworkexercisestatement} |

3911 | \label{exe:cfr0:sexe0:b01} |

3912 | Assuming 1.609344\footnote{\label{footnote:exe:cfr0:sexe0:b01}This |

3913 | conversion factor was |

3914 | obtained from \cite{bibref:b:nistsp811:1995ed} and is |

3915 | assumed to be the most accurate conversion factor available.} |

3916 | as the exact conversion factor from miles to |

3917 | kilometers, find the best rational approximation to this |

3918 | conversion factor with a maximum numerator of 255 and a maximum |

3919 | denominator of 255. |

3920 | \end{vworkexercisestatement} |

3921 | |

3922 | \begin{vworkexercisestatement} |

3923 | \label{exe:cfr0:sexe0:b02} |

3924 | Assuming 1.609344 (see Footnote \ref{footnote:exe:cfr0:sexe0:b01}) |

3925 | as the exact conversion factor from miles to |

3926 | kilometers, find the best rational approximation to this |

3927 | conversion factor with a maximum numerator of 65,535 and a maximum |

3928 | denominator of 65,535. |

3929 | \end{vworkexercisestatement} |

3930 | |

3931 | \subsection{Continued Fraction Representation Of Irrational Numbers} |

3932 | |

3933 | \begin{vworkexercisestatement} |

3934 | \label{exe:cfr0:sexe0:c01} |

3935 | Show that the continued fraction representation of the |

3936 | golden ratio $(\sqrt{5}/2 + 1/2)$ is $[1;\overline{1}]$. |

3937 | \end{vworkexercisestatement} |

3938 | |

3939 | \vworkexercisefooter{} |

3940 | |

3941 | |

3942 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |

3943 | |

3944 | \noindent\begin{figure}[!b] |

3945 | \noindent\rule[-0.25in]{\textwidth}{1pt} |

3946 | \begin{tiny} |

3947 | \begin{verbatim} |

3948 | $HeadURL$ |

3949 | $Revision$ |

3950 | $Date$ |

3951 | $Author$ |

3952 | \end{verbatim} |

3953 | \end{tiny} |

3954 | \noindent\rule[0.25in]{\textwidth}{1pt} |

3955 | \end{figure} |

3956 | |

3957 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |

3958 | % |

3959 | %End of file C_CFR0.TEX |

Name | Value |
---|---|

svn:eol-style |
native |

svn:keywords |
Author Date Id Revision URL Header |

dashley@gmail.com | ViewVC Help |

Powered by ViewVC 1.1.25 |