Parent Directory | 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)

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 |