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