/[dtapublic]/sf_code/esrgpubs/acm0010/paper/acm_paper.tex
ViewVC logotype

Contents of /sf_code/esrgpubs/acm0010/paper/acm_paper.tex

Parent Directory Parent Directory | Revision Log Revision Log


Revision 24 - (show annotations) (download) (as text)
Sat Oct 8 06:15:00 2016 UTC (8 years ago) by dashley
File MIME type: application/x-tex
File size: 91761 byte(s)
Initial commit.
1 %$Header: /cvsroot/esrg/sfesrg/esrgpubs/acm0010/paper/acm_paper.tex,v 1.5 2003/04/08 03:57:12 dtashley Exp $
2
3 \documentclass{esub2acm}
4
5 \usepackage{amsfonts}
6 \usepackage{amsmath}
7
8 \usepackage{graphicx}
9
10 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
11 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
12 % NEW NUMBERED ENVIRONMENTS (THEOREMS, EXAMPLES, ETC.) %
13 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
14 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
15 \newtheorem{algorithm}{Algorithm}
16
17 \newtheorem{example}{Example}
18
19 \newtheorem{mytheorem}{Theorem}
20
21 %%Sets of real numbers.
22 \newcommand{\realset}{{\mathbb{R}}}
23 \newcommand{\realsetnonneg}{{\mathbb{R}^+}}
24 %%
25 %%Sets of integers.
26 \newcommand{\intset}{{\mathbb{Z}}}
27 \newcommand{\intsetnonneg}{{\mathbb{Z}^+}}
28 \newcommand{\intsetpos}{{\mathbb{N}}}
29 %%
30 %%Sets of rational numbers.
31 \newcommand{\ratset}{{\mathbb{Q}}}
32 \newcommand{\ratsetnonneg}{{\mathbb{Q}^+}}
33 %%
34 %%Sets of irrational numbers.
35 \newcommand{\irratset}{{\mathbb{error}}}
36 \newcommand{\irratsetnonneg}{{\mathbb{error}^+}}
37
38 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
39 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
40 % NEW ENVIRONMENT DEFINITIONS %
41 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
42 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
43 %The "itemize" environment defined by the IEEE style files didn't seem to have
44 %quite the right appearance for presenting our algorithms. For this reason, the
45 %following environments were defined. Level 0 is flush left with bullets, Level 1
46 %is slightly more indented, etc.
47 \newenvironment{alglvl0}{\begin{list}
48 {$\bullet$}{\setlength{\labelwidth}{3mm}\setlength{\leftmargin}{6mm}}}
49 {\end{list}}
50 \newenvironment{alglvl1}{\begin{list}
51 {$\bullet$}{\setlength{\labelwidth}{3mm}\setlength{\leftmargin}{6mm}}}
52 {\end{list}}
53 \newenvironment{alglvl2}{\begin{list}
54 {$\bullet$}{\setlength{\labelwidth}{3mm}\setlength{\leftmargin}{6mm}}}
55 {\end{list}}
56
57 %The following environment is intended for listing properties (of continued fractions,
58 %convergents, etc.).
59 \newenvironment{propenum}{\begin{list}
60 {$\bullet$}{\setlength{\labelwidth}{3mm}\setlength{\leftmargin}{6mm}}}
61 {\end{list}}
62
63 %The following environment is intended for general enumeration.
64 \newenvironment{generalenum}{\begin{list}
65 {$\bullet$}{\setlength{\labelwidth}{3mm}\setlength{\leftmargin}{6mm}}}
66 {\end{list}}
67
68 %The following environment is intended for general enumeration with a slight indent.
69 \newenvironment{generalenumindent01}{\begin{list}
70 {$\bullet$}{\setlength{\labelwidth}{3mm}\setlength{\leftmargin}{12mm}}}
71 {\end{list}}
72
73 %The following environment is for the glossary at the end.
74 \newenvironment{glossaryenum}{\begin{list}
75 {}{\setlength{\labelwidth}{0mm}
76 \setlength{\leftmargin}{4mm}
77 \setlength{\itemindent}{-4mm}
78 \setlength{\parsep}{0.85mm}}}
79 {\end{list}}
80
81
82 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
83 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
84 %%Not sure what Greek letter to use to denote the difference
85 %%at the terminal L(x_{MAX}). For that reason will
86 %%leave that option open and define it as a new command,
87 %%so it can be changed in one place.
88 \newcommand{\lxtermdifffuncsymbol}{\psi}
89
90
91 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
92 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
93 % HYPHENATION EXCEPTION RULES %
94 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
95 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
96 %\hyphenation{http:-//-www.-cf.-ac.-uk/-uwcc/-maths/-zhig-ljavskyaa/}
97 \hyphenation{micro-con-trol-ler}
98 \hyphenation{rat-io-met-ric}
99 \hyphenation{rat-ion-al}
100 \hyphenation{Zhig-ljav-sky}
101
102 \begin{document}
103
104 \title{On Best Rational Approximations Using\\
105 Large Integers}
106 \author{David T. Ashley, Joseph P. DeVoe, Karl Perttunen, Cory Pratt\\
107 Visteon Corporation
108 \and
109 Anatoly Zhigljavsky\\
110 University Of Cardiff}
111 %\sponsor{Association for Computing Machinery, Inc.,
112 % 1515 Broadway, New York, NY 10036, USA
113 % Tel: (212) 555-1212; Fax: (212) 555-2000}
114
115 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
116 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
117 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
118 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
119 \begin{abstract}
120 Computer processors are equipped with
121 instructions to multiply and divide very large integers.
122 These instructions can be used to economically implement linear scalings
123 from an integer domain to an integer range by choosing
124 a rational number $r_A = h/k$, calculating the product $hx$ using
125 an integer multiplication instruction, and applying an
126 integer division instruction to form $\lfloor{}hx/k\rfloor{}$.
127 This paper presents a novel $O(log \; max(h_{MAX}, k_{MAX}))$
128 algorithm based on continued fractions
129 for finding the closest rational number $r_A = h/k$ to an arbitrary
130 real number $r_I$ subject to constraints
131 $h \leq h_{MAX}$ and $k \leq k_{MAX}$.
132 Novel results are presented bounding the maximum distance between available
133 choices of $r_A$ when $r_A$ will be chosen only in an interval
134 $[l,r]$, utilizing a second novel
135 $O(log \; max(h_{MAX}, k_{MAX}))$
136 continued
137 fraction algorithm. Novel results bounding the
138 error due to
139 the necessity of an integer domain and range are presented.
140 The results and
141 techniques presented have relevance to scientific
142 computing (where integer operations may execute much more quickly than
143 floating point operations), to consumer electronics and
144 embedded real-time systems (where the processor may have
145 integer multiplication and division instructions, but no
146 floating-point capability), to the design of special-purpose
147 digital logic (which may implement multiplication and division
148 in hardware), and to the design of mechanical
149 systems (two gears meshed together mechanically implement
150 a ratio which is the ratio of their numbers of teeth).
151 \end{abstract}
152 % A category with only the three required fields
153 %\category{H.4.m} {Information Systems} {Miscellaneous}
154 %A category including the fourth, optional field
155 \category{G.1.2} {Numerical Analysis}{Approximation}[linear approximation]
156 \terms{Algorithms, Theory}
157 \keywords{Rational approximation, Farey series, continued fraction,
158 approximation error, integer lattice.}
159 \begin{bottomstuff}
160 % You might add a line or two here if a version of your article appeared
161 % previously, or if the work was supported by an organization or conducted
162 % under a grant.
163 %\begin{authinfo}
164 %\name{David T. Ashley, Joseph P. DeVoe, Cory Pratt, Karl Perttunen} use if there are several authors with different addresses
165 %\address{P.O. Box 1221, Dublin, OH 43017-6221}
166 %\affiliation{} use if there are several authors with different affiliations
167 %\biography{} optional; not generally used.
168 %\end{authinfo}
169 % Here's a neat thing: all you have to put in your document is the command
170 %"\permission" and LaTeX automatically enters the complete text of the
171 %"Permission to copy..." boilerplate
172 \permission
173 \end{bottomstuff}
174 \markboth{D.T. Ashley, J.P. DeVoe, K. Perttunen, C. Pratt, and A. Zhigljavsky}
175 {On Best Rational Approximations Using Large Integers}
176 \maketitle
177
178
179 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
180 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
181 % INTRODUCTION %
182 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
183 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
184 \section{Introduction}
185 Modern computer instruction sets contain instructions
186 for multiplication and division of large integers. In many
187 applications, the mainstay of efficient software design is the ability
188 to phrase a computational problem in a form which is
189 economically executed by the hardware available. In a very
190 capable processor (such as a workstation or supercomputer),
191 approximations involving only integers may be attractive because
192 integer instructions execute more quickly than
193 floating-point instructions, or because the processor design
194 allows them to execute
195 concurrently with floating-point instructions. In very inexpensive
196 processors (such as those used in consumer electronics), approximations
197 involving only integers may be attractive because the processor
198 has no floating-point capability.
199
200 This paper presents results and techniques
201 for making optimal use of integer multiplication and division
202 instructions to approximate functions of the form $F(x) = r_I x$,
203 $r_I \in \realsetnonneg$ using
204 functions in the form of (\ref{eq:fundeqn}).\footnote{Mnemonic for $r_I$ and $r_A$:
205 \emph{I}=ideal, \emph{A}=actual. In this paper,
206 $\realsetnonneg$,
207 $\intsetnonneg{}$, and
208 $\intsetpos{}$
209 are the sets of non-negative real numbers,
210 non-negative integers, and
211 positive integers, respectively.}
212
213 \begin{equation}
214 \label{eq:fundeqn}
215 J(x)
216 =
217 \lfloor r_A \lfloor x \rfloor \rfloor
218 =
219 \left\lfloor\frac{h \lfloor x \rfloor}{k}\right\rfloor{};
220 h \in \intsetnonneg{}, \leq h_{MAX} ; k \in \intsetpos{}, \leq k_{MAX}.
221 \end{equation}
222
223 Because modern processors can multiply and divide
224 \emph{very}
225 large integers (32- and 64-bit integers are
226 typical), choosing $h$ and $k$ so as to place
227 $r_A = h/k$ as close as possible to an arbitrary
228 $r_I \in \realsetnonneg$ involves a
229 very large search space, and an efficient algorithm
230 is necessary for computational viability.
231
232 Section \ref{sec:fareyseries} presents a
233 summary of important properties of the Farey series, and
234 Section \ref{sec:continuedfractions} presents a
235 summary of important properties of the apparatus
236 of continued fractions.\footnote{The algorithms presented
237 are based on the properties of the Farey series and
238 the apparatus of continued fractions---because
239 these are topics from number theory that seldom
240 find application in practical computer arithmetic, a summary
241 is necessary for readability.}
242
243 Section
244 \ref{sec:kmaxonlycase} presents a novel
245 $O(log \; k_{MAX})$ continued fraction algorithm
246 for finding the best rational approximations $r_A = h/k$
247 to an arbitrary $r_I \in \realsetnonneg$ subject to the constraint
248 $k \leq k_{MAX}$. Section \ref{sec:hmaxandkmaxcase} extends the
249 algorithm of Section \ref{sec:kmaxonlycase}
250 to the case where both $h$ and $k$
251 are constrained, $h \leq h_{MAX} \wedge k \leq k_{MAX}$; and presents
252 a novel $O(log \; max(h_{MAX}, k_{MAX}))$ continued fraction
253 algorithm for finding the best rational approximations in the
254 rectangular area of the integer lattice formed by the constraints.
255
256 Section \ref{sec:intervalcase} presents novel results
257 bounding the distance between rational numbers in a rectangular area of the
258 integer lattice when $r_I \in [l,r]$.
259 Section \ref{sec:endtoenderror} presents a method for bounding
260 the end-to-end approximation error as a function of $r_A-r_I$.
261
262 Section \ref{sec:designexample} provides a practical design
263 example illustrating the techniques.
264
265
266 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
267 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
268 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
269 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
270 \section{The Farey Series Of Order $N$}
271 \label{sec:fareyseries}
272
273 The \emph{Farey series
274 of order $N$}, denoted $F_{N}$,
275 is the ordered set of all irreducible
276 rational numbers $h/k$ in the interval
277 [0,1]
278 with a denominator $k\leq N$.
279 For example, the Farey series of
280 order 7, $F_7$, is
281
282 \begin{equation}
283 \label{eq:eq0045}
284 F_7 = \left\{ {\frac{0}{1},\frac{1}{7},\frac{1}{6},
285 \frac{1}{5},\frac{1}{4},\frac{2}{7},
286 \frac{1}{3},\frac{2}{5},\frac{3}{7},\frac{1}{2},\frac{4}{7},
287 \frac{3}{5},\frac{2}{3},\frac{5}{7},\frac{3}{4},
288 \frac{4}{5},\frac{5}{6},\frac{6}{7},\frac{1}{1}} \right\}.
289 \end{equation}
290
291 The distribution of Farey rational numbers in
292 [0,1] is repeated
293 in any
294 $[n,n+1]$, $n\in \intsetnonneg$; so the distribution of
295 Farey rationals in [0,1] supplies complete
296 information about the distribution in
297 all of $\realsetnonneg$.\footnote{We
298 stretch the proper nomenclature by referring
299 to sequential rational numbers outside the
300 interval $[0,1]$ as Farey terms or as part of
301 $F_N$, which, in the strictest sense, they are not.
302 All of the results presented in
303 this paper (except Sections \ref{subsec:numberofelements} and \ref{subsec:probresults}) apply
304 everywhere in $\realsetnonneg$, and this abuse
305 is not harmful.}
306
307 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
308 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
309 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
310 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
311 \subsection{Properties Of Sequential Elements}
312
313 \begin{mytheorem}
314 \label{thm:thm01}
315 If $H/K$ and $h/k$ are two successive terms of $F_{N}$,
316 then
317 \end{mytheorem}
318
319 \begin{equation}
320 \label{eq:eq0048}
321 K h - H k = 1.
322 \end{equation}
323
324 \emph{Note:} This condition is necessary but not
325 sufficient for $h/k$ to be the Farey successor of $H/K$.
326 In general, there is
327 more than one $h/k$ with $k \leq N$ such that $Kh - Hk = 1$.
328
329 \begin{proof}
330 See \cite{HardyAndWrightClassic} p.23, \cite{LeVeque} p.222.
331 \end{proof}
332
333 \begin{mytheorem}
334 \label{thm:thm05}
335 If $H/K$ is a term of $F_{N}$,
336 the successor of $H/K$
337 in $F_{N}$ is the $h/k$ satisfying
338 $Kh-Hk=1$ with the largest
339 denominator $k\leq N$.
340 \end{mytheorem}
341
342 \begin{proof}
343 Any potential successor of $H/K$
344 which meets $Kh-Hk=1$ can be formed
345 by adding $1/Kk$ to $H/K$
346 (\ref{eq:eq0055}).
347
348 \begin{equation}
349 \label{eq:eq0055}
350 Kh - Hk = 1 \to \frac{h}{k} = \frac{{1 + Hk}}{{Kk}} = \frac{H}{K} + \frac{1}{Kk}
351 \end{equation}
352
353 If $h/k$ and $h'/k'$ both
354 satisfy $Kh-Hk=1$ with $k'<k\leq{}N$, then
355 $H/K<h/k<h'/k'$. Thus the $h/k$
356 with the largest $k \leq N$
357 that meets $Kh-Hk=1$ is the successor
358 in $F_{N}$ to $H/K$.
359 \end{proof}
360
361 \begin{mytheorem}
362 \label{thm:thm03}
363 If $H/K$ and $h/k$ are two successive terms of $F_{N}$, then
364 \end{mytheorem}
365
366 \begin{equation}
367 \label{eq:eq0050}
368 K + k > N.
369 \end{equation}
370
371 \emph{Note:} This condition is necessary but not
372 sufficient for $h/k$ to be the Farey successor of $H/K$.
373
374 \begin{proof}
375 See \cite{HardyAndWrightClassic} p.23.
376 \end{proof}
377
378 \begin{mytheorem}
379 \label{thm:thm04}
380 If $h_{j-2}/k_{j-2}$, $h_{j-1}/k_{j-1}$, and $h_{j}/k_{j}$
381 are three consecutive terms of $F_{N}$, then:
382 \end{mytheorem}
383
384 \begin{equation}
385 \label{eq:eq0051}
386 h_{j} = \left\lfloor {\frac{{k_{j-2}
387 + N}}{{k_{j - 1} }}} \right\rfloor h_{j - 1} - h_{j-2}
388 \end{equation}
389
390 \begin{equation}
391 \label{eq:eq0052}
392 k_{j} = \left\lfloor {\frac{{k_{j-2} + N}}{{k_{j
393 - 1} }}} \right\rfloor k_{j - 1} - k_{j-2}
394 \end{equation}
395
396 \emph{Notes:} (1)Theorem \ref{thm:thm04} gives
397 recursive formulas for
398 generating successive terms in $F_N$
399 if two consecutive terms are known.
400 (2)Equations (\ref{eq:eq0051}) and
401 (\ref{eq:eq0052}) can be solved to
402 allow generation of terms in the decreasing direction
403 (\ref{eq:eq0053}, \ref{eq:eq0054}).
404
405 \begin{equation}
406 \label{eq:eq0053}
407 h_j = \left\lfloor {\frac{{k_{j + 2} + N}}{{k_{j + 1} }}} \right\rfloor h_{j + 1} - h_{j + 2}
408 \end{equation}
409
410 \begin{equation}
411 \label{eq:eq0054}
412 k_j = \left\lfloor {\frac{{k_{j + 2} + N}}{{k_{j + 1} }}} \right\rfloor k_{j + 1} - k_{j + 2}
413 \end{equation}
414
415 \begin{proof}
416 See \cite{SchroederClassic} p.83.
417 \end{proof}
418
419 In general, given only a single irreducible rational number $h/k$,
420 there is no method to find the immediate
421 predecessor or successor in $F_N$ without some
422 iteration (Equations \ref{eq:eq0051},
423 \ref{eq:eq0052},
424 \ref{eq:eq0053}, and \ref{eq:eq0054} require
425 two successive elements).
426
427 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
428 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
429 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
430 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
431 \subsection{Number Of Elements}
432 \label{subsec:numberofelements}
433
434 The number of elements in $F_N$ is approximately
435 $3 N^2 / \pi{}^2$.\footnote{This is a classic result
436 from number theory, and its basis isn't discussed here. In this
437 instance we mean $F_N$ strictly
438 in the interval $[0,1]$.}
439 $F_{255=2^8-1}$ contains about 20,000 elements,
440 $F_{65,535=2^{16}-1}$ contains about 1.3 billion elements,
441 $F_{2^{32}-1}$ contains about $5.6 \times 10^{18}$
442 elements, and $F_{2^{64}-1}$ contains about
443 $1.0 \times 10^{38}$ elements.
444
445 The large numbers of elements in the Farey
446 series of the orders used in practice make it impractical
447 to linearly search the Farey series to find the best rational
448 approximations.\footnote{For example, a particularly naive approach might
449 be to start at an integer $i$, where three successive terms
450 in $F_N$ are $(Ni-1)/N$, $i/1$, and $(Ni+1)/N$, and to use
451 (\ref{eq:eq0051}) through (\ref{eq:eq0054})
452 to linearly search upward or downward until the
453 real number of interest is enclosed. Even in
454 $F_{2^{32}-1}$, searching 1,000,000 rational numbers per
455 second, such a search would require up to about 90,000 years.}
456
457
458 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
459 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
460 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
461 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
462 \subsection{Probabilistic Results On $| r_I - r_A |$}
463 \label{subsec:probresults}
464
465 If rational numbers of the form $r_A = h/k$, subject to the constraint
466 $k \leq k_{MAX}$, are used to approximate arbitrary real numbers
467 $r_I$, it might not be clear how close we can ``typically'' choose
468 $r_A$ to an aribtrary $r_I$ under the constraint.
469 We consider different asymptotics for
470 the precision of the approximation of an arbitrary $r_I$ by a
471 rational number
472 $r_A=h/k$ with $k \leq k_{MAX}$. For simplicity of notation
473 we
474 denote $\alpha= r_I$ and $N=k_{ \rm MAX }$ and assume, without
475 loss of generality, that
476 $ \alpha \in [0,1]$.
477
478 We are thus interested in the asymptotic behaviour, when $N
479 \rightarrow \infty$,
480 of the quantity
481 $$
482 %\begin{equation}
483 \label{eq:dist}
484 \rho_N(\alpha) = \min_{h/k \in F_N} \left|\alpha - h/k\right|\, ,
485 $$
486 %\end{equation}
487 which is the distance between $\alpha$ and $F_N$, the Farey
488 series of order $N$.
489
490 The worst--case scenario is not very interesting: from the
491 construction of the Farey series
492 we observe that for a fixed $N$ the longest intervals between the
493 neighbours of $F_N$
494 are $[0,1/N]$ and $[1-1/N,1]$ and therefore for all $N$
495 \begin{equation}
496 \label{eq:max_error}
497 \max_{\alpha \in [0,1]} \rho_N(\alpha) = \frac{1}{2N}\, .
498 \end{equation}
499 (This supremum is achieved at the points $1/(2N)$ and $1-1/(2N)$.)
500
501 However, such behaviour of $\rho_N(\alpha)$ is not typical: as
502 is shown below,
503 typical values of the approximation error $\rho_N(\alpha)$ are
504 much smaller.
505
506 First consider the behaviour of $\rho_N(\alpha)$ for almost all
507 $\alpha \in [0,1]$.\footnote{ A statement is true
508 for almost all $\alpha \in [0,1]$ if the measure of the set where this
509 statement is wrong has measure zero.}
510 We then have (see \cite{KargaevZ}, \cite{Harman})
511 that for almost all $\alpha \in [0,1]$ and any $\varepsilon >0$,
512 (\ref{eq:liminf}) and (\ref{eq:limsup}) hold.
513
514 \begin{equation}
515 \label{eq:liminf}
516 \lim_{N\rightarrow\infty}\rho_N(\alpha) N^2 \log^{1+\varepsilon} N =
517 + \infty, \quad
518 \liminf_{N\rightarrow\infty} \rho_N(\alpha) N^2 \log N = 0
519 \end{equation}
520
521 \begin{equation}
522 \label{eq:limsup}
523 \limsup_{N\rightarrow\infty} \frac{ \rho_N(\alpha) N^2 }{ \log N } = +
524 \infty, \quad
525 \lim_{N\rightarrow\infty} \frac{ \rho_N(\alpha) N^2 }{
526 \log^{1+\varepsilon} N } = 0
527 \end{equation}
528
529 Even more is true: in (\ref{eq:liminf}) and (\ref{eq:limsup})
530 one can replace $\log N$ by $\log N \log \log N $, $\log N \log \log
531 N \log \log \log N$, and so on.
532 Analogously, $\log^{1+\varepsilon} N$ could be replaced by
533 $\log N (\log \log N)^{1+\varepsilon} $, $\log N \log \log N (\log \log
534 \log N)^{1+\varepsilon}$, and so on.
535
536 These statements are analogues of Khinchin's metric theorem,
537 the classic result
538 in metric number theory, see e.g. \cite{Harman}.
539
540 The asymptotic distribution of the suitably normalised
541 $\rho_N(\alpha)$
542 was derived in \cite{KargaevZ1}. A main result of this
543 paper is that
544 the sequence of functions
545 $N^2\rho_N(\alpha)$ converges in distribution, when $N\rightarrow
546 \infty$,
547 to the probability measure on $[0, \infty)$ with the density given
548 by (\ref{eq:dens-ab}).
549
550 \begin{equation}
551 \label{eq:dens-ab}
552 {p}(\tau) =
553 \left\{\begin{array}{l}
554 6/\pi^2, \hfill\mbox{ if $0 \leq \tau \leq \frac{1}{2}$ }\\
555 \\
556 \frac{6}{\pi^2 \tau} \left(1 + \log \tau - \tau
557 \right), \hfill\mbox{ if $\frac{1}{2}\leq \tau\leq 2 $ } \\
558 \\
559 \frac{ 3}{\pi^2 \tau}\left(2\log(2 \tau)\!
560 -\!4\log(\sqrt{\tau}\!+\!\sqrt{\tau\!-\!2})\!
561 -\! (\sqrt{\tau}\!-\!\sqrt{\tau\!-\!2})^2 \right),
562 \\
563 \hfill \mbox{ if $2 \leq \tau < \infty $ } \\
564 \end{array}
565 \right.
566 \end{equation}
567
568 This means that
569 for all $a,A$
570 such that
571 $0<a<A<\infty$,
572 (\ref{eq:davedrzinsert01}) applies,
573 where
574 {\rm `meas'} denotes for the standard Lebesgue measure on $[0,1]$.
575
576 \begin{equation}
577 \label{eq:davedrzinsert01}
578 {\rm meas} \{ \alpha \in [0,1]: \;a < N^2 \rho_N(\alpha) \leq A \}
579 \rightarrow
580 \int_a^A {p}(\tau) d \tau\,
581 \;\;{\rm as}\; N \rightarrow \infty
582 \end{equation}
583
584 Another result in \cite{KargaevZ1} concerns the asymptotic
585 behavior
586 of the moments of the approximation error $\rho_N(\alpha) $. It
587 says that
588 for any $\delta\neq 0$ and $N \rightarrow \infty$,
589 (\ref{eq:moments}) applies,
590 where $\zeta(\cdot)$ and B$(\cdot,\cdot)$
591 are the Riemann zeta--function and the Beta--function,
592 respectively.
593
594 \begin{equation}
595 \label{eq:moments}
596 %\hspace{-8mm}
597 {
598 %\textstile
599 \small
600 \frac{\delta+1}{2}
601 }
602 \int_0^1 \rho_N^{\delta} (\alpha) d \alpha =
603 \left\{\begin{array}{l}
604 \infty{}, \hfill\mbox{if $ \delta \leq -1 $}\\
605 \\
606 % \frac{6}{\delta^2 (\delta+1)\pi^2 } \left(2^{-\delta} +
607 \frac{3}{\delta^2 \pi^2 } \left(2^{-\delta} +
608 \delta 2^{\delta+2} {\rm B}(\!-\delta,\frac{1}{2}) \right)
609 N^{-2\delta}\left(1\! +\! o(1)\right), \\
610 \hfill\mbox{if $-1\!<\!\delta\!<\!1, \delta\! \neq\! 0$ }\\
611 \\
612 \frac{3}{\pi^2} N^{-2} \log N +
613 O\left( N^{-2} \right),
614 \hfill\mbox{if $\delta =1 $ }\\
615 \\
616 %\frac{2^{1-\delta}}{1+\delta}
617 2^{-\delta}
618 \frac{\zeta(\delta)}{ \zeta(\delta+1)}
619 N^{-\delta-1}+
620 O\left( N^{-2\delta} \right),
621 \hfill \mbox{if $\delta >1$ }
622 \end{array}
623 \right.
624 \end{equation}
625
626 In particular, the average of the approximation error $\rho_N
627 (\alpha)$ asymptotically equals
628 \begin{equation}
629 \label{eq:average_as}
630 \int_{0}^1 \rho_N(\alpha) d\alpha = \frac{3}{\pi^2} \frac{\log N}{N^2} +
631 O\left(\frac{1}{N^2}\right),
632 \;\;\;\; N\rightarrow \infty \,.
633 \end{equation}
634
635 Comparison of (\ref{eq:average_as})
636 with (\ref{eq:limsup}) shows that the
637 asymptotic behavior of the average approximation error $\int
638 \rho_N(\alpha) d\alpha$
639 resembles the behavior of the superior limit of $\rho_N(\alpha)$.
640 Even this limit
641 decreases much faster than the maximum error $\max_{\alpha }
642 \rho_N(\alpha)$, see
643 (\ref{eq:max_error}): for typical $\alpha$ the rate of decrease of
644 $\rho_N(\alpha)$, when $ N\rightarrow \infty ,$
645 is, roughly speaking, $1/N^2$ rather than $1/N$, the error for the
646 worst combination of $\alpha$ and $N$.
647
648 These results show that there is a significant advantage to using the Farey series
649 as the set from which to choose rational approximations, rather than
650 more naively using only rational numbers with the maximum
651 denominator $k_{MAX}$ (as is often done in practice).
652
653
654 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
655 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
656 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
657 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
658 \section{The Apparatus Of Continued Fractions}
659 \label{sec:continuedfractions}
660
661 An \emph{n-th order finite simple continued fraction} is a fraction in the form
662 of (\ref{eq:eq0057}), where $a_0 \in \intsetnonneg$
663 and $a_{k} \in \intsetpos$ for $k > 0$. To ensure that two continued fractions
664 which represent the same number can't be written differently, we also require that
665 the final element $a_n$ not be equal to 1 (except when
666 representing the integer 1).\footnote{If $a_n=1$, the continued fraction can be reduced in order by
667 one and $a_{n-1}$ can be increased by one while still preserving the value of the continued
668 fraction.}
669 A continued fraction
670 in the form of (\ref{eq:eq0057}) is denoted $[a_0; a_1, a_2, \ldots, a_n]$, and each
671 $a_k$ is called an \emph{element} or \emph{partial quotient}.
672
673 \begin{equation}
674 \label{eq:eq0057}
675 a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2
676 + \cfrac{1}{\;\;\;\;\;\;\;\;\;\;\;\;\;\;\ldots + \cfrac{1}{a_n}}}}
677 =
678 [a_0; a_1, a_2, \ldots , a_n]
679 \end{equation}
680
681 Continued fractions provide an alternate apparatus for
682 representing real numbers. The form of (\ref{eq:eq0057}) has
683 important properties which are presented without proof.
684
685 \begin{propenum}
686 \item Every rational number can be represented by a finite
687 simple continued fraction $[a_{0};a_{1},a_{2},\ldots{} ,a_{n}]$.
688 \item Each unique $[a_{0};a_{1},a_{2},\ldots{} ,a_{n}]$ corresponds to a
689 uniquely valued rational number.
690 \end{propenum}
691
692 Without proof, we present the following algorithm for
693 finding partial quotients $a_k$ of an arbitrary
694 non-negative rational number $a/b$.
695
696 \begin{algorithm}\label{alg:akgenalg}\end{algorithm}
697 \begin{alglvl0}
698 \item $k:=-1$.
699 \item $divisor_{-1} := a$.
700 \item $remainder_{-1} := b$.
701
702 \item Repeat
703
704 \begin{alglvl1}
705 \item $k := k + 1$.
706 \item $dividend_k := divisor_{k-1}$.
707 \item $divisor_k := remainder_{k-1}$.
708 \item $a_k := dividend_k \; div \; divisor_k$.
709 \item $remainder_k := dividend_k \; mod \; divisor_k$.
710 \end{alglvl1}
711
712 \item Until ($remainder_k = 0$).
713 \end{alglvl0}
714
715 Without proof, we present the following properties of
716 Algorithm \ref{alg:akgenalg}.
717
718 \begin{propenum}
719 \item The algorithm will produce the same $[a_{0};a_{1},a_{2},\ldots{} ,a_{n}]$
720 for any $(ia)/(ib)$, $i \in \intsetpos{}$, i.e.
721 the rational number $a/b$ need not be reduced before
722 applying the algorithm.
723 \item The algorithm will always terminate (i.e. the
724 continued fraction representation
725 $[a_{0};a_{1},a_{2},\ldots{} ,a_{n}]$ will be
726 finite).
727 \end{propenum}
728
729 The apparatus of continued fractions is best viewed as
730 an alternate apparatus for representing real numbers, and
731 Algorithm \ref{alg:akgenalg} is best viewed as an algorithm for
732 determining in which partition a rational number lies, in the same sense
733 that long division successively partitions a rational number as each
734 successive decimal digit is obtained. To say that
735 the first three digits of a real number $x$ are ``3.14'' is logically equivalent
736 to saying that $3.14 \leq x < 3.15$ (i.e. that $x$ lies in a certain
737 partition). In the same sense, (\ref{eq:cfeq01}), (\ref{eq:cfeq02}),
738 and (\ref{eq:cfeq03}) are valid equivalences.
739
740 \begin{equation}
741 \label{eq:cfeq01}
742 (x=[a_0] \vee x=[a_0; \ldots ] ) \leftrightarrow (a_0 \leq x < a_0 + 1)
743 \end{equation}
744
745 \begin{equation}
746 \label{eq:cfeq02}
747 (x=[a_0; a_1] \vee x=[a_0; a_1, \ldots ] ) \leftrightarrow
748 \left(
749 {
750 a_0 + \frac{1}{a_1 + 1} < x \leq a_0 + \frac{1}{a_1}
751 }
752 \right)
753 \end{equation}
754
755 \begin{equation}
756 \label{eq:cfeq03}
757 \begin{array}{c}
758 (x=[a_0; a_1, a_2] \vee x=[a_0; a_1, a_2, \ldots ] ) \vspace{0.05in}\\
759 \updownarrow \vspace{0.0in}\\
760 \left(
761 {
762 a_0+\cfrac{1}{a_1 + \cfrac{1}{a_2}} \leq x < a_0+\cfrac{1}{a_1 + \cfrac{1}{a_2+1}}
763 }
764 \right)
765 \end{array}
766 \end{equation}
767
768 The form of (\ref{eq:cfeq01}), (\ref{eq:cfeq02}),
769 and (\ref{eq:cfeq03}) could be continued indefinitely to show the
770 defining inequality for higher-order partitions.
771 From the form of (\ref{eq:cfeq01}), (\ref{eq:cfeq02}),
772 and (\ref{eq:cfeq03}) it can be readily seen that irrational numbers have a
773 non-terminating
774 continued fraction representation, and that the algorithm for finding that
775 representation would be symbolic and involve successively determining
776 higher order partial quotients (i.e. at each step, in which
777 partition the irrational number lies). The algorithm for determining
778 the partial quotients of an irrational number isn't discussed in this
779 paper.
780 In most practical applications, $r_I$ is known empirically to at least several
781 decimal places, and the most practical technique is to use the
782 best known decimal
783 approximation as the starting point to apply Algorithm \ref{alg:akgenalg}.
784
785
786 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
787 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
788 % (4)(F)(v) CONVERGENTS OF A CONTINUED FRACTION %
789 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
790 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
791 The \emph{kth convergent} of a finite simple continued fraction
792 $[a_{0};a_{1},a_{2},\ldots{},a_{n}]$,
793 denoted $s_{k} = p_k/q_k$, is the rational number corresponding to the
794 continued fraction $[a_{0};a_{1},a_{2},\ldots{},a_{k}]$,
795 $k \leq n$. Equations (\ref{eq:eq0059}) through (\ref{eq:eq0064})
796 define the canonical way to
797 construct all $s_{k}=p_{k}/q_{k}$ from all $a_{k}$.
798
799 \begin{equation}
800 \label{eq:eq0059}
801 p_{ - 1} = 1
802 \end{equation}
803
804 \begin{equation}
805 \label{eq:eq0060}
806 q_{ - 1} = 0
807 \end{equation}
808
809 \begin{equation}
810 \label{eq:eq0061}
811 p_0 = a_0 = \left\lfloor {r_I } \right\rfloor
812 \end{equation}
813
814 \begin{equation}
815 \label{eq:eq0062}
816 q_0 = 1
817 \end{equation}
818
819 \begin{equation}
820 \label{eq:eq0063}
821 p_k = a_k p_{k - 1} + p_{k - 2}
822 \end{equation}
823
824 \begin{equation}
825 \label{eq:eq0064}
826 q_k = a_k q_{k - 1} + q_{k - 2}
827 \end{equation}
828
829 When $p_{k}$ and $q_{k}$ (the numerator and denominator of the
830 $k$th convergent $s_{k}$) are formed as specified by (\ref{eq:eq0059})
831 through (\ref{eq:eq0064}), convergents $s_{k}=p_{k}/q_{k}$ have the following
832 properties, which are presented without proof.
833
834 \begin{propenum}
835
836 \item Each even-ordered convergent
837 $s_{k} = p_k/q_k = [a_{0}; a_{1}, a_{2}, \ldots{}, a_{k}]$
838 is less than $[a_{0}; a_{1}, a_{2}, \ldots{}, a_{n}]$, and
839 each odd-ordered convergent $s_{k}$ is greater than
840 $[a_{0}$; $a_{1}$, $a_{2}$, $\ldots{}$, $a_{n}]$,
841 with the exception of the final convergent $s_{k}$, $k=n$,
842 which is equal to $[a_{0}; a_{1}, a_{2}, \ldots{}, a_{n}]$.
843
844 \item Each convergent is irreducible; that is, $p_k$ and
845 $q_k$ are coprime.
846
847 \item Each $q_{k}$ is greater than $q_{k-1}$; that is, the denominators
848 of convergents are ever-increasing. Furthermore, the
849 denominators of convergents
850 increase at a minimum rate that is exponential
851 (Eq. \ref{eq:skminexpincrease}), \cite{KhinchinClassic} Theorem 12.
852
853 \begin{equation}
854 \label{eq:skminexpincrease}
855 q_k \geq 2^{\frac{k-1}{2}}, \; k \geq 2
856 \end{equation}
857
858 \end{propenum}
859
860 An \emph{intermediate fraction} is a fraction of the form
861
862 \begin{equation}
863 \label{eq:intermediatefractiondef}
864 \frac{i p_k + p_{k-1}}{i q_k + q_{k-1}}, \; i < a_{k+1}.
865 \end{equation}
866
867 It can be seen by comparing (\ref{eq:intermediatefractiondef}) with
868 (\ref{eq:eq0063}) and (\ref{eq:eq0064}) that an intermediate fraction
869 can be denoted compactly by the continued fraction representation of
870 a convergent, with the final element adjusted downward. For example,
871 if $[a_0; a_1, a_2, \ldots , a_{k-1}]$ and $[a_0; a_1, a_2, \ldots , a_{k-1}, a_k]$,
872 $k \leq n$,
873 are convergents; $[a_0; a_1, a_2, \ldots , a_{k-1}, 1]$,
874 $[a_0$; $a_1$, $a_2$, $\ldots$, $a_{k-1}$, $2]$, \ldots{}, and
875 $[a_0; a_1, a_2, \ldots , a_{k-1}, a_k -1]$ are intermediate fractions.
876
877
878 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
879 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
880 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
881 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
882 \section{Choosing $r_A = h/k$ Subject To $k \leq k_{MAX}$}
883 \label{sec:kmaxonlycase}
884
885 Finding the best rational approximation $r_A=h/k$ to an arbitrary
886 $r_I \in \realsetnonneg$ subject only to the constraint $k \leq k_{MAX}$
887 is equivalent to the problem of finding the two members
888 of $F_{k_{MAX}}$ which enclose $r_I$. Potential naive algorithms
889 include
890 building $F_{k_{MAX}}$ starting at an integer [$O(k_{MAX}^2$)],
891 building $F_{k_{MAX}}$ starting at a rational number with a large
892 prime denominator [$O(k_{MAX})$], and
893 building the Stern-Brocot tree [$O(k_{MAX})$].
894 For $k_{MAX}$ of a few hundred
895 or less, any of these algorithms are satisfactory, and they can be
896 carried out even with ordinary spreadsheet software, such as
897 \emph{Microsoft Excel}.
898
899 However, for $k_{MAX}$ typical of the more powerful
900 microcontrollers used in consumer
901 electronics ($2^{16}$ or $2^{32}$), and particularly for $k_{MAX}$ reflecting
902 the integer arithmetic capability of workstations
903 and supercomputers ($2^{32}$, $2^{64}$, or larger), $O(k_{MAX}^2)$
904 and $O(k_{MAX})$ algorithms are not computationally viable. This section
905 presents a novel $O(log \; k_{MAX})$ algorithm which is suitable for
906 finding best rational approximations even in Farey series of very large
907 order, based on the apparatus of continued fractions.
908
909
910 \subsection{Finding Best Rational Approximations With $r_I \in \hspace{-0.85em} / \hspace{0.25em} F_{k_{MAX}}$}
911
912 \begin{mytheorem}
913 \label{thm:thm06}
914 For a non-negative rational\footnote{Although it isn't discussed in this
915 paper, it isn't required that a number be rational in order to apply this
916 theorem. As emphasized by (\ref{eq:cfeq01}), (\ref{eq:cfeq02}), and (\ref{eq:cfeq03}),
917 the process of obtaining continued
918 fraction partial quotients is essentially a process of determining in which
919 partition a number lies. All numbers in the same partition---rational or
920 irrational---have the same Farey neighbors in all Farey series up to a certain order.
921 If the partial quotients of
922 an irrational number can be obtained up through $a_k$ s.t. $s_k = p_k/q_k$ is the
923 highest-order convergent with $q_k \leq N$, then this theorem can be applied.
924 Knowledge of all $a_0 \ldots{} a_k$ is equivalent
925 to the knowledge that the number is in a partition where all numbers in that partition have
926 the same Farey neighbors in all Farey series up through order $q_{k+1}-1$.}
927 number $a/b$ not in
928 $F_N$ which has a
929 continued fraction representation
930 $[a_0;a_1,a_2,\ldots{} ,a_n]$, the
931 highest-order convergent $s_k = p_k/q_k$ with $q_k \leq N$ is one
932 neighbor\footnote{By neighbors in $F_N$ we mean the rational numbers
933 in $F_N$ immediately to the left and immediately to the right
934 of $a/b$.}
935 to $a/b$ in $F_N$, and the other neighbor in
936 $F_N$ is\footnote{Theorem \ref{thm:thm06}
937 is a somewhat stronger statement about best approximations
938 than Khinchin makes in \cite{KhinchinClassic}, Theorem 15.
939 We were not able to locate
940 this theorem or a proof in print,
941 but this theorem is understood within the number theory community.
942 It appears on the Web
943 page of David Eppstein in the form of a
944 `C'-language computer program,
945 \texttt{http://www.ics.uci.edu/\~{}{}eppstein/numth/frap.c}.
946 Although
947 Dr. Eppstein phrases the solution in terms of modifying
948 a partial quotient, his approach is equivalent to
949 (\ref{eq:eq0065}).}
950 \end{mytheorem}
951
952 \begin{equation}
953 \label{eq:eq0065}
954 \frac{{\displaystyle{\left\lfloor {\frac{{N - q_{k - 1} }}{{q_k }}} \right\rfloor}
955 p_k + p_{k - 1} }}{{\displaystyle{\left\lfloor {\frac{{N - q_{k - 1} }}{{q_k }}}
956 \right\rfloor} q_k + q_{k - 1} }}.
957 \end{equation}
958
959 \begin{proof}
960 First, it is proved that the highest-order
961 convergent $s_k = p_k/q_k$ with $q_k \leq N$ is one of the two
962 neighbors to $a/b$ in $F_N$. $s_k \in F_N$, since $q_k \leq N$.
963 By \cite{KhinchinClassic}, Theorem 9, the upper bound on the
964 difference between $a/b$ and arbitrary $s_k$ is given by
965
966 \begin{equation}
967 \label{eq:eq0066}
968 \left| {\frac{a}{b} - \frac{{p_k }}{{q_k }}} \right| < \frac{1}{{q_k q_{k + 1} }}.
969 \end{equation}
970
971 For two consecutive terms in $F_N$, $Kh-Hk=1$.
972 For a Farey neighbor $H/K$ to $s_k$ in $F_N$, (\ref{eq:eq0067}) must hold.
973
974 \begin{equation}
975 \label{eq:eq0067}
976 \frac{1}{q_k N} \leq \left| {\frac{H}{K} - \frac{p_k}{q_k}} \right|
977 \end{equation}
978
979 $q_{k+1}>N$, because $q_{k+1}>q_k$ and $p_k/q_k$ was chosen to be the
980 highest-order convergent with $q_k\leq N$. Using this knowledge and
981 combining (\ref{eq:eq0066}) and (\ref{eq:eq0067}) leads to
982 (\ref{eq:eq0069}).
983
984 \begin{equation}
985 \label{eq:eq0069}
986 \left| {\frac{a}{b} - \frac{{p_k }}{{q_k }}} \right| < \frac{1}{{q_k q_{k + 1} }}
987 <
988 \frac{1}{q_k N} \leq \left| {\frac{H}{K} - \frac{p_k}{q_k}} \right|
989 \end{equation}
990
991 This proves that $s_k$ is one neighbor to $a/b$ in $F_N$.
992 The apparatus of continued fractions ensures that the
993 highest order convergent $s_k$ with $q_k\leq N$ is closer to $a/b$ than
994 to any neighboring term in $F_N$. Thus, there is
995 no intervening term of $F_N$ between $s_k$ and $a/b$.
996 If $k$ is even, $s_k<a/b$, and if $k$ is
997 odd, $s_k>a/b$.
998
999 It must be proved that (\ref{eq:eq0065}) is the other Farey
1000 neighbor. For brevity, only the case of $k$ even is proved: the
1001 case of $k$ odd is symmetrical. (\ref{eq:eq0065}) is of the form (\ref{eq:eq0071}),
1002 where $i \in \intsetnonneg$.
1003
1004 \begin{equation}
1005 \label{eq:eq0071}
1006 \frac{{ip_k + p_{k - 1} }}{{iq_k + q_{k - 1} }}
1007 \end{equation}
1008
1009 $k$ is even, $s_k < a/b$, and the two Farey terms enclosing $a/b$, in
1010 order, are
1011
1012 \begin{equation}
1013 \label{eq:eq0072}
1014 \frac{p_k }{q_k },\frac{ip_k + p_{k - 1} }{iq_k + q_{k - 1} }.
1015 \end{equation}
1016
1017 Applying the $Kh - Hk = 1$ test, (\ref{eq:eq0074}), gives the
1018 result of 1, since by theorem
1019 (\cite{KhinchinClassic}, Theorem 2),
1020 $q_kp_{k-1}-p_kq_{k-1}=(-1)^k$.
1021
1022 \begin{equation}
1023 \label{eq:eq0074}
1024 \begin{array}{*{20}c}
1025 {(q_k )(ip_k + p_{k - 1} ) - (p_k )(iq_k + q_{k - 1} ) = 1}
1026 \end{array}
1027 \end{equation}
1028
1029 Thus, every potential Farey neighbor of the form (\ref{eq:eq0071})
1030 meets the $Kh - Hk = 1$ test. It is also straightforward
1031 to show that \emph{only} potential Farey neighbors of the
1032 form (\ref{eq:eq0071}) can meet the $Kh-Hk=1$ test, using the
1033 property that $p_k$ and $q_k$ are coprime.
1034
1035 It must be established that a
1036 rational number of the form (\ref{eq:eq0071})
1037 is irreducible. This result comes directly from (\ref{eq:eq0074}),
1038 since if the numerator
1039 and denominator of (\ref{eq:eq0065}) or
1040 (\ref{eq:eq0071}) are not coprime, the difference of 1 is
1041 not possible.
1042
1043 The denominator of (\ref{eq:eq0065})
1044 can be rewritten as
1045
1046 \begin{equation}
1047 \label{eq:eq0076}
1048 N - \left[ {\left( {N - q_{k - 1} } \right)\bmod q_k } \right] \in \left\{ {N - q_k + 1,...,N} \right\}.
1049 \end{equation}
1050
1051 It must be shown that if one irreducible
1052 rational number---namely, the rational number given by
1053 (\ref{eq:eq0065})---with a denominator
1054 $\in \{ N-q_k+1,\ldots{} ,N \}$ meets the $Kh - Hk = 1$
1055 test, there can be no other irreducible rational number
1056 in $F_N$ with a larger
1057 denominator which also meets this test.
1058
1059 Given (\ref{eq:eq0076}), and given that \emph{only} rational numbers of the form
1060 (\ref{eq:eq0071}) can meet the $Kh-Hk=1$ test, and given that any number of the
1061 form (\ref{eq:eq0071}) is irreducible, the irreducible number meeting the
1062 $Kh-Hk=1$ test with the next larger denominator after the denominator of (\ref{eq:eq0065})
1063 will have a denominator $\in \{ N+1, \ldots, N+q_k \}$. Thus,
1064 no other irreducible rational number in $F_N$ besides that given
1065 by (\ref{eq:eq0065}) with a larger denominator
1066 $\leq N$ and which meets the $Kh - Hk = 1$ test can exist; therefore
1067 (\ref{eq:eq0065}) is the other enclosing Farey neighbor to
1068 $a/b$ in $F_N$.
1069 \end{proof}
1070
1071 Theorem \ref{thm:thm06} suggests an algorithm for determining best approximations to
1072 a rational $r_I =a/b \notin F_{k_{MAX}}$ subject to the constraint $k \leq k_{MAX}$.
1073
1074 \begin{algorithm}\label{alg:bratrnnifnalg}\end{algorithm}
1075 \begin{alglvl0}
1076 \item $k := -1$.
1077 \item $divisor_{-1} := a$.
1078 \item $remainder_{-1} := b$.
1079 \item $p_{-1} := 1$.
1080 \item $q_{-1} := 0$.
1081
1082 \item Repeat
1083
1084 \begin{alglvl1}
1085 \item $k := k + 1$.
1086 \item $dividend_k := divisor_{k-1}$.
1087 \item $divisor_k := remainder_{k-1}$.
1088 \item $a_k := dividend_k \; div \; divisor_k$.
1089 \item $remainder_k := dividend_k \; mod \; divisor_k$.
1090 \item If $k=0$ then $p_k := a_k$ else $p_k := a_k p_{k-1} + p_{k-2}$.
1091 \item If $k=0$ then $q_k := 1$ else $q_k := a_k q_{k-1} + q_{k-2}$.
1092 \end{alglvl1}
1093
1094 \item Until ($q_k > k_{MAX}$).
1095 \item $s_{k-1} = p_{k-1}/q_{k-1}$ will be one Farey neighbor to $a/b$ in $F_{k_{MAX}}$.
1096 Apply (\ref{eq:eq0065}) to obtain the other Farey neighbor.
1097 \end{alglvl0}
1098
1099 Algorithm \ref{alg:bratrnnifnalg} builds the partial quotients $a_k$ and convergents
1100 $s_k = p_k/q_k$ of $a/b$ only as far as required to obtain the highest-order
1101 convergent with $q_k \leq N$; thus the number of iterations required is tied to
1102 $k_{MAX}$, rather than to the precision of $a/b$. It is easy to see that
1103 Algorithm \ref{alg:bratrnnifnalg} is $O(log \; k_{MAX})$, since the the denominators
1104 of convergents $q_k$ have a minimum exponential rate of increase
1105 (\ref{eq:skminexpincrease}).\footnote{Although Algorithm \ref{alg:bratrnnifnalg}
1106 is the best known algorithm for finding Farey neighbors, it is an oversimplification
1107 to state that Algorithm \ref{alg:bratrnnifnalg} is $O(log \; k_{MAX})$. In the
1108 classical sense---speaking only in terms of numbers of operations and assuming that each type of
1109 operation takes the same amount of time regardless of the data---the algorithm
1110 is $O(log \; k_{MAX})$. However, when applying the algorithm for $a$, $b$, and $k_{MAX}$
1111 much larger than the native data sizes of the computer used, one must use some sort
1112 of arbitrary-precision or long integer calculation package, and the calculation times
1113 of such packages are probably between $O(log \; N)$ and $O(N)$ with respect to the data values.
1114 Taking this into account, the algorithm may be as poor as $O(N \; log \; N)$ for data much larger than
1115 accomodated by the computer used. However, this is not an impediment to practical calculations.
1116 The rational approximation software packaged with this paper (submitted to CALGO) will find
1117 neighbors
1118 within the Farey series of order $2^{128}$ with a calculation time of just a few seconds
1119 on a personal computer, and will find neighbors within the Farey series of order $2^{1,000}$ with a
1120 calculation time
1121 of less than 60 seconds.}
1122
1123 \subsection{Finding Best Rational Approximations With $r_I \in F_{k_{MAX}}$}
1124
1125 The case where $r_I \in F_{k_{MAX}}$ corresponds to the case where $r_I$ is at the
1126 edge of a partition, in the sense suggested by (\ref{eq:cfeq01}),
1127 (\ref{eq:cfeq02}), and (\ref{eq:cfeq03}). In this case, the
1128 highest-order convergent
1129 $s_n = p_n/q_n = r_I \in F_{k_{MAX}}$, and (\ref{eq:eq0065})
1130 supplies the right Farey neighbor to
1131 $r_I$ if $n$ is even, or the left Farey neighbor to $r_I$ if $n$ is odd.
1132 In the former case (\ref{eq:eq0053}) and (\ref{eq:eq0054}) can be used
1133 to obtain the left Farey neighbor, and in the latter case
1134 (\ref{eq:eq0051}) and (\ref{eq:eq0052}) can be used to obtain
1135 the right Farey neighbor. The second half of the proof
1136 of Theorem \ref{thm:thm06} applies.
1137
1138 Thus, finding the neighbors in $F_{k_{MAX}}$ to an arbitrary
1139 $r_I = a/b \in F_{k_{MAX}}$ is also an $O(log \; k_{MAX})$
1140 procedure, and easily accomplished using the apparatus of continued
1141 fractions.
1142
1143
1144 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1145 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1146 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1147 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1148 \section{Choosing $r_A = h/k$ Subject To $h \leq h_{MAX}$ And $k \leq k_{MAX}$}
1149 \label{sec:hmaxandkmaxcase}
1150
1151 Up to this point, only the case of constrained $k$
1152 has been considered. However, in a practical application, $h$ is also typically
1153 constrained, usually by the size of the operands
1154 and results that machine multiplication
1155 and division instructions can accomodate.
1156
1157 When $h$ and $k$ are both constrained, $h \leq h_{MAX} \wedge k \leq k_{MAX}$,
1158 the set of rational numbers $h/k$ that can be formed has a convenient
1159 and intuitive
1160 graphical interpretation (Figure \ref{fig:lattice01}
1161 illustrates this interpretation
1162 with $h_{MAX}=3$ and $k_{MAX}=5$).
1163 Each rational number $h/k$ that can be formed under the constraints
1164 corresponds to a point in the integer lattice.
1165
1166 \begin{figure}
1167 \centering
1168 \includegraphics[width=4.25in]{intlat01.eps}
1169 \caption{Integer Lattice Interpretation Of Rational Numbers $h/k$ Formable Under Constraints
1170 $h \leq h_{MAX}$ And $k \leq k_{MAX}$}
1171 \label{fig:lattice01}
1172 \end{figure}
1173
1174 From Figure \ref{fig:lattice01}, it is clear that:
1175
1176 \begin{generalenum}
1177 \item The angle $\theta$ of the ray from the origin to $(k,h)$
1178 is monotonically increasing with respect to the value of
1179 $h/k$, and:
1180
1181 \begin{generalenumindent01}
1182 \item $h/k = tan \theta$.
1183 \item $\theta = tan^{-1} h/k$.
1184 \end{generalenumindent01}
1185
1186 \item The smallest rational number that can be formed under the
1187 constraints is $0/1$, the smallest non-zero rational number
1188 is $1/k_{MAX}$, and the largest rational number is $h_{MAX}/1$.
1189
1190 \item Only irreducible rational numbers are directly ``visible''
1191 from the origin (reducible numbers are hidden ``behind''
1192 the irreducible numbers, when viewed from the origin).
1193
1194 \item The ascending set of irreducible rational numbers that can be formed
1195 subject to the constraints can be constructed graphically
1196 by sweeping a line starting at $\theta = 0$ through the range
1197 $0 \leq \theta < \pi/2$, recording each integer lattice point
1198 that is directly ``visible'' from the origin.
1199
1200 \item For $r_A = h/k \leq h_{MAX}/k_{MAX}$, the constraint $k \leq k_{MAX}$ is the
1201 dominant constraint, and the set of formable rational numbers
1202 $\leq h_{MAX}/k_{MAX}$ is simply $F_{k_{MAX}}$.
1203
1204 \end{generalenum}
1205
1206 By symmetry in Figure \ref{fig:lattice01}, it can be
1207 seen that each formable rational number $\geq h_{MAX}/k_{MAX}$ is the reciprocal
1208 of an element of the Farey series of order $h_{MAX}$. Thus, it is clear that
1209 the set of formable rational numbers under the constraints
1210 $h \leq h_{MAX} \wedge k \leq k_{MAX}$ can be built by concatenating
1211 a portion of $F_{k_{MAX}}$ with a portion of $F_{h_{MAX}}$, but with
1212 the terms of $F_{h_{MAX}}$ inverted and reversed in order.
1213
1214 We denote the series formed from $F_N$ by inverting each element (except $0/1$)
1215 and reversing the order as $F_{\overline{N}}$. For example, using this definition,
1216
1217 \begin{equation}
1218 F_{\overline{3}} =
1219 \left\{
1220 \ldots{},
1221 \frac{3}{8}, \frac{2}{5}, \frac{3}{7},
1222 \frac{1}{2}, \frac{3}{5}, \frac{2}{3}, \frac{3}{4},
1223 \frac{1}{1}, \frac{3}{2}, \frac{2}{1}, \frac{3}{1}
1224 \right\}.
1225 \end{equation}
1226
1227 We denote the series formed by concatenating $F_{k_{MAX}}$ up through
1228 $h_{MAX}/k_{MAX}$ to $F_{\overline{h_{MAX}}}$ from $h_{MAX}/k_{MAX}$
1229 through $h_{MAX}/1$ as $F_{k_{MAX}, \overline{h_{MAX}}}$.
1230
1231 Note that
1232 $F_{k_{MAX}, \overline{h_{MAX}}}$ is the ordered set of all
1233 irreducible rational numbers that can be formed subject to
1234 $h \leq h_{MAX} \wedge k \leq k_{MAX}$. For example, using this
1235 definition,
1236
1237 \begin{equation}
1238 \label{eq:concatseries01}
1239 F_{5, \overline{3}} =
1240 \left\{
1241 \frac{0}{1}, \frac{1}{5}, \frac{1}{4}, \frac{1}{3},
1242 \frac{2}{5}, \frac{1}{2}, \frac{3}{5},
1243 \frac{2}{3}, \frac{3}{4},
1244 \frac{1}{1}, \frac{3}{2}, \frac{2}{1}, \frac{3}{1}
1245 \right\}.
1246 \end{equation}
1247
1248 It can be verified that the result in (\ref{eq:concatseries01}) is the same
1249 as would be obtained in Figure \ref{fig:lattice01} by sweeping a
1250 line from the origin counterclockwise through $0 \leq \theta < \pi/2$, recording
1251 each point of the integer lattice directly ``visible'' from the origin.
1252
1253 The following $O(log \; max(h_{MAX}, k_{MAX}))$ algorithm is presented
1254 for finding the neighbors in $F_{k_{MAX}, \overline{h_{MAX}}}$ to
1255 an arbitrary irreducible rational number $a/b$.
1256
1257 \begin{algorithm}\label{alg:rectangular}\end{algorithm}
1258 \begin{alglvl0}
1259 \item If $a/b < h_{MAX}/k_{MAX}$, apply Algorithm \ref{alg:bratrnnifnalg}
1260 directly;
1261 \item Else if $a/b > h_{MAX}/k_{MAX}$, apply Algorithm \ref{alg:bratrnnifnalg}
1262 using $b/a$, rather than $a/b$ as $r_I$, and using $N=h_{MAX}$ rather than
1263 $N=k_{MAX}$, and invert and transpose the two
1264 Farey neighbors obtained;
1265 \item Else if $a/b = h_{MAX}/k_{MAX}$, apply both steps above: the first step
1266 to obtain the left neighbor in $F_{k_{MAX}, \overline{h_{MAX}}}$
1267 and the second step to obtain the right
1268 neighbor.
1269 \end{alglvl0}
1270
1271
1272 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1273 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1274 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1275 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1276 \section{Choosing $r_A = h/k$ Only In An Interval $[l,r]$}
1277 \label{sec:intervalcase}
1278
1279 It is clear from the earlier discussion of the Farey series that the maximum
1280 distance between terms in $F_{k_{MAX}}$ is $1/k_{MAX}$, and that this maximum
1281 distance occurs only adjacent to an integer. It is also clear from the
1282 discussion of $F_{\overline{h_{MAX}}}$ that the maximum distance between terms
1283 is 1.
1284
1285 Thus, when we use $F_{k_{MAX}, \overline{h_{MAX}}}$ to approximate real numbers,
1286 in general the worst-case distance between terms is 1.
1287
1288 In practical applications when rational approximation is used,
1289 the approximation tends to be used over a restricted interval
1290 $[l \gg 0, r \ll h_{MAX}]$ rather than over the full range of the rational numbers that
1291 can be formed, $[0, h_{MAX}]$. This section develops novel upper bounds on
1292 the distance between terms of $F_{k_{MAX}, \overline{h_{MAX}}}$ in an interval
1293 $[l,r]$. For simplicity, assume $l,r \in F_{k_{MAX}, \overline{h_{MAX}}}$.
1294
1295 Three distinct cases are developed (Figure \ref{fig:threecases}).
1296 The upper bound developed from Case III is always larger than the upper
1297 bound developed from Case II, which is always larger than the upper bound developed
1298 from Case I; so if only the absolute maximum error over
1299 the interval $[l,r]$ is of interest, only the
1300 highest-numbered case which applies needs to be evaluated. However, some
1301 applications may have different error requirements in different regions
1302 of the interval $[l,r]$, and for these applications it may be beneficial
1303 to analyze more than one case.
1304
1305 \begin{figure}
1306 \centering
1307 \includegraphics[width=4.25in]{intlat02.eps}
1308 \caption{Three Cases For Bounding Distance Between Terms In $F_{k_{MAX}, \overline{h_{MAX}}}$}
1309 \label{fig:threecases}
1310 \end{figure}
1311
1312
1313 \subsection{Case I: $r_I < h_{MAX}/k_{MAX}$}
1314 \label{subsec:casei}
1315
1316 With $r_I < h_{MAX}/k_{MAX}$, $k \leq k_{MAX}$ is the dominant
1317 constraint, and the neighbors available to $r_I$ are simply the
1318 terms of $F_{k_{MAX}}$. If $[l, r] \cap [0, h_{MAX}/k_{MAX}]$
1319 includes an integer, clearly the maximum distance from $r_I$ to the
1320 nearest available term of $F_{k_{MAX}, \overline{h_{MAX}}}$ is given
1321 by
1322
1323 \begin{equation}
1324 \left|
1325 \frac{h}{k} - r_I
1326 \right|
1327 \leq
1328 \frac{1}{2 k_{MAX}}.
1329 \end{equation}
1330
1331 If $[l, r] \cap [0, h_{MAX}/k_{MAX}]$ does
1332 not include an integer, it can be shown that the
1333 maximum distance between Farey terms is driven by the
1334 rational number with the smallest denominator in the
1335 interval.
1336
1337 For two consecutive terms $p/q$ and $p'/q'$ in $F_{k_{MAX}}$,
1338 $p'q - pq' = 1$ (Theorem \ref{thm:thm01}), so that
1339
1340 \begin{equation}
1341 \frac{p'}{q'} - \frac{p}{q} =
1342 \frac{p'q - pq'}{q q'} = \frac{1}{qq'} .
1343 \end{equation}
1344
1345 By Theorem \ref{thm:thm03}, $q+q' > k_{MAX}$, therefore
1346
1347 \begin{equation}
1348 \label{eq:minqplacementupperbound}
1349 \frac{1}{q k_{MAX}} \leq
1350 \frac{1}{q q'} <
1351 \frac{1}{q (k_{MAX}-q)}.
1352 \end{equation}
1353
1354 Let $q_{MIN}$ be the smallest denominator of any rational number
1355 $\in F_{k_{MAX}}$ in the interval $[l,r]$. It is then easy to show
1356 that for any consecutive denominators $q, q'$ which occur in
1357 $F_{k_{MAX}}$ in the interval $[l,r]$,
1358
1359 \begin{equation}
1360 \frac{1}{q q'} < \frac{1}{q_{MIN} \; max (q_{MIN}, k_{MAX} - q_{MIN})} .
1361 \end{equation}
1362
1363 Thus, the upper bound on the distance between consecutive terms of $F_{k_{MAX}}$
1364 in an interval $[l,r]$ is tied to the minimum denominator of any
1365 rational number $\in F_{k_{MAX}}$ in $[l,r]$.
1366
1367 Note that clearly
1368 $q_{MIN} \leq 1/(r-l)$, so for most practical intervals $[l,r]$,
1369 the search for $q_{MIN}$ would not be computationally expensive.
1370 However, applications could arise where an approximation is used
1371 in an \emph{extremely} narrow interval, and having an algorithm available that
1372 is computationally viable for such cases is advantageous. For example,
1373 locating the rational number $\in F_{2^{20,000}}$ with the smallest denominator
1374 in an interval of width $2^{-10,000}$ could be a serious computational
1375 problem.
1376
1377 To locate $q_{MIN}$ in $[l,r]$, note that at least one rational number
1378 with $q_{MIN}$ as a denominator in $[l,r]$ is the best approximation
1379 of order $q_{MIN}$ to the midpoint of the interval,
1380 $(l+r)/2$.\footnote{Thanks to David M. Einstein and David Eppstein
1381 for this observation, contributed via the \texttt{sci.math} newsgroup,
1382 which is the linchpin of Algorithm \ref{alg:cfmindenominator}.}
1383 By theorem (\cite{KhinchinClassic}, Theorem 15), every best approximation
1384 of a number is a convergent or intermediate fraction of the
1385 continued fraction representation of the number. We seek the
1386 convergent or intermediate fraction of $(l+r)/2$ with the smallest
1387 denominator that is in the interval $[l,r]$.
1388
1389 The convergents and intermediate fractions of $(l+r)/2$ are naturally
1390 arranged in order of increasing denominator. However, it would be
1391 inefficient to test \emph{every} intermediate fraction
1392 for membership in $[l,r]$, as partial quotients $a_k$ are unlimited in
1393 size and such an algorithm may not be $O(log \; k_{MAX})$. Instead,
1394 since intermediate fractions are formed using the parameterized
1395 expression $(i p_k + p_{k-1})/(i q_k + q_{k-1})$,
1396 and since intermediate fractions are ever-increasing
1397 or ever-decreasing with respect to the parameter $i$, the
1398 smallest value of $i$ which will create an intermediate
1399 fraction potentially within $[l,r]$ can be directly
1400 calculated. Only the intermediate fraction formed with
1401 this calculated value of $i$ needs to be tested for membership in
1402 $[l,r]$.
1403
1404 Let $l_N$ and $l_D$ be the numerator and denominator of $l$, and
1405 let $r_N$ and $r_D$ be the numerator and denominator of $r$.
1406 In the case of $k$ even; $s_k < l < (l+r)/2$ (otherwise $s_k$
1407 would have been identified as $\in [l,r]$, see Algorithm
1408 \ref{alg:cfmindenominator}); $s_{k+1} \geq (l+r)/2$;
1409 with increasing $i$, $(i p_k + p_{k-1})/(i q_k + q_{k-1})$
1410 forms a decreasing sequence; and the inequality we seek to solve is
1411
1412 \begin{equation}
1413 \label{eq:ifselection01}
1414 \frac{i p_k + p_{k-1}}{i q_k + q_{k-1}} \leq \frac{r_N}{r_D}.
1415 \end{equation}
1416
1417 Solving (\ref{eq:ifselection01}), the smallest integral value of $i$ that will suffice is
1418
1419 \begin{equation}
1420 \label{eq:ifselection02}
1421 i = \left\lceil {
1422 \frac{r_N q_{k-1} - r_D p_{k-1}}{r_D p_k - r_N q_k}
1423 } \right\rceil .
1424 \end{equation}
1425
1426 Similarly, for $k$ odd, the sequence is increasing,
1427 and the inequality and solution are
1428
1429 \begin{equation}
1430 \label{eq:ifselection03}
1431 \frac{i p_k + p_{k-1}}{i q_k + q_{k-1}} \geq \frac{l_N}{l_D}
1432 \to
1433 i = \left\lceil {
1434 \frac{l_N q_{k-1} - l_D p_{k-1}}{l_D p_k - l_N q_k}
1435 } \right\rceil .
1436 \end{equation}
1437
1438 (\ref{eq:ifselection01}),
1439 (\ref{eq:ifselection02}),
1440 and (\ref{eq:ifselection03}) suggest the following continued fraction
1441 algorithm for finding
1442 a rational number with the smallest denominator in an
1443 interval $[l,r]$.
1444
1445 \begin{algorithm}\label{alg:cfmindenominator}\end{algorithm}
1446 \begin{alglvl0}
1447 \item Calculate all partial quotients $a_k$ and all convergents
1448 $s_k = p_k/q_k$ of the midpoint of the interval,
1449 $(l+r)/2$.
1450
1451 \item For each convergent $s_k=p_k/q_k$, in order of increasing $k$:
1452
1453 \begin{alglvl1}
1454
1455 \item If $s_k = p_k/q_k \in [l,r]$, $s_k$ is a rational number with
1456 the lowest denominator, STOP.
1457
1458 \item If $k$ is even,
1459
1460 \begin{alglvl2}
1461
1462 \item Calculate $i$ according to (\ref{eq:ifselection02}).
1463 If $i < a_{k+1}$ and the intermediate fraction
1464 $(i p_k + p_{k-1})$ $/$ $(i q_k + q_{k-1})$ $\geq$ $l$, this intermediate
1465 fraction is
1466 a rational number with the lowest denominator, STOP.
1467
1468 \end{alglvl2}
1469
1470 \item Else if $k$ is odd,
1471
1472 \begin{alglvl2}
1473
1474 \item Calculate $i$ according to (\ref{eq:ifselection03}).
1475 If $i < a_{k+1}$ and the intermediate fraction
1476 $(i p_k + p_{k-1})$ $/$ $(i q_k + q_{k-1})$ $\leq$ $r$, this intermediate
1477 fraction is
1478 a rational number with the lowest denominator, STOP.
1479
1480 \end{alglvl2}
1481
1482 \end{alglvl1}
1483
1484 \end{alglvl0}
1485
1486 Algorithm \ref{alg:cfmindenominator} is approximately $O(log \; k_{MAX})$,
1487 since there are a fixed number of steps per convergent, and the maximum number
1488 of convergents is $O(log \; k_{MAX})$. Once a rational number with the smallest
1489 denominator $q_{MIN}$ is located, (\ref{eq:minqplacementupperbound})
1490 can be applied to bound $|r_A - r_I|$; namely,
1491
1492 \begin{equation}
1493 \label{eq:qminmaxplacementerror}
1494 \left| {\frac{h}{k} - r_I} \right|
1495 <
1496 \frac{1}{2q_{MIN} \; max(q_{MIN}, k_{MAX} - q_{MIN})} .
1497 \end{equation}
1498
1499
1500 \subsection{Case II: $h_{MAX}/k_{MAX} < r_I < 1$}
1501 \label{subsec:caseii}
1502
1503 If $h_{MAX}/k_{MAX} < r_I < 1$, a graphical argument
1504 (Figure \ref{fig:caseii}) can be used
1505 to more tightly bound the maximum distance between terms of
1506 $F_{k_{MAX}, \overline{h_{MAX}}}$.
1507
1508 \begin{figure}
1509 \centering
1510 \includegraphics[height=2.0in]{intlat03.eps}
1511 \caption{Graphical Interpretation Of Case II: $h_{MAX}/k_{MAX} < r_I < 1$}
1512 \label{fig:caseii}
1513 \end{figure}
1514
1515 In this case, a formable term at or to the left\footnote{To the left on the
1516 number line, but to the right in Figure \ref{fig:caseii}.}
1517 of $r_I$ is represented by the point $(\lfloor h_{MAX}/r_I \rfloor + 1, h_{MAX} )$
1518 in the integer lattice,
1519 and a formable term at or to the right of $r_I$ is
1520 represented by the point $(\lfloor h_{MAX}/r_I \rfloor, h_{MAX} )$
1521 in the integer lattice. Thus, the maximum distance between
1522 neighboring terms in $F_{k_{MAX}, \overline{h_{MAX}}}$
1523 is given by the difference of these two terms,
1524
1525 \begin{equation}
1526 \frac{h_{MAX}}{\left\lfloor {\frac{h_{MAX}}{r_I}} \right\rfloor}
1527 -
1528 \frac{h_{MAX}}{\left\lfloor {\frac{h_{MAX}}{r_I}} \right\rfloor + 1}
1529 =
1530 \frac{h_{MAX}}{{\left\lfloor {\frac{h_{MAX}}{r_I}} \right\rfloor}^2
1531 + \left\lfloor {\frac{h_{MAX}}{r_I}} \right\rfloor},
1532 \end{equation}
1533
1534 and the maximum distance from $r_I$ to a neighboring term is
1535 given by
1536
1537 \begin{equation}
1538 \label{eq:caseiimaxplacementerror}
1539 \left|
1540 \frac{h}{k} - r_I
1541 \right|
1542 \leq
1543 \frac{h_{MAX}}{2 \left( { {\left\lfloor {\frac{h_{MAX}}{r_I}} \right\rfloor}^2
1544 + \left\lfloor {\frac{h_{MAX}}{r_I}} \right\rfloor } \right) }.
1545 \end{equation}
1546
1547 Note that Case II will exist only if $h_{MAX}/k_{MAX} < 1$.
1548
1549
1550 \subsection{Case III: $1 < h_{MAX}/k_{MAX} < r_I$}
1551 \label{subsec:caseiii}
1552
1553 It can be established graphically, using the coordinate system of
1554 Figure \ref{fig:lattice01}
1555 or Figure \ref{fig:threecases}, that the line $h=r_I k$ intercepts the
1556 line $h=h_{MAX}$ at the point $(h_{MAX}/r_I, h_{MAX})$. It is clear
1557 from a graphical argument that all of the terms of the Farey series
1558 of order $\lfloor h_{MAX}/r_I \rfloor$ are available as neighbors
1559 of $r_I$. Therefore,
1560
1561 \begin{equation}
1562 \label{caseiiiplacementerror}
1563 \left|
1564 \frac{h}{k} - r_I
1565 \right|
1566 \leq
1567 \frac{1}{2 \left\lfloor \frac{h_{MAX}}{r_I} \right\rfloor}.
1568 \end{equation}
1569
1570
1571 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1572 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1573 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1574 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1575 \section{End-To-End Approximation Error}
1576 \label{sec:endtoenderror}
1577
1578 A rational approximation requires an integer domain and range, and there are three
1579 sources of error inherent in such an approximation:
1580
1581 \begin{generalenum}
1582
1583 \item Input quantization error, as the input to the approximation is restricted
1584 to $\intsetnonneg$.
1585
1586 \item Error in selecting $r_A = h / k$, as in general it isn't possible to choose
1587 $r_A = r_I$.
1588
1589 \item Output quantization error, as the remainder of the division of $hx$ by
1590 $k$ is discarded, and the output must be $\in \intsetnonneg$.
1591
1592 \end{generalenum}
1593
1594 To model the end-to-end approximation error, a model function
1595 is introduced which represents the function we wish to approximate,
1596
1597 \begin{equation}
1598 \label{eq:eq0001}
1599 F(x)=r_{I}x .
1600 \end{equation}
1601
1602 However, the approximation necessarily involves quantizing
1603 the input $x$, as well as the result of the integer division:
1604
1605 \begin{equation}
1606 \label{eq:eq0006}
1607 J(x) = \left\lfloor {r_A \left\lfloor x \right\rfloor } \right\rfloor
1608 = \left\lfloor {\frac{{h\left\lfloor x \right\rfloor }}{k}} \right\rfloor .
1609 \end{equation}
1610
1611 Quantization of a real argument $x$ which is not necessarily
1612 rational is treated by noting that quntization introduces an
1613 error $\varepsilon \in [0,1)$:
1614
1615 \begin{equation}
1616 \lfloor x \rfloor = x - \varepsilon; \; \varepsilon \in [0,1) .
1617 \end{equation}
1618
1619 Quantization of a rational argument $a/b$ is treated
1620 by noting that the largest quantization error $\varepsilon$
1621 occurs when $a$ is one less than an integral multiple of
1622 $b$:
1623
1624 \begin{equation}
1625 \left\lfloor {\frac{a}{b}} \right\rfloor
1626 =
1627 \frac{a}{b} - \varepsilon; \;
1628 \varepsilon \in
1629 \left[ {0, \frac{b-1}{b}} \right] .
1630 \end{equation}
1631
1632 The difference function $J(x)-F(x)$, can be stated
1633 as in (\ref{eq:eq0031}) or (\ref{eq:eq0032}). The two quantizations in (\ref{eq:eq0031})
1634 can be treated by introducing $\varepsilon_{1}$
1635 and $\varepsilon_{2}$ to yield (\ref{eq:eq0032}).
1636 Note that $\varepsilon_{1}$ and $\varepsilon_{2}$
1637 are independent, meaning for this application that in general $r_I$,
1638 $r_A = h/k$, and $x$ can be
1639 chosen so as to force any combination of $\varepsilon_{1}$ and
1640 $\varepsilon_{2}$, so that no combinations of $\varepsilon_{1}$ and $\varepsilon_{2}$
1641 can be excluded.
1642
1643 \begin{equation}
1644 \label{eq:eq0031}
1645 J(x) - F(x) = \left\lfloor {\frac{{h\left\lfloor x \right\rfloor
1646 }}{k}} \right\rfloor - r_I x
1647 \end{equation}
1648
1649 \begin{equation}
1650 \label{eq:eq0032}
1651 J(x) - F(x) = \frac{{h(x - \varepsilon _1 ) }}{k} - \varepsilon _2 - r_I x
1652 ; \;
1653 \varepsilon _1 \in [0,1)
1654 ; \;
1655 \varepsilon _2 \in \left[ {0,\frac{{k - 1}}{k}} \right]
1656 \end{equation}
1657
1658 Choosing the extremes of
1659 $\varepsilon_{1}$ and $\varepsilon_{2}$
1660 so as to minimize and maximize the difference
1661 function bounds the approximation error (\ref{eq:eq0035}).
1662
1663 \begin{equation}
1664 \label{eq:eq0035}
1665 J(x) - F(x) \in
1666 \left( {(r_A - r_I )x - r_A - \frac{{k - 1}}{k},(r_A - r_I )x } \right]
1667 \end{equation}
1668
1669 Minimizing and maximizing (\ref{eq:eq0035}) over
1670 a domain of $[0,x_{MAX}]$ leads to (\ref{eq:eq0036}).
1671
1672 \begin{equation}
1673 \label{eq:eq0036}
1674 \left. {J(x) - F(x)} \right|_{x \in [0,x_{MAX} ]} \in
1675 \left\{ {\begin{array}{*{20}c}
1676 {\left( {(r_A - r_I )x_{MAX} - r_A - \frac{{k - 1}}{k},0} \right],}
1677 \hfill & {r_A < r_I } \hfill \\
1678 \\
1679 {\left( { - r_A - \frac{{k - 1}}{k},0} \right],} \hfill & {r_A = r_I } \hfill \\
1680 \\
1681 {\left( { - r_A - \frac{{k - 1}}{k},(r_A - r_I )x_{MAX} } \right] ,}
1682 \hfill & {r_A > r_I } \hfill \\
1683 \end{array}} \right.
1684 \end{equation}
1685
1686 Thus, given an $r_I \in \realsetnonneg$ and a rational approximation to $r_I$,
1687 $r_A = h/k$, the error introduced by this rational approximation used over a
1688 domain $[0,x_{MAX}]$ can be bounded.
1689
1690
1691 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1692 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1693 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1694 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1695 \section{Design Example}
1696 \label{sec:designexample}
1697
1698 A design example is presented to illustrate the methods presented.
1699 An $r_I$ specified with only modest precision and an
1700 $h_{MAX}$ and $k_{MAX}$ of only modest size are used to avoid a large
1701 number of partial quotients or large integers.\footnote{The rational
1702 approximation
1703 software submitted with this paper will handle rational approximations involving hundreds
1704 of digits and hundreds of partial quotients. However, such approximations make unsuitable
1705 examples because of the length, the difficulty in typesetting huge integers and
1706 rational numbers, and because
1707 the examples can't be carried out manually by a reader.}
1708
1709 \textbf{Design Example:}
1710 Assume that real numbers are to be approximated by rational numbers
1711 in the interval $[0.385, 2.160]$, subject to $h_{MAX} = 193 \wedge k_{MAX}=500$.
1712 Bound $|r_A - r_I|$ under these constraints. Find the best rational
1713 approximations to $1/\pi \approx 0.31830989$ and
1714 $2/\pi \approx 0.63661977$ under the same constraints.
1715
1716 \textbf{Solution:}
1717 In this example, \emph{Case I}, \emph{Case II}, and \emph{Case III}
1718 (Sections \ref{subsec:casei}, \ref{subsec:caseii}, and \ref{subsec:caseiii}) apply. Case III
1719 will dominate the upper bound on the error in selecting $r_A$,
1720 but it is instructive to work through Case I and Case II.
1721
1722 To apply the results from \emph{Case I}, it is necessary to find
1723 a rational number with the smallest denominator in the interval
1724 $[l = 0.385, r = 193/500 = 0.386]$. The midpoint of the interval
1725 is $(l+r)/2 = 0.3855 = 771/2000$.
1726
1727 Table \ref{tbl:cfexpansmidpoint} shows the generation of the partial quotients and convergents of the
1728 midpoint, 771/2000, using Algorithm \ref{alg:bratrnnifnalg}.
1729
1730 \begin{table}
1731 \caption{Partial Quotients And Convergents Of 0.3855 (Midpoint Of The Interval
1732 $[0.385, 0.386]$)}
1733 \label{tbl:cfexpansmidpoint}
1734 \begin{center}
1735 \begin{tabular}{|c|c|c|c|c|c|c|}
1736 \hline
1737 \small{Index} & \small{$dividend_k$} & \small{$divisor_k$} & \small{$a_k$} & \small{$remainder_k$} & \small{$p_k$} & \small{$q_k$} \\
1738 \small{($k$)} & & & & & & \\
1739 \hline
1740 \hline
1741 \small{-1} & \small{N/A} & \small{771} & \small{N/A} & \small{2000} & \small{1} & \small{0} \\
1742 \hline
1743 \small{0} & \small{771} & \small{2000} & \small{0} & \small{771} & \small{0} & \small{1} \\
1744 \hline
1745 \small{1} & \small{2000} & \small{771} & \small{2} & \small{458} & \small{1} & \small{2} \\
1746 \hline
1747 \small{2} & \small{771} & \small{458} & \small{1} & \small{313} & \small{1} & \small{3} \\
1748 \hline
1749 \small{3} & \small{458} & \small{313} & \small{1} & \small{145} & \small{2} & \small{5} \\
1750 \hline
1751 \small{4} & \small{313} & \small{145} & \small{2} & \small{23} & \small{5} & \small{13} \\
1752 \hline
1753 \small{5} & \small{145} & \small{23} & \small{6} & \small{7} & \small{32} & \small{83} \\
1754 \hline
1755 \small{6} & \small{23} & \small{7} & \small{3} & \small{2} & \small{101} & \small{262} \\
1756 \hline
1757 \small{7} & \small{7} & \small{2} & \small{3} & \small{1} & \small{335} & \small{869} \\
1758 \hline
1759 \small{8} & \small{2} & \small{1} & \small{2} & \small{0} & \small{771} & \small{2000} \\
1760 \hline
1761 \end{tabular}
1762 \end{center}
1763 \end{table}
1764
1765 Algorithm \ref{alg:cfmindenominator} can be applied to locate the fraction
1766 in $[l,r]$ with the smallest denominator. $s_0 =0/1 \notin [l,r]$. The intermediate fraction
1767 $(p_0 + p_{-1})/(q_0 + q_{-1})=1/1 \notin [l,r]$. $s_1 = 1/2 \notin [l,r]$.
1768 $s_2 = 1/3 \notin [l,r]$. $s_3 = 2/5 \notin [l,r]$. The intermediate fraction
1769 $(p_3 + p_2)/(q_3 + q_2)=3/8 \notin [l,r]$. $s_4 = 5/13 \notin [l,r]$.
1770 (\ref{eq:ifselection02}) can be applied to determine the lowest value of the
1771 parameter $i$ for which an intermediate fraction \emph{may} be in $[l,r]$:
1772
1773 \begin{equation}
1774 i = \left\lceil {
1775 \frac
1776 {(r_N = 193)(q_3 = 5) - (r_D = 500)(p_3=2)}
1777 {(r_D=500)(p_4 = 5)-(r_N=193)(q_4=13)}
1778 } \right\rceil
1779 =
1780 \left\lceil {\frac{-35}{-9}} \right\rceil = 4.
1781 \end{equation}
1782
1783 Thus, it is only necessary to examine the intermediate fraction $(4 p_4 + p_3)/(4 q_4 + q_3)$
1784 for potential membership in $[l,r]$. This intermediate fraction, $22/57$ $\approx$ $0.385965$ $\in$ $[l,r]$.
1785 Thus, the fraction with the lowest denominator in the interval is 22/57, and $q_{min} = 57$.
1786
1787 Application of (\ref{eq:qminmaxplacementerror}) yields
1788
1789 \begin{equation}
1790 \begin{array}{l}
1791 \displaystyle{\left| {\frac{h}{k} - r_I} \right| < } \\
1792 \\
1793 \displaystyle{\left({\frac{1}{2q_{MIN} \; max(q_{MIN}, k_{MAX}-q_{MIN})} = \frac{1}{(2)(57)(500-57)} = \frac{1}{50,502} } \right) .}
1794 \end{array}
1795 \end{equation}
1796
1797 Note that the 1/50,502 maximum error in placing $r_A$ is much better than the
1798 1/1,000 worst-case error for $F_{500}$ in general without restrictions on
1799 the interval.
1800
1801 Case II and Case III aren't as complicated as Case I---applying these
1802 cases is a simple matter of substitution into (\ref{eq:caseiimaxplacementerror})
1803 or (\ref{caseiiiplacementerror}).
1804 Case II and
1805 (\ref{eq:caseiimaxplacementerror}) apply, but the error bounds from
1806 Case III will be larger, so Case II is not evaluated.
1807 Case III applies: the line $h=r_I k$ intersects the line $h=h_{MAX}$ at
1808 the point
1809 $(h_{MAX}/r_I, h_{MAX})$ = $(193/2.160, 193)$, thus all terms
1810 of the Farey series of order $\lfloor 193/2.160 \rfloor = 89$ are
1811 available for selection. Therefore, applying (\ref{caseiiiplacementerror}),
1812
1813 \begin{equation}
1814 \left| {\frac{h}{k} - r_I} \right|
1815 \leq
1816 \frac{1}{2 \times 89} \approx 0.0056 .
1817 \end{equation}
1818
1819 Thus, if $F_{500, \overline{193}}$ is used to approximate real numbers over the
1820 interval $[0.385$, $2.160]$, an upper bound on $|r_A - r_I|$ is $1/178 \approx 0.0056$.
1821 Note that Case III dominates, and that the upper bound on $|r_A - r_I|$ varies
1822 within the interval.
1823
1824 To find the best rational approximations to $1/ \pi$ in $F_{500, \overline{193}}$,
1825 note that $1/ \pi < 193/500$, so all of the terms in $F_{500}$ are available.
1826 Table \ref{tbl:cfexpansraponeoverpi} shows the partial quotients and convergents
1827 of $1/ \pi$, using 0.31830989 as a rational approximation of $1/ \pi$. $s_4$
1828 is the highest-order convergent with $q_k \leq 500$, so $s_4 = 113/355$ is one
1829 Farey neighbor to $1/ \pi$ in $F_{500}$. Applying (\ref{eq:eq0065}) to generate
1830 the other neighbor in $F_{500}$ yields 106/333. Note that $113/355 - 1/\pi \approx -3 \times 10^{-8}$
1831 and $106/333 - 1/\pi \approx 8 \times 10^{-6}$ (the errors are quite small).
1832
1833 \begin{table}
1834 \caption{Partial Quotients And Convergents Of 31,830,989/100,000,000
1835 (A Rational Approximation To $1/ \pi$)}
1836 \label{tbl:cfexpansraponeoverpi}
1837 \begin{center}
1838 \begin{tabular}{|c|c|c|c|c|c|c|}
1839 \hline
1840 \small{Index} & \small{$dividend_k$} & \small{$divisor_k$} & \small{$a_k$} & \small{$remainder_k$} & \small{$p_k$} & \small{$q_k$} \\
1841 \small{($k$)} & & & & & & \\
1842 \hline
1843 \hline
1844 \small{-1} & \small{N/A} & \small{31,830,989} & \small{N/A} & \small{100,000,000} & \small{1} & \small{0} \\
1845 \hline
1846 \small{0} & \small{31,830,989} & \small{100,000,000} & \small{0} & \small{31,830,989} & \small{0} & \small{1} \\
1847 \hline
1848 \small{1} & \small{100,000,000} & \small{31,830,989} & \small{3} & \small{4,507,033} & \small{1} & \small{3} \\
1849 \hline
1850 \small{2} & \small{31,830,989} & \small{4,507,033} & \small{7} & \small{281,758} & \small{7} & \small{22} \\
1851 \hline
1852 \small{3} & \small{4,507,033} & \small{281,758} & \small{15} & \small{280,663} & \small{106} & \small{333} \\
1853 \hline
1854 \small{4} & \small{281,758} & \small{280,663} & \small{1} & \small{1,095} & \small{113} & \small{355} \\
1855 \hline
1856 \small{5} & \small{280,663} & \small{1,095} & \small{256} & \small{343} & \small{29,034} & \small{91,213} \\
1857 \hline
1858 \small{6} & \small{1,095} & \small{343} & \small{3} & \small{66} & \small{87,215} & \small{273,994} \\
1859 \hline
1860 \small{7} & \small{343} & \small{66} & \small{5} & \small{13} & \small{465,109} & \small{1,461,183} \\
1861 \hline
1862 \small{8} & \small{66} & \small{13} & \small{5} & \small{1} & \small{2,412,760} & \small{7,579,909} \\
1863 \hline
1864 \small{9} & \small{13} & \small{1} & \small{13} & \small{0} & \small{31,830,989} & \small{100,000,000} \\
1865 \hline
1866 \end{tabular}
1867 \end{center}
1868 \end{table}
1869
1870 To find the best rational approximations to $2/ \pi$ in $F_{500, \overline{193}}$,
1871 note that $2/ \pi > 193/500$, so the second clause of Algorithm \ref{alg:rectangular}
1872 applies. Table \ref{tbl:cfexpansrappiovertwo} shows the partial quotients and convergents
1873 of $\pi / 2$, using 1/0.63661977 as a rational approximation of $\pi /2$. $s_3$
1874 is the highest-order convergent with $q_k \leq 193$, so $s_3^{-1} = (11/7)^{-1}$ is one
1875 neighbor to $2/ \pi$ in $F_{\overline{193}}$. Applying (\ref{eq:eq0065}) to generate
1876 the reciprocal of the other neighbor in $F_{\overline{193}}$ yields 300/191, implying that
1877 191/300 is the other neighbor. $7/11 - 2/\pi \approx -3 \times 10^{-4}$.
1878 $191/300 - 2/\pi \approx 5 \times 10^{-5}$.
1879
1880 \begin{table}
1881 \caption{Partial Quotients And Convergents Of 100,000,000/63,661,977
1882 (A Rational Approximation To $\pi / 2$)}
1883 \label{tbl:cfexpansrappiovertwo}
1884 \begin{center}
1885 \begin{tabular}{|c|c|c|c|c|c|c|}
1886 \hline
1887 \small{Index} & \small{$dividend_k$} & \small{$divisor_k$} & \small{$a_k$} & \small{$remainder_k$} & \small{$p_k$} & \small{$q_k$} \\
1888 \small{($k$)} & & & & & & \\
1889 \hline
1890 \hline
1891 \small{-1} & \small{N/A} & \small{100,000,000} & \small{N/A} & \small{63,661,977} & \small{1} & \small{0} \\
1892 \hline
1893 \small{0} & \small{100,000,000} & \small{63,661,977} & \small{1} & \small{36,338,023} & \small{1} & \small{1} \\
1894 \hline
1895 \small{1} & \small{63,661,977} & \small{36,338,023} & \small{1} & \small{27,323,954} & \small{2} & \small{1} \\
1896 \hline
1897 \small{2} & \small{36,338,023} & \small{27,323,954} & \small{1} & \small{9,014,069} & \small{3} & \small{2} \\
1898 \hline
1899 \small{3} & \small{27,323,954} & \small{9,014,069} & \small{3} & \small{281,747} & \small{11} & \small{7} \\
1900 \hline
1901 \small{4} & \small{9,014,069} & \small{281,747} & \small{31} & \small{279,912} & \small{344} & \small{219} \\
1902 \hline
1903 \small{5} & \small{281,747} & \small{279,912} & \small{1} & \small{1,835} & \small{355} & \small{226} \\
1904 \hline
1905 \small{6} & \small{279,912} & \small{1,835} & \small{152} & \small{992} & \small{54,304} & \small{34,571} \\
1906 \hline
1907 \small{7} & \small{1,835} & \small{992} & \small{1} & \small{843} & \small{54,659} & \small{34,797} \\
1908 \hline
1909 \small{8} & \small{992} & \small{843} & \small{1} & \small{149} & \small{108,963} & \small{69,368} \\
1910 \hline
1911 \small{9} & \small{843} & \small{149} & \small{5} & \small{98} & \small{599,474} & \small{381,637} \\
1912 \hline
1913 \small{10} & \small{149} & \small{98} & \small{1} & \small{51} & \small{708,437} & \small{451,005} \\
1914 \hline
1915 \small{11} & \small{98} & \small{51} & \small{1} & \small{47} & \small{1,307,911} & \small{832,642} \\
1916 \hline
1917 \small{12} & \small{51} & \small{47} & \small{1} & \small{4} & \small{2,016,348} & \small{1,283,647} \\
1918 \hline
1919 \small{13} & \small{47} & \small{4} & \small{11} & \small{3} & \small{23,487,739} & \small{14,952,759} \\
1920 \hline
1921 \small{14} & \small{4} & \small{3} & \small{1} & \small{1} & \small{25,504,087} & \small{16,236,406} \\
1922 \hline
1923 \small{15} & \small{3} & \small{1} & \small{3} & \small{0} & \small{100,000,000}& \small{63,661,977} \\
1924 \hline
1925 \end{tabular}
1926 \end{center}
1927 \end{table}
1928
1929
1930 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1931 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1932 %% (9) ACKNOWLEDGEMENTS %
1933 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1934 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1935 %%Need to retain e-mail addresses to contact all people who have contributed
1936 %%to thank.
1937 %%Greg Bachelis (greg@math.wayne.edu)
1938 %%Robert Berman (rberman@math.wayne.edu)
1939 %%Feng Lin (flin@ece.eng.wayne.edu)
1940 %%Nick Sahinidis (nikos@uiuc.edu)
1941 %%Adam Van Tuyl, (vantuyl@mast.queensu.ca)
1942 %%Carl Schweiger (carl@titan.princeton.edu)
1943 %%Ken Tindell (ktindell@ssx5.com)
1944 %%Steve Vestal (vestal@htc.honeywell.com)
1945 %%Bob Whitinger (bob@whitinger.net, bob.whitinger@sea.siemens.com)
1946 %%David B. Stewart (dstewart@eng.umd.edu)
1947 %%Johan Bengtsson (johanb@docs.uu.se)
1948 %%Michael J. Burke (mburke@visteon.com)
1949 %%Mark Endicott (mendicot@visteon.com)
1950 %%David Eppstein (eppstein@ics.uci.edu)
1951 %%Cliff Stallings (cliff@eng.wayne.edu)
1952 %%Robert Kakos (robert@enterprise.eng.wayne.edu)
1953 %%Klaus-Peter Zauner (kjz@cs.wayne.edu)
1954 %%Karsten Tinnefeld (tinnefeld@ls2.cs.uni-dortmund.de)
1955 %%Paulette Groen (pgroen@visteon.com)
1956 %%Paula Smith (psmith77@visteon.com)
1957 %%Mircea Munteanu (mmuntean@visteon.com)
1958 %%Adam Gibson (adam.g@virgin.net)
1959 %%Virgil (vmhjr@frii.com)
1960 %%Bob Crosby (b-crosby@ti.com)
1961 %%Una Smith (una.smith@yale.edu)
1962 %%Andrea Blome (ablome@mail.cfigroup.com)
1963 %%Axel Franke (Axel.Franke@physics.umu.se)
1964 %%
1965 %%Need also to include Adam's Web site on my Web page,
1966 %%http://archives.math.utk.edu/articles/atuyl/confrac/
1967 %%
1968 %%Need also to include David Eppstein's Web site
1969 %%http://www.ics.uci.edu/~eppstein/
1970 %%
1971 %%
1972 \begin{acks}
1973 We would like to gratefully acknowledge the assistance
1974 of Greg Bachelis, Robert Berman, Feng
1975 Lin, Nick Sahinidis, Adam Van Tuyl,
1976 Carl Schweiger, Ken Tindell, Steve Vestal,
1977 Bob Whitinger, and David B. Stewart
1978 in finding the areas of
1979 mathematics relevant to the rational number selection
1980 problem. We would also like to
1981 thank Johan Bengtsson, Michael J. Burke,
1982 Mark Endicott, David Eppstein,
1983 David M. Einstein, Mircea Munteanu,
1984 Adam Gibson, and Virgil (of the \texttt{sci.math.num-analysis} newsgroup)
1985 for insight into this problem; Cliff Stallings and
1986 Robert Kakos for support from Wayne State
1987 University's College Of Engineering; Paulette Groen and
1988 Paula Smith for support from Visteon; Bob Crosby for support
1989 from Texas Instruments; Klaus-Peter Zauner, Andrea Blome,
1990 Una Smith, Karsten Tinnefeld, and
1991 Axel Franke for other tool
1992 and logistical support; and the management
1993 team at Visteon for allowing us to pursue this
1994 effort in the workplace.
1995 \end{acks}
1996
1997 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1998 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1999 %% (11) REFERENCES %
2000 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2001 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2002 \nocite{*}
2003 \bibliographystyle{ESUB2ACM}
2004 \begin{thebibliography}{1}
2005
2006 \bibitem{HardyAndWrightClassic}
2007 G.H. Hardy, E.M. Wright,
2008 \newblock{\em An Introduction To The Theory Of Numbers}, ISBN 0-19-853171-0.
2009
2010 \bibitem{Harman}
2011 G. Harman (1998), \newblock{\em Metric Number Theory}, Oxford University Press.
2012
2013 \bibitem{KargaevZ}
2014 P. Kargaev, A. Zhigljavsky (1966),
2015 \newblock{\em Approximation Of Real Numbers By Rationals: Some Metric Theorems},
2016 Journal of Number Theory, 61, 209-225.
2017
2018 \bibitem{KargaevZ1}
2019 P. Kargaev, A. Zhigljavsky (1967),
2020 \newblock{\em Asymptotic Distribution Of The Distance Function To The Farey Points},
2021 Journal of Number Theory, 65, 130-149.
2022
2023 \bibitem{KhinchinClassic}
2024 A. Ya. Khinchin,
2025 \newblock{\em Continued Fractions}, University Of
2026 Chicago Press, 1964; Library Of Congress Catalog Card
2027 Number 64-15819.
2028
2029 \bibitem{LeVeque}
2030 William J. LeVeque,
2031 \newblock{\em Fundamentals Of Number Theory},
2032 Dover Publications, 1977,
2033 ISBN 0-486-68906-9.
2034
2035 \bibitem{OldsClassic}
2036 C. D. Olds,
2037 \newblock{\em Continued Fractions},
2038 Randam House, 1963,
2039 Library Of Congress Catalog Card Number 61-12185.
2040
2041 \bibitem{OreClassic}
2042 Oystein Ore,
2043 \newblock{\em Number Theory And Its History},
2044 ISBN 0-486-65620-9.
2045
2046 \bibitem{SchroederClassic}
2047 M. R. Schroeder,
2048 \newblock{\em Number Theory In Science And Communication},
2049 ISBN 3-540-62006-0.
2050
2051 \end{thebibliography}
2052
2053 \clearpage
2054
2055 \begin{figure*}
2056 \caption{Version Control Information (For Reference Only---Will
2057 Be Removed Before Submission Of Paper)}
2058 \vspace{3.0mm}
2059 \begin{tiny}
2060 \texttt{\LaTeX{} compile date: \today{}.}
2061 \begin{verbatim}
2062 CVS Version Control Information:
2063 $Header: /cvsroot/esrg/sfesrg/esrgpubs/acm0010/paper/acm_paper.tex,v 1.5 2003/04/08 03:57:12 dtashley Exp $.
2064 \end{verbatim}
2065 \end{tiny}
2066 \end{figure*}
2067
2068
2069
2070 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2071 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2072 % (10) CONTACT INFORMATION %
2073 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2074 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2075 %\section{Contact}
2076 %
2077 %Additional supplemental materials (such as Excel
2078 %spreadsheets which generate Farey terms automatically)
2079 %are downloadable from http://www.daveashley.com.
2080 %E-mail addresses and home pages (where applicable)
2081 %for authors are supplied below.
2082 %David T. Ashley:
2083 % daveashley@daveashley.com
2084 % http://www.daveashley.com/
2085 %Joseph P. DeVoe
2086 % jdevoe@visteon.com
2087 %Karl Perttunen
2088 % kperttun@visteon.com
2089 %Cory Pratt
2090 % cpratt2@visteon.com
2091 %Anatoly Zhigljavsky
2092 % zhigljavskyaa@cardiff.ac.uk
2093 % http:\-//\-www.\-cf.\-ac.\-uk/\-uwcc/\-maths/\-zhig\-ljav\-skyaa/
2094
2095 \end{document}
2096
2097 % $Log: acm_paper.tex,v $
2098 % Revision 1.5 2003/04/08 03:57:12 dtashley
2099 % Extra lines in log deleted.
2100 %
2101 % Revision 1.4 2003/04/08 03:49:14 dtashley
2102 % Final keyword expansion change.
2103 %
2104 % Revision 1.3 2003/04/08 03:48:32 dtashley
2105 % Log information at end of file changed for CVS.
2106 %
2107 % ***************** Version 13 *****************
2108 % User: Dashley1 Date: 11/13/00 Time: 3:59a
2109 % Updated in $/ACM Rational Approximation Paper And Algorithms/LaTeX Paper And Graphics
2110 % Final versions for submission to the ACM.
2111 %
2112 % ***************** Version 12 *****************
2113 % User: Dashley1 Date: 11/12/00 Time: 1:03a
2114 % Updated in $/ACM Rational Approximation Paper And Algorithms/LaTeX Paper And Graphics
2115 % Minor error corrected.
2116 %
2117 % ***************** Version 11 *****************
2118 % User: Dashley1 Date: 11/11/00 Time: 6:10a
2119 % Updated in $/ACM Rational Approximation Paper And Algorithms/LaTeX Paper And Graphics
2120 % (Believed) final check-in before submission.
2121 %
2122 % ***************** Version 10 *****************
2123 % User: Dashley1 Date: 11/08/00 Time: 12:51a
2124 % Updated in $/ACM Rational Approximation Paper And Algorithms/LaTeX Paper And Graphics
2125 % Proofreading changes, graphics changes.
2126 %
2127 % ***************** Version 9 *****************
2128 % User: Dashley1 Date: 11/06/00 Time: 11:23p
2129 % Updated in $/ACM Rational Approximation Paper And Algorithms/LaTeX Paper And Graphics
2130 % All revisions completed, out for proofreading.
2131 %
2132 % ***************** Version 8 *****************
2133 % User: Dashley1 Date: 11/06/00 Time: 3:16a
2134 % Updated in $/ACM Rational Approximation Paper And Algorithms/LaTeX Paper And Graphics
2135 % Safety check-in.
2136 %
2137 % ***************** Version 7 *****************
2138 % User: Dashley1 Date: 11/05/00 Time: 1:38a
2139 % Updated in $/ACM Rational Approximation Paper And Algorithms/LaTeX Paper And Graphics
2140 % Safety check-in.
2141 %
2142 % ***************** Version 6 *****************
2143 % User: Dashley1 Date: 11/04/00 Time: 12:47a
2144 % Updated in $/ACM Rational Approximation Paper And Algorithms/LaTeX Paper And Graphics
2145 % Completion of fundamental ideas about concatenated series.
2146 %
2147 % ***************** Version 5 *****************
2148 % User: Dashley1 Date: 11/03/00 Time: 3:08a
2149 % Updated in $/ACM Rational Approximation Paper And Algorithms/LaTeX Paper And Graphics
2150 % Safety check-in, major progress.
2151 %
2152 % ***************** Version 4 *****************
2153 % User: Dashley1 Date: 10/30/00 Time: 6:40p
2154 % Updated in $/ACM Rational Approximation Paper And Algorithms/LaTeX Paper And Graphics
2155 % Completion of CF expansion functionality.
2156 %
2157 % ***************** Version 3 *****************
2158 % User: Dashley1 Date: 10/18/00 Time: 1:08a
2159 % Updated in $/ACM Rational Approximation Paper And Algorithms/LaTeX Paper And Graphics
2160 % IEEE paper ported. Compiles.
2161 %
2162 % ***************** Version 2 *****************
2163 % User: Dashley1 Date: 10/17/00 Time: 8:33p
2164 % Updated in $/ACM Rational Approximation Paper And Algorithms/LaTeX Paper And Graphics
2165 % VC info added.
2166 %
2167 %End of file ACM_PAPER.TEX
2168
2169

dashley@gmail.com
ViewVC Help
Powered by ViewVC 1.1.25