%$Header: /cvsroot/esrg/sfesrg/esrgpubs/acm0010/paper/acm_paper.tex,v 1.5 2003/04/08 03:57:12 dtashley Exp $ \documentclass{esub2acm} \usepackage{amsfonts} \usepackage{amsmath} \usepackage{graphicx} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % NEW NUMBERED ENVIRONMENTS (THEOREMS, EXAMPLES, ETC.) % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \newtheorem{algorithm}{Algorithm} \newtheorem{example}{Example} \newtheorem{mytheorem}{Theorem} %%Sets of real numbers. \newcommand{\realset}{{\mathbb{R}}} \newcommand{\realsetnonneg}{{\mathbb{R}^+}} %% %%Sets of integers. \newcommand{\intset}{{\mathbb{Z}}} \newcommand{\intsetnonneg}{{\mathbb{Z}^+}} \newcommand{\intsetpos}{{\mathbb{N}}} %% %%Sets of rational numbers. \newcommand{\ratset}{{\mathbb{Q}}} \newcommand{\ratsetnonneg}{{\mathbb{Q}^+}} %% %%Sets of irrational numbers. \newcommand{\irratset}{{\mathbb{error}}} \newcommand{\irratsetnonneg}{{\mathbb{error}^+}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % NEW ENVIRONMENT DEFINITIONS % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %The "itemize" environment defined by the IEEE style files didn't seem to have %quite the right appearance for presenting our algorithms. For this reason, the %following environments were defined. Level 0 is flush left with bullets, Level 1 %is slightly more indented, etc. \newenvironment{alglvl0}{\begin{list} {$\bullet$}{\setlength{\labelwidth}{3mm}\setlength{\leftmargin}{6mm}}} {\end{list}} \newenvironment{alglvl1}{\begin{list} {$\bullet$}{\setlength{\labelwidth}{3mm}\setlength{\leftmargin}{6mm}}} {\end{list}} \newenvironment{alglvl2}{\begin{list} {$\bullet$}{\setlength{\labelwidth}{3mm}\setlength{\leftmargin}{6mm}}} {\end{list}} %The following environment is intended for listing properties (of continued fractions, %convergents, etc.). \newenvironment{propenum}{\begin{list} {$\bullet$}{\setlength{\labelwidth}{3mm}\setlength{\leftmargin}{6mm}}} {\end{list}} %The following environment is intended for general enumeration. \newenvironment{generalenum}{\begin{list} {$\bullet$}{\setlength{\labelwidth}{3mm}\setlength{\leftmargin}{6mm}}} {\end{list}} %The following environment is intended for general enumeration with a slight indent. \newenvironment{generalenumindent01}{\begin{list} {$\bullet$}{\setlength{\labelwidth}{3mm}\setlength{\leftmargin}{12mm}}} {\end{list}} %The following environment is for the glossary at the end. \newenvironment{glossaryenum}{\begin{list} {}{\setlength{\labelwidth}{0mm} \setlength{\leftmargin}{4mm} \setlength{\itemindent}{-4mm} \setlength{\parsep}{0.85mm}}} {\end{list}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%Not sure what Greek letter to use to denote the difference %%at the terminal L(x_{MAX}). For that reason will %%leave that option open and define it as a new command, %%so it can be changed in one place. \newcommand{\lxtermdifffuncsymbol}{\psi} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % HYPHENATION EXCEPTION RULES % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %\hyphenation{http:-//-www.-cf.-ac.-uk/-uwcc/-maths/-zhig-ljavskyaa/} \hyphenation{micro-con-trol-ler} \hyphenation{rat-io-met-ric} \hyphenation{rat-ion-al} \hyphenation{Zhig-ljav-sky} \begin{document} \title{On Best Rational Approximations Using\\ Large Integers} \author{David T. Ashley, Joseph P. DeVoe, Karl Perttunen, Cory Pratt\\ Visteon Corporation \and Anatoly Zhigljavsky\\ University Of Cardiff} %\sponsor{Association for Computing Machinery, Inc., % 1515 Broadway, New York, NY 10036, USA % Tel: (212) 555-1212; Fax: (212) 555-2000} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{abstract} Computer processors are equipped with instructions to multiply and divide very large integers. These instructions can be used to economically implement linear scalings from an integer domain to an integer range by choosing a rational number $r_A = h/k$, calculating the product $hx$ using an integer multiplication instruction, and applying an integer division instruction to form $\lfloor{}hx/k\rfloor{}$. This paper presents a novel $O(log \; max(h_{MAX}, k_{MAX}))$ algorithm based on continued fractions for finding the closest rational number $r_A = h/k$ to an arbitrary real number $r_I$ subject to constraints $h \leq h_{MAX}$ and $k \leq k_{MAX}$. Novel results are presented bounding the maximum distance between available choices of $r_A$ when $r_A$ will be chosen only in an interval $[l,r]$, utilizing a second novel $O(log \; max(h_{MAX}, k_{MAX}))$ continued fraction algorithm. Novel results bounding the error due to the necessity of an integer domain and range are presented. The results and techniques presented have relevance to scientific computing (where integer operations may execute much more quickly than floating point operations), to consumer electronics and embedded real-time systems (where the processor may have integer multiplication and division instructions, but no floating-point capability), to the design of special-purpose digital logic (which may implement multiplication and division in hardware), and to the design of mechanical systems (two gears meshed together mechanically implement a ratio which is the ratio of their numbers of teeth). \end{abstract} % A category with only the three required fields %\category{H.4.m} {Information Systems} {Miscellaneous} %A category including the fourth, optional field \category{G.1.2} {Numerical Analysis}{Approximation}[linear approximation] \terms{Algorithms, Theory} \keywords{Rational approximation, Farey series, continued fraction, approximation error, integer lattice.} \begin{bottomstuff} % You might add a line or two here if a version of your article appeared % previously, or if the work was supported by an organization or conducted % under a grant. %\begin{authinfo} %\name{David T. Ashley, Joseph P. DeVoe, Cory Pratt, Karl Perttunen} use if there are several authors with different addresses %\address{P.O. Box 1221, Dublin, OH 43017-6221} %\affiliation{} use if there are several authors with different affiliations %\biography{} optional; not generally used. %\end{authinfo} % Here's a neat thing: all you have to put in your document is the command %"\permission" and LaTeX automatically enters the complete text of the %"Permission to copy..." boilerplate \permission \end{bottomstuff} \markboth{D.T. Ashley, J.P. DeVoe, K. Perttunen, C. Pratt, and A. Zhigljavsky} {On Best Rational Approximations Using Large Integers} \maketitle %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % INTRODUCTION % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Introduction} Modern computer instruction sets contain instructions for multiplication and division of large integers. In many applications, the mainstay of efficient software design is the ability to phrase a computational problem in a form which is economically executed by the hardware available. In a very capable processor (such as a workstation or supercomputer), approximations involving only integers may be attractive because integer instructions execute more quickly than floating-point instructions, or because the processor design allows them to execute concurrently with floating-point instructions. In very inexpensive processors (such as those used in consumer electronics), approximations involving only integers may be attractive because the processor has no floating-point capability. This paper presents results and techniques for making optimal use of integer multiplication and division instructions to approximate functions of the form $F(x) = r_I x$, $r_I \in \realsetnonneg$ using functions in the form of (\ref{eq:fundeqn}).\footnote{Mnemonic for $r_I$ and $r_A$: \emph{I}=ideal, \emph{A}=actual. In this paper, $\realsetnonneg$, $\intsetnonneg{}$, and $\intsetpos{}$ are the sets of non-negative real numbers, non-negative integers, and positive integers, respectively.} \begin{equation} \label{eq:fundeqn} J(x) = \lfloor r_A \lfloor x \rfloor \rfloor = \left\lfloor\frac{h \lfloor x \rfloor}{k}\right\rfloor{}; h \in \intsetnonneg{}, \leq h_{MAX} ; k \in \intsetpos{}, \leq k_{MAX}. \end{equation} Because modern processors can multiply and divide \emph{very} large integers (32- and 64-bit integers are typical), choosing $h$ and $k$ so as to place $r_A = h/k$ as close as possible to an arbitrary $r_I \in \realsetnonneg$ involves a very large search space, and an efficient algorithm is necessary for computational viability. Section \ref{sec:fareyseries} presents a summary of important properties of the Farey series, and Section \ref{sec:continuedfractions} presents a summary of important properties of the apparatus of continued fractions.\footnote{The algorithms presented are based on the properties of the Farey series and the apparatus of continued fractions---because these are topics from number theory that seldom find application in practical computer arithmetic, a summary is necessary for readability.} Section \ref{sec:kmaxonlycase} presents a novel $O(log \; k_{MAX})$ continued fraction algorithm for finding the best rational approximations $r_A = h/k$ to an arbitrary $r_I \in \realsetnonneg$ subject to the constraint $k \leq k_{MAX}$. Section \ref{sec:hmaxandkmaxcase} extends the algorithm of Section \ref{sec:kmaxonlycase} to the case where both $h$ and $k$ are constrained, $h \leq h_{MAX} \wedge k \leq k_{MAX}$; and presents a novel $O(log \; max(h_{MAX}, k_{MAX}))$ continued fraction algorithm for finding the best rational approximations in the rectangular area of the integer lattice formed by the constraints. Section \ref{sec:intervalcase} presents novel results bounding the distance between rational numbers in a rectangular area of the integer lattice when $r_I \in [l,r]$. Section \ref{sec:endtoenderror} presents a method for bounding the end-to-end approximation error as a function of $r_A-r_I$. Section \ref{sec:designexample} provides a practical design example illustrating the techniques. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{The Farey Series Of Order $N$} \label{sec:fareyseries} The \emph{Farey series of order $N$}, denoted $F_{N}$, is the ordered set of all irreducible rational numbers $h/k$ in the interval [0,1] with a denominator $k\leq N$. For example, the Farey series of order 7, $F_7$, is \begin{equation} \label{eq:eq0045} F_7 = \left\{ {\frac{0}{1},\frac{1}{7},\frac{1}{6}, \frac{1}{5},\frac{1}{4},\frac{2}{7}, \frac{1}{3},\frac{2}{5},\frac{3}{7},\frac{1}{2},\frac{4}{7}, \frac{3}{5},\frac{2}{3},\frac{5}{7},\frac{3}{4}, \frac{4}{5},\frac{5}{6},\frac{6}{7},\frac{1}{1}} \right\}. \end{equation} The distribution of Farey rational numbers in [0,1] is repeated in any $[n,n+1]$, $n\in \intsetnonneg$; so the distribution of Farey rationals in [0,1] supplies complete information about the distribution in all of $\realsetnonneg$.\footnote{We stretch the proper nomenclature by referring to sequential rational numbers outside the interval $[0,1]$ as Farey terms or as part of $F_N$, which, in the strictest sense, they are not. All of the results presented in this paper (except Sections \ref{subsec:numberofelements} and \ref{subsec:probresults}) apply everywhere in $\realsetnonneg$, and this abuse is not harmful.} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Properties Of Sequential Elements} \begin{mytheorem} \label{thm:thm01} If $H/K$ and $h/k$ are two successive terms of $F_{N}$, then \end{mytheorem} \begin{equation} \label{eq:eq0048} K h - H k = 1. \end{equation} \emph{Note:} This condition is necessary but not sufficient for $h/k$ to be the Farey successor of $H/K$. In general, there is more than one $h/k$ with $k \leq N$ such that $Kh - Hk = 1$. \begin{proof} See \cite{HardyAndWrightClassic} p.23, \cite{LeVeque} p.222. \end{proof} \begin{mytheorem} \label{thm:thm05} If $H/K$ is a term of $F_{N}$, the successor of $H/K$ in $F_{N}$ is the $h/k$ satisfying $Kh-Hk=1$ with the largest denominator $k\leq N$. \end{mytheorem} \begin{proof} Any potential successor of $H/K$ which meets $Kh-Hk=1$ can be formed by adding $1/Kk$ to $H/K$ (\ref{eq:eq0055}). \begin{equation} \label{eq:eq0055} Kh - Hk = 1 \to \frac{h}{k} = \frac{{1 + Hk}}{{Kk}} = \frac{H}{K} + \frac{1}{Kk} \end{equation} If $h/k$ and $h'/k'$ both satisfy $Kh-Hk=1$ with $k' N. \end{equation} \emph{Note:} This condition is necessary but not sufficient for $h/k$ to be the Farey successor of $H/K$. \begin{proof} See \cite{HardyAndWrightClassic} p.23. \end{proof} \begin{mytheorem} \label{thm:thm04} If $h_{j-2}/k_{j-2}$, $h_{j-1}/k_{j-1}$, and $h_{j}/k_{j}$ are three consecutive terms of $F_{N}$, then: \end{mytheorem} \begin{equation} \label{eq:eq0051} h_{j} = \left\lfloor {\frac{{k_{j-2} + N}}{{k_{j - 1} }}} \right\rfloor h_{j - 1} - h_{j-2} \end{equation} \begin{equation} \label{eq:eq0052} k_{j} = \left\lfloor {\frac{{k_{j-2} + N}}{{k_{j - 1} }}} \right\rfloor k_{j - 1} - k_{j-2} \end{equation} \emph{Notes:} (1)Theorem \ref{thm:thm04} gives recursive formulas for generating successive terms in $F_N$ if two consecutive terms are known. (2)Equations (\ref{eq:eq0051}) and (\ref{eq:eq0052}) can be solved to allow generation of terms in the decreasing direction (\ref{eq:eq0053}, \ref{eq:eq0054}). \begin{equation} \label{eq:eq0053} h_j = \left\lfloor {\frac{{k_{j + 2} + N}}{{k_{j + 1} }}} \right\rfloor h_{j + 1} - h_{j + 2} \end{equation} \begin{equation} \label{eq:eq0054} k_j = \left\lfloor {\frac{{k_{j + 2} + N}}{{k_{j + 1} }}} \right\rfloor k_{j + 1} - k_{j + 2} \end{equation} \begin{proof} See \cite{SchroederClassic} p.83. \end{proof} In general, given only a single irreducible rational number $h/k$, there is no method to find the immediate predecessor or successor in $F_N$ without some iteration (Equations \ref{eq:eq0051}, \ref{eq:eq0052}, \ref{eq:eq0053}, and \ref{eq:eq0054} require two successive elements). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Number Of Elements} \label{subsec:numberofelements} The number of elements in $F_N$ is approximately $3 N^2 / \pi{}^2$.\footnote{This is a classic result from number theory, and its basis isn't discussed here. In this instance we mean $F_N$ strictly in the interval $[0,1]$.} $F_{255=2^8-1}$ contains about 20,000 elements, $F_{65,535=2^{16}-1}$ contains about 1.3 billion elements, $F_{2^{32}-1}$ contains about $5.6 \times 10^{18}$ elements, and $F_{2^{64}-1}$ contains about $1.0 \times 10^{38}$ elements. The large numbers of elements in the Farey series of the orders used in practice make it impractical to linearly search the Farey series to find the best rational approximations.\footnote{For example, a particularly naive approach might be to start at an integer $i$, where three successive terms in $F_N$ are $(Ni-1)/N$, $i/1$, and $(Ni+1)/N$, and to use (\ref{eq:eq0051}) through (\ref{eq:eq0054}) to linearly search upward or downward until the real number of interest is enclosed. Even in $F_{2^{32}-1}$, searching 1,000,000 rational numbers per second, such a search would require up to about 90,000 years.} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Probabilistic Results On $| r_I - r_A |$} \label{subsec:probresults} If rational numbers of the form $r_A = h/k$, subject to the constraint $k \leq k_{MAX}$, are used to approximate arbitrary real numbers $r_I$, it might not be clear how close we can ``typically'' choose $r_A$ to an aribtrary $r_I$ under the constraint. We consider different asymptotics for the precision of the approximation of an arbitrary $r_I$ by a rational number $r_A=h/k$ with $k \leq k_{MAX}$. For simplicity of notation we denote $\alpha= r_I$ and $N=k_{ \rm MAX }$ and assume, without loss of generality, that $ \alpha \in [0,1]$. We are thus interested in the asymptotic behaviour, when $N \rightarrow \infty$, of the quantity $$ %\begin{equation} \label{eq:dist} \rho_N(\alpha) = \min_{h/k \in F_N} \left|\alpha - h/k\right|\, , $$ %\end{equation} which is the distance between $\alpha$ and $F_N$, the Farey series of order $N$. The worst--case scenario is not very interesting: from the construction of the Farey series we observe that for a fixed $N$ the longest intervals between the neighbours of $F_N$ are $[0,1/N]$ and $[1-1/N,1]$ and therefore for all $N$ \begin{equation} \label{eq:max_error} \max_{\alpha \in [0,1]} \rho_N(\alpha) = \frac{1}{2N}\, . \end{equation} (This supremum is achieved at the points $1/(2N)$ and $1-1/(2N)$.) However, such behaviour of $\rho_N(\alpha)$ is not typical: as is shown below, typical values of the approximation error $\rho_N(\alpha)$ are much smaller. First consider the behaviour of $\rho_N(\alpha)$ for almost all $\alpha \in [0,1]$.\footnote{ A statement is true for almost all $\alpha \in [0,1]$ if the measure of the set where this statement is wrong has measure zero.} We then have (see \cite{KargaevZ}, \cite{Harman}) that for almost all $\alpha \in [0,1]$ and any $\varepsilon >0$, (\ref{eq:liminf}) and (\ref{eq:limsup}) hold. \begin{equation} \label{eq:liminf} \lim_{N\rightarrow\infty}\rho_N(\alpha) N^2 \log^{1+\varepsilon} N = + \infty, \quad \liminf_{N\rightarrow\infty} \rho_N(\alpha) N^2 \log N = 0 \end{equation} \begin{equation} \label{eq:limsup} \limsup_{N\rightarrow\infty} \frac{ \rho_N(\alpha) N^2 }{ \log N } = + \infty, \quad \lim_{N\rightarrow\infty} \frac{ \rho_N(\alpha) N^2 }{ \log^{1+\varepsilon} N } = 0 \end{equation} Even more is true: in (\ref{eq:liminf}) and (\ref{eq:limsup}) one can replace $\log N$ by $\log N \log \log N $, $\log N \log \log N \log \log \log N$, and so on. Analogously, $\log^{1+\varepsilon} N$ could be replaced by $\log N (\log \log N)^{1+\varepsilon} $, $\log N \log \log N (\log \log \log N)^{1+\varepsilon}$, and so on. These statements are analogues of Khinchin's metric theorem, the classic result in metric number theory, see e.g. \cite{Harman}. The asymptotic distribution of the suitably normalised $\rho_N(\alpha)$ was derived in \cite{KargaevZ1}. A main result of this paper is that the sequence of functions $N^2\rho_N(\alpha)$ converges in distribution, when $N\rightarrow \infty$, to the probability measure on $[0, \infty)$ with the density given by (\ref{eq:dens-ab}). \begin{equation} \label{eq:dens-ab} {p}(\tau) = \left\{\begin{array}{l} 6/\pi^2, \hfill\mbox{ if $0 \leq \tau \leq \frac{1}{2}$ }\\ \\ \frac{6}{\pi^2 \tau} \left(1 + \log \tau - \tau \right), \hfill\mbox{ if $\frac{1}{2}\leq \tau\leq 2 $ } \\ \\ \frac{ 3}{\pi^2 \tau}\left(2\log(2 \tau)\! -\!4\log(\sqrt{\tau}\!+\!\sqrt{\tau\!-\!2})\! -\! (\sqrt{\tau}\!-\!\sqrt{\tau\!-\!2})^2 \right), \\ \hfill \mbox{ if $2 \leq \tau < \infty $ } \\ \end{array} \right. \end{equation} This means that for all $a,A$ such that $01$ } \end{array} \right. \end{equation} In particular, the average of the approximation error $\rho_N (\alpha)$ asymptotically equals \begin{equation} \label{eq:average_as} \int_{0}^1 \rho_N(\alpha) d\alpha = \frac{3}{\pi^2} \frac{\log N}{N^2} + O\left(\frac{1}{N^2}\right), \;\;\;\; N\rightarrow \infty \,. \end{equation} Comparison of (\ref{eq:average_as}) with (\ref{eq:limsup}) shows that the asymptotic behavior of the average approximation error $\int \rho_N(\alpha) d\alpha$ resembles the behavior of the superior limit of $\rho_N(\alpha)$. Even this limit decreases much faster than the maximum error $\max_{\alpha } \rho_N(\alpha)$, see (\ref{eq:max_error}): for typical $\alpha$ the rate of decrease of $\rho_N(\alpha)$, when $ N\rightarrow \infty ,$ is, roughly speaking, $1/N^2$ rather than $1/N$, the error for the worst combination of $\alpha$ and $N$. These results show that there is a significant advantage to using the Farey series as the set from which to choose rational approximations, rather than more naively using only rational numbers with the maximum denominator $k_{MAX}$ (as is often done in practice). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{The Apparatus Of Continued Fractions} \label{sec:continuedfractions} An \emph{n-th order finite simple continued fraction} is a fraction in the form of (\ref{eq:eq0057}), where $a_0 \in \intsetnonneg$ and $a_{k} \in \intsetpos$ for $k > 0$. To ensure that two continued fractions which represent the same number can't be written differently, we also require that the final element $a_n$ not be equal to 1 (except when representing the integer 1).\footnote{If $a_n=1$, the continued fraction can be reduced in order by one and $a_{n-1}$ can be increased by one while still preserving the value of the continued fraction.} A continued fraction in the form of (\ref{eq:eq0057}) is denoted $[a_0; a_1, a_2, \ldots, a_n]$, and each $a_k$ is called an \emph{element} or \emph{partial quotient}. \begin{equation} \label{eq:eq0057} a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{\;\;\;\;\;\;\;\;\;\;\;\;\;\;\ldots + \cfrac{1}{a_n}}}} = [a_0; a_1, a_2, \ldots , a_n] \end{equation} Continued fractions provide an alternate apparatus for representing real numbers. The form of (\ref{eq:eq0057}) has important properties which are presented without proof. \begin{propenum} \item Every rational number can be represented by a finite simple continued fraction $[a_{0};a_{1},a_{2},\ldots{} ,a_{n}]$. \item Each unique $[a_{0};a_{1},a_{2},\ldots{} ,a_{n}]$ corresponds to a uniquely valued rational number. \end{propenum} Without proof, we present the following algorithm for finding partial quotients $a_k$ of an arbitrary non-negative rational number $a/b$. \begin{algorithm}\label{alg:akgenalg}\end{algorithm} \begin{alglvl0} \item $k:=-1$. \item $divisor_{-1} := a$. \item $remainder_{-1} := b$. \item Repeat \begin{alglvl1} \item $k := k + 1$. \item $dividend_k := divisor_{k-1}$. \item $divisor_k := remainder_{k-1}$. \item $a_k := dividend_k \; div \; divisor_k$. \item $remainder_k := dividend_k \; mod \; divisor_k$. \end{alglvl1} \item Until ($remainder_k = 0$). \end{alglvl0} Without proof, we present the following properties of Algorithm \ref{alg:akgenalg}. \begin{propenum} \item The algorithm will produce the same $[a_{0};a_{1},a_{2},\ldots{} ,a_{n}]$ for any $(ia)/(ib)$, $i \in \intsetpos{}$, i.e. the rational number $a/b$ need not be reduced before applying the algorithm. \item The algorithm will always terminate (i.e. the continued fraction representation $[a_{0};a_{1},a_{2},\ldots{} ,a_{n}]$ will be finite). \end{propenum} The apparatus of continued fractions is best viewed as an alternate apparatus for representing real numbers, and Algorithm \ref{alg:akgenalg} is best viewed as an algorithm for determining in which partition a rational number lies, in the same sense that long division successively partitions a rational number as each successive decimal digit is obtained. To say that the first three digits of a real number $x$ are ``3.14'' is logically equivalent to saying that $3.14 \leq x < 3.15$ (i.e. that $x$ lies in a certain partition). In the same sense, (\ref{eq:cfeq01}), (\ref{eq:cfeq02}), and (\ref{eq:cfeq03}) are valid equivalences. \begin{equation} \label{eq:cfeq01} (x=[a_0] \vee x=[a_0; \ldots ] ) \leftrightarrow (a_0 \leq x < a_0 + 1) \end{equation} \begin{equation} \label{eq:cfeq02} (x=[a_0; a_1] \vee x=[a_0; a_1, \ldots ] ) \leftrightarrow \left( { a_0 + \frac{1}{a_1 + 1} < x \leq a_0 + \frac{1}{a_1} } \right) \end{equation} \begin{equation} \label{eq:cfeq03} \begin{array}{c} (x=[a_0; a_1, a_2] \vee x=[a_0; a_1, a_2, \ldots ] ) \vspace{0.05in}\\ \updownarrow \vspace{0.0in}\\ \left( { a_0+\cfrac{1}{a_1 + \cfrac{1}{a_2}} \leq x < a_0+\cfrac{1}{a_1 + \cfrac{1}{a_2+1}} } \right) \end{array} \end{equation} The form of (\ref{eq:cfeq01}), (\ref{eq:cfeq02}), and (\ref{eq:cfeq03}) could be continued indefinitely to show the defining inequality for higher-order partitions. From the form of (\ref{eq:cfeq01}), (\ref{eq:cfeq02}), and (\ref{eq:cfeq03}) it can be readily seen that irrational numbers have a non-terminating continued fraction representation, and that the algorithm for finding that representation would be symbolic and involve successively determining higher order partial quotients (i.e. at each step, in which partition the irrational number lies). The algorithm for determining the partial quotients of an irrational number isn't discussed in this paper. In most practical applications, $r_I$ is known empirically to at least several decimal places, and the most practical technique is to use the best known decimal approximation as the starting point to apply Algorithm \ref{alg:akgenalg}. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % (4)(F)(v) CONVERGENTS OF A CONTINUED FRACTION % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% The \emph{kth convergent} of a finite simple continued fraction $[a_{0};a_{1},a_{2},\ldots{},a_{n}]$, denoted $s_{k} = p_k/q_k$, is the rational number corresponding to the continued fraction $[a_{0};a_{1},a_{2},\ldots{},a_{k}]$, $k \leq n$. Equations (\ref{eq:eq0059}) through (\ref{eq:eq0064}) define the canonical way to construct all $s_{k}=p_{k}/q_{k}$ from all $a_{k}$. \begin{equation} \label{eq:eq0059} p_{ - 1} = 1 \end{equation} \begin{equation} \label{eq:eq0060} q_{ - 1} = 0 \end{equation} \begin{equation} \label{eq:eq0061} p_0 = a_0 = \left\lfloor {r_I } \right\rfloor \end{equation} \begin{equation} \label{eq:eq0062} q_0 = 1 \end{equation} \begin{equation} \label{eq:eq0063} p_k = a_k p_{k - 1} + p_{k - 2} \end{equation} \begin{equation} \label{eq:eq0064} q_k = a_k q_{k - 1} + q_{k - 2} \end{equation} When $p_{k}$ and $q_{k}$ (the numerator and denominator of the $k$th convergent $s_{k}$) are formed as specified by (\ref{eq:eq0059}) through (\ref{eq:eq0064}), convergents $s_{k}=p_{k}/q_{k}$ have the following properties, which are presented without proof. \begin{propenum} \item Each even-ordered convergent $s_{k} = p_k/q_k = [a_{0}; a_{1}, a_{2}, \ldots{}, a_{k}]$ is less than $[a_{0}; a_{1}, a_{2}, \ldots{}, a_{n}]$, and each odd-ordered convergent $s_{k}$ is greater than $[a_{0}$; $a_{1}$, $a_{2}$, $\ldots{}$, $a_{n}]$, with the exception of the final convergent $s_{k}$, $k=n$, which is equal to $[a_{0}; a_{1}, a_{2}, \ldots{}, a_{n}]$. \item Each convergent is irreducible; that is, $p_k$ and $q_k$ are coprime. \item Each $q_{k}$ is greater than $q_{k-1}$; that is, the denominators of convergents are ever-increasing. Furthermore, the denominators of convergents increase at a minimum rate that is exponential (Eq. \ref{eq:skminexpincrease}), \cite{KhinchinClassic} Theorem 12. \begin{equation} \label{eq:skminexpincrease} q_k \geq 2^{\frac{k-1}{2}}, \; k \geq 2 \end{equation} \end{propenum} An \emph{intermediate fraction} is a fraction of the form \begin{equation} \label{eq:intermediatefractiondef} \frac{i p_k + p_{k-1}}{i q_k + q_{k-1}}, \; i < a_{k+1}. \end{equation} It can be seen by comparing (\ref{eq:intermediatefractiondef}) with (\ref{eq:eq0063}) and (\ref{eq:eq0064}) that an intermediate fraction can be denoted compactly by the continued fraction representation of a convergent, with the final element adjusted downward. For example, if $[a_0; a_1, a_2, \ldots , a_{k-1}]$ and $[a_0; a_1, a_2, \ldots , a_{k-1}, a_k]$, $k \leq n$, are convergents; $[a_0; a_1, a_2, \ldots , a_{k-1}, 1]$, $[a_0$; $a_1$, $a_2$, $\ldots$, $a_{k-1}$, $2]$, \ldots{}, and $[a_0; a_1, a_2, \ldots , a_{k-1}, a_k -1]$ are intermediate fractions. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Choosing $r_A = h/k$ Subject To $k \leq k_{MAX}$} \label{sec:kmaxonlycase} Finding the best rational approximation $r_A=h/k$ to an arbitrary $r_I \in \realsetnonneg$ subject only to the constraint $k \leq k_{MAX}$ is equivalent to the problem of finding the two members of $F_{k_{MAX}}$ which enclose $r_I$. Potential naive algorithms include building $F_{k_{MAX}}$ starting at an integer [$O(k_{MAX}^2$)], building $F_{k_{MAX}}$ starting at a rational number with a large prime denominator [$O(k_{MAX})$], and building the Stern-Brocot tree [$O(k_{MAX})$]. For $k_{MAX}$ of a few hundred or less, any of these algorithms are satisfactory, and they can be carried out even with ordinary spreadsheet software, such as \emph{Microsoft Excel}. However, for $k_{MAX}$ typical of the more powerful microcontrollers used in consumer electronics ($2^{16}$ or $2^{32}$), and particularly for $k_{MAX}$ reflecting the integer arithmetic capability of workstations and supercomputers ($2^{32}$, $2^{64}$, or larger), $O(k_{MAX}^2)$ and $O(k_{MAX})$ algorithms are not computationally viable. This section presents a novel $O(log \; k_{MAX})$ algorithm which is suitable for finding best rational approximations even in Farey series of very large order, based on the apparatus of continued fractions. \subsection{Finding Best Rational Approximations With $r_I \in \hspace{-0.85em} / \hspace{0.25em} F_{k_{MAX}}$} \begin{mytheorem} \label{thm:thm06} For a non-negative rational\footnote{Although it isn't discussed in this paper, it isn't required that a number be rational in order to apply this theorem. As emphasized by (\ref{eq:cfeq01}), (\ref{eq:cfeq02}), and (\ref{eq:cfeq03}), the process of obtaining continued fraction partial quotients is essentially a process of determining in which partition a number lies. All numbers in the same partition---rational or irrational---have the same Farey neighbors in all Farey series up to a certain order. If the partial quotients of an irrational number can be obtained up through $a_k$ s.t. $s_k = p_k/q_k$ is the highest-order convergent with $q_k \leq N$, then this theorem can be applied. Knowledge of all $a_0 \ldots{} a_k$ is equivalent to the knowledge that the number is in a partition where all numbers in that partition have the same Farey neighbors in all Farey series up through order $q_{k+1}-1$.} number $a/b$ not in $F_N$ which has a continued fraction representation $[a_0;a_1,a_2,\ldots{} ,a_n]$, the highest-order convergent $s_k = p_k/q_k$ with $q_k \leq N$ is one neighbor\footnote{By neighbors in $F_N$ we mean the rational numbers in $F_N$ immediately to the left and immediately to the right of $a/b$.} to $a/b$ in $F_N$, and the other neighbor in $F_N$ is\footnote{Theorem \ref{thm:thm06} is a somewhat stronger statement about best approximations than Khinchin makes in \cite{KhinchinClassic}, Theorem 15. We were not able to locate this theorem or a proof in print, but this theorem is understood within the number theory community. It appears on the Web page of David Eppstein in the form of a `C'-language computer program, \texttt{http://www.ics.uci.edu/\~{}{}eppstein/numth/frap.c}. Although Dr. Eppstein phrases the solution in terms of modifying a partial quotient, his approach is equivalent to (\ref{eq:eq0065}).} \end{mytheorem} \begin{equation} \label{eq:eq0065} \frac{{\displaystyle{\left\lfloor {\frac{{N - q_{k - 1} }}{{q_k }}} \right\rfloor} p_k + p_{k - 1} }}{{\displaystyle{\left\lfloor {\frac{{N - q_{k - 1} }}{{q_k }}} \right\rfloor} q_k + q_{k - 1} }}. \end{equation} \begin{proof} First, it is proved that the highest-order convergent $s_k = p_k/q_k$ with $q_k \leq N$ is one of the two neighbors to $a/b$ in $F_N$. $s_k \in F_N$, since $q_k \leq N$. By \cite{KhinchinClassic}, Theorem 9, the upper bound on the difference between $a/b$ and arbitrary $s_k$ is given by \begin{equation} \label{eq:eq0066} \left| {\frac{a}{b} - \frac{{p_k }}{{q_k }}} \right| < \frac{1}{{q_k q_{k + 1} }}. \end{equation} For two consecutive terms in $F_N$, $Kh-Hk=1$. For a Farey neighbor $H/K$ to $s_k$ in $F_N$, (\ref{eq:eq0067}) must hold. \begin{equation} \label{eq:eq0067} \frac{1}{q_k N} \leq \left| {\frac{H}{K} - \frac{p_k}{q_k}} \right| \end{equation} $q_{k+1}>N$, because $q_{k+1}>q_k$ and $p_k/q_k$ was chosen to be the highest-order convergent with $q_k\leq N$. Using this knowledge and combining (\ref{eq:eq0066}) and (\ref{eq:eq0067}) leads to (\ref{eq:eq0069}). \begin{equation} \label{eq:eq0069} \left| {\frac{a}{b} - \frac{{p_k }}{{q_k }}} \right| < \frac{1}{{q_k q_{k + 1} }} < \frac{1}{q_k N} \leq \left| {\frac{H}{K} - \frac{p_k}{q_k}} \right| \end{equation} This proves that $s_k$ is one neighbor to $a/b$ in $F_N$. The apparatus of continued fractions ensures that the highest order convergent $s_k$ with $q_k\leq N$ is closer to $a/b$ than to any neighboring term in $F_N$. Thus, there is no intervening term of $F_N$ between $s_k$ and $a/b$. If $k$ is even, $s_ka/b$. It must be proved that (\ref{eq:eq0065}) is the other Farey neighbor. For brevity, only the case of $k$ even is proved: the case of $k$ odd is symmetrical. (\ref{eq:eq0065}) is of the form (\ref{eq:eq0071}), where $i \in \intsetnonneg$. \begin{equation} \label{eq:eq0071} \frac{{ip_k + p_{k - 1} }}{{iq_k + q_{k - 1} }} \end{equation} $k$ is even, $s_k < a/b$, and the two Farey terms enclosing $a/b$, in order, are \begin{equation} \label{eq:eq0072} \frac{p_k }{q_k },\frac{ip_k + p_{k - 1} }{iq_k + q_{k - 1} }. \end{equation} Applying the $Kh - Hk = 1$ test, (\ref{eq:eq0074}), gives the result of 1, since by theorem (\cite{KhinchinClassic}, Theorem 2), $q_kp_{k-1}-p_kq_{k-1}=(-1)^k$. \begin{equation} \label{eq:eq0074} \begin{array}{*{20}c} {(q_k )(ip_k + p_{k - 1} ) - (p_k )(iq_k + q_{k - 1} ) = 1} \end{array} \end{equation} Thus, every potential Farey neighbor of the form (\ref{eq:eq0071}) meets the $Kh - Hk = 1$ test. It is also straightforward to show that \emph{only} potential Farey neighbors of the form (\ref{eq:eq0071}) can meet the $Kh-Hk=1$ test, using the property that $p_k$ and $q_k$ are coprime. It must be established that a rational number of the form (\ref{eq:eq0071}) is irreducible. This result comes directly from (\ref{eq:eq0074}), since if the numerator and denominator of (\ref{eq:eq0065}) or (\ref{eq:eq0071}) are not coprime, the difference of 1 is not possible. The denominator of (\ref{eq:eq0065}) can be rewritten as \begin{equation} \label{eq:eq0076} N - \left[ {\left( {N - q_{k - 1} } \right)\bmod q_k } \right] \in \left\{ {N - q_k + 1,...,N} \right\}. \end{equation} It must be shown that if one irreducible rational number---namely, the rational number given by (\ref{eq:eq0065})---with a denominator $\in \{ N-q_k+1,\ldots{} ,N \}$ meets the $Kh - Hk = 1$ test, there can be no other irreducible rational number in $F_N$ with a larger denominator which also meets this test. Given (\ref{eq:eq0076}), and given that \emph{only} rational numbers of the form (\ref{eq:eq0071}) can meet the $Kh-Hk=1$ test, and given that any number of the form (\ref{eq:eq0071}) is irreducible, the irreducible number meeting the $Kh-Hk=1$ test with the next larger denominator after the denominator of (\ref{eq:eq0065}) will have a denominator $\in \{ N+1, \ldots, N+q_k \}$. Thus, no other irreducible rational number in $F_N$ besides that given by (\ref{eq:eq0065}) with a larger denominator $\leq N$ and which meets the $Kh - Hk = 1$ test can exist; therefore (\ref{eq:eq0065}) is the other enclosing Farey neighbor to $a/b$ in $F_N$. \end{proof} Theorem \ref{thm:thm06} suggests an algorithm for determining best approximations to a rational $r_I =a/b \notin F_{k_{MAX}}$ subject to the constraint $k \leq k_{MAX}$. \begin{algorithm}\label{alg:bratrnnifnalg}\end{algorithm} \begin{alglvl0} \item $k := -1$. \item $divisor_{-1} := a$. \item $remainder_{-1} := b$. \item $p_{-1} := 1$. \item $q_{-1} := 0$. \item Repeat \begin{alglvl1} \item $k := k + 1$. \item $dividend_k := divisor_{k-1}$. \item $divisor_k := remainder_{k-1}$. \item $a_k := dividend_k \; div \; divisor_k$. \item $remainder_k := dividend_k \; mod \; divisor_k$. \item If $k=0$ then $p_k := a_k$ else $p_k := a_k p_{k-1} + p_{k-2}$. \item If $k=0$ then $q_k := 1$ else $q_k := a_k q_{k-1} + q_{k-2}$. \end{alglvl1} \item Until ($q_k > k_{MAX}$). \item $s_{k-1} = p_{k-1}/q_{k-1}$ will be one Farey neighbor to $a/b$ in $F_{k_{MAX}}$. Apply (\ref{eq:eq0065}) to obtain the other Farey neighbor. \end{alglvl0} Algorithm \ref{alg:bratrnnifnalg} builds the partial quotients $a_k$ and convergents $s_k = p_k/q_k$ of $a/b$ only as far as required to obtain the highest-order convergent with $q_k \leq N$; thus the number of iterations required is tied to $k_{MAX}$, rather than to the precision of $a/b$. It is easy to see that Algorithm \ref{alg:bratrnnifnalg} is $O(log \; k_{MAX})$, since the the denominators of convergents $q_k$ have a minimum exponential rate of increase (\ref{eq:skminexpincrease}).\footnote{Although Algorithm \ref{alg:bratrnnifnalg} is the best known algorithm for finding Farey neighbors, it is an oversimplification to state that Algorithm \ref{alg:bratrnnifnalg} is $O(log \; k_{MAX})$. In the classical sense---speaking only in terms of numbers of operations and assuming that each type of operation takes the same amount of time regardless of the data---the algorithm is $O(log \; k_{MAX})$. However, when applying the algorithm for $a$, $b$, and $k_{MAX}$ much larger than the native data sizes of the computer used, one must use some sort of arbitrary-precision or long integer calculation package, and the calculation times of such packages are probably between $O(log \; N)$ and $O(N)$ with respect to the data values. Taking this into account, the algorithm may be as poor as $O(N \; log \; N)$ for data much larger than accomodated by the computer used. However, this is not an impediment to practical calculations. The rational approximation software packaged with this paper (submitted to CALGO) will find neighbors within the Farey series of order $2^{128}$ with a calculation time of just a few seconds on a personal computer, and will find neighbors within the Farey series of order $2^{1,000}$ with a calculation time of less than 60 seconds.} \subsection{Finding Best Rational Approximations With $r_I \in F_{k_{MAX}}$} The case where $r_I \in F_{k_{MAX}}$ corresponds to the case where $r_I$ is at the edge of a partition, in the sense suggested by (\ref{eq:cfeq01}), (\ref{eq:cfeq02}), and (\ref{eq:cfeq03}). In this case, the highest-order convergent $s_n = p_n/q_n = r_I \in F_{k_{MAX}}$, and (\ref{eq:eq0065}) supplies the right Farey neighbor to $r_I$ if $n$ is even, or the left Farey neighbor to $r_I$ if $n$ is odd. In the former case (\ref{eq:eq0053}) and (\ref{eq:eq0054}) can be used to obtain the left Farey neighbor, and in the latter case (\ref{eq:eq0051}) and (\ref{eq:eq0052}) can be used to obtain the right Farey neighbor. The second half of the proof of Theorem \ref{thm:thm06} applies. Thus, finding the neighbors in $F_{k_{MAX}}$ to an arbitrary $r_I = a/b \in F_{k_{MAX}}$ is also an $O(log \; k_{MAX})$ procedure, and easily accomplished using the apparatus of continued fractions. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Choosing $r_A = h/k$ Subject To $h \leq h_{MAX}$ And $k \leq k_{MAX}$} \label{sec:hmaxandkmaxcase} Up to this point, only the case of constrained $k$ has been considered. However, in a practical application, $h$ is also typically constrained, usually by the size of the operands and results that machine multiplication and division instructions can accomodate. When $h$ and $k$ are both constrained, $h \leq h_{MAX} \wedge k \leq k_{MAX}$, the set of rational numbers $h/k$ that can be formed has a convenient and intuitive graphical interpretation (Figure \ref{fig:lattice01} illustrates this interpretation with $h_{MAX}=3$ and $k_{MAX}=5$). Each rational number $h/k$ that can be formed under the constraints corresponds to a point in the integer lattice. \begin{figure} \centering \includegraphics[width=4.25in]{intlat01.eps} \caption{Integer Lattice Interpretation Of Rational Numbers $h/k$ Formable Under Constraints $h \leq h_{MAX}$ And $k \leq k_{MAX}$} \label{fig:lattice01} \end{figure} From Figure \ref{fig:lattice01}, it is clear that: \begin{generalenum} \item The angle $\theta$ of the ray from the origin to $(k,h)$ is monotonically increasing with respect to the value of $h/k$, and: \begin{generalenumindent01} \item $h/k = tan \theta$. \item $\theta = tan^{-1} h/k$. \end{generalenumindent01} \item The smallest rational number that can be formed under the constraints is $0/1$, the smallest non-zero rational number is $1/k_{MAX}$, and the largest rational number is $h_{MAX}/1$. \item Only irreducible rational numbers are directly ``visible'' from the origin (reducible numbers are hidden ``behind'' the irreducible numbers, when viewed from the origin). \item The ascending set of irreducible rational numbers that can be formed subject to the constraints can be constructed graphically by sweeping a line starting at $\theta = 0$ through the range $0 \leq \theta < \pi/2$, recording each integer lattice point that is directly ``visible'' from the origin. \item For $r_A = h/k \leq h_{MAX}/k_{MAX}$, the constraint $k \leq k_{MAX}$ is the dominant constraint, and the set of formable rational numbers $\leq h_{MAX}/k_{MAX}$ is simply $F_{k_{MAX}}$. \end{generalenum} By symmetry in Figure \ref{fig:lattice01}, it can be seen that each formable rational number $\geq h_{MAX}/k_{MAX}$ is the reciprocal of an element of the Farey series of order $h_{MAX}$. Thus, it is clear that the set of formable rational numbers under the constraints $h \leq h_{MAX} \wedge k \leq k_{MAX}$ can be built by concatenating a portion of $F_{k_{MAX}}$ with a portion of $F_{h_{MAX}}$, but with the terms of $F_{h_{MAX}}$ inverted and reversed in order. We denote the series formed from $F_N$ by inverting each element (except $0/1$) and reversing the order as $F_{\overline{N}}$. For example, using this definition, \begin{equation} F_{\overline{3}} = \left\{ \ldots{}, \frac{3}{8}, \frac{2}{5}, \frac{3}{7}, \frac{1}{2}, \frac{3}{5}, \frac{2}{3}, \frac{3}{4}, \frac{1}{1}, \frac{3}{2}, \frac{2}{1}, \frac{3}{1} \right\}. \end{equation} We denote the series formed by concatenating $F_{k_{MAX}}$ up through $h_{MAX}/k_{MAX}$ to $F_{\overline{h_{MAX}}}$ from $h_{MAX}/k_{MAX}$ through $h_{MAX}/1$ as $F_{k_{MAX}, \overline{h_{MAX}}}$. Note that $F_{k_{MAX}, \overline{h_{MAX}}}$ is the ordered set of all irreducible rational numbers that can be formed subject to $h \leq h_{MAX} \wedge k \leq k_{MAX}$. For example, using this definition, \begin{equation} \label{eq:concatseries01} F_{5, \overline{3}} = \left\{ \frac{0}{1}, \frac{1}{5}, \frac{1}{4}, \frac{1}{3}, \frac{2}{5}, \frac{1}{2}, \frac{3}{5}, \frac{2}{3}, \frac{3}{4}, \frac{1}{1}, \frac{3}{2}, \frac{2}{1}, \frac{3}{1} \right\}. \end{equation} It can be verified that the result in (\ref{eq:concatseries01}) is the same as would be obtained in Figure \ref{fig:lattice01} by sweeping a line from the origin counterclockwise through $0 \leq \theta < \pi/2$, recording each point of the integer lattice directly ``visible'' from the origin. The following $O(log \; max(h_{MAX}, k_{MAX}))$ algorithm is presented for finding the neighbors in $F_{k_{MAX}, \overline{h_{MAX}}}$ to an arbitrary irreducible rational number $a/b$. \begin{algorithm}\label{alg:rectangular}\end{algorithm} \begin{alglvl0} \item If $a/b < h_{MAX}/k_{MAX}$, apply Algorithm \ref{alg:bratrnnifnalg} directly; \item Else if $a/b > h_{MAX}/k_{MAX}$, apply Algorithm \ref{alg:bratrnnifnalg} using $b/a$, rather than $a/b$ as $r_I$, and using $N=h_{MAX}$ rather than $N=k_{MAX}$, and invert and transpose the two Farey neighbors obtained; \item Else if $a/b = h_{MAX}/k_{MAX}$, apply both steps above: the first step to obtain the left neighbor in $F_{k_{MAX}, \overline{h_{MAX}}}$ and the second step to obtain the right neighbor. \end{alglvl0} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Choosing $r_A = h/k$ Only In An Interval $[l,r]$} \label{sec:intervalcase} It is clear from the earlier discussion of the Farey series that the maximum distance between terms in $F_{k_{MAX}}$ is $1/k_{MAX}$, and that this maximum distance occurs only adjacent to an integer. It is also clear from the discussion of $F_{\overline{h_{MAX}}}$ that the maximum distance between terms is 1. Thus, when we use $F_{k_{MAX}, \overline{h_{MAX}}}$ to approximate real numbers, in general the worst-case distance between terms is 1. In practical applications when rational approximation is used, the approximation tends to be used over a restricted interval $[l \gg 0, r \ll h_{MAX}]$ rather than over the full range of the rational numbers that can be formed, $[0, h_{MAX}]$. This section develops novel upper bounds on the distance between terms of $F_{k_{MAX}, \overline{h_{MAX}}}$ in an interval $[l,r]$. For simplicity, assume $l,r \in F_{k_{MAX}, \overline{h_{MAX}}}$. Three distinct cases are developed (Figure \ref{fig:threecases}). The upper bound developed from Case III is always larger than the upper bound developed from Case II, which is always larger than the upper bound developed from Case I; so if only the absolute maximum error over the interval $[l,r]$ is of interest, only the highest-numbered case which applies needs to be evaluated. However, some applications may have different error requirements in different regions of the interval $[l,r]$, and for these applications it may be beneficial to analyze more than one case. \begin{figure} \centering \includegraphics[width=4.25in]{intlat02.eps} \caption{Three Cases For Bounding Distance Between Terms In $F_{k_{MAX}, \overline{h_{MAX}}}$} \label{fig:threecases} \end{figure} \subsection{Case I: $r_I < h_{MAX}/k_{MAX}$} \label{subsec:casei} With $r_I < h_{MAX}/k_{MAX}$, $k \leq k_{MAX}$ is the dominant constraint, and the neighbors available to $r_I$ are simply the terms of $F_{k_{MAX}}$. If $[l, r] \cap [0, h_{MAX}/k_{MAX}]$ includes an integer, clearly the maximum distance from $r_I$ to the nearest available term of $F_{k_{MAX}, \overline{h_{MAX}}}$ is given by \begin{equation} \left| \frac{h}{k} - r_I \right| \leq \frac{1}{2 k_{MAX}}. \end{equation} If $[l, r] \cap [0, h_{MAX}/k_{MAX}]$ does not include an integer, it can be shown that the maximum distance between Farey terms is driven by the rational number with the smallest denominator in the interval. For two consecutive terms $p/q$ and $p'/q'$ in $F_{k_{MAX}}$, $p'q - pq' = 1$ (Theorem \ref{thm:thm01}), so that \begin{equation} \frac{p'}{q'} - \frac{p}{q} = \frac{p'q - pq'}{q q'} = \frac{1}{qq'} . \end{equation} By Theorem \ref{thm:thm03}, $q+q' > k_{MAX}$, therefore \begin{equation} \label{eq:minqplacementupperbound} \frac{1}{q k_{MAX}} \leq \frac{1}{q q'} < \frac{1}{q (k_{MAX}-q)}. \end{equation} Let $q_{MIN}$ be the smallest denominator of any rational number $\in F_{k_{MAX}}$ in the interval $[l,r]$. It is then easy to show that for any consecutive denominators $q, q'$ which occur in $F_{k_{MAX}}$ in the interval $[l,r]$, \begin{equation} \frac{1}{q q'} < \frac{1}{q_{MIN} \; max (q_{MIN}, k_{MAX} - q_{MIN})} . \end{equation} Thus, the upper bound on the distance between consecutive terms of $F_{k_{MAX}}$ in an interval $[l,r]$ is tied to the minimum denominator of any rational number $\in F_{k_{MAX}}$ in $[l,r]$. Note that clearly $q_{MIN} \leq 1/(r-l)$, so for most practical intervals $[l,r]$, the search for $q_{MIN}$ would not be computationally expensive. However, applications could arise where an approximation is used in an \emph{extremely} narrow interval, and having an algorithm available that is computationally viable for such cases is advantageous. For example, locating the rational number $\in F_{2^{20,000}}$ with the smallest denominator in an interval of width $2^{-10,000}$ could be a serious computational problem. To locate $q_{MIN}$ in $[l,r]$, note that at least one rational number with $q_{MIN}$ as a denominator in $[l,r]$ is the best approximation of order $q_{MIN}$ to the midpoint of the interval, $(l+r)/2$.\footnote{Thanks to David M. Einstein and David Eppstein for this observation, contributed via the \texttt{sci.math} newsgroup, which is the linchpin of Algorithm \ref{alg:cfmindenominator}.} By theorem (\cite{KhinchinClassic}, Theorem 15), every best approximation of a number is a convergent or intermediate fraction of the continued fraction representation of the number. We seek the convergent or intermediate fraction of $(l+r)/2$ with the smallest denominator that is in the interval $[l,r]$. The convergents and intermediate fractions of $(l+r)/2$ are naturally arranged in order of increasing denominator. However, it would be inefficient to test \emph{every} intermediate fraction for membership in $[l,r]$, as partial quotients $a_k$ are unlimited in size and such an algorithm may not be $O(log \; k_{MAX})$. Instead, since intermediate fractions are formed using the parameterized expression $(i p_k + p_{k-1})/(i q_k + q_{k-1})$, and since intermediate fractions are ever-increasing or ever-decreasing with respect to the parameter $i$, the smallest value of $i$ which will create an intermediate fraction potentially within $[l,r]$ can be directly calculated. Only the intermediate fraction formed with this calculated value of $i$ needs to be tested for membership in $[l,r]$. Let $l_N$ and $l_D$ be the numerator and denominator of $l$, and let $r_N$ and $r_D$ be the numerator and denominator of $r$. In the case of $k$ even; $s_k < l < (l+r)/2$ (otherwise $s_k$ would have been identified as $\in [l,r]$, see Algorithm \ref{alg:cfmindenominator}); $s_{k+1} \geq (l+r)/2$; with increasing $i$, $(i p_k + p_{k-1})/(i q_k + q_{k-1})$ forms a decreasing sequence; and the inequality we seek to solve is \begin{equation} \label{eq:ifselection01} \frac{i p_k + p_{k-1}}{i q_k + q_{k-1}} \leq \frac{r_N}{r_D}. \end{equation} Solving (\ref{eq:ifselection01}), the smallest integral value of $i$ that will suffice is \begin{equation} \label{eq:ifselection02} i = \left\lceil { \frac{r_N q_{k-1} - r_D p_{k-1}}{r_D p_k - r_N q_k} } \right\rceil . \end{equation} Similarly, for $k$ odd, the sequence is increasing, and the inequality and solution are \begin{equation} \label{eq:ifselection03} \frac{i p_k + p_{k-1}}{i q_k + q_{k-1}} \geq \frac{l_N}{l_D} \to i = \left\lceil { \frac{l_N q_{k-1} - l_D p_{k-1}}{l_D p_k - l_N q_k} } \right\rceil . \end{equation} (\ref{eq:ifselection01}), (\ref{eq:ifselection02}), and (\ref{eq:ifselection03}) suggest the following continued fraction algorithm for finding a rational number with the smallest denominator in an interval $[l,r]$. \begin{algorithm}\label{alg:cfmindenominator}\end{algorithm} \begin{alglvl0} \item Calculate all partial quotients $a_k$ and all convergents $s_k = p_k/q_k$ of the midpoint of the interval, $(l+r)/2$. \item For each convergent $s_k=p_k/q_k$, in order of increasing $k$: \begin{alglvl1} \item If $s_k = p_k/q_k \in [l,r]$, $s_k$ is a rational number with the lowest denominator, STOP. \item If $k$ is even, \begin{alglvl2} \item Calculate $i$ according to (\ref{eq:ifselection02}). If $i < a_{k+1}$ and the intermediate fraction $(i p_k + p_{k-1})$ $/$ $(i q_k + q_{k-1})$ $\geq$ $l$, this intermediate fraction is a rational number with the lowest denominator, STOP. \end{alglvl2} \item Else if $k$ is odd, \begin{alglvl2} \item Calculate $i$ according to (\ref{eq:ifselection03}). If $i < a_{k+1}$ and the intermediate fraction $(i p_k + p_{k-1})$ $/$ $(i q_k + q_{k-1})$ $\leq$ $r$, this intermediate fraction is a rational number with the lowest denominator, STOP. \end{alglvl2} \end{alglvl1} \end{alglvl0} Algorithm \ref{alg:cfmindenominator} is approximately $O(log \; k_{MAX})$, since there are a fixed number of steps per convergent, and the maximum number of convergents is $O(log \; k_{MAX})$. Once a rational number with the smallest denominator $q_{MIN}$ is located, (\ref{eq:minqplacementupperbound}) can be applied to bound $|r_A - r_I|$; namely, \begin{equation} \label{eq:qminmaxplacementerror} \left| {\frac{h}{k} - r_I} \right| < \frac{1}{2q_{MIN} \; max(q_{MIN}, k_{MAX} - q_{MIN})} . \end{equation} \subsection{Case II: $h_{MAX}/k_{MAX} < r_I < 1$} \label{subsec:caseii} If $h_{MAX}/k_{MAX} < r_I < 1$, a graphical argument (Figure \ref{fig:caseii}) can be used to more tightly bound the maximum distance between terms of $F_{k_{MAX}, \overline{h_{MAX}}}$. \begin{figure} \centering \includegraphics[height=2.0in]{intlat03.eps} \caption{Graphical Interpretation Of Case II: $h_{MAX}/k_{MAX} < r_I < 1$} \label{fig:caseii} \end{figure} In this case, a formable term at or to the left\footnote{To the left on the number line, but to the right in Figure \ref{fig:caseii}.} of $r_I$ is represented by the point $(\lfloor h_{MAX}/r_I \rfloor + 1, h_{MAX} )$ in the integer lattice, and a formable term at or to the right of $r_I$ is represented by the point $(\lfloor h_{MAX}/r_I \rfloor, h_{MAX} )$ in the integer lattice. Thus, the maximum distance between neighboring terms in $F_{k_{MAX}, \overline{h_{MAX}}}$ is given by the difference of these two terms, \begin{equation} \frac{h_{MAX}}{\left\lfloor {\frac{h_{MAX}}{r_I}} \right\rfloor} - \frac{h_{MAX}}{\left\lfloor {\frac{h_{MAX}}{r_I}} \right\rfloor + 1} = \frac{h_{MAX}}{{\left\lfloor {\frac{h_{MAX}}{r_I}} \right\rfloor}^2 + \left\lfloor {\frac{h_{MAX}}{r_I}} \right\rfloor}, \end{equation} and the maximum distance from $r_I$ to a neighboring term is given by \begin{equation} \label{eq:caseiimaxplacementerror} \left| \frac{h}{k} - r_I \right| \leq \frac{h_{MAX}}{2 \left( { {\left\lfloor {\frac{h_{MAX}}{r_I}} \right\rfloor}^2 + \left\lfloor {\frac{h_{MAX}}{r_I}} \right\rfloor } \right) }. \end{equation} Note that Case II will exist only if $h_{MAX}/k_{MAX} < 1$. \subsection{Case III: $1 < h_{MAX}/k_{MAX} < r_I$} \label{subsec:caseiii} It can be established graphically, using the coordinate system of Figure \ref{fig:lattice01} or Figure \ref{fig:threecases}, that the line $h=r_I k$ intercepts the line $h=h_{MAX}$ at the point $(h_{MAX}/r_I, h_{MAX})$. It is clear from a graphical argument that all of the terms of the Farey series of order $\lfloor h_{MAX}/r_I \rfloor$ are available as neighbors of $r_I$. Therefore, \begin{equation} \label{caseiiiplacementerror} \left| \frac{h}{k} - r_I \right| \leq \frac{1}{2 \left\lfloor \frac{h_{MAX}}{r_I} \right\rfloor}. \end{equation} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{End-To-End Approximation Error} \label{sec:endtoenderror} A rational approximation requires an integer domain and range, and there are three sources of error inherent in such an approximation: \begin{generalenum} \item Input quantization error, as the input to the approximation is restricted to $\intsetnonneg$. \item Error in selecting $r_A = h / k$, as in general it isn't possible to choose $r_A = r_I$. \item Output quantization error, as the remainder of the division of $hx$ by $k$ is discarded, and the output must be $\in \intsetnonneg$. \end{generalenum} To model the end-to-end approximation error, a model function is introduced which represents the function we wish to approximate, \begin{equation} \label{eq:eq0001} F(x)=r_{I}x . \end{equation} However, the approximation necessarily involves quantizing the input $x$, as well as the result of the integer division: \begin{equation} \label{eq:eq0006} J(x) = \left\lfloor {r_A \left\lfloor x \right\rfloor } \right\rfloor = \left\lfloor {\frac{{h\left\lfloor x \right\rfloor }}{k}} \right\rfloor . \end{equation} Quantization of a real argument $x$ which is not necessarily rational is treated by noting that quntization introduces an error $\varepsilon \in [0,1)$: \begin{equation} \lfloor x \rfloor = x - \varepsilon; \; \varepsilon \in [0,1) . \end{equation} Quantization of a rational argument $a/b$ is treated by noting that the largest quantization error $\varepsilon$ occurs when $a$ is one less than an integral multiple of $b$: \begin{equation} \left\lfloor {\frac{a}{b}} \right\rfloor = \frac{a}{b} - \varepsilon; \; \varepsilon \in \left[ {0, \frac{b-1}{b}} \right] . \end{equation} The difference function $J(x)-F(x)$, can be stated as in (\ref{eq:eq0031}) or (\ref{eq:eq0032}). The two quantizations in (\ref{eq:eq0031}) can be treated by introducing $\varepsilon_{1}$ and $\varepsilon_{2}$ to yield (\ref{eq:eq0032}). Note that $\varepsilon_{1}$ and $\varepsilon_{2}$ are independent, meaning for this application that in general $r_I$, $r_A = h/k$, and $x$ can be chosen so as to force any combination of $\varepsilon_{1}$ and $\varepsilon_{2}$, so that no combinations of $\varepsilon_{1}$ and $\varepsilon_{2}$ can be excluded. \begin{equation} \label{eq:eq0031} J(x) - F(x) = \left\lfloor {\frac{{h\left\lfloor x \right\rfloor }}{k}} \right\rfloor - r_I x \end{equation} \begin{equation} \label{eq:eq0032} J(x) - F(x) = \frac{{h(x - \varepsilon _1 ) }}{k} - \varepsilon _2 - r_I x ; \; \varepsilon _1 \in [0,1) ; \; \varepsilon _2 \in \left[ {0,\frac{{k - 1}}{k}} \right] \end{equation} Choosing the extremes of $\varepsilon_{1}$ and $\varepsilon_{2}$ so as to minimize and maximize the difference function bounds the approximation error (\ref{eq:eq0035}). \begin{equation} \label{eq:eq0035} J(x) - F(x) \in \left( {(r_A - r_I )x - r_A - \frac{{k - 1}}{k},(r_A - r_I )x } \right] \end{equation} Minimizing and maximizing (\ref{eq:eq0035}) over a domain of $[0,x_{MAX}]$ leads to (\ref{eq:eq0036}). \begin{equation} \label{eq:eq0036} \left. {J(x) - F(x)} \right|_{x \in [0,x_{MAX} ]} \in \left\{ {\begin{array}{*{20}c} {\left( {(r_A - r_I )x_{MAX} - r_A - \frac{{k - 1}}{k},0} \right],} \hfill & {r_A < r_I } \hfill \\ \\ {\left( { - r_A - \frac{{k - 1}}{k},0} \right],} \hfill & {r_A = r_I } \hfill \\ \\ {\left( { - r_A - \frac{{k - 1}}{k},(r_A - r_I )x_{MAX} } \right] ,} \hfill & {r_A > r_I } \hfill \\ \end{array}} \right. \end{equation} Thus, given an $r_I \in \realsetnonneg$ and a rational approximation to $r_I$, $r_A = h/k$, the error introduced by this rational approximation used over a domain $[0,x_{MAX}]$ can be bounded. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Design Example} \label{sec:designexample} A design example is presented to illustrate the methods presented. An $r_I$ specified with only modest precision and an $h_{MAX}$ and $k_{MAX}$ of only modest size are used to avoid a large number of partial quotients or large integers.\footnote{The rational approximation software submitted with this paper will handle rational approximations involving hundreds of digits and hundreds of partial quotients. However, such approximations make unsuitable examples because of the length, the difficulty in typesetting huge integers and rational numbers, and because the examples can't be carried out manually by a reader.} \textbf{Design Example:} Assume that real numbers are to be approximated by rational numbers in the interval $[0.385, 2.160]$, subject to $h_{MAX} = 193 \wedge k_{MAX}=500$. Bound $|r_A - r_I|$ under these constraints. Find the best rational approximations to $1/\pi \approx 0.31830989$ and $2/\pi \approx 0.63661977$ under the same constraints. \textbf{Solution:} In this example, \emph{Case I}, \emph{Case II}, and \emph{Case III} (Sections \ref{subsec:casei}, \ref{subsec:caseii}, and \ref{subsec:caseiii}) apply. Case III will dominate the upper bound on the error in selecting $r_A$, but it is instructive to work through Case I and Case II. To apply the results from \emph{Case I}, it is necessary to find a rational number with the smallest denominator in the interval $[l = 0.385, r = 193/500 = 0.386]$. The midpoint of the interval is $(l+r)/2 = 0.3855 = 771/2000$. Table \ref{tbl:cfexpansmidpoint} shows the generation of the partial quotients and convergents of the midpoint, 771/2000, using Algorithm \ref{alg:bratrnnifnalg}. \begin{table} \caption{Partial Quotients And Convergents Of 0.3855 (Midpoint Of The Interval $[0.385, 0.386]$)} \label{tbl:cfexpansmidpoint} \begin{center} \begin{tabular}{|c|c|c|c|c|c|c|} \hline \small{Index} & \small{$dividend_k$} & \small{$divisor_k$} & \small{$a_k$} & \small{$remainder_k$} & \small{$p_k$} & \small{$q_k$} \\ \small{($k$)} & & & & & & \\ \hline \hline \small{-1} & \small{N/A} & \small{771} & \small{N/A} & \small{2000} & \small{1} & \small{0} \\ \hline \small{0} & \small{771} & \small{2000} & \small{0} & \small{771} & \small{0} & \small{1} \\ \hline \small{1} & \small{2000} & \small{771} & \small{2} & \small{458} & \small{1} & \small{2} \\ \hline \small{2} & \small{771} & \small{458} & \small{1} & \small{313} & \small{1} & \small{3} \\ \hline \small{3} & \small{458} & \small{313} & \small{1} & \small{145} & \small{2} & \small{5} \\ \hline \small{4} & \small{313} & \small{145} & \small{2} & \small{23} & \small{5} & \small{13} \\ \hline \small{5} & \small{145} & \small{23} & \small{6} & \small{7} & \small{32} & \small{83} \\ \hline \small{6} & \small{23} & \small{7} & \small{3} & \small{2} & \small{101} & \small{262} \\ \hline \small{7} & \small{7} & \small{2} & \small{3} & \small{1} & \small{335} & \small{869} \\ \hline \small{8} & \small{2} & \small{1} & \small{2} & \small{0} & \small{771} & \small{2000} \\ \hline \end{tabular} \end{center} \end{table} Algorithm \ref{alg:cfmindenominator} can be applied to locate the fraction in $[l,r]$ with the smallest denominator. $s_0 =0/1 \notin [l,r]$. The intermediate fraction $(p_0 + p_{-1})/(q_0 + q_{-1})=1/1 \notin [l,r]$. $s_1 = 1/2 \notin [l,r]$. $s_2 = 1/3 \notin [l,r]$. $s_3 = 2/5 \notin [l,r]$. The intermediate fraction $(p_3 + p_2)/(q_3 + q_2)=3/8 \notin [l,r]$. $s_4 = 5/13 \notin [l,r]$. (\ref{eq:ifselection02}) can be applied to determine the lowest value of the parameter $i$ for which an intermediate fraction \emph{may} be in $[l,r]$: \begin{equation} i = \left\lceil { \frac {(r_N = 193)(q_3 = 5) - (r_D = 500)(p_3=2)} {(r_D=500)(p_4 = 5)-(r_N=193)(q_4=13)} } \right\rceil = \left\lceil {\frac{-35}{-9}} \right\rceil = 4. \end{equation} Thus, it is only necessary to examine the intermediate fraction $(4 p_4 + p_3)/(4 q_4 + q_3)$ for potential membership in $[l,r]$. This intermediate fraction, $22/57$ $\approx$ $0.385965$ $\in$ $[l,r]$. Thus, the fraction with the lowest denominator in the interval is 22/57, and $q_{min} = 57$. Application of (\ref{eq:qminmaxplacementerror}) yields \begin{equation} \begin{array}{l} \displaystyle{\left| {\frac{h}{k} - r_I} \right| < } \\ \\ \displaystyle{\left({\frac{1}{2q_{MIN} \; max(q_{MIN}, k_{MAX}-q_{MIN})} = \frac{1}{(2)(57)(500-57)} = \frac{1}{50,502} } \right) .} \end{array} \end{equation} Note that the 1/50,502 maximum error in placing $r_A$ is much better than the 1/1,000 worst-case error for $F_{500}$ in general without restrictions on the interval. Case II and Case III aren't as complicated as Case I---applying these cases is a simple matter of substitution into (\ref{eq:caseiimaxplacementerror}) or (\ref{caseiiiplacementerror}). Case II and (\ref{eq:caseiimaxplacementerror}) apply, but the error bounds from Case III will be larger, so Case II is not evaluated. Case III applies: the line $h=r_I k$ intersects the line $h=h_{MAX}$ at the point $(h_{MAX}/r_I, h_{MAX})$ = $(193/2.160, 193)$, thus all terms of the Farey series of order $\lfloor 193/2.160 \rfloor = 89$ are available for selection. Therefore, applying (\ref{caseiiiplacementerror}), \begin{equation} \left| {\frac{h}{k} - r_I} \right| \leq \frac{1}{2 \times 89} \approx 0.0056 . \end{equation} Thus, if $F_{500, \overline{193}}$ is used to approximate real numbers over the interval $[0.385$, $2.160]$, an upper bound on $|r_A - r_I|$ is $1/178 \approx 0.0056$. Note that Case III dominates, and that the upper bound on $|r_A - r_I|$ varies within the interval. To find the best rational approximations to $1/ \pi$ in $F_{500, \overline{193}}$, note that $1/ \pi < 193/500$, so all of the terms in $F_{500}$ are available. Table \ref{tbl:cfexpansraponeoverpi} shows the partial quotients and convergents of $1/ \pi$, using 0.31830989 as a rational approximation of $1/ \pi$. $s_4$ is the highest-order convergent with $q_k \leq 500$, so $s_4 = 113/355$ is one Farey neighbor to $1/ \pi$ in $F_{500}$. Applying (\ref{eq:eq0065}) to generate the other neighbor in $F_{500}$ yields 106/333. Note that $113/355 - 1/\pi \approx -3 \times 10^{-8}$ and $106/333 - 1/\pi \approx 8 \times 10^{-6}$ (the errors are quite small). \begin{table} \caption{Partial Quotients And Convergents Of 31,830,989/100,000,000 (A Rational Approximation To $1/ \pi$)} \label{tbl:cfexpansraponeoverpi} \begin{center} \begin{tabular}{|c|c|c|c|c|c|c|} \hline \small{Index} & \small{$dividend_k$} & \small{$divisor_k$} & \small{$a_k$} & \small{$remainder_k$} & \small{$p_k$} & \small{$q_k$} \\ \small{($k$)} & & & & & & \\ \hline \hline \small{-1} & \small{N/A} & \small{31,830,989} & \small{N/A} & \small{100,000,000} & \small{1} & \small{0} \\ \hline \small{0} & \small{31,830,989} & \small{100,000,000} & \small{0} & \small{31,830,989} & \small{0} & \small{1} \\ \hline \small{1} & \small{100,000,000} & \small{31,830,989} & \small{3} & \small{4,507,033} & \small{1} & \small{3} \\ \hline \small{2} & \small{31,830,989} & \small{4,507,033} & \small{7} & \small{281,758} & \small{7} & \small{22} \\ \hline \small{3} & \small{4,507,033} & \small{281,758} & \small{15} & \small{280,663} & \small{106} & \small{333} \\ \hline \small{4} & \small{281,758} & \small{280,663} & \small{1} & \small{1,095} & \small{113} & \small{355} \\ \hline \small{5} & \small{280,663} & \small{1,095} & \small{256} & \small{343} & \small{29,034} & \small{91,213} \\ \hline \small{6} & \small{1,095} & \small{343} & \small{3} & \small{66} & \small{87,215} & \small{273,994} \\ \hline \small{7} & \small{343} & \small{66} & \small{5} & \small{13} & \small{465,109} & \small{1,461,183} \\ \hline \small{8} & \small{66} & \small{13} & \small{5} & \small{1} & \small{2,412,760} & \small{7,579,909} \\ \hline \small{9} & \small{13} & \small{1} & \small{13} & \small{0} & \small{31,830,989} & \small{100,000,000} \\ \hline \end{tabular} \end{center} \end{table} To find the best rational approximations to $2/ \pi$ in $F_{500, \overline{193}}$, note that $2/ \pi > 193/500$, so the second clause of Algorithm \ref{alg:rectangular} applies. Table \ref{tbl:cfexpansrappiovertwo} shows the partial quotients and convergents of $\pi / 2$, using 1/0.63661977 as a rational approximation of $\pi /2$. $s_3$ is the highest-order convergent with $q_k \leq 193$, so $s_3^{-1} = (11/7)^{-1}$ is one neighbor to $2/ \pi$ in $F_{\overline{193}}$. Applying (\ref{eq:eq0065}) to generate the reciprocal of the other neighbor in $F_{\overline{193}}$ yields 300/191, implying that 191/300 is the other neighbor. $7/11 - 2/\pi \approx -3 \times 10^{-4}$. $191/300 - 2/\pi \approx 5 \times 10^{-5}$. \begin{table} \caption{Partial Quotients And Convergents Of 100,000,000/63,661,977 (A Rational Approximation To $\pi / 2$)} \label{tbl:cfexpansrappiovertwo} \begin{center} \begin{tabular}{|c|c|c|c|c|c|c|} \hline \small{Index} & \small{$dividend_k$} & \small{$divisor_k$} & \small{$a_k$} & \small{$remainder_k$} & \small{$p_k$} & \small{$q_k$} \\ \small{($k$)} & & & & & & \\ \hline \hline \small{-1} & \small{N/A} & \small{100,000,000} & \small{N/A} & \small{63,661,977} & \small{1} & \small{0} \\ \hline \small{0} & \small{100,000,000} & \small{63,661,977} & \small{1} & \small{36,338,023} & \small{1} & \small{1} \\ \hline \small{1} & \small{63,661,977} & \small{36,338,023} & \small{1} & \small{27,323,954} & \small{2} & \small{1} \\ \hline \small{2} & \small{36,338,023} & \small{27,323,954} & \small{1} & \small{9,014,069} & \small{3} & \small{2} \\ \hline \small{3} & \small{27,323,954} & \small{9,014,069} & \small{3} & \small{281,747} & \small{11} & \small{7} \\ \hline \small{4} & \small{9,014,069} & \small{281,747} & \small{31} & \small{279,912} & \small{344} & \small{219} \\ \hline \small{5} & \small{281,747} & \small{279,912} & \small{1} & \small{1,835} & \small{355} & \small{226} \\ \hline \small{6} & \small{279,912} & \small{1,835} & \small{152} & \small{992} & \small{54,304} & \small{34,571} \\ \hline \small{7} & \small{1,835} & \small{992} & \small{1} & \small{843} & \small{54,659} & \small{34,797} \\ \hline \small{8} & \small{992} & \small{843} & \small{1} & \small{149} & \small{108,963} & \small{69,368} \\ \hline \small{9} & \small{843} & \small{149} & \small{5} & \small{98} & \small{599,474} & \small{381,637} \\ \hline \small{10} & \small{149} & \small{98} & \small{1} & \small{51} & \small{708,437} & \small{451,005} \\ \hline \small{11} & \small{98} & \small{51} & \small{1} & \small{47} & \small{1,307,911} & \small{832,642} \\ \hline \small{12} & \small{51} & \small{47} & \small{1} & \small{4} & \small{2,016,348} & \small{1,283,647} \\ \hline \small{13} & \small{47} & \small{4} & \small{11} & \small{3} & \small{23,487,739} & \small{14,952,759} \\ \hline \small{14} & \small{4} & \small{3} & \small{1} & \small{1} & \small{25,504,087} & \small{16,236,406} \\ \hline \small{15} & \small{3} & \small{1} & \small{3} & \small{0} & \small{100,000,000}& \small{63,661,977} \\ \hline \end{tabular} \end{center} \end{table} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% (9) ACKNOWLEDGEMENTS % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%Need to retain e-mail addresses to contact all people who have contributed %%to thank. %%Greg Bachelis (greg@math.wayne.edu) %%Robert Berman (rberman@math.wayne.edu) %%Feng Lin (flin@ece.eng.wayne.edu) %%Nick Sahinidis (nikos@uiuc.edu) %%Adam Van Tuyl, (vantuyl@mast.queensu.ca) %%Carl Schweiger (carl@titan.princeton.edu) %%Ken Tindell (ktindell@ssx5.com) %%Steve Vestal (vestal@htc.honeywell.com) %%Bob Whitinger (bob@whitinger.net, bob.whitinger@sea.siemens.com) %%David B. Stewart (dstewart@eng.umd.edu) %%Johan Bengtsson (johanb@docs.uu.se) %%Michael J. Burke (mburke@visteon.com) %%Mark Endicott (mendicot@visteon.com) %%David Eppstein (eppstein@ics.uci.edu) %%Cliff Stallings (cliff@eng.wayne.edu) %%Robert Kakos (robert@enterprise.eng.wayne.edu) %%Klaus-Peter Zauner (kjz@cs.wayne.edu) %%Karsten Tinnefeld (tinnefeld@ls2.cs.uni-dortmund.de) %%Paulette Groen (pgroen@visteon.com) %%Paula Smith (psmith77@visteon.com) %%Mircea Munteanu (mmuntean@visteon.com) %%Adam Gibson (adam.g@virgin.net) %%Virgil (vmhjr@frii.com) %%Bob Crosby (b-crosby@ti.com) %%Una Smith (una.smith@yale.edu) %%Andrea Blome (ablome@mail.cfigroup.com) %%Axel Franke (Axel.Franke@physics.umu.se) %% %%Need also to include Adam's Web site on my Web page, %%http://archives.math.utk.edu/articles/atuyl/confrac/ %% %%Need also to include David Eppstein's Web site %%http://www.ics.uci.edu/~eppstein/ %% %% \begin{acks} We would like to gratefully acknowledge the assistance of Greg Bachelis, Robert Berman, Feng Lin, Nick Sahinidis, Adam Van Tuyl, Carl Schweiger, Ken Tindell, Steve Vestal, Bob Whitinger, and David B. Stewart in finding the areas of mathematics relevant to the rational number selection problem. We would also like to thank Johan Bengtsson, Michael J. Burke, Mark Endicott, David Eppstein, David M. Einstein, Mircea Munteanu, Adam Gibson, and Virgil (of the \texttt{sci.math.num-analysis} newsgroup) for insight into this problem; Cliff Stallings and Robert Kakos for support from Wayne State University's College Of Engineering; Paulette Groen and Paula Smith for support from Visteon; Bob Crosby for support from Texas Instruments; Klaus-Peter Zauner, Andrea Blome, Una Smith, Karsten Tinnefeld, and Axel Franke for other tool and logistical support; and the management team at Visteon for allowing us to pursue this effort in the workplace. \end{acks} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% (11) REFERENCES % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \nocite{*} \bibliographystyle{ESUB2ACM} \begin{thebibliography}{1} \bibitem{HardyAndWrightClassic} G.H. Hardy, E.M. Wright, \newblock{\em An Introduction To The Theory Of Numbers}, ISBN 0-19-853171-0. \bibitem{Harman} G. Harman (1998), \newblock{\em Metric Number Theory}, Oxford University Press. \bibitem{KargaevZ} P. Kargaev, A. Zhigljavsky (1966), \newblock{\em Approximation Of Real Numbers By Rationals: Some Metric Theorems}, Journal of Number Theory, 61, 209-225. \bibitem{KargaevZ1} P. Kargaev, A. Zhigljavsky (1967), \newblock{\em Asymptotic Distribution Of The Distance Function To The Farey Points}, Journal of Number Theory, 65, 130-149. \bibitem{KhinchinClassic} A. Ya. Khinchin, \newblock{\em Continued Fractions}, University Of Chicago Press, 1964; Library Of Congress Catalog Card Number 64-15819. \bibitem{LeVeque} William J. LeVeque, \newblock{\em Fundamentals Of Number Theory}, Dover Publications, 1977, ISBN 0-486-68906-9. \bibitem{OldsClassic} C. D. Olds, \newblock{\em Continued Fractions}, Randam House, 1963, Library Of Congress Catalog Card Number 61-12185. \bibitem{OreClassic} Oystein Ore, \newblock{\em Number Theory And Its History}, ISBN 0-486-65620-9. \bibitem{SchroederClassic} M. R. Schroeder, \newblock{\em Number Theory In Science And Communication}, ISBN 3-540-62006-0. \end{thebibliography} \clearpage \begin{figure*} \caption{Version Control Information (For Reference Only---Will Be Removed Before Submission Of Paper)} \vspace{3.0mm} \begin{tiny} \texttt{\LaTeX{} compile date: \today{}.} \begin{verbatim} CVS Version Control Information: $Header: /cvsroot/esrg/sfesrg/esrgpubs/acm0010/paper/acm_paper.tex,v 1.5 2003/04/08 03:57:12 dtashley Exp $. \end{verbatim} \end{tiny} \end{figure*} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % (10) CONTACT INFORMATION % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %\section{Contact} % %Additional supplemental materials (such as Excel %spreadsheets which generate Farey terms automatically) %are downloadable from http://www.daveashley.com. %E-mail addresses and home pages (where applicable) %for authors are supplied below. %David T. Ashley: % daveashley@daveashley.com % http://www.daveashley.com/ %Joseph P. DeVoe % jdevoe@visteon.com %Karl Perttunen % kperttun@visteon.com %Cory Pratt % cpratt2@visteon.com %Anatoly Zhigljavsky % zhigljavskyaa@cardiff.ac.uk % http:\-//\-www.\-cf.\-ac.\-uk/\-uwcc/\-maths/\-zhig\-ljav\-skyaa/ \end{document} % $Log: acm_paper.tex,v $ % Revision 1.5 2003/04/08 03:57:12 dtashley % Extra lines in log deleted. % % Revision 1.4 2003/04/08 03:49:14 dtashley % Final keyword expansion change. % % Revision 1.3 2003/04/08 03:48:32 dtashley % Log information at end of file changed for CVS. % % ***************** Version 13 ***************** % User: Dashley1 Date: 11/13/00 Time: 3:59a % Updated in $/ACM Rational Approximation Paper And Algorithms/LaTeX Paper And Graphics % Final versions for submission to the ACM. % % ***************** Version 12 ***************** % User: Dashley1 Date: 11/12/00 Time: 1:03a % Updated in $/ACM Rational Approximation Paper And Algorithms/LaTeX Paper And Graphics % Minor error corrected. % % ***************** Version 11 ***************** % User: Dashley1 Date: 11/11/00 Time: 6:10a % Updated in $/ACM Rational Approximation Paper And Algorithms/LaTeX Paper And Graphics % (Believed) final check-in before submission. % % ***************** Version 10 ***************** % User: Dashley1 Date: 11/08/00 Time: 12:51a % Updated in $/ACM Rational Approximation Paper And Algorithms/LaTeX Paper And Graphics % Proofreading changes, graphics changes. % % ***************** Version 9 ***************** % User: Dashley1 Date: 11/06/00 Time: 11:23p % Updated in $/ACM Rational Approximation Paper And Algorithms/LaTeX Paper And Graphics % All revisions completed, out for proofreading. % % ***************** Version 8 ***************** % User: Dashley1 Date: 11/06/00 Time: 3:16a % Updated in $/ACM Rational Approximation Paper And Algorithms/LaTeX Paper And Graphics % Safety check-in. % % ***************** Version 7 ***************** % User: Dashley1 Date: 11/05/00 Time: 1:38a % Updated in $/ACM Rational Approximation Paper And Algorithms/LaTeX Paper And Graphics % Safety check-in. % % ***************** Version 6 ***************** % User: Dashley1 Date: 11/04/00 Time: 12:47a % Updated in $/ACM Rational Approximation Paper And Algorithms/LaTeX Paper And Graphics % Completion of fundamental ideas about concatenated series. % % ***************** Version 5 ***************** % User: Dashley1 Date: 11/03/00 Time: 3:08a % Updated in $/ACM Rational Approximation Paper And Algorithms/LaTeX Paper And Graphics % Safety check-in, major progress. % % ***************** Version 4 ***************** % User: Dashley1 Date: 10/30/00 Time: 6:40p % Updated in $/ACM Rational Approximation Paper And Algorithms/LaTeX Paper And Graphics % Completion of CF expansion functionality. % % ***************** Version 3 ***************** % User: Dashley1 Date: 10/18/00 Time: 1:08a % Updated in $/ACM Rational Approximation Paper And Algorithms/LaTeX Paper And Graphics % IEEE paper ported. Compiles. % % ***************** Version 2 ***************** % User: Dashley1 Date: 10/17/00 Time: 8:33p % Updated in $/ACM Rational Approximation Paper And Algorithms/LaTeX Paper And Graphics % VC info added. % %End of file ACM_PAPER.TEX