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

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

Parent Directory Parent Directory | Revision Log Revision Log


Revision 275 - (hide annotations) (download) (as text)
Mon Aug 12 00:47:10 2019 UTC (4 years, 7 months ago) by dashley
File MIME type: application/x-tex
File size: 167063 byte(s)
Change keyword substitution (migration from cvs to svn).
1 dashley 140 %$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 dashley 275 $HeadURL$
3949     $Revision$
3950     $Date$
3951     $Author$
3952 dashley 140 \end{verbatim}
3953     \end{tiny}
3954     \noindent\rule[0.25in]{\textwidth}{1pt}
3955     \end{figure}
3956    
3957     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3958     %
3959     %End of file C_CFR0.TEX

Properties

Name Value
svn:eol-style native
svn:keywords Author Date Id Revision URL Header

dashley@gmail.com
ViewVC Help
Powered by ViewVC 1.1.25