1 |
%$Header$ |
2 |
|
3 |
\chapter{\ccfrzerolongtitle{}} |
4 |
|
5 |
\label{ccfr0} |
6 |
|
7 |
\beginchapterquote{``I began by saying that there is probably less difference |
8 |
between the positions of a mathematician and a physicist |
9 |
than is generally supposed, and that the most important |
10 |
seems to me to be this, that the mathematician is in much |
11 |
more direct contact with reality \ldots{} mathematical |
12 |
objects are so much more what they seem. A chair or a |
13 |
star is not in the least what it seems to be; the more we think |
14 |
of it, the fuzzier its outlines become in the haze of sensation |
15 |
which surround it; but `2' or `317' has nothing to do with |
16 |
sensation, and its properties stand out the more clearly the more |
17 |
closely we scrutinize it.''} |
18 |
{G. H. Hardy \cite{bibref:b:mathematiciansapology:1940}, pp. 128-130} |
19 |
\index{Hardy, G. H.} |
20 |
|
21 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
22 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
23 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
24 |
\section{Introduction} |
25 |
%Section tag: INT0 |
26 |
\label{ccfr0:sint0} |
27 |
\index{continued fraction} |
28 |
\index{continued fraction!definition} |
29 |
|
30 |
A \emph{finite simple continued fraction} is a fraction of the form |
31 |
|
32 |
\begin{equation} |
33 |
\label{eq:ccfr0:int0:00} |
34 |
a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 |
35 |
+ \cfrac{1}{\;\;\;\;\;\;\;\;\;\;\;\;\;\;\ldots + \cfrac{1}{a_n}}}} |
36 |
= |
37 |
[a_0; a_1, a_2, \ldots , a_n] , |
38 |
\end{equation} |
39 |
|
40 |
\noindent{}where $a_0 \in \vworkintsetnonneg$ and |
41 |
$a_i \in \vworkintsetpos$, $i > 0$. Each integer |
42 |
$a_i$ is called an \index{continued fraction!element}\emph{element} or |
43 |
\index{continued fraction!partial quotient}\emph{partial quotient} |
44 |
of the continued fraction. |
45 |
We require, except in the case of |
46 |
the continued fraction representation of an integer, |
47 |
that the final element $a_n$ not be equal |
48 |
to 1.\footnote{\label{footnote:ccfr0:sint0:00}The reason for |
49 |
this restriction is discussed later.} |
50 |
|
51 |
Continued fractions are quite unwieldly to write and typeset, |
52 |
and so a continued fraction in the form of (\ref{eq:ccfr0:int0:00}) |
53 |
is written as $[a_0; a_1, a_2, \ldots , a_n]$. Note that the |
54 |
separator between $a_0$ and $a_1$ is a semicolon (`;'), and that all other |
55 |
separators are commas (`,'). In some works, commas are used exclusively; and in |
56 |
other works, the first element is $a_1$ rather than $a_0$. Throughout this |
57 |
work, the notational conventions illustrated in (\ref{eq:ccfr0:int0:00}) are |
58 |
followed. |
59 |
|
60 |
In this chapter, the framework of continued fractions is presented in the |
61 |
context of finding rational numbers in $F_N$, the Farey series of order $N$, |
62 |
enclosing an arbitrary $r_I \in \vworkrealsetnonneg$. The continued fraction |
63 |
algorithm presented (Algorithm \ref{alg:ccfr0:scba0:cfenclosingneighborsfn}) |
64 |
is $O(log N)$, and so is suitable for finding the best rational |
65 |
approximations in $F_N$ even when $N$ is very large. Because our emphasis |
66 |
is on practical applications rather than number theory, we don't include more |
67 |
information than is necessary to understand the applications we have in |
68 |
mind. |
69 |
|
70 |
The study of continued |
71 |
fractions is a topic from number theory (a branch of mathematics). It may be |
72 |
counterintuitive to anyone but a number theorist that continued fractions |
73 |
can be used to economically find best rational approximations, |
74 |
or that continued fractions are anything but |
75 |
a parlor curiosity. C.D. Olds (\cite{bibref:b:OldsClassic}, p. 3) comments: |
76 |
|
77 |
\index{Olds, C. D.} |
78 |
|
79 |
\begin{quote} |
80 |
At first glance, nothing seems simpler or less significant than writing a number, |
81 |
for example $\frac{9}{7}$, in the form |
82 |
|
83 |
\begin{equation} |
84 |
\frac{9}{7} = 1 + \frac{2}{7} = 1 + \frac{1}{\cfrac{7}{2}} |
85 |
= 1 + \cfrac{1}{3 + \cfrac{1}{2}} |
86 |
= 1 + \cfrac{1}{3 + \cfrac{1}{1 + \cfrac{1}{1}}}. |
87 |
\end{equation} |
88 |
|
89 |
It turns out, however, that fractions of this form, called ``continued |
90 |
fractions'', provide much insight into mathematical problems, particularly into |
91 |
the nature of numbers. |
92 |
|
93 |
Continued fractions were studied by the great mathematicians of the seventeenth |
94 |
and eighteenth centuries and are a subject of active investigation today. |
95 |
\end{quote} |
96 |
|
97 |
|
98 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
99 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
100 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
101 |
\section{History Of Continued Fractions} |
102 |
%Section tag: HST0 |
103 |
\label{cfr0:hst0} |
104 |
\index{continued fraction!history of} |
105 |
|
106 |
The only work we are aware of that explicitly treats the history |
107 |
of continued fractions is \cite{bibref:b:HistoryCfPadeApproxBrezinski}. |
108 |
Although the history of continued fractions is complex, |
109 |
two points are clear. First, it is clear that Euclid's \index{Euclid} |
110 |
GCD algorithm \index{Euclid!GCD algorithm} |
111 |
(Algorithm \ref{alg:ccfr0:sega0:euclidsgcdalgorithm}), |
112 |
which was known no later than around 300 B.C., |
113 |
represents the historical origin of the continued fraction. Second, |
114 |
it is clear that the utility of the apparatus of continued fractions |
115 |
in finding best rational approximations---specifically the properties |
116 |
of convergents---was understood by the 17th century. |
117 |
|
118 |
In this section, we present some excerpts from |
119 |
\cite{bibref:b:HistoryCfPadeApproxBrezinski} |
120 |
which show the very early use of continued fractions to obtain best rational |
121 |
approximations with a numerator and denominator less than certain |
122 |
prescribed limits. |
123 |
We simply demonstrate that the technique we present was known by |
124 |
the 17th century (with the possible exception of the |
125 |
second component of Theorem \ref{thm:ccfr0:scba0:cfenclosingneighbors}), |
126 |
and we don't attempt to describe the other uses |
127 |
of continued fractions or the significance of continued fractions |
128 |
in mathematics or number theory. |
129 |
|
130 |
Although we present best rational |
131 |
approximations in the context of being able to effectively use |
132 |
processor integer multiplication and division instructions, |
133 |
earlier historical work was aimed at either |
134 |
providing rational approximations to irrational numbers ($\sqrt{2}$ or $\pi$, |
135 |
for example), or at determining optimal numbers of gear teeth |
136 |
(in mechanical systems). Naturally, the need for best rational approximations |
137 |
in the context of computer arithmetic is a relatively recent |
138 |
development. |
139 |
|
140 |
In the introduction of \cite{bibref:b:HistoryCfPadeApproxBrezinski}, |
141 |
Brezinski \index{Brezenski, Claude} hints at the broad application and importance |
142 |
of continued fractions: |
143 |
|
144 |
\begin{quote} |
145 |
The history of continued fractions is certainly one of the longest |
146 |
among those of mathematical concepts, since it begins with |
147 |
Euclid's algorithm \index{Euclid!GCD algorithm} for the greatest common divisor at least |
148 |
three centuries B.C. As it is often the case and like |
149 |
Monsieur Jourdain in Moli\`ere's ``le bourgeois gentilhomme'' |
150 |
(who was speaking in prose though he did not know he was doing so), |
151 |
continued fractions were used for many centuries before their real |
152 |
discovery. |
153 |
|
154 |
The history of continued fractions and Pad\'e approximants is also |
155 |
quite important, since they played a leading role in the development |
156 |
of some branches of mathematics. For example, they were the basis |
157 |
for the proof of the transcendence of $\pi$ in 1882, an open |
158 |
problem for more than two thousand years, and also for our modern |
159 |
spectral theory of operators. Actually they still are of great |
160 |
interest in many fields of pure and applied mathematics and in |
161 |
numerical analysis, where they provide computer approximations to |
162 |
special functions and are connected to some convergence acceleration |
163 |
methods. Continued fractions are also used in number theory, |
164 |
computer science, automata, electronics, etc. \ldots{} |
165 |
\end{quote} |
166 |
|
167 |
Notice that Theorem \ref{thm:ccfr0:scba0:cfenclosingneighbors} |
168 |
has two components. First, it is shown that the highest-order |
169 |
convergent with an acceptable denominator is closer to $a/b$ than |
170 |
any Farey neighbor to this convergent (thus, this convergent must be |
171 |
either a left or right Farey neighbor of $a/b$). Second, it is shown |
172 |
what the other Farey neighbor must be. It is historically clear |
173 |
that the properties of convergents as best rational approximations were |
174 |
understood by the 17th century (this is the \emph{first} part of |
175 |
Theorem \ref{thm:ccfr0:scba0:cfenclosingneighbors}). However, it |
176 |
is not historically clear when the \emph{second} part of |
177 |
Theorem \ref{thm:ccfr0:scba0:cfenclosingneighbors} was discovered. |
178 |
|
179 |
Even in Khinchin's \index{Khinchin, A. Ya.} classic work, |
180 |
\cite{bibref:b:KhinchinClassic}, Theorem 15, p. 22, Khinchin stops |
181 |
just short of the result presented as the second part of |
182 |
Theorem \ref{thm:ccfr0:scba0:cfenclosingneighbors}. Khinchin writes: |
183 |
|
184 |
\begin{quote} |
185 |
THEOREM 15. \em Every best approximation of a number is a convergent |
186 |
or an intermediate fraction of the continued fraction representing |
187 |
that number. |
188 |
\end{quote} |
189 |
|
190 |
\noindent{}Theorem \ref{thm:ccfr0:scba0:cfenclosingneighbors} goes |
191 |
slightly farther than Khinchin's \emph{THEOREM 15}, above. |
192 |
Khinchin \index{Khinchin, A. Ya.} states |
193 |
that a best approximation will be a convergent or an intermediate |
194 |
fraction---but Theorem \ref{thm:ccfr0:scba0:cfenclosingneighbors} |
195 |
goes slightly farther to indicate \emph{exactly which} intermediate fraction |
196 |
is potentially the best approximation. Khinchin's \emph{THEOREM 15} |
197 |
is correct, but could be strengthened. Khinchin's work |
198 |
was first published in 1935. This raises the [unlikely] possibility |
199 |
that the second part of Theorem \ref{thm:ccfr0:scba0:cfenclosingneighbors} |
200 |
had not been published even as recently as 1935, although |
201 |
we (the authors) don't have the ability to confirm or |
202 |
refute this. |
203 |
|
204 |
In \cite{bibref:b:HistoryCfPadeApproxBrezinski}, p. 70, Brezinski |
205 |
\index{Brezenski, Claude} |
206 |
writes: |
207 |
|
208 |
\begin{quote} |
209 |
In the same period, algorithms equivalent to continued fractions were |
210 |
still used to find approximate values for ratios and to simplify |
211 |
fractions. We have already mentioned Albert Girard. |
212 |
|
213 |
Among the other authors who treated the subject, the most prominent |
214 |
is Daniel SCHWENTER \index{Schwenter, Daniel} |
215 |
(N\"urnberg, 31.1.1585 - Altdorf, 19.1.1636), |
216 |
who wrote two books ``\emph{Geometriae practicae novae et auctae |
217 |
tractatus}'' published in 1627 and ``\emph{Delicae |
218 |
Physico-mathematicae}'' which appeared in 1636 followed by a |
219 |
second edition in 1651. |
220 |
|
221 |
In his first book, Schwenter found approximations of 177/233 by |
222 |
finding their g.c.d. and gave the successive convergents |
223 |
79/104, 19/25, 3/4, 1/1, and 0/1. His calculations were arranged |
224 |
in a table\footnote{The table is reproduced in |
225 |
\cite{bibref:b:HistoryCfPadeApproxBrezinski}, |
226 |
but is omitted here.} \ldots{} although he gave no explanation of the method. |
227 |
\end{quote} |
228 |
|
229 |
On p. 84, Brezenski \index{Brezenski, Claude} writes: |
230 |
|
231 |
\begin{quote} |
232 |
Wallis \index{Wallis, John} also made use of continued fractions in his book |
233 |
``\emph{A treatise of algebra both historical and practical}'' |
234 |
(published in 1685), to approximate ratios with large |
235 |
numerators and denominators: |
236 |
|
237 |
\emph{``Before I leave the business of Decimal Parts, and the |
238 |
advantages which in practice may there cause; I have thought fit |
239 |
here to insert a Process Of Reducing Fractions or Proportions to |
240 |
smaller termes, retaining as near as may be, the just value.} |
241 |
|
242 |
\emph{It was occasion'd by a Problem sent me (as I remember) about the |
243 |
Year 1663 or 1664, by Dr. Lamplugh the present Bishop of Exeter from |
244 |
(his Wives Father) Dr. Davenant then one of the Prebends |
245 |
Residentaries of the Church of Salisbury, a very worthy Person, of |
246 |
great Learning and Modesty; as I mire inderstand from persons |
247 |
well acquainted with him, and by divers Writings of his which I have seen, |
248 |
though I never had the opportunity of being personally acquainted with him, |
249 |
otherwise than by Letter. And amongst |
250 |
his other Learning, he was very well skilled the Mathematicks, |
251 |
and a diligent Proficient therein.} |
252 |
|
253 |
\emph{He sent me (as it abovesaid) a Fraction (which what it was I |
254 |
do not now particulary remember) who's Numerator and Denominator |
255 |
were, each of them of about six or seven places; and Proposed to |
256 |
find the nearest Fraction in value to it, whose Denominator should |
257 |
not be greater than 999.''} |
258 |
|
259 |
\begin{center} |
260 |
\rule{3in}{0.3mm} \\\ |
261 |
\end{center} |
262 |
|
263 |
\begin{center} |
264 |
\emph{The Problem} \\ |
265 |
\end{center} |
266 |
|
267 |
\emph{A Fraction (or Proportion) being assigned, to sind one as near as |
268 |
may be equal to it, in Numbers non exceeding a Number given, and in |
269 |
the smallest Terms.} |
270 |
|
271 |
\emph{As (for instance), the Fraction $\frac{2684769}{8376571}$ (or the |
272 |
Proportion of 2684769 to 8376571) being assigned, to sind one equal to it |
273 |
(if it may be) or at least the next Greater, or the next Lesser, |
274 |
which may be expressed in Numbers not greater than 999; that is, in numbers |
275 |
not exceeding three places.} |
276 |
|
277 |
\begin{center} |
278 |
\rule{3in}{0.3mm} \\ |
279 |
\end{center} |
280 |
|
281 |
\emph{If the Fraction sought (whose terms are not to be greater than |
282 |
a Number given) be the Next Greater than a Fraction Proposed; divide the |
283 |
proposed Fractions Denominator by its Numerator: If the Next-Lesser, then |
284 |
the Numerator by the Denominator, continuing the Quotient in Decimal |
285 |
Parts, to such an Accuracy as shall be sufficient; which Quotient |
286 |
for the Next-Greater, is to be the Denominator answering to the |
287 |
Numerator 1: But for the next Lesser, it is to be |
288 |
the Numerator answering to the Denominator 1: Completing a Fraction |
289 |
as near as shall be necessary to that Proposed, which Fraction I |
290 |
call to First Fraction Compleat: And the same wanting the Appendage of |
291 |
Decimal parts, I call, the First Fraction Cartail'd.} |
292 |
|
293 |
\emph{Khen by this Appendage of the First Fraction, |
294 |
divide 1 Integer, and by the Integer Number which is Next-Less then |
295 |
the sull Quotient, (that is, in case such Quotient be just an |
296 |
Interger Number, by the Integer Next-Less than it; but is it be an Interger |
297 |
with Decimal parts annexed, than by that Integer |
298 |
without those} |
299 |
|
300 |
\emph{Decimal parts;) multiply both Terms of the first Fraction Compleat, |
301 |
(the Numerator and the Denominator;) And the Products of such |
302 |
Multiplication, I call the Continual Increments of those Terms respectively. |
303 |
And so much as the Appendage of Decimal parts in such Continual Increment |
304 |
wants of 1 Integer, I call the Complements of the Appendage of the |
305 |
continual Increment.} |
306 |
|
307 |
\emph{Then both to the Numerator and the Denominator of the First |
308 |
Fraction, add (respectively) its continual Increment, which make the Terms |
309 |
of the Second Fraction; and these again (respectively) |
310 |
increased by the same Continual |
311 |
Increment, make the Terms of the Third Fraction: And so onward, |
312 |
as long as the Fraction so arising hath an Appendage, which is not less |
313 |
than the Complement of the Appendage of the Continual Increment.} |
314 |
|
315 |
\emph{But where such Appendage becomes less than that Complement, |
316 |
that Fraction I call the Last of the First Order; which also is to |
317 |
be the First of the Second Order.''} |
318 |
\end{quote} |
319 |
|
320 |
Although Wallis' archaic English above is difficult to decipher, |
321 |
it appears that Wallis is describing the process of |
322 |
obtaining the convergents and intermediate fractions of |
323 |
the continued fraction representation of a rational number. |
324 |
|
325 |
On p. 86, Brezenski writes: |
326 |
|
327 |
\begin{quote} |
328 |
We have already mentioned the Dutch mathematician and astronomer |
329 |
Christiaan HUYGENS \index{Huygens, Christiaan} (The Hague, 14.4.1629 - The Hague, 8.6.1695). |
330 |
He made several contributions to continued fractions and related |
331 |
matters. |
332 |
|
333 |
In 1682, Huygens built an automatic planetarium. To this end, |
334 |
he used continued fractions, as described in his book |
335 |
``\emph{Descriptio automati planetarii}'', which was published |
336 |
after his death (The Hague, 1698). In one year the earth |
337 |
covers 359$^{\circ}$ $45'$ $40''$ $30'''$ and Saturn 12$^{\circ}$ |
338 |
$13'$ $34''$ $18'''$, which gives the ratio 77708431/2640858. |
339 |
|
340 |
For finding the smallest integers whose ratio is close to the preceding |
341 |
one, he divided the greatest number by the smallest, then the smallest |
342 |
by the first remainder, and so on, which is Euclid's algorithm. |
343 |
He thus got |
344 |
|
345 |
\begin{equation} |
346 |
29 + \cfrac{1}{2 + \cfrac{1}{2 + \cfrac{1}{1 + |
347 |
\cfrac{1}{5 + \cfrac{1}{1 + \cfrac{1}{4 + \ldots{}}}}}}} |
348 |
\nonumber |
349 |
\end{equation} |
350 |
|
351 |
for the ratio. |
352 |
|
353 |
The fourth convergent of this continued fraction is 206/7, which |
354 |
gave him the number of teeth for the gears of his planetarium, only |
355 |
producing an error of $40'$ in a century! [H. 177], [H. 272]. |
356 |
|
357 |
In a work, undated but not after 1687, he treats the general problem: |
358 |
|
359 |
\emph{``Etant donn\'es deux grands nombres ayant entr'eux un |
360 |
certain rapport, en trouver d'autres plus petits pour les dents |
361 |
des roues qui ne soient pas incommodes par leurs grandeurs et qui |
362 |
aient entr'eux \`a peu pr\`es le m\^eme rapport, |
363 |
de telle facon qu'aucun couple de nombres plus petits ne |
364 |
fournisse un rapport plus approchant de la vraie |
365 |
valeur.''}\footnote{English translation \index{Raspide, Sandrine@de Raspide, Sandrine} |
366 |
\cite{bibref:i:sandrinederaspide}: |
367 |
\emph{If we consider two large numbers forming a given ratio, |
368 |
we need to find another set of smaller numbers for the teeth of the gearwheels, |
369 |
which are not inconvenient in their size and which bear the very same ratio |
370 |
between them, in such a way that no other pair of smaller numbers |
371 |
brings a ratio closer to the actual value.}} |
372 |
|
373 |
Thus Huygens was conscious of the property of best approximation |
374 |
exhibited by continued fractions. He explained his method |
375 |
as follows: |
376 |
|
377 |
\emph{``Pour trouver donc des nombres plus petits qui expriment |
378 |
approximativement ce rapport, je divise le plus grand des nombres |
379 |
par le plus petit, puis le plus petit par le reste de la premi\`ere |
380 |
division et ensuite ce reste par le noveau reste \ldots{} |
381 |
Poursuivant ce calcul aussi longtemps que possible, on parvient |
382 |
enfin par la division \`a un reste 1.''}\footnote{English |
383 |
translation \index{Raspide, Sandrine@de Raspide, Sandrine} |
384 |
\cite{bibref:i:sandrinederaspide}: \emph{Thus to find some smaller numbers that |
385 |
approximately express this ratio, I divide the largest of |
386 |
the numbers by the smallest, then the smallest by the |
387 |
remainder of the first division and then this remainder by |
388 |
the new remainder, continuing this calculation as long as possible, |
389 |
we finally end up with a division into a remainder of 1.}} |
390 |
|
391 |
Then he makes the following comments: |
392 |
|
393 |
\emph{``Or, lorsqu'on n\'eglige \`a partir d'une fraction |
394 |
quelconque les derniers termes de la s\'erie et celles qui |
395 |
la suivent, et qu'on r\'eduit les autres plus le |
396 |
nombre entier \`a un commun d\'enominateur, le rapport de ce |
397 |
dernier au num\'erateur, sera voisin de celui du plus |
398 |
petit nombre donn\'e au plus grand; et la diff\'erence |
399 |
sera si faible qu'il serait impossible d'obtenir un meilleur accord |
400 |
avec des nombres plus petits.''}\footnote{English |
401 |
translation \index{Raspide, Sandrine@de Raspide, Sandrine} |
402 |
\cite{bibref:i:sandrinederaspide}: |
403 |
\emph{However, when, from an ordinary fraction, we neglect |
404 |
the last terms of the run and the ones that follow, and when |
405 |
we reduce the others plus the integer to a common denominator, |
406 |
the ratio of the latter to the numerator will be in the neighborhood |
407 |
of the smallest given number to the largest; and the difference will |
408 |
be so small that it would be impossible to obtain a better |
409 |
approximation with smaller numbers.}} |
410 |
|
411 |
He proves this result and applies it to the continued fraction |
412 |
for $\pi$. |
413 |
|
414 |
Let us give the opinion of the French astronomer |
415 |
\index{Delambre, Jean Baptiste Joseph}Jean Baptiste |
416 |
Joseph DELAMBRE (Amiens, 19.9.1749 - Paris, 19.8.1822), about |
417 |
this part of Huygens' work. It is quite interesting [H. 108]: |
418 |
|
419 |
\emph{`` \ldots{}; enfin il d\'ecrit son plan\'etaire.}\footnote{English |
420 |
translation \index{Raspide, Sandrine@de Raspide, Sandrine} |
421 |
\cite{bibref:i:sandrinederaspide}: |
422 |
\emph{\ldots{}; finally, he describes his planetarium.}} |
423 |
|
424 |
\emph{Ces sortes de machines ne sont que des objets de |
425 |
curiosit\'e pour les amateurs, ils sont absolument inutiles |
426 |
\`a l'Astronomie; celle \index{Huygens, Christiaan}d'Huygens |
427 |
\'etait destin\'ee \`a montrer |
428 |
les mouvements elliptiques des plan\`etes, suivant les id\'ees |
429 |
de \index{Kepler, Johannes}K\'epler. Le probl\`eme \`a r\'esoudre \'etait celui-ci: |
430 |
Etant donn\'e deux grands nombres, trouver deux autres nombres plus |
431 |
pitits et plus commodes, qui soient \`a peu pr\`es dans la m\^eme raison. |
432 |
Il y emploie les fractions continues, et sans donner la |
433 |
th\'eorie analytique de ces fractions, il les applique \`a des |
434 |
exemples. Il trouve ainsi le nombre des dents qui'il convient de donner |
435 |
aux roues.}\footnote{English translation \index{Raspide, Sandrine@de Raspide, Sandrine} |
436 |
\cite{bibref:i:sandrinederaspide}: \emph{These kinds of machines are |
437 |
mere objects of curiosity for the amateurs, completely useless to astronomy; |
438 |
Huygens' machine was meant to demonstrate the elliptic movements of the |
439 |
planets, following Kepler's ideas. The problem to solve was the following: |
440 |
given two large numbers, we need to find two other numbers, smaller and |
441 |
more convenient, which are more or less in the same ratio. To achieve |
442 |
this, Huygens uses continued ratios, and, without giving the analytic |
443 |
theory of these ratios, he applies it to some examples. Thus, he is able |
444 |
to determine the number of teeth needed for the gearwheels.}} |
445 |
|
446 |
\emph{Cette propri\'et\'e des fractions continues, para\^{\i}t \`a |
447 |
\index{Lagrange, Joseph-Louis}Lagrange, une des principales d\'ecouvertes |
448 |
d'Huygens. Cet \'eloge |
449 |
un peu exag\'er\'e fut sans doute dict\'e \`a |
450 |
Lagrange par l'usage qu'il a su faire de ces fractions dans l'Analyse. |
451 |
Quelques g\'eom\`etres ont paru douter des avantages de ces fractions et |
452 |
de l'utilit\'e |
453 |
qu'elles peuvent avoir dans les recherches analytiques. Quant au |
454 |
probl\`eme des rouages, il nous semble qu'on peut le r\'esoudre d'une |
455 |
mani\`ere plus simple et plus commode par l'Arithm\'etique ordinaire. |
456 |
Nous avons d\'ej\`a appliqu\'e notre m\'ethode |
457 |
aux intercalations du calendrier. Nous allons l'appliquer aux deux |
458 |
exemples choisis par Huyhens.''}\footnote{English |
459 |
translation \index{Raspide, Sandrine@de Raspide, Sandrine} |
460 |
\cite{bibref:i:sandrinederaspide}: |
461 |
\emph{The property of continued fractions seems, to Lagrange, |
462 |
one of the main discoveries of Huygens. This slightly overdone |
463 |
praise was probably induced in Lagrange for the use that he made of |
464 |
the fractions in his Analysis. Some surveyors seemed to have questioned |
465 |
the advantages of these fractions and their use in analytical research. |
466 |
As far as the gearing problem is concerned, it seems to us that we can |
467 |
solve it in a simpler and easier way with ordinary arithmetic. |
468 |
We have already applied our methodology to the intercalation of the calendar. |
469 |
We are going to apply it to the two examples chosen by Huygens.}} |
470 |
|
471 |
Delambre concludes: |
472 |
|
473 |
\emph{``Les fractions continues ne m'ont jamais paru qu'une chose |
474 |
curieuse qui, au reste, ne servait qu'\`a obscurcir et compliquer et je |
475 |
n'en ai jamais fait d'usage que pour m'en d\'emontrer |
476 |
l'inutilit\'e.''}\footnote{English translation |
477 |
\index{Raspide, Sandrine@de Raspide, Sandrine} |
478 |
\cite{bibref:i:sandrinederaspide}: |
479 |
\emph{Continued fractions never appeared to me as something more |
480 |
than a mere curiosity that, at the end of the day, only serves |
481 |
to darken and complicate matters, and I only used them to |
482 |
demonstrate their uselessness.}} |
483 |
|
484 |
This was not a prophetic view! |
485 |
\end{quote} |
486 |
|
487 |
Thus, it is clear that the use of continued fraction convergents |
488 |
as best rational approximations dates back to at least the |
489 |
17th century (this is the first part of |
490 |
Theorem \ref{thm:ccfr0:scba0:cfenclosingneighbors}). However, |
491 |
the details of the historical appearance of the second part of |
492 |
Theorem \ref{thm:ccfr0:scba0:cfenclosingneighbors} (the formula |
493 |
for the other Farey neighbor, Eq. \ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01}) |
494 |
are not known to the authors. |
495 |
|
496 |
|
497 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
498 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
499 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
500 |
\section{Overview Of The Apparatus} |
501 |
%Section tag: PAR0 |
502 |
|
503 |
The apparatus of continued fractions is best viewed as |
504 |
an alternate apparatus for representing real numbers. |
505 |
Knowledge of the first $n$ partial quotients of |
506 |
the continued fraction representation of a real number |
507 |
$x$ is equivalent to the knowledge that the number lies |
508 |
in a certain partition (Eqns. |
509 |
\ref{eq:ccfr0:spar0:01}, |
510 |
\ref{eq:ccfr0:spar0:02}, and \ref{eq:ccfr0:spar0:03}). With additional |
511 |
partial quotients, the partitions become more restrictive. |
512 |
|
513 |
\begin{equation} |
514 |
\label{eq:ccfr0:spar0:01} |
515 |
(x=[a_0] \vee x=[a_0; \ldots ] ) \leftrightarrow (a_0 \leq x < a_0 + 1) |
516 |
\end{equation} |
517 |
|
518 |
\begin{equation} |
519 |
\label{eq:ccfr0:spar0:02} |
520 |
(x=[a_0; a_1] \vee x=[a_0; a_1, \ldots ] ) \leftrightarrow |
521 |
\left( |
522 |
{ |
523 |
a_0 + \frac{1}{a_1 + 1} < x \leq a_0 + \frac{1}{a_1} |
524 |
} |
525 |
\right) |
526 |
\end{equation} |
527 |
|
528 |
\begin{equation} |
529 |
\label{eq:ccfr0:spar0:03} |
530 |
\begin{array}{c} |
531 |
(x=[a_0; a_1, a_2] \vee x=[a_0; a_1, a_2, \ldots ] ) \vspace{0.05in}\\ |
532 |
\updownarrow \vspace{0.0in}\\ |
533 |
\left( |
534 |
{ |
535 |
a_0+\cfrac{1}{a_1 + \cfrac{1}{a_2}} \leq x < a_0+\cfrac{1}{a_1 + \cfrac{1}{a_2+1}} |
536 |
} |
537 |
\right) |
538 |
\end{array} |
539 |
\end{equation} |
540 |
|
541 |
Algorithms for finding the continued fraction representation |
542 |
of a real number are best viewed as algorithms for |
543 |
determining in which partition a real number lies. However, what is |
544 |
special (for our purposes) is that the partitions imposed by the |
545 |
apparatus of continued fractions have a special relationship |
546 |
with best rational approximations---namely, that all numbers (both |
547 |
rational and irrational) with the same partial quotients up to a |
548 |
point also have the same Farey neighbors up to a certain order. |
549 |
Stated more colloquially, the apparatus of continued fractions |
550 |
hacks up the real number line in a way that is especially meaningful |
551 |
for finding best rational approximations. |
552 |
|
553 |
|
554 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
555 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
556 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
557 |
\section[CF Representation Of Rationals] |
558 |
{Continued Fraction Representation Of Rational Numbers} |
559 |
%Section tag: CRN0 |
560 |
|
561 |
Without proof, we present the following algorithm, Algorithm |
562 |
\ref{alg:ccfr0:scrn0:akgenalg}, for |
563 |
determining the continued fraction representation (i.e. the partial |
564 |
quotients) of a non-negative |
565 |
rational number $a/b$. |
566 |
|
567 |
\begin{vworkalgorithmstatementpar}{Continued Fraction Representation Of |
568 |
A Rational Number \mbox{\boldmath $a/b$}} |
569 |
\label{alg:ccfr0:scrn0:akgenalg} |
570 |
\begin{alglvl0} |
571 |
\item $k:=-1$. |
572 |
\item $divisor_{-1} := a$. |
573 |
\item $remainder_{-1} := b$. |
574 |
|
575 |
\item Repeat |
576 |
|
577 |
\begin{alglvl1} |
578 |
\item $k := k + 1$. |
579 |
\item $dividend_k := divisor_{k-1}$. |
580 |
\item $divisor_k := remainder_{k-1}$. |
581 |
\item $a_k := dividend_k \; div \; divisor_k$. |
582 |
\item $remainder_k := dividend_k \; mod \; divisor_k$. |
583 |
\end{alglvl1} |
584 |
|
585 |
\item Until ($remainder_k = 0$). |
586 |
\end{alglvl0} |
587 |
\end{vworkalgorithmstatementpar} |
588 |
%\vworkalgorithmfooter{} |
589 |
|
590 |
\begin{vworkexamplestatement} |
591 |
\label{ex:ccfr0:scrn0:01} |
592 |
Find the continued fraction partial quotients of |
593 |
$67/29$.\footnote{This example is reproduced from |
594 |
Olds \cite{bibref:b:OldsClassic}, p. 8.} |
595 |
\end{vworkexamplestatement} |
596 |
\begin{vworkexampleparsection}{Solution} |
597 |
\begin{table} |
598 |
\caption{Continued Fraction Partial Quotients Of $67/29$ (Example \ref{ex:ccfr0:scrn0:01})} |
599 |
\label{tbl:ccfr0:scrn0:01} |
600 |
\begin{center} |
601 |
\begin{tabular}{|c|c|c|c|c|} |
602 |
\hline |
603 |
\small{Index} & \small{$dividend_k$} & \small{$divisor_k$} & \small{$a_k$} & \small{$remainder_k$} \\ |
604 |
\small{($k$)} & & & & \\ |
605 |
\hline |
606 |
\hline |
607 |
\small{-1} & \small{N/A} & \small{67} & \small{N/A} & \small{29} \\ |
608 |
\hline |
609 |
\small{0} & \small{67} & \small{29} & \small{2} & \small{9} \\ |
610 |
\hline |
611 |
\small{1} & \small{29} & \small{9} & \small{3} & \small{2} \\ |
612 |
\hline |
613 |
\small{2} & \small{9} & \small{2} & \small{4} & \small{1} \\ |
614 |
\hline |
615 |
\small{3} & \small{2} & \small{1} & \small{2} & \small{0} \\ |
616 |
\hline |
617 |
\end{tabular} |
618 |
\end{center} |
619 |
\end{table} |
620 |
Table \ref{tbl:ccfr0:scrn0:01} shows the application of |
621 |
Algorithm \ref{alg:ccfr0:scrn0:akgenalg} to find the |
622 |
continued fraction partial quotients of $67/29$. From |
623 |
Table \ref{tbl:ccfr0:scrn0:01}, the continued fraction |
624 |
representation of $67/29$ is $[2;3,4,2]$. |
625 |
\end{vworkexampleparsection} |
626 |
\vworkexamplefooter{} |
627 |
|
628 |
The process of obtaining the continued fraction representation of |
629 |
a rational number is a |
630 |
process of obtaining each partial quotient $a_i$, and then processing the |
631 |
remainder at each step to obtain further partial quotients. Noting that |
632 |
the dividend and divisor at each step come from previous remainders |
633 |
(except for $k=0$ and $k=1$) allows us to simplify notation from |
634 |
Algorithm \ref{alg:ccfr0:scrn0:akgenalg}. If $r_i$ is used to |
635 |
denote the remainder from the division that produced $a_i$, the following |
636 |
recursive equations come immediately. |
637 |
|
638 |
\begin{equation} |
639 |
\label{eq:ccfr0:scrn0:00a} |
640 |
\frac{a}{b} |
641 |
= |
642 |
a_0 + \frac{r_0}{b} |
643 |
= |
644 |
a_0 + \frac{1}{\frac{b}{r_0}} |
645 |
, \; 0 < r_0 < b |
646 |
\end{equation} |
647 |
|
648 |
\begin{equation} |
649 |
\label{eq:ccfr0:scrn0:00b} |
650 |
\frac{b}{r_0} |
651 |
= |
652 |
a_1 + \frac{r_1}{r_0} |
653 |
, \; 0 < r_1 < r_0 |
654 |
\end{equation} |
655 |
|
656 |
\begin{equation} |
657 |
\label{eq:ccfr0:scrn0:00c} |
658 |
\frac{r_0}{r_1} |
659 |
= |
660 |
a_2 + \frac{r_2}{r_1} |
661 |
, \; 0 < r_2 < r_1 |
662 |
\end{equation} |
663 |
|
664 |
\noindent{}Finally, nearing the termination of |
665 |
Algorithm \ref{alg:ccfr0:scrn0:akgenalg}: |
666 |
|
667 |
\begin{equation} |
668 |
\label{eq:ccfr0:scrn0:00d} |
669 |
\frac{r_{n-3}}{r_{n-2}} |
670 |
= |
671 |
a_{n-1} + \frac{r_{n-1}}{r_{n-2}} |
672 |
, \; 0 < r_{n-1} < r_{n-2} |
673 |
\end{equation} |
674 |
|
675 |
\begin{equation} |
676 |
\label{eq:ccfr0:scrn0:00e} |
677 |
\frac{r_{n-2}}{r_{n-1}} |
678 |
= |
679 |
a_n |
680 |
\end{equation} |
681 |
|
682 |
A natural question to ask is whether Algorithm \ref{alg:ccfr0:scrn0:akgenalg} |
683 |
will always terminate---that is, whether we can always find a continued |
684 |
fraction representation of a rational number. We present this result |
685 |
as Lemma \ref{lem:ccfr0:scrn0:alwaysterminates}. |
686 |
|
687 |
\begin{vworklemmastatement} |
688 |
\label{lem:ccfr0:scrn0:alwaysterminates} |
689 |
Algorithm \ref{alg:ccfr0:scrn0:akgenalg} will always terminate: that is, |
690 |
every rational number has a finite continued fraction representation |
691 |
$[a_0; a_1, \ldots{} , a_n]$. |
692 |
\end{vworklemmastatement} |
693 |
\begin{vworklemmaproof} |
694 |
Note in Algorithm \ref{alg:ccfr0:scrn0:akgenalg} and in |
695 |
(\ref{eq:ccfr0:scrn0:00a}) through (\ref{eq:ccfr0:scrn0:00e}) |
696 |
that the remainder of one round becomes the divisor of the |
697 |
next round, hence the remainders must form a decreasing sequence |
698 |
|
699 |
\begin{equation} |
700 |
\label{eq:lem:ccfr0:scrn0:alwaysterminates} |
701 |
r_0 > r_1 > r_2 > \ldots{} > r_{n-2} > r_{n-1} , |
702 |
\end{equation} |
703 |
|
704 |
because in general a remainder must be less than the divisor in |
705 |
the division that created it. |
706 |
\end{vworklemmaproof} |
707 |
\vworklemmafooter{} |
708 |
|
709 |
|
710 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
711 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
712 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
713 |
\section{Convergents And Intermediate Fractions} |
714 |
%Section tag: CNV0 |
715 |
\label{ccfr0:scnf0} |
716 |
|
717 |
Lemma \ref{lem:ccfr0:scrn0:alwaysterminates} shows that every |
718 |
rational number has a finite continued fraction representation. A second |
719 |
reasonable question to ask is whether every finite simple continued |
720 |
fraction corresponds to a rational number. The most convincing way |
721 |
to answer that question would be to devise a concrete procedure for |
722 |
[re-]constructing a rational number from its continued fraction |
723 |
representation. |
724 |
|
725 |
Given a finite continued fraction $[a_0; a_1, \ldots{}, a_n]$, it is |
726 |
obvious that a rational number can be constructed using the same |
727 |
algebraic technique that would be applied by hand. Such a technique |
728 |
involves ``reconstruction from the right'' because we would begin |
729 |
by using $a_n$ and then work backwards to $a_0$. We illustrate |
730 |
the most obvious technique with an example. |
731 |
|
732 |
\begin{vworkexamplestatement} |
733 |
\label{ex:ccfr0:scnv0:abreconstructionfromright:01} |
734 |
Find a rational number $a/b$ corresponding to the |
735 |
continued fraction $[2;3,4,2]$. |
736 |
\end{vworkexamplestatement} |
737 |
\begin{vworkexampleparsection}{Solution} |
738 |
The most obvious technique is to write out the continued fraction and then to |
739 |
algebraically simplify the continued fraction from the bottom up (this |
740 |
is what we call ``working from the right'', as we begin with $a_n$). |
741 |
(\ref{eq:ccfr0:scnv0:ex:abreconstructionfromright:00}) through |
742 |
(\ref{eq:ccfr0:scnv0:ex:abreconstructionfromright:02}) |
743 |
illustrate this technique. |
744 |
|
745 |
\begin{equation} |
746 |
\label{eq:ccfr0:scnv0:ex:abreconstructionfromright:00} |
747 |
[2;3,4,2] = |
748 |
2 + \cfrac{1}{3 + \cfrac{1}{4 + \cfrac{1}{2}}} |
749 |
\end{equation} |
750 |
|
751 |
\begin{equation} |
752 |
\label{eq:ccfr0:scnv0:ex:abreconstructionfromright:01} |
753 |
[2;3,4,2] = |
754 |
2 + \cfrac{1}{3 + \cfrac{2}{9}} |
755 |
\end{equation} |
756 |
|
757 |
\begin{equation} |
758 |
\label{eq:ccfr0:scnv0:ex:abreconstructionfromright:02} |
759 |
[2;3,4,2] = |
760 |
2 + \frac{9}{29} = \frac{67}{29} |
761 |
\end{equation} |
762 |
|
763 |
\end{vworkexampleparsection} |
764 |
\vworkexamplefooter{} |
765 |
|
766 |
Although converting a continued fraction $[a_0; a_1, \ldots{}, a_n]$ |
767 |
to a rational number working ``from the right'' is the most |
768 |
intuitively obvious technique because it mirrors how a |
769 |
continued fraction would most naturally be simplified by |
770 |
hand, it is also possible to convert a continued fraction to |
771 |
a rational number ``from the left''. In all subsequent |
772 |
discussions we embrace the ``from the left'' technique because |
773 |
it allows us to more economically calculate \emph{convergents}, which |
774 |
have special properties, and which we now describe. |
775 |
|
776 |
\index{continued fraction!convergent} |
777 |
The \emph{kth order convergent} of a continued fraction |
778 |
$[a_0; a_1, \ldots{}, a_n]$ is the irreducible rational number |
779 |
corresponding to $[a_0; a_1, \ldots{}, a_k]$, $k \leq n$. |
780 |
In other words, the $k$th order convergent is the irreducible rational number |
781 |
corresponding to the first $k+1$ partial quotients of a |
782 |
continued fraction.\footnote{``$k+1$'' because the notational |
783 |
numbering |
784 |
for partial quotients starts at 0 rather than 1.} |
785 |
|
786 |
An $n$th order continued fraction $[a_0; a_1, \ldots{}, a_n]$ |
787 |
has $n+1$ convergents, $[a_0]$, |
788 |
$[a_0; a_1]$, \ldots{}, and $[a_0; a_1, \ldots{}, a_n]$. |
789 |
We denote the $k$th order convergent as $s_k$, with numerator |
790 |
$p_k$ and denominator $q_k$. |
791 |
|
792 |
\begin{vworkexamplestatement} |
793 |
\label{ex:ccfr0:scnv0:convergentexample:01} |
794 |
Find all convergents of $[2;3,4,2]$. |
795 |
\end{vworkexamplestatement} |
796 |
\begin{vworkexampleparsection}{Solution}\hspace{-0.4em}\footnote{Canonically, it is |
797 |
required that all convergents be irreducible. Any valid method can be used to |
798 |
calculate convergents---including algebraic simplification---so long as the |
799 |
rational numbers obtained are irreducible.} |
800 |
\begin{equation} |
801 |
s_0 = [a_0] = [2] = 2 = \frac{2}{1} = \frac{p_0}{q_0} |
802 |
\end{equation} |
803 |
|
804 |
\begin{equation} |
805 |
s_1 = [a_0;a_1] = [2;3] = 2 + \frac{1}{3} = \frac{7}{3} = \frac{p_1}{q_1} |
806 |
\end{equation} |
807 |
|
808 |
\begin{equation} |
809 |
s_2 = [a_0;a_1,a_2] = |
810 |
[2;3,4] = |
811 |
2 + \cfrac{1}{3 + \cfrac{1}{4}} = \frac{30}{13} = \frac{p_2}{q_2} |
812 |
\end{equation} |
813 |
|
814 |
\begin{equation} |
815 |
s_3 = [a_0;a_1,a_2,a_3] = [2;3,4,2] = |
816 |
2 + \cfrac{1}{3 + \cfrac{1}{4 + \cfrac{1}{2}}} = \frac{67}{29} = \frac{p_3}{q_3} |
817 |
\end{equation} |
818 |
\end{vworkexampleparsection} |
819 |
\vworkexamplefooter{} |
820 |
|
821 |
We now move on to the question of how to convert a continued fraction |
822 |
to a rational number ``from the left''. We present the |
823 |
canonical algorithm for construction of convergents ``from the left''. |
824 |
In addition |
825 |
to producing irreducible rational numbers (we prove this property |
826 |
later), the algorithm is |
827 |
convenient because it is economical---lower-order convergents |
828 |
are used in the calculation of higher-order convergents and there |
829 |
are no wasted calculations. |
830 |
|
831 |
\begin{vworktheoremstatementpar}{Rule For Canonical Construction Of Continued Fraction |
832 |
Convergents} |
833 |
\label{thm:ccfr0:scnv0:canonicalconvergentconstruction} |
834 |
The numerators $p_i$ and the denominators $q_i$ of the $i$th |
835 |
convergent $s_i$ of the continued fraction |
836 |
$[a_0;a_1, \ldots{} , a_n]$ satisfy the equations |
837 |
|
838 |
\begin{eqnarray} |
839 |
\label{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:01} |
840 |
p_i & = & a_i p_{i-1} + p_{i-2} \\ |
841 |
\label{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:02} |
842 |
q_i & = & a_i q_{i-1} + q_{i-2} |
843 |
\end{eqnarray} |
844 |
|
845 |
\noindent{}with the initial values |
846 |
|
847 |
\begin{eqnarray} |
848 |
\label{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:03} |
849 |
p_0 = a_0, & & p_1 = a_0 a_1 + 1, \\ |
850 |
\label{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:04} |
851 |
q_0 = 1, & & q_1 = a_1 . |
852 |
\end{eqnarray} |
853 |
\end{vworktheoremstatementpar} |
854 |
\begin{vworktheoremproof}\hspace{-0.4em}\footnote{Reproduced nearly |
855 |
verbatim from \cite{bibref:b:OldsClassic}, Theorem 1.3, pp. 21-23.} |
856 |
The proof is inductive. First, the case of $i=2$ is verified, |
857 |
then an inductive step is used to show that the theorem applies |
858 |
for $i \geq 3$. |
859 |
|
860 |
To create a canonical form, we assign |
861 |
$s_0 = [a_0] = p_0/q_0 = a_0/1$. Thus, in all cases, $p_0 = a_0$ |
862 |
and $q_0 = 1$. Similarly, to create a unique canonical form, |
863 |
|
864 |
\begin{equation} |
865 |
\label{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:05} |
866 |
s_1 = [a_0;a_1] = a_0 + \frac{1}{a_1} = \frac{a_0 a_1 + 1}{a_1} = \frac{p_1}{q_1} , |
867 |
\end{equation} |
868 |
|
869 |
\noindent{}and canonically, $p_1 = a_0 a_1 + 1$ and $q_1 = a_1$. |
870 |
|
871 |
For $i=2$, we need to verify that the algebraic results coincide with the |
872 |
claims of the theorem. Simplifying $s_2$ algebraically leads to |
873 |
|
874 |
\begin{equation} |
875 |
\label{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:06} |
876 |
\begin{array}{c} |
877 |
s_2 = [a_0;a_1,a_2] = |
878 |
a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2}} = |
879 |
a_0 + \cfrac{1}{\cfrac{a_1 a_2 + 1}{a_2}} = a_0 + \cfrac{a_2}{a_1 a_2 + 1} \\ |
880 |
\\ |
881 |
=\cfrac{a_0 (a_1 a_2 + 1) + a_2}{a_1 a_2 + 1} |
882 |
=\cfrac{a_2(a_0 a_1 + 1) + a_0}{a_2 a_1 + 1} . |
883 |
\end{array} |
884 |
\end{equation} |
885 |
|
886 |
\noindent{}On the other hand, applying the recursive formula |
887 |
claimed by the theorem (Eqns. |
888 |
\ref{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:01}, |
889 |
\ref{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:02}) yields |
890 |
|
891 |
\begin{equation} |
892 |
\label{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:07} |
893 |
s_2 = \frac{a_2 p_1 + p_0}{a_2 q_1 + q_0} |
894 |
= \frac{a_2(a_0 a_1 + 1) + a_0}{a_2 (a_1) + 1} , |
895 |
\end{equation} |
896 |
|
897 |
which, on inspection, is consistent with the results of |
898 |
(\ref{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:06}). |
899 |
|
900 |
We now prove the inductive step. Assume that |
901 |
the recursive relationships supplied as |
902 |
(\ref{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:01}) |
903 |
and (\ref{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:02}) |
904 |
hold up through some $s_k = p_k/q_k$. We would like to show that |
905 |
(\ref{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:01}) |
906 |
and (\ref{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:02}) |
907 |
then hold for $s_{k+1}$. |
908 |
|
909 |
$s_k$ is a fraction of the form |
910 |
|
911 |
\begin{equation} |
912 |
\label{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:07b} |
913 |
s_k |
914 |
= |
915 |
[a_0; a_1, a_2, \ldots , a_k] |
916 |
= |
917 |
a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 |
918 |
+ \cfrac{1}{\;\;\;\;\;\;\;\;\;\;\;\;\;\;\ldots + |
919 |
\cfrac{1}{a_{k-1} + \cfrac{1}{a_k}}}}} . |
920 |
\end{equation} |
921 |
|
922 |
In order to form $s_{k+1}$, note that we can replace $a_k$ by |
923 |
$a_k + 1/a_{k + 1}$. (Note that there is no requirement |
924 |
in Eqns. \ref{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:01}, |
925 |
\ref{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:02}, |
926 |
\ref{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:06}, |
927 |
\ref{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:07}, |
928 |
or \ref{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:07b} |
929 |
that the partial quotients $a_i$ be integers.) |
930 |
In other words, we can form a |
931 |
$k$th order continued fraction having the same value as a |
932 |
$k+1$th order continued fraction by substituting |
933 |
$a_k := a_k + \frac{1}{a_{k + 1}}$. Using this substitution |
934 |
we can calculate $s_{k+1}$ using the same recursive |
935 |
relationship shown to be valid in calculating $s_k$: |
936 |
|
937 |
\begin{equation} |
938 |
\label{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:08} |
939 |
\begin{array}{c} |
940 |
s_{k+1} = |
941 |
\cfrac |
942 |
{\left( {a_k+\cfrac{1}{a_{k+1}} } \right) p_{k-1} + p_{k-2}} |
943 |
{\left( {a_k+\cfrac{1}{a_{k+1}} } \right) q_{k-1} + q_{k-2}} |
944 |
= |
945 |
\cfrac |
946 |
{(a_k a_{k+1} + 1) p_{k-1} + a_{k+1} p_{k-2}} |
947 |
{(a_k a_{k+1} + 1) q_{k-1} + a_{k+1} q_{k-2}} \\ |
948 |
\\ |
949 |
= |
950 |
\cfrac |
951 |
{a_{k+1} (a_k p_{k-1} + p_{k-2}) + p_{k-1}} |
952 |
{a_{k+1} (a_k q_{k-1} + q_{k-2}) + q_{k-1}} |
953 |
\end{array} |
954 |
\end{equation} |
955 |
|
956 |
Now, we can use the assumption that the recursive relationships |
957 |
hold for $s_k$, i.e. |
958 |
|
959 |
\begin{eqnarray} |
960 |
\label{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:09} |
961 |
p_k = a_k p_{k-1} + p_{k-2} \\ |
962 |
\label{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:10} |
963 |
q_k = a_k q_{k-1} + q_{k-2} |
964 |
\end{eqnarray} |
965 |
|
966 |
Substituting |
967 |
(\ref{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:09}) and |
968 |
(\ref{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:10}) into |
969 |
(\ref{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:08}) yields |
970 |
|
971 |
\begin{equation} |
972 |
\label{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:11} |
973 |
s_{k+1} = \frac{p_{k+1}}{q_{k+1}} |
974 |
= \frac{a_{k+1} p_k + p_{k-1}}{a_{k+1} q_k + q_{k-1}} . |
975 |
\end{equation} |
976 |
|
977 |
\noindent{}This completes the inductive step and the proof. |
978 |
\end{vworktheoremproof} |
979 |
\begin{vworktheoremparsection}{Remarks} |
980 |
Note that this algorithm gives a way to convert a continued fraction |
981 |
$[a_0;a_1,\ldots{},a_n]$ to a rational number $a/b$, as the value of |
982 |
a continued fraction is the value of the final convergent $s_n$. |
983 |
Note also that it is possible to convert a continued fraction to |
984 |
a rational number starting from $a_n$ (i.e. working ``from |
985 |
the right''), and that starting with $a_n$ is probably the |
986 |
more intuitive approach. |
987 |
\end{vworktheoremparsection} |
988 |
\vworktheoremfooter{} |
989 |
|
990 |
It is sometimes convenient to consider a convergent of order |
991 |
$-1$ (\cite{bibref:b:KhinchinClassic}, p. 5), and for |
992 |
algebraic convenience to adopt the convention that |
993 |
$p_{-1} = 1$ and $q_{-1} = 0$. If this is done, the recursive |
994 |
relationships of Theorem \ref{thm:ccfr0:scnv0:canonicalconvergentconstruction} |
995 |
apply for $k \geq 1$ rather than for $k \geq 2$. All of the subsequent |
996 |
theorems and proofs assume this convention. |
997 |
|
998 |
We now prove several properties of convergents. |
999 |
|
1000 |
\begin{vworktheoremstatement} |
1001 |
\label{thm:ccfr0:scnv0:crossproductminusone} |
1002 |
For all $k \geq 0$, |
1003 |
|
1004 |
\begin{equation} |
1005 |
\label{eq:ccfr0:scnv0:thm:crossproductminusone:00} |
1006 |
q_k p_{k-1} - p_k q_{k-1} = (-1)^k |
1007 |
\end{equation} |
1008 |
\end{vworktheoremstatement} |
1009 |
\begin{vworktheoremproof}\hspace{-0.4em}\footnote{From |
1010 |
\cite{bibref:b:KhinchinClassic}, Theorem 2, p. 5.} |
1011 |
Multiplying (\ref{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:01}) |
1012 |
by $p_{k-1}$, multiplying |
1013 |
(\ref{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:02}) by |
1014 |
$q_{k-1}$, then subtracting the equations yields |
1015 |
|
1016 |
\begin{equation} |
1017 |
\label{eq:ccfr0:scnv0:thm:crossproductminusone:01} |
1018 |
q_k p_{k-1} - p_k q_{k-1} = -(q_{k-1} p_{k-2} - p_{k-1} q_{k-2}) , |
1019 |
\end{equation} |
1020 |
|
1021 |
and since $q_0 p_{-1} - p_0 q_{-1} = 1$, the theorem is |
1022 |
proved. |
1023 |
\end{vworktheoremproof} |
1024 |
\begin{vworktheoremparsection}{Corollary I} |
1025 |
For all $k \geq 1$, |
1026 |
|
1027 |
\begin{equation} |
1028 |
\label{eq:ccfr0:scnv0:thm:crossproductminusone:02} |
1029 |
\frac{p_{k-1}}{q_{k-1}} - \frac{p_k}{q_k} = \frac{(-1)^k}{q_k q_{k-1}} . |
1030 |
\end{equation} |
1031 |
\end{vworktheoremparsection} |
1032 |
\begin{vworktheoremproof} |
1033 |
(\ref{eq:ccfr0:scnv0:thm:crossproductminusone:02}) can be obtained |
1034 |
in a straightforward way by algebraic operations on |
1035 |
(\ref{eq:ccfr0:scnv0:thm:crossproductminusone:00}). |
1036 |
\end{vworktheoremproof} |
1037 |
%\vworktheoremfooter{} |
1038 |
|
1039 |
\begin{vworktheoremstatement} |
1040 |
\label{thm:ccfr0:scnv0:crossproductminusonebacktwo} |
1041 |
For all $k \geq 1$, |
1042 |
|
1043 |
\begin{equation} |
1044 |
q_k p_{k-2} - p_k q_{k-2} = (-1)^{k-1} a_k . |
1045 |
\end{equation} |
1046 |
\end{vworktheoremstatement} |
1047 |
\begin{vworktheoremproof}\hspace{-0.4em}\footnote{From |
1048 |
\cite{bibref:b:KhinchinClassic}, Theorem 3, p. 6.} |
1049 |
By multiplying (\ref{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:01}) |
1050 |
by $q_{k-2}$ and |
1051 |
(\ref{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:02}) |
1052 |
by $p_{k-2}$ and then subtracting the first from the |
1053 |
second, we obtain, on the basis of Theorem |
1054 |
\ref{thm:ccfr0:scnv0:crossproductminusone}, |
1055 |
|
1056 |
\begin{equation} |
1057 |
q_k p_{k-2} - p_k q_{k-2} |
1058 |
= a_k (q_{k-1} p_{k-2} - p_{k-1} q_{k-2}) = (-1)^{k-1} a_k , |
1059 |
\end{equation} |
1060 |
which completes the proof. |
1061 |
\end{vworktheoremproof} |
1062 |
\vworktheoremfooter{} |
1063 |
|
1064 |
The results in Theorems \ref{thm:ccfr0:scnv0:crossproductminusone} |
1065 |
and \ref{thm:ccfr0:scnv0:crossproductminusonebacktwo} allow us |
1066 |
to establish the relative ordering of convergents. |
1067 |
Theorems \ref{thm:ccfr0:scnv0:crossproductminusone} and |
1068 |
\ref{thm:ccfr0:scnv0:crossproductminusonebacktwo} demonstrate that |
1069 |
even-ordered convergents form an increasing sequence and that odd-ordered |
1070 |
convergents form a decreasing sequence, and that every odd-ordered convergent |
1071 |
is greater than every even-ordered convergent. |
1072 |
|
1073 |
\begin{vworktheoremstatement} |
1074 |
\label{thm:ccfr0:scnv0:irreducibility} |
1075 |
For all $k \geq 0$, $s_k = p_k/q_k$ is |
1076 |
irreducible. |
1077 |
\end{vworktheoremstatement} |
1078 |
\begin{vworktheoremproof} |
1079 |
This proof comes immediately from the form |
1080 |
of (\ref{eq:ccfr0:scnv0:thm:crossproductminusone:00}). |
1081 |
Without coprimality of $p_k$ and $q_k$, the difference |
1082 |
of $\pm 1$ is impossible (see |
1083 |
\cprizeroxrefcomma{}Lemma \ref{lem:cpri0:ppn0:000p}). |
1084 |
\end{vworktheoremproof} |
1085 |
%\vworktheoremfooter{} |
1086 |
|
1087 |
\begin{vworkexamplestatement} |
1088 |
\label{ex:ccfr0:scrn0:abreconstruction:01} |
1089 |
Find an irreducible rational number $a/b$ corresponding to the |
1090 |
continued fraction $[2;3,4,2]$. |
1091 |
\end{vworkexamplestatement} |
1092 |
\begin{vworkexampleparsection}{Solution} |
1093 |
Application of Theorem \ref{thm:ccfr0:scnv0:canonicalconvergentconstruction} |
1094 |
yields the following convergents. The final convergent $s_3$ is the |
1095 |
value of the continued fraction $[2;3,4,2]$ and Theorem |
1096 |
\ref{thm:ccfr0:scnv0:irreducibility} assures us that each convergent is |
1097 |
irreducible. |
1098 |
|
1099 |
\begin{equation} |
1100 |
\label{eq:ccfr0:scrn0:02a} |
1101 |
p_{-1} = 1, \; q_{-1} = 0 |
1102 |
\end{equation} |
1103 |
|
1104 |
\begin{equation} |
1105 |
\label{eq:ccfr0:scrn0:02b} |
1106 |
s_0 = \frac{p_0}{q_0} = \frac{a_0}{1} = \frac{2}{1} |
1107 |
\end{equation} |
1108 |
|
1109 |
\begin{equation} |
1110 |
\label{eq:ccfr0:scrn0:02c} |
1111 |
s_1 = \frac{p_1}{q_1} = \frac{a_1 p_0 + p_{-1}}{a_1 q_0 + q_{-1}} |
1112 |
= \frac{(3)(2) + (1)}{(3)(1)+(0)} |
1113 |
= \frac{7}{3} |
1114 |
\end{equation} |
1115 |
|
1116 |
\begin{equation} |
1117 |
\label{eq:ccfr0:scrn0:02d} |
1118 |
s_2 = \frac{p_2}{q_2} = \frac{a_2 p_1 + p_{0}}{a_2 q_1 + q_{0}} |
1119 |
= \frac{(4)(7) + (2)}{(4)(3)+(1)} |
1120 |
= \frac{30}{13} |
1121 |
\end{equation} |
1122 |
|
1123 |
\begin{equation} |
1124 |
\label{eq:ccfr0:scrn0:02e} |
1125 |
s_3 = \frac{p_3}{q_3} = \frac{a_3 p_2 + p_{1}}{a_3 q_2 + q_{1}} |
1126 |
= \frac{(2)(30) + (7)}{(2)(13)+(3)} |
1127 |
= \frac{67}{29} |
1128 |
\end{equation} |
1129 |
|
1130 |
Note that this result coincides with |
1131 |
Example \ref{ex:ccfr0:scrn0:01}. |
1132 |
\end{vworkexampleparsection} |
1133 |
\vworkexamplefooter{} |
1134 |
|
1135 |
We've shown in Algorithm \ref{alg:ccfr0:scrn0:akgenalg} |
1136 |
that any rational number can be expressed as a continued fraction, and |
1137 |
with Theorem \ref{thm:ccfr0:scnv0:canonicalconvergentconstruction} |
1138 |
that any finite continued fraction can be converted to a rational |
1139 |
number. Although we don't say more until Section \ref{ccfr0:scin0}, |
1140 |
it follows directly that any irrational number results in |
1141 |
an \emph{infinite} (or non-terminating) continued fraction, and that |
1142 |
any infinite continued fraction represents an irrational number. |
1143 |
In the theorems that follow, we don't treat infinite continued |
1144 |
fractions with mathematical rigor, because our emphasis is on |
1145 |
specific applications of continued fractions. |
1146 |
|
1147 |
\begin{vworktheoremstatement} |
1148 |
\label{thm:ccfr0:scnv0:evenslessthanoddsgreaterthan} |
1149 |
For a finite continued fraction representation of |
1150 |
the [rational] number $\alpha$, every even-ordered convergent |
1151 |
is less than $\alpha$ and every odd-ordered convergent is |
1152 |
greater than $\alpha$, with the exception of the final convergent |
1153 |
$s_n$, which is equal to $\alpha$. |
1154 |
For an infinite continued fraction corresponding to the |
1155 |
[irrational] real |
1156 |
number $\alpha$, every even-ordered convergent is less than |
1157 |
$\alpha$, and every odd-ordered convergent is greater than |
1158 |
$\alpha$. |
1159 |
\end{vworktheoremstatement} |
1160 |
\begin{vworktheoremparsection}{Proof (Informal)} |
1161 |
In the case of a finite continued fraction, the proof is obvious |
1162 |
and immediate. Since $s_n$, the final convergent, is equal |
1163 |
to the rational number $\alpha$, Theorems \ref{thm:ccfr0:scnv0:crossproductminusone} |
1164 |
and \ref{thm:ccfr0:scnv0:crossproductminusonebacktwo} demonstrate this |
1165 |
unequivocally. |
1166 |
|
1167 |
In the case of an infinite continued fraction, |
1168 |
note the form of the proof of Theorem |
1169 |
\ref{thm:ccfr0:scnv0:canonicalconvergentconstruction}, |
1170 |
where the substitution of $a_k := a_k + 1/a_{k+1}$ |
1171 |
is made. It can be demonstrated that for any even-ordered |
1172 |
convergent $s_k$, additional partial quotients (except |
1173 |
$a_{k+1} = a_n = 1$, which isn't allowed in general or even |
1174 |
possible with an infinite continued fraction) can only |
1175 |
increase the value. It can similarly be demonstrated that |
1176 |
additional partial quotients can only decrease the value |
1177 |
of an odd-ordered convergent. Because the continued fraction |
1178 |
is infinite, any particular even-ordered convergent will be |
1179 |
increased if more partial quotients are allowed, and any particular |
1180 |
odd-ordered convergent will be decreased in value if more |
1181 |
partial quotients are allowed. Thus, we can conclude that |
1182 |
all even-ordered convergents are less than the value of |
1183 |
$\alpha$, and all odd-ordered convergents are greater |
1184 |
than the value of $\alpha$.\footnote{To make this proof more |
1185 |
formal would require the discussion of \emph{remainders}, |
1186 |
which wouldn't contribute to the applications discussed in this |
1187 |
work.} |
1188 |
\end{vworktheoremparsection} |
1189 |
%\vworktheoremfooter{} |
1190 |
|
1191 |
\begin{vworktheoremstatement} |
1192 |
\label{thm:ccfr0:scnv0:minimumrateofconvergentdenominatorincrease} |
1193 |
For $k \geq 2$, |
1194 |
|
1195 |
\begin{equation} |
1196 |
q_k \geq 2^{\frac{k-1}{2}} . |
1197 |
\end{equation} |
1198 |
\end{vworktheoremstatement} |
1199 |
\begin{vworktheoremproof}\hspace{-0.4em}\footnote{From |
1200 |
\cite{bibref:b:KhinchinClassic}, Theorem 12, p. 13.} |
1201 |
For $k \geq 2$, |
1202 |
|
1203 |
\begin{equation} |
1204 |
q_k = a_k q_{k-1} + q_{k-2} \geq q_{k-1} + q_{k-2} \geq 2 q_{k-2} . |
1205 |
\end{equation} |
1206 |
|
1207 |
Successive application of this inequality yields |
1208 |
|
1209 |
\begin{equation} |
1210 |
q_{2k} \geq 2^k q_0 = 2^k, \; q_{2k+1} \geq 2^k q_1 \geq 2^k , |
1211 |
\end{equation} |
1212 |
|
1213 |
which proves the theorem. Thus, the denominators of convergents |
1214 |
increase at least as rapidly as the terms of a geometric |
1215 |
progression. |
1216 |
\end{vworktheoremproof} |
1217 |
\begin{vworktheoremparsection}{Remarks} |
1218 |
(1) This minimum geometric rate of increase of denominators of convergents is how |
1219 |
we make the claim that Algorithms |
1220 |
\ref{alg:ccfr0:scba0:cfenclosingneighborsfn} and |
1221 |
\ref{alg:ccfr0:scba0:cffareyneighborfn} are $O(log \; N)$ and |
1222 |
that Algorithms |
1223 |
\ref{alg:ccfr0:scba0:cfenclosingneighborsfab} |
1224 |
and \ref{alg:ccfr0:scba0:cffareyneighborfab} are |
1225 |
$O(log \; max(h_{MAX}, k_{MAX}))$. |
1226 |
(2) This theorem supplies the \emph{minimum} rate of increase, |
1227 |
but the demonominators of convergents can increase much faster. To achieve |
1228 |
the minimum rate of increase, every $a_k$ must be 1, which occurs |
1229 |
only with the continued fraction representation of |
1230 |
$\sqrt{5}/2 + 1/2$ (the famous \index{golden ratio}golden ratio). |
1231 |
(See also Exercise \ref{exe:cfr0:sexe0:c01}.) |
1232 |
\end{vworktheoremparsection} |
1233 |
\vworktheoremfooter{} |
1234 |
|
1235 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1236 |
|
1237 |
Since Theorem \ref{thm:ccfr0:scnv0:canonicalconvergentconstruction} |
1238 |
provides a concrete |
1239 |
procedure for going from a continued fraction $[a_0; a_1, \ldots{} , a_n]$ |
1240 |
to a rational number $a/b$ that, when Algorithm \ref{alg:ccfr0:scrn0:akgenalg} |
1241 |
is applied, will again result in $[a_0; a_1, \ldots{} , a_n]$, we have |
1242 |
successfully demonstrated that every continued fraction |
1243 |
$[a_0; a_1, \ldots{} , a_n]$ corresponds to [at least one] |
1244 |
rational number $a/b$. |
1245 |
|
1246 |
The next natural questions to ask are questions of representation |
1247 |
uniqueness and the nature of the mapping between the set of rational numbers |
1248 |
and the set of continued fractions. For example, will 32/100 and 64/200 have |
1249 |
the same continued fraction representation $[a_0; a_1, \ldots{} , a_n]$? |
1250 |
Do two different continued fractions ever correspond |
1251 |
to the same rational number? We answer these questions now. |
1252 |
|
1253 |
Algorithm \ref{alg:ccfr0:scrn0:akgenalg} will produce the |
1254 |
same $[a_0; a_1, \ldots{} , a_n]$ for any $ia/ib$, i.e. all rational numbers |
1255 |
which are equivalent in value will generate the same continued fraction |
1256 |
representation (see Lemma \ref{lem:ccfr0:scrn0:aoverbneednotbeirreducible}). |
1257 |
|
1258 |
It was hinted in the introduction (Section |
1259 |
\ref{ccfr0:sint0}, Footnote \ref{footnote:ccfr0:sint0:00}) |
1260 |
that, except in the case of representing an integer, it is |
1261 |
not allowed for the final partial quotient $a_n$ to be 1. |
1262 |
We now explain the reasons why this must be disallowed. First, |
1263 |
if $a_n = 1$, then $a_{n-1}$ can be increased by 1 and |
1264 |
the continued fraction can be reduced in order |
1265 |
by 1 and while still preserving its value. For example, it |
1266 |
can easily be verified that $[1;2,3,3,1]$ and $[1;2,3,4]$ |
1267 |
represent the same number. However, this observation alone |
1268 |
is not enough to recommend a canonical form---this observation |
1269 |
does not suggest that $[1;2,3,4]$ should be preferred |
1270 |
over $[1;2,3,3,1]$. However, what \emph{can} be noted is that |
1271 |
that a continued fraction representation with $a_n=1$, $n>0$ |
1272 |
cannot be attained using Algorithm \ref{alg:ccfr0:scrn0:akgenalg} or |
1273 |
(\ref{eq:ccfr0:scrn0:00a}) through (\ref{eq:ccfr0:scrn0:00e}), |
1274 |
because a form with $a_n=1$, $n>0$ violates the assumption that |
1275 |
successive remainders are ever-decreasing (see Eq. |
1276 |
\ref{eq:lem:ccfr0:scrn0:alwaysterminates}). The property that |
1277 |
remainders are ever-decreasing is a necessary condition in |
1278 |
proofs of some important properties, and so requiring |
1279 |
that $a_n \neq{} 1$, $n>0$ |
1280 |
is the most natural convention for a canonical form. |
1281 |
|
1282 |
\begin{vworklemmastatement} |
1283 |
\label{lem:ccfr0:scrn0:aoverbneednotbeirreducible} |
1284 |
Algorithm \ref{alg:ccfr0:scrn0:akgenalg} will |
1285 |
produce the same result |
1286 |
$[a_0; a_1, \ldots{} , a_n]$ for any |
1287 |
$ia/ib$, i.e. $a/b$ need not be reduced before the algorithm |
1288 |
is applied. |
1289 |
\end{vworklemmastatement} |
1290 |
\begin{vworklemmaproof} |
1291 |
Assume that $a/b$ is irreducible, and that $ia/ib$, |
1292 |
$i \in \{ 2, 3, \ldots \}$ is used as input to |
1293 |
the algorithm. By definition, any rational number |
1294 |
with the same value as $a/b$ is of the form $ia/ib$, |
1295 |
$i \in \vworkintsetpos$. |
1296 |
Note that (\ref{eq:ccfr0:scrn0:00a}) through |
1297 |
(\ref{eq:ccfr0:scrn0:00e}) ``scale up'', while still producing |
1298 |
the same partial quotients $[a_0; a_1, \ldots{} , a_n]$. |
1299 |
Specifically: |
1300 |
|
1301 |
\begin{equation} |
1302 |
\label{eq:ccfr0:scrn0:10a} |
1303 |
\frac{ia}{ib} |
1304 |
= |
1305 |
a_0 + \frac{ir_0}{ib} |
1306 |
= |
1307 |
a_0 + \frac{1}{\frac{ib}{ir_0}} |
1308 |
\end{equation} |
1309 |
|
1310 |
\begin{equation} |
1311 |
\label{eq:ccfr0:scrn0:10b} |
1312 |
\frac{ib}{ir_0} |
1313 |
= |
1314 |
a_1 + \frac{ir_1}{ir_0} |
1315 |
\end{equation} |
1316 |
|
1317 |
\begin{equation} |
1318 |
\label{eq:ccfr0:scrn0:10c} |
1319 |
\frac{ir_0}{ir_1} |
1320 |
= |
1321 |
a_2 + \frac{ir_2}{ir_1} |
1322 |
\end{equation} |
1323 |
|
1324 |
\noindent{}Finally, nearing the termination of |
1325 |
Algorithm \ref{alg:ccfr0:scrn0:akgenalg}: |
1326 |
|
1327 |
\begin{equation} |
1328 |
\label{eq:ccfr0:scrn0:10d} |
1329 |
\frac{ir_{n-3}}{ir_{n-2}} |
1330 |
= |
1331 |
a_{n-1} + \frac{ir_{n-1}}{ir_{n-2}} |
1332 |
\end{equation} |
1333 |
|
1334 |
\begin{equation} |
1335 |
\label{eq:ccfr0:scrn0:10e} |
1336 |
\frac{ir_{n-2}}{ir_{n-1}} |
1337 |
= |
1338 |
a_n |
1339 |
\end{equation} |
1340 |
|
1341 |
Thus, it is easy to show that Algorithm \ref{alg:ccfr0:scrn0:akgenalg} |
1342 |
will produce the same continued fraction representation regardless of whether |
1343 |
the input to the algorithm is reduced. It is also easy to show that the |
1344 |
last non-zero remainder as the algorithm is applied ($r_{n-1}$, in |
1345 |
Eqns. \ref{eq:ccfr0:scrn0:10d} and \ref{eq:ccfr0:scrn0:10e}) |
1346 |
is the greatest common divisor of $ia$ and $ib$ (this is done |
1347 |
in the proof of Algorithm \ref{alg:ccfr0:sega0:euclidsgcdalgorithm}). |
1348 |
\end{vworklemmaproof} |
1349 |
%\vworklemmafooter{} |
1350 |
|
1351 |
\begin{vworklemmastatement} |
1352 |
\label{lem:ccfr0:scrn0:cfrepresentationisunique} |
1353 |
So long as $a_n \neq 1$, $n>0$, a rational number $a/b$ has only |
1354 |
one [unique] continued fraction representation |
1355 |
$[a_0; a_1, \ldots{} , a_n]$. |
1356 |
\end{vworklemmastatement} |
1357 |
\begin{vworklemmaproof} |
1358 |
Assume that two different continued fractions, |
1359 |
$[a_0; a_1, \ldots{} , a_m]$ and |
1360 |
$[\overline{a_0}; \overline{a_1}, \ldots{} , \overline{a_n}]$, |
1361 |
correspond to the same rational number $a/b$. By |
1362 |
\emph{different}, we mean either that $m=n$ but |
1363 |
$\exists i, a_i \neq \overline{a_i}$, or that $m \neq n$. |
1364 |
|
1365 |
Note that Theorem \ref{thm:ccfr0:scnv0:canonicalconvergentconstruction} |
1366 |
will map from any continued fraction to an irreducible rational |
1367 |
number $a/b$. Assume we apply |
1368 |
Theorem \ref{thm:ccfr0:scnv0:canonicalconvergentconstruction} to |
1369 |
$[a_0; a_1, \ldots{} , a_m]$ to produce $a/b$, and |
1370 |
to $[\overline{a_0}; \overline{a_1}, \ldots{} , \overline{a_n}]$ |
1371 |
to produce $\overline{a}/\overline{b}$. Because two irreducible |
1372 |
rational numbers are equal iff their components are |
1373 |
equal, |
1374 |
$[(a/b) = (\overline{a}/\overline{b})] \vworkhimp{} % |
1375 |
[(a = \overline{a}) \wedge (b = \overline{b})]$. Because |
1376 |
$a/b = \overline{a}/\overline{b}$, we denote both of these |
1377 |
numbers simply as $a/b$. |
1378 |
|
1379 |
By (\ref{eq:ccfr0:scrn0:11a}), |
1380 |
$a = a_0 b + r_0 = \overline{a_0} b + \overline{r_0}$, |
1381 |
$0 < r_0, \overline{r_0} < b$. Because |
1382 |
$r_0, \overline{r_0} < b$, there is only one combination |
1383 |
of $a_0$ and $r_0$ or of $\overline{a_0}$ and |
1384 |
$\overline{r_0}$ that can result in $a$. Thus, we can conclude |
1385 |
that $a_0 = \overline{a_0}$ and |
1386 |
$r_0 = \overline{r_0}$. This type of reasoning, can be |
1387 |
carried ``downward'' inductively, each time fixing |
1388 |
$a_{i}$ and $r_{i}$. Finally, we must conclude |
1389 |
that $(a/b = \overline{a}/\overline{b}) \vworkhimp % |
1390 |
[a_0; a_1, \ldots{} , a_m] = % |
1391 |
[\overline{a_0}; \overline{a_1}, \ldots{} , \overline{a_n}]$ |
1392 |
and that $m=n$. |
1393 |
\end{vworklemmaproof} |
1394 |
\begin{vworklemmaparsection}{Remarks} |
1395 |
The case of $a_n=1$, $n>0$ deserves further discussion. |
1396 |
Theorem \ref{thm:ccfr0:scnv0:canonicalconvergentconstruction} will produce |
1397 |
an irreducible rational number even if |
1398 |
$a_n = 1$, $n>0$. How is it that uniqueness of representation can |
1399 |
be claimed when clearly, for example, $[2;3,4,2]$ and $[2;3,4,1,1]$ |
1400 |
are the same number? The answer is that $a_n = 1$, $n>0$ requires |
1401 |
that $r_{n-2}=r_{n-1}=1$, which violates the ``uniqueness'' assumption |
1402 |
used in fixing $a_i$ and $r_i$ in the proof above---specifically note |
1403 |
that the condition $0<r_{n-1}<r_{n-2}$ in (\ref{eq:ccfr0:scrn0:11d}) |
1404 |
is violated. If one is allowed to violate the required |
1405 |
ever-decreasing remainders, then $a_i$ and $r_i$ cannot |
1406 |
be uniquely fixed at each step of the proof, above. |
1407 |
\end{vworklemmaparsection} |
1408 |
\vworklemmafooter{} |
1409 |
|
1410 |
\index{continued fraction!intermediate fraction} |
1411 |
An \emph{intermediate fraction} is a fraction represented |
1412 |
by the continued fraction representation of a $k$-th order |
1413 |
convergent with the final partial quotient $a_k$ reduced |
1414 |
(this can naturally only be done when $a_k > 1$). As Khinchin |
1415 |
points out (\cite{bibref:b:KhinchinClassic}, p. 14): |
1416 |
``\emph{In arithmetic applications, these intermediate |
1417 |
fractions play an important role (though not as important |
1418 |
a role as the convergents)}''. |
1419 |
|
1420 |
The intermediate fractions (of a $k$-th order convergent) |
1421 |
form a monotonically increasing or decreasing sequence of |
1422 |
fractions (\cite{bibref:b:KhinchinClassic}, p. 13): |
1423 |
|
1424 |
\begin{equation} |
1425 |
\label{eq:ccfr0:scrn0:intermediatefrac01} |
1426 |
\frac{p_{k-2}}{q_{k-2}}, |
1427 |
\frac{p_{k-2} + p_{k-1}}{q_{k-2} + q_{k-1}}, |
1428 |
\frac{p_{k-2} + 2 p_{k-1}}{q_{k-2} + 2 q_{k-1}}, |
1429 |
\ldots{} , |
1430 |
\frac{p_{k-2} + a_k p_{k-1}}{q_{k-2} + a_k q_{k-1}} |
1431 |
= |
1432 |
\frac{p_k}{q_k} . |
1433 |
\end{equation} |
1434 |
|
1435 |
Note in (\ref{eq:ccfr0:scrn0:intermediatefrac01}) that the |
1436 |
first and last fractions are not intermediate fractions (rather, they are |
1437 |
convergents). |
1438 |
|
1439 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1440 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1441 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1442 |
\section{Euclid's GCD Algorithm} |
1443 |
%Section tag: EGA0 |
1444 |
\index{Euclid!GCD algorithm} |
1445 |
|
1446 |
The apparatus of continued fractions is closely related to Euclid's GCD |
1447 |
algorithm (in fact, historically, Euclid's GCD algorithm is considered |
1448 |
a precursor of continued fractions). It was noted in |
1449 |
Lemma \ref{lem:ccfr0:scrn0:aoverbneednotbeirreducible} that the last non-zero |
1450 |
remainder when Algorithm \ref{alg:ccfr0:scrn0:akgenalg} is applied |
1451 |
is the greatest common divisor of $a$ and $b$. In this section, we |
1452 |
present Euclid's algorithm, prove it, and show it similarity to |
1453 |
Algorithm \ref{alg:ccfr0:scrn0:akgenalg}. |
1454 |
|
1455 |
Knuth (\cite{bibref:b:knuthclassic2ndedvol2}, p. 335) presents some background |
1456 |
information about Euclid's GCD algorithm: |
1457 |
|
1458 |
\begin{quote} |
1459 |
Euclid's algorithm is found in Book 7, Propositions 1 and 2 of his |
1460 |
\emph{Elements} (c. 300 B.C.), but it probably wasn't his own |
1461 |
invention. Some scholars believe that the method was known up to |
1462 |
200 years earlier, at least in its subtractive form, and it |
1463 |
was almost certainly known to Eudoxus (c. 375 B.C.); see |
1464 |
K. von Fritz, \emph{Ann. Math.} (2) \textbf{46} 1945, 242-264. |
1465 |
Aristotle (c. 330 B.C.) hinted at it in his \emph{Topics}, 158b, |
1466 |
29-35. However, very little hard evidence about such early history |
1467 |
has survived [see. W. R. Knorr, \emph{The Evolution of the Euclidian |
1468 |
Elements} (Dordrecht: 1975)]. |
1469 |
|
1470 |
We might call Euclid's method the granddaddy of all algorithms, because |
1471 |
it is the oldest nontrivial algorithm that has survived to the present day. |
1472 |
(The chief rival for this honor is perhaps the ancient Egyptian method |
1473 |
for multiplication, which was based on doubling and adding, and which forms |
1474 |
the basis for efficient calculation of \emph{n}th powers as explained |
1475 |
in section 4.6.3. \ldots{}) |
1476 |
\end{quote} |
1477 |
|
1478 |
\begin{vworkalgorithmstatementpar} |
1479 |
{Euclid's GCD Algorithm For Greatest Common Divisor Of Positive |
1480 |
Integers \mbox{\boldmath $a$} |
1481 |
And \mbox{\boldmath $b$}}\hspace{-0.4em}\footnote{Knuth |
1482 |
(\cite{bibref:b:knuthclassic2ndedvol2}, pp. 336-337) distinguishes between the \emph{original} |
1483 |
Euclidian algorithm and the \emph{modern} Euclidian algorithm. The algorithm presented here |
1484 |
is more closely patterned after the \emph{modern} Euclidian algorithm.} |
1485 |
\label{alg:ccfr0:sega0:euclidsgcdalgorithm} |
1486 |
\begin{alglvl0} |
1487 |
\item If ($a < b$), swap $a$ and $b$.\footnote{This step isn't strictly necessary, but is usually done |
1488 |
to save one iteration.} |
1489 |
\item Repeat |
1490 |
\begin{alglvl1} |
1491 |
\item $r := a \; mod \; b$. |
1492 |
\item If ($r = 0$), STOP. |
1493 |
\item $a := b$. |
1494 |
\item $b := r$. |
1495 |
\end{alglvl1} |
1496 |
\item \textbf{Exit condition:} $b$ will be the g.c.d. of $a$ and $b$. |
1497 |
\end{alglvl0} |
1498 |
\end{vworkalgorithmstatementpar} |
1499 |
\begin{vworkalgorithmproof} |
1500 |
Olds (\cite{bibref:b:OldsClassic}, pp. 16-17) shows the |
1501 |
relationship between Algorithm |
1502 |
\ref{alg:ccfr0:scrn0:akgenalg} and Euclid's algorithm, and presents |
1503 |
a proof, which is reproduced nearly verbatim here. |
1504 |
|
1505 |
First, note that $d$ is the GCD of $a$ and $b$ iff: |
1506 |
|
1507 |
\begin{itemize} |
1508 |
\item (Necessary Condition I) $d$ divides both $a$ and $b$, and |
1509 |
\item (Necessary Condition II) any common divisor $c$ of $a$ and $b$ divides $d$. |
1510 |
\end{itemize} |
1511 |
|
1512 |
Essentially, we will prove that the final non-zero remainder |
1513 |
when the algorithm is applied meets the two criteria above, |
1514 |
and hence must be the GCD of $a$ and $b$. |
1515 |
|
1516 |
Note that (\ref{eq:ccfr0:scrn0:00a}) through |
1517 |
(\ref{eq:ccfr0:scrn0:00e}) can be rewritten as |
1518 |
(\ref{eq:ccfr0:scrn0:11a}) through |
1519 |
(\ref{eq:ccfr0:scrn0:11e}), which make them |
1520 |
consistent with the form Olds' presents. |
1521 |
|
1522 |
\begin{eqnarray} |
1523 |
\label{eq:ccfr0:scrn0:11a} |
1524 |
a = a_0 b + r_0, && 0 < r_0 < b \\ |
1525 |
\label{eq:ccfr0:scrn0:11b} |
1526 |
b = a_1 r_0 + r_1, && 0 < r_1 < r_0 \\ |
1527 |
\label{eq:ccfr0:scrn0:11c} |
1528 |
r_0 = a_2 r_1 + r_2, && 0 < r_2 < r_1 \\ |
1529 |
\ldots{}\hspace{-1.67em}&& \nonumber \\ |
1530 |
\label{eq:ccfr0:scrn0:11d} |
1531 |
r_{n-3} = a_{n-1} r_{n-2} + r_{n-1}, && 0 < r_{n-1} < r_{n-2} \\ |
1532 |
\label{eq:ccfr0:scrn0:11e} |
1533 |
r_{n-2} = a_n r_{n-1} + 0, && 0 = r_n |
1534 |
\end{eqnarray} |
1535 |
|
1536 |
First, we will show that \emph{Necessary Condition I}, above, is met. |
1537 |
Note from (\ref{eq:ccfr0:scrn0:11e}) that $r_{n-1} \vworkdivides r_{n-2}$, |
1538 |
since $r_{n-2}$ is an integer multiple of $r_{n-1}$. Note from |
1539 |
(\ref{eq:ccfr0:scrn0:11d}) that $r_{n-1} \vworkdivides r_{n-3}$, since |
1540 |
$r_{n-3}$ is also an integer multiple of $r_{n-1}$. This logic can |
1541 |
be carried ``upward'' in the set of equations represented |
1542 |
by (\ref{eq:ccfr0:scrn0:11a}) through (\ref{eq:ccfr0:scrn0:11e}), |
1543 |
and we can finally conclude that $r_{n-1} \vworkdivides b$ and |
1544 |
$r_{n-1} \vworkdivides a$. This proves \emph{Necessary Condition I}. |
1545 |
|
1546 |
Second, we will show that \emph{Necessary Condition II}, above, is met. |
1547 |
This time, in (\ref{eq:ccfr0:scrn0:11a}) through (\ref{eq:ccfr0:scrn0:11e}), |
1548 |
we work top-down rather than bottom-up. Assume that $c$ is a divisor |
1549 |
of $a$ and a divisor of $b$. Then, from the form of (\ref{eq:ccfr0:scrn0:11a}), |
1550 |
$c$ divides $r_0$.\footnote{This implication may be counterintuitive |
1551 |
at first glance. It concerns "reachability" of linear combinations |
1552 |
of integers with a common divisor. Specifically, if |
1553 |
$a$ and $b$ have a common divisor $c$, any linear combination |
1554 |
$ia + jb$, ($i,j \in \vworkintset$), can ``reach'' only multiples of $c$. |
1555 |
In (\ref{eq:ccfr0:scrn0:11a}), $(1)(a)+(-a_0)(b)=r_0$, thus |
1556 |
$r_0$ must be a multiple of $c$. An identical argument applies for |
1557 |
(\ref{eq:ccfr0:scrn0:11a}) through (\ref{eq:ccfr0:scrn0:11e}).} |
1558 |
Similarly, from the form of (\ref{eq:ccfr0:scrn0:11b}), |
1559 |
$c$ divides $r_1$. This rationale can be carried ``downward'' to finally |
1560 |
conclude that $c$ divides $r_{n-1}$. Thus, |
1561 |
$(c \vworkdivides a) \wedge (c \vworkdivides b) \vworkhimp (c \vworkdivides r_{n-1})$, |
1562 |
where $r_{n-1}$ is the last non-zero remainder. This proves |
1563 |
\emph{Necessary Condition II}. |
1564 |
|
1565 |
Thus, $r_{n-1}$ is the GCD of $a$ and $b$. |
1566 |
\end{vworkalgorithmproof} |
1567 |
\begin{vworkalgorithmparsection}{Remarks} |
1568 |
It is easy to observe that the only difference between |
1569 |
Algorithm \ref{alg:ccfr0:scrn0:akgenalg} and |
1570 |
Algorithm \ref{alg:ccfr0:sega0:euclidsgcdalgorithm} is |
1571 |
that Algorithm \ref{alg:ccfr0:scrn0:akgenalg} records the |
1572 |
quotient of each division, whereas |
1573 |
Algorithm \ref{alg:ccfr0:sega0:euclidsgcdalgorithm} |
1574 |
does not. |
1575 |
\end{vworkalgorithmparsection} |
1576 |
%\vworkalgorithmfooter{} |
1577 |
|
1578 |
\begin{vworkexamplestatement} |
1579 |
\label{ex:ccfr0:sega0:01} |
1580 |
Use Euclid's algorithm to find the greatest common divisor |
1581 |
of 1,736,651 and 26,023. |
1582 |
\end{vworkexamplestatement} |
1583 |
\begin{vworkexampleparsection}{Solution} |
1584 |
\begin{table} |
1585 |
\caption{Euclid's Algorithm Applied To Find Greatest Common Divisor Of 1,736,651 and 26,023 |
1586 |
(Example \ref{ex:ccfr0:sega0:01})} |
1587 |
\label{tbl:ex:ccfr0:sega0:01} |
1588 |
\begin{center} |
1589 |
\begin{tabular}{|c|c|c|c|} |
1590 |
\hline |
1591 |
\small{Iteration} & \small{$a$} & \small{$b$} & \small{$r : = a \; mod \; b$} \\ |
1592 |
\hline |
1593 |
\hline |
1594 |
\small{1} & \small{1,736,651} & \small{26,023} & \small{19,133} \\ |
1595 |
\hline |
1596 |
\small{2} & \small{26,023} & \small{19,133} & \small{6,890} \\ |
1597 |
\hline |
1598 |
\small{3} & \small{19,133} & \small{6,890} & \small{5,353} \\ |
1599 |
\hline |
1600 |
\small{4} & \small{6,890} & \small{5,353} & \small{1,537} \\ |
1601 |
\hline |
1602 |
\small{5} & \small{5,353} & \small{1,537} & \small{742} \\ |
1603 |
\hline |
1604 |
\small{6} & \small{1,537} & \small{742} & \small{53} \\ |
1605 |
\hline |
1606 |
\small{7} & \small{742} & \small{53} & \small{0} \\ |
1607 |
\hline |
1608 |
\end{tabular} |
1609 |
\end{center} |
1610 |
\end{table} |
1611 |
Table \ref{tbl:ex:ccfr0:sega0:01} shows the application of |
1612 |
Algorithm \ref{alg:ccfr0:sega0:euclidsgcdalgorithm} (Euclid's |
1613 |
GCD algorithm) to find the greatest common divisor |
1614 |
of 1,736,651 and 26,023. The last non-zero remainder (and hence |
1615 |
the greatest common divisor) is 53. |
1616 |
\end{vworkexampleparsection} |
1617 |
\begin{vworkexampleparsection}{Remarks} |
1618 |
The prime factorization of 1,736,651 is $151 \times 53 \times 31 \times 7$, and |
1619 |
the prime factorization of 26,023 is $491 \times 53$, which is consistent |
1620 |
with the result in Table \ref{tbl:ex:ccfr0:sega0:01}. |
1621 |
\end{vworkexampleparsection} |
1622 |
\vworkexamplefooter{} |
1623 |
|
1624 |
|
1625 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1626 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1627 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1628 |
\section[CF Representation Of Irrationals] |
1629 |
{Continued Fraction Representation Of Irrational Numbers} |
1630 |
%Section tag: CIN0 |
1631 |
\label{ccfr0:scin0} |
1632 |
|
1633 |
\index{continued fraction!irrational numbers@of irrational numbers} |
1634 |
\index{irrational number!continued fraction representation of}Irrational |
1635 |
numbers (such as $\sqrt{2}$ or $\pi$) necessarily have infinite continued |
1636 |
fraction representations (i.e. the representations do not terminate). This is clear, since |
1637 |
Theorem \ref{thm:ccfr0:scnv0:canonicalconvergentconstruction} gives a concrete procedure |
1638 |
for constructing a rational number from any \emph{finite} continued fraction; |
1639 |
therefore a continued fraction corresponding to an irrational number |
1640 |
cannot be finite. |
1641 |
|
1642 |
The algorithm for determining the partial quotients of an irrational number is |
1643 |
awkward, because it is a symbolic (rather than a numerical) algorithm. |
1644 |
We present the algorithm here for perspective and completeness, although it |
1645 |
is not often useful in practical engineering work. In practical work, an |
1646 |
ordinary handheld calculator will supply a real number to far more precision |
1647 |
than necessary, and the displayed real number can be converted to a rational |
1648 |
number for the application of Algorithm \ref{alg:ccfr0:scrn0:akgenalg}. |
1649 |
For practical work, it is rarely necessary to apply a Algorithm |
1650 |
\ref{alg:ccfr0:scin0:symboliccfalgorithm}. |
1651 |
|
1652 |
The symbolic algorithm for determining the continued fraction partial quotients |
1653 |
of a real number is a recursive process very similar to the algorithm for |
1654 |
determining the continued fraction partial quotients of a rational number. |
1655 |
The essential activity is choosing the largest possible integer $a_i$ in each |
1656 |
iteration. |
1657 |
|
1658 |
Algorithm \ref{alg:ccfr0:scin0:symboliccfalgorithm} begins by choosing |
1659 |
the largest integer $a_0$ not larger than $x$, then expressing $x$ as |
1660 |
|
1661 |
\begin{equation} |
1662 |
x = a_0 + \frac{1}{x_1} . |
1663 |
\end{equation} |
1664 |
|
1665 |
\noindent{}With $a_0$ chosen, $x_1$ can then be expressed as |
1666 |
|
1667 |
\begin{equation} |
1668 |
x_1 = \frac{1}{x - a_0} . |
1669 |
\end{equation} |
1670 |
|
1671 |
\noindent{}$x_1$ can then be expressed as |
1672 |
|
1673 |
\begin{equation} |
1674 |
x_1 = a_1 + \frac{1}{x_2} , |
1675 |
\end{equation} |
1676 |
|
1677 |
\noindent{}and $a_1$, the largest integer not larger than $x_1$, |
1678 |
can be chosen. |
1679 |
This process can be continued indefinitely (with an irrational $x$, it won't terminate) |
1680 |
to determine as many partial quotients as desired. |
1681 |
|
1682 |
\begin{vworkalgorithmstatementpar} |
1683 |
{Symbolic Algorithm For Obtaining |
1684 |
Continued Fraction Representation Of An Irrational Number |
1685 |
\mbox{\boldmath $x$}} |
1686 |
\label{alg:ccfr0:scin0:symboliccfalgorithm} |
1687 |
\begin{alglvl0} |
1688 |
\item $x_0 := x$ (the real number whose partial quotients are desired). |
1689 |
\item $k := -1$. |
1690 |
\item Repeat |
1691 |
\begin{alglvl1} |
1692 |
\item $k := k + 1$. |
1693 |
\item $a_k := \lfloor x_k \rfloor$. |
1694 |
\item $x_{k+1} := \displaystyle{\frac{1}{x_k - a_k}}$. |
1695 |
\end{alglvl1} |
1696 |
\item Until (as many partial quotients as desired are obtained). |
1697 |
\end{alglvl0} |
1698 |
\end{vworkalgorithmstatementpar} |
1699 |
%\vworkalgorithmfooter{} |
1700 |
|
1701 |
\begin{vworkexamplestatement} |
1702 |
\label{ex:ccfr0:scin0:symboliccfalgorithmexample} |
1703 |
Find the first several continued fraction partial quotients of $\sqrt{3}$. |
1704 |
\end{vworkexamplestatement} |
1705 |
\begin{vworkexampleparsection}{Solution} |
1706 |
Applying Algorithm \ref{alg:ccfr0:scin0:symboliccfalgorithm}: |
1707 |
|
1708 |
\begin{equation} |
1709 |
x_0 := x = \sqrt{3} |
1710 |
\end{equation} |
1711 |
|
1712 |
\begin{equation} |
1713 |
k := -1 |
1714 |
\end{equation} |
1715 |
|
1716 |
\begin{equation} |
1717 |
k := k+1 = 0 |
1718 |
\end{equation} |
1719 |
|
1720 |
\begin{equation} |
1721 |
a_0 := \lfloor x_0 \rfloor = \lfloor \sqrt{3} \rfloor = 1 |
1722 |
\end{equation} |
1723 |
|
1724 |
\begin{equation} |
1725 |
x_1 := \frac{1}{x_0 - a_0} |
1726 |
= \frac{1}{\sqrt{3}-1} |
1727 |
= \frac{\sqrt{3}+1}{2} |
1728 |
\end{equation} |
1729 |
|
1730 |
\begin{equation} |
1731 |
k := k + 1 = 1 |
1732 |
\end{equation} |
1733 |
|
1734 |
\begin{equation} |
1735 |
a_1 := \lfloor x_1 \rfloor = |
1736 |
\left\lfloor {\frac{\sqrt{3}+1}{2}} \right\rfloor = 1 |
1737 |
\end{equation} |
1738 |
|
1739 |
\begin{equation} |
1740 |
x_2 := \frac{1}{x_1 - 1} |
1741 |
= \frac{1}{\frac{\sqrt{3}+1}{2}-1} |
1742 |
= \sqrt{3}+1 |
1743 |
\end{equation} |
1744 |
|
1745 |
\begin{equation} |
1746 |
k := k + 1 = 2 |
1747 |
\end{equation} |
1748 |
|
1749 |
\begin{equation} |
1750 |
a_2 := \lfloor x_2 \rfloor = \lfloor \sqrt{3}+1 \rfloor = 2 |
1751 |
\end{equation} |
1752 |
|
1753 |
\begin{equation} |
1754 |
x_3 := \frac{1}{(\sqrt{3}+1)-2} = \frac{\sqrt{3}+1}{2} |
1755 |
\end{equation} |
1756 |
|
1757 |
Note that $x_3 = x_1$, so the algorithm will repeat with |
1758 |
$a_3=1$, $a_4=2$, $a_5=1$, $a_6=2$, etc. Thus, the continued |
1759 |
fraction representation of $\sqrt{3}$ is |
1760 |
$[1;1,2,1,2,1,2, \ldots{}]$ = $[1;\overline{1,2}]$. |
1761 |
\end{vworkexampleparsection} |
1762 |
\begin{vworkexampleparsection}{Remarks} |
1763 |
\index{continued fraction!repeating} |
1764 |
It can be proved that all continued fractions that repeat or repeat |
1765 |
from some point onward |
1766 |
represent real numbers of the form $\frac{P \pm \sqrt{D}}{Q}$, |
1767 |
where $D \in \vworkintsetpos$ is not the square of an integer. |
1768 |
It can also be shown |
1769 |
that all numbers of this form result in continued fractions that |
1770 |
repeat or repeat from some point onward. (See Olds |
1771 |
\cite{bibref:b:OldsClassic}, Chapter 4.) It is beyond the scope |
1772 |
of our interest in continued fractions to develop these properties. |
1773 |
\end{vworkexampleparsection} |
1774 |
\vworkexamplefooter{} |
1775 |
|
1776 |
|
1777 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1778 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1779 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1780 |
\section{Convergents As Best Approximations} |
1781 |
%Section tag: CBA0 |
1782 |
|
1783 |
Up until this point, we've presented general properties of continued |
1784 |
fractions and convergents without regard for practical applications. |
1785 |
In this section, we present results and algorithms to use the |
1786 |
apparatus of continued fractions to obtain best rational approximations. |
1787 |
|
1788 |
Although we don't dwell on other algorithms for locating best |
1789 |
rational approximations (we present only the single best |
1790 |
algorithm), it is worth noting that there are many naive algorithms |
1791 |
for locating best rational approximations. These include: |
1792 |
|
1793 |
\begin{itemize} |
1794 |
|
1795 |
\item Exhaustive search of the integer lattice |
1796 |
[$O(h_{MAX} k_{MAX})$]. |
1797 |
|
1798 |
\item Building the Farey series starting at an |
1799 |
integer [$O(max(h_{MAX}, k_{MAX})^2)$] |
1800 |
(see Algorithm \cfryzeroxrefhyphen{}\ref{alg:cfry0:sgfs0:02}). |
1801 |
|
1802 |
\item Building the Farey series starting at a rational number with |
1803 |
a large prime denominator [$O(max(h_{MAX}, k_{MAX}))$]. |
1804 |
|
1805 |
\item Building the Stern-Brocot tree (see Section \ref{ccfr0:ssbt0}) |
1806 |
[$O(max(h_{MAX}, k_{MAX}))$]. |
1807 |
|
1808 |
\end{itemize} |
1809 |
|
1810 |
Although we don't justify it formally, |
1811 |
the continued fraction algorithms presented here are |
1812 |
$O(log \; max(h_{MAX}, k_{MAX}))$.\footnote{Well, |
1813 |
not exactly. In the classical computer science |
1814 |
sense (speaking only in terms of number of operations), |
1815 |
the algorithms are $O(log \; max(h_{MAX}, k_{MAX}))$. However, |
1816 |
if $h_{MAX}$ and $k_{MAX}$ are increased beyond the sizes |
1817 |
of integers that a computer can inherently accomodate, one must |
1818 |
use long integer calculation software, which requires more time for |
1819 |
each integer operation than is required for machine native |
1820 |
integer sizes. As $h_{MAX}$ and $k_{MAX}$ are increased far |
1821 |
beyond integer sizes accomodated inherently by the computer, |
1822 |
the relationship surely is not $O(log \; max(h_{MAX}, k_{MAX}))$.} |
1823 |
The basis on which we |
1824 |
make that assertion is the geometric rate of |
1825 |
increase of convergents (see Theorem |
1826 |
\ref{thm:ccfr0:scnv0:minimumrateofconvergentdenominatorincrease}), |
1827 |
which means that the number of steps required is tied to the |
1828 |
logarithm of the maximum denominator involved, as it is |
1829 |
necessary to obtain partial quotients and convergents only until |
1830 |
$q_k \geq max(h_{MAX},k_{MAX})$. |
1831 |
|
1832 |
\begin{vworktheoremstatement} |
1833 |
\label{thm:ccfr0:scba0:convergentcloseness} |
1834 |
In the case of an infinite continued fraction for $k \geq 0$ or in the |
1835 |
case of a finite continued fraction for $0 \leq k < n-1$, a convergent |
1836 |
$s_k = p_k/q_k$ to a [rational or irrational] number |
1837 |
$\alpha \in \vworkrealsetnonneg$ satisfies |
1838 |
|
1839 |
\begin{equation} |
1840 |
\left| {\alpha - \frac{p_k}{q_k}} \right| |
1841 |
< |
1842 |
\frac{1}{q_k q_{k+1}} . |
1843 |
\end{equation} |
1844 |
|
1845 |
In the case of a finite continued fraction with $k = n-1$, |
1846 |
|
1847 |
\begin{equation} |
1848 |
\left| {\alpha - \frac{p_k}{q_k}} \right| |
1849 |
= |
1850 |
\frac{1}{q_k q_{k+1}} . |
1851 |
\end{equation} |
1852 |
\end{vworktheoremstatement} |
1853 |
\begin{vworktheoremproof} |
1854 |
The proof comes directly from Theorem |
1855 |
\ref{thm:ccfr0:scnv0:crossproductminusone} (Corollary I) |
1856 |
and Theorem |
1857 |
\ref{thm:ccfr0:scnv0:evenslessthanoddsgreaterthan}. |
1858 |
\end{vworktheoremproof} |
1859 |
\begin{vworktheoremparsection}{Remarks} |
1860 |
Khinchin describes this result (\cite{bibref:b:KhinchinClassic}, p. 9) |
1861 |
as playing a basic role in the arithmetic |
1862 |
applications of continued fractions. In fact, this theorem is used |
1863 |
in the proof of Theorem |
1864 |
\ref{thm:ccfr0:scba0:cfenclosingneighbors}. |
1865 |
\end{vworktheoremparsection} |
1866 |
\vworktheoremfooter{} |
1867 |
|
1868 |
|
1869 |
We now present and prove the fundamental theorem of this chapter, which gives an |
1870 |
$O(log \; N)$ algorithm for finding the enclosing neighbors in $F_N$ to an arbitrary |
1871 |
rational number $a/b$.\footnote{\label{footnote:ccfr0:scba0:rationalitynotrequired}Theorem |
1872 |
\ref{thm:ccfr0:scba0:cfenclosingneighbors} |
1873 |
applies to irrational numbers as well, |
1874 |
so long as one can obtain enough partial quotients, but we don't highlight this |
1875 |
fact because it is rare in engineering applications that one uses symbolic methods |
1876 |
to obtain best rational approximations. |
1877 |
As emphasized by (\ref{eq:ccfr0:spar0:01}), (\ref{eq:ccfr0:spar0:02}), and |
1878 |
(\ref{eq:ccfr0:spar0:03}), |
1879 |
the process of obtaining partial quotients is essentially a process of determining in which |
1880 |
partition a number lies. All numbers in the same partition---rational or |
1881 |
irrational---have the same Farey neighbors in all Farey series up to a certain order. |
1882 |
If the partial quotients of |
1883 |
an irrational number can be obtained up through $a_k$ s.t. $s_k = p_k/q_k$ is the |
1884 |
highest-order convergent with $q_k \leq N$, then this theorem can be applied. |
1885 |
Knowledge of all $a_0, \ldots{} , a_k$ is equivalent |
1886 |
to the knowledge that the number is in a partition where all numbers in that partition have |
1887 |
the same Farey neighbors in all Farey series up through at least order $q_k$.} |
1888 |
|
1889 |
|
1890 |
\begin{vworktheoremstatementpar}{Enclosing Neighbors Of \mbox{\boldmath $x \notin F_N$} |
1891 |
In \mbox{\boldmath $F_N$}} |
1892 |
\label{thm:ccfr0:scba0:cfenclosingneighbors} |
1893 |
For a non-negative rational |
1894 |
number $a/b$ not in |
1895 |
$F_N$ which has a |
1896 |
continued fraction representation |
1897 |
$[a_0;a_1,a_2,\ldots{} ,a_n]$, the |
1898 |
highest-order convergent $s_k = p_k/q_k$ with $q_k \leq N$ is one |
1899 |
neighbor\footnote{By neighbors in $F_N$ we mean the rational numbers |
1900 |
in $F_N$ immediately to the left and immediately to the right |
1901 |
of $a/b$.} |
1902 |
to $a/b$ in $F_N$, and the other neighbor in |
1903 |
$F_N$ is\footnote{Theorem \ref{thm:ccfr0:scba0:cfenclosingneighbors} |
1904 |
is a somewhat stronger statement about best approximations |
1905 |
than Khinchin makes in \cite{bibref:b:KhinchinClassic}, Theorem 15. |
1906 |
We were not able to locate |
1907 |
this theorem or a proof in print, |
1908 |
but this theorem is understood within the number theory community. |
1909 |
It appears on the Web |
1910 |
page of David Eppstein \cite{bibref:i:davideppstein} in the form of a |
1911 |
`C'-language computer program, |
1912 |
\texttt{http://www.ics.uci.edu/\~{}{}eppstein/numth/frap.c}. |
1913 |
Although |
1914 |
Dr. Eppstein phrases the solution in terms of modifying |
1915 |
a partial quotient, his approach is equivalent to |
1916 |
(\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01}).} |
1917 |
|
1918 |
\begin{equation} |
1919 |
\label{eq:ccfr0:scba0:thm:cfenclosingneighbors:01} |
1920 |
\frac{{\displaystyle{\left\lfloor {\frac{{N - q_{k - 1} }}{{q_k }}} \right\rfloor} |
1921 |
p_k + p_{k - 1} }}{{\displaystyle{\left\lfloor {\frac{{N - q_{k - 1} }}{{q_k }}} |
1922 |
\right\rfloor} q_k + q_{k - 1} }}. |
1923 |
\end{equation} |
1924 |
\end{vworktheoremstatementpar} |
1925 |
\begin{vworktheoremproof} |
1926 |
First, it is proved that the highest-order |
1927 |
convergent $s_k = p_k/q_k$ with $q_k \leq N$ is one of the two |
1928 |
neighbors to $a/b$ in $F_N$. $s_k \in F_N$, since $q_k \leq N$. |
1929 |
By Theorem \ref{thm:ccfr0:scba0:convergentcloseness}, the upper bound on the |
1930 |
difference between $a/b$ and arbitrary $s_k$ is given by |
1931 |
|
1932 |
\begin{equation} |
1933 |
\label{eq:ccfr0:scba0:thm:cfenclosingneighbors:02} |
1934 |
\left| {\frac{a}{b} - \frac{{p_k }}{{q_k }}} \right| < \frac{1}{{q_k q_{k + 1} }}. |
1935 |
\end{equation} |
1936 |
|
1937 |
For two consecutive terms in $F_N$, $Kh-Hk=1$ |
1938 |
(\cfryzeroxrefcomma{}Theorem \ref{thm:cfry0:spfs:02}). |
1939 |
For a Farey neighbor $H/K$ to $s_k$ in $F_N$, |
1940 |
(\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:03}) must hold. |
1941 |
|
1942 |
\begin{equation} |
1943 |
\label{eq:ccfr0:scba0:thm:cfenclosingneighbors:03} |
1944 |
\frac{1}{q_k N} \leq \left| {\frac{H}{K} - \frac{p_k}{q_k}} \right| |
1945 |
\end{equation} |
1946 |
|
1947 |
$q_{k+1}>N$, because $q_{k+1}>q_k$ and $p_k/q_k$ was chosen to be the |
1948 |
highest-order convergent with $q_k\leq N$. Using this knowledge and |
1949 |
combining (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:02}) and |
1950 |
(\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:03}) leads to |
1951 |
(\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:04}). |
1952 |
|
1953 |
\begin{equation} |
1954 |
\label{eq:ccfr0:scba0:thm:cfenclosingneighbors:04} |
1955 |
\left| {\frac{a}{b} - \frac{{p_k }}{{q_k }}} \right| < \frac{1}{{q_k q_{k + 1} }} |
1956 |
< |
1957 |
\frac{1}{q_k N} \leq \left| {\frac{H}{K} - \frac{p_k}{q_k}} \right| |
1958 |
\end{equation} |
1959 |
|
1960 |
This proves that $s_k$ is one neighbor to $a/b$ in $F_N$. |
1961 |
The apparatus of continued fractions ensures that the |
1962 |
highest order convergent $s_k$ with $q_k\leq N$ is closer to $a/b$ than |
1963 |
to any neighboring term in $F_N$. Thus, there is |
1964 |
no intervening term of $F_N$ between $s_k$ and $a/b$. |
1965 |
If $k$ is even, $s_k<a/b$, and if $k$ is |
1966 |
odd, $s_k>a/b$. |
1967 |
|
1968 |
It must be proved that (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01}) is the other Farey |
1969 |
neighbor. For brevity, only the case of $k$ even is proved: the |
1970 |
case of $k$ odd is symmetrical. (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01}) |
1971 |
is of the form (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:05}), |
1972 |
where $i \in \vworkintsetnonneg$. |
1973 |
|
1974 |
\begin{equation} |
1975 |
\label{eq:ccfr0:scba0:thm:cfenclosingneighbors:05} |
1976 |
\frac{{ip_k + p_{k - 1} }}{{iq_k + q_{k - 1} }} |
1977 |
\end{equation} |
1978 |
|
1979 |
$k$ is even, $s_k < a/b$, and the two Farey terms enclosing $a/b$, in |
1980 |
order, are |
1981 |
|
1982 |
\begin{equation} |
1983 |
\label{eq:ccfr0:scba0:thm:cfenclosingneighbors:06} |
1984 |
\frac{p_k }{q_k },\frac{ip_k + p_{k - 1} }{iq_k + q_{k - 1} }. |
1985 |
\end{equation} |
1986 |
|
1987 |
Applying the $Kh - Hk = 1$ test, (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:07}), \ |
1988 |
gives the |
1989 |
result of 1, since by Theorem |
1990 |
\ref{thm:ccfr0:scnv0:crossproductminusone}, |
1991 |
$q_kp_{k-1}-p_kq_{k-1}=(-1)^k$. |
1992 |
|
1993 |
\begin{equation} |
1994 |
\label{eq:ccfr0:scba0:thm:cfenclosingneighbors:07} |
1995 |
\begin{array}{*{20}c} |
1996 |
{(q_k )(ip_k + p_{k - 1} ) - (p_k )(iq_k + q_{k - 1} ) = 1} |
1997 |
\end{array} |
1998 |
\end{equation} |
1999 |
|
2000 |
Thus, every potential Farey neighbor of the form (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:05}) |
2001 |
meets the $Kh - Hk = 1$ test. It is also straightforward |
2002 |
to show that \emph{only} potential Farey neighbors of the |
2003 |
form (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:05}) can meet the $Kh-Hk=1$ test, using the |
2004 |
property that $p_k$ and $q_k$ are coprime. |
2005 |
|
2006 |
It must be established that a |
2007 |
rational number of the form (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:05}) |
2008 |
is irreducible. This result comes directly from |
2009 |
(\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:07}), |
2010 |
since if the numerator |
2011 |
and denominator of (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01}) or |
2012 |
(\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:05}) are not coprime, the difference of 1 is |
2013 |
not possible. |
2014 |
|
2015 |
The denominator of (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01}) |
2016 |
can be rewritten as |
2017 |
|
2018 |
\begin{equation} |
2019 |
\label{eq:ccfr0:scba0:thm:cfenclosingneighbors:08} |
2020 |
N - \left[ {\left( {N - q_{k - 1} } \right)\bmod q_k } \right] \in \left\{ {N - q_k + 1,...,N} \right\}. |
2021 |
\end{equation} |
2022 |
|
2023 |
It must be shown that if one irreducible |
2024 |
rational number---namely, the rational number given by |
2025 |
(\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01})---with a denominator |
2026 |
$\in \{ N-q_k+1,\ldots{} ,N \}$ meets the $Kh - Hk = 1$ |
2027 |
test, there can be no other irreducible rational number |
2028 |
in $F_N$ with a larger |
2029 |
denominator which also meets this test. |
2030 |
|
2031 |
Given (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:07}), |
2032 |
and given that \emph{only} rational numbers of the form |
2033 |
(\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:05}) |
2034 |
can meet the $Kh-Hk=1$ test, and given that any number of the |
2035 |
form (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:05}) |
2036 |
is irreducible, the irreducible number meeting the |
2037 |
$Kh-Hk=1$ test with the next larger denominator after the denominator of |
2038 |
(\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01}) |
2039 |
will have a denominator $\in \{ N+1, \ldots, N+q_k \}$. Thus, |
2040 |
no other irreducible rational number in $F_N$ besides that given |
2041 |
by (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01}) with a larger denominator |
2042 |
$\leq N$ and which meets the $Kh - Hk = 1$ test can exist; therefore |
2043 |
(\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01}) is the other enclosing Farey neighbor to |
2044 |
$a/b$ in $F_N$. |
2045 |
\end{vworktheoremproof} |
2046 |
\vworktheoremfooter{} |
2047 |
|
2048 |
Theorem \ref{thm:ccfr0:scba0:cfenclosingneighbors} establishes that |
2049 |
the two neighbors in $F_N$ to a rational number $a/b$ will be the highest-order |
2050 |
convergent with a denominator not exceeding $N$, and the number |
2051 |
specified by (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01}). |
2052 |
An interesting and worthwhile question to ask about |
2053 |
Theorem \ref{thm:ccfr0:scba0:cfenclosingneighbors} is which of the |
2054 |
two neighbors will be \emph{closer} to $a/b$---the convergent or the |
2055 |
number specified by (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01})? |
2056 |
Can we make any strong, simple, and easy-to-remember statements |
2057 |
about the relative distance? We answer this question and some related |
2058 |
questions now. |
2059 |
|
2060 |
We are not aware of any rules that decisively predict which of the two |
2061 |
Farey neighbors in Theorem \ref{thm:ccfr0:scba0:cfenclosingneighbors} |
2062 |
will be closer to $a/b$\footnote{We should qualify this by saying that |
2063 |
we mean a rule which uses only partial quotients up through |
2064 |
$a_k$ or at most $a_{k+1}$, which is the same information used |
2065 |
by the theorem. We should also add that although Theorem |
2066 |
\ref{thm:ccfr0:scba0:cfenclosingneighbors} is worded to only consider |
2067 |
non-negative rational numbers, the theorem and the results here |
2068 |
apply to non-negative irrational numbers as well, so long as enough partial |
2069 |
quotients can be obtained.}, although Lemma |
2070 |
\ref{lem:ccfr0:scba0:enclosingneighborstheoremfurtherresult} is able |
2071 |
to predict that the highest-ordered convergent $s_k$ with a denominator |
2072 |
not exceeding $N$ will be closer in many cases. |
2073 |
In general, either neighbor may be closer. |
2074 |
The most straightforward approach that we |
2075 |
are aware of is to calculate both Farey neighbors and to calculate |
2076 |
their respective distances from $a/b$. The difficulty in devising a simple rule |
2077 |
to predict which neighbor |
2078 |
is closer is compounded by that fact that knowledge of |
2079 |
$[a_0; a_1, \ldots{} , a_k]$ such that $s_k$ is the highest-ordered |
2080 |
convergent with $q_k \leq N$ is incomplete knowledge of $a/b$ and can |
2081 |
only confine $a/b$ to an inequality in the sense suggested by |
2082 |
(\ref{eq:ccfr0:spar0:01}) through |
2083 |
(\ref{eq:ccfr0:spar0:03}). Note that the |
2084 |
value specified by (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01}) |
2085 |
is an intermediate fraction, and that the statement of Theorem |
2086 |
\ref{thm:ccfr0:scba0:cfenclosingneighbors} |
2087 |
coincides with Khinchin's Theorem 15 |
2088 |
(\cite{bibref:b:KhinchinClassic}, p. 22). |
2089 |
|
2090 |
However, even in the absence of a rule to decisively |
2091 |
predict which of the |
2092 |
two Farey neighbors specified by Theorem |
2093 |
\ref{thm:ccfr0:scba0:cfenclosingneighbors} is closer to $a/b$, |
2094 |
there are other useful properties of convergents |
2095 |
as best approximations which we present |
2096 |
now. |
2097 |
|
2098 |
It has been stated earlier that even-ordered convergents form an |
2099 |
increasing sequence and that odd-ordered convergents also form a |
2100 |
decreasing sequence. However, up to this point, we have not made |
2101 |
a statement about the relationship between even- and odd-ordered |
2102 |
convergents. We present such a statement as Lemma |
2103 |
\ref{lem:ccfr0:scba0:convergenterrordecreases}, |
2104 |
below. |
2105 |
|
2106 |
\begin{vworklemmastatement} |
2107 |
\label{lem:ccfr0:scba0:convergenterrordecreases} |
2108 |
In the case of a finite or infinite continued fraction representation |
2109 |
of a non-negative rational or irrational |
2110 |
number $\alpha \in \vworkrealsetnonneg$, for all $k$, |
2111 |
|
2112 |
\begin{equation} |
2113 |
\label{eq:lem:ccfr0:scba0:convergenterrordecreases:01} |
2114 |
\left| {\alpha - \frac{p_k}{q_k}} \right| < |
2115 |
\left| {\alpha - \frac{p_{k-1}}{q_{k-1}}} \right| . |
2116 |
\end{equation} |
2117 |
In other words, convergents get ever-closer to $\alpha$, without |
2118 |
respect to whether they are even- or odd-ordered convergents. |
2119 |
\end{vworklemmastatement} |
2120 |
\begin{vworklemmaproof} |
2121 |
In this proof, we show that for all $k$, |
2122 |
|
2123 |
\begin{equation} |
2124 |
\label{eq:lem:ccfr0:scba0:convergenterrordecreases:02} |
2125 |
| s_{k-2} - s_{k-1} | > 2 | s_{k-1} - s_k | . |
2126 |
\end{equation} |
2127 |
|
2128 |
To understand why the proof is valid, consider the case of $k$ even, |
2129 |
in which case $s_k < \alpha$, so that $s_{k-1} - \alpha < s_{k-1} - s_k$. |
2130 |
If $s_{k-1} - s_{k-2} > 2 (s_{k-1} - s_k)$, then |
2131 |
$s_{k-2}$ is further to the left of $\alpha$ than $s_{k-1}$ is to the |
2132 |
right of $\alpha$; thus (\ref{eq:lem:ccfr0:scba0:convergenterrordecreases:01}) |
2133 |
applies. A symmetrical argument holds for $k$ odd. |
2134 |
|
2135 |
By Theorem \ref{thm:ccfr0:scnv0:crossproductminusone}, |
2136 |
|
2137 |
\begin{equation} |
2138 |
\label{eq:lem:ccfr0:scba0:convergenterrordecreases:03} |
2139 |
s_{k-2} - s_{k-1} |
2140 |
= \frac{p_{k-2}}{q_{k-2}} |
2141 |
- \frac{p_{k-1}}{q_{k-1}} |
2142 |
= \frac{(-1)^{k-1}}{q_{k-2} q_{k-1}} , |
2143 |
\end{equation} |
2144 |
|
2145 |
and similarly |
2146 |
|
2147 |
\begin{equation} |
2148 |
\label{eq:lem:ccfr0:scba0:convergenterrordecreases:04} |
2149 |
s_{k-1} - s_{k} |
2150 |
= \frac{p_{k-1}}{q_{k-1}} |
2151 |
- \frac{p_{k}}{q_{k}} |
2152 |
= \frac{(-1)^{k}}{q_{k-1} q_{k}} . |
2153 |
\end{equation} |
2154 |
|
2155 |
In order for (\ref{eq:lem:ccfr0:scba0:convergenterrordecreases:02}) |
2156 |
to be met, it must be true that |
2157 |
$2 q_{k-2} q_{k-1} < q_{k-1} q_k$, or equivalently that |
2158 |
$2 q_{k-2} < q_k$. Since canonically $q_k = a_k q_{k-1} + q_{k-2}$ |
2159 |
(Eq. \ref{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:10}), |
2160 |
the requirement is that $2 q_{k-2} < a_k q_{k-1} + q_{k-2}$. |
2161 |
Since $a_k \geq 1$ and convergents are ever-increasing, |
2162 |
(\ref{eq:lem:ccfr0:scba0:convergenterrordecreases:02}) is met and the |
2163 |
lemma is proved. |
2164 |
\end{vworklemmaproof} |
2165 |
\vworklemmafooter{} |
2166 |
|
2167 |
Theorem \ref{thm:ccfr0:scba0:convergentcloseness} establishes a |
2168 |
maximum distance from a number $\alpha$ that we wish to approximate |
2169 |
to a convergent. We now provide a second result that establishes |
2170 |
a \emph{minimum} distance. (This result is Theorem 13, p. |
2171 |
15, from \cite{bibref:b:KhinchinClassic}.) |
2172 |
|
2173 |
\begin{vworktheoremstatement} |
2174 |
\label{thm:ccfr0:scba0:convergentfarness} |
2175 |
In the case of an infinite continued fraction representation |
2176 |
$[a_0; a_1, a_2, \ldots]$ of |
2177 |
a non-negative irrational number $\alpha \in \vworkrealsetnonneg$, |
2178 |
for all $k \geq 0$; or in the case of a [necessarily finite] |
2179 |
continued fraction representation $[a_0; a_1, a_2, \ldots , a_n]$ |
2180 |
of a non-negative rational number |
2181 |
$\alpha \in \vworkrealsetnonneg$, for all $0 \leq k \leq n-1$, |
2182 |
|
2183 |
\begin{equation} |
2184 |
\label{eq:thm:ccfr0:scba0:convergentfarness:01} |
2185 |
\left| {\alpha - \frac{p_k}{q_k}} \right| > \frac{1}{q_k(q_{k+1}+q_k)} . |
2186 |
\end{equation} |
2187 |
\end{vworktheoremstatement} |
2188 |
\begin{vworktheoremproof} |
2189 |
We've already established (Lemma \ref{lem:ccfr0:scba0:convergenterrordecreases}) |
2190 |
that each convergent $s_{k+1}$ is nearer to |
2191 |
a number $\alpha$ to be approximated than the previous |
2192 |
convergent, $s_k$, i.e. for all $k$, |
2193 |
|
2194 |
\begin{equation} |
2195 |
\label{eq:thm:ccfr0:scba0:convergentfarness:02} |
2196 |
\left| {\alpha - \frac{p_{k+1}}{q_{k+1}}} \right| < |
2197 |
\left| {\alpha - \frac{p_{k}}{q_{k}}} \right| . |
2198 |
\end{equation} |
2199 |
|
2200 |
Since the mediant of two fractions always lies between |
2201 |
them (Lemma \cfryzeroxrefhyphen{}\ref{lem:cfry0:spfs:02c}), it |
2202 |
follows directly that |
2203 |
|
2204 |
\begin{equation} |
2205 |
\label{eq:thm:ccfr0:scba0:convergentfarness:03} |
2206 |
\left| {\alpha - \frac{p_{k}}{q_{k}}} \right| > |
2207 |
\left| {\frac{p_k + p_{k+1}}{q_k + q_{k+1}} - \frac{p_k}{q_k}} \right| = |
2208 |
\frac{1}{q_k ( q_k + q_{k+1})} . |
2209 |
\end{equation} |
2210 |
\end{vworktheoremproof} |
2211 |
\begin{vworktheoremparsection}{Remark I} |
2212 |
This theorem can be combined with Theorem \ref{thm:ccfr0:scba0:convergentcloseness} |
2213 |
to give the following combined inequality: |
2214 |
|
2215 |
\begin{equation} |
2216 |
\label{eq:thm:ccfr0:scba0:convergentfarness:04} |
2217 |
\frac{1}{q_k ( q_k + q_{k+1})} < |
2218 |
\left| {\alpha - \frac{p_{k}}{q_{k}}} \right| \leq |
2219 |
\frac{1}{q_k q_{k+1}} . |
2220 |
\end{equation} |
2221 |
\end{vworktheoremparsection} |
2222 |
\vworktheoremfooter{} |
2223 |
|
2224 |
We now supply an interesting and sometimes useful property of |
2225 |
convergents used as best approximations. Note that we later show that |
2226 |
Lemma \ref{lem:ccfr0:scba0:convergentbetterappthanlesserdenominator} |
2227 |
is a weak statement (a stronger statement can be made, Lemma |
2228 |
\ref{lem:ccfr0:scba0:morecomplexconvergentbapprule}), but this lemma |
2229 |
has the advantage of being extremely easy to remember. |
2230 |
|
2231 |
\begin{vworklemmastatement} |
2232 |
\label{lem:ccfr0:scba0:convergentbetterappthanlesserdenominator} |
2233 |
A convergent $s_k = p_k/q_k$ to a non-negative [rational or irrational] number |
2234 |
$\alpha \in \vworkrealsetnonneg$ is closer to $\alpha$ |
2235 |
than any other rational number with the same or a smaller |
2236 |
denominator. |
2237 |
\end{vworklemmastatement} |
2238 |
\begin{vworklemmaproof} |
2239 |
Let $\alpha$ be the non-negative real number, rational or irrational, |
2240 |
that we wish to approximate. |
2241 |
|
2242 |
If there is a number (let's call it $c/d$) |
2243 |
closer to $\alpha$ than $s_k = p_k / q_k$, with the same or a smaller denominator |
2244 |
than $s_k$, then by definition it must be in the Farey series of order |
2245 |
$q_k$, which we denote $F_{q_k}$. |
2246 |
|
2247 |
Theorem \ref{thm:ccfr0:scba0:cfenclosingneighbors} |
2248 |
assures us that the two Farey neighbors to $\alpha$ in $F_{q_k}$ will be |
2249 |
$s_k$ and the number given by (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01}). |
2250 |
Note that Theorem \ref{thm:ccfr0:scba0:cfenclosingneighbors} |
2251 |
applies to irrational numbers as well (although the theorem statement |
2252 |
does not indicate this), so we interpret |
2253 |
Theorem \ref{thm:ccfr0:scba0:cfenclosingneighbors} |
2254 |
in that sense. |
2255 |
|
2256 |
Note in (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01}) that the |
2257 |
expression involving the $floor(\cdot{})$ function will evaluate |
2258 |
to be zero, since $N=q_k$. Thus, the other Farey neighbor to |
2259 |
$\alpha$ in $F_{q_k}$ will be $s_{k-1} = p_{k-1}/q_{k-1}$. |
2260 |
|
2261 |
We have already shown in Lemma \ref{lem:ccfr0:scba0:convergenterrordecreases} |
2262 |
that $|\alpha - s_{k-1}| > |\alpha - s_{k}|$, therefore |
2263 |
$s_k$ is closer to $\alpha$ than the other Farey neighbor given |
2264 |
by (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01}). |
2265 |
Furthermore, because any $c/d$ which is closer to $\alpha$ than |
2266 |
$s_k$ must be present in $F_{q_k}$, such a $c/d$ does not exist. |
2267 |
\end{vworklemmaproof} |
2268 |
\begin{vworklemmaparsection}{Remark I} |
2269 |
In practice, this lemma is little more than parlor trivia |
2270 |
(it is not mathematically significant), but it is useful |
2271 |
information and very easy to remember. For example, $355/113$ is a convergent to |
2272 |
$\pi$, and it is sometimes useful to know that no better rational approximation |
2273 |
can exist with the same or a smaller denominator. |
2274 |
\end{vworklemmaparsection} |
2275 |
\begin{vworklemmaparsection}{Remark II} |
2276 |
A stronger statement can be made (see |
2277 |
Lemma \ref{lem:ccfr0:scba0:morecomplexconvergentbapprule}). |
2278 |
\end{vworklemmaparsection} |
2279 |
\vworklemmafooter{} |
2280 |
|
2281 |
We now |
2282 |
present a stronger statement about convergents as best approximations that |
2283 |
is not as easy to remember as |
2284 |
Lemma \ref{lem:ccfr0:scba0:convergentbetterappthanlesserdenominator}. |
2285 |
|
2286 |
\begin{vworklemmastatement} |
2287 |
\label{lem:ccfr0:scba0:morecomplexconvergentbapprule} |
2288 |
A convergent $s_k = p_k/q_k$ to a non-negative |
2289 |
[rational or irrational] number |
2290 |
$\alpha \in \vworkrealsetnonneg$ is closer to $\alpha$ |
2291 |
than any other rational number with a denominator |
2292 |
less than $q_k + q_{k-1}$. |
2293 |
\end{vworklemmastatement} |
2294 |
\begin{vworklemmaproof} |
2295 |
Let $N$ be the denominator of a rational number which is |
2296 |
potentially closer to $\alpha$ than $s_k$. If |
2297 |
$N < q_k + q_{k+1}$, then |
2298 |
(\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01}) |
2299 |
evaluates to $s_{k-1}$, and Lemma |
2300 |
\ref{lem:ccfr0:scba0:convergenterrordecreases} has established that |
2301 |
$s_k$ is closer to $\alpha$ than $s_{k-1}$. If, on the other |
2302 |
hand, $N \geq q_k + q_{k+1}$, then the intermediate fraction specified by |
2303 |
(\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01}) \emph{may} be |
2304 |
closer to $\alpha$ than $s_k$. |
2305 |
\end{vworklemmaproof} |
2306 |
\begin{vworklemmaparsection}{Remark I} |
2307 |
This statement is harder to remember, but a stronger statement |
2308 |
than Lemma \ref{lem:ccfr0:scba0:convergentbetterappthanlesserdenominator}. |
2309 |
\end{vworklemmaparsection} |
2310 |
\begin{vworklemmaparsection}{Remark II} |
2311 |
Note that the only valid implication is $N < q_k + q_{k+1} \rightarrow$ |
2312 |
(convergent is closer). Note that |
2313 |
$N \geq q_k + q_{k+1} \nrightarrow$ (intermediate fraction is closer)! |
2314 |
If $N \geq q_k + q_{k+1}$, either the convergent or the intermediate fraction |
2315 |
may be closer. |
2316 |
This statement is harder to remember, but a stronger statement |
2317 |
than Lemma \ref{lem:ccfr0:scba0:convergentbetterappthanlesserdenominator}. |
2318 |
\end{vworklemmaparsection} |
2319 |
\vworklemmafooter{} |
2320 |
|
2321 |
Finally, we present a result about Theorem |
2322 |
\ref{thm:ccfr0:scba0:cfenclosingneighbors} that will predict |
2323 |
in some circumstances that the highest-ordered convergent |
2324 |
$s_k$ with a denominator not exceeding $N$ must be closer |
2325 |
to $a/b$ than the intermediate fraction specified by |
2326 |
(\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01}). |
2327 |
|
2328 |
\begin{vworklemmastatement} |
2329 |
\label{lem:ccfr0:scba0:enclosingneighborstheoremfurtherresult} |
2330 |
In Theorem \ref{thm:ccfr0:scba0:cfenclosingneighbors}, |
2331 |
if $N < q_k + q_{k-1}$, the highest ordered convergent |
2332 |
$s_k$ with a denominator not exceeding $N$ is closer to |
2333 |
$a/b$\footnote{Note that this result is also valid for |
2334 |
convergents to an irrational number, although |
2335 |
Theorem \ref{thm:ccfr0:scba0:cfenclosingneighbors} is |
2336 |
not worded in this way.} then the intermediate fraction specified by |
2337 |
(\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01}). |
2338 |
If $N \geq q_k + q_{k-1}$, either $s_k$ or the intermediate |
2339 |
fraction specified by (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01}) |
2340 |
may be closer. |
2341 |
\end{vworklemmastatement} |
2342 |
\begin{vworklemmaproof} |
2343 |
See the proof of Lemma |
2344 |
\ref{lem:ccfr0:scba0:morecomplexconvergentbapprule}. |
2345 |
\end{vworklemmaproof} |
2346 |
\vworklemmafooter{} |
2347 |
|
2348 |
Theorem \ref{thm:ccfr0:scba0:cfenclosingneighbors} immediately suggests |
2349 |
an algorithm for obtaining the enclosing rational numbers in $F_N$ |
2350 |
to a rational number $a/b \notin F_N$, which we present as |
2351 |
Algorithm \ref{alg:ccfr0:scba0:cfenclosingneighborsfn}. Although |
2352 |
we don't formally show it, the algorithm is $O(log \; N)$, due to |
2353 |
the minimum geometric rate of increase of convergents |
2354 |
(Theorem \ref{thm:ccfr0:scnv0:minimumrateofconvergentdenominatorincrease}). |
2355 |
Note that the algorithm will proceed only until $q_k > N$, not necessarily |
2356 |
until all partial quotients of $a/b$ are obtained. Note also that the |
2357 |
algorithm can be applied to irrational numbers with minor |
2358 |
modification (all that matters is that we can obtain enough |
2359 |
partial quotients). |
2360 |
|
2361 |
\begin{vworkalgorithmstatementpar}{Enclosing Neighbors Of \mbox{\boldmath $a/b \notin F_N$} |
2362 |
In \mbox{\boldmath $F_N$}} |
2363 |
\label{alg:ccfr0:scba0:cfenclosingneighborsfn} |
2364 |
\begin{alglvl0} |
2365 |
\item $k := -1$. |
2366 |
\item $divisor_{-1} := a$. |
2367 |
\item $remainder_{-1} := b$. |
2368 |
\item $p_{-1} := 1$. |
2369 |
\item $q_{-1} := 0$. |
2370 |
|
2371 |
\item Repeat |
2372 |
|
2373 |
\begin{alglvl1} |
2374 |
\item $k := k + 1$. |
2375 |
\item $dividend_k := divisor_{k-1}$. |
2376 |
\item $divisor_k := remainder_{k-1}$. |
2377 |
\item $a_k := dividend_k \; div \; divisor_k$. |
2378 |
\item $remainder_k := dividend_k \; mod \; divisor_k$. |
2379 |
\item If $k=0$ then $p_k := a_k$ else $p_k := a_k p_{k-1} + p_{k-2}$. |
2380 |
\item If $k=0$ then $q_k := 1$ else $q_k := a_k q_{k-1} + q_{k-2}$. |
2381 |
\end{alglvl1} |
2382 |
|
2383 |
\item Until ($q_k > k_{MAX}$). |
2384 |
\item $s_{k-1} = p_{k-1}/q_{k-1}$ will be one Farey neighbor to $a/b$ in $F_{k_{MAX}}$. |
2385 |
Apply (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01}) |
2386 |
to obtain the other Farey neighbor. |
2387 |
\end{alglvl0} |
2388 |
\end{vworkalgorithmstatementpar} |
2389 |
%\vworkalgorithmfooter{} |
2390 |
|
2391 |
\begin{vworkexamplestatement} |
2392 |
\label{ex:ccfr0:scba0:bestrapapptoratnum} |
2393 |
Find the members of $F_{100}$ which enclose the conversion factor |
2394 |
from kilometers-per-hour to miles-per-hour. Assume that |
2395 |
one mile is 1.6093 kilometers (exactly). |
2396 |
\end{vworkexamplestatement} |
2397 |
\begin{vworkexampleparsection}{Solution} |
2398 |
The conversion factor from KPH to MPH is the reciprocal of 1.6093. As a rational |
2399 |
number, 1.6093 is 16,093/10,000, so 10,000/16,093 is its exact reciprocal. |
2400 |
Applying Algorithm \ref{alg:ccfr0:scba0:cfenclosingneighborsfn} |
2401 |
with $a/b = 10,000/16,093$ and $k_{MAX} = 100$ yields Table |
2402 |
\ref{tbl:ex:ccfr0:scba0:bestrapapptoratnum}. |
2403 |
|
2404 |
\begin{table} |
2405 |
\caption{Application Of Algorithm \ref{alg:ccfr0:scba0:cfenclosingneighborsfn} |
2406 |
To Find Members Of $F_{100}$ Which Enclose 10,000/16,093 |
2407 |
(Example \ref{ex:ccfr0:scba0:bestrapapptoratnum})} |
2408 |
\label{tbl:ex:ccfr0:scba0:bestrapapptoratnum} |
2409 |
\begin{center} |
2410 |
\begin{tabular}{|c|c|c|c|c|c|c|} |
2411 |
\hline |
2412 |
\small{Index} & \small{$dividend_k$} & \small{$divisor_k$} & \small{$a_k$} & \small{$remainder_k$} & \small{$p_k$} & \small{$q_k$} \\ |
2413 |
\small{($k$)} & & & & & & \\ |
2414 |
\hline |
2415 |
\hline |
2416 |
\small{-1} & \small{N/A} & \small{10,000} & \small{N/A} & \small{16,093} & \small{1} & \small{0} \\ |
2417 |
\hline |
2418 |
\small{0} & \small{10,000} & \small{16,093} & \small{0} & \small{10,000} & \small{0} & \small{1} \\ |
2419 |
\hline |
2420 |
\small{1} & \small{16,093} & \small{10,000} & \small{1} & \small{6,093} & \small{1} & \small{1} \\ |
2421 |
\hline |
2422 |
\small{2} & \small{10,000} & \small{6,093} & \small{1} & \small{3,907} & \small{1} & \small{2} \\ |
2423 |
\hline |
2424 |
\small{3} & \small{6,093} & \small{3,907} & \small{1} & \small{2,186} & \small{2} & \small{3} \\ |
2425 |
\hline |
2426 |
\small{4} & \small{3,907} & \small{2,186} & \small{1} & \small{1,721} & \small{3} & \small{5} \\ |
2427 |
\hline |
2428 |
\small{5} & \small{2,186} & \small{1,721} & \small{1} & \small{465} & \small{5} & \small{8} \\ |
2429 |
\hline |
2430 |
\small{6} & \small{1,721} & \small{465} & \small{3} & \small{326} & \small{18} & \small{29} \\ |
2431 |
\hline |
2432 |
\small{7} & \small{465} & \small{326} & \small{1} & \small{139} & \small{23} & \small{37} \\ |
2433 |
\hline |
2434 |
\small{8} & \small{326} & \small{139} & \small{2} & \small{48} & \small{64} & \small{103} \\ |
2435 |
\hline |
2436 |
\end{tabular} |
2437 |
\end{center} |
2438 |
\end{table} |
2439 |
|
2440 |
Note from Table \ref{tbl:ex:ccfr0:scba0:bestrapapptoratnum} |
2441 |
that the 7-th order convergent, $s_7 = 23/37$, |
2442 |
is the highest-ordered convergent with $q_k \leq 100$, so |
2443 |
by Theorem \ref{thm:ccfr0:scba0:cfenclosingneighbors}, 23/37 |
2444 |
is one neighbor in $F_{100}$ to 10,000/16,093. Because $s_7$ |
2445 |
is an odd-ordered convergent, it will be the right |
2446 |
Farey neighbor. |
2447 |
By (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01}), the |
2448 |
other Farey neighbor is 41/66, and it will be the left |
2449 |
Farey neighbor. |
2450 |
\end{vworkexampleparsection} |
2451 |
%\vworkexamplefooter{} |
2452 |
|
2453 |
|
2454 |
\begin{vworkexamplestatement} |
2455 |
\label{ex:ccfr0:scba0:bestrapapptoirratnum} |
2456 |
Find the members of $F_{200}$ which |
2457 |
enclose $\sqrt{3}$. |
2458 |
\end{vworkexamplestatement} |
2459 |
\begin{vworkexampleparsection}{Solution} |
2460 |
We demonstrated in Example |
2461 |
\ref{ex:ccfr0:scin0:symboliccfalgorithmexample} |
2462 |
that the continued fraction representation of |
2463 |
$\sqrt{3}$ is $[1;\overline{1,2}]$. |
2464 |
As is highlighted in Footnote |
2465 |
\ref{footnote:ccfr0:scba0:rationalitynotrequired}, it isn't required |
2466 |
that a number be rational to apply Theorem |
2467 |
\ref{thm:ccfr0:scba0:cfenclosingneighbors}, so long as |
2468 |
enough partial quotients can be obtained. |
2469 |
Using knowledge of the partial quotients of |
2470 |
$\sqrt{3}$ and applying Algorithm \ref{alg:ccfr0:scba0:cfenclosingneighborsfn} |
2471 |
yields Table \ref{tbl:ex:ccfr0:scba0:bestrapapptoirratnum} (note that it isn't necessary |
2472 |
to track remainders, as we already have all of the partial quotients for |
2473 |
$\sqrt{3}$). |
2474 |
|
2475 |
\begin{table} |
2476 |
\caption{Application Of Algorithm \ref{alg:ccfr0:scba0:cfenclosingneighborsfn} |
2477 |
To Find Members Of $F_{100}$ Which Enclose $\sqrt{3}$ |
2478 |
(Example \ref{ex:ccfr0:scba0:bestrapapptoirratnum})} |
2479 |
\label{tbl:ex:ccfr0:scba0:bestrapapptoirratnum} |
2480 |
\begin{center} |
2481 |
\begin{tabular}{|c|c|c|c|} |
2482 |
\hline |
2483 |
\hspace{0.15in}\small{Index ($k$)}\hspace{0.15in} & \hspace{0.15in}\small{$a_k$}\hspace{0.15in} & |
2484 |
\hspace{0.15in}\small{$p_k$}\hspace{0.15in} & \hspace{0.15in}\small{$q_k$}\hspace{0.15in} \\ |
2485 |
\hline |
2486 |
\hline |
2487 |
\small{-1} & \small{N/A} & \small{1} & \small{0} \\ |
2488 |
\hline |
2489 |
\small{0} & \small{1} & \small{1} & \small{1} \\ |
2490 |
\hline |
2491 |
\small{1} & \small{1} & \small{2} & \small{1} \\ |
2492 |
\hline |
2493 |
\small{2} & \small{2} & \small{5} & \small{3} \\ |
2494 |
\hline |
2495 |
\small{3} & \small{1} & \small{7} & \small{4} \\ |
2496 |
\hline |
2497 |
\small{4} & \small{2} & \small{19} & \small{11} \\ |
2498 |
\hline |
2499 |
\small{5} & \small{1} & \small{26} & \small{15} \\ |
2500 |
\hline |
2501 |
\small{6} & \small{2} & \small{71} & \small{41} \\ |
2502 |
\hline |
2503 |
\small{7} & \small{1} & \small{97} & \small{56} \\ |
2504 |
\hline |
2505 |
\small{8} & \small{2} & \small{265} & \small{153} \\ |
2506 |
\hline |
2507 |
\small{9} & \small{1} & \small{362} & \small{209} \\ |
2508 |
\hline |
2509 |
\end{tabular} |
2510 |
\end{center} |
2511 |
\end{table} |
2512 |
|
2513 |
Note from Table \ref{tbl:ex:ccfr0:scba0:bestrapapptoirratnum} |
2514 |
that the 8-th order convergent, $s_8 = 265/153$, |
2515 |
is the highest-ordered convergent with $q_k \leq 200$, so |
2516 |
by Theorem \ref{thm:ccfr0:scba0:cfenclosingneighbors}, 265/153 |
2517 |
is one neighbor in $F_{100}$ to $\sqrt{3}$. Because $s_8$ |
2518 |
is an even-ordered convergent, it will be the left |
2519 |
Farey neighbor. |
2520 |
By (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01}), the |
2521 |
other Farey neighbor is 97/56, and it will be the right |
2522 |
Farey neighbor. |
2523 |
\end{vworkexampleparsection} |
2524 |
\vworkexamplefooter{} |
2525 |
|
2526 |
|
2527 |
It is clear that Algorithm \ref{alg:ccfr0:scba0:cfenclosingneighborsfn} |
2528 |
can be trivially modified to find enclosing neighbors |
2529 |
in $F_{k_{MAX},\overline{h_{MAX}}}$, and we present this |
2530 |
trivial modification as Algorithm |
2531 |
\ref{alg:ccfr0:scba0:cfenclosingneighborsfab}. |
2532 |
|
2533 |
\begin{vworkalgorithmstatementpar}{Enclosing Neighbors Of |
2534 |
\mbox{\boldmath $x \notin F_{k_{MAX},\overline{h_{MAX}}}$} |
2535 |
In \mbox{\boldmath $F_{k_{MAX},\overline{h_{MAX}}}$}} |
2536 |
\label{alg:ccfr0:scba0:cfenclosingneighborsfab} |
2537 |
\begin{alglvl0} |
2538 |
\item If $a/b < h_{MAX}/k_{MAX}$, apply Algorithm |
2539 |
\ref{alg:ccfr0:scba0:cfenclosingneighborsfn} directly; |
2540 |
|
2541 |
\item Else if $a/b > h_{MAX}/k_{MAX}$, apply Algorithm |
2542 |
\ref{alg:ccfr0:scba0:cfenclosingneighborsfn} using $b/a$ rather |
2543 |
than $a/b$ as the input to the algorithm, using $h_{MAX}$ |
2544 |
rather than $k_{MAX}$ as $N$, and |
2545 |
using the reciprocals of the results of the algorithm.\footnote{The |
2546 |
basis for taking the reciprocals of input and output and |
2547 |
using $h_{MAX}$ rather than $k_{MAX}$ are explained |
2548 |
in \cfryzeroxrefcomma{}Section \ref{cfry0:schk0}.} |
2549 |
|
2550 |
\end{alglvl0} |
2551 |
\end{vworkalgorithmstatementpar} |
2552 |
%\vworkalgorithmfooter{} |
2553 |
|
2554 |
\begin{vworkexamplestatement} |
2555 |
\label{ex:ccfr0:scba0:bestratapptoirratnum2d} |
2556 |
Find the members of $F_{200,\overline{100}}$ which |
2557 |
enclose $\sqrt{3}$. |
2558 |
\end{vworkexamplestatement} |
2559 |
\begin{vworkexampleparsection}{Solution} |
2560 |
It was shown in Example \ref{ex:ccfr0:scba0:bestrapapptoirratnum} |
2561 |
that the two enclosing neighbors to $\sqrt{3}$ in |
2562 |
$F_{200}$ are 265/153 and 97/56. Note that the first of |
2563 |
these neighbors, 265/153, violates the constraint on the |
2564 |
numerator. |
2565 |
As explained in Section \cfryzeroxrefhyphen{}\ref{cfry0:schk0}, |
2566 |
because $\sqrt{3} > 100/200$, the constraint on the |
2567 |
numerator is the dominant constraint, and the necessary |
2568 |
approach is to find the neighbors of $1/\sqrt{3}$ in |
2569 |
$F_{100}$, then invert the results. |
2570 |
Although we don't explain it in this work, |
2571 |
the reciprocal of a continued fraction can be formed by |
2572 |
``right-shifting'' or ``left-shifting'' the continued fraction one position. |
2573 |
Thus, if $[1;1,2,1,2,1,2, \ldots{}]$ = $[1;\overline{1,2}]$ |
2574 |
is the continued fraction representation of $\sqrt{3}$, then |
2575 |
$[0;1,1,2,1,2,1, \ldots{}]$ = $[0;1,\overline{1,2}]$ is the |
2576 |
continued fraction representation of $1/\sqrt{3}$. Using |
2577 |
this result and constructing the convergents until |
2578 |
$q_k \geq 100$ yields Table \ref{tbl:ex:ccfr0:scba0:bestratapptoirratnum2d}. |
2579 |
|
2580 |
\begin{table} |
2581 |
\caption{Application Of Algorithm \ref{alg:ccfr0:scba0:cfenclosingneighborsfab} |
2582 |
To Find Members Of $F_{100}$ Which Enclose $1/\sqrt{3}$ |
2583 |
(Example \ref{ex:ccfr0:scba0:bestratapptoirratnum2d})} |
2584 |
\label{tbl:ex:ccfr0:scba0:bestratapptoirratnum2d} |
2585 |
\begin{center} |
2586 |
\begin{tabular}{|c|c|c|c|} |
2587 |
\hline |
2588 |
\hspace{0.15in}\small{Index ($k$)}\hspace{0.15in} & \hspace{0.15in}\small{$a_k$}\hspace{0.15in} & |
2589 |
\hspace{0.15in}\small{$p_k$}\hspace{0.15in} & \hspace{0.15in}\small{$q_k$}\hspace{0.15in} \\ |
2590 |
\hline |
2591 |
\hline |
2592 |
\small{-1} & \small{N/A} & \small{1} & \small{0} \\ |
2593 |
\hline |
2594 |
\small{0} & \small{0} & \small{0} & \small{1} \\ |
2595 |
\hline |
2596 |
\small{1} & \small{1} & \small{1} & \small{1} \\ |
2597 |
\hline |
2598 |
\small{2} & \small{1} & \small{1} & \small{2} \\ |
2599 |
\hline |
2600 |
\small{3} & \small{2} & \small{3} & \small{5} \\ |
2601 |
\hline |
2602 |
\small{4} & \small{1} & \small{4} & \small{7} \\ |
2603 |
\hline |
2604 |
\small{5} & \small{2} & \small{11} & \small{19} \\ |
2605 |
\hline |
2606 |
\small{6} & \small{1} & \small{15} & \small{26} \\ |
2607 |
\hline |
2608 |
\small{7} & \small{2} & \small{41} & \small{71} \\ |
2609 |
\hline |
2610 |
\small{8} & \small{1} & \small{56} & \small{97} \\ |
2611 |
\hline |
2612 |
\small{9} & \small{2} & \small{153} & \small{265} \\ |
2613 |
\hline |
2614 |
\end{tabular} |
2615 |
\end{center} |
2616 |
\end{table} |
2617 |
|
2618 |
Note from Table \ref{tbl:ex:ccfr0:scba0:bestratapptoirratnum2d} |
2619 |
that the 8-th order convergent, $s_8 = 56/97$, |
2620 |
is the highest-ordered convergent with $q_k \leq 100$, so |
2621 |
by Theorem \ref{thm:ccfr0:scba0:cfenclosingneighbors}, 56/97 |
2622 |
is one neighbor in $F_{100}$ to $1/\sqrt{3}$. Because $s_8$ |
2623 |
is an even-ordered convergent, it will be the left |
2624 |
Farey neighbor. |
2625 |
By (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01}), the |
2626 |
other Farey neighbor is 41/71, and it will be the right |
2627 |
Farey neighbor. Taking the reciprocal of these neighbors (and |
2628 |
reversing their order) yields $97/56 < \sqrt{3} < 41/71$ |
2629 |
as the two members of $F_{200, \overline{100}}$ which enclose |
2630 |
$\sqrt{3}$. |
2631 |
\end{vworkexampleparsection} |
2632 |
\vworkexamplefooter{} |
2633 |
|
2634 |
|
2635 |
A natural question to ask is whether, given only a \emph{single} |
2636 |
rational number $a/b \in F_N$, the apparatus of continued fractions |
2637 |
can be used to economically find its neighbors in $F_N$. Examining |
2638 |
the proof of Theorem \ref{thm:ccfr0:scba0:cfenclosingneighbors}, |
2639 |
we see that the entire proof applies even if the denominator of the |
2640 |
highest-order convergent, $q_n$, is less than or equal to $N$---that is, |
2641 |
the number specified by (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01}) |
2642 |
is a left or right Farey neighbor in $F_N$ of $a/b$. If $n$ is even, |
2643 |
$s_{n-1} > s_n$, and the number specified by |
2644 |
(\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01}) will be the right Farey neighbor |
2645 |
of $s_n$, and |
2646 |
(\cfryzeroxrefhyphen{}\ref{eq:cfry0:sgfs0:thm:01:eq03}) and |
2647 |
(\cfryzeroxrefhyphen{}\ref{eq:cfry0:sgfs0:thm:01:eq04}) |
2648 |
can be used to find the left Farey neighbor. |
2649 |
On the other hand if $n$ odd, $s_{n-1} < s_n$, (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01}) |
2650 |
will be the left Farey neighbor of $s_n$, and |
2651 |
(\cfryzeroxrefhyphen{}\ref{eq:cfry0:sgfs0:thm:01:eq01}) |
2652 |
and |
2653 |
(\cfryzeroxrefhyphen{}\ref{eq:cfry0:sgfs0:thm:01:eq02}) |
2654 |
can be used to find the |
2655 |
right Farey neighbor. We summarize these observations as Algorithm |
2656 |
\ref{alg:ccfr0:scba0:cffareyneighborfn}. |
2657 |
|
2658 |
\begin{vworkalgorithmstatementpar}{Neighbors Of |
2659 |
\mbox{\boldmath $a/b \in F_N$} |
2660 |
In \mbox{\boldmath $F_N$}} |
2661 |
\label{alg:ccfr0:scba0:cffareyneighborfn} |
2662 |
\end{vworkalgorithmstatementpar} |
2663 |
\begin{alglvl0} |
2664 |
|
2665 |
\item Apply the first part of Algorithm |
2666 |
\ref{alg:ccfr0:scba0:cfenclosingneighborsfn} to obtain |
2667 |
all of the partial quotients and convergents of $a/b$. |
2668 |
The final convergent, $s_n = p_n/q_n$, will be |
2669 |
$a/b$ in reduced form. |
2670 |
|
2671 |
\item Use (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01}) |
2672 |
(with $k = n$) to obtain the right Farey neighbor |
2673 |
(if $n$ is even) or the left Farey neighbor (if $n$ |
2674 |
is odd). |
2675 |
|
2676 |
\item If $n$ is even, $s_{n-1} > s_n$, and the number specified by |
2677 |
(\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01}) will be |
2678 |
the right Farey neighbor of $s_n$. Use |
2679 |
(\cfryzeroxrefhyphen{}\ref{eq:cfry0:sgfs0:thm:01:eq03}) and |
2680 |
(\cfryzeroxrefhyphen{}\ref{eq:cfry0:sgfs0:thm:01:eq04}) |
2681 |
to find the left Farey neighbor. |
2682 |
On the other hand if $n$ is odd, $s_{n-1} < s_n$, |
2683 |
(\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01}) |
2684 |
will be the left Farey neighbor of $s_n$. Use |
2685 |
(\cfryzeroxrefhyphen{}\ref{eq:cfry0:sgfs0:thm:01:eq01}) |
2686 |
and (\cfryzeroxrefhyphen{}\ref{eq:cfry0:sgfs0:thm:01:eq02}) |
2687 |
to find the right Farey neighbor. |
2688 |
|
2689 |
\end{alglvl0} |
2690 |
%\vworkalgorithmfooter{} |
2691 |
|
2692 |
\begin{vworkexamplestatement} |
2693 |
\label{ex:ccfr0:scba0:fnneighborsaoverbinfn} |
2694 |
Find the neighbors of 5/7 in $F_{1,000,000}$. |
2695 |
\end{vworkexamplestatement} |
2696 |
\begin{vworkexampleparsection}{Solution} |
2697 |
As per Algorithm \ref{alg:ccfr0:scba0:cffareyneighborfn}, the first |
2698 |
step is to obtain the partial quotients and convergents of 5/7 |
2699 |
(these partial quotients and convergents are shown in |
2700 |
Table \ref{tbl:ex:ccfr0:scba0:fnneighborsaoverbinfn}). |
2701 |
|
2702 |
\begin{table} |
2703 |
\caption{Partial Quotients And Convergents Of 5/7 |
2704 |
(Example \ref{ex:ccfr0:scba0:fnneighborsaoverbinfn})} |
2705 |
\label{tbl:ex:ccfr0:scba0:fnneighborsaoverbinfn} |
2706 |
\begin{center} |
2707 |
\begin{tabular}{|c|c|c|c|c|c|c|} |
2708 |
\hline |
2709 |
\small{Index ($k$)} & \small{$dividend_k$} & \small{$divisor_k$} & \small{$a_k$} & \small{$remainder_k$} & \small{$p_k$} & \small{$q_k$} \\ |
2710 |
\hline |
2711 |
\hline |
2712 |
\small{-1} & \small{N/A} & \small{5} & \small{N/A} & \small{7} & \small{1} & \small{0} \\ |
2713 |
\hline |
2714 |
\small{0} & \small{5} & \small{7} & \small{0} & \small{5} & \small{0} & \small{1} \\ |
2715 |
\hline |
2716 |
\small{1} & \small{7} & \small{5} & \small{1} & \small{2} & \small{1} & \small{1} \\ |
2717 |
\hline |
2718 |
\small{2} & \small{5} & \small{2} & \small{2} & \small{1} & \small{2} & \small{3} \\ |
2719 |
\hline |
2720 |
\small{3} & \small{2} & \small{1} & \small{2} & \small{0} & \small{5} & \small{7} \\ |
2721 |
\hline |
2722 |
\end{tabular} |
2723 |
\end{center} |
2724 |
\end{table} |
2725 |
|
2726 |
Since the final convergent, $s_{3}$, is an odd-ordered convergent, $s_{k-1} < s_k$, and |
2727 |
(\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01}) will supply the left Farey neighbor |
2728 |
of 5/7. Applying (\ref{eq:ccfr0:scba0:thm:cfenclosingneighbors:01}) with |
2729 |
$N=1,000,000$, $k=3$, $k-1=2$, $p_k = 5$, $q_k = 7$, $p_{k-1}=2$, and $q_{k-1}=3$ |
2730 |
yields $\frac{714,282}{999,995}$ as the left Farey neighbor of 5/7 in $F_{1,000,000}$. |
2731 |
Application of (\cfryzeroxrefhyphen{}\ref{eq:cfry0:sgfs0:thm:01:eq01}) |
2732 |
and (\cfryzeroxrefhyphen{}\ref{eq:cfry0:sgfs0:thm:01:eq02}) |
2733 |
yields $\frac{714,283}{999,996}$ as the right Farey neighbor. |
2734 |
\end{vworkexampleparsection} |
2735 |
%\vworkexamplefooter{} |
2736 |
|
2737 |
|
2738 |
\begin{vworkalgorithmstatementpar}{Neighbors Of |
2739 |
\mbox{\boldmath $x \in F_{k_{MAX},\overline{h_{MAX}}}$} |
2740 |
In \mbox{\boldmath $F_{k_{MAX},\overline{h_{MAX}}}$}} |
2741 |
\label{alg:ccfr0:scba0:cffareyneighborfab} |
2742 |
\begin{alglvl0} |
2743 |
\item If $a/b < h_{MAX}/k_{MAX}$, apply Algorithm |
2744 |
\ref{alg:ccfr0:scba0:cffareyneighborfn} directly; |
2745 |
|
2746 |
\item Else if $a/b > h_{MAX}/k_{MAX}$, apply Algorithm |
2747 |
\ref{alg:ccfr0:scba0:cffareyneighborfn} using $b/a$ rather |
2748 |
than $a/b$ as the input to the algorithm, using $h_{MAX}$ |
2749 |
rather than $k_{MAX}$ as $N$, and |
2750 |
using the reciprocals of the results of the algorithm.\footnote{The |
2751 |
basis for taking the reciprocals of input and output and |
2752 |
using $h_{MAX}$ rather than $k_{MAX}$ are explained |
2753 |
in \cfryzeroxrefcomma{}Section \ref{cfry0:schk0}.} |
2754 |
\end{alglvl0} |
2755 |
\end{vworkalgorithmstatementpar} |
2756 |
\vworkalgorithmfooter{} |
2757 |
|
2758 |
|
2759 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
2760 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
2761 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
2762 |
\section{The Stern-Brocot Tree} |
2763 |
%Section tag: SBT0 |
2764 |
\label{ccfr0:ssbt0} |
2765 |
|
2766 |
In this chapter, we've developed continued fraction techniques of best |
2767 |
rational approximation without reference to any other models or theory. |
2768 |
Because the algorithms presented in this chapter are $O(log \; N)$, |
2769 |
the results so far are completely satisfactory and usable in practice. |
2770 |
It is not necessary to go further or to present additional information. |
2771 |
|
2772 |
However, there is a second model of best rational approximation (and a second |
2773 |
set of algorithms), involving |
2774 |
the Stern-Brocot tree. In fact, when reviewing the material in this |
2775 |
chapter, some readers have inquired why the Stern-Brocot tree was not |
2776 |
used.\footnote{In brief, the Stern-Brocot tree was not used because |
2777 |
the resulting algorithms are $O(N)$, and so will introduce practical |
2778 |
computational difficulties when used with large integers.} In this |
2779 |
section, we introduce the Stern-Brocot tree, demonstrate how to construct it, |
2780 |
mention its major properties, show its correspondence with the apparatus of |
2781 |
continued fractions, and finally show why we \emph{must} use the apparatus |
2782 |
of continued fractions to find best rational approximations. |
2783 |
|
2784 |
|
2785 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
2786 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
2787 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
2788 |
\subsection{Definition And Properties Of The Stern-Brocot Tree} |
2789 |
%Section tag: DPT0 |
2790 |
\label{ccfr0:ssbt0:sdpt0} |
2791 |
|
2792 |
\index{Stern-Brocot tree}The Stern-Brocot tree |
2793 |
(Figure \ref{fig:ccfr0:ssbt0:sdpt0:00}), is |
2794 |
an infinite binary tree which contains all positive rational numbers. |
2795 |
|
2796 |
\begin{figure} |
2797 |
\centering |
2798 |
\includegraphics[width=4.6in]{c_cfr0/sbtdpt01.eps} |
2799 |
\caption{The Stern-Brocot Tree} |
2800 |
\label{fig:ccfr0:ssbt0:sdpt0:00} |
2801 |
\end{figure} |
2802 |
|
2803 |
To construct the tree, one begins with the two fractions $\frac{0}{1}$ |
2804 |
and $\frac{1}{0}$, and forms the mediant (see Definition |
2805 |
\cfryzeroxrefhyphen{}\ref{def:cfry0:spfs:02}) |
2806 |
of two adjacent fractions as many |
2807 |
times as desired to generate additional fractions. |
2808 |
Figure \ref{fig:ccfr0:ssbt0:sdpt0:00} illustrates the construction process. |
2809 |
Note in Figure \ref{fig:ccfr0:ssbt0:sdpt0:00} that the adjacent fractions |
2810 |
are always above and to the left and above and to the right of the fraction |
2811 |
being constructed, and that in the construction of the Stern-Brocot |
2812 |
tree, one of the adjacent fractions can be many levels upwards in the tree |
2813 |
from the fraction being constructed. For example, in |
2814 |
Figure \ref{fig:ccfr0:ssbt0:sdpt0:00}, when constructing the fraction |
2815 |
4/5, the left adjacent fraction (3/4) is nearby in the figure, but |
2816 |
the right adjacent fraction (1/1) is three levels up to the left and |
2817 |
one level up to the right. Note when constructing the fraction 4/5 that |
2818 |
its right adjacent fraction is \emph{not} 4/3. |
2819 |
|
2820 |
Note that it is also possible to maintain the Stern-Brocot tree as an |
2821 |
ordered list, rather than a tree, starting with the list |
2822 |
$\{0/1, 1/0\}$. An additional element may be inserted |
2823 |
between any two existing elements in the list by forming their mediant, |
2824 |
and this process may be repeated indefinitely. Note also that two |
2825 |
elements $s_L$ and $s_R$ are Farey neighbors to any number $\alpha$ |
2826 |
if $s_L < \alpha < s_R$ and the mediant of $s_L$ and $s_R$ has a |
2827 |
denominator larger than the order of the Farey series. This gives a convenient |
2828 |
procedure for forming best rational approximations using only the Stern-Brocot |
2829 |
tree, as the following example shows. |
2830 |
|
2831 |
\begin{vworkexamplestatement} |
2832 |
\label{ex:ccfr0:ssbt0:sdpt0:01} |
2833 |
Find the members of $F_{10}$ which enclose $\pi$. |
2834 |
\end{vworkexamplestatement} |
2835 |
\begin{vworkexampleparsection}{Solution} |
2836 |
By repeatedly calculating mediants, terms can be added to the list |
2837 |
$\{\frac{0}{1}, \frac{1}{0} \}$ until $\pi$ is enclosed and it is not |
2838 |
possible to generate additional enclosing terms whose denominator does not |
2839 |
exceed 10. This process is carried out below. |
2840 |
|
2841 |
\begin{equation} |
2842 |
\left\{ {\frac{0}{1}, \frac{1}{0} } \right\}, |
2843 |
\left\{ {\frac{0}{1}, \frac{1}{1}, \frac{1}{0} } \right\}, |
2844 |
\left\{ {\frac{0}{1}, \frac{1}{1}, \frac{2}{1}, \frac{1}{0} } \right\}, |
2845 |
\left\{ {\frac{0}{1}, \frac{1}{1}, \frac{2}{1}, \frac{3}{1}, \frac{1}{0} } \right\}, |
2846 |
\end{equation} |
2847 |
|
2848 |
\begin{equation} |
2849 |
\left\{ {\frac{0}{1}, \frac{1}{1}, \frac{2}{1}, \frac{3}{1}, |
2850 |
\frac{4}{1}, \frac{1}{0} } \right\}, |
2851 |
\left\{ {\frac{0}{1}, \frac{1}{1}, \frac{2}{1}, \frac{3}{1}, \frac{7}{2}, |
2852 |
\frac{4}{1}, \frac{1}{0} } \right\}, |
2853 |
\left\{ {\frac{0}{1}, \frac{1}{1}, \frac{2}{1}, \frac{3}{1}, \frac{10}{3}, \frac{7}{2}, |
2854 |
\frac{4}{1}, \frac{1}{0} } \right\}, |
2855 |
\end{equation} |
2856 |
|
2857 |
\begin{equation} |
2858 |
\left\{ {\frac{0}{1}, \frac{1}{1}, \frac{2}{1}, |
2859 |
\frac{3}{1}, \frac{13}{4}, \frac{10}{3}, \frac{7}{2}, |
2860 |
\frac{4}{1}, \frac{1}{0} } \right\}, |
2861 |
\left\{ {\frac{0}{1}, \frac{1}{1}, \frac{2}{1}, |
2862 |
\frac{3}{1}, \frac{16}{5}, \frac{13}{4}, \frac{10}{3}, \frac{7}{2}, |
2863 |
\frac{4}{1}, \frac{1}{0} } \right\}, |
2864 |
\end{equation} |
2865 |
|
2866 |
\begin{equation} |
2867 |
\left\{ {\frac{0}{1}, \frac{1}{1}, \frac{2}{1}, |
2868 |
\frac{3}{1}, \frac{19}{6}, \frac{16}{5}, \frac{13}{4}, \frac{10}{3}, \frac{7}{2}, |
2869 |
\frac{4}{1}, \frac{1}{0} } \right\}, |
2870 |
\end{equation} |
2871 |
|
2872 |
\begin{equation} |
2873 |
\left\{ {\frac{0}{1}, \frac{1}{1}, \frac{2}{1}, |
2874 |
\frac{3}{1}, \frac{22}{7}, \frac{19}{6}, |
2875 |
\frac{16}{5}, \frac{13}{4}, \frac{10}{3}, \frac{7}{2}, |
2876 |
\frac{4}{1}, \frac{1}{0} } \right\}, |
2877 |
\end{equation} |
2878 |
|
2879 |
\begin{equation} |
2880 |
\left\{ {\frac{0}{1}, \frac{1}{1}, \frac{2}{1}, |
2881 |
\frac{3}{1}, \frac{25}{8}, \frac{22}{7}, \frac{19}{6}, |
2882 |
\frac{16}{5}, \frac{13}{4}, \frac{10}{3}, \frac{7}{2}, |
2883 |
\frac{4}{1}, \frac{1}{0} } \right\}. |
2884 |
\end{equation} |
2885 |
|
2886 |
Note that 25/8 and 22/7 are the left and right neighbors to |
2887 |
$\pi$ in $F_{10}$, since $25/8 < \pi < 22/7$, and since the |
2888 |
mediant of 25/8 and 22/7 (49/15) has a denominator which is |
2889 |
too large for the Farey series being considered. |
2890 |
|
2891 |
Note also that the construction process above could be |
2892 |
trivially amended to treat the case of a constrained numerator |
2893 |
rather than a constrained denominator. |
2894 |
\end{vworkexampleparsection} |
2895 |
\vworkexamplefooter{} |
2896 |
|
2897 |
The Stern-Brocot tree has many remarkable properties (especially in view of the |
2898 |
simplicity of its construction). We mention the following properties |
2899 |
without proof. |
2900 |
|
2901 |
\begin{itemize} |
2902 |
\item Each rational number in the tree is irreducible. |
2903 |
|
2904 |
\item Each rational number appears in the tree only once. |
2905 |
|
2906 |
\item Every positive rational number appears in the tree (i.e. there are no rational |
2907 |
numbers absent). |
2908 |
\end{itemize} |
2909 |
|
2910 |
A more detailed discussion of the Stern-Brocot tree and proof of its |
2911 |
properties is provided |
2912 |
in \cite{bibref:b:concretemathematics}, pp. 116-123. |
2913 |
|
2914 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
2915 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
2916 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
2917 |
\subsection{The Correspondence Between The Stern-Brocot Tree And The |
2918 |
Apparatus Of Continued Fractions} |
2919 |
%Section tag: DPT0 |
2920 |
\label{ccfr0:ssbt0:sdpt1} |
2921 |
|
2922 |
The Stern-Brocot tree, on examination, bears a clear resemblence to |
2923 |
the apparatus of continued fractions. For example, in examining |
2924 |
Figure \ref{fig:ccfr0:ssbt0:sdpt0:00} and following leftmost branches in |
2925 |
the tree, the rational numbers 1/2, 1/3, 1/4, and 1/5 correspond respectively |
2926 |
to the continued fractions [0;2], [0;3], [0;4], and [0;5]. Similarly, |
2927 |
following |
2928 |
the right branches down from 1/2 yields, in order, [0;1,2], [0;1,3], and |
2929 |
[0;1,4]. Clearly, a relationship between the Stern-Brocot tree and the |
2930 |
apparatus of continued fractions may exist. |
2931 |
|
2932 |
Suspicions of a simple relationship may also arise by noting that the |
2933 |
way in which the Stern-Brocot tree is constructed when only left branches |
2934 |
or only right branches are pursued is of the same form as the rule for |
2935 |
the formation of continued fraction convergents (Eqns. |
2936 |
\ref{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:01} |
2937 |
and \ref{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:02}). For example, |
2938 |
the $n$th successor to the right of 1/3 has the form |
2939 |
|
2940 |
\begin{equation} |
2941 |
\label{eq:ccfr0:ssbt0:sdpt1:01} |
2942 |
\frac{n + 1}{2n+3}, |
2943 |
\end{equation} |
2944 |
|
2945 |
\noindent{}which is suspiciously similar to |
2946 |
(\ref{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:01}) and |
2947 |
(\ref{eq:thm:ccfr0:scnv0:canonicalconvergentconstruction:02}). |
2948 |
|
2949 |
There is, in fact, an intimate relationship between the Stern-Brocot |
2950 |
tree and the apparatus of continued fractions. We present |
2951 |
this relationship as |
2952 |
Lemma \ref{lem:ccfr0:ssbt0:sdpt1:sbtcfcorrespondence}, |
2953 |
below. |
2954 |
|
2955 |
\begin{vworklemmastatement} |
2956 |
\label{lem:ccfr0:ssbt0:sdpt1:sbtcfcorrespondence} |
2957 |
Let $R^{z_0}L^{z_1} \ldots{} L^{z_{j-2}} R^{z_{j-1}} L^{z_{j}}$ |
2958 |
or $R^{z_0}L^{z_1} \ldots{} R^{z_{j-2}} L^{z_{j-1}} R^{z_{j}}$ |
2959 |
(depending on whether the final leg of the path is towards the |
2960 |
left or towards the right, respectively) be the path in the |
2961 |
Stern-Brocot tree from the fraction 1/1 to the fraction $a/b$, where |
2962 |
$L^N$ denotes traveling downward and to the left in the tree |
2963 |
$N$ nodes, and $R^N$ denotes traveling downward and to the right |
2964 |
in the tree $N$ nodes. Then the continued fraction representation |
2965 |
of $a/b$ is $[z_0; z_1, \ldots{}, z_{j-2}, z_{j-1}, z_j + 1]$. |
2966 |
\end{vworklemmastatement} |
2967 |
\begin{vworklemmaproof} |
2968 |
The proof is inductive. First note that the constraints of the path |
2969 |
require that $z_0 \geq 0$, and that $z_k \geq 1$, $k > 0$. In other |
2970 |
words, only the first rightward leg of the path can have zero steps. |
2971 |
|
2972 |
If the path is $R^{z_0}$, $z_0 = 0$, then the lemma predicts that the continued fraction |
2973 |
representation will be $[z_0 + 1]$ = $[1]$, which is the correct continued |
2974 |
fraction representation of the fraction 1/1. Note that the rational number |
2975 |
1/1 has no ancestor in the tree. |
2976 |
|
2977 |
If the path is $R^{z_0}$, $z_0 \neq 0$, then the lemma predicts that the |
2978 |
continued fraction representation will be $[z_0 + 1]$, which is correct |
2979 |
on inspection since the most rightward path in the Stern-Brocot tree |
2980 |
traverses the non-negative integers. Note that the immediate ancestor of |
2981 |
the fraction $[z_0 + 1]$ is $[z_0]$. |
2982 |
|
2983 |
If the path is $R^{z_0}, L^{z_1}$, $z_0 = 0$, then the |
2984 |
fraction $a/b$ will be the weighted mediant of |
2985 |
1/1 and 0/1, |
2986 |
|
2987 |
\begin{equation} |
2988 |
\label{eq:ccfr0:ssbt0:sdpt1:02} |
2989 |
\frac{1}{z_1 + 1} |
2990 |
= |
2991 |
[0; z_1 + 1], |
2992 |
\end{equation} |
2993 |
|
2994 |
\noindent{}which argrees with the lemma. Note that the |
2995 |
immediate ancestor ancestor of $[0; z_1 + 1]$ in the |
2996 |
tree is $[0; z_1]$. |
2997 |
|
2998 |
If the path is $R^{z_0}, L^{z_1}$, $z_0 \neq 0$, then the |
2999 |
fraction $a/b$ will be the weighted mediant of |
3000 |
$(z_0 + 1)/1$ and $z_0/1$, i.e. |
3001 |
|
3002 |
\begin{equation} |
3003 |
\label{eq:ccfr0:ssbt0:sdpt1:03} |
3004 |
\frac{(z_0 + 1) + (z_0 z_1)}{(1) + (z_1)} |
3005 |
= z_0 + \frac{1}{z_1 + 1} |
3006 |
= [z_0; z_1 + 1], |
3007 |
\end{equation} |
3008 |
|
3009 |
\noindent{}which is consistent with the lemma. Note also that |
3010 |
the immediate ancestor of the rational number specified by |
3011 |
(\ref{eq:ccfr0:ssbt0:sdpt1:03}) is |
3012 |
|
3013 |
\begin{equation} |
3014 |
\label{eq:ccfr0:ssbt0:sdpt1:03b} |
3015 |
\frac{(z_0 + 1) + z_0 (z_1 - 1)}{(1) + (z_1 - 1)} |
3016 |
= z_0 + \frac{1}{z_1} |
3017 |
= [z_0; z_1]. |
3018 |
\end{equation} |
3019 |
|
3020 |
The cases with two or fewer path components have been |
3021 |
proved above. It remains to prove all cases with three |
3022 |
or more path components. |
3023 |
|
3024 |
Let $s_k = p_k/q_k$ denote the $k$th-ordered convergent |
3025 |
of the continued fraction $[z_0; z_1, \ldots{}, z_{j-1}, z_j]$ |
3026 |
(note that the final partial quotient is \emph{not} adjusted upwards by one). |
3027 |
For $k \geq 2$, we can establish a relationship between |
3028 |
$[z_0; z_1, \ldots{}, z_{k-1}, z_k]$ |
3029 |
and |
3030 |
$[z_0; z_1, \ldots{}, z_{k-1}, z_k + 1]$ |
3031 |
as follows: |
3032 |
|
3033 |
\begin{equation} |
3034 |
\label{eq:ccfr0:ssbt0:sdpt1:04} |
3035 |
[z_0; z_1, z_2, \ldots{}, z_{k-2}, z_{k-1}, z_k + 1] |
3036 |
= |
3037 |
\frac{(z_k + 1)p_{k-1} + p_{k-2}}{(z_k + 1)q_{k-1} + q_{k-2}} |
3038 |
= |
3039 |
\frac{p_k + p_{k-1}}{q_k + q_{k-1}}. |
3040 |
\end{equation} |
3041 |
|
3042 |
If we agree for convenience, as was mentioned in |
3043 |
Section \ref{ccfr0:scnf0}, that we will define $s_{-1} = p_{-1}/q_{-1} = 1/0$, |
3044 |
then (\ref{eq:ccfr0:ssbt0:sdpt1:04}) holds for $k \geq 1$. |
3045 |
|
3046 |
\textbf{(Inductive Step):} Assume that the lemma holds |
3047 |
up through $k-1$. For a path in the Stern-Brocot tree |
3048 |
$R^{z_0}L^{z_1} \ldots{} L^{z_{k-2}} R^{z_{k-1}} L^{z_{k}}$ |
3049 |
or $R^{z_0}L^{z_1} \ldots{} R^{z_{k-2}} L^{z_{k-1}} R^{z_{k}}$, |
3050 |
$k \geq 2$, the ``reversal'' fraction above (i.e. the fraction where the path changes |
3051 |
directions) is |
3052 |
|
3053 |
\begin{equation} |
3054 |
\label{eq:ccfr0:ssbt0:sdpt1:05} |
3055 |
[z_0; \ldots{}, z_{k-2}, z_{k-1} + 1] = |
3056 |
\frac{p_{k-1} + p_{k-2}}{q_{k-1} + q_{k-2}} |
3057 |
\end{equation} |
3058 |
|
3059 |
\noindent{}(this is established by the lemma on the path through $k-1$ and by |
3060 |
Eqn. \ref{eq:ccfr0:ssbt0:sdpt1:04}). |
3061 |
|
3062 |
The immediate ancestor of the fraction specified in |
3063 |
(\ref{eq:ccfr0:ssbt0:sdpt1:05}) is |
3064 |
|
3065 |
\begin{equation} |
3066 |
\label{eq:ccfr0:ssbt0:sdpt1:06} |
3067 |
[z_0; \ldots{}, z_{k-2}, z_{k-1}] = |
3068 |
\frac{z_{k-1}p_{k-2} + p_{k-3}}{z_{k-1}q_{k-2} + q_{k-3}} , |
3069 |
\end{equation} |
3070 |
|
3071 |
\noindent{}as was shown to hold in (\ref{eq:ccfr0:ssbt0:sdpt1:03b}) and |
3072 |
in the inductive step. |
3073 |
|
3074 |
The rational number corresponding to the path |
3075 |
$R^{z_0}L^{z_1} \ldots{} L^{z_{k-2}} R^{z_{k-1}} L^{z_{k}}$ |
3076 |
or $R^{z_0}L^{z_1} \ldots{} R^{z_{k-2}} L^{z_{k-1}} R^{z_{k}}$ |
3077 |
is a weighted mediant of (\ref{eq:ccfr0:ssbt0:sdpt1:05}) |
3078 |
and (\ref{eq:ccfr0:ssbt0:sdpt1:06}): |
3079 |
|
3080 |
\begin{eqnarray} |
3081 |
\label{eq:ccfr0:ssbt0:sdpt1:07} |
3082 |
\hspace{-0.35in} |
3083 |
\frac{z_k(z_{k-1}p_{k-2} + p_{k-3}) + p_{k-1} + p_{k-2}} |
3084 |
{z_k(z_{k-1}q_{k-2} + q_{k-3}) + q_{k-1} + q_{k-2}} |
3085 |
& = & |
3086 |
\frac{(z_k + 1)p_{k-1} + p_{k-2}}{(z_k + 1)q_{k-1} + q_{k-2}} \\ |
3087 |
\label{eq:ccfr0:ssbt0:sdpt1:08} |
3088 |
& = & \frac{p_k + p_{k-1}}{q_k + q_{k-1}} \\ |
3089 |
& = & [z_0; z_1, \ldots{}, z_{k-1}, z_{k} + 1], |
3090 |
\end{eqnarray} |
3091 |
|
3092 |
\noindent{}which establishes the main result of the lemma in the |
3093 |
inductive step. Note also that the immediate ancestor of the |
3094 |
fraction specified in (\ref{eq:ccfr0:ssbt0:sdpt1:07}) is |
3095 |
$[z_0; \ldots{}, z_{k-1}, z_{k}]$ (which is necessary for |
3096 |
the inductive step). This proves the lemma. |
3097 |
\end{vworklemmaproof} |
3098 |
\begin{vworklemmaparsection}{Remarks} |
3099 |
This lemma provides a straightforward method to go from a |
3100 |
fraction's position in the Stern-Brocot tree to its continued |
3101 |
fraction representation, or vice-versa. |
3102 |
|
3103 |
To go from a fraction's position in the Stern-Brocot tree to its |
3104 |
continued fraction representation: |
3105 |
|
3106 |
\begin{itemize} |
3107 |
\item Starting with moves downward and to the right from the |
3108 |
fraction 1/1 ($z_0$), observe the length of the alternating |
3109 |
rightward and leftward node traversals required to reach |
3110 |
the desired fraction. |
3111 |
|
3112 |
\item Adjust the final length upward by one. |
3113 |
|
3114 |
\item These lengths in order are then the successive partial quotients |
3115 |
of the fraction. |
3116 |
\end{itemize} |
3117 |
|
3118 |
To go from the continued fraction representation of a fraction |
3119 |
to its position in the Stern-Brocot tree: |
3120 |
|
3121 |
\begin{itemize} |
3122 |
\item Reduce the final partial quotient by one. |
3123 |
|
3124 |
\item Use the partial quotients, in order, in an alternating fashion, |
3125 |
to go rightward and downward |
3126 |
and leftward and downward in the Stern-Brocot tree. The fraction |
3127 |
reached on the final leg will be the fraction of interest. |
3128 |
\end{itemize} |
3129 |
\end{vworklemmaparsection} |
3130 |
\vworklemmafooter{} |
3131 |
|
3132 |
It is clear from the lemma above that the Stern-Brocot tree and the |
3133 |
apparatus of continued fractions are intimately related. Specifically, |
3134 |
the Stern-Brocot tree provides a model for the formation and arrangement |
3135 |
of rational numbers, but the apparatus of continued fractions provides |
3136 |
a much more efficient way to navigate the Stern-Brocot tree and to find |
3137 |
best rational approximations. |
3138 |
|
3139 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
3140 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
3141 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
3142 |
\subsection{Using The Stern-Brocot Tree To Find Best Rational Approximations} |
3143 |
%Section tag: USB0 |
3144 |
\label{ccfr0:ssbt0:susb0} |
3145 |
|
3146 |
It is clear from Example \ref{ex:ccfr0:ssbt0:sdpt0:01} that the Stern-Brocot |
3147 |
tree can be used to find best rational approximations in the Farey series |
3148 |
of any order, simply by forming mediants until the number of interest |
3149 |
is enclosed. It is also clear that an algorithm of repeatedly forming |
3150 |
mediants in order to find a best rational approximation in |
3151 |
$F_{k_{MAX}, \overline{h_{MAX}}}$ can be devised. |
3152 |
|
3153 |
However, the sole drawback of such a procedure is that building the Stern-Brocot |
3154 |
tree from the top in order to find neighbors in $F_N$ is an |
3155 |
$O(N)$ procedure, which renders it unsuitable for use with large |
3156 |
$N$. For this reason, the continued fraction algorithms presented |
3157 |
earlier in the chapter, which are $O(log \; N)$ (due to the |
3158 |
guaranteed minimum exponential rate of increase of convergent |
3159 |
denominators, Theorem \ref{thm:ccfr0:scnv0:minimumrateofconvergentdenominatorincrease}), |
3160 |
are the only practical algorithms. |
3161 |
|
3162 |
|
3163 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
3164 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
3165 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
3166 |
\section{Practical Techniques} |
3167 |
%Section tag: PTQ0 |
3168 |
|
3169 |
Although this chapter has presented rather theoretical results and techniques |
3170 |
from number theory, our emphasis is on practical applications (which is why |
3171 |
we've concentrated on finding Farey neighbors of \emph{rational} numbers). |
3172 |
Practicing engineers would be more likely to use the digits from a calculator |
3173 |
as the starting point to obtain a rational approximation than to use |
3174 |
a symbolic irrational constant, such as $\pi$. |
3175 |
|
3176 |
In this section, we present \emph{practical} techniques---those most likely |
3177 |
to be used in practice by microcontroller software developers. |
3178 |
|
3179 |
|
3180 |
|
3181 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
3182 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
3183 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
3184 |
\subsection{Practical Aspects Of Beginning With A Rational Approximation} |
3185 |
%Subsection tag: PAS0 |
3186 |
\label{ccfr0:sptq0:sspas0} |
3187 |
|
3188 |
In practical applications, one often begins with a rational approximation |
3189 |
to a irrational number. |
3190 |
For example, one might use 3.14159265359 (from |
3191 |
a calculator) as the value of $\pi$ for the application of |
3192 |
Algorithm \ref{alg:ccfr0:scrn0:akgenalg}. This naturally raises the |
3193 |
question of how accurate the rational approximation used |
3194 |
as a starting point must be to avoid identifying the wrong |
3195 |
rational numbers as Farey neighbors. We illustrate the possibility |
3196 |
of identifying the wrong rational number with an example. |
3197 |
|
3198 |
\begin{vworkexamplestatement} |
3199 |
\label{ex:ccfr0:sptq0:01} |
3200 |
Find the members of $F_{255}$ which enclose $\pi$, using |
3201 |
3.1416 as the value of $\pi$. |
3202 |
\end{vworkexamplestatement} |
3203 |
\begin{vworkexampleparsection}{[Erroneous] Solution And Remarks} |
3204 |
It can be shown using the methods presented earlier that |
3205 |
the members of $F_{255}$ which enclose 3.1416 are |
3206 |
355/113 and 732/333, i.e. |
3207 |
|
3208 |
\begin{equation} |
3209 |
\frac{355}{113} < 3.1416 < \frac{732}{333} . |
3210 |
\end{equation} |
3211 |
|
3212 |
However, in fact, 688/219 and 355/113 are the actual enclosing |
3213 |
neighbors of $\pi$ in $F_{255}$: |
3214 |
|
3215 |
\begin{equation} |
3216 |
\frac{688}{219} < \pi < \frac{355}{113} < 3.1416 < \frac{732}{333} . |
3217 |
\end{equation} |
3218 |
|
3219 |
Thus by using an imprecise approximation of $\pi$, we have incorrectly |
3220 |
identified the neighbors to $\pi$ in $F_{255}$. |
3221 |
\end{vworkexampleparsection} |
3222 |
\vworkexamplefooter{} |
3223 |
|
3224 |
How do we avoid incorrectly identifying the rational |
3225 |
numbers which enclose an irrational number when a |
3226 |
rational approximation of the irrational number is |
3227 |
used as the starting point for the selection algorithm? |
3228 |
There are three practical approaches to the problem. |
3229 |
|
3230 |
Observe that when we know |
3231 |
the first several decimal digits of an irrational number, |
3232 |
the actual value of the irrational number is confined |
3233 |
to an interval. For example, if a calculator displays |
3234 |
``3.1416'' as the value of $\pi$, we might safely |
3235 |
assume that $3.14155 \leq \pi \leq 3.14165$, if the |
3236 |
digits that the calculator displays were |
3237 |
obtained by rounding. |
3238 |
|
3239 |
As a first approach to dealing with a rational approximation |
3240 |
to an irrational number, |
3241 |
we might simply determine the |
3242 |
Farey neighbors of both endpoints of the interval of |
3243 |
uncertainty. For example, if |
3244 |
314,155/100,000 and 314,165/100,000 have the same |
3245 |
Farey neighbors in a Farey series of interest (which we can |
3246 |
easily determine using the algorithms presented earlier |
3247 |
in this chapter), we could |
3248 |
correctly deduce that these Farey neighbors are the |
3249 |
Farey neighbors of $\pi$. On the other hand, |
3250 |
if 314,155/100,000 and 314,165/100,000 have different |
3251 |
enclosing Farey neighbors, then there are Farey |
3252 |
terms in the interval [3.14155, 3.14165], |
3253 |
and more information about $\pi$ |
3254 |
would be required to determine its true Farey neighbors. |
3255 |
|
3256 |
A second approach to this same problem would be to devise an |
3257 |
algorithm to process |
3258 |
the endpoints of the interval of uncertainty simultaneously and note |
3259 |
when their partial quotients diverge. |
3260 |
|
3261 |
A third approach, which is |
3262 |
perhaps the most direct, is to apply |
3263 |
Algorithm \cfryzeroxrefhyphen{}\ref{alg:cfmindenominator} to determine |
3264 |
the rational number with the minimum denominator in the interval of uncertainty. |
3265 |
We would thus know that we have enough information to determine uniquely the |
3266 |
enclosing rational numbers in any Farey series up to one less than this |
3267 |
minimum denominator. |
3268 |
|
3269 |
\begin{vworkexamplestatement} |
3270 |
\label{ex:ccfr0:sptq0:02} |
3271 |
Assume that 3.142 is the only value for $\pi$ available. What is the maximum |
3272 |
order of the Farey series where the enclosing rational numbers to $\pi$ can |
3273 |
be unambiguously determined? |
3274 |
\end{vworkexamplestatement} |
3275 |
\begin{vworkexampleparsection}{Solution} |
3276 |
Assume that the constant ``3.142'' was obtained by rounding of digits, rather than |
3277 |
by truncation of digits: thus $3.1415 \leq \pi \leq 3.1425$. Applying |
3278 |
Algorithm \cfryzeroxrefhyphen{}\ref{alg:cfmindenominator} yields 333/106 |
3279 |
as the rational number with the smallest denominator in the interval |
3280 |
[3.1415, 3.1425]. Thus, no rational number with a smaller denominator exists |
3281 |
in the interval, and the enclosing rational numbers of $\pi$ in the Farey series of |
3282 |
up to order 105 can be determined with the limited information available. |
3283 |
\end{vworkexampleparsection} |
3284 |
\vworkexamplefooter{} |
3285 |
|
3286 |
|
3287 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
3288 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
3289 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
3290 |
\subsection{Obtaining Irrational Numbers To High Precision} |
3291 |
%Subsection tag: OIN0 |
3292 |
\label{ccfr0:sptq0:ssoin0} |
3293 |
|
3294 |
It may happen in practice that one desires more information about an |
3295 |
irrational number than can be easily obtained. As a practical example, |
3296 |
a typical scientific calculator treats $\pi$ as 3.14159265359, implying that |
3297 |
$3.141592653585 \leq \pi \leq 3.141592653595$. Application of |
3298 |
Algorithm \cfryzeroxrefhyphen{}\ref{alg:cfmindenominator} to this |
3299 |
interval yields 1,146,408/364,913 as the rational number with the |
3300 |
smallest denominator in this interval: implying that we cannot determine the |
3301 |
enclosing rational approximations to $\pi$ even in $F_{2^{32}-1}$ using |
3302 |
the information most readily available. How do we obtain more digits of $\pi$? |
3303 |
And even if we can obtain more digits of $\pi$, how do we manipulate rational |
3304 |
numbers with such large integer components? (We discuss the problem of obtaining |
3305 |
more digits below, but discuss manipulation in Section \ref{ccfr0:sptq0:smhp0}.) |
3306 |
|
3307 |
There are two approaches to determining $\pi$ or other numbers to |
3308 |
high precision. |
3309 |
|
3310 |
\begin{enumerate} |
3311 |
|
3312 |
\item Locate information about the number on the Web or in a reference |
3313 |
book. (Note that decimal digits of the number, partial quotients |
3314 |
of the number, or convergents of the number can all be used; and it |
3315 |
is typical for all of these to be somewhere on the Web. However, |
3316 |
convergents are the most useful form for obtaining best rational |
3317 |
approximations.) |
3318 |
|
3319 |
\item Use commercial symbolic manipulation software (\index{Mathematica@\emph{Mathematica}}\emph{Mathematica} |
3320 |
\cite{bibref:s:wolframmathematica}, |
3321 |
for example) to |
3322 |
obtain the number of interest to arbitrary |
3323 |
precison.\footnote{\label{footnote:ccfr0:sptq0:ssoin0:mathematicaexpensive}\emph{Mathematica} |
3324 |
\cite{bibref:s:wolframmathematica} is quite expensive (version 4.1 |
3325 |
for Windows, as of March 2001, is \$1,495), |
3326 |
and something that a microcontroller software developer |
3327 |
would very rarely use, so we assume that most microcontroller software |
3328 |
developers would search for a less expensive solution.} |
3329 |
|
3330 |
\end{enumerate} |
3331 |
|
3332 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
3333 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
3334 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
3335 |
\subsection{Manipulating High-Precision Rational Numbers} |
3336 |
%Subsection tag: MHP0 |
3337 |
\label{ccfr0:sptq0:smhp0} |
3338 |
|
3339 |
Assuming that one is able to determine a [rational or irrational] number |
3340 |
of interest to high-precision (either a large number of decimal digits or a rational |
3341 |
number with large integer components), how does |
3342 |
one manipulate rational numbers with large integer components? |
3343 |
In this section, we list software alternatives. |
3344 |
|
3345 |
The first alternative we should mention is \emph{The Iju Tool Set}, distributed |
3346 |
with this book. Starting with version 1.05, this tool set contains |
3347 |
a subset of the GNU MP Library \cite{bibref:s:gnumultipleprecisionarithmeticlibrary}, |
3348 |
and will manipulate |
3349 |
large integers and rational numbers with large integer components. To provide |
3350 |
more flexibility for the user, this tool set is embedded as extensions to |
3351 |
the Tcl scripting language; so that any of the functionality provided can be |
3352 |
used either interactively or from within a Tcl script. |
3353 |
|
3354 |
\begin{figure} |
3355 |
\centering |
3356 |
\includegraphics[width=4.6in]{c_cfr0/ijt_ss01.eps} |
3357 |
\caption{Large Integer Arithmetic And Best Rational Approximations Using \emph{IjuConsole} |
3358 |
From \emph{The Iju Tool Set}} |
3359 |
\label{fig:ccfr0:sptq0:smhp0:00} |
3360 |
\end{figure} |
3361 |
|
3362 |
Figure \ref{fig:ccfr0:sptq0:smhp0:00} shows a screen snapshot\footnote{By |
3363 |
the way, \emph{IjuConsole} will handle \emph{much} larger integers, but |
3364 |
small examples were used so that all of the information would fit |
3365 |
in a single screen snapshot.} of |
3366 |
\emph{IjuConsole} (the \emph{Wish}-like Tcl |
3367 |
interpreter from \emph{The Iju Tool Set}) being used interactively |
3368 |
to provide the answers to several questions involving large integers and |
3369 |
rational numbers with large integer components. The first command |
3370 |
shown,\\ |
3371 |
|
3372 |
\texttt{arbint intmul 218643832695416243621 13254215384521848},\\ |
3373 |
|
3374 |
\noindent{}illustrates integer multiplication. The second command shown,\\ |
3375 |
|
3376 |
\texttt{arbint intfac 55},\\ |
3377 |
|
3378 |
\noindent{}illustrates calculating the factorial of |
3379 |
55. The third command shown, \\ |
3380 |
|
3381 |
\texttt{arbint cfbrapab [arbint const pi 500] 65535 65535},\\ |
3382 |
|
3383 |
\noindent{}illustrates calculating the best rational approximation to |
3384 |
$\pi$ with numerator and denominator not exceeding |
3385 |
65,535, and using the first 500 digits of $\pi$ as |
3386 |
the value of $\pi$. The fourth command shown,\\ |
3387 |
|
3388 |
\texttt{arbint cfbrapab 1.609344 1023 1023},\\ |
3389 |
|
3390 |
\noindent{}illustrates finding the best rational approximation to |
3391 |
the conversion factor from MPH to KPH with numerator and denominator |
3392 |
not exceeding 1,023. The last command shown,\\ |
3393 |
|
3394 |
\texttt{arbint rnadd 78/2976 342/2763},\\ |
3395 |
|
3396 |
\noindent{}illustrates the addition of |
3397 |
two rational numbers. |
3398 |
|
3399 |
Many other potential solutions for dealing with large |
3400 |
integers have been submitted by newsgroup |
3401 |
posters, and are listed below. (Please note that these alternatives haven't actually been |
3402 |
tried, and we can't say whether they are viable.) |
3403 |
|
3404 |
\begin{enumerate} |
3405 |
|
3406 |
\item \index{Mathematica@\emph{Mathematica}}\emph{Mathematica} |
3407 |
\cite{bibref:s:wolframmathematica} (by Wolfram Research) will easily operate on large integers and |
3408 |
rational numbers with large integer components (see |
3409 |
Footnote \ref{footnote:ccfr0:sptq0:ssoin0:mathematicaexpensive}). |
3410 |
(Suggested by \index{Lutus, Paul} Paul Lutus \cite{bibref:i:paullutus} and |
3411 |
\index{Taylor, Don} Don Taylor \cite{bibref:i:dontaylor}.) |
3412 |
|
3413 |
\item \index{GNU!Multiple Precision Arithmetic Library (GMP)}The |
3414 |
\emph{GNU Multiple Precision Arithmetic |
3415 |
Library (GMP)} \cite{bibref:s:gnumultipleprecisionarithmeticlibrary}. |
3416 |
This library, which is free and on the Web, can be linked into |
3417 |
`C' and `C++' programs, and allows fast integer calculations of |
3418 |
any size that do not exceed the memory available in the computer. |
3419 |
This library could be used to quickly construct a program to |
3420 |
process rational numbers with very large integer components. |
3421 |
|
3422 |
\item \index{UBASIC@\emph{UBASIC}}\emph{UBASIC} \cite{bibref:s:ubasic} |
3423 |
(\index{Kida, Yuji}by Yuji Kida \cite{bibref:i:yujikida}) |
3424 |
is an extended-precision version of the BASIC |
3425 |
language which will handle integers up to 2,600 digits and |
3426 |
exact rational arithmetic. (Suggested by \index{Schorn, Richard} Richard Schorn |
3427 |
\cite{bibref:i:richardschorn}.) |
3428 |
|
3429 |
\item \index{Derive 5@\emph{Derive 5}}\emph{Derive 5} \cite{bibref:s:derive5} (by Texas Instruments). |
3430 |
The exact capabilities of this software are not known, but the Web page indicates |
3431 |
it can perform exact rational arithmetic. (Suggested by \index{Schorn, Richard} Richard Schorn |
3432 |
\cite{bibref:i:richardschorn} and \index{Taylor, Don} Don Taylor \cite{bibref:i:dontaylor}.) |
3433 |
|
3434 |
\item \index{Maple@\emph{Maple}}\emph{Maple} \cite{bibref:s:maple} (by Waterloo |
3435 |
Maple, Inc.). The exact capabilities of this software are not known. |
3436 |
(Suggested by |
3437 |
\index{Lutus, Paul} Paul Lutus \cite{bibref:i:paullutus} and |
3438 |
\index{Taylor, Don} Don Taylor \cite{bibref:i:dontaylor}.) |
3439 |
|
3440 |
\item \index{MuPAD@\emph{MuPAD}}\emph{MuPAD} \cite{bibref:s:mupad} (from |
3441 |
the University Of Paderborn, Germany). The capabilities of this |
3442 |
software are not known. (Suggested by \index{Schorn, Richard} Richard Schorn |
3443 |
\cite{bibref:i:richardschorn}.) |
3444 |
|
3445 |
\end{enumerate} |
3446 |
|
3447 |
%http://www.csc.fi/math_topics/Mail/FAQ/msg00015.html |
3448 |
|
3449 |
In addition to the large integer resources above, a |
3450 |
much longer list of resources is maintained |
3451 |
at the URL |
3452 |
|
3453 |
\begin{quote} |
3454 |
\texttt{http://www.csc.fi/math\_topics/Mail/FAQ/msg00015.html}, |
3455 |
\end{quote} |
3456 |
|
3457 |
\noindent{}and is reproduced below. Because this URL was apparently last updated |
3458 |
in 1994, it is not known which of the resources listed are still |
3459 |
available. |
3460 |
|
3461 |
\begin{quote} |
3462 |
\begin{scriptsize} |
3463 |
\begin{verbatim} |
3464 |
-------------------------------------------------------------------------------- |
3465 |
Subject: List of Arbitrary Precision C packages |
3466 |
From: mrr@scss3.cl.msu.edu (Mark Riordan) |
3467 |
Date: 27 Jan 1994 16:06:01 GMT |
3468 |
Newsgroups: sci.math |
3469 |
-------------------------------------------------------------------------------- |
3470 |
This is the file BIGNUMS.TXT from ripem.msu.edu, last updated January 1994. |
3471 |
|
3472 |
In response to Email requests, I have assembled this list of |
3473 |
large-integer arithmetic packages of which I have heard. |
3474 |
Most of these are C function libraries, available in source form. |
3475 |
A few also deal with floating point numbers. |
3476 |
|
3477 |
For your convenience, I have placed copies of |
3478 |
some of these on ripem.msu.edu (35.8.1.178). They are |
3479 |
available for anonymous FTP in the directory "pub/bignum". |
3480 |
However, what I have may not be the most current version in all cases. |
3481 |
|
3482 |
Here they are, in no particular order: |
3483 |
|
3484 |
mp |
3485 |
Multiple Precision package that comes with some Unixes |
3486 |
|
3487 |
Multiple precision package accessed via -lmp flag on your |
3488 |
compiler. Provides +, -, *, /, gcd, exponentiation, |
3489 |
sqrt. Comes with SunOS, NeXT Mach, BBN Mach 1000, |
3490 |
and probably a few others. See "man 3 mp". |
3491 |
Object code only, of course. |
3492 |
|
3493 |
PARI |
3494 |
Henri Cohen, et al., Universite Bordeaux I, Paris, FRANCE |
3495 |
|
3496 |
Multiple precision desk calculator and library routines. |
3497 |
Contains optimized assembly code for Motorola 68020, |
3498 |
semi-optimized code for SPARC, and apparently rather slow |
3499 |
generic C version. Does both integers and reals. |
3500 |
Does vectors and matrices as well as scalars. |
3501 |
Contains a number of advanced functions, some of which I've |
3502 |
never heard of. ("Weber's function"?) |
3503 |
Has a factorization function, primality test, & other related stuff. |
3504 |
Plenty of TEX documentation. |
3505 |
Public domain, but you can't distribute modified versions. |
3506 |
Available via anonymous FTP from ftp.inria.fr:lang/ and |
3507 |
math.ucla.edu. The ucla site has Mac, MSDOS, OS/2, and |
3508 |
NeXT-specific versions there in addition to: |
3509 |
Filename: pari-1.37.tar.Z (There are now more recent versions) |
3510 |
|
3511 |
Arithmetic in Global Fields (Arith) |
3512 |
Kevin R. Coombes, David R. Grant |
3513 |
|
3514 |
Package of routines for arbitrary precision integers or |
3515 |
polynomials over finite fields. Includes basic +, -, *, / |
3516 |
and a few others like gcd. Source code in C. |
3517 |
Distributed under the terms of the GNU public license. |
3518 |
Includes man pages and TEX documentation. |
3519 |
Filename: arith.tar.Z |
3520 |
|
3521 |
Arbitrary Precision Math Library |
3522 |
Lloyd Zusman Los Gatos, CA |
3523 |
|
3524 |
C package which supports basic +, -, *, /. Provides for radix |
3525 |
points (i.e., non-integers). Not as polished as the others here. |
3526 |
Posted to comp.sources.misc in October 1988. |
3527 |
Filename: apml.tar.Z |
3528 |
|
3529 |
BigNum |
3530 |
J. Vuillemin, INRIA, FRANCE, and others. |
3531 |
Distributed by Digital Equipment Paris Research Lab (DECPRL) |
3532 |
|
3533 |
A "portable and efficient arbitrary-precision integer" package. |
3534 |
C code, with generic C "kernel", plus assembly "kernels" for |
3535 |
MC680x0, Intel i960, MIPS, NS32032, Pyramid, and of course VAX. |
3536 |
This is probably one of the better-known packages of this type. |
3537 |
Implements +, -, *, /, mod, plus logical operations OR, AND, XOR. |
3538 |
Both signed and unsigned arithmetic available. |
3539 |
Available via email from librarian@decprl.dec.com. |
3540 |
You will receive 5 shell archives. Give your postal address |
3541 |
and you will also receive printed documentation from France. |
3542 |
Package includes TEX documentation. |
3543 |
Publicly available for non-commercial use. |
3544 |
I removed this from my archive when I heard a rumor that PRL |
3545 |
doesn't like others to distribute it. However, BIGNUM *is* |
3546 |
distributed as part of ecpp (see below). |
3547 |
|
3548 |
Lenstra's LIP package |
3549 |
Arjen Lenstra Bellcore |
3550 |
|
3551 |
Portable unsigned integer package written entirely in C. |
3552 |
Includes +, -, *, /, exponentiation, mod, primality testing, |
3553 |
sqrt, random number generator, and a few others. |
3554 |
An earlier version of this package is the only of these packages |
3555 |
I have actually used. It works well and is very portable. |
3556 |
I haven't done any benchmarks against the others, but the code |
3557 |
looks clever & Lenstra is an accomplished number theorist. |
3558 |
|
3559 |
LIP replaces lenstra-3.1.c. The package now includes encrypted |
3560 |
source code; to obtain the decryption key, you must send a |
3561 |
signed license agreement to Bellcore. See the documentation. |
3562 |
Filename: lenstra-LIP-package.tar This is a collection of |
3563 |
all the files in flash.bellcore.com:/pub/lenstra |
3564 |
|
3565 |
bmp (Brent's Multiple Precision?) |
3566 |
R. P. Brent |
3567 |
|
3568 |
1981 vintage FORTRAN code to do extended precision floating & |
3569 |
fixed point arithmetic. Includes most of the mathematical |
3570 |
functions you'd find in a FORTRAN run-time library. |
3571 |
This code is an ACM algorithm, number 524. |
3572 |
To obtain, send a mail message to netlib@ornl.gov |
3573 |
containing the line "send mp.f from bmp" or better yet, perhaps |
3574 |
just start with "help". |
3575 |
|
3576 |
SPX |
3577 |
Kannan Alagappan & Joseph Tardo, DEC |
3578 |
|
3579 |
This is a huge prototype public key authentication system |
3580 |
based on RSA. I mention it here because those who have heard |
3581 |
of SPX have probably correctly guessed that it contains a large |
3582 |
integer package and I want to inform you that the large integer |
3583 |
package it contains is indeed DEC's BigNum from France. |
3584 |
You can get a beta test copy of SPX from crl.dec.com (192.58.206.2). |
3585 |
Use it only for testing, as it "may" expire on a certain date. |
3586 |
(I don't know whether this has expired yet.) |
3587 |
|
3588 |
amp (Antti's Multiple Precision?) |
3589 |
Antti Louko alo@kampi.hut.fi |
3590 |
|
3591 |
Multiple precision integer package in C. Includes +, -, *, /, %, |
3592 |
pow, mod, 1/x mod y, random, sqrt, gcd. Available for non-commercial |
3593 |
use. The package includes "share-secret", a public key system based |
3594 |
on the Diffie-Hellman algorithm. |
3595 |
This is normally part of the well-known "des-dist.tar.Z", |
3596 |
but I have removed the DES part to avoid having to deal with |
3597 |
cryptographic export laws, and have named the result: |
3598 |
Filename: amp.tar.Z |
3599 |
|
3600 |
gennum |
3601 |
Per Bothner U of Wisconsin-Madison |
3602 |
|
3603 |
C++ routines and classes to do generic arithmetic, both |
3604 |
integer and rational. Part of the "Q" programming system. |
3605 |
Distributed under the terms of the GNU public license. |
3606 |
Obtained from cygnus.com. |
3607 |
Filename: gennum.tar.Z |
3608 |
|
3609 |
MIRACL |
3610 |
(Shamus Software, Dublin, Ireland) |
3611 |
|
3612 |
Integer and fractional multiple precision package. |
3613 |
MIRACL is a portable C library. Full C/C++ source code included |
3614 |
(In-line assembly support for 80x86). Number theoretic primitives |
3615 |
needed to support PK Cryptography are supplied. |
3616 |
C++ classes for Multiprecision Integers, Modular arithmetic, and |
3617 |
Chinese Remainder Thereom. Implementation in C/C++ of all modern |
3618 |
methods of Integer Factorisation, viz Brent-pollard, p-1, p+1, |
3619 |
Elliptic Curve, MPQS. Includes TEX manual and some DOS .EXEs. |
3620 |
Not public domain, but free for academic and non-commercial use. |
3621 |
Obtained from ftp.compapp.dcu.ie. |
3622 |
Filename: /pub/crypt/other/miracl-3.23.zip and miracl.tar.Z (older) |
3623 |
|
3624 |
precision |
3625 |
Dave Barrett barrettd@tigger.colorado.edu |
3626 |
|
3627 |
Multiple precision integer package in C with +,-,*,/, sqrt, rand, |
3628 |
mod, pow, log. Simple vector support. Does dynamic allocation of memory. |
3629 |
Free as long as you don't sell it or any program that uses it. |
3630 |
Filename: precision.tar.Z |
3631 |
|
3632 |
UBASIC |
3633 |
Prof. Yuji Kida, Rikkyo University, Nishi-Ikebukuro 3, Tokyo 171, Japan |
3634 |
kida@rkmath.rikkyo.ac.jp |
3635 |
|
3636 |
Multiple-precision version of the BASIC programming language, |
3637 |
for MS-DOS. Includes floating point. Said (by Keith Briggs) |
3638 |
to be pretty fast. Object only, I think. ervin@morekypr.bitnet |
3639 |
says: "This is the best package that I know of for |
3640 |
fast arithmetic. Has a version optimized for 386 machines. Includes |
3641 |
routines to do MPQS, the fastest currently known general factoring |
3642 |
algorithm. An additional file is at both sites to allow MPQS to use |
3643 |
hard drives so that it can factor up to 80 digits. Many number |
3644 |
theoretical functions are included in UBASIC. It allows over 2500 |
3645 |
digits of precision." |
3646 |
Available via anonymous FTP from shape.mps.ohio-state.edu, |
3647 |
or simtel20.army.mil, or wuarchive.wustl.edu. |
3648 |
|
3649 |
calc_v22 |
3650 |
Unknown |
3651 |
|
3652 |
MS-DOS C-like language that allows "infinite" precision. |
3653 |
Nice intrinsic functions. ervin@morekypr.bitnet reports problems |
3654 |
when changing precision on the fly. |
3655 |
See simtel20 or wuarchive. |
3656 |
|
3657 |
briggs_arith |
3658 |
Keith Briggs (kbriggs@maths.adelaide.edu.au) |
3659 |
|
3660 |
Turbo Pascal 5 source for routines that do multiple-precision |
3661 |
+, -, *, /, sqrt, gcd, factoring, rand for integers; also includes |
3662 |
+, -, *, / and rand for rational numbers. |
3663 |
Filename: briggs_arith.pas |
3664 |
|
3665 |
Institute fur Experimentelle Mathematik |
3666 |
Dr Gerhard Schneider (?) |
3667 |
|
3668 |
Fast C multiple-precision subroutine library. |
3669 |
I don't know anything about it; sl25@ely.cl.cam.ac.uk says |
3670 |
to contact MAT420@DE0HRZ1A.BITNET for more info. |
3671 |
Postal Address: |
3672 |
Institute fur Experimentelle Mathematik |
3673 |
EllernStr 29 |
3674 |
D4300 Essen-12 GERMANY |
3675 |
|
3676 |
LongInt |
3677 |
Markus Mueller (mueller@komsys.tik.ethz.ch) |
3678 |
|
3679 |
"Multi precision arithmetic written in MODULA-2, with the most time critical |
3680 |
parts written in Assembler. Includes basic arithmetics (+, -, *, /, %) as |
3681 |
well as arithmetics MODULO a number. An additional module provides a |
3682 |
collection of procedures for primality testing, gcd, multiplicative |
3683 |
inverse and more. The package is part of a Privacy Enhanced Mail (PEM) |
3684 |
package which includes a PEM mailer, RSA key generator and Certificate |
3685 |
generation tools." |
3686 |
|
3687 |
Source is in Modula-2, C, and assembler for Sun 3. LongInt has |
3688 |
also been ported to MS-DOS under Logitech Modula-2 and Turbo |
3689 |
Assembler. Availability: free for university use (research and |
3690 |
education); otherwise, a source license is required. To obtain, |
3691 |
write or email to: |
3692 |
|
3693 |
Markus Mueller |
3694 |
Bertastrasse 7 |
3695 |
CH-8953 Dietikon |
3696 |
Switzerland |
3697 |
email: mueller@komsys.tik.ethz.ch |
3698 |
|
3699 |
bignum-1.2 |
3700 |
Henrik.Johansson@Nexus.Comm.SE |
3701 |
|
3702 |
Bignum package written in portable C. Will in the future |
3703 |
conform to the Common Lisp functions that handles integers. |
3704 |
Currently includes +, -, *, /, exponentiation, "exptmod", |
3705 |
comparison, random numbers, and gcd. |
3706 |
Filename: bignum-1.2 |
3707 |
|
3708 |
ACM algorithm 567 |
3709 |
D.W. LOZIER and J.M. SMITH |
3710 |
|
3711 |
FORTRAN subroutines to do extended-precision floating point |
3712 |
and normalized Legendre polynomials. |
3713 |
ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE 7,1 (MARCH, 1981) |
3714 |
Obtained from research.att.com:netlib/toms/567.Z |
3715 |
Filename: acm-algorithm-567-floating-point.fortran.Z |
3716 |
|
3717 |
range |
3718 |
O. Aberth and M. J. Schaefer |
3719 |
|
3720 |
C++ package to do extended-precision floating point arithmetic |
3721 |
with programmer-defined precision. Uses decimal representations |
3722 |
internally. Contains basic +, -, *, /, relational operators, |
3723 |
++, and a few functions like sin, cos, sqrt, log. Documentation |
3724 |
a trifle confusing. |
3725 |
Obtained from math.tamu.edu:pub/range/range.tar.Z |
3726 |
Filename: range.tar.Z |
3727 |
|
3728 |
bsint |
3729 |
Author unknown. |
3730 |
|
3731 |
Pre-alpha release of C++ big integer package. |
3732 |
Implements basic math operators, exponentiation, and modular |
3733 |
exponentiation. Very skimpy documentation. |
3734 |
See milton.u.washington.edu:/pub/user-supported/tzs/bsint.tar.Z |
3735 |
|
3736 |
GNU Multiple Precision (GMP) |
3737 |
GNU (Free Software Foundation) multiple precision package. |
3738 |
I haven't looked at it yet. This is current as of April 1992, |
3739 |
but there may be a more recent version by the time you read |
3740 |
this. This package is very widely available on FTP sites. |
3741 |
Filename: gmp-1.3.2.tar.Z |
3742 |
|
3743 |
libg++ - GNU's C++ class library |
3744 |
Free Software Foundation |
3745 |
|
3746 |
Includes Integer and Rational classes. Integer provides |
3747 |
the usual C++ operators, plus exponentiation, gcd, lcm. |
3748 |
Limited functionality, but documentation is better than most. |
3749 |
Look for libg++-2.4.tar.gz on an FTP server near you. |
3750 |
|
3751 |
Elliptic Curve Primality Proving |
3752 |
Francois Morain, France. |
3753 |
|
3754 |
Large package to prove the primality of any prime. |
3755 |
Includes Inria's BIGNUM package. |
3756 |
Obtained from ftp.inria.fr (128.93.1.26). |
3757 |
Filename: ecpp.V3.4.1.tar.Z |
3758 |
|
3759 |
PGP (Pretty Good Privacy) |
3760 |
Philip Zimmermann prz@sage.cgd.ucar.EDU |
3761 |
|
3762 |
Crypto package that includes bignum routines in C. |
3763 |
Assembly implementations available for several processors; |
3764 |
said to be quite fast for numbers around 1000 bits in size. |
3765 |
The crypto package violates RSA patents, but the bignum routines |
3766 |
can be used without fear of legal repercussions. |
3767 |
|
3768 |
Bell's Arbitrary Precision Calculator |
3769 |
David I. Bell, Australia (dbell@pdact.pd.necisa.oz.au) |
3770 |
|
3771 |
Arbitrary-precision calculator with good online help, C-like |
3772 |
language, many builtin functions, support for integers, |
3773 |
rational numbers (they work like floating point), complex numbers, |
3774 |
matrices, strings, lists, files, "objects". Includes |
3775 |
gcd, primality testing, even trig functions. Recommended. |
3776 |
(Large package, though.) Obtained from comp.sources.unix. |
3777 |
Filename: calc-1.24.7.tar.Z |
3778 |
|
3779 |
Calc for GNU Emacs |
3780 |
Dave Gillespie (daveg@synaptics.com) |
3781 |
|
3782 |
Advanced calculator written in Emacs Lisp. Includes arbitrary |
3783 |
precision integers and floating point, bitwise operations, |
3784 |
log and trig functions, financial functions, number theoretic |
3785 |
functions including prime factorization, symbolic calculus, |
3786 |
and an interface to GNUPLOT. |
3787 |
Filename: calc-2.02a.tar.Z |
3788 |
|
3789 |
MPFUN: A Multiple Precision Floating Point Computation Package |
3790 |
David H. Bailey (dbailey@nas.nasa.gov) |
3791 |
|
3792 |
Package of Fortran subroutines to perform multiprecision |
3793 |
floating point arithmetic. Also includes a program that |
3794 |
can automatically convert ordinary Fortran-77 code into code |
3795 |
that calls the MPFUN routines. |
3796 |
Keith Briggs says: "It's a masterpiece, and the state of the art |
3797 |
as far as Fortran goes." |
3798 |
Documentation in TeX format. Unrestricted distribution |
3799 |
allowed at no cost. |
3800 |
Filenames: mpfun_fortran.tar.Z & mpfun_tex_papers.tar.Z |
3801 |
|
3802 |
MPQS |
3803 |
Mark S. Manasse (msm@src.dec.com) and Arjen Lenstra |
3804 |
|
3805 |
C program to factor numbers on a distributed network of |
3806 |
heterogeneous machines. June 1993 version. |
3807 |
Filename: mpqs-distributed-factoring.shar |
3808 |
|
3809 |
GNU bc |
3810 |
Author: Philip A. Nelson (phil@cs.wwu.edu) |
3811 |
GNU bc is an interactive algebraic language with arbitrary precision. |
3812 |
GNU bc is almost the same as bc & dc in some Unixes. |
3813 |
Filename: bc-1.02.tar.z (for example, in GNU prep.ai.mit.edu:pub/gnu/) |
3814 |
|
3815 |
bc & dc |
3816 |
bc is an interactive processor for an arbitrary precision arithmetic |
3817 |
language or just compiler/preprocessor for dc calculator with arbitrary |
3818 |
precision; they comes with some Unixes. |
3819 |
|
3820 |
Built-in support in other languages |
3821 |
Various |
3822 |
|
3823 |
Multiple precision arithmetic is available in a number of |
3824 |
programming languages, such as Lisp and ABC (cf. mcsun.eu.net). |
3825 |
Version 8 of the programming language Icon (Griswold's successor |
3826 |
to SNOBOL4 available from cs.arizona.edu) has large integers. |
3827 |
Perl (by Larry Wall, available from devvax.jpl.nasa.gov) |
3828 |
includes source, in Perl, for such a package, but it's probably |
3829 |
not suitable for serious use. |
3830 |
For some of these, source code may be available. This list is |
3831 |
long enough, so I'm not going to pursue it aggressively. |
3832 |
|
3833 |
Thanks to Keith Briggs and several others who contributed to this list. |
3834 |
|
3835 |
See also other sites, such as nic.funet.fi:pub/sci/math/multiplePrecision/. |
3836 |
|
3837 |
Mark Riordan mrr@ripem.msu.edu |
3838 |
-------------------------------------------------------------------------------- |
3839 |
\end{verbatim} |
3840 |
\end{scriptsize} |
3841 |
\end{quote} |
3842 |
|
3843 |
|
3844 |
|
3845 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
3846 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
3847 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
3848 |
\section{Authors And Acknowledgements} |
3849 |
%Section tag: ACK0 |
3850 |
This chapter was primarily written by \index{Ashley, David T.}David T. Ashley |
3851 |
\cite{bibref:i:daveashley}, and is based on a paper originally |
3852 |
authored by |
3853 |
David T. Ashley \cite{bibref:i:daveashley}, |
3854 |
Joseph P. DeVoe \cite{bibref:i:joedevoe}, |
3855 |
Karl Perttunen \cite{bibref:i:karlperttunen}, |
3856 |
Cory L. Pratt \cite{bibref:i:corypratt}, |
3857 |
and Anatoly Zhigljavsky \cite{bibref:i:anatolyzhigljavsky}. |
3858 |
|
3859 |
We would like to gratefully acknowledge the assistance of |
3860 |
\index{Davidson, Iain} Iain Davidson \cite{bibref:i:iaindavidson}, |
3861 |
\index{Edgar, Gerald A.} Gerald A. Edgar \cite{bibref:i:geraldaedgar}, and |
3862 |
\index{Smiley, Len} Len Smiley \cite{bibref:i:lensmiley} |
3863 |
in locating works related to the history of continued fractions. |
3864 |
We would also like to acknolwedge the assistance of |
3865 |
\index{Davidson, Iain} Iain Davidson \cite{bibref:i:iaindavidson} |
3866 |
in providing insight into algorithms and other assistance. |
3867 |
|
3868 |
For translating the remarks of Huygens and Delambre (Section |
3869 |
\ref{cfr0:hst0}) from French |
3870 |
to English, we are grateful to Sandrine de Raspide\index{Raspide, Sandrine@de Raspide, Sandrine} \cite{bibref:i:sandrinederaspide} |
3871 |
and Danil Hiridjee\index{Hiridjee, Danil} \cite{bibref:i:danilhiridjee}. |
3872 |
|
3873 |
We would also like to acknowledge the assistance of \texttt{sci.math} |
3874 |
\cite{bibref:n:scimathnewsgroup} |
3875 |
newsgroup posters in suggesting software which can manipulate |
3876 |
high-precision numbers, including |
3877 |
\index{Lutus, Paul} Paul Lutus \cite{bibref:i:paullutus}, |
3878 |
\index{Schorn, Richard} Richard Schorn \cite{bibref:i:richardschorn}, |
3879 |
and |
3880 |
\index{Taylor, Don} Don Taylor \cite{bibref:i:dontaylor}. |
3881 |
|
3882 |
Special thanks to |
3883 |
\index{Eastham, Chip} Chip Eastham \cite{bibref:i:chipeastham}, |
3884 |
\index{Kolker, Robert} Robert Kolker \cite{bibref:i:robertkolker}, |
3885 |
and |
3886 |
\index{Reichert, Jan-Hinnerk} Jan-Hinnerk Reichert \cite{bibref:i:janhinnerkreichert} |
3887 |
for locating and assisting in the correction of typographic |
3888 |
and mathematical errors. |
3889 |
|
3890 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
3891 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
3892 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
3893 |
\section{Exercises} |
3894 |
%Section tag: EXE0 |
3895 |
|
3896 |
\subsection{Algorithms} |
3897 |
|
3898 |
\begin{vworkexercisestatement} |
3899 |
\label{exe:cfr0:sexe0:a01} |
3900 |
Develop an algorithm to convert a continued fraction $[a_0;a_1, \ldots{}, a_n]$ |
3901 |
to a rational number $a/b$ ``from the right'' (starting with $a_n$), and prove |
3902 |
that the $a/b$ generated will be irreducible. (Hint: the ordinary algorithm |
3903 |
often applied by hand---working ``from the bottom up'' as shown in |
3904 |
Example \ref{ex:ccfr0:scnv0:abreconstructionfromright:01} |
3905 |
will always generate a coprime $a/b$.) |
3906 |
\end{vworkexercisestatement} |
3907 |
|
3908 |
\subsection{Calculation Of Best Rational Approximations} |
3909 |
|
3910 |
\begin{vworkexercisestatement} |
3911 |
\label{exe:cfr0:sexe0:b01} |
3912 |
Assuming 1.609344\footnote{\label{footnote:exe:cfr0:sexe0:b01}This |
3913 |
conversion factor was |
3914 |
obtained from \cite{bibref:b:nistsp811:1995ed} and is |
3915 |
assumed to be the most accurate conversion factor available.} |
3916 |
as the exact conversion factor from miles to |
3917 |
kilometers, find the best rational approximation to this |
3918 |
conversion factor with a maximum numerator of 255 and a maximum |
3919 |
denominator of 255. |
3920 |
\end{vworkexercisestatement} |
3921 |
|
3922 |
\begin{vworkexercisestatement} |
3923 |
\label{exe:cfr0:sexe0:b02} |
3924 |
Assuming 1.609344 (see Footnote \ref{footnote:exe:cfr0:sexe0:b01}) |
3925 |
as the exact conversion factor from miles to |
3926 |
kilometers, find the best rational approximation to this |
3927 |
conversion factor with a maximum numerator of 65,535 and a maximum |
3928 |
denominator of 65,535. |
3929 |
\end{vworkexercisestatement} |
3930 |
|
3931 |
\subsection{Continued Fraction Representation Of Irrational Numbers} |
3932 |
|
3933 |
\begin{vworkexercisestatement} |
3934 |
\label{exe:cfr0:sexe0:c01} |
3935 |
Show that the continued fraction representation of the |
3936 |
golden ratio $(\sqrt{5}/2 + 1/2)$ is $[1;\overline{1}]$. |
3937 |
\end{vworkexercisestatement} |
3938 |
|
3939 |
\vworkexercisefooter{} |
3940 |
|
3941 |
|
3942 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
3943 |
|
3944 |
\noindent\begin{figure}[!b] |
3945 |
\noindent\rule[-0.25in]{\textwidth}{1pt} |
3946 |
\begin{tiny} |
3947 |
\begin{verbatim} |
3948 |
$HeadURL$ |
3949 |
$Revision$ |
3950 |
$Date$ |
3951 |
$Author$ |
3952 |
\end{verbatim} |
3953 |
\end{tiny} |
3954 |
\noindent\rule[0.25in]{\textwidth}{1pt} |
3955 |
\end{figure} |
3956 |
|
3957 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
3958 |
% |
3959 |
%End of file C_CFR0.TEX |