/[dtapublic]/pubs/books/ucbka/trunk/c_cfr0/c_cfr0.tex
ViewVC logotype

Contents of /pubs/books/ucbka/trunk/c_cfr0/c_cfr0.tex

Parent Directory Parent Directory | Revision Log Revision Log


Revision 140 - (show annotations) (download) (as text)
Mon Jul 3 01:59:16 2017 UTC (5 years, 1 month ago) by dashley
File MIME type: application/x-tex
File size: 170706 byte(s)
Change SVN properties for EOL and keyword expansion.
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 $RCSfile: c_cfr0.tex,v $
3949 $Source: /home/dashley/cvsrep/e3ft_gpl01/e3ft_gpl01/dtaipubs/esrgubka/c_cfr0/c_cfr0.tex,v $
3950 $Revision: 1.18 $
3951 $Author: dtashley $
3952 $Date: 2004/03/12 11:12:35 $
3953 \end{verbatim}
3954 \end{tiny}
3955 \noindent\rule[0.25in]{\textwidth}{1pt}
3956 \end{figure}
3957
3958 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3959 % $Log: c_cfr0.tex,v $
3960 % Revision 1.18 2004/03/12 11:12:35 dtashley
3961 % Erroneous equation reference corrected, plus a cosmetic change to source code
3962 % by addition of separation bars.
3963 %
3964 % Revision 1.17 2004/01/18 20:09:04 dtashley
3965 % Danil Hiridjee added in acknowledgements.
3966 %
3967 % Revision 1.16 2003/11/03 02:14:24 dtashley
3968 % All duplicate labels as flagged by LaTeX removed. Additional files added
3969 % to Microsoft Visual Studio edit context.
3970 %
3971 % Revision 1.15 2003/04/03 19:31:30 dtashley
3972 % Correction about the number corresponding to the continued fraction
3973 % [1;1,1,1,...], received from Jan-Hinnerk Reichert, with additional
3974 % information provided by two newsgroup posters, made.
3975 %
3976 % Revision 1.14 2002/08/22 00:33:33 dtashley
3977 % Have made aesthetic changes in CFRY0 and CCFR0. Checking in all before
3978 % rebuild of book.
3979 %
3980 % Revision 1.13 2002/04/27 00:21:03 dtashley
3981 % Substantial edits--preparing for review.
3982 %
3983 % Revision 1.12 2002/02/12 19:12:55 dtashley
3984 % Unwieldly fraction corrected.
3985 %
3986 % Revision 1.11 2001/08/31 23:11:14 dtashley
3987 % End of August 2001 safety check-in.
3988 %
3989 % Revision 1.10 2001/08/25 22:51:25 dtashley
3990 % Complex re-organization of book.
3991 %
3992 % Revision 1.9 2001/08/22 10:46:12 dtashley
3993 % Initial check-in, edits.
3994 %
3995 % Revision 1.8 2001/07/23 21:40:40 dtashley
3996 % Hopefully final changes to the section about convergents as best
3997 % approximations. Tool documentation changes.
3998 %
3999 % Revision 1.7 2001/07/23 03:30:19 dtashley
4000 % Edits.
4001 %
4002 % Revision 1.6 2001/07/09 21:38:45 dtashley
4003 % Longer list of large integer resources added.
4004 %
4005 % Revision 1.5 2001/07/09 02:22:55 dtashley
4006 % Edits. Safety check-in after changes and addition of figures.
4007 %
4008 % Revision 1.4 2001/07/06 23:46:55 dtashley
4009 % Edits. Addition of K-map diagrams to Boolean function chapter.
4010 %
4011 % Revision 1.3 2001/07/01 21:10:59 dtashley
4012 % Safety check-in after major re-org.
4013 %
4014 % Revision 1.2 2001/06/29 23:47:43 dtashley
4015 % Conversion away from binary for CVS archiving, typos and poor wording
4016 % in French translation corrected.
4017 %
4018 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
4019 % $History: c_cfr0.tex $
4020 %
4021 % ***************** Version 6 *****************
4022 % User: Dashley1 Date: 3/11/01 Time: 4:42a
4023 % Updated in $/uC Software Multi-Volume Book (A)/Chapter, CFR0, Continued Fractions
4024 % Nearly complete except for pending French translation.
4025 %
4026 % ***************** Version 5 *****************
4027 % User: Dashley1 Date: 3/07/01 Time: 12:17a
4028 % Updated in $/uC Software Multi-Volume Book (A)/Chapter, CFR0, Continued Fractions
4029 % Edits.
4030 %
4031 % ***************** Version 4 *****************
4032 % User: Dashley1 Date: 12/22/00 Time: 12:54a
4033 % Updated in $/uC Software Multi-Volume Book (A)/Chapter, CFR0, Continued Fractions
4034 % Tcl automated method of build refined.
4035 %
4036 % ***************** Version 3 *****************
4037 % User: David T. Ashley Date: 7/29/00 Time: 11:50p
4038 % Updated in $/uC Software Multi-Volume Book (A)/Chapter, CFR0, Continued Fractions
4039 % Edits, addition of solutions manual volume.
4040 %
4041 % ***************** Version 2 *****************
4042 % User: David T. Ashley Date: 7/09/00 Time: 11:23p
4043 % Updated in $/uC Software Multi-Volume Book (A)/Chapter, CFR0, Continued Fractions
4044 % Addition of new chapters, enhancements to preface.
4045 %
4046 % ***************** Version 1 *****************
4047 % User: David T. Ashley Date: 7/09/00 Time: 9:27p
4048 % Created in $/uC Software Multi-Volume Book (A)/Chapter, CFR0, Continued Fractions
4049 % Initial check-in.
4050 %End of file C_CFR0.TEX

Properties

Name Value
svn:eol-style native
svn:keywords Header

dashley@gmail.com
ViewVC Help
Powered by ViewVC 1.1.25