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

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

Parent Directory | Revision Log | View Patch Patch

-revision 4 by dashley,
Thu Oct  6 03:15:02 2016 UTC
+revision 140 by dashley,
Mon Jul  3 01:59:16 2017 UTC
 Line 1
- %$Header: /home/dashley/cvsrep/e3ft_gpl01/e3ft_gpl01/dtaipubs/esrgubka/c_cfr0/c_cfr0.tex,v 1.18 2004/03/12 11:12:35 dtashley Exp $
+ %$Header$
  \chapter{\ccfrzerolongtitle{}}
  \label{ccfr0}
  \beginchapterquote{``I began by saying that there is probably less difference
                       between the positions of a mathematician and a physicist
                       than is generally supposed, and that the most important
                       seems to me to be this, that the mathematician is in much
                       more direct contact with reality \ldots{} mathematical
                       objects are so much more what they seem.  A chair or a
                       star is not in the least what it seems to be; the more we think
                       of it, the fuzzier its outlines become in the haze of sensation
                       which surround it; but `2' or `317' has nothing to do with
                       sensation, and its properties stand out the more clearly the more
                       closely we scrutinize it.''}
                       {G. H. Hardy \cite{bibref:b:mathematiciansapology:1940}, pp. 128-130}
                                           \index{Hardy, G. H.}
  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  \section{Introduction}
  %Section tag: INT0
  \label{ccfr0:sint0}
  \index{continued fraction}
  \index{continued fraction!definition}
  A \emph{finite simple continued fraction} is a fraction of the form
  \begin{equation}
  \label{eq:ccfr0:int0:00}
  a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2
      + \cfrac{1}{\;\;\;\;\;\;\;\;\;\;\;\;\;\;\ldots + \cfrac{1}{a_n}}}}
      =
      [a_0; a_1, a_2, \ldots , a_n] ,
  \end{equation}
  \noindent{}where $a_0 \in \vworkintsetnonneg$ and
  $a_i \in \vworkintsetpos$, $i > 0$.  Each integer
  $a_i$ is called an \index{continued fraction!element}\emph{element} or
  \index{continued fraction!partial quotient}\emph{partial quotient}
  of the continued fraction.
  We require, except in the case of
  the continued fraction representation of an integer,
  that the final element $a_n$ not be equal
  to 1.\footnote{\label{footnote:ccfr0:sint0:00}The reason for
  this restriction is discussed later.}
  Continued fractions are quite unwieldly to write and typeset,
  and so a continued fraction in the form of (\ref{eq:ccfr0:int0:00})
  is written as $[a_0; a_1, a_2, \ldots , a_n]$.  Note that the
  separator between $a_0$ and $a_1$ is a semicolon (`;'), and that all other
  separators are commas (`,').  In some works, commas are used exclusively; and in
  other works, the first element is $a_1$ rather than $a_0$.  Throughout this
  work, the notational conventions illustrated in (\ref{eq:ccfr0:int0:00}) are
  followed.
  In this chapter, the framework of continued fractions is presented in the
  context of finding rational numbers in $F_N$, the Farey series of order $N$,
  enclosing an arbitrary $r_I \in \vworkrealsetnonneg$.  The continued fraction
  algorithm presented (Algorithm \ref{alg:ccfr0:scba0:cfenclosingneighborsfn})
  is $O(log N)$, and so is suitable for finding the best rational
  approximations in $F_N$ even when $N$ is very large.  Because our emphasis
  is on practical applications rather than number theory, we don't include more
  information than is necessary to understand the applications we have in
  mind.
  The study of continued
  fractions is a topic from number theory (a branch of mathematics).  It may be
  counterintuitive to anyone but a number theorist that continued fractions
  can be used to economically find best rational approximations,
  or that continued fractions are anything but
  a parlor curiosity.  C.D. Olds (\cite{bibref:b:OldsClassic}, p. 3) comments:
  \index{Olds, C. D.}
  \begin{quote}
  At first glance, nothing seems simpler or less significant than writing a number,
  for example $\frac{9}{7}$, in the form
  \begin{equation}
  \frac{9}{7} = 1 + \frac{2}{7} = 1 + \frac{1}{\cfrac{7}{2}}
              = 1 + \cfrac{1}{3 + \cfrac{1}{2}}
              = 1 + \cfrac{1}{3 + \cfrac{1}{1 + \cfrac{1}{1}}}.
  \end{equation}
  It turns out, however, that fractions of this form, called ``continued
  fractions'', provide much insight into mathematical problems, particularly into
  the nature of numbers.
  Continued fractions were studied by the great mathematicians of the seventeenth
  and eighteenth centuries and are a subject of active investigation today.
  \end{quote}
  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  \section{History Of Continued Fractions}
  %Section tag: HST0
  \label{cfr0:hst0}
  \index{continued fraction!history of}
  The only work we are aware of that explicitly treats the history
  of continued fractions is \cite{bibref:b:HistoryCfPadeApproxBrezinski}.
  Although the history of continued fractions is complex,
  two points are clear.  First, it is clear that Euclid's \index{Euclid}
  GCD algorithm \index{Euclid!GCD algorithm}
  (Algorithm \ref{alg:ccfr0:sega0:euclidsgcdalgorithm}),
  which was known no later than around 300 B.C.,
  represents the historical origin of the continued fraction.  Second,
  it is clear that the utility of the apparatus of continued fractions
  in finding best rational approximations---specifically the properties
  of convergents---was understood by the 17th century.
  In this section, we present some excerpts from
  \cite{bibref:b:HistoryCfPadeApproxBrezinski}
  which show the very early use of continued fractions to obtain best rational
  approximations with a numerator and denominator less than certain
  prescribed limits.
  We simply demonstrate that the technique we present was known by
  the 17th century (with the possible exception of the
  second component of Theorem \ref{thm:ccfr0:scba0:cfenclosingneighbors}),
  and we don't attempt to describe the other uses
  of continued fractions or the significance of continued fractions
  in mathematics or number theory.
  Although we present best rational
  approximations in the context of being able to effectively use
  processor integer multiplication and division instructions,
  earlier historical work was aimed at either
  providing rational approximations to irrational numbers ($\sqrt{2}$ or $\pi$,
  for example), or at determining optimal numbers of gear teeth
  (in mechanical systems).  Naturally, the need for best rational approximations
  in the context of computer arithmetic is a relatively recent
  development.
  In the introduction of \cite{bibref:b:HistoryCfPadeApproxBrezinski},
  Brezinski \index{Brezenski, Claude} hints at the broad application and importance
  of continued fractions:
  \begin{quote}
  The history of continued fractions is certainly one of the longest
  among those of mathematical concepts, since it begins with
  Euclid's algorithm \index{Euclid!GCD algorithm} for the greatest common divisor at least
  three centuries B.C.  As it is often the case and like
  Monsieur Jourdain in Moli\`ere's ``le bourgeois gentilhomme''
  (who was speaking in prose though he did not know he was doing so),
  continued fractions were used for many centuries before their real
  discovery.
  The history of continued fractions and Pad\'e approximants is also
  quite important, since they played a leading role in the development
  of some branches of mathematics.  For example, they were the basis
  for the proof of the transcendence of $\pi$ in 1882, an open
  problem for more than two thousand years, and also for our modern
  spectral theory of operators.  Actually they still are of great
  interest in many fields of pure and applied mathematics and in
  numerical analysis, where they provide computer approximations to
  special functions and are connected to some convergence acceleration
  methods.  Continued fractions are also used in number theory,
  computer science, automata, electronics, etc. \ldots{}
  \end{quote}
  Notice that Theorem \ref{thm:ccfr0:scba0:cfenclosingneighbors}
  has two components.  First, it is shown that the highest-order
  convergent with an acceptable denominator is closer to $a/b$ than
  any Farey neighbor to this convergent (thus, this convergent must be
  either a left or right  Farey neighbor of $a/b$).  Second, it is shown
  what the other Farey neighbor must be.  It is historically clear
  that the properties of convergents as best rational approximations were
  understood by the 17th century (this is the \emph{first} part of
  Theorem \ref{thm:ccfr0:scba0:cfenclosingneighbors}).  However, it
  is not historically clear when the \emph{second} part of
  Theorem \ref{thm:ccfr0:scba0:cfenclosingneighbors} was discovered.
  Even in Khinchin's \index{Khinchin, A. Ya.} classic work,
  \cite{bibref:b:KhinchinClassic}, Theorem 15, p. 22, Khinchin stops
  just short of the result presented as the second part of
  Theorem \ref{thm:ccfr0:scba0:cfenclosingneighbors}.  Khinchin writes:
  \begin{quote}
  THEOREM 15.  \em Every best approximation of a number is a convergent
  or an intermediate fraction of the continued fraction representing
  that number.
  \end{quote}
  \noindent{}Theorem \ref{thm:ccfr0:scba0:cfenclosingneighbors} goes
  slightly farther than Khinchin's \emph{THEOREM 15}, above.
  Khinchin \index{Khinchin, A. Ya.} states
  that a best approximation will be a convergent or an intermediate
  fraction---but Theorem \ref{thm:ccfr0:scba0:cfenclosingneighbors}
  goes slightly farther to indicate \emph{exactly which} intermediate fraction
  is potentially the best approximation.  Khinchin's \emph{THEOREM 15}
  is correct, but could be strengthened.  Khinchin's work
  was first published in 1935.  This raises the [unlikely] possibility
  that the second part of Theorem \ref{thm:ccfr0:scba0:cfenclosingneighbors}
  had not been published even as recently as 1935, although
  we (the authors) don't have the ability to confirm or
  refute this.
  In \cite{bibref:b:HistoryCfPadeApproxBrezinski}, p. 70, Brezinski
  \index{Brezenski, Claude}
  writes:
  \begin{quote}
  In the same period, algorithms equivalent to continued fractions were
  still used to find approximate values for ratios and to simplify
  fractions.  We have already mentioned Albert Girard.
  Among the other authors who treated the subject, the most prominent
  is Daniel SCHWENTER \index{Schwenter, Daniel}
  (N\"urnberg, 31.1.1585 - Altdorf, 19.1.1636),
  who wrote two books ``\emph{Geometriae practicae novae et auctae
  tractatus}'' published in 1627 and ``\emph{Delicae
  Physico-mathematicae}'' which appeared in 1636 followed by a
  second edition in 1651.
  In his first book, Schwenter found approximations of 177/233 by
  finding their g.c.d. and gave the successive convergents
 /104, 19/25, 3/4, 1/1, and 0/1.  His calculations were arranged
  in a table\footnote{The table is reproduced in
  \cite{bibref:b:HistoryCfPadeApproxBrezinski},
  but is omitted here.} \ldots{} although he gave no explanation of the method.
  \end{quote}
  On p. 84, Brezenski \index{Brezenski, Claude} writes:
  \begin{quote}
  Wallis \index{Wallis, John} also made use of continued fractions in his book
  ``\emph{A treatise of algebra both historical and practical}''
  (published in 1685), to approximate ratios with large
  numerators and denominators:
  \emph{``Before I leave the business of Decimal Parts, and the
  advantages which in practice may there cause; I have thought fit
  here to insert a Process Of Reducing Fractions or Proportions to
  smaller termes, retaining as near as may be, the just value.}
  \emph{It was occasion'd by a Problem sent me (as I remember) about the
  Year 1663 or 1664, by Dr. Lamplugh the present Bishop of Exeter from
  (his Wives Father) Dr. Davenant then one of the Prebends
  Residentaries of the Church of Salisbury, a very worthy Person, of
  great Learning and Modesty; as I mire inderstand from persons
  well acquainted with him, and by divers Writings of his which I have seen,
  though I never had the opportunity of being personally acquainted with him,
  otherwise than by Letter.  And amongst
  his other Learning, he was very well skilled the Mathematicks,
  and a diligent Proficient therein.}
  \emph{He sent me (as it abovesaid) a Fraction (which what it was I
  do not now particulary remember) who's Numerator and Denominator
  were, each of them of about six or seven places; and Proposed to
  find the nearest Fraction in value to it, whose Denominator should
  not be greater than 999.''}
  \begin{center}
  \rule{3in}{0.3mm}  \\\
  \end{center}
  \begin{center}
  \emph{The Problem} \\
  \end{center}
  \emph{A Fraction (or Proportion) being assigned, to sind one as near as
  may be equal to it, in Numbers non exceeding a Number given, and in
  the smallest Terms.}
  \emph{As (for instance), the Fraction $\frac{2684769}{8376571}$ (or the
  Proportion of 2684769 to 8376571) being assigned, to sind one equal to it
  (if it may be) or at least the next Greater, or the next Lesser,
  which may be expressed in Numbers not greater than 999; that is, in numbers
  not exceeding three places.}
  \begin{center}
  \rule{3in}{0.3mm}  \\
  \end{center}
  \emph{If the Fraction sought (whose terms are not to be greater than
  a Number given) be the Next Greater than a Fraction Proposed; divide the
  proposed Fractions Denominator by its Numerator:  If the Next-Lesser, then
  the Numerator by the Denominator, continuing the Quotient in Decimal
  Parts, to such an Accuracy as shall be sufficient; which Quotient
  for the Next-Greater, is to be the Denominator answering to the
  Numerator 1:  But for the next Lesser, it is to be
  the Numerator answering to the Denominator 1:  Completing a Fraction
  as near as shall be necessary to that Proposed, which Fraction I
  call to First Fraction Compleat:  And the same wanting the Appendage of
  Decimal parts, I call, the First Fraction Cartail'd.}
  \emph{Khen by this Appendage of the First Fraction,
  divide 1 Integer, and by the Integer Number which is Next-Less then
  the sull Quotient, (that is, in case such Quotient be just an
  Interger Number, by the Integer Next-Less than it; but is it be an Interger
  with Decimal parts annexed, than by that Integer
  without those}
  \emph{Decimal parts;) multiply both Terms of the first Fraction Compleat,
  (the Numerator and the Denominator;)  And the Products of such
  Multiplication, I call the Continual Increments of those Terms respectively.
  And so much as the Appendage of Decimal parts in such Continual Increment
  wants of 1 Integer, I call the Complements of the Appendage of the
  continual Increment.}
  \emph{Then both to the Numerator and the Denominator of the First
  Fraction, add (respectively) its continual Increment, which make the Terms
  of the Second Fraction; and these again (respectively)
  increased by the same Continual
  Increment, make the Terms of the Third Fraction:  And so onward,
  as long as the Fraction so arising hath an Appendage, which is not less
  than the Complement of the Appendage of the Continual Increment.}
  \emph{But where such Appendage becomes less than that Complement,
  that Fraction I call the Last of the First Order; which also is to
  be the First of the Second Order.''}
  \end{quote}
  Although Wallis' archaic English above is difficult to decipher,
  it appears that Wallis is describing the process of
  obtaining the convergents and intermediate fractions of
  the continued fraction representation of a rational number.
  On p. 86, Brezenski writes:
  \begin{quote}
  We have already mentioned the Dutch mathematician and astronomer
  Christiaan HUYGENS \index{Huygens, Christiaan} (The Hague, 14.4.1629 - The Hague, 8.6.1695).
  He made several contributions to continued fractions and related
  matters.
  In 1682, Huygens built an automatic planetarium.  To this end,
  he used continued fractions, as described in his book
  ``\emph{Descriptio automati planetarii}'', which was published
  after his death (The Hague, 1698).  In one year the earth
  covers 359$^{\circ}$ $45'$ $40''$ $30'''$ and Saturn 12$^{\circ}$
  $13'$ $34''$ $18'''$, which gives the ratio 77708431/2640858.
  For finding the smallest integers whose ratio is close to the preceding
  one, he divided the greatest number by the smallest, then the smallest
  by the first remainder, and so on, which is Euclid's algorithm.
  He thus got
  \begin{equation}
 + \cfrac{1}{2 + \cfrac{1}{2 + \cfrac{1}{1 +
  \cfrac{1}{5 + \cfrac{1}{1 + \cfrac{1}{4 + \ldots{}}}}}}}
  \nonumber
  \end{equation}
  for the ratio.
  The fourth convergent of this continued fraction is 206/7, which
  gave him the number of teeth for the gears of his planetarium, only
  producing an error of $40'$ in a century! [H. 177], [H. 272].
  In a work, undated but not after 1687, he treats the general problem:
  \emph{``Etant donn\'es deux grands nombres ayant entr'eux un
  certain rapport, en trouver d'autres plus petits pour les dents
  des roues qui ne soient pas incommodes par leurs grandeurs et qui
  aient entr'eux \`a peu pr\`es le m\^eme rapport,
  de telle facon qu'aucun couple de nombres plus petits ne
  fournisse un rapport plus approchant de la vraie
  valeur.''}\footnote{English translation \index{Raspide, Sandrine@de Raspide, Sandrine}
  \cite{bibref:i:sandrinederaspide}:
  \emph{If we consider two large numbers forming a given ratio,
  we need to find another set of smaller numbers for the teeth of the gearwheels,
  which are not inconvenient in their size and which bear the very same ratio
  between them, in such a way that no other pair of smaller numbers
  brings a ratio closer to the actual value.}}
  Thus Huygens was conscious of the property of best approximation
  exhibited by continued fractions.  He explained his method
  as follows:
  \emph{``Pour trouver donc des nombres plus petits qui expriment
  approximativement ce rapport, je divise le plus grand des nombres
  par le plus petit, puis le plus petit par le reste de la premi\`ere
  division et ensuite ce reste par le noveau reste \ldots{}
  Poursuivant ce calcul aussi longtemps que possible, on parvient
  enfin par la division \`a un reste 1.''}\footnote{English
  translation \index{Raspide, Sandrine@de Raspide, Sandrine}
  \cite{bibref:i:sandrinederaspide}:  \emph{Thus to find some smaller numbers that
  approximately express this ratio, I divide the largest of
  the numbers by the smallest, then the smallest by the
  remainder of the first division and then this remainder by
  the new remainder, continuing this calculation as long as possible,
  we finally end up with a division into a remainder of 1.}}
  Then he makes the following comments:
  \emph{``Or, lorsqu'on n\'eglige \`a partir d'une fraction
  quelconque les derniers termes de la s\'erie et celles qui
  la suivent, et qu'on r\'eduit les autres plus le
  nombre entier \`a un commun d\'enominateur, le rapport de ce
  dernier au num\'erateur, sera voisin de celui du plus
  petit nombre donn\'e au plus grand; et la diff\'erence
  sera si faible qu'il serait impossible d'obtenir un meilleur accord
  avec des nombres plus petits.''}\footnote{English
  translation \index{Raspide, Sandrine@de Raspide, Sandrine}
  \cite{bibref:i:sandrinederaspide}:
  \emph{However, when, from an ordinary fraction, we neglect
  the last terms of the run and the ones that follow, and when
  we reduce the others plus the integer to a common denominator,
  the ratio of the latter to the numerator will be in the neighborhood
  of the smallest given number to the largest; and the difference will
  be so small that it would be impossible to obtain a better
  approximation with smaller numbers.}}
  He proves this result and applies it to the continued fraction
  for $\pi$.
  Let us give the opinion of the French astronomer
  \index{Delambre, Jean Baptiste Joseph}Jean Baptiste
  Joseph DELAMBRE (Amiens, 19.9.1749 - Paris, 19.8.1822), about
  this part of Huygens' work.  It is quite interesting [H. 108]:
  \emph{`` \ldots{}; enfin il d\'ecrit son plan\'etaire.}\footnote{English
  translation \index{Raspide, Sandrine@de Raspide, Sandrine}
  \cite{bibref:i:sandrinederaspide}:
  \emph{\ldots{}; finally, he describes his planetarium.}}
  \emph{Ces sortes de machines ne sont que des objets de
  curiosit\'e pour les amateurs, ils sont absolument inutiles
  \`a l'Astronomie; celle \index{Huygens, Christiaan}d'Huygens
  \'etait destin\'ee \`a montrer
  les mouvements elliptiques des plan\`etes, suivant les id\'ees
  de \index{Kepler, Johannes}K\'epler.  Le probl\`eme \`a r\'esoudre \'etait celui-ci:
  Etant donn\'e deux grands nombres, trouver deux autres nombres plus
  pitits et plus commodes, qui soient \`a peu pr\`es dans la m\^eme raison.
  Il y emploie les fractions continues, et sans donner la
  th\'eorie analytique de ces fractions, il les applique \`a des
  exemples.  Il trouve ainsi le nombre des dents qui'il convient de donner
  aux roues.}\footnote{English translation \index{Raspide, Sandrine@de Raspide, Sandrine}
  \cite{bibref:i:sandrinederaspide}:  \emph{These kinds of machines are
  mere objects of curiosity for the amateurs, completely useless to astronomy;
  Huygens' machine was meant to demonstrate the elliptic movements of the
  planets, following Kepler's ideas.  The problem to solve was the following:
  given two large numbers, we need to find two other numbers, smaller and
  more convenient, which are more or less in the same ratio.  To achieve
  this, Huygens uses continued ratios, and, without giving the analytic
  theory of these ratios, he applies it to some examples.  Thus, he is able
  to determine the number of teeth needed for the gearwheels.}}
  \emph{Cette propri\'et\'e des fractions continues, para\^{\i}t \`a
  \index{Lagrange, Joseph-Louis}Lagrange, une des principales d\'ecouvertes
  d'Huygens.  Cet \'eloge
  un peu exag\'er\'e fut sans doute dict\'e \`a
  Lagrange par l'usage qu'il a su faire de ces fractions dans l'Analyse.
  Quelques g\'eom\`etres ont paru douter des avantages de ces fractions et
  de l'utilit\'e
  qu'elles peuvent avoir dans les recherches analytiques.  Quant au
  probl\`eme des rouages, il nous semble qu'on peut le r\'esoudre d'une
  mani\`ere plus simple et plus commode par l'Arithm\'etique ordinaire.
  Nous avons d\'ej\`a appliqu\'e notre m\'ethode
  aux intercalations du calendrier.  Nous allons l'appliquer aux deux
  exemples choisis par Huyhens.''}\footnote{English
  translation \index{Raspide, Sandrine@de Raspide, Sandrine}
  \cite{bibref:i:sandrinederaspide}:
  \emph{The property of continued fractions seems, to Lagrange,
  one of the main discoveries of Huygens.  This slightly overdone
  praise was probably induced in Lagrange for the use that he made of
  the fractions in his Analysis.  Some surveyors seemed to have questioned
  the advantages of these fractions and their use in analytical research.
  As far as the gearing problem is concerned, it seems to us that we can
  solve it in a simpler and easier way with ordinary arithmetic.
  We have already applied our methodology to the intercalation of the calendar.
  We are going to apply it to the two examples chosen by Huygens.}}
  Delambre concludes:
  \emph{``Les fractions continues ne m'ont jamais paru qu'une chose
  curieuse qui, au reste, ne servait qu'\`a obscurcir et compliquer et je
  n'en ai jamais fait d'usage que pour m'en d\'emontrer
  l'inutilit\'e.''}\footnote{English translation
  \index{Raspide, Sandrine@de Raspide, Sandrine}
  \cite{bibref:i:sandrinederaspide}:
  \emph{Continued fractions never appeared to me as something more
  than a mere curiosity that, at the end of the day, only serves
  to darken and complicate matters, and I only used them to
  demonstrate their uselessness.}}
  This was not a prophetic view!
  \end{quote}
  Thus, it is clear that the use of continued fraction convergents
  as best rational approximations dates back to at least the
 th century (this is the first part of
  Theorem \ref{thm:ccfr0:scba0:cfenclosingneighbors}).  However,
  the details of the historical appearance of the second part of
  Theorem \ref{thm:ccfr0:scba0:cfenclosingneighbors} (the formula
  for the other Farey neighbor, Eq. \ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01})
  are not known to the authors.
  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  \section{Overview Of The Apparatus}
  %Section tag: PAR0
  The apparatus of continued fractions is best viewed as
  an alternate apparatus for representing real numbers.
  Knowledge of the first $n$ partial quotients of
  the continued fraction representation of a real number
  $x$ is equivalent to the knowledge that the number lies
  in a certain partition (Eqns.
  \ref{eq:ccfr0:spar0:01},
  \ref{eq:ccfr0:spar0:02}, and \ref{eq:ccfr0:spar0:03}).  With additional
  partial quotients, the partitions become more restrictive.
  \begin{equation}
  \label{eq:ccfr0:spar0:01}
  (x=[a_0] \vee x=[a_0; \ldots ] ) \leftrightarrow (a_0 \leq x < a_0 + 1)
  \end{equation}
  \begin{equation}
  \label{eq:ccfr0:spar0:02}
  (x=[a_0; a_1] \vee x=[a_0; a_1, \ldots ] ) \leftrightarrow
  \left(
  {
  a_0 + \frac{1}{a_1 + 1} < x \leq a_0 + \frac{1}{a_1}
  }
  \right)
  \end{equation}
  \begin{equation}
  \label{eq:ccfr0:spar0:03}
  \begin{array}{c}
   (x=[a_0; a_1, a_2] \vee x=[a_0; a_1, a_2, \ldots ] ) \vspace{0.05in}\\
  \updownarrow \vspace{0.0in}\\
  \left(
  {
  a_0+\cfrac{1}{a_1 + \cfrac{1}{a_2}} \leq x < a_0+\cfrac{1}{a_1 + \cfrac{1}{a_2+1}}
  }
  \right)
  \end{array}
  \end{equation}
  Algorithms for finding the continued fraction representation
  of a real number are best viewed as algorithms for
  determining in which partition a real number lies.  However, what is
  special (for our purposes) is that the partitions imposed by the
  apparatus of continued fractions have a special relationship
  with best rational approximations---namely, that all numbers (both
  rational and irrational) with the same partial quotients up to a
  point also have the same Farey neighbors up to a certain order.
  Stated more colloquially, the apparatus of continued fractions
  hacks up the real number line in a way that is especially meaningful
  for finding best rational approximations.
  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  \section[CF Representation Of Rationals]
          {Continued Fraction Representation Of Rational Numbers}
  %Section tag:  CRN0
  Without proof, we present the following algorithm, Algorithm
  \ref{alg:ccfr0:scrn0:akgenalg}, for
  determining the continued fraction representation (i.e. the partial
  quotients) of a non-negative
  rational number $a/b$.
  \begin{vworkalgorithmstatementpar}{Continued Fraction Representation Of
                                     A Rational Number \mbox{\boldmath $a/b$}}
  \label{alg:ccfr0:scrn0:akgenalg}
  \begin{alglvl0}
  \item $k:=-1$.
  \item $divisor_{-1} := a$.
  \item $remainder_{-1} := b$.
  \item Repeat
  \begin{alglvl1}
  \item $k := k + 1$.
  \item $dividend_k := divisor_{k-1}$.
  \item $divisor_k  := remainder_{k-1}$.
  \item $a_k :=  dividend_k \; div \; divisor_k$.
  \item $remainder_k := dividend_k \; mod \; divisor_k$.
  \end{alglvl1}
  \item Until ($remainder_k = 0$).
  \end{alglvl0}
  \end{vworkalgorithmstatementpar}
  %\vworkalgorithmfooter{}
  \begin{vworkexamplestatement}
  \label{ex:ccfr0:scrn0:01}
  Find the continued fraction partial quotients of
  $67/29$.\footnote{This example is reproduced from
  Olds \cite{bibref:b:OldsClassic}, p. 8.}
  \end{vworkexamplestatement}
  \begin{vworkexampleparsection}{Solution}
  \begin{table}
  \caption{Continued Fraction Partial Quotients Of $67/29$ (Example \ref{ex:ccfr0:scrn0:01})}
  \label{tbl:ccfr0:scrn0:01}
  \begin{center}
  \begin{tabular}{|c|c|c|c|c|}
  \hline
  \small{Index} & \small{$dividend_k$}  & \small{$divisor_k$} & \small{$a_k$}   & \small{$remainder_k$} \\
  \small{($k$)} &                       &                     &                 &                       \\
  \hline
  \hline
  \small{-1}    & \small{N/A}           & \small{67}          & \small{N/A}     & \small{29}            \\
  \hline
  \small{0}     & \small{67}            & \small{29}          & \small{2}       & \small{9}             \\
  \hline
  \small{1}     & \small{29}            & \small{9}           & \small{3}       & \small{2}             \\
  \hline
  \small{2}     & \small{9}             & \small{2}           & \small{4}       & \small{1}             \\
  \hline
  \small{3}     & \small{2}             & \small{1}           & \small{2}       & \small{0}             \\
  \hline
  \end{tabular}
  \end{center}
  \end{table}
  Table \ref{tbl:ccfr0:scrn0:01} shows the application of
  Algorithm \ref{alg:ccfr0:scrn0:akgenalg} to find the
  continued fraction partial quotients of $67/29$.  From
  Table \ref{tbl:ccfr0:scrn0:01}, the continued fraction
  representation of $67/29$ is $[2;3,4,2]$.
  \end{vworkexampleparsection}
  \vworkexamplefooter{}
  The process of obtaining the continued fraction representation of
  a rational number is a
  process of obtaining each partial quotient $a_i$, and then processing the
  remainder at each step to obtain further partial quotients.  Noting that
  the dividend and divisor at each step come from previous remainders
  (except for $k=0$ and $k=1$) allows us to simplify notation from
  Algorithm \ref{alg:ccfr0:scrn0:akgenalg}.  If $r_i$ is used to
  denote the remainder from the division that produced $a_i$, the following
  recursive equations come immediately.
  \begin{equation}
  \label{eq:ccfr0:scrn0:00a}
  \frac{a}{b}
  =
  a_0 + \frac{r_0}{b}
  =
  a_0 + \frac{1}{\frac{b}{r_0}}
  , \; 0 < r_0 < b
  \end{equation}
  \begin{equation}
  \label{eq:ccfr0:scrn0:00b}
  \frac{b}{r_0}
  =
  a_1 + \frac{r_1}{r_0}
  , \; 0 < r_1 < r_0
  \end{equation}
  \begin{equation}
  \label{eq:ccfr0:scrn0:00c}
  \frac{r_0}{r_1}
  =
  a_2 + \frac{r_2}{r_1}
  , \; 0 < r_2 < r_1
  \end{equation}
  \noindent{}Finally, nearing the termination of
  Algorithm \ref{alg:ccfr0:scrn0:akgenalg}:
  \begin{equation}
  \label{eq:ccfr0:scrn0:00d}
  \frac{r_{n-3}}{r_{n-2}}
  =
  a_{n-1} + \frac{r_{n-1}}{r_{n-2}}
  , \; 0 < r_{n-1} < r_{n-2}
  \end{equation}
  \begin{equation}
  \label{eq:ccfr0:scrn0:00e}
  \frac{r_{n-2}}{r_{n-1}}
  =
  a_n
  \end{equation}
  A natural question to ask is whether Algorithm \ref{alg:ccfr0:scrn0:akgenalg}
  will always terminate---that is, whether we can always find a continued
  fraction representation of a rational number.  We present this result
  as Lemma \ref{lem:ccfr0:scrn0:alwaysterminates}.
  \begin{vworklemmastatement}
  \label{lem:ccfr0:scrn0:alwaysterminates}
  Algorithm \ref{alg:ccfr0:scrn0:akgenalg} will always terminate:  that is,
  every rational number has a finite continued fraction representation
  $[a_0; a_1, \ldots{} , a_n]$.
  \end{vworklemmastatement}
  \begin{vworklemmaproof}
  Note in Algorithm \ref{alg:ccfr0:scrn0:akgenalg} and in
  (\ref{eq:ccfr0:scrn0:00a}) through (\ref{eq:ccfr0:scrn0:00e})
  that the remainder of one round becomes the divisor of the
  next round, hence the remainders must form a decreasing sequence
  \begin{equation}
  \label{eq:lem:ccfr0:scrn0:alwaysterminates}
  r_0 > r_1 > r_2 > \ldots{} > r_{n-2} > r_{n-1} ,
  \end{equation}
  because in general a remainder must be less than the divisor in
  the division that created it.
  \end{vworklemmaproof}
  \vworklemmafooter{}
  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  \section{Convergents And Intermediate Fractions}
  %Section tag: CNV0
  \label{ccfr0:scnf0}
  Lemma \ref{lem:ccfr0:scrn0:alwaysterminates} shows that every
  rational number has a finite continued fraction representation.  A second
  reasonable question to ask is whether every finite simple continued
  fraction corresponds to a rational number.  The most convincing way
  to answer that question would be to devise a concrete procedure for
  [re-]constructing a rational number from its continued fraction
  representation.
  Given a finite continued fraction $[a_0; a_1, \ldots{}, a_n]$, it is
  obvious that a rational number can be constructed using the same
  algebraic technique that would be applied by hand.  Such a technique
  involves ``reconstruction from the right'' because we would begin
  by using $a_n$ and then work backwards to $a_0$.  We illustrate
  the most obvious technique with an example.
  \begin{vworkexamplestatement}
  \label{ex:ccfr0:scnv0:abreconstructionfromright:01}
  Find a rational number $a/b$ corresponding to the
  continued fraction $[2;3,4,2]$.
  \end{vworkexamplestatement}
  \begin{vworkexampleparsection}{Solution}
  The most obvious technique is to write out the continued fraction and then to
  algebraically simplify the continued fraction from the bottom up (this
  is what we call ``working from the right'', as we begin with $a_n$).
  (\ref{eq:ccfr0:scnv0:ex:abreconstructionfromright:00}) through
  (\ref{eq:ccfr0:scnv0:ex:abreconstructionfromright:02})
  illustrate this technique.
  \begin{equation}
  \label{eq:ccfr0:scnv0:ex:abreconstructionfromright:00}
  [2;3,4,2] =
 + \cfrac{1}{3 + \cfrac{1}{4 + \cfrac{1}{2}}}
  \end{equation}
  \begin{equation}
  \label{eq:ccfr0:scnv0:ex:abreconstructionfromright:01}
  [2;3,4,2] =
 + \cfrac{1}{3 + \cfrac{2}{9}}
  \end{equation}
  \begin{equation}
  \label{eq:ccfr0:scnv0:ex:abreconstructionfromright:02}
  [2;3,4,2] =
 + \frac{9}{29} = \frac{67}{29}
  \end{equation}
  \end{vworkexampleparsection}
  \vworkexamplefooter{}
  Although converting a continued fraction $[a_0; a_1, \ldots{}, a_n]$
  to a rational number working ``from the right'' is the most
  intuitively obvious technique because it mirrors how a
  continued fraction would most naturally be simplified by
  hand, it is also possible to convert a continued fraction to
  a rational number ``from the left''.  In all subsequent
  discussions we embrace the ``from the left'' technique because
  it allows us to more economically calculate \emph{convergents}, which
  have special properties, and which we now describe.
  \index{continued fraction!convergent}
  The \emph{kth order convergent} of a continued fraction
  $[a_0; a_1, \ldots{}, a_n]$ is the irreducible rational number
  corresponding to $[a_0; a_1, \ldots{}, a_k]$, $k \leq n$.
  In other words, the $k$th order convergent is the irreducible rational number
  corresponding to the first $k+1$ partial quotients of a
  continued fraction.\footnote{``$k+1$'' because the notational
  numbering
  for partial quotients starts at 0 rather than 1.}
  An $n$th order continued fraction $[a_0; a_1, \ldots{}, a_n]$
  has $n+1$ convergents, $[a_0]$,
  $[a_0; a_1]$, \ldots{}, and $[a_0; a_1, \ldots{}, a_n]$.
  We denote the $k$th order convergent as $s_k$, with numerator
  $p_k$ and denominator $q_k$.
  \begin{vworkexamplestatement}
  \label{ex:ccfr0:scnv0:convergentexample:01}
  Find all convergents of $[2;3,4,2]$.
  \end{vworkexamplestatement}
  \begin{vworkexampleparsection}{Solution}\hspace{-0.4em}\footnote{Canonically, it is
  required that all convergents be irreducible.  Any valid method can be used to
  calculate convergents---including algebraic simplification---so long as the
  rational numbers obtained are irreducible.}
  \begin{equation}
  s_0 = [a_0] = [2] = 2 = \frac{2}{1} = \frac{p_0}{q_0}
  \end{equation}
  \begin{equation}
  s_1 = [a_0;a_1] = [2;3] = 2 + \frac{1}{3} = \frac{7}{3} = \frac{p_1}{q_1}
  \end{equation}
  \begin{equation}
  s_2 = [a_0;a_1,a_2] =
  [2;3,4] =
 + \cfrac{1}{3 + \cfrac{1}{4}} = \frac{30}{13} = \frac{p_2}{q_2}
  \end{equation}
  \begin{equation}
  s_3 = [a_0;a_1,a_2,a_3] = [2;3,4,2] =
 + \cfrac{1}{3 + \cfrac{1}{4 + \cfrac{1}{2}}} = \frac{67}{29} = \frac{p_3}{q_3}
  \end{equation}
  \end{vworkexampleparsection}
  \vworkexamplefooter{}
  We now move on to the question of how to convert a continued fraction
  to a rational number ``from the left''.  We present the
  canonical algorithm for construction of convergents ``from the left''.
  In addition
  to producing irreducible rational numbers (we prove this property
  later), the algorithm is
  convenient because it is economical---lower-order convergents
  are used in the calculation of higher-order convergents and there
  are no wasted calculations.
  \begin{vworktheoremstatementpar}{Rule For Canonical Construction Of Continued Fraction
                                   Convergents}
  \label{thm:ccfr0:scnv0:canonicalconvergentconstruction}
  The numerators $p_i$ and the denominators $q_i$ of the $i$th
  convergent $s_i$ of the continued fraction
  $[a_0;a_1, \ldots{} , a_n]$ satisfy the equations
  \begin{eqnarray}
  \label{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:01}
  p_i & = & a_i p_{i-1} + p_{i-2}  \\
  \label{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:02}
  q_i & = & a_i q_{i-1} + q_{i-2}
  \end{eqnarray}
  \noindent{}with the initial values
  \begin{eqnarray}
  \label{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:03}
  p_0 = a_0, & & p_1 = a_0 a_1 + 1, \\
  \label{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:04}
  q_0 = 1, & &   q_1 = a_1 .
  \end{eqnarray}
  \end{vworktheoremstatementpar}
  \begin{vworktheoremproof}\hspace{-0.4em}\footnote{Reproduced nearly
  verbatim from \cite{bibref:b:OldsClassic}, Theorem 1.3, pp. 21-23.}
  The proof is inductive.  First, the case of $i=2$ is verified,
  then an inductive step is used to show that the theorem applies
  for $i \geq 3$.
  To create a canonical form, we assign
  $s_0 = [a_0] = p_0/q_0 = a_0/1$.  Thus, in all cases, $p_0 = a_0$
  and $q_0 = 1$.  Similarly, to create a unique canonical form,
  \begin{equation}
  \label{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:05}
  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} ,
  \end{equation}
  \noindent{}and canonically, $p_1 = a_0 a_1 + 1$ and $q_1 = a_1$.
  For $i=2$, we need to verify that the algebraic results coincide with the
  claims of the theorem.  Simplifying $s_2$ algebraically leads to
  \begin{equation}
  \label{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:06}
  \begin{array}{c}
  s_2 = [a_0;a_1,a_2] =
  a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2}} =
  a_0 + \cfrac{1}{\cfrac{a_1 a_2 + 1}{a_2}} = a_0 + \cfrac{a_2}{a_1 a_2 + 1}  \\
  \\
  =\cfrac{a_0 (a_1 a_2 + 1) + a_2}{a_1 a_2 + 1}
  =\cfrac{a_2(a_0 a_1 + 1) + a_0}{a_2 a_1 + 1} .
  \end{array}
  \end{equation}
  \noindent{}On the other hand, applying the recursive formula
  claimed by the theorem (Eqns.
  \ref{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:01},
  \ref{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:02}) yields
  \begin{equation}
  \label{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:07}
  s_2 = \frac{a_2 p_1 + p_0}{a_2 q_1 + q_0}
  = \frac{a_2(a_0 a_1 + 1) + a_0}{a_2 (a_1) + 1} ,
  \end{equation}
  which, on inspection, is consistent with the results of
  (\ref{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:06}).
  We now prove the inductive step.  Assume that
  the recursive relationships supplied as
  (\ref{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:01})
  and (\ref{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:02})
  hold up through some $s_k = p_k/q_k$.  We would like to show that
  (\ref{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:01})
  and (\ref{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:02})
  then hold for $s_{k+1}$.
  $s_k$ is a fraction of the form
  \begin{equation}
  \label{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:07b}
  s_k
  =
  [a_0; a_1, a_2, \ldots , a_k]
  =
  a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2
      + \cfrac{1}{\;\;\;\;\;\;\;\;\;\;\;\;\;\;\ldots +
          \cfrac{1}{a_{k-1} + \cfrac{1}{a_k}}}}} .
  \end{equation}
  In order to form $s_{k+1}$, note that we can replace $a_k$ by
  $a_k + 1/a_{k + 1}$.  (Note that there is no requirement
  in Eqns. \ref{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:01},
  \ref{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:02},
  \ref{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:06},
  \ref{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:07},
  or \ref{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:07b}
  that the partial quotients $a_i$ be integers.)
  In other words, we can form a
  $k$th order continued fraction having the same value as a
  $k+1$th order continued fraction by substituting
  $a_k := a_k + \frac{1}{a_{k + 1}}$.  Using this substitution
  we can calculate $s_{k+1}$ using the same recursive
  relationship shown to be valid in calculating $s_k$:
  \begin{equation}
  \label{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:08}
  \begin{array}{c}
  s_{k+1} =
  \cfrac
  {\left( {a_k+\cfrac{1}{a_{k+1}} } \right) p_{k-1} + p_{k-2}}
  {\left( {a_k+\cfrac{1}{a_{k+1}} } \right) q_{k-1} + q_{k-2}}
  =
  \cfrac
  {(a_k a_{k+1} + 1) p_{k-1} + a_{k+1} p_{k-2}}
  {(a_k a_{k+1} + 1) q_{k-1} + a_{k+1} q_{k-2}} \\
    \\
  =
  \cfrac
  {a_{k+1} (a_k p_{k-1} + p_{k-2}) + p_{k-1}}
  {a_{k+1} (a_k q_{k-1} + q_{k-2}) + q_{k-1}}
  \end{array}
  \end{equation}
  Now, we can use the assumption that the recursive relationships
  hold for $s_k$, i.e.
  \begin{eqnarray}
  \label{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:09}
  p_k = a_k p_{k-1} + p_{k-2} \\
  \label{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:10}
  q_k = a_k q_{k-1} + q_{k-2}
  \end{eqnarray}
  Substituting
  (\ref{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:09}) and
  (\ref{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:10}) into
  (\ref{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:08}) yields
  \begin{equation}
  \label{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:11}
  s_{k+1} = \frac{p_{k+1}}{q_{k+1}}
  = \frac{a_{k+1} p_k + p_{k-1}}{a_{k+1} q_k + q_{k-1}}  .
  \end{equation}
  \noindent{}This completes the inductive step and the proof.
  \end{vworktheoremproof}
  \begin{vworktheoremparsection}{Remarks}
  Note that this algorithm gives a way to convert a continued fraction
  $[a_0;a_1,\ldots{},a_n]$ to a rational number $a/b$, as the value of
  a continued fraction is the value of the final convergent $s_n$.
  Note also that it is possible to convert a continued fraction to
  a rational number starting from $a_n$ (i.e. working ``from
  the right''), and that starting with $a_n$ is probably the
  more intuitive approach.
  \end{vworktheoremparsection}
  \vworktheoremfooter{}
  It is sometimes convenient to consider a convergent of order
  $-1$ (\cite{bibref:b:KhinchinClassic}, p. 5), and for
  algebraic convenience to adopt the convention that
  $p_{-1} = 1$ and $q_{-1} = 0$.  If this is done, the recursive
  relationships of Theorem \ref{thm:ccfr0:scnv0:canonicalconvergentconstruction}
  apply for $k \geq 1$ rather than for $k \geq 2$.  All of the subsequent
  theorems and proofs assume this convention.
  We now prove several properties of convergents.
  \begin{vworktheoremstatement}
  \label{thm:ccfr0:scnv0:crossproductminusone}
  For all $k \geq 0$,
  \begin{equation}
  \label{eq:ccfr0:scnv0:thm:crossproductminusone:00}
  q_k p_{k-1} - p_k q_{k-1} = (-1)^k
  \end{equation}
  \end{vworktheoremstatement}
  \begin{vworktheoremproof}\hspace{-0.4em}\footnote{From
  \cite{bibref:b:KhinchinClassic}, Theorem 2, p. 5.}
  Multiplying (\ref{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:01})
  by $p_{k-1}$, multiplying
  (\ref{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:02}) by
  $q_{k-1}$, then subtracting the equations yields
  \begin{equation}
  \label{eq:ccfr0:scnv0:thm:crossproductminusone:01}
  q_k p_{k-1} - p_k q_{k-1} = -(q_{k-1} p_{k-2} - p_{k-1} q_{k-2}) ,
  \end{equation}
  and since $q_0 p_{-1} - p_0 q_{-1} = 1$, the theorem is
  proved.
  \end{vworktheoremproof}
  \begin{vworktheoremparsection}{Corollary I}
  For all $k \geq 1$,
  \begin{equation}
  \label{eq:ccfr0:scnv0:thm:crossproductminusone:02}
  \frac{p_{k-1}}{q_{k-1}} - \frac{p_k}{q_k} = \frac{(-1)^k}{q_k q_{k-1}} .
  \end{equation}
  \end{vworktheoremparsection}
  \begin{vworktheoremproof}
  (\ref{eq:ccfr0:scnv0:thm:crossproductminusone:02}) can be obtained
  in a straightforward way by algebraic operations on
  (\ref{eq:ccfr0:scnv0:thm:crossproductminusone:00}).
  \end{vworktheoremproof}
  %\vworktheoremfooter{}
  \begin{vworktheoremstatement}
  \label{thm:ccfr0:scnv0:crossproductminusonebacktwo}
  For all $k \geq 1$,
  \begin{equation}
  q_k p_{k-2} - p_k q_{k-2} = (-1)^{k-1} a_k .
  \end{equation}
  \end{vworktheoremstatement}
  \begin{vworktheoremproof}\hspace{-0.4em}\footnote{From
  \cite{bibref:b:KhinchinClassic}, Theorem 3, p. 6.}
  By multiplying (\ref{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:01})
  by $q_{k-2}$ and
  (\ref{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:02})
  by $p_{k-2}$ and then subtracting the first from the
  second, we obtain, on the basis of Theorem
  \ref{thm:ccfr0:scnv0:crossproductminusone},
  \begin{equation}
  q_k p_{k-2} - p_k q_{k-2}
  = a_k (q_{k-1} p_{k-2} - p_{k-1} q_{k-2}) = (-1)^{k-1} a_k ,
  \end{equation}
  which completes the proof.
  \end{vworktheoremproof}
  \vworktheoremfooter{}
  The results in Theorems \ref{thm:ccfr0:scnv0:crossproductminusone}
  and \ref{thm:ccfr0:scnv0:crossproductminusonebacktwo} allow us
  to establish the relative ordering of convergents.
  Theorems \ref{thm:ccfr0:scnv0:crossproductminusone} and
  \ref{thm:ccfr0:scnv0:crossproductminusonebacktwo} demonstrate that
  even-ordered convergents form an increasing sequence and that odd-ordered
  convergents form a decreasing sequence, and that every odd-ordered convergent
  is greater than every even-ordered convergent.
  \begin{vworktheoremstatement}
  \label{thm:ccfr0:scnv0:irreducibility}
  For all $k \geq 0$, $s_k = p_k/q_k$ is
  irreducible.
  \end{vworktheoremstatement}
  \begin{vworktheoremproof}
  This proof comes immediately from the form
  of (\ref{eq:ccfr0:scnv0:thm:crossproductminusone:00}).
  Without coprimality of $p_k$ and $q_k$, the difference
  of $\pm 1$ is impossible (see
  \cprizeroxrefcomma{}Lemma \ref{lem:cpri0:ppn0:000p}).
  \end{vworktheoremproof}
  %\vworktheoremfooter{}
  \begin{vworkexamplestatement}
  \label{ex:ccfr0:scrn0:abreconstruction:01}
  Find an irreducible rational number $a/b$ corresponding to the
  continued fraction $[2;3,4,2]$.
  \end{vworkexamplestatement}
  \begin{vworkexampleparsection}{Solution}
  Application of Theorem \ref{thm:ccfr0:scnv0:canonicalconvergentconstruction}
  yields the following convergents.  The final convergent $s_3$ is the
  value of the continued fraction $[2;3,4,2]$ and Theorem
  \ref{thm:ccfr0:scnv0:irreducibility} assures us that each convergent is
  irreducible.
  \begin{equation}
  \label{eq:ccfr0:scrn0:02a}
  p_{-1} = 1, \; q_{-1} = 0
  \end{equation}
  \begin{equation}
  \label{eq:ccfr0:scrn0:02b}
  s_0 = \frac{p_0}{q_0} = \frac{a_0}{1} = \frac{2}{1}
  \end{equation}
  \begin{equation}
  \label{eq:ccfr0:scrn0:02c}
  s_1 = \frac{p_1}{q_1} = \frac{a_1 p_0 + p_{-1}}{a_1 q_0 + q_{-1}}
      = \frac{(3)(2) + (1)}{(3)(1)+(0)}
      = \frac{7}{3}
  \end{equation}
  \begin{equation}
  \label{eq:ccfr0:scrn0:02d}
  s_2 = \frac{p_2}{q_2} = \frac{a_2 p_1 + p_{0}}{a_2 q_1 + q_{0}}
      = \frac{(4)(7) + (2)}{(4)(3)+(1)}
      = \frac{30}{13}
  \end{equation}
  \begin{equation}
  \label{eq:ccfr0:scrn0:02e}
  s_3 = \frac{p_3}{q_3} = \frac{a_3 p_2 + p_{1}}{a_3 q_2 + q_{1}}
      = \frac{(2)(30) + (7)}{(2)(13)+(3)}
      = \frac{67}{29}
  \end{equation}
  Note that this result coincides with
  Example \ref{ex:ccfr0:scrn0:01}.
  \end{vworkexampleparsection}
  \vworkexamplefooter{}
  We've shown in Algorithm \ref{alg:ccfr0:scrn0:akgenalg}
  that any rational number can be expressed as a continued fraction, and
  with Theorem \ref{thm:ccfr0:scnv0:canonicalconvergentconstruction}
  that any finite continued fraction can be converted to a rational
  number.  Although we don't say more until Section \ref{ccfr0:scin0},
  it follows directly that any irrational number results in
  an \emph{infinite} (or non-terminating) continued fraction, and that
  any infinite continued fraction represents an irrational number.
  In the theorems that follow, we don't treat infinite continued
  fractions with mathematical rigor, because our emphasis is on
  specific applications of continued fractions.
  \begin{vworktheoremstatement}
  \label{thm:ccfr0:scnv0:evenslessthanoddsgreaterthan}
  For a finite continued fraction representation of
  the [rational] number $\alpha$, every even-ordered convergent
  is less than $\alpha$ and every odd-ordered convergent is
  greater than $\alpha$, with the exception of the final convergent
  $s_n$, which is equal to $\alpha$.
  For an infinite continued fraction corresponding to the
  [irrational] real
  number $\alpha$, every even-ordered convergent is less than
  $\alpha$, and every odd-ordered convergent is greater than
  $\alpha$.
  \end{vworktheoremstatement}
  \begin{vworktheoremparsection}{Proof (Informal)}
  In the case of a finite continued fraction, the proof is obvious
  and immediate.  Since $s_n$, the final convergent, is equal
  to the rational number $\alpha$, Theorems \ref{thm:ccfr0:scnv0:crossproductminusone}
  and \ref{thm:ccfr0:scnv0:crossproductminusonebacktwo} demonstrate this
  unequivocally.
  In the case of an infinite continued fraction,
  note the form of the proof of Theorem
  \ref{thm:ccfr0:scnv0:canonicalconvergentconstruction},
  where the substitution of $a_k := a_k + 1/a_{k+1}$
  is made.  It can be demonstrated that for any even-ordered
  convergent $s_k$, additional partial quotients (except
  $a_{k+1} = a_n = 1$, which isn't allowed in general or even
  possible with an infinite continued fraction) can only
  increase the value.  It can similarly be demonstrated that
  additional partial quotients can only decrease the value
  of an odd-ordered convergent.  Because the continued fraction
  is infinite, any particular even-ordered convergent will be
  increased if more partial quotients are allowed, and any particular
  odd-ordered convergent will be decreased in value if more
  partial quotients are allowed.  Thus, we can conclude that
  all even-ordered convergents are less than the value of
  $\alpha$, and all odd-ordered convergents are greater
  than the value of $\alpha$.\footnote{To make this proof more
  formal would require the discussion of \emph{remainders},
  which wouldn't contribute to the applications discussed in this
  work.}
  \end{vworktheoremparsection}
  %\vworktheoremfooter{}
  \begin{vworktheoremstatement}
  \label{thm:ccfr0:scnv0:minimumrateofconvergentdenominatorincrease}
  For $k \geq 2$,
  \begin{equation}
  q_k \geq 2^{\frac{k-1}{2}} .
  \end{equation}
  \end{vworktheoremstatement}
  \begin{vworktheoremproof}\hspace{-0.4em}\footnote{From
  \cite{bibref:b:KhinchinClassic}, Theorem 12, p. 13.}
  For $k \geq 2$,
  \begin{equation}
  q_k = a_k q_{k-1} + q_{k-2} \geq q_{k-1} + q_{k-2} \geq 2 q_{k-2} .
  \end{equation}
  Successive application of this inequality yields
  \begin{equation}
  q_{2k} \geq 2^k q_0 = 2^k, \; q_{2k+1} \geq 2^k q_1 \geq 2^k ,
  \end{equation}
  which proves the theorem.  Thus, the denominators of convergents
  increase at least as rapidly as the terms of a geometric
  progression.
  \end{vworktheoremproof}
  \begin{vworktheoremparsection}{Remarks}
  (1) This minimum geometric rate of increase of denominators of convergents is how
  we make the claim that Algorithms
  \ref{alg:ccfr0:scba0:cfenclosingneighborsfn} and
  \ref{alg:ccfr0:scba0:cffareyneighborfn} are $O(log \; N)$ and
  that Algorithms
  \ref{alg:ccfr0:scba0:cfenclosingneighborsfab}
  and \ref{alg:ccfr0:scba0:cffareyneighborfab} are
  $O(log \; max(h_{MAX}, k_{MAX}))$.
  (2) This theorem supplies the \emph{minimum} rate of increase,
  but the demonominators of convergents can increase much faster.  To achieve
  the minimum rate of increase, every $a_k$ must be 1, which occurs
  only with the continued fraction representation of
  $\sqrt{5}/2 + 1/2$ (the famous \index{golden ratio}golden ratio).
  (See also Exercise \ref{exe:cfr0:sexe0:c01}.)
  \end{vworktheoremparsection}
  \vworktheoremfooter{}
  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  Since Theorem \ref{thm:ccfr0:scnv0:canonicalconvergentconstruction}
  provides a concrete
  procedure for going from a continued fraction $[a_0; a_1, \ldots{} , a_n]$
  to a rational number $a/b$ that, when Algorithm \ref{alg:ccfr0:scrn0:akgenalg}
  is applied, will again result in $[a_0; a_1, \ldots{} , a_n]$, we have
  successfully demonstrated that every continued fraction
  $[a_0; a_1, \ldots{} , a_n]$ corresponds to [at least one]
  rational number $a/b$.
  The next natural questions to ask are questions of representation
  uniqueness and the nature of the mapping between the set of rational numbers
  and the set of continued fractions.  For example, will 32/100 and 64/200 have
  the same continued fraction representation $[a_0; a_1, \ldots{} , a_n]$?
  Do two different continued fractions ever correspond
  to the same rational number?  We answer these questions now.
  Algorithm \ref{alg:ccfr0:scrn0:akgenalg} will produce the
  same $[a_0; a_1, \ldots{} , a_n]$ for any $ia/ib$, i.e. all rational numbers
  which are equivalent in value will generate the same continued fraction
  representation (see Lemma \ref{lem:ccfr0:scrn0:aoverbneednotbeirreducible}).
  It was hinted in the introduction (Section
  \ref{ccfr0:sint0}, Footnote \ref{footnote:ccfr0:sint0:00})
  that, except in the case of representing an integer, it is
  not allowed for the final partial quotient $a_n$ to be 1.
  We now explain the reasons why this must be disallowed.  First,
  if $a_n = 1$, then $a_{n-1}$ can be increased by 1 and
  the continued fraction can be reduced in order
  by 1 and while still preserving its value.  For example, it
  can easily be verified that $[1;2,3,3,1]$ and $[1;2,3,4]$
  represent the same number.  However, this observation alone
  is not enough to recommend a canonical form---this observation
  does not suggest that  $[1;2,3,4]$ should be preferred
  over $[1;2,3,3,1]$.  However, what \emph{can} be noted is that
  that a continued fraction representation with $a_n=1$, $n>0$
  cannot be attained using Algorithm \ref{alg:ccfr0:scrn0:akgenalg} or
  (\ref{eq:ccfr0:scrn0:00a}) through (\ref{eq:ccfr0:scrn0:00e}),
  because a form with $a_n=1$, $n>0$ violates the assumption that
  successive remainders are ever-decreasing (see Eq.
  \ref{eq:lem:ccfr0:scrn0:alwaysterminates}).  The property that
  remainders are ever-decreasing is a necessary condition in
  proofs of some important properties, and so requiring
  that $a_n \neq{} 1$, $n>0$
  is the most natural convention for a canonical form.
  \begin{vworklemmastatement}
  \label{lem:ccfr0:scrn0:aoverbneednotbeirreducible}
  Algorithm \ref{alg:ccfr0:scrn0:akgenalg} will
  produce the same result
  $[a_0; a_1, \ldots{} , a_n]$ for any
  $ia/ib$, i.e. $a/b$ need not be reduced before the algorithm
  is applied.
  \end{vworklemmastatement}
  \begin{vworklemmaproof}
  Assume that $a/b$ is irreducible, and that $ia/ib$,
  $i \in \{ 2, 3, \ldots \}$ is used as input to
  the algorithm.  By definition, any rational number
  with the same value as $a/b$ is of the form $ia/ib$,
  $i \in \vworkintsetpos$.
  Note that (\ref{eq:ccfr0:scrn0:00a}) through
  (\ref{eq:ccfr0:scrn0:00e}) ``scale up'', while still producing
  the same partial quotients $[a_0; a_1, \ldots{} , a_n]$.
  Specifically:
  \begin{equation}
  \label{eq:ccfr0:scrn0:10a}
  \frac{ia}{ib}
  =
  a_0 + \frac{ir_0}{ib}
  =
  a_0 + \frac{1}{\frac{ib}{ir_0}}
  \end{equation}
  \begin{equation}
  \label{eq:ccfr0:scrn0:10b}
  \frac{ib}{ir_0}
  =
  a_1 + \frac{ir_1}{ir_0}
  \end{equation}
  \begin{equation}
  \label{eq:ccfr0:scrn0:10c}
  \frac{ir_0}{ir_1}
  =
  a_2 + \frac{ir_2}{ir_1}
  \end{equation}
  \noindent{}Finally, nearing the termination of
  Algorithm \ref{alg:ccfr0:scrn0:akgenalg}:
  \begin{equation}
  \label{eq:ccfr0:scrn0:10d}
  \frac{ir_{n-3}}{ir_{n-2}}
  =
  a_{n-1} + \frac{ir_{n-1}}{ir_{n-2}}
  \end{equation}
  \begin{equation}
  \label{eq:ccfr0:scrn0:10e}
  \frac{ir_{n-2}}{ir_{n-1}}
  =
  a_n
  \end{equation}
  Thus, it is easy to show that Algorithm \ref{alg:ccfr0:scrn0:akgenalg}
  will produce the same continued fraction representation regardless of whether
  the input to the algorithm is reduced.  It is also easy to show that the
  last non-zero remainder as the algorithm is applied ($r_{n-1}$, in
  Eqns. \ref{eq:ccfr0:scrn0:10d} and \ref{eq:ccfr0:scrn0:10e})
  is the greatest common divisor of $ia$ and $ib$ (this is done
  in the proof of Algorithm \ref{alg:ccfr0:sega0:euclidsgcdalgorithm}).
  \end{vworklemmaproof}
  %\vworklemmafooter{}
  \begin{vworklemmastatement}
  \label{lem:ccfr0:scrn0:cfrepresentationisunique}
  So long as $a_n \neq 1$, $n>0$, a rational number $a/b$ has only
  one [unique] continued fraction representation
  $[a_0; a_1, \ldots{} , a_n]$.
  \end{vworklemmastatement}
  \begin{vworklemmaproof}
  Assume that two different continued fractions,
  $[a_0; a_1, \ldots{} , a_m]$ and
  $[\overline{a_0}; \overline{a_1}, \ldots{} , \overline{a_n}]$,
  correspond to the same rational number $a/b$.  By
  \emph{different}, we mean either that $m=n$ but
  $\exists i, a_i \neq \overline{a_i}$, or that $m \neq n$.
  Note that Theorem \ref{thm:ccfr0:scnv0:canonicalconvergentconstruction}
  will map from any continued fraction to an irreducible rational
  number $a/b$.  Assume we apply
  Theorem \ref{thm:ccfr0:scnv0:canonicalconvergentconstruction} to
  $[a_0; a_1, \ldots{} , a_m]$ to produce $a/b$, and
  to $[\overline{a_0}; \overline{a_1}, \ldots{} , \overline{a_n}]$
  to produce $\overline{a}/\overline{b}$.  Because two irreducible
  rational numbers are equal iff their components are
  equal,
  $[(a/b) = (\overline{a}/\overline{b})] \vworkhimp{} %
  [(a = \overline{a}) \wedge (b = \overline{b})]$.  Because
  $a/b = \overline{a}/\overline{b}$, we denote both of these
  numbers simply as $a/b$.
  By (\ref{eq:ccfr0:scrn0:11a}),
  $a = a_0 b + r_0 = \overline{a_0} b + \overline{r_0}$,
  $0 < r_0, \overline{r_0} < b$.  Because
  $r_0, \overline{r_0} < b$, there is only one combination
  of $a_0$ and $r_0$ or of $\overline{a_0}$ and
  $\overline{r_0}$ that can result in $a$.  Thus, we can conclude
  that $a_0 = \overline{a_0}$ and
  $r_0 = \overline{r_0}$.  This type of reasoning, can be
  carried ``downward'' inductively, each time fixing
  $a_{i}$ and $r_{i}$.  Finally, we must conclude
  that $(a/b = \overline{a}/\overline{b}) \vworkhimp %
  [a_0; a_1, \ldots{} , a_m] = %
  [\overline{a_0}; \overline{a_1}, \ldots{} , \overline{a_n}]$
  and that $m=n$.
  \end{vworklemmaproof}
  \begin{vworklemmaparsection}{Remarks}
  The case of $a_n=1$, $n>0$ deserves further discussion.
  Theorem \ref{thm:ccfr0:scnv0:canonicalconvergentconstruction} will produce
  an irreducible rational number even if
  $a_n = 1$, $n>0$.  How is it that uniqueness of representation can
  be claimed when clearly, for example, $[2;3,4,2]$ and $[2;3,4,1,1]$
  are the same number?  The answer is that $a_n = 1$, $n>0$ requires
  that $r_{n-2}=r_{n-1}=1$, which violates the ``uniqueness'' assumption
  used in fixing $a_i$ and $r_i$ in the proof above---specifically note
  that the condition $0<r_{n-1}<r_{n-2}$ in (\ref{eq:ccfr0:scrn0:11d})
  is violated.  If one is allowed to violate the required
  ever-decreasing remainders, then $a_i$ and $r_i$ cannot
  be uniquely fixed at each step of the proof, above.
  \end{vworklemmaparsection}
  \vworklemmafooter{}
  \index{continued fraction!intermediate fraction}
  An \emph{intermediate fraction} is a fraction represented
  by the continued fraction representation of a $k$-th order
  convergent with the final partial quotient $a_k$ reduced
  (this can naturally only be done when $a_k > 1$).  As Khinchin
  points out (\cite{bibref:b:KhinchinClassic}, p. 14):
  ``\emph{In arithmetic applications, these intermediate
  fractions play an important role (though not as important
  a role as the convergents)}''.
  The intermediate fractions (of a $k$-th order convergent)
  form a monotonically increasing or decreasing sequence of
  fractions (\cite{bibref:b:KhinchinClassic}, p. 13):
  \begin{equation}
  \label{eq:ccfr0:scrn0:intermediatefrac01}
  \frac{p_{k-2}}{q_{k-2}},
  \frac{p_{k-2} + p_{k-1}}{q_{k-2} + q_{k-1}},
  \frac{p_{k-2} + 2 p_{k-1}}{q_{k-2} + 2 q_{k-1}},
  \ldots{} ,
  \frac{p_{k-2} + a_k p_{k-1}}{q_{k-2} + a_k q_{k-1}}
  =
  \frac{p_k}{q_k} .
  \end{equation}
  Note in (\ref{eq:ccfr0:scrn0:intermediatefrac01}) that the
  first and last fractions are not intermediate fractions (rather, they are
  convergents).
  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  \section{Euclid's GCD Algorithm}
  %Section tag: EGA0
  \index{Euclid!GCD algorithm}
  The apparatus of continued fractions is closely related to Euclid's GCD
  algorithm (in fact, historically, Euclid's GCD algorithm is considered
  a precursor of continued fractions).  It was noted in
  Lemma \ref{lem:ccfr0:scrn0:aoverbneednotbeirreducible} that the last non-zero
  remainder when Algorithm \ref{alg:ccfr0:scrn0:akgenalg} is applied
  is the greatest common divisor of $a$ and $b$.  In this section, we
  present Euclid's algorithm, prove it, and show it similarity to
  Algorithm \ref{alg:ccfr0:scrn0:akgenalg}.
  Knuth (\cite{bibref:b:knuthclassic2ndedvol2}, p. 335) presents some background
  information about Euclid's GCD algorithm:
  \begin{quote}
  Euclid's algorithm is found in Book 7, Propositions 1 and 2 of his
  \emph{Elements} (c. 300 B.C.), but it probably wasn't his own
  invention.  Some scholars believe that the method was known up to
 years earlier, at least in its subtractive form, and it
  was almost certainly known to Eudoxus (c. 375 B.C.); see
  K. von Fritz, \emph{Ann. Math.} (2) \textbf{46} 1945, 242-264.
  Aristotle (c. 330 B.C.) hinted at it in his \emph{Topics}, 158b,
 -35.  However, very little hard evidence about such early history
  has survived [see. W. R. Knorr, \emph{The Evolution of the Euclidian
  Elements} (Dordrecht:  1975)].
  We might call Euclid's method the granddaddy of all algorithms, because
  it is the oldest nontrivial algorithm that has survived to the present day.
  (The chief rival for this honor is perhaps the ancient Egyptian method
  for multiplication, which was based on doubling and adding, and which forms
  the basis for efficient calculation of \emph{n}th powers as explained
  in section 4.6.3.  \ldots{})
  \end{quote}
  \begin{vworkalgorithmstatementpar}
     {Euclid's GCD Algorithm For Greatest Common Divisor Of Positive
     Integers \mbox{\boldmath $a$}
     And \mbox{\boldmath $b$}}\hspace{-0.4em}\footnote{Knuth
  (\cite{bibref:b:knuthclassic2ndedvol2}, pp. 336-337) distinguishes between the \emph{original}
  Euclidian algorithm and the \emph{modern} Euclidian algorithm.  The algorithm presented here
  is more closely patterned after the \emph{modern} Euclidian algorithm.}
  \label{alg:ccfr0:sega0:euclidsgcdalgorithm}
  \begin{alglvl0}
  \item If ($a < b$), swap $a$ and $b$.\footnote{This step isn't strictly necessary, but is usually done
        to save one iteration.}
  \item Repeat
     \begin{alglvl1}
     \item $r := a \; mod \; b$.
     \item If ($r = 0$), STOP.
     \item $a := b$.
     \item $b := r$.
     \end{alglvl1}
  \item \textbf{Exit condition:} $b$ will be the g.c.d. of $a$ and $b$.
  \end{alglvl0}
  \end{vworkalgorithmstatementpar}
  \begin{vworkalgorithmproof}
  Olds (\cite{bibref:b:OldsClassic}, pp. 16-17) shows the
  relationship between Algorithm
  \ref{alg:ccfr0:scrn0:akgenalg} and Euclid's algorithm, and presents
  a proof, which is reproduced nearly verbatim here.
  First, note that $d$ is the GCD of $a$ and $b$ iff:
  \begin{itemize}
  \item (Necessary Condition I) $d$ divides both $a$ and $b$, and
  \item (Necessary Condition II) any common divisor $c$ of $a$ and $b$ divides $d$.
  \end{itemize}
  Essentially, we will prove that the final non-zero remainder
  when the algorithm is applied meets the two criteria above,
  and hence must be the GCD of $a$ and $b$.
  Note that (\ref{eq:ccfr0:scrn0:00a}) through
  (\ref{eq:ccfr0:scrn0:00e}) can be rewritten as
  (\ref{eq:ccfr0:scrn0:11a}) through
  (\ref{eq:ccfr0:scrn0:11e}), which make them
  consistent with the form Olds' presents.
  \begin{eqnarray}
  \label{eq:ccfr0:scrn0:11a}
  a   = a_0 b   +   r_0, && 0 < r_0 < b                          \\
  \label{eq:ccfr0:scrn0:11b}
  b   = a_1 r_0 +   r_1, && 0 < r_1 < r_0                        \\
  \label{eq:ccfr0:scrn0:11c}
  r_0 = a_2 r_1 +   r_2, && 0 < r_2 < r_1                        \\
  \ldots{}\hspace{-1.67em}&&                     \nonumber       \\
  \label{eq:ccfr0:scrn0:11d}
  r_{n-3} = a_{n-1} r_{n-2} + r_{n-1}, && 0 < r_{n-1} < r_{n-2}  \\
  \label{eq:ccfr0:scrn0:11e}
  r_{n-2} = a_n     r_{n-1} + 0,       && 0 = r_n
  \end{eqnarray}
  First, we will show that \emph{Necessary Condition I}, above, is met.
  Note from (\ref{eq:ccfr0:scrn0:11e}) that $r_{n-1} \vworkdivides r_{n-2}$,
  since $r_{n-2}$ is an integer multiple of $r_{n-1}$.  Note from
  (\ref{eq:ccfr0:scrn0:11d}) that $r_{n-1} \vworkdivides r_{n-3}$, since
  $r_{n-3}$ is also an integer multiple of $r_{n-1}$.  This logic can
  be carried ``upward'' in the set of equations represented
  by (\ref{eq:ccfr0:scrn0:11a}) through (\ref{eq:ccfr0:scrn0:11e}),
  and we can finally conclude that $r_{n-1} \vworkdivides b$ and
  $r_{n-1} \vworkdivides a$.  This proves \emph{Necessary Condition I}.
  Second, we will show that \emph{Necessary Condition II}, above, is met.
  This time, in (\ref{eq:ccfr0:scrn0:11a}) through (\ref{eq:ccfr0:scrn0:11e}),
  we work top-down rather than bottom-up.  Assume that $c$ is a divisor
  of $a$ and a divisor of $b$.  Then, from the form of (\ref{eq:ccfr0:scrn0:11a}),
  $c$ divides $r_0$.\footnote{This implication may be counterintuitive
  at first glance.  It concerns "reachability" of linear combinations
  of integers with a common divisor.  Specifically, if
  $a$ and $b$ have a common divisor $c$, any linear combination
  $ia + jb$, ($i,j \in \vworkintset$),  can ``reach'' only multiples of $c$.
  In (\ref{eq:ccfr0:scrn0:11a}), $(1)(a)+(-a_0)(b)=r_0$, thus
  $r_0$ must be a multiple of $c$.  An identical argument applies for
  (\ref{eq:ccfr0:scrn0:11a}) through (\ref{eq:ccfr0:scrn0:11e}).}
  Similarly, from the form of (\ref{eq:ccfr0:scrn0:11b}),
  $c$ divides $r_1$.  This rationale can be carried ``downward'' to finally
  conclude that $c$ divides $r_{n-1}$.  Thus,
  $(c \vworkdivides a) \wedge (c \vworkdivides b) \vworkhimp (c \vworkdivides r_{n-1})$,
  where $r_{n-1}$ is the last non-zero remainder.  This proves
  \emph{Necessary Condition II}.
  Thus, $r_{n-1}$ is the GCD of $a$ and $b$.
  \end{vworkalgorithmproof}
  \begin{vworkalgorithmparsection}{Remarks}
  It is easy to observe that the only difference between
  Algorithm \ref{alg:ccfr0:scrn0:akgenalg} and
  Algorithm \ref{alg:ccfr0:sega0:euclidsgcdalgorithm} is
  that Algorithm \ref{alg:ccfr0:scrn0:akgenalg} records the
  quotient of each division, whereas
  Algorithm \ref{alg:ccfr0:sega0:euclidsgcdalgorithm}
  does not.
  \end{vworkalgorithmparsection}
  %\vworkalgorithmfooter{}
  \begin{vworkexamplestatement}
  \label{ex:ccfr0:sega0:01}
  Use Euclid's algorithm to find the greatest common divisor
  of 1,736,651 and 26,023.
  \end{vworkexamplestatement}
  \begin{vworkexampleparsection}{Solution}
  \begin{table}
  \caption{Euclid's Algorithm Applied To Find Greatest Common Divisor Of 1,736,651 and 26,023
           (Example \ref{ex:ccfr0:sega0:01})}
  \label{tbl:ex:ccfr0:sega0:01}
  \begin{center}
  \begin{tabular}{|c|c|c|c|}
  \hline
  \small{Iteration} & \small{$a$}  & \small{$b$} & \small{$r : = a \; mod \; b$}        \\
  \hline
  \hline
  \small{1}    & \small{1,736,651}           & \small{26,023}          & \small{19,133} \\
  \hline
  \small{2}    &    \small{26,023}           & \small{19,133}          &  \small{6,890} \\
  \hline
  \small{3}    &    \small{19,133}           &  \small{6,890}          &  \small{5,353} \\
  \hline
  \small{4}    &     \small{6,890}           &  \small{5,353}          &  \small{1,537} \\
  \hline
  \small{5}    &     \small{5,353}           &  \small{1,537}          &    \small{742} \\
  \hline
  \small{6}    &     \small{1,537}           &    \small{742}          &     \small{53} \\
  \hline
  \small{7}    &       \small{742}           &     \small{53}          &      \small{0} \\
  \hline
  \end{tabular}
  \end{center}
  \end{table}
  Table \ref{tbl:ex:ccfr0:sega0:01} shows the application of
  Algorithm \ref{alg:ccfr0:sega0:euclidsgcdalgorithm} (Euclid's
  GCD algorithm) to find the greatest common divisor
  of 1,736,651 and 26,023.  The last non-zero remainder (and hence
  the greatest common divisor) is 53.
  \end{vworkexampleparsection}
  \begin{vworkexampleparsection}{Remarks}
  The prime factorization of 1,736,651 is $151 \times 53 \times 31 \times 7$, and
  the prime factorization of 26,023 is $491 \times 53$, which is consistent
  with the result in Table \ref{tbl:ex:ccfr0:sega0:01}.
  \end{vworkexampleparsection}
  \vworkexamplefooter{}
  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  \section[CF Representation Of Irrationals]
          {Continued Fraction Representation Of Irrational Numbers}
  %Section tag:  CIN0
  \label{ccfr0:scin0}
  \index{continued fraction!irrational numbers@of irrational numbers}
  \index{irrational number!continued fraction representation of}Irrational
  numbers (such as $\sqrt{2}$ or $\pi$) necessarily have infinite continued
  fraction representations (i.e. the representations do not terminate).  This is clear, since
  Theorem \ref{thm:ccfr0:scnv0:canonicalconvergentconstruction} gives a concrete procedure
  for constructing a rational number from any \emph{finite} continued fraction;
  therefore a continued fraction corresponding to an irrational number
  cannot be finite.
  The algorithm for determining the partial quotients of an irrational number is
  awkward, because it is a symbolic (rather than a numerical) algorithm.
  We present the algorithm here for perspective and completeness, although it
  is not often useful in practical engineering work.  In practical work, an
  ordinary handheld calculator will supply a real number to far more precision
  than necessary, and the displayed real number can be converted to a rational
  number for the application of Algorithm \ref{alg:ccfr0:scrn0:akgenalg}.
  For practical work, it is rarely necessary to apply a Algorithm
  \ref{alg:ccfr0:scin0:symboliccfalgorithm}.
  The symbolic algorithm for determining the continued fraction partial quotients
  of a real number is a recursive process very similar to the algorithm for
  determining the continued fraction partial quotients of a rational number.
  The essential activity is choosing the largest possible integer $a_i$ in each
  iteration.
  Algorithm \ref{alg:ccfr0:scin0:symboliccfalgorithm} begins by choosing
  the largest integer $a_0$ not larger than $x$, then expressing $x$ as
  \begin{equation}
  x = a_0 + \frac{1}{x_1} .
  \end{equation}
  \noindent{}With $a_0$ chosen, $x_1$ can then be expressed as
  \begin{equation}
  x_1 = \frac{1}{x - a_0} .
  \end{equation}
  \noindent{}$x_1$ can then be expressed as
  \begin{equation}
  x_1 = a_1 + \frac{1}{x_2} ,
  \end{equation}
  \noindent{}and $a_1$, the largest integer not larger than $x_1$,
  can be chosen.
  This process can be continued indefinitely (with an irrational $x$, it won't terminate)
  to determine as many partial quotients as desired.
  \begin{vworkalgorithmstatementpar}
     {Symbolic Algorithm For Obtaining
      Continued Fraction Representation Of An Irrational Number
     \mbox{\boldmath $x$}}
  \label{alg:ccfr0:scin0:symboliccfalgorithm}
  \begin{alglvl0}
  \item $x_0 := x$ (the real number whose partial quotients are desired).
  \item $k := -1$.
  \item Repeat
     \begin{alglvl1}
     \item $k := k + 1$.
     \item $a_k := \lfloor x_k \rfloor$.
     \item $x_{k+1} := \displaystyle{\frac{1}{x_k - a_k}}$.
     \end{alglvl1}
  \item Until (as many partial quotients as desired are obtained).
  \end{alglvl0}
  \end{vworkalgorithmstatementpar}
  %\vworkalgorithmfooter{}
  \begin{vworkexamplestatement}
  \label{ex:ccfr0:scin0:symboliccfalgorithmexample}
  Find the first several continued fraction partial quotients of $\sqrt{3}$.
  \end{vworkexamplestatement}
  \begin{vworkexampleparsection}{Solution}
  Applying Algorithm \ref{alg:ccfr0:scin0:symboliccfalgorithm}:
  \begin{equation}
  x_0 := x = \sqrt{3}
  \end{equation}
  \begin{equation}
  k := -1
  \end{equation}
  \begin{equation}
  k := k+1 = 0
  \end{equation}
  \begin{equation}
  a_0 := \lfloor x_0 \rfloor = \lfloor \sqrt{3} \rfloor = 1
  \end{equation}
  \begin{equation}
  x_1 := \frac{1}{x_0 - a_0}
      = \frac{1}{\sqrt{3}-1}
      = \frac{\sqrt{3}+1}{2}
  \end{equation}
  \begin{equation}
  k := k + 1 = 1
  \end{equation}
  \begin{equation}
  a_1 := \lfloor x_1 \rfloor =
  \left\lfloor {\frac{\sqrt{3}+1}{2}} \right\rfloor = 1
  \end{equation}
  \begin{equation}
  x_2 := \frac{1}{x_1 - 1}
       = \frac{1}{\frac{\sqrt{3}+1}{2}-1}
       = \sqrt{3}+1
  \end{equation}
  \begin{equation}
  k := k + 1 = 2
  \end{equation}
  \begin{equation}
  a_2 := \lfloor x_2 \rfloor = \lfloor \sqrt{3}+1 \rfloor = 2
  \end{equation}
  \begin{equation}
  x_3 := \frac{1}{(\sqrt{3}+1)-2} = \frac{\sqrt{3}+1}{2}
  \end{equation}
  Note that $x_3 = x_1$, so the algorithm will repeat with
  $a_3=1$, $a_4=2$, $a_5=1$, $a_6=2$, etc.  Thus, the continued
  fraction representation of $\sqrt{3}$ is
  $[1;1,2,1,2,1,2, \ldots{}]$ = $[1;\overline{1,2}]$.
  \end{vworkexampleparsection}
  \begin{vworkexampleparsection}{Remarks}
  \index{continued fraction!repeating}
  It can be proved that all continued fractions that repeat or repeat
  from some point onward
  represent real numbers of the form $\frac{P \pm \sqrt{D}}{Q}$,
  where $D \in \vworkintsetpos$ is not the square of an integer.
  It can also be shown
  that all numbers of this form result in continued fractions that
  repeat or repeat from some point onward.  (See Olds
  \cite{bibref:b:OldsClassic}, Chapter 4.)  It is beyond the scope
  of our interest in continued fractions to develop these properties.
  \end{vworkexampleparsection}
  \vworkexamplefooter{}
  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  \section{Convergents As Best Approximations}
  %Section tag:  CBA0
  Up until this point, we've presented general properties of continued
  fractions and convergents without regard for practical applications.
  In this section, we present results and algorithms to use the
  apparatus of continued fractions to obtain best rational approximations.
  Although we don't dwell on other algorithms for locating best
  rational approximations (we present only the single best
  algorithm), it is worth noting that there are many naive algorithms
  for locating best rational approximations.  These include:
  \begin{itemize}
  \item  Exhaustive search of the integer lattice
         [$O(h_{MAX} k_{MAX})$].
  \item  Building the Farey series starting at an
         integer [$O(max(h_{MAX}, k_{MAX})^2)$]
             (see Algorithm \cfryzeroxrefhyphen{}\ref{alg:cfry0:sgfs0:02}).
  \item  Building the Farey series starting at a rational number with
         a large prime denominator [$O(max(h_{MAX}, k_{MAX}))$].
  \item  Building the Stern-Brocot tree (see Section \ref{ccfr0:ssbt0})
         [$O(max(h_{MAX}, k_{MAX}))$].
  \end{itemize}
  Although we don't justify it formally,
  the continued fraction algorithms presented here are
  $O(log \; max(h_{MAX}, k_{MAX}))$.\footnote{Well,
  not exactly.  In the classical computer science
  sense (speaking only in terms of number of operations),
  the algorithms are $O(log \; max(h_{MAX}, k_{MAX}))$.  However,
  if $h_{MAX}$ and $k_{MAX}$ are increased beyond the sizes
  of integers that a computer can inherently accomodate, one must
  use long integer calculation software, which requires more time for
  each integer operation than is required for machine native
  integer sizes.  As $h_{MAX}$ and $k_{MAX}$ are increased far
  beyond integer sizes accomodated inherently by the computer,
  the relationship surely is not $O(log \; max(h_{MAX}, k_{MAX}))$.}
  The basis on which we
  make that assertion is the geometric rate of
  increase of convergents (see Theorem
  \ref{thm:ccfr0:scnv0:minimumrateofconvergentdenominatorincrease}),
  which means that the number of steps required is tied to the
  logarithm of the maximum denominator involved, as it is
  necessary to obtain partial quotients and convergents only until
  $q_k \geq max(h_{MAX},k_{MAX})$.
  \begin{vworktheoremstatement}
  \label{thm:ccfr0:scba0:convergentcloseness}
  In the case of an infinite continued fraction for $k \geq 0$ or in the
  case of a finite continued fraction for $0 \leq k < n-1$, a convergent
  $s_k = p_k/q_k$ to a [rational or irrational] number
  $\alpha \in \vworkrealsetnonneg$ satisfies
  \begin{equation}
  \left| {\alpha - \frac{p_k}{q_k}} \right|
  <
  \frac{1}{q_k q_{k+1}} .
  \end{equation}
  In the case of a finite continued fraction with $k = n-1$,
  \begin{equation}
  \left| {\alpha - \frac{p_k}{q_k}} \right|
  =
  \frac{1}{q_k q_{k+1}} .
  \end{equation}
  \end{vworktheoremstatement}
  \begin{vworktheoremproof}
  The proof comes directly from Theorem
  \ref{thm:ccfr0:scnv0:crossproductminusone} (Corollary I)
  and Theorem
  \ref{thm:ccfr0:scnv0:evenslessthanoddsgreaterthan}.
  \end{vworktheoremproof}
  \begin{vworktheoremparsection}{Remarks}
  Khinchin describes this result (\cite{bibref:b:KhinchinClassic}, p. 9)
  as playing a basic role in the arithmetic
  applications of continued fractions.  In fact, this theorem is used
  in the proof of Theorem
  \ref{thm:ccfr0:scba0:cfenclosingneighbors}.
  \end{vworktheoremparsection}
  \vworktheoremfooter{}
  We now present and prove the fundamental theorem of this chapter, which gives an
  $O(log \; N)$ algorithm for finding the enclosing neighbors in $F_N$ to an arbitrary
  rational number $a/b$.\footnote{\label{footnote:ccfr0:scba0:rationalitynotrequired}Theorem
  \ref{thm:ccfr0:scba0:cfenclosingneighbors}
  applies to irrational numbers as well,
  so long as one can obtain enough partial quotients, but we don't highlight this
  fact because it is rare in engineering applications that one uses symbolic methods
  to obtain best rational approximations.
  As emphasized by (\ref{eq:ccfr0:spar0:01}), (\ref{eq:ccfr0:spar0:02}), and
  (\ref{eq:ccfr0:spar0:03}),
  the process of obtaining partial quotients is essentially a process of determining in which
  partition a number lies.  All numbers in the same partition---rational or
  irrational---have the same Farey neighbors in all Farey series up to a certain order.
  If the partial quotients of
  an irrational number can be obtained up through $a_k$ s.t. $s_k = p_k/q_k$ is the
  highest-order convergent with $q_k \leq N$, then this theorem can be applied.
  Knowledge of all $a_0, \ldots{} , a_k$ is equivalent
  to the knowledge that the number is in a partition where all numbers in that partition have
  the same Farey neighbors in all Farey series up through at least order $q_k$.}
  \begin{vworktheoremstatementpar}{Enclosing Neighbors Of \mbox{\boldmath $x \notin F_N$}
                                   In \mbox{\boldmath $F_N$}}
  \label{thm:ccfr0:scba0:cfenclosingneighbors}
  For a non-negative rational
  number $a/b$ not in
  $F_N$ which has a
  continued fraction representation
  $[a_0;a_1,a_2,\ldots{} ,a_n]$, the
  highest-order convergent $s_k = p_k/q_k$ with $q_k \leq N$ is one
  neighbor\footnote{By neighbors in $F_N$ we mean the rational numbers
  in $F_N$ immediately to the left and immediately to the right
  of $a/b$.}
  to $a/b$ in $F_N$, and the other neighbor in
  $F_N$ is\footnote{Theorem \ref{thm:ccfr0:scba0:cfenclosingneighbors}
  is a somewhat stronger statement about best approximations
  than Khinchin makes in \cite{bibref:b:KhinchinClassic}, Theorem 15.
  We were not able to locate
  this theorem or a proof in print,
  but this theorem is understood within the number theory community.
  It appears on the Web
  page of David Eppstein \cite{bibref:i:davideppstein} in the form of a
  `C'-language computer program,
  \texttt{http://www.ics.uci.edu/\~{}{}eppstein/numth/frap.c}.
  Although
  Dr. Eppstein phrases the solution in terms of modifying
  a partial quotient, his approach is equivalent to
  (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01}).}
  \begin{equation}
  \label{eq:ccfr0:scba0:thm:cfenclosingneighbors:01}
  \frac{{\displaystyle{\left\lfloor {\frac{{N - q_{k - 1} }}{{q_k }}} \right\rfloor}
   p_k  + p_{k - 1} }}{{\displaystyle{\left\lfloor {\frac{{N - q_{k - 1} }}{{q_k }}}
   \right\rfloor} q_k  + q_{k - 1} }}.
  \end{equation}
  \end{vworktheoremstatementpar}
  \begin{vworktheoremproof}
  First, it is proved that the highest-order
  convergent $s_k = p_k/q_k$ with $q_k \leq N$ is one of the two
  neighbors to $a/b$ in $F_N$.  $s_k \in F_N$, since $q_k \leq N$.
  By Theorem \ref{thm:ccfr0:scba0:convergentcloseness}, the upper bound on the
  difference between $a/b$ and arbitrary $s_k$ is given by
  \begin{equation}
  \label{eq:ccfr0:scba0:thm:cfenclosingneighbors:02}
  \left| {\frac{a}{b}  - \frac{{p_k }}{{q_k }}} \right| < \frac{1}{{q_k q_{k + 1} }}.
  \end{equation}
  For two consecutive terms in $F_N$, $Kh-Hk=1$
  (\cfryzeroxrefcomma{}Theorem \ref{thm:cfry0:spfs:02}).
  For a Farey neighbor $H/K$ to $s_k$ in $F_N$,
  (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:03}) must hold.
  \begin{equation}
  \label{eq:ccfr0:scba0:thm:cfenclosingneighbors:03}
  \frac{1}{q_k N} \leq \left| {\frac{H}{K} - \frac{p_k}{q_k}} \right|
  \end{equation}
  $q_{k+1}>N$, because $q_{k+1}>q_k$ and $p_k/q_k$ was chosen to be the
  highest-order convergent with $q_k\leq N$.  Using this knowledge and
  combining (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:02}) and
  (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:03}) leads to
  (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:04}).
  \begin{equation}
  \label{eq:ccfr0:scba0:thm:cfenclosingneighbors:04}
  \left| {\frac{a}{b}  - \frac{{p_k }}{{q_k }}} \right| < \frac{1}{{q_k q_{k + 1} }}
  <
  \frac{1}{q_k N} \leq \left| {\frac{H}{K} - \frac{p_k}{q_k}} \right|
  \end{equation}
  This proves that $s_k$ is one neighbor to $a/b$ in $F_N$.
  The apparatus of continued fractions ensures that the
  highest order convergent $s_k$ with $q_k\leq N$ is closer to $a/b$ than
  to any neighboring term in $F_N$.  Thus, there is
  no intervening term of $F_N$ between $s_k$ and $a/b$.
  If $k$ is even, $s_k<a/b$, and if $k$ is
  odd, $s_k>a/b$.
  It must be proved that (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01}) is the other Farey
  neighbor.  For brevity, only the case of $k$ even is proved:  the
  case of $k$ odd is symmetrical.  (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01})
  is of the form (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:05}),
  where $i \in \vworkintsetnonneg$.
  \begin{equation}
  \label{eq:ccfr0:scba0:thm:cfenclosingneighbors:05}
  \frac{{ip_k  + p_{k - 1} }}{{iq_k  + q_{k - 1} }}
  \end{equation}
  $k$ is even, $s_k < a/b$, and the two Farey terms enclosing $a/b$, in
  order, are
  \begin{equation}
  \label{eq:ccfr0:scba0:thm:cfenclosingneighbors:06}
  \frac{p_k }{q_k },\frac{ip_k  + p_{k - 1} }{iq_k  + q_{k - 1} }.
  \end{equation}
  Applying the $Kh - Hk = 1$ test, (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:07}), \
  gives the
  result of 1, since by Theorem
  \ref{thm:ccfr0:scnv0:crossproductminusone},
  $q_kp_{k-1}-p_kq_{k-1}=(-1)^k$.
  \begin{equation}
  \label{eq:ccfr0:scba0:thm:cfenclosingneighbors:07}
  \begin{array}{*{20}c}
  {(q_k )(ip_k  + p_{k - 1} ) - (p_k )(iq_k  + q_{k - 1} ) = 1}
  \end{array}
  \end{equation}
  Thus, every potential Farey neighbor of the form (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:05})
  meets the $Kh - Hk = 1$ test.  It is also straightforward
  to show that \emph{only} potential Farey neighbors of the
  form (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:05}) can meet the $Kh-Hk=1$ test, using the
  property that $p_k$ and $q_k$ are coprime.
  It must be established that a
  rational number of the form (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:05})
  is irreducible.  This result comes directly from
  (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:07}),
  since if the numerator
  and denominator of (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01}) or
  (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:05}) are not coprime, the difference of 1 is
  not possible.
  The denominator of (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01})
  can be rewritten as
  \begin{equation}
  \label{eq:ccfr0:scba0:thm:cfenclosingneighbors:08}
  N - \left[ {\left( {N - q_{k - 1} } \right)\bmod q_k } \right] \in \left\{ {N - q_k  + 1,...,N} \right\}.
  \end{equation}
  It must be shown that if one irreducible
  rational number---namely, the rational number given by
  (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01})---with a denominator
  $\in \{ N-q_k+1,\ldots{} ,N \}$ meets the $Kh - Hk = 1$
  test, there can be no other irreducible rational number
  in $F_N$ with a larger
  denominator which also meets this test.
  Given (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:07}),
  and given that \emph{only} rational numbers of the form
  (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:05})
  can meet the $Kh-Hk=1$ test, and given that any number of the
  form (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:05})
  is irreducible, the irreducible number meeting the
  $Kh-Hk=1$ test with the next larger denominator after the denominator of
   (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01})
  will have a denominator $\in \{ N+1, \ldots, N+q_k \}$.  Thus,
  no other irreducible rational number in $F_N$ besides that given
  by (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01}) with a larger denominator
  $\leq N$ and which meets the $Kh - Hk = 1$ test can exist; therefore
  (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01}) is the other enclosing Farey neighbor to
  $a/b$ in $F_N$.
  \end{vworktheoremproof}
  \vworktheoremfooter{}
  Theorem \ref{thm:ccfr0:scba0:cfenclosingneighbors} establishes that
  the two neighbors in $F_N$ to a rational number $a/b$ will be the highest-order
  convergent with a denominator not exceeding $N$, and the number
  specified by (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01}).
  An interesting and worthwhile question to ask about
  Theorem \ref{thm:ccfr0:scba0:cfenclosingneighbors} is which of the
  two neighbors will be \emph{closer} to $a/b$---the convergent or the
  number specified by (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01})?
  Can we make any strong, simple, and easy-to-remember statements
  about the relative distance?  We answer this question and some related
  questions now.
  We are not aware of any rules that decisively predict which of the two
  Farey neighbors in Theorem \ref{thm:ccfr0:scba0:cfenclosingneighbors}
  will be closer to $a/b$\footnote{We should qualify this by saying that
  we mean a rule which uses only partial quotients up through
  $a_k$ or at most $a_{k+1}$, which is the same information used
  by the theorem.  We should also add that although Theorem
  \ref{thm:ccfr0:scba0:cfenclosingneighbors} is worded to only consider
  non-negative rational numbers, the theorem and the results here
  apply to non-negative irrational numbers as well, so long as enough partial
  quotients can be obtained.}, although Lemma
  \ref{lem:ccfr0:scba0:enclosingneighborstheoremfurtherresult} is able
  to predict that the highest-ordered convergent $s_k$ with a denominator
  not exceeding $N$ will be closer in many cases.
  In general, either neighbor may be closer.
  The most straightforward approach that we
  are aware of is to calculate both Farey neighbors and to calculate
  their respective distances from $a/b$.  The difficulty in devising a simple rule
  to predict which neighbor
  is closer is compounded by that fact that knowledge of
  $[a_0; a_1, \ldots{} , a_k]$ such that $s_k$ is the highest-ordered
  convergent with $q_k \leq N$ is incomplete knowledge of $a/b$ and can
  only confine $a/b$ to an inequality in the sense suggested by
  (\ref{eq:ccfr0:spar0:01}) through
  (\ref{eq:ccfr0:spar0:03}).  Note that the
  value specified by (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01})
  is an intermediate fraction, and that the statement of Theorem
  \ref{thm:ccfr0:scba0:cfenclosingneighbors}
  coincides with Khinchin's Theorem 15
  (\cite{bibref:b:KhinchinClassic}, p. 22).
  However, even in the absence of a rule to decisively
  predict which of the
  two Farey neighbors specified by Theorem
  \ref{thm:ccfr0:scba0:cfenclosingneighbors} is closer to $a/b$,
  there are other useful properties of convergents
  as best approximations which we present
  now.
  It has been stated earlier that even-ordered convergents form an
  increasing sequence and that odd-ordered convergents also form a
  decreasing sequence.  However, up to this point, we have not made
  a statement about the relationship between even- and odd-ordered
  convergents.  We present such a statement as Lemma
  \ref{lem:ccfr0:scba0:convergenterrordecreases},
  below.
  \begin{vworklemmastatement}
  \label{lem:ccfr0:scba0:convergenterrordecreases}
  In the case of a finite or infinite continued fraction representation
  of a non-negative rational or irrational
  number $\alpha \in \vworkrealsetnonneg$, for all $k$,
  \begin{equation}
  \label{eq:lem:ccfr0:scba0:convergenterrordecreases:01}
  \left| {\alpha - \frac{p_k}{q_k}} \right| <
  \left| {\alpha - \frac{p_{k-1}}{q_{k-1}}} \right| .
  \end{equation}
  In other words, convergents get ever-closer to $\alpha$, without
  respect to whether they are even- or odd-ordered convergents.
  \end{vworklemmastatement}
  \begin{vworklemmaproof}
  In this proof, we show that for all $k$,
  \begin{equation}
  \label{eq:lem:ccfr0:scba0:convergenterrordecreases:02}
  | s_{k-2} - s_{k-1} | > 2 | s_{k-1} - s_k | .
  \end{equation}
  To understand why the proof is valid, consider the case of $k$ even,
  in which case $s_k < \alpha$, so that $s_{k-1} - \alpha < s_{k-1} - s_k$.
  If $s_{k-1} - s_{k-2} > 2 (s_{k-1} - s_k)$, then
  $s_{k-2}$ is further to the left of $\alpha$ than $s_{k-1}$ is to the
  right of $\alpha$; thus (\ref{eq:lem:ccfr0:scba0:convergenterrordecreases:01})
  applies.  A symmetrical argument holds for $k$ odd.
  By Theorem \ref{thm:ccfr0:scnv0:crossproductminusone},
  \begin{equation}
  \label{eq:lem:ccfr0:scba0:convergenterrordecreases:03}
  s_{k-2} - s_{k-1}
  = \frac{p_{k-2}}{q_{k-2}}
  - \frac{p_{k-1}}{q_{k-1}}
  = \frac{(-1)^{k-1}}{q_{k-2} q_{k-1}} ,
  \end{equation}
  and similarly
  \begin{equation}
  \label{eq:lem:ccfr0:scba0:convergenterrordecreases:04}
  s_{k-1} - s_{k}
  = \frac{p_{k-1}}{q_{k-1}}
  - \frac{p_{k}}{q_{k}}
  = \frac{(-1)^{k}}{q_{k-1} q_{k}} .
  \end{equation}
  In order for (\ref{eq:lem:ccfr0:scba0:convergenterrordecreases:02})
  to be met, it must be true that
  $2 q_{k-2} q_{k-1} < q_{k-1} q_k$, or equivalently that
  $2 q_{k-2} < q_k$.  Since canonically $q_k = a_k q_{k-1} + q_{k-2}$
  (Eq. \ref{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:10}),
  the requirement is that $2 q_{k-2} < a_k q_{k-1} + q_{k-2}$.
  Since $a_k \geq 1$ and convergents are ever-increasing,
  (\ref{eq:lem:ccfr0:scba0:convergenterrordecreases:02}) is met and the
  lemma is proved.
  \end{vworklemmaproof}
  \vworklemmafooter{}
  Theorem \ref{thm:ccfr0:scba0:convergentcloseness} establishes a
  maximum distance from a number $\alpha$ that we wish to approximate
  to a convergent.  We now provide a second result that establishes
  a \emph{minimum} distance.  (This result is Theorem 13, p.
 , from \cite{bibref:b:KhinchinClassic}.)
  \begin{vworktheoremstatement}
  \label{thm:ccfr0:scba0:convergentfarness}
  In the case of an infinite continued fraction representation
  $[a_0; a_1, a_2, \ldots]$ of
  a non-negative irrational number $\alpha \in \vworkrealsetnonneg$,
  for all $k \geq 0$; or in the case of a [necessarily finite]
  continued fraction representation $[a_0; a_1, a_2, \ldots , a_n]$
  of a non-negative rational number
  $\alpha \in \vworkrealsetnonneg$, for all $0 \leq k \leq n-1$,
  \begin{equation}
  \label{eq:thm:ccfr0:scba0:convergentfarness:01}
  \left| {\alpha - \frac{p_k}{q_k}} \right| > \frac{1}{q_k(q_{k+1}+q_k)} .
  \end{equation}
  \end{vworktheoremstatement}
  \begin{vworktheoremproof}
  We've already established (Lemma \ref{lem:ccfr0:scba0:convergenterrordecreases})
  that each convergent $s_{k+1}$ is nearer to
  a number $\alpha$ to be approximated than the previous
  convergent, $s_k$, i.e. for all $k$,
  \begin{equation}
  \label{eq:thm:ccfr0:scba0:convergentfarness:02}
  \left| {\alpha - \frac{p_{k+1}}{q_{k+1}}} \right| <
  \left| {\alpha - \frac{p_{k}}{q_{k}}} \right| .
  \end{equation}
  Since the mediant of two fractions always lies between
  them (Lemma \cfryzeroxrefhyphen{}\ref{lem:cfry0:spfs:02c}), it
  follows directly that
  \begin{equation}
  \label{eq:thm:ccfr0:scba0:convergentfarness:03}
  \left| {\alpha - \frac{p_{k}}{q_{k}}} \right| >
  \left| {\frac{p_k + p_{k+1}}{q_k + q_{k+1}} - \frac{p_k}{q_k}} \right| =
  \frac{1}{q_k ( q_k + q_{k+1})} .
  \end{equation}
  \end{vworktheoremproof}
  \begin{vworktheoremparsection}{Remark I}
  This theorem can be combined with Theorem \ref{thm:ccfr0:scba0:convergentcloseness}
  to give the following combined inequality:
  \begin{equation}
  \label{eq:thm:ccfr0:scba0:convergentfarness:04}
  \frac{1}{q_k ( q_k + q_{k+1})} <
  \left| {\alpha - \frac{p_{k}}{q_{k}}} \right| \leq
  \frac{1}{q_k q_{k+1}} .
  \end{equation}
  \end{vworktheoremparsection}
  \vworktheoremfooter{}
  We now supply an interesting and sometimes useful property of
  convergents used as best approximations.  Note that we later show that
  Lemma \ref{lem:ccfr0:scba0:convergentbetterappthanlesserdenominator}
  is a weak statement (a stronger statement can be made, Lemma
  \ref{lem:ccfr0:scba0:morecomplexconvergentbapprule}), but this lemma
  has the advantage of being extremely easy to remember.
  \begin{vworklemmastatement}
  \label{lem:ccfr0:scba0:convergentbetterappthanlesserdenominator}
  A convergent $s_k = p_k/q_k$ to a non-negative [rational or irrational] number
  $\alpha \in \vworkrealsetnonneg$ is closer to $\alpha$
  than any other rational number with the same or a smaller
  denominator.
  \end{vworklemmastatement}
  \begin{vworklemmaproof}
  Let $\alpha$ be the non-negative real number, rational or irrational,
  that we wish to approximate.
  If there is a number (let's call it $c/d$)
  closer to $\alpha$ than $s_k = p_k / q_k$, with the same or a smaller denominator
  than $s_k$, then by definition it must be in the Farey series of order
  $q_k$, which we denote $F_{q_k}$.
  Theorem \ref{thm:ccfr0:scba0:cfenclosingneighbors}
  assures us that the two Farey neighbors to $\alpha$ in $F_{q_k}$ will be
  $s_k$ and the number given by (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01}).
  Note that Theorem \ref{thm:ccfr0:scba0:cfenclosingneighbors}
  applies to irrational numbers as well (although the theorem statement
  does not indicate this), so we interpret
  Theorem \ref{thm:ccfr0:scba0:cfenclosingneighbors}
  in that sense.
  Note in (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01}) that the
  expression involving the $floor(\cdot{})$ function will evaluate
  to be zero, since $N=q_k$.  Thus, the other Farey neighbor to
  $\alpha$ in $F_{q_k}$ will be $s_{k-1} = p_{k-1}/q_{k-1}$.
  We have already shown in Lemma \ref{lem:ccfr0:scba0:convergenterrordecreases}
  that $|\alpha - s_{k-1}| > |\alpha - s_{k}|$, therefore
  $s_k$ is closer to $\alpha$ than the other Farey neighbor given
  by (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01}).
  Furthermore, because any $c/d$ which is closer to $\alpha$ than
  $s_k$ must be present in $F_{q_k}$, such a $c/d$ does not exist.
  \end{vworklemmaproof}
  \begin{vworklemmaparsection}{Remark I}
  In practice, this lemma is little more than parlor trivia
  (it is not mathematically significant), but it is useful
  information and very easy to remember.  For example, $355/113$ is a convergent to
  $\pi$, and it is sometimes useful to know that no better rational approximation
  can exist with the same or a smaller denominator.
  \end{vworklemmaparsection}
  \begin{vworklemmaparsection}{Remark II}
  A stronger statement can be made (see
  Lemma \ref{lem:ccfr0:scba0:morecomplexconvergentbapprule}).
  \end{vworklemmaparsection}
  \vworklemmafooter{}
  We now
  present a stronger statement about convergents as best approximations that
  is not as easy to remember as
  Lemma \ref{lem:ccfr0:scba0:convergentbetterappthanlesserdenominator}.
  \begin{vworklemmastatement}
  \label{lem:ccfr0:scba0:morecomplexconvergentbapprule}
  A convergent $s_k = p_k/q_k$ to a non-negative
  [rational or irrational] number
  $\alpha \in \vworkrealsetnonneg$ is closer to $\alpha$
  than any other rational number with a denominator
  less than $q_k + q_{k-1}$.
  \end{vworklemmastatement}
  \begin{vworklemmaproof}
  Let $N$ be the denominator of a rational number which is
  potentially closer to $\alpha$ than $s_k$.  If
  $N < q_k + q_{k+1}$, then
  (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01})
  evaluates to $s_{k-1}$, and Lemma
  \ref{lem:ccfr0:scba0:convergenterrordecreases} has established that
  $s_k$ is closer to $\alpha$ than $s_{k-1}$.  If, on the other
  hand, $N \geq q_k + q_{k+1}$, then the intermediate fraction specified by
  (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01}) \emph{may} be
  closer to $\alpha$ than $s_k$.
  \end{vworklemmaproof}
  \begin{vworklemmaparsection}{Remark I}
  This statement is harder to remember, but a stronger statement
  than Lemma \ref{lem:ccfr0:scba0:convergentbetterappthanlesserdenominator}.
  \end{vworklemmaparsection}
  \begin{vworklemmaparsection}{Remark II}
  Note that the only valid implication is $N < q_k + q_{k+1} \rightarrow$
  (convergent is closer).  Note that
  $N \geq q_k + q_{k+1} \nrightarrow$ (intermediate fraction is closer)!
  If $N \geq q_k + q_{k+1}$, either the convergent or the intermediate fraction
  may be closer.
  This statement is harder to remember, but a stronger statement
  than Lemma \ref{lem:ccfr0:scba0:convergentbetterappthanlesserdenominator}.
  \end{vworklemmaparsection}
  \vworklemmafooter{}
  Finally, we present a result about Theorem
  \ref{thm:ccfr0:scba0:cfenclosingneighbors} that will predict
  in some circumstances that the highest-ordered convergent
  $s_k$ with a denominator not exceeding $N$ must be closer
  to $a/b$ than the intermediate fraction specified by
  (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01}).
  \begin{vworklemmastatement}
  \label{lem:ccfr0:scba0:enclosingneighborstheoremfurtherresult}
  In Theorem \ref{thm:ccfr0:scba0:cfenclosingneighbors},
  if $N < q_k + q_{k-1}$, the highest ordered convergent
  $s_k$ with a denominator not exceeding $N$ is closer to
  $a/b$\footnote{Note that this result is also valid for
  convergents to an irrational number, although
  Theorem \ref{thm:ccfr0:scba0:cfenclosingneighbors} is
  not worded in this way.} then the intermediate fraction specified by
  (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01}).
  If $N \geq q_k + q_{k-1}$, either $s_k$ or the intermediate
  fraction specified by (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01})
  may be closer.
  \end{vworklemmastatement}
  \begin{vworklemmaproof}
  See the proof of Lemma
  \ref{lem:ccfr0:scba0:morecomplexconvergentbapprule}.
  \end{vworklemmaproof}
  \vworklemmafooter{}
  Theorem \ref{thm:ccfr0:scba0:cfenclosingneighbors} immediately suggests
  an algorithm for obtaining the enclosing rational numbers in $F_N$
  to a rational number $a/b \notin F_N$, which we present as
  Algorithm \ref{alg:ccfr0:scba0:cfenclosingneighborsfn}.  Although
  we don't formally show it, the algorithm is $O(log \; N)$, due to
  the minimum geometric rate of increase of convergents
  (Theorem \ref{thm:ccfr0:scnv0:minimumrateofconvergentdenominatorincrease}).
  Note that the algorithm will proceed only until $q_k > N$, not necessarily
  until all partial quotients of $a/b$ are obtained.  Note also that the
  algorithm can be applied to irrational numbers with minor
  modification (all that matters is that we can obtain enough
  partial quotients).
  \begin{vworkalgorithmstatementpar}{Enclosing Neighbors Of \mbox{\boldmath $a/b \notin F_N$}
                                   In \mbox{\boldmath $F_N$}}
  \label{alg:ccfr0:scba0:cfenclosingneighborsfn}
  \begin{alglvl0}
  \item $k := -1$.
  \item $divisor_{-1} := a$.
  \item $remainder_{-1} := b$.
  \item $p_{-1} := 1$.
  \item $q_{-1} := 0$.
  \item Repeat
  \begin{alglvl1}
  \item $k := k + 1$.
  \item $dividend_k := divisor_{k-1}$.
  \item $divisor_k  := remainder_{k-1}$.
  \item $a_k :=  dividend_k \; div \; divisor_k$.
  \item $remainder_k := dividend_k \; mod \; divisor_k$.
  \item If $k=0$ then $p_k := a_k$ else $p_k := a_k p_{k-1} + p_{k-2}$.
  \item If $k=0$ then $q_k := 1$ else $q_k := a_k q_{k-1} + q_{k-2}$.
  \end{alglvl1}
  \item Until ($q_k > k_{MAX}$).
  \item $s_{k-1} = p_{k-1}/q_{k-1}$ will be one Farey neighbor to $a/b$ in $F_{k_{MAX}}$.
        Apply (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01})
            to obtain the other Farey neighbor.
  \end{alglvl0}
  \end{vworkalgorithmstatementpar}
  %\vworkalgorithmfooter{}
  \begin{vworkexamplestatement}
  \label{ex:ccfr0:scba0:bestrapapptoratnum}
  Find the members of $F_{100}$ which enclose the conversion factor
  from kilometers-per-hour to miles-per-hour.  Assume that
  one mile is 1.6093 kilometers (exactly).
  \end{vworkexamplestatement}
  \begin{vworkexampleparsection}{Solution}
  The conversion factor from KPH to MPH is the reciprocal of 1.6093.  As a rational
  number, 1.6093 is 16,093/10,000, so 10,000/16,093 is its exact reciprocal.
  Applying Algorithm \ref{alg:ccfr0:scba0:cfenclosingneighborsfn}
  with $a/b = 10,000/16,093$ and $k_{MAX} = 100$ yields Table
  \ref{tbl:ex:ccfr0:scba0:bestrapapptoratnum}.
  \begin{table}
  \caption{Application Of Algorithm \ref{alg:ccfr0:scba0:cfenclosingneighborsfn}
           To Find Members Of $F_{100}$ Which Enclose 10,000/16,093
                   (Example \ref{ex:ccfr0:scba0:bestrapapptoratnum})}
  \label{tbl:ex:ccfr0:scba0:bestrapapptoratnum}
  \begin{center}
  \begin{tabular}{|c|c|c|c|c|c|c|}
  \hline
  \small{Index} & \small{$dividend_k$}  & \small{$divisor_k$} & \small{$a_k$}   & \small{$remainder_k$} & \small{$p_k$}    & \small{$q_k$}  \\
  \small{($k$)} &                       &                     &                 &                       &                  &                \\
  \hline
  \hline
  \small{-1}    & \small{N/A}           & \small{10,000}      & \small{N/A}     & \small{16,093}        & \small{1}        & \small{0}      \\
  \hline
  \small{0}     & \small{10,000}        & \small{16,093}      & \small{0}       & \small{10,000}        & \small{0}        & \small{1}      \\
  \hline
  \small{1}     & \small{16,093}        & \small{10,000}      & \small{1}       & \small{6,093}         & \small{1}        & \small{1}      \\
  \hline
  \small{2}     & \small{10,000}        & \small{6,093}       & \small{1}       & \small{3,907}         & \small{1}        & \small{2}      \\
  \hline
  \small{3}     & \small{6,093}         & \small{3,907}       & \small{1}       & \small{2,186}         & \small{2}        & \small{3}      \\
  \hline
  \small{4}     & \small{3,907}         & \small{2,186}       & \small{1}       & \small{1,721}         & \small{3}        & \small{5}      \\
  \hline
  \small{5}     & \small{2,186}         & \small{1,721}       & \small{1}       & \small{465}           & \small{5}        & \small{8}      \\
  \hline
  \small{6}     & \small{1,721}         & \small{465}         & \small{3}       & \small{326}           & \small{18}       & \small{29}     \\
  \hline
  \small{7}     & \small{465}           & \small{326}         & \small{1}       & \small{139}           & \small{23}       & \small{37}     \\
  \hline
  \small{8}     & \small{326}           & \small{139}         & \small{2}       & \small{48}            & \small{64}       & \small{103}    \\
  \hline
  \end{tabular}
  \end{center}
  \end{table}
  Note from Table \ref{tbl:ex:ccfr0:scba0:bestrapapptoratnum}
  that the 7-th order convergent, $s_7 = 23/37$,
  is the highest-ordered convergent with $q_k \leq 100$, so
  by Theorem \ref{thm:ccfr0:scba0:cfenclosingneighbors}, 23/37
  is one neighbor in $F_{100}$ to 10,000/16,093.  Because $s_7$
  is an odd-ordered convergent, it will be the right
  Farey neighbor.
  By (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01}), the
  other Farey neighbor is 41/66, and it will be the left
  Farey neighbor.
  \end{vworkexampleparsection}
  %\vworkexamplefooter{}
  \begin{vworkexamplestatement}
  \label{ex:ccfr0:scba0:bestrapapptoirratnum}
  Find the members of $F_{200}$ which
  enclose $\sqrt{3}$.
  \end{vworkexamplestatement}
  \begin{vworkexampleparsection}{Solution}
  We demonstrated in Example
  \ref{ex:ccfr0:scin0:symboliccfalgorithmexample}
  that the continued fraction representation of
  $\sqrt{3}$ is $[1;\overline{1,2}]$.
  As is highlighted in Footnote
  \ref{footnote:ccfr0:scba0:rationalitynotrequired}, it isn't required
  that a number be rational to apply Theorem
  \ref{thm:ccfr0:scba0:cfenclosingneighbors}, so long as
  enough partial quotients can be obtained.
  Using knowledge of the partial quotients of
  $\sqrt{3}$ and applying Algorithm \ref{alg:ccfr0:scba0:cfenclosingneighborsfn}
  yields Table \ref{tbl:ex:ccfr0:scba0:bestrapapptoirratnum} (note that it isn't necessary
  to track remainders, as we already have all of the partial quotients for
  $\sqrt{3}$).
  \begin{table}
  \caption{Application Of Algorithm \ref{alg:ccfr0:scba0:cfenclosingneighborsfn}
           To Find Members Of $F_{100}$ Which Enclose $\sqrt{3}$
                   (Example \ref{ex:ccfr0:scba0:bestrapapptoirratnum})}
  \label{tbl:ex:ccfr0:scba0:bestrapapptoirratnum}
  \begin{center}
  \begin{tabular}{|c|c|c|c|}
  \hline
  \hspace{0.15in}\small{Index ($k$)}\hspace{0.15in} & \hspace{0.15in}\small{$a_k$}\hspace{0.15in}   &
   \hspace{0.15in}\small{$p_k$}\hspace{0.15in}    & \hspace{0.15in}\small{$q_k$}\hspace{0.15in}  \\
  \hline
  \hline
  \small{-1}    & \small{N/A}     & \small{1}        & \small{0}      \\
  \hline
  \small{0}     & \small{1}       & \small{1}        & \small{1}      \\
  \hline
  \small{1}     & \small{1}       & \small{2}        & \small{1}      \\
  \hline
  \small{2}     & \small{2}       & \small{5}        & \small{3}      \\
  \hline
  \small{3}     & \small{1}       & \small{7}        & \small{4}      \\
  \hline
  \small{4}     & \small{2}       & \small{19}       & \small{11}     \\
  \hline
  \small{5}     & \small{1}       & \small{26}       & \small{15}     \\
  \hline
  \small{6}     & \small{2}       & \small{71}       & \small{41}     \\
  \hline
  \small{7}     & \small{1}       & \small{97}       & \small{56}     \\
  \hline
  \small{8}     & \small{2}       & \small{265}      & \small{153}    \\
  \hline
  \small{9}     & \small{1}       & \small{362}      & \small{209}    \\
  \hline
  \end{tabular}
  \end{center}
  \end{table}
  Note from Table \ref{tbl:ex:ccfr0:scba0:bestrapapptoirratnum}
  that the 8-th order convergent, $s_8 = 265/153$,
  is the highest-ordered convergent with $q_k \leq 200$, so
  by Theorem \ref{thm:ccfr0:scba0:cfenclosingneighbors}, 265/153
  is one neighbor in $F_{100}$ to $\sqrt{3}$.  Because $s_8$
  is an even-ordered convergent, it will be the left
  Farey neighbor.
  By (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01}), the
  other Farey neighbor is 97/56, and it will be the right
  Farey neighbor.
  \end{vworkexampleparsection}
  \vworkexamplefooter{}
  It is clear that Algorithm \ref{alg:ccfr0:scba0:cfenclosingneighborsfn}
  can be trivially modified to find enclosing neighbors
  in $F_{k_{MAX},\overline{h_{MAX}}}$, and we present this
  trivial modification as Algorithm
  \ref{alg:ccfr0:scba0:cfenclosingneighborsfab}.
  \begin{vworkalgorithmstatementpar}{Enclosing Neighbors Of
                                     \mbox{\boldmath $x \notin F_{k_{MAX},\overline{h_{MAX}}}$}
                                     In \mbox{\boldmath $F_{k_{MAX},\overline{h_{MAX}}}$}}
  \label{alg:ccfr0:scba0:cfenclosingneighborsfab}
  \begin{alglvl0}
  \item If $a/b < h_{MAX}/k_{MAX}$, apply Algorithm
        \ref{alg:ccfr0:scba0:cfenclosingneighborsfn} directly;
  \item Else if $a/b > h_{MAX}/k_{MAX}$, apply Algorithm
        \ref{alg:ccfr0:scba0:cfenclosingneighborsfn} using $b/a$ rather
            than $a/b$ as the input to the algorithm, using $h_{MAX}$
            rather than $k_{MAX}$ as $N$, and
            using the reciprocals of the results of the algorithm.\footnote{The
            basis for taking the reciprocals of input and output and
            using $h_{MAX}$ rather than $k_{MAX}$ are explained
            in \cfryzeroxrefcomma{}Section \ref{cfry0:schk0}.}
  \end{alglvl0}
  \end{vworkalgorithmstatementpar}
  %\vworkalgorithmfooter{}
  \begin{vworkexamplestatement}
  \label{ex:ccfr0:scba0:bestratapptoirratnum2d}
  Find the members of $F_{200,\overline{100}}$ which
  enclose $\sqrt{3}$.
  \end{vworkexamplestatement}
  \begin{vworkexampleparsection}{Solution}
  It was shown in Example \ref{ex:ccfr0:scba0:bestrapapptoirratnum}
  that the two enclosing neighbors to $\sqrt{3}$ in
  $F_{200}$ are 265/153 and 97/56.  Note that the first of
  these neighbors, 265/153, violates the constraint on the
  numerator.
  As explained in Section \cfryzeroxrefhyphen{}\ref{cfry0:schk0},
  because $\sqrt{3} > 100/200$, the constraint on the
  numerator is the dominant constraint, and the necessary
  approach is to find the neighbors of $1/\sqrt{3}$ in
  $F_{100}$, then invert the results.
  Although we don't explain it in this work,
  the reciprocal of a continued fraction can be formed by
  ``right-shifting'' or ``left-shifting'' the continued fraction one position.
  Thus, if $[1;1,2,1,2,1,2, \ldots{}]$ = $[1;\overline{1,2}]$
  is the continued fraction representation of $\sqrt{3}$, then
  $[0;1,1,2,1,2,1, \ldots{}]$ = $[0;1,\overline{1,2}]$ is the
  continued fraction representation of $1/\sqrt{3}$.  Using
  this result and constructing the convergents until
  $q_k \geq 100$ yields Table \ref{tbl:ex:ccfr0:scba0:bestratapptoirratnum2d}.
  \begin{table}
  \caption{Application Of Algorithm \ref{alg:ccfr0:scba0:cfenclosingneighborsfab}
           To Find Members Of $F_{100}$ Which Enclose $1/\sqrt{3}$
                   (Example \ref{ex:ccfr0:scba0:bestratapptoirratnum2d})}
  \label{tbl:ex:ccfr0:scba0:bestratapptoirratnum2d}
  \begin{center}
  \begin{tabular}{|c|c|c|c|}
  \hline
  \hspace{0.15in}\small{Index ($k$)}\hspace{0.15in} & \hspace{0.15in}\small{$a_k$}\hspace{0.15in}   &
   \hspace{0.15in}\small{$p_k$}\hspace{0.15in}    & \hspace{0.15in}\small{$q_k$}\hspace{0.15in}  \\
  \hline
  \hline
  \small{-1}    & \small{N/A}     & \small{1}        & \small{0}      \\
  \hline
  \small{0}     & \small{0}       & \small{0}        & \small{1}      \\
  \hline
  \small{1}     & \small{1}       & \small{1}        & \small{1}      \\
  \hline
  \small{2}     & \small{1}       & \small{1}        & \small{2}      \\
  \hline
  \small{3}     & \small{2}       & \small{3}        & \small{5}      \\
  \hline
  \small{4}     & \small{1}       & \small{4}        & \small{7}      \\
  \hline
  \small{5}     & \small{2}       & \small{11}       & \small{19}     \\
  \hline
  \small{6}     & \small{1}       & \small{15}       & \small{26}     \\
  \hline
  \small{7}     & \small{2}       & \small{41}       & \small{71}     \\
  \hline
  \small{8}     & \small{1}       & \small{56}       & \small{97}     \\
  \hline
  \small{9}     & \small{2}       & \small{153}      & \small{265}    \\
  \hline
  \end{tabular}
  \end{center}
  \end{table}
  Note from Table \ref{tbl:ex:ccfr0:scba0:bestratapptoirratnum2d}
  that the 8-th order convergent, $s_8 = 56/97$,
  is the highest-ordered convergent with $q_k \leq 100$, so
  by Theorem \ref{thm:ccfr0:scba0:cfenclosingneighbors}, 56/97
  is one neighbor in $F_{100}$ to $1/\sqrt{3}$.  Because $s_8$
  is an even-ordered convergent, it will be the left
  Farey neighbor.
  By (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01}), the
  other Farey neighbor is 41/71, and it will be the right
  Farey neighbor.  Taking the reciprocal of these neighbors (and
  reversing their order) yields $97/56 < \sqrt{3} < 41/71$
  as the two members of $F_{200, \overline{100}}$ which enclose
  $\sqrt{3}$.
  \end{vworkexampleparsection}
  \vworkexamplefooter{}
  A natural question to ask is whether, given only a \emph{single}
  rational number $a/b \in F_N$, the apparatus of continued fractions
  can be used to economically find its neighbors in $F_N$.  Examining
  the proof of Theorem \ref{thm:ccfr0:scba0:cfenclosingneighbors},
  we see that the entire proof applies even if the denominator of the
  highest-order convergent, $q_n$, is less than or equal to $N$---that is,
  the number specified by (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01})
  is a left or right Farey neighbor in $F_N$ of $a/b$.  If $n$ is even,
  $s_{n-1} > s_n$, and the number specified by
  (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01}) will be the right Farey neighbor
  of $s_n$, and
  (\cfryzeroxrefhyphen{}\ref{eq:cfry0:sgfs0:thm:01:eq03}) and
  (\cfryzeroxrefhyphen{}\ref{eq:cfry0:sgfs0:thm:01:eq04})
  can be used to find the left Farey neighbor.
  On the other hand if $n$ odd, $s_{n-1} < s_n$, (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01})
  will be the left Farey neighbor of $s_n$, and
  (\cfryzeroxrefhyphen{}\ref{eq:cfry0:sgfs0:thm:01:eq01})
  and
  (\cfryzeroxrefhyphen{}\ref{eq:cfry0:sgfs0:thm:01:eq02})
  can be used to find the
  right Farey neighbor.  We summarize these observations as Algorithm
  \ref{alg:ccfr0:scba0:cffareyneighborfn}.
  \begin{vworkalgorithmstatementpar}{Neighbors Of
                                     \mbox{\boldmath $a/b \in F_N$}
                                     In \mbox{\boldmath $F_N$}}
  \label{alg:ccfr0:scba0:cffareyneighborfn}
  \end{vworkalgorithmstatementpar}
  \begin{alglvl0}
  \item  Apply the first part of Algorithm
         \ref{alg:ccfr0:scba0:cfenclosingneighborsfn} to obtain
             all of the partial quotients and convergents of $a/b$.
             The final convergent, $s_n = p_n/q_n$, will be
             $a/b$ in reduced form.
  \item  Use (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01})
         (with $k = n$) to obtain the right Farey neighbor
             (if $n$ is even) or the left Farey neighbor (if $n$
             is odd).
  \item  If $n$ is even, $s_{n-1} > s_n$, and the number specified by
         (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01}) will be
             the right Farey neighbor of $s_n$.  Use
         (\cfryzeroxrefhyphen{}\ref{eq:cfry0:sgfs0:thm:01:eq03}) and
         (\cfryzeroxrefhyphen{}\ref{eq:cfry0:sgfs0:thm:01:eq04})
         to find the left Farey neighbor.
         On the other hand if $n$ is odd, $s_{n-1} < s_n$,
             (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01})
         will be the left Farey neighbor of $s_n$.  Use
         (\cfryzeroxrefhyphen{}\ref{eq:cfry0:sgfs0:thm:01:eq01})
         and (\cfryzeroxrefhyphen{}\ref{eq:cfry0:sgfs0:thm:01:eq02})
         to find the right Farey neighbor.
  \end{alglvl0}
  %\vworkalgorithmfooter{}
  \begin{vworkexamplestatement}
  \label{ex:ccfr0:scba0:fnneighborsaoverbinfn}
  Find the neighbors of 5/7 in $F_{1,000,000}$.
  \end{vworkexamplestatement}
  \begin{vworkexampleparsection}{Solution}
  As per Algorithm \ref{alg:ccfr0:scba0:cffareyneighborfn}, the first
  step is to obtain the partial quotients and convergents of 5/7
  (these partial quotients and convergents are shown in
  Table \ref{tbl:ex:ccfr0:scba0:fnneighborsaoverbinfn}).
  \begin{table}
  \caption{Partial Quotients And Convergents Of 5/7
                   (Example \ref{ex:ccfr0:scba0:fnneighborsaoverbinfn})}
  \label{tbl:ex:ccfr0:scba0:fnneighborsaoverbinfn}
  \begin{center}
  \begin{tabular}{|c|c|c|c|c|c|c|}
  \hline
  \small{Index ($k$)} & \small{$dividend_k$}  & \small{$divisor_k$} & \small{$a_k$}   & \small{$remainder_k$} & \small{$p_k$}    & \small{$q_k$}  \\
  \hline
  \hline
  \small{-1}    & \small{N/A}           & \small{5}           & \small{N/A}     & \small{7}             & \small{1}        & \small{0}      \\
  \hline
  \small{0}     & \small{5}             & \small{7}           & \small{0}       & \small{5}             & \small{0}        & \small{1}      \\
  \hline
  \small{1}     & \small{7}             & \small{5}           & \small{1}       & \small{2}             & \small{1}        & \small{1}      \\
  \hline
  \small{2}     & \small{5}             & \small{2}           & \small{2}       & \small{1}             & \small{2}        & \small{3}      \\
  \hline
  \small{3}     & \small{2}             & \small{1}           & \small{2}       & \small{0}             & \small{5}        & \small{7}      \\
  \hline
  \end{tabular}
  \end{center}
  \end{table}
  Since the final convergent, $s_{3}$, is an odd-ordered convergent, $s_{k-1} < s_k$, and
  (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01}) will supply the left Farey neighbor
  of 5/7.  Applying (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01}) with
  $N=1,000,000$, $k=3$, $k-1=2$, $p_k = 5$, $q_k = 7$, $p_{k-1}=2$, and $q_{k-1}=3$
  yields $\frac{714,282}{999,995}$ as the left Farey neighbor of 5/7 in $F_{1,000,000}$.
  Application of (\cfryzeroxrefhyphen{}\ref{eq:cfry0:sgfs0:thm:01:eq01})
  and (\cfryzeroxrefhyphen{}\ref{eq:cfry0:sgfs0:thm:01:eq02})
  yields $\frac{714,283}{999,996}$ as the right Farey neighbor.
  \end{vworkexampleparsection}
  %\vworkexamplefooter{}
  \begin{vworkalgorithmstatementpar}{Neighbors Of
                                     \mbox{\boldmath $x \in F_{k_{MAX},\overline{h_{MAX}}}$}
                                     In \mbox{\boldmath $F_{k_{MAX},\overline{h_{MAX}}}$}}
  \label{alg:ccfr0:scba0:cffareyneighborfab}
  \begin{alglvl0}
  \item If $a/b < h_{MAX}/k_{MAX}$, apply Algorithm
        \ref{alg:ccfr0:scba0:cffareyneighborfn} directly;
  \item Else if $a/b > h_{MAX}/k_{MAX}$, apply Algorithm
        \ref{alg:ccfr0:scba0:cffareyneighborfn} using $b/a$ rather
            than $a/b$ as the input to the algorithm, using $h_{MAX}$
            rather than $k_{MAX}$ as $N$, and
            using the reciprocals of the results of the algorithm.\footnote{The
            basis for taking the reciprocals of input and output and
            using $h_{MAX}$ rather than $k_{MAX}$ are explained
            in \cfryzeroxrefcomma{}Section \ref{cfry0:schk0}.}
  \end{alglvl0}
  \end{vworkalgorithmstatementpar}
  \vworkalgorithmfooter{}
  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  \section{The Stern-Brocot Tree}
  %Section tag:  SBT0
  \label{ccfr0:ssbt0}
  In this chapter, we've developed continued fraction techniques of best
  rational approximation without reference to any other models or theory.
  Because the algorithms presented in this chapter are $O(log \; N)$,
  the results so far are completely satisfactory and usable in practice.
  It is not necessary to go further or to present additional information.
  However, there is a second model of best rational approximation (and a second
  set of algorithms), involving
  the Stern-Brocot tree.  In fact, when reviewing the material in this
  chapter, some readers have inquired why the Stern-Brocot tree was not
  used.\footnote{In brief, the Stern-Brocot tree was not used because
  the resulting algorithms are $O(N)$, and so will introduce practical
  computational difficulties when used with large integers.}  In this
  section, we introduce the Stern-Brocot tree, demonstrate how to construct it,
- mention its major properties, show its correspondence with the apparatus of
+ mention its major properties, show its correspondence with the appar