/[dtapublic]/sf_code/esrgdstb/common/suppmatls/papers_articles/embedded_control/uc_math/rat_app/ieee_rap_2000.txt
ViewVC logotype

Contents of /sf_code/esrgdstb/common/suppmatls/papers_articles/embedded_control/uc_math/rat_app/ieee_rap_2000.txt

Parent Directory Parent Directory | Revision Log Revision Log


Revision 27 - (show annotations) (download)
Sat Oct 8 07:04:15 2016 UTC (7 years, 5 months ago) by dashley
File MIME type: text/plain
File size: 142554 byte(s)
Initial commit.
1 %% $Header: /cvsroot/esrg/sfesrg/esrgdstb/common/suppmatls/papers_articles/embedded_control/uc_math/rat_app/ieee_rap_2000.txt,v 1.1 2002/04/24 07:23:58 dtashley Exp $
2 %
3 %Made liaison with Stephany Gervasi at IEEE Computer;
4 %she now accepts initial papers for review (Yu-Tzu's old
5 %job). Must give her .PS or .PDF on initial submission. Best e-mail
6 %is tse@computer.org. Her physical mailing address is exactly
7 %the same as Yu-Tzu's, below.
8 %==================================================================
9 %Made liaison with Yu-Tzu Tsai at IEEE Computer, the contact
10 %information for where she works is below. Final
11 %manuscript should be submitted to her as .PDF
12 %or .PS electronically. I was also advised that paper
13 %should not exceed 20 pages.
14 %
15 %Her e-mail is YTSAI@COMPUTER.ORG.
16 %
17 %Publications Office
18 %10662 Los Vaqueros Circle
19 %P. O. Box 3014
20 %Los Alamitos, CA 90720-1264
21 %Phone: +1-714-821-8380
22 %FAX: +1-714-821-4010
23 %Publications Orders: +1-800-272-6657
24 %
25 %===================================================================
26 %Notes from conversation with Joe on 12/31/99.
27 %
28 % a)Joe indicated to change "load" to algorithm on p.1. Done.
29 %
30 % b)Joe indicated that the quantization error for a rational number
31 % could be compactly expressed as (a mod b)/b. We might want to
32 % include this, but it may not assist in the error analysis, but
33 % it may be useful as a way of thinking.
34 %
35 % c)Joe indicated that for equations (10) and (11), the the sign
36 % seemed inconsistent with the subsequent equations. We should
37 % discuss and resolve this.
38 %
39 %%01/10/00: Pasting in e-mail from Dr. Zhigljavsky for reference.
40 %%
41 %%Concerning
42 %%"I" to denote the set of integers,
43 %%your collegues is right, the standard notation is:
44 %%
45 %%Z for the set of all integers
46 %%Z_{+} for the set of non-negative integers
47 %%N for the set of positive integers (1,2,3,...)
48 %%R for reals
49 %%
50 %%They are actually not standard R,Z,N. To generate proper ones one
51 %%should use
52 %%
53 %%\usepackage{amsfonts}
54 %%
55 %%and then, in the mathematical mode, type
56 %%
57 %%\Bbb{R}
58 %%
59 %%\Bbb{N}
60 %%or
61 %%\Bbb{Z}
62 %%
63 %%rather than just R,Z or N.
64 %%
65 %%Dave's Note: LaTeX warned me that \Bbb{} is outdated, and to use \mathbb{} instead. It appears that
66 %%\Bbb{} is no longer fully supported, as it gives Greek symbols where there should be none, appears
67 %%to be a bug because \Bbb{} no longer supported, so will use \mathbb{}, which does not have this
68 %%bug.
69 %%
70 %%Dave's Second Note: Was advised by Robert Berman
71 %%that normally Q used for rationals, sometimes P or I for irrationals, all in those alternate typefaces
72 %%similar to R, Z, etc.
73 %%May want to adopt those for brevity. He also advised that some flexibility in
74 %%definitions, as long as this is made clear.
75 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
76 %%Notes on using the "hyperref" package.
77 %%
78 %%On about 03/30/00, the hyperref package was tested, and the results were impressive. It
79 %%causes generation of a PostScript file that, when distilled using Acrobat Distiller,
80 %%contains bookmarks. A newsgroup posting from Una Smith was very helpful.
81 %%
82 %%Here are the important points from Una's post:
83 %%
84 %%The last package invoked must be the hyperref package,
85 %% \usepackage[ps2pdf]{hyperref}
86 %%
87 %%This must be immediately followed by the following line to deal with
88 %%a bug in hyperref which will be fixed later.
89 %% \let\x\undefined
90 %%
91 %%There must be a file hyperref.cfg with the following contents:
92 %% \hypersetup{%
93 %% backref=false,
94 %% colorlinks=false,
95 %% pageanchor=false,
96 %% bookmarks=true,
97 %% bookmarksopen=true}%
98 %%
99 %%Una's e-mail is UNA.SMITH@YALE.EDU
100 %%
101 %%It is also noteworthy that there may be errors on the first few compilations because of
102 %%(I'm guessing) different formats on the .AUX files.
103 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
104 %%Notes from conversation with Bill Hagen on 04/05/00.
105 %%
106 %%I had sent an e-mail to Bill with four questions about what is and what is not allowed under
107 %%IEEE copyright. Bill answered my questions on the phone so he won't respond to the E-mail.
108 %%
109 %% a)E-mailing ... don't worry about it so long as the purpose is research collaboration or
110 %% sharing paper.
111 %%
112 %% b)Postal mailing ... don't worry about it so long as it is for research collaboration or
113 %% sharing paper and not a "for profit" or "vending" thing.
114 %%
115 %% c)Teaching an internal corporate class. Bill indicated that he does not believe the IEEE
116 %% would have a problem with it, but that it might be best to have an exchange of letters
117 %% before this is done. In other words, probably Visteon would not have to pay the copyright
118 %% fees "per student", but need to confirm via more formal mechanism. This would also
119 %% ease any concerns by our corporate librarian.
120 %%
121 %% d)Use of material in a book ... Bill does not believe there will be a problem so long as
122 %% it is my own material (not a DIFFERENT IEEE paper); but, again, a more formal mechanism
123 %% might be advised, i.e. an exchange of letters. This might also ease any concerns by
124 %% a publisher.
125 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
126 %%Not sure what notation to use for the set of rational numbers. I believe (if memory
127 %%serves me correctly), that "Q" can be used, but don't remember for sure. To protect
128 %%for this, will define a new LaTeX command so can change all occurences in one place
129 %%until we have talked and confirmed with Dr. Zhigljavsky. In fact, will define all
130 %%sets this way just in case there needs to be a global change.
131 %%
132 %%Sets of real numbers.
133 \newcommand{\realset}{{\mathbb{R}}}
134 \newcommand{\realsetnonneg}{{\mathbb{R}^+}}
135 %%
136 %%Sets of integers.
137 \newcommand{\intset}{{\mathbb{Z}}}
138 \newcommand{\intsetnonneg}{{\mathbb{Z}^+}}
139 \newcommand{\intsetpos}{{\mathbb{N}}}
140 %%
141 %%Sets of rational numbers.
142 \newcommand{\ratset}{{\mathbb{Q}}}
143 \newcommand{\ratsetnonneg}{{\mathbb{Q}^+}}
144 %%
145 %%Sets of irrational numbers.
146 \newcommand{\irratset}{{\mathbb{error}}}
147 \newcommand{\irratsetnonneg}{{\mathbb{error}^+}}
148
149 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
150 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
151 %%Not sure what Greek letter to use to denote the difference
152 %%at the terminal L(x_{MAX}). For that reason will
153 %%leave that option open and define it as a new command,
154 %%so it can be changed in one place.
155 \newcommand{\lxtermdifffuncsymbol}{\psi}
156
157
158 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
159 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
160 % STYLE FILES, ETC. %
161 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
162 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
163 \documentclass[twocolumn]{ieee_pq} %!PN
164
165 \usepackage{amsfonts}
166 \usepackage{amsmath}
167
168 \usepackage{graphicx}
169
170 %Using hyperref reserved for generating a .PDF only.
171 %\usepackage[ps2pdf]{hyperref}
172 %\let\x\undefined
173
174 \def\BibTeX{{\rm B\kern-.05em{\sc i\kern-.025em b}\kern-.08em
175 T\kern-.1667em\lower.7ex\hbox{E}\kern-.125emX}}
176
177
178 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
179 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
180 % NEW NUMBERED ENVIRONMENTS (THEOREMS, EXAMPLES, ETC.) %
181 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
182 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
183 \newtheorem{algorithm}{Algorithm}
184
185 \newtheorem{example}{Example}
186
187 \newtheorem{theorem}{Theorem}
188
189
190 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
191 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
192 % NEW ENVIRONMENT DEFINITIONS %
193 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
194 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
195 %The "itemize" environment defined by the IEEE style files didn't seem to have
196 %quite the right appearance for presenting our algorithms. For this reason, the
197 %following environments were defined. Level 0 is flush left with bullets, Level 1
198 %is slightly more indented, etc.
199 \newenvironment{alglvl0}{\begin{list}
200 {$\bullet$}{\setlength{\labelwidth}{3mm}\setlength{\leftmargin}{6mm}}}
201 {\end{list}}
202 \newenvironment{alglvl1}{\begin{list}
203 {$\bullet$}{\setlength{\labelwidth}{3mm}\setlength{\leftmargin}{6mm}}}
204 {\end{list}}
205
206 %The following environment is intended for listing properties (of continued fractions,
207 %convergents, etc.).
208 \newenvironment{propenum}{\begin{list}
209 {$\bullet$}{\setlength{\labelwidth}{3mm}\setlength{\leftmargin}{6mm}}}
210 {\end{list}}
211
212 %The following environment is intended for general enumeration.
213 \newenvironment{generalenum}{\begin{list}
214 {$\bullet$}{\setlength{\labelwidth}{3mm}\setlength{\leftmargin}{6mm}}}
215 {\end{list}}
216
217 %The following environment is intended for general enumeration with a slight indent.
218 \newenvironment{generalenumindent01}{\begin{list}
219 {$\bullet$}{\setlength{\labelwidth}{3mm}\setlength{\leftmargin}{12mm}}}
220 {\end{list}}
221
222
223
224 %The following environment is for the glossary at the end.
225 \newenvironment{glossaryenum}{\begin{list}
226 {}{\setlength{\labelwidth}{0mm}
227 \setlength{\leftmargin}{4mm}
228 \setlength{\itemindent}{-4mm}
229 \setlength{\parsep}{0.85mm}}}
230 {\end{list}}
231
232
233 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
234 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
235 % SET THE PAGE NUMBER %
236 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
237 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
238 \setcounter{page}{99}
239
240
241 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
242 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
243 % HYPHENATION EXCEPTION RULES %
244 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
245 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
246 %\hyphenation{http:-//-www.-cf.-ac.-uk/-uwcc/-maths/-zhig-ljavskyaa/}
247 \hyphenation{micro-con-trol-ler}
248 \hyphenation{rat-io-met-ric}
249 \hyphenation{rat-ion-al}
250 \hyphenation{Zhig-ljav-sky}
251
252
253 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
254 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
255 % START OF DOCUMENT %
256 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
257 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
258 \begin{document}
259
260 \thispagestyle{empty}
261
262 %\begin{centering}
263
264 \begin{large}
265
266 \textbf{December 8, 2000:} This paper
267 is distributed with the \emph{IjuTools} suite.
268 The paper contained on the following pages was rejected by ``\emph{IEEE Transactions On Computers}'' in 2000.
269 Therefore, the five authors listed hold the copyright.
270 \LaTeX{} source code is also included in this distribution. The five authors hereby waive all rights under
271 copyright law and grant permission to reproduce or use this paper and the accompanying
272 \LaTeX{} source code, in whole or in part, for any purpose whatsoever,
273 commercial or non-commercial, with no requirement for
274 renumeration of the authors, and no requirement to cite or otherwise supply the identity
275 of the authors.
276
277 Under Adobe Arobat 3, some subscripts in this paper disappear when printed. Adobe Acrobat 4
278 or its successors are recommended for printing.
279 \end{large}
280
281 %\end{centering}
282
283 \cleardoublepage
284
285 \title{Economical Implementation Of Linear Scaling Functions
286 In Microcontroller Software Using Rational Number
287 Approximation Techniques}
288
289 \author{David T. Ashley,
290 Joseph P. DeVoe,
291 Cory Pratt,
292 Karl Perttunen,
293 Anatoly Zhigljavsky
294 \thanks{D.T. Ashley, J.P. DeVoe, C. Pratt, and K.
295 Perttunen are with Visteon Automotive
296 Systems in Dearborn, Michigan, USA. E-mail:
297 \{dashley1, jdevoe, cpratt2, kperttun\}@visteon.com.
298 Anatoly Zhigljavsky is with Cardiff University,
299 Cardiff, UK.
300 E-mail: zhigljavskyaa@cardiff.ac.uk.}}
301
302 \markboth{ }{ }
303
304 \maketitle
305
306
307
308 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
309 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
310 % (1) ABSTRACT AND KEYWORDS %
311 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
312 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
313 \begin{abstract}
314 Inexpensive microcontrollers are widely used in
315 vehicles, consumer
316 electronics, laboratory equipment, and medical equipment.
317 A significant problem in the design of software
318 for these devices
319 is the efficient and reliable implementation of
320 arithmetic. In this paper,
321 techniques are developed to use an
322 instruction set typical of an
323 inexpensive microcontroller to economically approximate
324 linear scaling functions of the form
325 $f(x)=r_{I}x$ ($r_{I}$ non-negative and real but
326 not necessarily rational)
327 in the first quadrant using a rational approximation factor
328 $r_{A}=h/k$.
329 Methods and considerations in choosing $h$ and $k$ are
330 developed, and error terms are derived which bound the
331 error introduced by the rational approximation.
332 \end{abstract}
333
334
335 \begin{keywords}
336 Microcontroller arithmetic, linear scaling, rational approximation, Farey series,
337 continued fractions.
338 \end{keywords}
339
340 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
341 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
342 % (2) INTRODUCTION %
343 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
344 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
345 \section{Introduction}
346 \PARstart{L}{ow-cost} microcontrollers provide
347 weak instruction sets, and a significant
348 design challenge in the development of
349 software for these devices is the
350 economical implementation of arithmetic.
351 This paper presents techniques which are
352 suitable for economically implementing
353 high-precision linear scalings using
354 instructions which are characteristic of
355 inexpensive 4-bit and 8-bit microcontrollers.
356
357 This paper is confined
358 to the approximation of linear
359 scalings of the form
360 $y=r_{I}x$ ($r_I \in \realsetnonneg{}$, not
361 necessarily $\in \ratsetnonneg{}$)
362 by linear scalings of the form $y=hx/k$
363 ($h \in \intsetnonneg{}$, $k \in \intsetpos{}$).
364 In
365 Section \ref{sec:analysisapproxerr},
366 error terms for rational approximations
367 are derived without regard for how
368 integers $h$ and $k$ are chosen.
369 In
370 Section \ref{sec:methodshkchoose},
371 results from
372 number theory are presented which give
373 insight into how to choose rational
374 numbers $h/k$ for use as scaling factors.
375 In
376 Section \ref{sec:probresults},
377 probabilistic results from number theory are
378 presented outlining how close
379 to a real $r_I$ a rational
380 $r_A = h/k$ can typically be chosen.
381 In
382 Section \ref{sec:tabscalingfactors},
383 a special case in which
384 $k$ is chosen as an integral power of
385 two is developed with the aim of providing a
386 framework for tabulating scaling factors.
387 In
388 Section \ref{sec:imptechniques},
389 practical techniques for economically
390 implementing rational scaling functions
391 using inexpensive microcontroller
392 instruction sets are presented.
393 In Section \ref{sec:designexamples},
394 design examples which illustrate
395 the techniques are presented.
396
397 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
398 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
399 % (3) ANALYSIS OF APPROXIMATION ERROR (WITHOUT REGARD FOR HOW R_A IS CHOSEN) %
400 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
401 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
402 \section{Analysis Of Approximation Error}
403 \label{sec:analysisapproxerr}
404
405 A function $y=r_{I}x$
406 ($r_{I} \in \realsetnonneg{}$,
407 not necessarily $\in \ratsetnonneg{}$)
408 is to be approximated
409 by a function $y=r_{A}x$;
410 $r_{A}=h/k$, $\in \ratsetnonneg$.\footnote{Mnemonic for $r_I$ and $r_A$:
411 \emph{I}=ideal, \emph{A}=actual.}
412 In this section, error terms are
413 developed which bound
414 the error introduced when
415 $f(x)=r_{I}x$ is approximated
416 by $f(x)=r_{A}x$ in the first
417 quadrant only ($x \in \realsetnonneg{}$).
418
419
420 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
421 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
422 % (2)(A) MODEL FUNCTIONS %
423 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
424 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
425 \subsection{Model Functions}
426
427 (\ref{eq:eq0001}) through
428 (\ref{eq:eq0003}) provide
429 models of the function
430 to be approximated
431 which vary in whether
432 the domain is real or
433 integral, and in
434 whether the range is
435 real or integral.
436 The \emph{floor($\cdot{}$)} function,
437 denoted $\lfloor \cdot{} \rfloor$,
438 is used to model
439 the effect of quantization,
440 such as occurs when a real argument
441 is quantized for implementation
442 using integer arithmetic, or
443 when the fractional
444 part of a quotient is
445 discarded.\footnote{The \emph{ceiling($\cdot{}$)} function, denoted
446 $\lceil \cdot{} \rceil$, is also used and appears in many algebraic
447 results throughout the paper. There is often ambiguity in how
448 the \emph{floor($\cdot{}$)} and
449 \emph{ceiling($\cdot{}$)} functions are defined for negative
450 arguments. Here,
451 $\lfloor -1.1 \rfloor = \lceil -2.1 \rceil = -2$.}
452
453 In practical problems,
454 the domain and range may
455 be integral rather
456 than real for either
457 practical or conceptual reasons.
458 As an example of
459 a domain which is
460 integral for \emph{practical}
461 reasons, consider an embedded
462 software algorithm which has access
463 only to integral data
464 (as might happen with
465 integral vehicle speed
466 reported to an embedded software algorithm
467 over a network).
468 In this case,
469 the behavior of the software
470 may be specified only over
471 $\intsetnonneg$, as it is
472 impossible to excite the
473 software with non-integral
474 values. It may also happen that
475 the domain is \emph{conceptually}
476 integral, as occurs when the
477 input argument is a count or other
478 inherently integral quantity.
479 The range may also be integral for
480 similar practical or conceptual reasons.
481
482 (\ref{eq:eq0001}) provides a model of the ideal
483 function to be approximated when
484 both domain and range are the
485 non-negative real numbers.
486
487 \begin{equation}
488 \label{eq:eq0001}
489 F(x)=r_{I}x
490 \end{equation}
491
492 (\ref{eq:eq0002}) provides a model
493 of the ideal function to be
494 approximated when the function
495 is to be evaluated on a domain
496 of non-negative integers only.
497
498 \begin{equation}
499 \label{eq:eq0002}
500 G(x)= r_{I} \lfloor x \rfloor
501 \end{equation}
502
503 (\ref{eq:eq0004}) provides
504 a model of the ideal
505 function to be
506 approximated when
507 only the range is integral.
508
509 \begin{equation}
510 \label{eq:eq0004}
511 H(x)=\lfloor r_{I}x\rfloor
512 \end{equation}
513
514 (\ref{eq:eq0003}) provides
515 a model of the ideal
516 function to be aproximated
517 when both the
518 domain and range are the
519 non-negative integers.
520
521 \begin{equation}
522 \label{eq:eq0003}
523 I(x)=\lfloor r_{I}\lfloor x\rfloor\rfloor
524 \end{equation}
525
526 (\ref{eq:eq0005}) defines $r_{A}$,
527 the rational number used
528 to approximate $r_{I}$.
529 $h/k$ is always assumed reduced.
530
531 \begin{equation}
532 \label{eq:eq0005}
533 r_{A}=\frac{h}{k}; \; h \in \intsetnonneg; \; k \in \intsetpos
534 \end{equation}
535
536 (\ref{eq:eq0006}) provides
537 a model of the function which is
538 used to approximate
539 (\ref{eq:eq0001}),
540 (\ref{eq:eq0002}),
541 (\ref{eq:eq0004}),
542 or
543 (\ref{eq:eq0003}).
544 The approximation
545 always has an integral domain and range.
546
547 \begin{equation}
548 \label{eq:eq0006}
549 J(x) = \left\lfloor {r_A \left\lfloor x \right\rfloor } \right\rfloor
550 = \left\lfloor {\frac{{h\left\lfloor x \right\rfloor }}{k}} \right\rfloor
551 \end{equation}
552
553 (\ref{eq:eq0007})
554 defines an enhancement to
555 (\ref{eq:eq0006}).
556 The approximation error introduced
557 can be shifted using integral parameter $z$.
558
559 \begin{equation}
560 \label{eq:eq0007}
561 K(x) = \left\lfloor {\frac{{h\left\lfloor x \right\rfloor
562 + z}}{k}} \right\rfloor ; \; z \in \intset{}
563 \end{equation}
564
565 (\ref{eq:eq0009}) and (\ref{eq:eq0009b})
566 are special cases of (\ref{eq:eq0006}) and (\ref{eq:eq0007})
567 which are useful
568 in microcontroller work, since division by a power of two can be achieved
569 very economically using right-shift instructions.
570
571 \begin{equation}
572 \label{eq:eq0009}
573 L(x) = \left\lfloor {\frac{{h\left\lfloor x \right\rfloor }}{{2^q }}} \right\rfloor ;
574 \; k = 2^q ; \;r_A = \frac{h}{{2^q }}
575 \end{equation}
576
577 \begin{equation}
578 \label{eq:eq0009b}
579 M(x) = \left\lfloor {\frac{{h\left\lfloor x \right\rfloor } + z }{{2^q }}} \right\rfloor;
580 \; k = 2^q ; \; r_A = \frac{h}{{2^q }}
581 \end{equation}
582
583
584 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
585 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
586 % (3)(B)METHODS OF ERROR ANALYSIS %
587 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
588 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
589 \subsection{Methods Of Error Analysis}
590
591 Quantization of a real argument which is not necessarily
592 rational is treated by noting that
593 quantization introduces an error
594 $\varepsilon \in [0,1)$ (Eq. \ref{eq:dtaea0001}).
595
596 \begin{equation}
597 \label{eq:dtaea0001}
598 \left\lfloor x \right\rfloor = x - \varepsilon ;\;\varepsilon \in [0,1)
599 \end{equation}
600
601 Quantization of a rational argument $a/b$ is treated by
602 noting that the largest quantization error
603 $\varepsilon$ occurs when
604 $a$ is one less than an integral multiple of $b$
605 (Eq. \ref{eq:dtaea0002}).\footnote{Strictly speaking,
606 $\varepsilon \in \left\{ 0, \frac{1}{b}, \ldots,
607 \frac{b-2}{b}, \frac{b-1}{b} \right\}$; however, since
608 only the smallest and largest values are of interest,
609 (\ref{eq:dtaea0002}) is used.}
610
611 \begin{equation}
612 \label{eq:dtaea0002}
613 \left\lfloor \frac{a}{b} \right\rfloor
614 = \frac{a}{b} - \varepsilon ; \; \; \varepsilon \in \left[0, \frac{b-1}{b} \right]
615 \end{equation}
616
617 Since a difference of integers must also be
618 an integer, results on differences of quantized values
619 are constrained further by intersection with the set of integers.
620 Care must be taken in the intersection of an interval
621 with the
622 set of integers, as the
623 distinction between an open interval and a closed
624 interval is significant. The identities
625 in (\ref{eq:dtaea0003}) through
626 (\ref{eq:dtaea0006}) are employed.\footnote{In (\ref{eq:dtaea0003})
627 through (\ref{eq:dtaea0006}) and throughout the paper,
628 a subscript of $\intset{}$ is used to denote that
629 a set may contain only integers.}
630
631 \begin{equation}
632 \label{eq:dtaea0003}
633 {[ x , y ] \cap \intset{} = [ \lceil x \rceil , \lfloor y \rfloor ]}_{\intset{}}
634 \end{equation}
635
636 \begin{equation}
637 \label{eq:dtaea0004}
638 {[ x , y ) \cap \intset{} = [ \lceil x \rceil , \lceil y-1 \rceil ]}_{\intset{}}
639 \end{equation}
640
641 \begin{equation}
642 \label{eq:dtaea0005}
643 {( x , y ] \cap \intset{} = [ \lfloor x+1 \rfloor , \lfloor y \rfloor ]}_{\intset{}}
644 \end{equation}
645
646 \begin{equation}
647 \label{eq:dtaea0006}
648 {( x , y ) \cap \intset{} = [ \lfloor x+1 \rfloor , \lceil y-1 \rceil ]}_{\intset{}}
649 \end{equation}
650
651
652 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
653 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
654 % (3)(C)ERROR ANALYSIS OF {J(X),K(X)}-I(X) %
655 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
656 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
657 \subsection{Error Analysis Of $ \{ J(x),K(x) \} - I(x)$}
658
659 (\ref{eq:eq0006}) is a
660 special case of (\ref{eq:eq0007}),
661 so the difference function
662 $K(x)-I(x)$ with $z=0$
663 is $J(x)-I(x)$. For this reason it is not necessary
664 to derive $J(x)-I(x)$ separately.
665 The difference function (or error function) is the
666 difference between the ideal model function
667 with integral domain and range [$I(x)$], and the
668 approximation function with integral domain and range
669 [$J(x)$ or $K(x)$] (Eq. \ref{eq:eq0010}).
670
671 \begin{equation}
672 \label{eq:eq0010}
673 K(x) - I(x) = \left\lfloor {\frac{{h\left\lfloor x \right\rfloor
674 + z}}{k}} \right\rfloor
675 - \left\lfloor {r_I \left\lfloor x \right\rfloor } \right\rfloor
676 \end{equation}
677
678 The inner \emph{floor($\cdot{}$)} function can be removed
679 with the understanding that
680 the difference function
681 will be evaluated on a
682 domain of integers only (\ref{eq:eq0011}).
683
684 \begin{equation}
685 \label{eq:eq0011}
686 K(x) - I(x) = \left\lfloor {\frac{{hx
687 + z}}{k}} \right\rfloor
688 - \left\lfloor {r_I x} \right\rfloor ;\quad x \in \intsetnonneg{}
689 \end{equation}
690
691 Quantization (two occurrences of the
692 \emph{floor($\cdot{}$)} function)
693 can be modeled as introducing
694 errors $\varepsilon_1$ and $\varepsilon_2$
695 (\ref{eq:eq0012}).
696 Because the domain is integral,
697 the largest quantization error in
698 $\varepsilon_{1}$ occurs when $hx+z$
699 is one less than an integral multiple of $k$,
700 hence $\varepsilon _1 \in \left[ {0,\frac{{k - 1}}{k}} \right]$.
701 Because $r_{I}$ may be irrational,
702 $\varepsilon_{2}\in [0,1)$.
703
704 \begin{figure*}
705 \begin{equation}
706 \label{eq:eq0012}
707 K(x) - I(x) =
708 \frac{{hx + z}}{k} - \varepsilon _1 - r_I x + \varepsilon _2 ;\;x \in \intsetnonneg{};
709 \;\;
710 \varepsilon _1 \in \left[ {0,\frac{{k - 1}}{k}} \right];\;\;\varepsilon _2 \in \left[ {0,1} \right)
711 \end{equation}
712 \end{figure*}
713
714 Choosing the extremes
715 of $\varepsilon_{1}$ and $\varepsilon_{2}$
716 so as to minimize and maximize the
717 difference function
718 bounds the approximation error (\ref{eq:eq0014}).
719
720 \begin{figure*}
721 \begin{equation}
722 \label{eq:eq0014}
723 K(x) - I(x) \in
724 \left[ {(r_A - r_I )x + \frac{z}{k} -
725 \frac{{k - 1}}{k},(r_A - r_I )x + \frac{z}{k} + 1} \right)
726 \end{equation}
727 \end{figure*}
728
729 (\ref{eq:eq0014}) may
730 be intersected with the set of integers,
731 because the result, a difference of integers,
732 must also be an integer (\ref{eq:eq0015}).
733
734 \begin{figure*}
735 \begin{equation}
736 \label{eq:eq0015}
737 K(x) - I(x) \in
738 \left[ {\left\lceil {(r_A - r_I )x + \frac{z}{k} -
739 \frac{{k - 1}}{k}} \right\rceil ,
740 \left\lceil {(r_A - r_I )x + \frac{z}{k}} \right\rceil } \right]_{\intset{}}
741 \end{equation}
742 \end{figure*}
743
744 With $z=0$, (\ref{eq:eq0015}) supplies $J(x)-I(x)$ (\ref{eq:eq0016}).
745
746 \begin{figure*}
747 \begin{equation}
748 \label{eq:eq0016}
749 J(x) - I(x) \in
750 \left[ {\left\lceil {(r_A - r_I )x -
751 \frac{{k - 1}}{k}} \right\rceil ,
752 \left\lceil {(r_A - r_I )x} \right\rceil } \right]_{\intset{}}
753 \end{equation}
754 \end{figure*}
755
756 $r_{A}$ must almost always
757 be chosen unequal to $r_{I}$,
758 and as a result the approximation error is
759 larger for larger $x$. Most
760 approximations are used only in a
761 restricted domain, and it is useful
762 to know the upper bound on approximation
763 error when the approximation
764 is used only in an interval
765 $[0,x_{MAX}]_{\intset{}}$, $x_{MAX} \in \intsetpos{}$.\footnote{Throughout
766 the paper, it is assumed that $x_{MAX} \in \intsetpos{}$.}
767 These upper bounds can be obtained by
768 substitution into (\ref{eq:eq0015}),
769 and are presented as (\ref{eq:eq0017}).
770 Note that the second case of (\ref{eq:eq0017})
771 may not be distinct,
772 depending on the choice of $z$.
773
774 \begin{figure*}
775 \begin{equation}
776 \label{eq:eq0017}
777 \left. {K(x) - I(x)} \right|_{x \in [0,x_{MAX} ]_{\intset{}}} \in
778 \left\{ {\begin{array}{*{20}l}
779 {\left[ {\left\lceil {(r_A - r_I )x_{MAX} + \frac{z}{k} - \frac{{k - 1}}{k}}
780 \right\rceil , \left\lceil {\frac{z}{k}} \right\rceil} \right]_{\intset{}} ,} \hfill & {r_A \le r_I - \frac{z+1}{{x_{MAX} k}}} \\
781 \\
782 { \left[ {0, \left\lceil {\frac{z}{k} } \right\rceil} \right]_{\intset{}},} \hfill & {r_I - \frac{z+1}{{x_{MAX} k}} < r_A \le r_I } \\
783 \\
784 \left[ { \left\lceil {\frac{z}{k} - \frac{k-1}{k}} \right\rceil , \left\lceil {\frac{z}{k}} \right\rceil } \right]_{\intset{}} , \hfill & {r_A = r_I} \\
785 \\
786 {\left[ { \left\lceil {\frac{z}{k} - \frac{k-1}{k}} \right\rceil ,
787 \left\lceil {(r_A - r_I )x_{MAX} + \frac{z}{k} } \right\rceil } \right]_{\intset{}} ,}
788 \hfill & {r_A > r_I } \\
789 \end{array}} \right.
790 \end{equation}
791 \end{figure*}
792
793 With $z=0$, analogous results for $J(x)-I(x)$
794 are obtained (\ref{eq:eq0018}).
795
796 \begin{figure*}
797 \begin{equation}
798 \label{eq:eq0018}
799 \left. {J(x) - I(x)} \right|_{x \in [0,x_{MAX} ]_{\intset{}}} \in
800 \left\{ {\begin{array}{*{20}l}
801 {\left[ {\left\lceil {(r_A - r_I )x_{MAX} - \frac{{k - 1}}{k}} \right\rceil ,0}
802 \right]_{\intset{}} ,} \hfill & {r_A \le r_I - \frac{1}{{x_{MAX} k}}} \\
803 \\
804 {\{ 0\} ,} \hfill & {r_I - \frac{1}{{x_{MAX} k}} < r_A \le r_I } \\
805 \\
806 {\left[ {0,\left\lceil {(r_A - r_I )x_{MAX} } \right\rceil } \right]_{\intset{}} ,}
807 \hfill & {r_A > r_I } \\
808 \end{array}} \right.
809 \end{equation}
810 \end{figure*}
811
812 In practice, there are three useful choices of the
813 parameter $z$. (\ref{eq:eq0019})
814 supplies the choice of $z$ which will assure that the
815 approximation error is never negative. (\ref{eq:eq0020}) supplies
816 the choice of $z$ which will assure that the approximation error
817 is never positive. (\ref{eq:eq0021})
818 supplies the choice of $z$ which will
819 center the approximation error about zero.
820
821 \begin{equation}
822 \label{eq:eq0019}
823 z_{NONEG} = \left\{ {\begin{array}{*{20}c}
824 {\left\lceil {(r_I - r_A )x_{MAX} k} \right\rceil ,}
825 \hfill & {} \hfill & {r_A < r_I } \hfill \\
826 {0,} \hfill & {} \hfill & {r_A \ge r{}_I} \hfill \\
827 \end{array}} \right.
828 \end{equation}
829
830 \begin{equation}
831 \label{eq:eq0020}
832 z_{NOPOS} = \left\{ {\begin{array}{*{20}c}
833 {0,} \hfill & {} \hfill & {r_A \le r_I } \hfill \\
834 {\left\lfloor {(r_I - r_A )x_{MAX} k} \right\rfloor ,}
835 \hfill & {} \hfill & {r_A > r{}_I} \hfill \\
836 \end{array}} \right.
837 \end{equation}
838
839 \begin{equation}
840 \label{eq:eq0021}
841 z_{CENTER} = \left\lfloor {\frac{{(r_I - r_A )x_{MAX} k}}{2}} \right\rfloor
842 \end{equation}
843
844 \begin{example}
845 In a vehicle software load, vehicle speed
846 is received in network messages as
847 integral KPH, and is to be converted to MPH and
848 retransmitted over a second network as integral MPH.
849 If $r_{A}$=59/95$\approx$0.62105263 is used to approximate
850 $r_{I}\approx$ 0.6214 (the ideal conversion factor
851 from KPH to MPH), how much error might be introduced by
852 this rational approximation (vs.
853 retransmitting the quantized product of $r_I$
854 and the received vehicle speed) for received
855 vehicle speeds up to 255 KPH?
856 \end{example}
857
858 \emph{Solution:} In this example,
859 the domain is integral and the range
860 is integral, so (\ref{eq:eq0018})
861 applies with $x_{MAX}=255$.
862 The first row of (\ref{eq:eq0018})
863 predicts that the error
864 will always be in $[-1,0]_{\intset{}}$=\{-1,0\},
865 so that the calculated integral
866 MPH may be up to one count less than
867 implied by $I(x)$ with $r_{I}=0.6214$.
868
869
870 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
871 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
872 % (3)(D)ERROR ANALYSIS OF {J(X),K(X)}-G(X) %
873 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
874 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
875 \subsection{Error Analysis Of $\{ J(x),K(x) \} - G(x)$ }
876
877 Because (\ref{eq:eq0006}) is a special
878 case of (\ref{eq:eq0007}),
879 the difference function $K(x)-G(x)$ with $z=0$
880 is $J(x)-G(x)$; hence
881 there is no need to derive $J(x)-G(x)$
882 explicitly.
883
884 \begin{equation}
885 \label{eq:eq0022}
886 K(x) - G(x) = \left\lfloor {\frac{{h\left\lfloor x \right\rfloor
887 + z}}{k}} \right\rfloor - r_I \left\lfloor x \right\rfloor
888 \end{equation}
889
890 The inner \emph{floor($\cdot{}$)}
891 function of (\ref{eq:eq0022}) can be removed with the
892 understanding that the difference function will be
893 evaluated on a domain of
894 integers only (\ref{eq:eq0023}).
895 The difference
896 function (\ref{eq:eq0023}) is real
897 (not required to be rational or integral).
898
899 \begin{equation}
900 \label{eq:eq0023}
901 K(x) - G(x) = \left\lfloor {\frac{{hx
902 + z}}{k}} \right\rfloor - r_I x;\quad x \in \intsetnonneg{}
903 \end{equation}
904
905 The arguments which support the
906 derivation of (\ref{eq:eq0011}) through
907 (\ref{eq:eq0021}) also support the derivation
908 of (\ref{eq:eq0023}) through (\ref{eq:eq0030}).
909 (\ref{eq:eq0028}), (\ref{eq:eq0029}), and (\ref{eq:eq0030})
910 supply choices of the parameter $z$
911 which ensure that the difference
912 function is never negative,
913 never positive, and
914 centered about zero, respectively.
915
916 \begin{figure*}
917 \begin{equation}
918 \label{eq:eq0024}
919 K(x) - G(x) \in
920 \left[ {(r_A - r_I )x + \frac{z}{k} - \frac{{k - 1}}{k},(r_A - r_I )x +
921 \frac{z}{k}} \right]
922 \end{equation}
923 \end{figure*}
924
925 \begin{figure*}
926 \begin{equation}
927 \label{eq:eq0025}
928 \left. {K(x) - G(x)} \right|_{x \in [0,x_{MAX} ]_{\intset{}}} \in
929 \left\{ {\begin{array}{*{20}c}
930 {\left[ {(r_A - r_I )x_{MAX} + \frac{z}{k} - \frac{{k - 1}}{k},\frac{z}{k}} \right] ,}
931 \hfill & {r_A < r_I } \hfill \\
932 \\
933 {\left[ {\frac{z}{k} - \frac{{k - 1}}{k},\frac{z}{k}} \right] ,} \hfill & {r_A = r_I }
934 \hfill \\
935 \\
936 {\left[ {\frac{z}{k} - \frac{{k - 1}}{k},(r_A - r_I )x_{MAX} + \frac{z}{k}} \right] ,}
937 \hfill & {r_A > r_I } \hfill \\
938 \end{array}} \right.
939 \end{equation}
940 \end{figure*}
941
942 \begin{figure*}
943 \begin{equation}
944 \label{eq:eq0026}
945 J(x) - G(x) \in
946 \left[ {(r_A - r_I )x - \frac{{k - 1}}{k},(r_A - r_I )x} \right]
947 \end{equation}
948 \end{figure*}
949
950 \begin{figure*}
951 \begin{equation}
952 \label{eq:eq0027}
953 \left. {J(x) - G(x)} \right|_{x \in [0,x_{MAX} ]_{\intset{}}} \in
954 \left\{ {\begin{array}{*{20}c}
955 {\left[ {(r_A - r_I )x_{MAX} - \frac{{k - 1}}{k},0} \right] ,} \hfill & {r_A < r_I }
956 \hfill \\
957 \\
958 {\left[ { - \frac{{k - 1}}{k},0} \right] ,} \hfill & {r_A = r_I } \hfill \\
959 \\
960 {\left[ { - \frac{{k - 1}}{k},(r_A - r_I )x_{MAX} } \right] ,} \hfill & {r_A > r_I }
961 \hfill \\
962 \end{array}} \right.
963 \end{equation}
964 \end{figure*}
965
966 \begin{figure*}
967 \begin{equation}
968 \label{eq:eq0028}
969 z_{NONEG} = \left\{ {\begin{array}{ll}
970 {\left\lceil {(r_I - r_A )x_{MAX} k + k - 1} \right\rceil ,} & {r_A < r_I } \\
971 & \\
972 {k-1,} \hfill & {r_A \ge r{}_I} \\
973 \end{array}} \right.
974 \end{equation}
975 \end{figure*}
976
977 \begin{equation}
978 \label{eq:eq0029}
979 z_{NOPOS} = \left\{ {\begin{array}{*{20}c}
980 {0,} \hfill & {} \hfill & {r_A \le r_I } \hfill \\
981 {\left\lfloor {(r_I - r_A )x_{MAX} k} \right\rfloor ,} \hfill & {} \hfill & {r_A > r{}_I}
982 \hfill \\
983 \end{array}} \right.
984 \end{equation}
985
986 \begin{equation}
987 \label{eq:eq0030}
988 z_{CENTER} = \left\lfloor {\frac{{(r_I - r_A )x_{MAX} k + k}}{2}} \right\rfloor
989 \end{equation}
990
991 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
992 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
993 % (3)(E)ERROR ANALYSIS OF {J(X),K(X)}-H(X) %
994 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
995 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
996 \subsection{Error Analysis Of $ \{ J(x),K(x) \} - H(x)$}
997
998 Because (\ref{eq:eq0006}) is a special case of (\ref{eq:eq0007}),
999 the difference function $K(x)-H(x)$ with $z=0$
1000 is $J(x)-H(x)$; hence there is no
1001 need to derive $J(x)-H(x)$ explicitly.
1002
1003 \begin{equation}
1004 \label{eq:eq0037}
1005 K(x) - H(x) = \left\lfloor {\frac{{h\left\lfloor x \right\rfloor
1006 + z}}{k}} \right\rfloor - \left\lfloor {r_I x} \right\rfloor
1007 \end{equation}
1008
1009 (\ref{eq:eq0037}) corresponds to the
1010 approximation error introduced when a function with
1011 a real domain and integral range is approximated using a
1012 function with an integral domain and range. The error
1013 term supplied by (\ref{eq:eq0037}) is integral.
1014
1015 The three quantizations in (\ref{eq:eq0037}) can be treated
1016 by introducing $\varepsilon_{1}$, $\varepsilon_{2}$, and $\varepsilon_{3}$
1017 (\ref{eq:eq0038}).
1018
1019 \begin{figure*}
1020 \begin{equation}
1021 \label{eq:eq0038}
1022 K(x) - H(x) = \frac{{h(x - \varepsilon _1 ) + z}}{k} - \varepsilon _2 - r_I x + \varepsilon _3
1023 ; \;\;
1024 \varepsilon _1 \in [0,1)
1025 ; \;\;
1026 \varepsilon _2 \in \left[ {0,\frac{{k - 1}}{k}} \right]
1027 ; \;\;
1028 \varepsilon _3 \in [0,1)
1029 \end{equation}
1030 \end{figure*}
1031
1032 Evaluating (\ref{eq:eq0038}) at the
1033 extremes of $\varepsilon_{1}$,
1034 $\varepsilon_{2}$,
1035 and $\varepsilon_{3}$ leads
1036 to (\ref{eq:eq0042}).
1037
1038 \begin{figure*}
1039 \begin{equation}
1040 \label{eq:eq0042}
1041 K(x) - H(x) \in
1042 \left( {(r_A - r_I )x - r_A + \frac{z}{k} - \frac{{k - 1}}{k},(r_A - r_I )x +
1043 \frac{z}{k} + 1} \right)
1044 \end{equation}
1045 \end{figure*}
1046
1047 Intersection of (\ref{eq:eq0042}) with the set
1048 of integers leads to (\ref{eq:eq0042b}).
1049
1050 \begin{figure*}
1051 \begin{equation}
1052 \label{eq:eq0042b}
1053 K(x) - H(x) \in
1054 {
1055 \left[
1056 {
1057 {
1058 \left\lfloor
1059 {
1060 (r_A - r_I) x - r_A + \frac{z}{k} + \frac{1}{k}
1061 }
1062 \right\rfloor
1063 }
1064 ,
1065 {
1066 \left\lceil
1067 {
1068 (r_A - r_I) x + \frac{z}{k}
1069 }
1070 \right\rceil
1071 }
1072 }
1073 \right]
1074 }_{\intset{}}
1075 \end{equation}
1076 \end{figure*}
1077
1078 Evaluating (\ref{eq:eq0042b}) at the
1079 extremes of $[0,x_{MAX}]$
1080 yields (\ref{eq:eq0043}). With $z=0$, (\ref{eq:eq0043})
1081 supplies $J(x) - H(x)$ (Eq. \ref{eq:eq0044}).
1082
1083 \begin{figure*}
1084 \begin{equation}
1085 \label{eq:eq0043}
1086 \left. {K(x) - H(x)} \right|_{x \in [0,x_{MAX} ] } \in
1087 \left\{ {\begin{array}{*{20}l}
1088 {\left[ {\left\lfloor {(r_A - r_I )x_{MAX} - r_A + \frac{z}{k} + \frac{1}{k}}
1089 \right\rfloor ,\left\lceil {\frac{z}{k}} \right\rceil } \right] _{\intset{}} ,}
1090 \hfill & {r_A < r_I } \\
1091 \\
1092 {\left[ {\left\lfloor { - r_A + \frac{z}{k} + \frac{1}{k}} \right\rfloor ,
1093 \left\lceil {\frac{z}{k}} \right\rceil } \right] _{\intset{}} ,}
1094 \hfill & {r_A = r_I }\\
1095 \\
1096 {\left[ {\left\lfloor { - r_A + \frac{z}{k} + \frac{1}{k}} \right\rfloor ,
1097 \left\lceil {(r_A - r_I )x_{MAX} + \frac{z}{k}} \right\rceil } \right] _{\intset{}},}
1098 \hfill & {r_A > r_I } \\
1099 \end{array}} \right.
1100 \end{equation}
1101 \end{figure*}
1102
1103 \begin{figure*}
1104 \begin{equation}
1105 \label{eq:eq0044}
1106 \left. {J(x) - H(x)} \right|_{x \in [0,x_{MAX} ] } \in
1107 \left\{ {\begin{array}{*{20}l}
1108 {\left[ {\left\lfloor {(r_A - r_I )x_{MAX} - r_A + \frac{1}{k}}
1109 \right\rfloor , 0 } \right] _{\intset{}} ,}
1110 \hfill & {r_A < r_I } \\
1111 \\
1112 {\left[ {\left\lfloor { - r_A + \frac{1}{k}} \right\rfloor ,
1113 { 0 } } \right] _{\intset{}} ,}
1114 \hfill & {r_A = r_I }\\
1115 \\
1116 {\left[ {\left\lfloor { - r_A + \frac{1}{k}} \right\rfloor ,
1117 \left\lceil {(r_A - r_I )x_{MAX}} \right\rceil } \right] _{\intset{}},}
1118 \hfill & {r_A > r_I } \\
1119 \end{array}} \right.
1120 \end{equation}
1121 \end{figure*}
1122
1123 (\ref{eq:eq0044a}), (\ref{eq:eq0044b}), and (\ref{eq:eq0044c})
1124 supply choices of the parameter $z$ which
1125 ensure that the difference function is never negative,
1126 never positive, and centered about zero, respectively.
1127
1128 \begin{figure*}
1129 \begin{equation}
1130 \label{eq:eq0044a}
1131 z_{NONEG} = \left\{ {\begin{array}{ll}
1132 {\left\lceil {(r_I - r_A )x_{MAX} k + r_A k - 1} \right\rceil ,} & {r_A < r_I } \\
1133 & \\
1134 {\lceil r_A k-1 \rceil ,} \hfill & {r_A \ge r_I} \\
1135 \end{array}} \right.
1136 \end{equation}
1137 \end{figure*}
1138
1139 \begin{equation}
1140 \label{eq:eq0044b}
1141 z_{NOPOS} = \left\{ {\begin{array}{*{20}c}
1142 {0,} \hfill & {} \hfill & {r_A \le r_I } \hfill \\
1143 {\left\lfloor {(r_I - r_A )x_{MAX} k} \right\rfloor ,} \hfill & {} \hfill & {r_A > r{}_I}
1144 \hfill \\
1145 \end{array}} \right.
1146 \end{equation}
1147
1148 \begin{equation}
1149 \label{eq:eq0044c}
1150 z_{CENTER}
1151 =
1152 \left\lfloor {\frac{{(r_I - r_A )x_{MAX} k + r_A k}}{2}} \right\rfloor
1153 \end{equation}
1154
1155
1156 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1157 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1158 % (3)(F)ERROR ANALYSIS OF {J(X),K(X)}-F(X) %
1159 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1160 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1161 \subsection{Error Analysis Of $ \{ J(x), K(x) \} - F(x)$}
1162
1163 Because (\ref{eq:eq0006}) is a special case of (\ref{eq:eq0007}),
1164 the difference function $K(x)-F(x)$ with $z=0$ is
1165 $J(x)-F(x)$; hence there is no
1166 need to derive $J(x)-F(x)$ explicitly.
1167
1168 \begin{equation}
1169 \label{eq:eq0031}
1170 K(x) - F(x) = \left\lfloor {\frac{{h\left\lfloor x \right\rfloor
1171 + z}}{k}} \right\rfloor - r_I x
1172 \end{equation}
1173
1174 (\ref{eq:eq0031}) corresponds to the approximation
1175 error introduced when a function with a
1176 real domain and range is approximated
1177 using a function with an integral domain and range.
1178 The error term supplied by (\ref{eq:eq0031})
1179 is real rather than integral.
1180
1181 The two quantizations in (\ref{eq:eq0031})
1182 can be treated by introducing $\varepsilon_{1}$
1183 and $\varepsilon_{2}$ (\ref{eq:eq0032}).
1184
1185 \begin{figure*}
1186 \begin{equation}
1187 \label{eq:eq0032}
1188 K(x) - F(x) = \frac{{h(x - \varepsilon _1 ) + z}}{k} - \varepsilon _2 - r_I x
1189 ; \;
1190 \varepsilon _1 \in [0,1)
1191 ; \;
1192 \varepsilon _2 \in \left[ {0,\frac{{k - 1}}{k}} \right]
1193 \end{equation}
1194 \end{figure*}
1195
1196 Choosing the extremes of
1197 $\varepsilon_{1}$ and $\varepsilon_{2}$
1198 so as to minimize and maximize the difference
1199 function bounds the approximation error (\ref{eq:eq0035}).
1200
1201 \begin{figure*}
1202 \begin{equation}
1203 \label{eq:eq0035}
1204 K(x) - F(x) \in
1205 \left( {(r_A - r_I )x - r_A + \frac{z}{k} - \frac{{k - 1}}{k},(r_A - r_I )x +
1206 \frac{z}{k}} \right]
1207 \end{equation}
1208 \end{figure*}
1209
1210 Minimizing and maximizing (\ref{eq:eq0035}) over
1211 a domain of $[0,x_{MAX}]$ gives (\ref{eq:eq0035b}). With
1212 $z=0$, (\ref{eq:eq0035b}) supplies $J(x)-F(x)$ (Eq. \ref{eq:eq0036}).
1213
1214
1215 \begin{figure*}
1216 \begin{equation}
1217 \label{eq:eq0035b}
1218 \left. {K(x) - F(x)} \right|_{x \in [0,x_{MAX} ]} \in
1219 \left\{ {\begin{array}{*{20}c}
1220 {\left( {(r_A - r_I )x_{MAX} - r_A + \frac{z}{k }- \frac{{k - 1}}{k}, \frac{z}{k}} \right],}
1221 \hfill & {r_A < r_I } \hfill \\
1222 \\
1223 {\left( { - r_A + \frac{z}{k} - \frac{{k - 1}}{k}, \frac{z}{k}} \right],} \hfill & {r_A = r_I } \hfill \\
1224 \\
1225 {\left( { - r_A + \frac{z}{k} - \frac{{k - 1}}{k},(r_A - r_I )x_{MAX} + \frac{z}{k}} \right] ,}
1226 \hfill & {r_A > r_I } \hfill \\
1227 \end{array}} \right.
1228 \end{equation}
1229 \end{figure*}
1230
1231
1232 \begin{figure*}
1233 \begin{equation}
1234 \label{eq:eq0036}
1235 \left. {J(x) - F(x)} \right|_{x \in [0,x_{MAX} ]} \in
1236 \left\{ {\begin{array}{*{20}c}
1237 {\left( {(r_A - r_I )x_{MAX} - r_A - \frac{{k - 1}}{k},0} \right],}
1238 \hfill & {r_A < r_I } \hfill \\
1239 \\
1240 {\left( { - r_A - \frac{{k - 1}}{k},0} \right],} \hfill & {r_A = r_I } \hfill \\
1241 \\
1242 {\left( { - r_A - \frac{{k - 1}}{k},(r_A - r_I )x_{MAX} } \right] ,}
1243 \hfill & {r_A > r_I } \hfill \\
1244 \end{array}} \right.
1245 \end{equation}
1246 \end{figure*}
1247
1248 (\ref{eq:eqkminusfzterm01}),
1249 (\ref{eq:eqkminusfzterm02}), and
1250 (\ref{eq:eqkminusfzterm03}) supply choices of the
1251 parameter $z$ which ensure that the difference function
1252 is never negative, never positive, and centered
1253 about zero, respectively.
1254
1255 \begin{figure*}
1256 \begin{equation}
1257 \label{eq:eqkminusfzterm01}
1258 z_{NONEG} = \left\{ {\begin{array}{ll}
1259 {\left\lceil {(r_I - r_A) x_{MAX} k + r_A k + k - 1} \right\rceil ,} & {r_A < r_I } \\
1260 & \\
1261 {\left\lceil {r_A k + k - 1} \right\rceil ,} & {r_A \ge r{}_I}\\
1262 \end{array}} \right.
1263 \end{equation}
1264 \end{figure*}
1265
1266 \begin{equation}
1267 \label{eq:eqkminusfzterm02}
1268 z_{NOPOS} = \left\{ {\begin{array}{*{20}c}
1269 {0,} \hfill & {} \hfill & {r_A \le r_I } \hfill \\
1270 {\left\lfloor {(r_I - r_A )x_{MAX} k} \right\rfloor ,}
1271 \hfill & {} \hfill & {r_A > r{}_I} \hfill \\
1272 \end{array}} \right.
1273 \end{equation}
1274
1275 \begin{equation}
1276 \label{eq:eqkminusfzterm03}
1277 z_{CENTER}
1278 =
1279 \left\lfloor {\frac{{(r_I - r_A )x_{MAX} k + r_A k + k}}{2}} \right\rfloor
1280 \end{equation}
1281
1282
1283 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1284 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1285 % (4) METHODS OF CHOOSING H AND K TO MATCH R_I WITH AN R_A %
1286 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1287 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1288 \section{Methods Of Choosing $h$ And $k$}
1289 \label{sec:methodshkchoose}
1290
1291
1292 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1293 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1294 % (4)(A)INTRODUCTION TO THE SECTION, GENERAL REMARKS %
1295 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1296 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1297 In this section, algorithms for choosing
1298 $h$ and $k$ subject to the constraints $h \leq h_{MAX}$ and
1299 $k \leq k_{MAX}$ in order to place $r_{A}=h/k$
1300 close to $r_{I}$ are presented. The algorithms are presented
1301 in order of increasing sophistication
1302 (and efficiency).\footnote{Although
1303 it won't be shown in this paper,
1304 if $N = k_{MAX}$ is the maximum allowable denominator,
1305 Algorithm \ref{alg:algstartingatint}
1306 is $O(N^2)$,
1307 Algorithm \ref{alg:algstartingatprime} is
1308 $O(N)$, and the continued fraction
1309 algorithm is $O(log N)$.}
1310
1311
1312
1313
1314
1315 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1316 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1317 % (4)(C)FAREY SERIES AND RELATED THEOREMS) %
1318 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1319 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1320 \subsection{Farey Series Methods Of Choosing $h$ And $k$}
1321
1322 The \emph{Farey series
1323 of order $N$}, denoted $F_{N}$,
1324 is the ordered set of all irreducible
1325 rational numbers $h/k$ in the interval
1326 [0,1]
1327 with a denominator $k\leq k_{MAX}$.
1328 As an example, the Farey series of
1329 order 5, $F_5$, is shown in (\ref{eq:eq0045}).
1330
1331 \begin{equation}
1332 \label{eq:eq0045}
1333 F_5 = \left\{ {\frac{0}{1},\frac{1}{5},\frac{1}{4},
1334 \frac{1}{3},\frac{2}{5},\frac{1}{2},
1335 \frac{3}{5},\frac{2}{3},\frac{3}{4},
1336 \frac{4}{5},\frac{1}{1}} \right\}
1337 \end{equation}
1338
1339 The distribution of Farey rational numbers in
1340 [0,1] is repeated
1341 in any
1342 $[n,n+1]$, $n\in \intset$; so that the distribution of
1343 Farey rationals in [0,1] supplies complete
1344 information about the distribution in
1345 all of $\realset$.\footnote{We
1346 occasionally abuse the proper nomenclature by referring
1347 to sequential rational numbers outside the
1348 interval [0,1] as Farey terms or as part of
1349 $F_N$, which, technically, they are not.
1350 All of the results presented in
1351 this paper can be shown to apply
1352 everywhere in $\realset$, so this abuse
1353 is not harmful.}
1354
1355 \begin{theorem}
1356 \label{thm:thm01}
1357 If $H/K$ and $h/k$ are two successive terms of $F_{N}$,
1358 then:
1359 \end{theorem}
1360
1361 \begin{equation}
1362 \label{eq:eq0048}
1363 K h - H k = 1
1364 \end{equation}
1365
1366 \emph{Note:} This condition is necessary but not
1367 sufficient for $h/k$ to be the Farey successor of $H/K$.
1368 In general, there is
1369 more than one $h/k$ with $k \leq k_{MAX}$ such that $Kh - Hk = 1$.
1370
1371 \begin{proof}
1372 See \cite{HardyAndWrightClassic} p.23, \cite{LeVeque} p.222.
1373 \end{proof}
1374
1375 \begin{theorem}
1376 \label{thm:thm03}
1377 If $H/K$ and $h/k$ are two successive terms of $F_{N}$, then:
1378 \end{theorem}
1379
1380 \begin{equation}
1381 \label{eq:eq0050}
1382 K + k > N
1383 \end{equation}
1384
1385 \emph{Note:} This condition is necessary but not
1386 sufficient for $h/k$ to be the Farey successor of $H/K$.
1387
1388 \begin{proof}
1389 See \cite{HardyAndWrightClassic} p.23.
1390 \end{proof}
1391
1392 \begin{theorem}
1393 \label{thm:thm04}
1394 If $h_{j-2}/k_{j-2}$, $h_{j-1}/k_{j-1}$, and $h_{j}/k_{j}$
1395 are three consecutive terms of $F_{N}$, then:
1396 \end{theorem}
1397
1398 \begin{equation}
1399 \label{eq:eq0051}
1400 h_{j} = \left\lfloor {\frac{{k_{j-2}
1401 + N}}{{k_{j - 1} }}} \right\rfloor h_{j - 1} - h_{j-2}
1402 \end{equation}
1403
1404 \begin{equation}
1405 \label{eq:eq0052}
1406 k_{j} = \left\lfloor {\frac{{k_{j-2} + N}}{{k_{j
1407 - 1} }}} \right\rfloor k_{j - 1} - k_{j-2}
1408 \end{equation}
1409
1410 \emph{Notes:} (1)Theorem \ref{thm:thm04} gives
1411 recursive formulas for
1412 generating successive terms in $F_N$
1413 if two consecutive terms are known.
1414 (2)Equations (\ref{eq:eq0051}) and
1415 (\ref{eq:eq0052}) can be solved to
1416 allow generation of terms in the decreasing direction
1417 (\ref{eq:eq0053}, \ref{eq:eq0054}).
1418
1419 \begin{equation}
1420 \label{eq:eq0053}
1421 h_j = \left\lfloor {\frac{{k_{j + 2} + N}}{{k_{j + 1} }}} \right\rfloor h_{j + 1} - h_{j + 2}
1422 \end{equation}
1423
1424 \begin{equation}
1425 \label{eq:eq0054}
1426 k_j = \left\lfloor {\frac{{k_{j + 2} + N}}{{k_{j + 1} }}} \right\rfloor k_{j + 1} - k_{j + 2}
1427 \end{equation}
1428
1429 \begin{proof}
1430 See \cite{SchroederClassic} p.83.
1431 \end{proof}
1432
1433 In general, given only a single irreducible rational number $h/k$,
1434 there is no method to find the immediate
1435 predecessor or successor in $F_N$ without some
1436 iteration (Eqns. \ref{eq:eq0051},
1437 \ref{eq:eq0052},
1438 \ref{eq:eq0053}, and \ref{eq:eq0054} require
1439 two successive elements). However, if the
1440 irreducible rational number is an integer $i=i/1$, the
1441 predecessor and successor in $F_N$ are $(i N - 1)/N$ and
1442 $(i N + 1)/N$, so it is convenient to build $F_N$
1443 in either direction starting
1444 at an integer. This suggests an algorithm for
1445 finding the closest rational numbers in
1446 $F_N$ to an $r_I$ when $N$ is small.
1447
1448 \begin{algorithm}\label{alg:algstartingatint}\end{algorithm}
1449 \begin{alglvl0}
1450 \item Choose an integer $i$ as either
1451 $\lfloor{}r_I\rfloor$ or $\lceil{}r_I\rceil$.
1452 \item If $i=\lfloor{}r_I\rfloor$ is chosen, use
1453 $h_{j-2}/k_{j-2} = i/1$, $h_{j-1}/k_{j-1} = (i N + 1)/N$
1454 and use (\ref{eq:eq0051}) and (\ref{eq:eq0052})
1455 to build successive increasing
1456 terms in $F_N$ until
1457 the terms which enclose $r_I$ are found.
1458 If $i=\lceil{}r_I\rceil$ is chosen, use
1459 $h_{j+2}/k_{j+2} = i/1$, $h_{j+1}/k_{j+1} = (i N - 1)/N$
1460 and use (\ref{eq:eq0053})
1461 and (\ref{eq:eq0054}) to build successive
1462 decreasing terms in $F_N$ until
1463 the terms which enclose $r_I$ are
1464 found.\footnote{This procedure is easily carried
1465 out with spreadsheet software, such as
1466 \emph{Microsoft Excel}.}
1467 \end{alglvl0}
1468
1469 The following additional theorem is presented,
1470 which can be useful in finding the next term
1471 of $F_N$ given only a single term.
1472
1473 \begin{theorem}
1474 \label{thm:thm05}
1475 If $H/K$ is a term of $F_{N}$,
1476 the immediate successor of $H/K$
1477 in $F_{N}$ is the $h/k$ satisfying
1478 $Kh-Hk=1$ with the largest
1479 denominator $k\leq N$.
1480 \end{theorem}
1481
1482 \begin{proof}
1483 Any potential successor of $H/K$
1484 which meets $Kh-Hk=1$ can be formed
1485 by adding $1/Kk$ to $H/K$
1486 (\ref{eq:eq0055}, \ref{eq:eq0056}).
1487
1488 \begin{eqnarray}
1489 \label{eq:eq0055}
1490 & Kh - Hk = 1 & \\
1491 & \Downarrow & \nonumber \\
1492 \label{eq:eq0056}
1493 & \displaystyle {\frac{h}{k} = \frac{{1 + Hk}}{{Kk}} = \frac{H}{K} + \frac{1}{{Kk}}} &
1494 \end{eqnarray}
1495
1496 If $h/k$ and $h'/k'$ both
1497 satisfy $Kh-Hk=1$ with $k'<k\leq{}N$, then
1498 $H/K<h/k<h'/k'$. Thus the $h/k$
1499 with the largest denominator $\leq N$
1500 that meets $Kh-Hk=1$ is the successor
1501 in $F_{N}$ to $H/K$.
1502 \end{proof}
1503
1504 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1505 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1506 % (4)(D)ALGORITHM 1: BUILD F_N AND SURROUND R_I %
1507 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1508 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1509
1510
1511
1512
1513 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1514 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1515 % (4)(E)ALGORITHM 2: BUILD F_N STARTING AT P/K_MAX %
1516 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1517 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1518 Finding the Farey successor from a single Farey
1519 term $\notin \intset{}$
1520 is labor-intensive and not easily done
1521 without a computer for even moderate $N$.
1522 Theorems \ref{thm:thm01}, \ref{thm:thm03},
1523 and \ref{thm:thm05} outline a computationally
1524 tractable way (Algorithm \ref{alg:algstartingatprime})
1525 to use a computer to
1526 form the successor in $F_{N}$ given
1527 only a single Farey term, even for large $N$.
1528 Once two successive Farey terms are known,
1529 Theorem \ref{thm:thm04} can be applied to
1530 generate additional terms at low cost.
1531 Algorithm \ref{alg:algstartingatprime}
1532 below outlines a method to
1533 economically find Farey terms on the left
1534 and right of a real number.
1535
1536 \begin{algorithm}\label{alg:algstartingatprime}\end{algorithm}
1537 \begin{alglvl0}
1538 \item Choose a prime number $\alpha\ll N$. $\alpha$ is
1539 the number of denominators that a computer
1540 can test against $Kh-Hk=1$ in a practical period of
1541 time.\footnote{Useful primes at each order of
1542 magnitude are 11; 101; 1,009; 10,007;
1543 100,003; 1,000,003; and 10,000,019.}
1544 \item Choose a rational number $h'/\alpha$ to the left of $r_{I}$
1545 ($h'=\lfloor r_{I}\alpha\rfloor$ is usually a good choice).
1546 \item Because $\alpha$ is prime,
1547 $h'/\alpha$ is not reducible unless
1548 $h'/\alpha$ is an integer.
1549 \item Denote the Farey term succeeding $h'/\alpha$ as $h/k$.
1550 Theorem \ref{thm:thm03} asserts
1551 that $\alpha +k>N$, implying that
1552 $k>N-\alpha$.
1553 \item Apply Theorems \ref{thm:thm01} and \ref{thm:thm05}.
1554 Search downward
1555 from $k=N$ to $k=N-\alpha +1$ for an $h/k$ which satisfies
1556 Theorem \ref{thm:thm01}.
1557 This will require at most $\alpha$ iterations.
1558 \item $h'/\alpha$ and $h/k$ are now known to be successive Farey
1559 terms in $F_N$ to the left of $r_I$.
1560 Theorem \ref{thm:thm04} can be employed to economically
1561 generate successive Farey terms until $r_I$ is enclosed.
1562 \end{alglvl0}
1563
1564
1565
1566 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1567 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1568 % (4)(F)FRAMEWORK OF CONTINUED FRACTIONS %
1569 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1570 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1571
1572
1573 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1574 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1575 % (4)(F)(i)DEFINITION OF A CONTINUED FRACTION %
1576 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1577 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1578 \subsection{Continued Fraction Methods Of Choosing $h$ And $k$}
1579
1580 For selection of a suitable rational number from $F_N$ when
1581 $N$ is a few hundred or less, building $F_N$
1582 starting at an integer (Algorithm \ref{alg:algstartingatint})
1583 or at a rational number with a large
1584 prime denominator (Algorithm \ref{alg:algstartingatprime})
1585 are practical techniques.\footnote{\label{footnote:exceldaveashleyfootnote}\emph{Microsoft Excel},
1586 which maintains
1587 integers with 48 bits of precision, can be used to
1588 build $F_N$ and select a suitable rational number
1589 for at least $N \approx 2^{24}$. (Multiplying
1590 two 24-bit numbers yields a 48-bit result, and so \emph{Excel}
1591 should be usable until at least order $\approx 2^{24}$.)}
1592 However, the number of elements of $F_N$ is approximately
1593 $3N^2/\pi^2$; and so for large $N$, $\realset{}$ is
1594 too dense with Farey rationals to economically search.
1595
1596 A more direct algorithm for locating
1597 the Farey neighbors of an arbitrary real
1598 $r_I$
1599 comes from the study of \emph{continued fractions}
1600 (a topic in number theory).
1601
1602 A \emph{finite simple continued fraction} is a fraction in the form
1603 of (\ref{eq:eq0057}), where $a_0 \in \intsetnonneg$
1604 and $a_{k} \in \intsetpos$ for $k > 0$. A continued fraction
1605 in the form of (\ref{eq:eq0057}) is denoted $[a_0; a_1, a_2, \ldots, a_n]$.
1606
1607 \begin{figure*}
1608 \begin{equation}
1609 \label{eq:eq0057}
1610 a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2
1611 + \cfrac{1}{\;\;\;\;\;\;\;\;\;\;\;\;\;\;\ldots + \cfrac{1}{a_n}}}}
1612 =
1613 [a_0; a_1, a_2, \ldots , a_n]
1614 \end{equation}
1615 \end{figure*}
1616
1617 Continued fractions provide an alternate apparatus for
1618 representing real numbers. The form of (\ref{eq:eq0057}) has
1619 important properties which are presented without proof.
1620
1621 \begin{propenum}
1622 \item Every rational number can be represented by a finite
1623 simple continued fraction $[a_{0};a_{1},a_{2},\ldots{} ,a_{n}]$.
1624 \item Each unique $[a_{0};a_{1},a_{2},\ldots{} ,a_{n}]$ corresponds to a
1625 uniquely valued rational number, so long as
1626 $a_{n}\neq 1$.\footnote{If $a_n=1$, the continued fraction
1627 can be reduced in order by
1628 one, and $a_{n-1}$ can be increased by one while
1629 still preserving the value of the continued fraction.
1630 The restriction that the
1631 final element $a_n \neq 1$ is necessary to guarantee that
1632 each uniquely valued
1633 rational number has a unique finite simple continued fraction
1634 representation.}
1635 \end{propenum}
1636
1637 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1638 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1639 % (4)(F)(ii) ALGORITHM 3: FORMING A CONTINUED FRACTION FROM AN IRRATIONAL NUMBER %
1640 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1641 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1642
1643
1644
1645 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1646 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1647 % (4)(F)(iii) ALGORITHM 4: FORMING A CONTINUED FRACTION FROM A RATIONAL NUMBER %
1648 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1649 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1650 Without proof, we present the following procedure for
1651 finding the continued fraction representation of an arbitrary
1652 non-negative rational number $a/b$.
1653
1654 \begin{algorithm}\label{alg:akgenalg}\end{algorithm}
1655 \begin{alglvl0}
1656 \item Start with $k=0$, dividend=$a$, divisor=$b$.
1657
1658 \item Repeat
1659
1660 \begin{alglvl1}
1661 \item Carry out the division of dividend/divisor to form an
1662 integer quotient $a_k$ and an integer remainder.
1663
1664 \item The divisor from the current iteration becomes the dividend
1665 for the next iteration, and the remainder from the current
1666 iteration becomes the divisor for the next iteration.
1667
1668 \item Increment $k$.
1669
1670 \end{alglvl1}
1671
1672 \item Until (remainder is zero).
1673 \end{alglvl0}
1674
1675 Without proof, we present the following properties of
1676 Algorithm \ref{alg:akgenalg}.
1677
1678 \begin{propenum}
1679 \item The algorithm will produce the same continued
1680 fraction representation $[a_{0};a_{1},a_{2},\ldots{} ,a_{n}]$
1681 for any $(ia)/(ib)$, $i \in \intsetpos{}$, i.e.
1682 the rational number $a/b$ need not be reduced before
1683 applying the algorithm.
1684 \item The algorithm will always terminate (i.e. the
1685 continued fraction representation
1686 $[a_{0};a_{1},a_{2},\ldots{} ,a_{n}]$ will be
1687 finite).
1688 \item The last non-zero remainder will be the greatest
1689 common divisor of $a$ and $b$.%
1690 { }
1691 \end{propenum}
1692
1693 \begin{example}
1694 Find the continued fraction representation
1695 of $a/b$=3,362,997/2,924,082.
1696 \end{example}
1697
1698 \emph{Solution:} Table \ref{tbl:cfexplrgratnum01} shows the application of
1699 Algorithm \ref{alg:akgenalg}
1700 to form the continued fraction representation of
1701 $a/b$.
1702
1703 \begin{table}
1704 \caption{Continued Fraction Representation Of $3,362,997/2,924,082$}
1705 \label{tbl:cfexplrgratnum01}
1706 \begin{center}
1707 \begin{tabular}{|c|c|c|c|c|}
1708 \hline
1709 Index (k) & Dividend & Divisor & $a_{k}$ & Remainder \\
1710 \hline
1711 \hline
1712 0 & 3,362,997 & 2,924,082 & 1 & 438,915 \\
1713 \hline
1714 1 & 2,924,082 & 438,915 & 6 & 290,592 \\
1715 \hline
1716 2 & 438,915 & 290,592 & 1 & 148,323 \\
1717 \hline
1718 3 & 290,592 & 148,323 & 1 & 142,269 \\
1719 \hline
1720 4 & 148,323 & 142,269 & 1 & 6,054 \\
1721 \hline
1722 5 & 142,269 & 6,054 & 23 & 3,027 \\
1723 \hline
1724 6 & 6,054 & 3,027 & 2 & 0 \\
1725 \hline
1726 \end{tabular}
1727 \end{center}
1728 \end{table}
1729
1730 Table \ref{tbl:cfexplrgratnum01}
1731 implies that the continued fraction representation of
1732 $a/b$ = 3,362,997/2,924,082 is $[1;6,1,1,1,23,2]$.
1733
1734 \begin{figure*}
1735 \begin{equation}
1736 \label{eq:eq0058}
1737 \frac{{{\rm 3,362,997}}}{{{\rm 2,924,082}}} =
1738 1 + \cfrac{1}{{6 + \cfrac{1}{{1 + \cfrac{1}{{1 + \cfrac{1}{{1 + \cfrac{1}{{23 + \cfrac{1}{2}}}}}}}}}}}
1739 =
1740 a_0 + \cfrac{1}{{a_1 + \cfrac{1}{{a_2 + \cfrac{1}{{a_3 + \cfrac{1}{{a_4 + \cfrac{1}{{a_5 + \cfrac{1}{a_6}}}}}}}}}}}
1741 =
1742 [1; 6, 1, 1, 1, 23, 2]
1743 \end{equation}
1744 \end{figure*}
1745
1746 Note in Table \ref{tbl:cfexplrgratnum01}
1747 that the final non-zero remainder is 3,027,
1748 the g.c.d. of 3,362,997 and 2,924,082.
1749
1750 Irrational numbers also have a continued fraction representation,
1751 but this representation is necessarily infinite (non-terminating).
1752
1753 An algorithm does exist for obtaining the continued
1754 fraction representation of an irrational number; but in practice the
1755 algorithm must be carried out symbolically (which
1756 can be difficult and not amenable to automation).
1757 For this reason, only the algorithm for obtaining the
1758 continued fraction representation of
1759 \emph{rational} numbers is presented here.
1760 Using a rational number as close as
1761 practical\footnote{Let $\alpha$ be
1762 the irrational number to be approximated,
1763 let $a/b$ be the rational number used as an approximation
1764 of $\alpha$ when applying Algorithm \ref{alg:akgenalg}, and let
1765 $H/K$ and $h/k$ be the two Farey neighbors identified
1766 through Theorem \ref{thm:thm06}.
1767 In a worst case, $\alpha < H/K < a/b < h/k$ or
1768 $H/K < a/b < h/k < \alpha$. In such cases, the misidentification
1769 of the two Farey neighbors is not detectable (because $\alpha$
1770 is not known precisely enough, otherwise a more precise
1771 $a/b$ would have been used). In \emph{all}
1772 cases, $H/K < a/b < h/k$.}
1773 to the irrational number to be approximated
1774 (such as using 3141592654/1000000000 for $\pi$, as is done in
1775 Example \ref{example:examplepi01}) is the
1776 recommended technique.
1777
1778 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1779 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1780 % (4)(F)(v) CONVERGENTS OF A CONTINUED FRACTION %
1781 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1782 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1783 The \emph{kth convergent} of a finite simple continued fraction
1784 $[a_{0};a_{1},a_{2},\ldots{},a_{n}]$,
1785 denoted $s_{k} = p_k/q_k$, is the rational number corresponding to the
1786 continued fraction $[a_{0};a_{1},a_{2},\ldots{},a_{k}]$,
1787 $k \leq n$.
1788
1789 Each convergent $s_{k}$ is a rational number with a
1790 numerator $p_{k}$ and denominator $q_{k}$.
1791 Eqns. (\ref{eq:eq0059}) through (\ref{eq:eq0064})
1792 define the canonical way to
1793 construct all $s_{k}=p_{k}/q_{k}$ from all $a_{k}$.
1794
1795 \begin{equation}
1796 \label{eq:eq0059}
1797 p_{ - 1} = 1
1798 \end{equation}
1799
1800 \begin{equation}
1801 \label{eq:eq0060}
1802 q_{ - 1} = 0
1803 \end{equation}
1804
1805 \begin{equation}
1806 \label{eq:eq0061}
1807 p_0 = a_0 = \left\lfloor {r_I } \right\rfloor
1808 \end{equation}
1809
1810 \begin{equation}
1811 \label{eq:eq0062}
1812 q_0 = 1
1813 \end{equation}
1814
1815 \begin{equation}
1816 \label{eq:eq0063}
1817 p_k = a_k p_{k - 1} + p_{k - 2}
1818 \end{equation}
1819
1820 \begin{equation}
1821 \label{eq:eq0064}
1822 q_k = a_k q_{k - 1} + q_{k - 2}
1823 \end{equation}
1824
1825 When $p_{k}$ and $q_{k}$ (the numerator and denominator of the
1826 $k$th convergent $s_{k}$) are formed as specified by (\ref{eq:eq0059})
1827 through (\ref{eq:eq0064}), convergents $s_{k}=p_{k}/q_{k}$ have the following
1828 properties, which are presented without proof.
1829
1830 \begin{propenum}
1831
1832 \item Each even-ordered convergent
1833 $s_{k} = p_k/q_k = [a_{0}; a_{1}, a_{2}, \ldots{}, a_{k}]$
1834 is less than $[a_{0}; a_{1}, a_{2}, \ldots{}, a_{n}]$, and
1835 each odd-ordered convergent $s_{k}$ is greater than
1836 $[a_{0}; a_{1}, a_{2}, \ldots{}, a_{n}]$,
1837 with the exception of the final convergent $s_{k}$, $k=n$,
1838 which is equal to $[a_{0}; a_{1}, a_{2}, \ldots{}, a_{n}]$.
1839
1840 \item Each convergent is irreducible; that is, $p_k$ and
1841 $q_k$ are coprime.
1842
1843 \item Each $q_{k}$ is greater than $q_{k-1}$; that is, the denominators
1844 of convergents are ever-increasing.
1845
1846 \end{propenum}
1847
1848 \begin{example}
1849 Find all convergents of the continued
1850 fraction representation of $a/b$=3,362,997/2,924,082; shown in
1851 Example 2 to be
1852 $[a_0;a_1,a_2,a_3,a_4,a_5,a_6]$=[1;6,1,1,1,23,2]
1853 \end{example}
1854
1855 \emph{Solution:} Table \ref{tbl:convcfexplrgratnum01}
1856 shows the results of the
1857 application of equations (\ref{eq:eq0059})
1858 through (\ref{eq:eq0064}) to form all
1859 convergents.
1860
1861 \begin{table}
1862 \caption{Convergents Of Continued Fraction
1863 Representation Of $3,362,997/2,924,082$}
1864 \label{tbl:convcfexplrgratnum01}
1865 \begin{center}
1866 \begin{tabular}{|c|c|c|c|}
1867 \hline
1868 Index (k) & $a_{k}$ & $p_{k}$ & $q_{k}$ \\
1869 \hline
1870 \hline
1871 -1 & Not defined & 1 & 0 \\
1872 \hline
1873 0 & 1 & 1 & 1 \\
1874 \hline
1875 1 & 6 & 7 & 6 \\
1876 \hline
1877 2 & 1 & 8 & 7 \\
1878 \hline
1879 3 & 1 & 15 & 13 \\
1880 \hline
1881 4 & 1 & 23 & 20 \\
1882 \hline
1883 5 & 23 & 544 & 473 \\
1884 \hline
1885 6 & 2 & 1,111 & 966 \\
1886 \hline
1887 \end{tabular}
1888 \end{center}
1889 \end{table}
1890
1891 Note that the final convergent, $s_{6}$=$p_{6}/q_{6}$=1,111/966 is
1892 the reduced form of $a/b$. Note also that all convergents
1893 $s_{k}=p_{k}/q_{k}$ are irreducible. It may also be verified that each
1894 even-ordered convergent is less than $a/b$, and that each odd-ordered
1895 convergent is greater than $a/b$, with the exception of
1896 the final convergent, which is equal to $a/b$.
1897
1898
1899 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1900 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1901 % (4)(F)(VI) THEOREM: USING CONTINUED FRACTIONS TO FIND FAREY NEIGHBORS %
1902 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1903 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1904 \begin{theorem}
1905 \label{thm:thm06}
1906 For a non-negative rational number $a/b$ not in
1907 $F_N$ which has a
1908 continued fraction representation
1909 $[a_0;a_1,a_2,\ldots{} ,a_n]$, the
1910 highest-order convergent $s_k = p_k/q_k$ with $q_k \leq N$ is one
1911 neighbor\footnote{By neighbors in $F_N$ we mean the rational numbers
1912 in $F_N$ immediately to the left and immediately to the right
1913 of $a/b$.}
1914 in $F_N$ to $a/b$, and the other neighbor in $F_N$ is given by
1915 (\ref{eq:eq0065}).\footnote{We were not able to locate
1916 Theorem \ref{thm:thm06} or a proof in print,
1917 but this theorem is known within the number theory community.
1918 It appears on the Web
1919 page of David Eppstein in the form of a
1920 `C'-language computer program,
1921 \texttt{http://www.ics.uci.edu/\~{}{}eppstein/numth/frap.c}.}
1922 \end{theorem}
1923
1924 \begin{equation}
1925 \label{eq:eq0065}
1926 \frac{{\displaystyle{\left\lfloor {\frac{{N - q_{k - 1} }}{{q_k }}} \right\rfloor}
1927 p_k + p_{k - 1} }}{{\displaystyle{\left\lfloor {\frac{{N - q_{k - 1} }}{{q_k }}}
1928 \right\rfloor} q_k + q_{k - 1} }}
1929 \end{equation}
1930
1931 \begin{proof}
1932 First, it is proved that the highest-order
1933 convergent $s_k = p_k/q_k$ with $q_k \leq N$ is one of the two
1934 neighbors to $a/b$ in $F_N$. Note that $s_k \in F_N$, since $s_k$ is rational
1935 and reduced with denominator not exceeding $N$.
1936 By theorem (\cite{KhinchinClassic}, Theorem 9, p. 9), the upper bound on the
1937 difference between $a/b$ and $s_k$ is given by (\ref{eq:eq0066}).
1938
1939 \begin{equation}
1940 \label{eq:eq0066}
1941 \left| {\frac{a}{b} - \frac{{p_k }}{{q_k }}} \right| < \frac{1}{{q_k q_{k + 1} }}
1942 \end{equation}
1943
1944 For two consecutive terms in $F_N$, $Kh-Hk=1$.
1945 For a Farey neighbor $H/K$ to $s_k$ in $F_N$, (\ref{eq:eq0067}) must hold.
1946
1947 \begin{equation}
1948 \label{eq:eq0067}
1949 \frac{1}{q_k N} \leq \left| {\frac{H}{K} - \frac{p_k}{q_k}} \right|
1950 \end{equation}
1951
1952 $q_{k+1}>N$, because $q_{k+1}>q_k$ and $p_k/q_k$ was chosen to be the
1953 highest-order convergent with $q_k\leq N$. Using this knowledge and
1954 combining (\ref{eq:eq0066}) and (\ref{eq:eq0067}) leads to
1955 (\ref{eq:eq0069}).
1956
1957 \begin{equation}
1958 \label{eq:eq0069}
1959 \left| {\frac{a}{b} - \frac{{p_k }}{{q_k }}} \right| < \frac{1}{{q_k q_{k + 1} }}
1960 <
1961 \frac{1}{q_k N} \leq \left| {\frac{H}{K} - \frac{p_k}{q_k}} \right|
1962 \end{equation}
1963
1964 This proves that $s_k$ is one neighbor to $a/b$ in $F_N$.
1965 The apparatus of continued fractions ensures that the
1966 highest order convergent $s_k$ with $q_k\leq N$ is closer to $a/b$ than
1967 to any neighboring term in $F_N$. Thus, there is
1968 no intervening term of $F_N$ between $s_k$ and $a/b$.
1969 If $k$ is even, $s_k<a/b$, and if $k$ is
1970 odd, $s_k>a/b$.
1971
1972 It must be proved that (\ref{eq:eq0065}) is the other Farey
1973 neighbor. (\ref{eq:eq0065}) is of the form (\ref{eq:eq0071}),
1974 where $i \in \intsetnonneg$.
1975
1976 \begin{equation}
1977 \label{eq:eq0071}
1978 \frac{{ip_k + p_{k - 1} }}{{iq_k + q_{k - 1} }}
1979 \end{equation}
1980
1981 If $k$ is even, $s_k < a/b$, and the two Farey terms enclosing $a/b$, in
1982 order, are given in the first clause
1983 of (\ref{eq:eq0072}). If $k$ is odd,
1984 $s_k > a/b$, and the two Farey terms enclosing $a/b$, in order, are
1985 given in the second clause of (\ref{eq:eq0072}).
1986
1987 \begin{equation}
1988 \label{eq:eq0072}
1989 \begin{array}{ll}
1990 \left\{ \displaystyle{{\frac{{p_k }}{{q_k }},\frac{{ip_k + p_{k - 1} }}{{iq_k + q_{k - 1} }}}} \right\}
1991 &
1992 (k \; even)
1993 \\ & \\
1994 \left\{ \displaystyle{{\frac{{ip_k + p_{k - 1} }}{{iq_k + q_{k - 1} }},\frac{{p_k }}{{q_k }}}} \right\}
1995 &
1996 (k \; odd)
1997 \\
1998 \end{array}
1999 \end{equation}
2000
2001 In either clause of (\ref{eq:eq0072}),
2002 applying the $Kh - Hk = 1$ test, (\ref{eq:eq0074}), gives the
2003 result of 1, since by theorem
2004 (\cite{KhinchinClassic}, Theorem 2, p. 5),
2005 $q_kp_{k-1}-p_kq_{k-1}=(-1)^k$, with the
2006 exponent of $k$ compensating
2007 for the ordering difference between
2008 the two clauses of
2009 (\ref{eq:eq0072}), as shown in (\ref{eq:eq0075}).
2010
2011 \begin{figure*}
2012 \begin{equation}
2013 \label{eq:eq0074}
2014 \begin{array}{*{20}c}
2015 {(q_k )(ip_k + p_{k - 1} ) - (p_k )(iq_k + q_{k - 1} ) = 1,} \hfill & {{\rm (k \; even)}} \hfill \\
2016 {(iq_k + q_{k - 1} )(p_k ) - (ip_k + p_{k - 1} )(q_k ) = 1,} \hfill & {{\rm (k \; odd)}} \hfill \\
2017 \end{array}
2018 \end{equation}
2019 \end{figure*}
2020
2021 \begin{equation}
2022 \label{eq:eq0075}
2023 \begin{array}{*{20}c}
2024 {q_k p_{k - 1} - p_k q_{k - 1} = ( - 1)^k = 1,} \hfill & {{\rm (k \; even)}} \hfill \\
2025 {q_{k - 1} p_k - p_{k - 1} q_k = - ( - 1)^k = 1,} \hfill & {{\rm (k \; odd)}} \hfill \\
2026 \end{array}
2027 \end{equation}
2028
2029 Thus, every potential Farey neighbor of the form (\ref{eq:eq0071})
2030 meets the $Kh - Hk = 1$ test. In order to show
2031 that (\ref{eq:eq0065}) is the
2032 companion Farey neighbor to $p_k/q_k$, it is only necessary
2033 to show that a term meeting the $Hk-Hk=1$ test with a
2034 larger denominator still not greater than $N$ cannot exist
2035 (Theorem \ref{thm:thm05}).
2036
2037 It must first be established that a
2038 rational number of the form (\ref{eq:eq0071})
2039 is irreducible. This result comes directly from (\ref{eq:eq0074}) and
2040 (\ref{eq:eq0075}), since if the numerator
2041 and denominator of (\ref{eq:eq0065}) or
2042 (\ref{eq:eq0071}) are not coprime, the difference of 1 is
2043 not possible.
2044
2045 The denominator of (\ref{eq:eq0065})
2046 can be rewritten as (\ref{eq:eq0076}).
2047
2048 \begin{equation}
2049 \label{eq:eq0076}
2050 N - \left[ {\left( {N - q_{k - 1} } \right)\bmod q_k } \right] \in \left\{ {N - q_k + 1,...,N} \right\}
2051 \end{equation}
2052
2053 Finally, it must be shown that if one irreducible
2054 rational number---namely, the rational number given by
2055 (\ref{eq:eq0065})---with a denominator
2056 $\in \{ N-q_k+1,\ldots{} ,N \}$ meets the $Kh - Hk = 1$
2057 test, there can be no other irreducible rational number
2058 in $F_N$ with a larger
2059 denominator which also meets this test.
2060
2061 Let $c/d$ be the irreducible rational number given by
2062 (\ref{eq:eq0065}), with $d$ already shown
2063 above to be $\in \{N - q_k + 1,...,N\}$.
2064 Since $c/d$ and $s_k = p_k/q_k$ meet the $Kh - Hk = 1$ test,
2065 (\ref{eq:eq0076b}) follows.
2066
2067 \begin{equation}
2068 \label{eq:eq0076b}
2069 c = \frac{1}{q_k} + \frac{p_k d}{q_k}; \; c \in \intset{}
2070 \end{equation}
2071
2072 $c$ as shown in (\ref{eq:eq0076b}) is necessarily an
2073 integer. Assume that $d \in \intset{}$ is to be perturbed by
2074 some amount $\Delta \in \intset{}$ to form a different
2075 integer $d + \Delta \in \intset{}$. In order for the $Kh - Hk = 1$ test
2076 to be met with the new choice of denominator
2077 $d + \Delta$, (\ref{eq:eq0076c}) is required.
2078
2079 \begin{equation}
2080 \label{eq:eq0076c}
2081 \frac{1}{q_k} + \frac{p_k d}{q_k} + \frac{p_k \Delta}{q_k} \in \intset{}
2082 \end{equation}
2083
2084 Comparing (\ref{eq:eq0076b}) with (\ref{eq:eq0076c}), it can be seen
2085 that since the first two terms of (\ref{eq:eq0076c}) sum to an integer,
2086 (\ref{eq:eq0076c}) implies that
2087 $p_k \Delta / q_k \in \intset{}$.
2088 $p_k$ and $q_k$
2089 are coprime, and so in order for $q_k$ to divide $p_k \Delta$ with
2090 no remainder, $\Delta$ must contain at least every prime factor of
2091 $q_k$, which implies that $\Delta \geq q_k$. Noting that the
2092 denominator of (\ref{eq:eq0065}) is necessarily
2093 $d \in \{N - q_k + 1,...,N\}$, any positive perturbation
2094 $\Delta \geq q_k$ will form a $d + \Delta > N$. Thus,
2095 no other irreducible rational number in $F_N$ besides that given
2096 by (\ref{eq:eq0065}) with a larger denominator
2097 $\leq N$ and which meets the $Kh - Hk = 1$ test can exist; therefore
2098 (\ref{eq:eq0065}) is the other enclosing Farey neighbor to
2099 $a/b$ in $F_N$.
2100 \end{proof}
2101
2102 \begin{example}
2103 \label{example:examplepi01}
2104 Find the members of $F_{65535}$ immediately
2105 before and immediately after $\pi$.
2106 \end{example}
2107
2108 \emph{Solution:} $\pi$ is transcendental and cannot be expressed
2109 as a rational number. Using 3141592654/1000000000
2110 as a rational approximation to $\pi$ and applying
2111 Algorithm \ref{alg:akgenalg}
2112 yields Table \ref{tbl:cfexpansrapppi}.
2113
2114 \begin{table}
2115 \caption{Continued Fraction Representation Of 3,141,592,654/1,000,000,000
2116 (A Rational Approximation To $\pi$)}
2117 \label{tbl:cfexpansrapppi}
2118 \begin{center}
2119 \begin{tabular}{|c|c|c|c|c|}
2120 \hline
2121 \small{Index} & \small{Dividend} & \small{Divisor} & $a_k$ & \small{Remainder} \\
2122 \small{(k)} & & & & \\
2123 \hline
2124 \hline
2125 \small{0} & \small{3,141,592,654} & \small{1,000,000,000} & \small{3} & \small{141,592,654} \\
2126 \hline
2127 \small{1} & \small{1,000,000,000} & \small{141,592,654} & \small{7} & \small{8,851,422} \\
2128 \hline
2129 \small{2} & \small{141,592,654} & \small{8,851,422} & \small{15} & \small{8,821,324} \\
2130 \hline
2131 \small{3} & \small{8,851,422} & \small{8,821,324} & \small{1} & \small{30,098} \\
2132 \hline
2133 \small{4} & \small{8,821,324} & \small{30,098} & \small{293} & \small{2,610} \\
2134 \hline
2135 \small{5} & \small{30,098} & \small{2,610} & \small{11} & \small{1,388} \\
2136 \hline
2137 \small{6} & \small{2,610} & \small{1,388} & \small{1} & \small{1,222} \\
2138 \hline
2139 \small{7} & \small{1,388} & \small{1,222} & \small{1} & \small{166} \\
2140 \hline
2141 \small{8} & \small{1,222} & \small{166} & \small{7} & \small{60} \\
2142 \hline
2143 \small{9} & \small{166} & \small{60} & \small{2} & \small{46} \\
2144 \hline
2145 \small{10} & \small{60} & \small{46} & \small{1} & \small{14} \\
2146 \hline
2147 \small{11} & \small{46} & \small{14} & \small{3} & \small{4} \\
2148 \hline
2149 \small{12} & \small{14} & \small{4} & \small{3} & \small{2} \\
2150 \hline
2151 \small{13} & \small{4} & \small{2} & \small{2} & \small{0} \\
2152 \hline
2153 \end{tabular}
2154 \end{center}
2155 \end{table}
2156
2157
2158 Table \ref{tbl:cfconvofpi} shows the formation of the convergents
2159 of the continued fraction
2160 representation of the
2161 rational approximation to $\pi$ using (\ref{eq:eq0059}) through (\ref{eq:eq0064}).
2162
2163 \begin{table}
2164 \caption{Convergents Of Continued Fraction Representation Of
2165 3,141,592,654/1,000,000,000 (A Rational Approximation
2166 To $\pi$)}
2167 \label{tbl:cfconvofpi}
2168 \begin{center}
2169 \begin{tabular}{|c|c|c|c|}
2170 \hline
2171 Index (k) & $a_{k}$ & $p_{k}$ & $q_{k}$ \\
2172 \hline
2173 \hline
2174 -1 & Not defined & 1 & 0 \\
2175 \hline
2176 0 & 3 & 3 & 1 \\
2177 \hline
2178 1 & 7 & 22 & 7 \\
2179 \hline
2180 2 & 15 & 333 & 106 \\
2181 \hline
2182 3 & 1 & 355 & 113 \\
2183 \hline
2184 4 & 293 & 104,348 & 33,215 \\
2185 \hline
2186 5 & 11 & 1,148,183 & 365,478 \\
2187 \hline
2188 6 & 1 & 1,252,531 & 398,693 \\
2189 \hline
2190 7 & 1 & 2,400,714 & 764,171 \\
2191 \hline
2192 8 & 7 & 18,057,529 & 5,747,890 \\
2193 \hline
2194 9 & 2 & 38,515,772 & 12,259,951 \\
2195 \hline
2196 10 & 1 & 56,573,301 & 18,007,841 \\
2197 \hline
2198 11 & 3 & 208,235,675 & 66,283,474 \\
2199 \hline
2200 12 & 3 & 681,280,326 & 216,858,263 \\
2201 \hline
2202 13 & 2 & 1,570,796,327 & 500,000,000 \\
2203 \hline
2204 \end{tabular}
2205 \end{center}
2206 \end{table}
2207
2208 By Theorem \ref{thm:thm06}, one Farey neighbor is the convergent
2209 with the largest denominator not greater than 65,535.
2210 From Table \ref{tbl:cfconvofpi}, this convergent is $s_4$ = $p_4/q_4$ =
2211 104,348/33,215 (and note that since this is an
2212 even-ordered convergent, it will be less than $a/b$). Also by
2213 Theorem \ref{thm:thm06}, applying equation
2214 (\ref{eq:eq0065}), the other Farey
2215 neighbor is 104,703/33,328.
2216
2217
2218 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2219 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2220 % (4)(F)CASE OF CONSTRAINED h %
2221 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2222 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2223 \subsection{Case Of Constrained $h$}
2224
2225 In a practical design problem, a rational approximation
2226 will typically be implemented by multiplying the input
2227 argument $x$ by $h$, adding an offset $z$, then dividing
2228 by $k$. Efficiency will often depend on being able to
2229 implement multiplication, addition, or
2230 division using single machine instructions, which are
2231 constrained in the size of the operands they can accomodate.
2232
2233 The results from number theory presented earlier are based
2234 only on the constraint $k \leq k_{MAX}$, i.e. only the constraint
2235 on the denominator is considered. However, in practical problems,
2236 the numerator is also typically constrained, usually by the
2237 size of operands that an integer multiplication instruction
2238 can accomodate.
2239
2240 $r_I$, $h_{MAX}$, and $k_{MAX}$
2241 can be specified so that the restriction on the numerator
2242 is the dominant constraint, which
2243 does not allow the Farey series of order
2244 $N=k_{MAX}$ to be economically
2245 used to find the best rational approximation to $r_{I}$,
2246 because $F_{k_{MAX}}$ near $r_I$ will contain
2247 predominantly terms with
2248 numerators violating $h \leq h_{MAX}$.
2249
2250 To provide for a more economical search for the best
2251 rational approximations when the numerator is constrained,
2252 Theorem \ref{thm:thmconstrainednumerator} is presented.
2253
2254 \begin{theorem}
2255 \label{thm:thmconstrainednumerator}
2256 Given a positive
2257 real number $r_I$ and constraints
2258 on a rational approximation $h/k$ to $r_I$,
2259 $0 \leq h \leq h_{MAX}$ and $0 < k \leq k_{MAX}$, the closest
2260 rational numbers to $r_I$ on the left and right
2261 subject to the constraints lie
2262 in $F_{N'}$, with $N'$ chosen as in (\ref{eq:eqconsth:aa}).
2263 \end{theorem}
2264
2265 \begin{equation}
2266 \label{eq:eqconsth:aa}
2267 N'=\left\lfloor
2268 {
2269 \frac{h_{MAX}}{r_I } + 1
2270 }
2271 \right\rfloor
2272 \end{equation}
2273
2274 \begin{proof}
2275 Note that by (\ref{eq:eqconsth:aa}),
2276 $N' > h_{MAX}/r_I$, for all choices
2277 of $h_{MAX}$ and $r_I$.
2278
2279 If $r_I \leq h_{MAX}/k_{MAX}$, $N' > k_{MAX}$;
2280 therefore $F_{N'} \supset F_{k_{MAX}}$,
2281 and the theorem is true.
2282
2283 If $r_I > h_{MAX}/k_{MAX}$, then $h_{MAX}/N' < r_I$.
2284 Note that $h_{MAX}/N'$ or its reduced form if it
2285 is reducible is necessarily in $F_{N'}$. Any
2286 rational number $a/b > h_{MAX}/N'$ with $b>N'$
2287 must also have $a > h_{MAX}$, which violates
2288 the constraints. Therefore, any $a/b$ such
2289 that $h_{MAX}/N' < a/b < r_I$ must lie
2290 in $F_{N'}$, and the closest rational number
2291 to $r_I$ on the right subject to the constraints
2292 must also lie in $F_{N'}$.
2293 \end{proof}
2294
2295 \begin{example}
2296 \label{ex:expiconstrainednumandden}
2297 Find the two best rational approximations to $\pi$ subject to
2298 $h_{MAX} = 255$ and $k_{MAX} = 255$.
2299 \end{example}
2300
2301 \emph{Solution:} In this problem, both the numerator and
2302 denominator are constrained. The constrained numerator is
2303 not treated directly by the results from number theory.
2304 Applying (\ref{eq:eqconsth:aa}) gives $N'$=82, thus it is only necessary
2305 to examine $F_{82}$ for best approximations to $\pi$ which
2306 meet both constraints. Building $F_{82}$ yields 245/78 and
2307 22/7 as the two best rational approximations to $\pi$
2308 under the constraints.
2309
2310
2311 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2312 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2313 % (4)(B)HOW CLOSE WE CAN USUALLY GET TO R_I WHEN CHOOSING R_A %
2314 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2315 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2316 \section{Probabilistic Results On $ | R_I - R_A | $}
2317 \label{sec:probresults}
2318
2319 In this section we consider different asymptotics for
2320 the precision of the approximation of an arbitrary $r_I$ by a fraction
2321 $r_A= h/k$ with $k \leq k_{ \rm MAX }$. For simplicity of notation
2322 we
2323 denote $\alpha= r_I$ and $N=k_{ \rm MAX }$ and assume, without
2324 loss of generality, that
2325 $ \alpha \in [0,1]$.
2326
2327 We are thus interested in the asymptotic behaviour, when $N
2328 \rightarrow \infty$,
2329 of the quantity
2330 $$
2331 %\begin{equation}
2332 \label{eq:dist}
2333 \rho_N(\alpha) = \min_{h/k \in F_N} \left|\alpha - h/k\right|\, ,
2334 $$
2335 %\end{equation}
2336 which is the distance between $\alpha$ and $F_N$, the Farey
2337 series of order $N$.
2338
2339 The worst--case scenario is not very interesting: from the
2340 construction of the Farey series
2341 we observe that for a fixed $N$ the longest intervals between the
2342 neighbours of $F_N$
2343 are $[0,1/N]$ and $[1-1/N,1]$ and therefore for all $N$
2344 \begin{equation}
2345 \label{eq:max_error}
2346 \max_{\alpha \in [0,1]} \rho_N(\alpha) = \frac{1}{2N}\, .
2347 \end{equation}
2348 (This supremum is achieved at the points $1/(2N)$ and $1-1/(2N)$.)
2349
2350 Such behaviour of $\rho_N(\alpha)$ is however not typical: as we
2351 shall see below,
2352 typical values of the approiximation error $\rho_N(\alpha)$ are
2353 much smaller.
2354
2355 Let us first consider the behaviour of $\rho_N(\alpha)$ for almost all
2356 $\alpha \in [0,1]$.\footnote{ A statement is true
2357 for almost all $\alpha \in [0,1]$ if the measure of the set where this
2358 statement is wrong has measure zero.}
2359 We then have, see \cite{KargaevZ} and also \cite{Harman},
2360 that for almost all $\alpha \in [0,1]$ and any $\varepsilon >0$,
2361 (\ref{eq:liminf}) and (\ref{eq:limsup}) hold.
2362
2363 \begin{figure*}
2364 \begin{equation}
2365 \label{eq:liminf}
2366 \lim_{N\rightarrow\infty}\rho_N(\alpha) N^2 \log^{1+\varepsilon} N =
2367 + \infty, \quad
2368 \liminf_{N\rightarrow\infty} \rho_N(\alpha) N^2 \log N = 0
2369 \end{equation}
2370 \end{figure*}
2371
2372 \begin{figure*}
2373 \begin{equation}
2374 \label{eq:limsup}
2375 \limsup_{N\rightarrow\infty} \frac{ \rho_N(\alpha) N^2 }{ \log N } = +
2376 \infty, \quad
2377 \lim_{N\rightarrow\infty} \frac{ \rho_N(\alpha) N^2 }{
2378 \log^{1+\varepsilon} N } = 0
2379 \end{equation}
2380 \end{figure*}
2381
2382 Even more is true: in (\ref{eq:liminf}) and (\ref{eq:limsup})
2383 one can replace $\log N$ by $\log N \log \log N $, $\log N \log \log
2384 N \log \log \log N$ and so on.
2385 Analogously, $\log^{1+\varepsilon} N$ could be replaced by
2386 $\log N (\log \log N)^{1+\varepsilon} $, $\log N \log \log N (\log \log
2387 \log N)^{1+\varepsilon}$ and so on.
2388
2389 These statements are analogues of Khinchin's metric theorem,
2390 the classic result
2391 in the metric number theory, see e.g. \cite{Harman}.
2392
2393 The asymptotic distribution of the suitably normalised
2394 $\rho_N(\alpha)$
2395 was derived in \cite{KargaevZ1}. A main result of this
2396 paper is that
2397 the sequence of functions
2398 $N^2\rho_N(\alpha)$ converges in distribution, when $N\rightarrow
2399 \infty$,
2400 to the probability measure on $[0, \infty)$ with the density given
2401 by (\ref{eq:dens-ab}).
2402
2403 \begin{figure*}
2404 \begin{equation}
2405 \label{eq:dens-ab}
2406 {p}(\tau) =
2407 \left\{\begin{array}{ll}
2408 6/\pi^2 & \mbox{ if $0 \leq \tau \leq \frac{1}{2}$ }\\
2409 & \\
2410 \frac{6}{\pi^2 \tau} \left(1 + \log \tau - \tau
2411 \right) & \mbox{ if $\frac{1}{2}\leq \tau\leq 2 $ } \\
2412 & \\
2413 \frac{ 3}{\pi^2 \tau}\left(2\log(2 \tau)\!
2414 -\!4\log(\sqrt{\tau}\!+\!\sqrt{\tau\!-\!2})\!
2415 -\! (\sqrt{\tau}\!-\!\sqrt{\tau\!-\!2})^2 \right)
2416 & \mbox{ if $2 \leq \tau < \infty $ }
2417 \end{array}
2418 \right.
2419 \end{equation}
2420 \end{figure*}
2421
2422 This means that
2423 for all $a,A$
2424 such that
2425 $0<a<A<\infty$,
2426 (\ref{eq:davedrzinsert01}) applies,
2427 where
2428 {\rm `meas'} denotes for the standard Lebesgue measure on $[0,1]$.
2429
2430 \begin{figure*}
2431 \begin{equation}
2432 \label{eq:davedrzinsert01}
2433 {\rm meas} \{ \alpha \in [0,1]: \;a < N^2 \rho_N(\alpha) \leq A \}
2434 \rightarrow
2435 \int_a^A {p}(\tau) d \tau\,
2436 \;\;{\rm as}\; N \rightarrow \infty
2437 \end{equation}
2438 \end{figure*}
2439
2440 Another result in \cite{KargaevZ1} concerns the asymptotic
2441 behavior
2442 of the moments of the approximation error $\rho_N(\alpha) $. It
2443 says that
2444 for any $\delta\neq 0$ and $N \rightarrow \infty$,
2445 (\ref{eq:moments}) applies,
2446 where $\zeta(\cdot)$ and B$(\cdot,\cdot)$
2447 are the Riemann zeta--function and the Beta--function,
2448 correspondingly.
2449
2450
2451 \begin{figure*}
2452 \begin{equation}
2453 \label{eq:moments}
2454 \hspace{-8mm}
2455 {
2456 %\textstile
2457 \small
2458 \frac{\delta+1}{2}
2459 }
2460 \int_0^1 \rho_N^{\delta} (\alpha) d \alpha =
2461 \left\{\begin{array}{ll}
2462 \infty & \mbox{if $ \delta \leq -1 $}\\
2463 & \\
2464 % \frac{6}{\delta^2 (\delta+1)\pi^2 } \left(2^{-\delta} +
2465 \frac{3}{\delta^2 \pi^2 } \left(2^{-\delta} +
2466 \delta 2^{\delta+2} {\rm B}(\!-\delta,\frac{1}{2}) \right)
2467 N^{-2\delta}\left(1\! +\! o(1)\right)
2468 & \mbox{if $-1\!<\!\delta\!<\!1, \delta\! \neq\! 0$ }\\
2469 & \\
2470 \frac{3}{\pi^2} N^{-2} \log N +
2471 O\left( N^{-2} \right)
2472 & \mbox{if $\delta =1 $ }\\
2473 & \\
2474 %\frac{2^{1-\delta}}{1+\delta}
2475 2^{-\delta}
2476 \frac{\zeta(\delta)}{ \zeta(\delta+1)}
2477 N^{-\delta-1}+
2478 O\left( N^{-2\delta} \right)
2479 & \mbox{if $\delta >1$ }
2480 \end{array}
2481 \right.
2482 \end{equation}
2483 \end{figure*}
2484
2485 In particular, the average of the approximation error $\rho_N
2486 (\alpha)$ asymptotically equals
2487 \begin{equation}
2488 \label{eq:average_as}
2489 \int_{0}^1 \rho_N(\alpha) d\alpha = \frac{3}{\pi^2} \frac{\log N}{N^2} +
2490 O\left(\frac{1}{N^2}\right),
2491 \;\;\;\; N\rightarrow \infty \,.
2492 \end{equation}
2493
2494 Comparison of (\ref{eq:average_as})
2495 with (\ref{eq:limsup}) shows that the
2496 asymptotic behavior of the average approximation error $\int
2497 \rho_N(\alpha) d\alpha$
2498 resembles the behavior of the superior limit of $\rho_N(\alpha)$.
2499 Even this limit
2500 decreases much faster than the maximum error $\max_{\alpha }
2501 \rho_N(\alpha)$, see
2502 (\ref{eq:max_error}): for typical $\alpha$ the rate of decrease of
2503 $\rho_N(\alpha)$, when $ N\rightarrow \infty ,$
2504 is, roughly speaking, $N^{-2}$ rather than $N^{-1}$, the error for the
2505 worst combination of $\alpha$ and $N$.
2506
2507 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2508 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2509 % (5) TABULATED VALUES AND THE H=2^Q CASE %
2510 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2511 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2512 \section{Tabulated Scaling Factors}
2513 \label{sec:tabscalingfactors}
2514
2515 Choosing $r_{A}=h/k$ using Farey series techniques as
2516 outlined in Section \ref{sec:methodshkchoose}
2517 is a suitable solution
2518 when $r_I$ is invariant and known at the time
2519 the scaling function is designed.
2520 The error terms developed allow
2521 prediction of the maximum approximation error over a
2522 domain $[0,x_{MAX}]$ when a specific $r_{A}\approx r_I$ is chosen.
2523
2524 A different problem which occurs in practice is
2525 the need to tabulate scaling factors in ROM or EEPROM.
2526 These scaling factors (which represent $r_A$) may depend
2527 on sensor or actuator calibrations and are not known
2528 precisely in advance at the time
2529 the software is designed, and so the technique of choosing
2530 and evaluating a
2531 rational number $r_A$ at design time
2532 as presented earlier cannot be
2533 applied.
2534
2535
2536
2537 \subsection{Method Of Tabulating Scaling Factors}
2538
2539 The previous sections have concentrated on scaling factors
2540 expressed as an arbitrary rational number $h/k$.
2541 However, it is usually not practical to tabulate scaling factors
2542 as rational numbers with an arbitrary denominator $k$ for the following
2543 reasons.
2544
2545 \begin{generalenum}
2546 \item Not all processors have division instructions,
2547 and division in software (as
2548 would be required with an arbitrary
2549 tabulated denominator $k$) is expensive.
2550 \item Even for processors with division
2551 instructions, if the required maximum
2552 arbitrary denominator $k$ exceeds
2553 the size which can be accomodated
2554 by the division instructions, there is no general way to perform
2555 a division of large operands
2556 using small division instructions (a solution
2557 involving arbitrary division is not
2558 scaleable).
2559 \item The rational elements of $F_N$ are irregularly spaced
2560 in $\realset$. The worst case occurs near integers,
2561 where the elements are $1/N$ apart. Allowing arbitrary tabulated
2562 rational
2563 numbers $r_A = h/k$ means that in some regions of $\realset{}$,
2564 $r_A$ can be placed very close to $r_I$, whereas in other
2565 regions, the maximum error may degrade to $|r_A - r_I| \leq 1/2N$.
2566 This irregular error is usually not useful in engineering endeavors,
2567 as the worst-case error must typically be assumed. The division by
2568 an arbitrary tabulated $k$ carries computational cost but
2569 a limited engineering
2570 benefit.
2571 \end{generalenum}
2572
2573 The method of tabulating scaling factors presented in this paper is to
2574 create scaling factors of the form $h/2^q$, so that the denominator is
2575 an integral power of two. This approach has the following advantages.
2576
2577 \begin{generalenum}
2578 \item The required multiplication by $h$ is scaleable, allowing large $h$ when
2579 necessary.
2580 \item The division by $2^q$ is economically performed using right shift
2581 instructions, which every processor has, and which are
2582 scaleable.
2583 \end{generalenum}
2584
2585
2586 \subsection{Design Approaches For $h/2^q$ Tabulated Linear Scalings}
2587
2588 Fig. \ref{figthreeelementsofchoice} shows the three elements of design
2589 choice in engineering an $h/2^q$ tabulated linear scaling.
2590 If any two of these elements are fixed, the third can be derived.
2591 The \emph{Maximum Approximation Error}
2592 (A)
2593 is the maximum approximation error that
2594 can be tolerated for any element of the domain and
2595 any tabulated $r_A$. The
2596 \emph{Domain And Range Of Approximation}
2597 (B)
2598 are the domain over which
2599 the approximation will be used, and the range which must be reachable
2600 by the appropriate choice of tabulated scaling factor $h$.
2601 The \emph{Data Size Of Tabulated $h$ And Value Of $q$, $2^q$}
2602 (C)
2603 are the number of bits which must be reserved for each
2604 tabulated $h$, and the number of bits by which the multiplication
2605 result $hx$ must be right-shifted (this value is typically hard-coded
2606 into the scaling strategy).
2607
2608 \begin{figure}
2609 \caption{Three Elements Of Design Choice In Tabulated Linear $h/2^q$ Scaling Design}
2610 \label{figthreeelementsofchoice}
2611 \begin{picture}(240,167)
2612
2613 \put(76,120){\line(1,0){100}}
2614 \put(141,35){\line(1,1){62}}
2615 \put(121,35){\line(-1,1){62}}
2616
2617 \put(35,133){\makebox(0,0){(A) Maximum}}
2618 \put(35,121){\makebox(0,0){Approximation}}
2619 \put(35,109){\makebox(0,0){Error}}
2620
2621 \put(217,133){\makebox(0,0){(B) Domain}}
2622 \put(217,121){\makebox(0,0){And Range Of}}
2623 \put(217,109){\makebox(0,0){Approximation}}
2624
2625 \put(126,24){\makebox(0,0){(C) Data Size Of Tabulated $h$}}
2626 \put(126,12){\makebox(0,0){And Value Of $q$, $2^q$}}
2627
2628 \end{picture}
2629 \end{figure}
2630
2631 The most typical case for beginning a design is that
2632 (A) (Fig. \ref{figthreeelementsofchoice})
2633 and
2634 (B) are known, so that
2635 (C)
2636 can be derived. A less typical case for beginning
2637 a design is that (B)
2638 and (C)
2639 are tentatively known, so that (A) can
2640 be derived (and if this error is unacceptable, the tentative design
2641 must be reevaluated). Although it is possible to make the
2642 necessary derivations, it never occurs in practice that
2643 a design begins with (A) and
2644 (C),
2645 with the intent of deriving
2646 (B). For this
2647 reason, only the first two cases are discussed in this paper.
2648
2649
2650 \subsection{Design By Placement Of $r_A$}
2651
2652 A useful paradigm of design is to consider the problem of engineering
2653 a tabulated $h/2^q$ scaling in terms of what abilities we preserve
2654 for placing $r_A$ with respect to $r_I$.
2655
2656 \begin{figure}
2657 \caption{Specification Of Domain And Possible Values Of $r_I$ As Triangular
2658 Region}
2659 \label{fig:specdomainrangetriangular}
2660
2661 \begin{picture}(240,130)
2662
2663 \put(20,20){\line(1,0){142}}
2664 \put(20,20){\line(0,1){97}}
2665 \put(20,20){\line(3,2){142}}
2666
2667 \put(162,20){\dashbox{.5}(0,97)}
2668 \put(8,75){\makebox(0,0){$\scriptstyle L(x)$}}
2669
2670 \put(93,12){\makebox(0,0){$\scriptstyle x$}}
2671 \put(163,12){\makebox(0,0){$\scriptstyle x_{MAX}$}}
2672 \put(210,115){\makebox(0,0){$\scriptstyle (x_{MAX}, \lfloor r_{IMAX} x_{MAX}\rfloor)$}}
2673
2674 \put(110, 55){\makebox(0,0){\small{Triangular}}}
2675 \put(110, 45){\makebox(0,0){\small{Region Of}}}
2676 \put(110, 35){\makebox(0,0){\small{Tabulated Approximation}}}
2677
2678 \end{picture}
2679 \end{figure}
2680
2681 Assume that at design time,
2682 we know that the linear scaling will be
2683 used over the domain $[0,x_{MAX}]$, $x_{MAX} \in \intsetpos{}$,
2684 and that $0 \leq r_I \leq r_{IMAX}$ for all of the $r_I$ we
2685 wish to tabulate. This establishes a triangular region in
2686 which the approximation will be used
2687 (Fig. \ref{fig:specdomainrangetriangular}).
2688
2689 The forms of $L(x)$ and $M(x)$
2690 (Eqns. \ref{eq:eq0009}, \ref{eq:eq0009b}) reveal that
2691 a specific choice of $q$ allows the selection of $r_A$
2692 in steps of $1/2^q$. With $q$ selected,
2693 there are four obvious choices for placement of $r_A$
2694 (\ref{dbpora01aa00}, \ref{dbpora01aa01},
2695 \ref{dbpora01aa02}, \ref{dbpora01aa03}), with almost no
2696 practical distinction between (\ref{dbpora01aa01})
2697 and (\ref{dbpora01aa02}). For brevity, only
2698 (\ref{dbpora01aa00}) will be developed---i.e. we
2699 will consider only placing $r_A$ at or to the left
2700 of $r_I$. Also for brevity, only
2701 $F(x)$ as a model function will be
2702 considered. All other cases can be developed
2703 using similar methods.
2704
2705 \begin{equation}
2706 \label{dbpora01aa00}
2707 r_I - \frac{1}{2^q} < r_A \leq r_I
2708 \end{equation}
2709
2710 \begin{equation}
2711 \label{dbpora01aa01}
2712 r_I - \frac{1}{2^{q+1}} \leq r_A < r_I + \frac{1}{2^{q+1}}
2713 \end{equation}
2714
2715 \begin{equation}
2716 \label{dbpora01aa02}
2717 r_I - \frac{1}{2^{q+1}} < r_A \leq r_I + \frac{1}{2^{q+1}}
2718 \end{equation}
2719
2720 \begin{equation}
2721 \label{dbpora01aa03}
2722 r_I \leq r_A < r_I + \frac{1}{2^q}
2723 \end{equation}
2724
2725 Placing $r_A$ consistently at or to the left
2726 of $r_I$ (\ref{dbpora01aa00}) will be accomplished
2727 if $h$ is chosen by (\ref{eq:dbpora03}).
2728
2729 \begin{equation}
2730 \label{eq:dbpora03}
2731 h = \left\lfloor {r_I 2^q} \right\rfloor
2732 \end{equation}
2733
2734 When $h$ is selected using (\ref{eq:dbpora03}),
2735 $r_A \leq r_I$ and (\ref{eq:dbpora05}) applies.
2736
2737 \begin{equation}
2738 \label{eq:dbpora05}
2739 r_A - r_I \in \left( { - \frac{1}{2^q} , 0 } \right]
2740 \end{equation}
2741
2742 To obtain a relationship
2743 (B,C)$\to$(A) (Fig. \ref{figthreeelementsofchoice}),
2744 (\ref{eq:dbpora05}) may be
2745 substituted into (\ref{eq:eq0035b})
2746 to yield (\ref{eq:dbpora03baa}).
2747
2748 \begin{figure*}
2749 \begin{equation}
2750 \label{eq:dbpora03baa}
2751 \left. {M(x) - F(x)} \right|_{x \in [0,x_{MAX}], r_A - r_I \in \left( {- \frac{1}{2^q}, 0} \right] }
2752 \in
2753 \left( {\frac{- x_{MAX} + z + 1}{2^q} - r_{IMAX} - 1, \frac{z}{2^q}} \right]
2754 \end{equation}
2755 \end{figure*}
2756
2757 To obtain a relationship (A,B)$\to$(C), define
2758 $\varepsilon_{SPAN}$ as the
2759 maximum span of error with a fixed
2760 $z$ and fixed $r_I$ as $x$ is allowed to vary
2761 throughout $[0,x_{MAX}]$ (Eq. \ref{eq:eq0035b}). It can be shown
2762 by solving (\ref{eq:eq0035b}) that
2763 $q$ must be chosen so as to meet (\ref{eq:dbpora03ba}) if
2764 the error span is not to exceed
2765 $\varepsilon_{SPAN}$. (\ref{eq:dbpora03ca}) supplies the
2766 smallest choice of $q$ which
2767 satisfies (\ref{eq:dbpora03ba}).
2768
2769 \begin{equation}
2770 \label{eq:dbpora03ba}
2771 q \geq \log{}_2 \left( {\frac{x_{MAX} - 1}{\varepsilon{}_{SPAN} - r_{IMAX} - 1}} \right)
2772 \end{equation}
2773
2774 \begin{figure*}
2775 \begin{equation}
2776 \label{eq:dbpora03ca}
2777 q
2778 =
2779 \left\lceil
2780 {
2781 \log{}_2 \left( {\frac{x_{MAX} - 1}{\varepsilon{}_{SPAN} - r_{IMAX} - 1}} \right)
2782 }
2783 \right\rceil
2784 =
2785 \left\lceil
2786 {
2787 \frac
2788 {
2789 {
2790 \ln{} \left( \displaystyle{{\frac{x_{MAX} - 1}{\varepsilon{}_{SPAN} - r_{IMAX} - 1}}} \right)
2791 }
2792 }
2793 {
2794 \ln 2
2795 }
2796 }
2797 \right\rceil
2798 \end{equation}
2799 \end{figure*}
2800
2801
2802 $q$ may be chosen larger than
2803 suggested by (\ref{eq:dbpora03ca}), but not smaller,
2804 while still meeting (\ref{eq:dbpora03ba}). In practice,
2805 this may be done because it is economical
2806 to choose $q$ to be a multiple of eight so that
2807 the division by $2^q$ is accomplished by ignoring
2808 the least significant byte(s) of $hx+z$, rather than by
2809 shifting. (This technique, however, will eliminate
2810 shifting at the expense of $h_{MAX}$, and
2811 usually only makes sense when $h_{MAX}$ can be
2812 increased without choosing different
2813 processor instructions
2814 to calculate $hx+z$.)
2815
2816 Once $q$ is fixed, $h_{MAX}$ can be
2817 calculated. Substituting $r_I = r_{IMAX}$
2818 into (\ref{eq:dbpora03}) yields (\ref{eq:dbpora03d}).
2819
2820 \begin{equation}
2821 \label{eq:dbpora03d}
2822 h_{MAX} = \left\lfloor {r_{IMAX} 2^q} \right\rfloor
2823 \end{equation}
2824
2825
2826
2827 \subsection{Design By Placement Of $L(x_{MAX})$}
2828
2829 A second useful paradigm of design is to
2830 consider the problem of engineering a
2831 tabulated $h/2^q$ scaling in terms of what abilities
2832 we preserve for placing the terminal point
2833 $L(x_{MAX})$ with respect to the terminal
2834 point of the model function $I(x)$, $I(x_{MAX})$,
2835 $\lxtermdifffuncsymbol{}_L \leq 0 \leq \lxtermdifffuncsymbol{}_U$,
2836 so that (\ref{eq:errplace02a}) is met
2837 (Fig \ref{fig:specdomainrangerectangular}).
2838
2839 \begin{eqnarray}
2840 \label{eq:errplace02a}
2841 &
2842 I(x_{MAX}) + \lxtermdifffuncsymbol{}_L
2843 \leq
2844 L(x_{MAX})
2845 \leq
2846 I(x_{MAX}) + \lxtermdifffuncsymbol{}_U
2847 &
2848 \\
2849 & \displaystyle{\Downarrow} & \nonumber
2850 \\
2851 \label{eq:errplace02b}
2852 &
2853 r_A - r_I \in
2854 \left(
2855 {
2856 \displaystyle
2857 {
2858 \frac{\lxtermdifffuncsymbol{}_L - 1}{x_{MAX}},
2859 \frac{\lxtermdifffuncsymbol{}_U + 1}{x_{MAX}}
2860 }
2861 } \right)
2862 &
2863 \end{eqnarray}
2864
2865 \begin{figure}
2866 \caption{Specification Of Domain And Possible Values Of $r_I$ As Rectangular
2867 Region}\begin{picture}(240,140)
2868 \label{fig:specdomainrangerectangular}
2869
2870 \put(25,20){\line(1,0){142}}
2871 \put(25,20){\line(0,1){110}}
2872 \put(25,20){\line(3,2){142}}
2873 \put(25,20){\line(5,2){142}}
2874
2875 \put(167,20){\dashbox{.5}(0,110)}
2876 \put(25,130){\dashbox{.5}(142,0)}
2877 \put(12,75){\makebox(0,0){$\scriptstyle L(x)$}}
2878 \put(12,130){\makebox(0,0){$\scriptstyle y_{MAX}$}}
2879
2880 \put(98,12){\makebox(0,0){$\scriptstyle x$}}
2881 \put(168,12){\makebox(0,0){$\scriptstyle x_{MAX}$}}
2882
2883 \put(212,115){\makebox(0,0){$\scriptstyle (x_{MAX}, I(x_{MAX})+ \lxtermdifffuncsymbol{}_U)$}}
2884 \put(204,96){\makebox(0,0){$\scriptstyle (x_{MAX}, L(x_{MAX}))$}}
2885 \put(212,77){\makebox(0,0){$\scriptstyle (x_{MAX}, I(x_{MAX})+ \lxtermdifffuncsymbol{}_L)$}}
2886
2887 \put(167,115){\circle*{4}}
2888 \put(167,96){\circle*{4}}
2889 \put(167,77){\circle*{4}}
2890
2891 \put(55, 120){\makebox(0,0){\small{Rectangular}}}
2892 \put(55, 110){\makebox(0,0){\small{Region Of}}}
2893 \put(55, 100){\makebox(0,0){\small{Required}}}
2894 \put(55, 90){\makebox(0,0){\small{Placeability}}}
2895
2896 \end{picture}
2897 \end{figure}
2898
2899 (\ref{eq:errplace02a}) places restrictions
2900 on the relationship between
2901 $r_A$ and $r_I$, and implies (\ref{eq:errplace02b}).
2902 This implication is
2903 not reversible.
2904
2905 For brevity, only $F(x)$ will be considered
2906 as a model function and only
2907 $L(x)$ will be considered as an approximation.
2908 To obtain a relationship
2909 which shows how the choice of
2910 $\lxtermdifffuncsymbol{}_L$
2911 and
2912 $\lxtermdifffuncsymbol{}_U$
2913 affect the error function
2914 $L(x) - F(x)$,
2915 (\ref{eq:errplace02b}) may be substituted
2916 into (\ref{eq:eq0035b}) to
2917 yield (\ref{eq:dbpolxmax01}).
2918
2919 \begin{figure*}
2920 \begin{equation}
2921 \label{eq:dbpolxmax01}
2922 \left. {L(x) - F(x)}
2923 \right|_{
2924 x \in [0,x_{MAX}],
2925 r_A - r_I \in
2926 \left(
2927 {
2928 \frac{\lxtermdifffuncsymbol{}_L - 1}{x_{MAX}},
2929 \frac{\lxtermdifffuncsymbol{}_U + 1}{x_{MAX}}
2930 }
2931 \right)
2932 }
2933 \in
2934 \left(
2935 {
2936 \lxtermdifffuncsymbol{}_L - 1 - r_A - \frac{2^q - 1}{2^q},
2937 \lxtermdifffuncsymbol{}_L + 1
2938 }
2939 \right)
2940 \end{equation}
2941 \end{figure*}
2942
2943 The ability to place the target
2944 point $L(x_{MAX})$ in the interval
2945 indicated in (\ref{eq:errplace02a}) requires (\ref{eq:errplace03}). Solving
2946 for $q$ leads to the constraint in
2947 (\ref{eq:errplace04}) and the smallest possible choice
2948 of $q$ in (\ref{eq:errplace05}).
2949
2950 \begin{equation}
2951 \label{eq:errplace03}
2952 \frac{1}{2^q} \leq \frac{\lxtermdifffuncsymbol{}_U - \lxtermdifffuncsymbol{}_L + 1}{x_{MAX}}
2953 \end{equation}
2954
2955 \begin{equation}
2956 \label{eq:errplace04}
2957 q \geq \log_2 \left({\frac{x_{MAX}}{\lxtermdifffuncsymbol{}_U - \lxtermdifffuncsymbol{}_L + 1}} \right)
2958 \end{equation}
2959
2960 \begin{figure*}
2961 \begin{equation}
2962 \label{eq:errplace05}
2963 q = \left\lceil {\log _2 \left( {\frac{x_{MAX}}{\lxtermdifffuncsymbol{}_U - \lxtermdifffuncsymbol{}_L + 1}} \right) } \right\rceil
2964 = \left\lceil {\frac{\ln \left( \displaystyle{{\frac{x_{MAX}}{\lxtermdifffuncsymbol{}_U - \lxtermdifffuncsymbol{}_L + 1}}} \right) }{\ln 2}} \right\rceil
2965 \end{equation}
2966 \end{figure*}
2967
2968 With $q$ chosen by (\ref{eq:errplace04})
2969 or (\ref{eq:errplace05}), $h$ can be chosen by
2970 (\ref{eq:errplace07}) so as to meet (\ref{eq:errplace02a}).
2971
2972 \begin{equation}
2973 \label{eq:errplace07}
2974 h = \left\lceil {\frac{2^{q} \left( {\left\lfloor {r_I x_{MAX}} \right\rfloor} + \lxtermdifffuncsymbol{}_L\right)}{x_{MAX}}} \right\rceil
2975 \end{equation}
2976
2977 (\ref{eq:errplace03}) through (\ref{eq:errplace05})
2978 give useful rules of thumb
2979 for sizing $q$ based on allowed variability in
2980 $L(x_{MAX})$. There are two
2981 additional useful practical applications for the paradigm
2982 of thought
2983 (\emph{observation} implies \emph{scaling factor}),
2984 and for the equations themselves.
2985
2986 The first additional practical application (for the
2987 paradigm of thought) is in the error analysis of
2988 self-calibrating systems. In Example
2989 \ref{ex:bathroomscale}, it is assumed that we
2990 precisely know
2991 the transfer characteristics of each
2992 bathroom scale transducer and can thereby
2993 choose $h$. A practical bathroom scale
2994 is more likely to be self-calibrating, so that
2995 at manufacture
2996 a known calibration weight $x_{CAL} \in \realsetnonneg{}$
2997 can be placed on the
2998 scale and the scale itself will determine the
2999 transfer characteristics of the transducer
3000 and choose $h$.\footnote{In this discussion
3001 and in (\ref{eq:errselfcal01}) and (\ref{eq:errselfcal02}),
3002 $r_I$ is taken to be the transfer characteristic of
3003 of the transducer; whereas in Example \ref{ex:bathroomscale},
3004 $1/r_I$ is the transfer characteristic of the transducer,
3005 and $r_I$ is the desired transfer characteristic of the
3006 linear scaling in the software.}
3007 For a self-calibrating scale,
3008 an important question is if a known calibration
3009 weight $x_{CAL}$ is placed on the scale and produces an
3010 A/D converter count $y_{CAL} = H(x_{CAL})$, how much can be inferred
3011 about the underlying $r_I$ of the transducer? It can be shown
3012 that the implication relationship in
3013 (\ref{eq:errselfcal01}) and (\ref{eq:errselfcal02}) applies.
3014 This self-calibration uncertainty should not be neglected
3015 in error analyses. Note in (\ref{eq:errselfcal02})
3016 that the self-calibration
3017 uncertainty in $r_I$ decreases with increasing
3018 $x_{CAL}$, which is consistent with intuition.
3019
3020 \begin{eqnarray}
3021 \label{eq:errselfcal01}
3022 &
3023 y_{CAL} = H(x_{CAL}) = \lfloor r_I x_{CAL} \rfloor
3024 &
3025 \\
3026 & \displaystyle{\Downarrow} & \nonumber
3027 \\
3028 \label{eq:errselfcal02}
3029 &
3030 r_I \in
3031 \left[
3032 {
3033 \displaystyle
3034 {
3035 \frac{y_{CAL}}{x_{CAL}}, \frac{y_{CAL}}{x_{CAL}} + \frac{1}{x_{CAL}}
3036 }
3037 }
3038 \right)
3039 &
3040 \end{eqnarray}
3041
3042 The second additional practical application
3043 (for the equations) is the special case of
3044 $\lxtermdifffuncsymbol{}_L = \lxtermdifffuncsymbol{}_U = 0$,
3045 which is useful in devising
3046 a tabulated linear scaling for
3047 piecewise linear functions when
3048 the linear segments must join neatly, or when the required
3049 accuracy of a linear scaling is not known
3050 precisely in advance and a reasonable
3051 default tabulated scaling strategy must be chosen.
3052 Theorem \ref{thm:fullplaceability}
3053 supplies a choice of $q$ and a result
3054 about $h_{MAX}$ which is useful in such cases.
3055
3056 \begin{theorem}
3057 \label{thm:fullplaceability}
3058 Given a rational linear scaling of
3059 the form (\ref{eq:eq0009}) with an $m$-bit
3060 domain and an $n$-bit range,
3061 choosing $q=m$ and
3062 $h_{MAX} = 2^{m+n} - 1$
3063 (i.e. choosing a data width of
3064 $m+n$ bits for $h$) will allow
3065 an $h$ to be chosen
3066 so that $L(x') = y'$ for any
3067 $x' \in [1, x_{MAX} = 2^m - 1]_\intset{}, \; y' \in [0, y_{MAX} = 2^n - 1]_\intset{}$.
3068 \end{theorem}
3069
3070 \begin{proof}
3071 At $x' = x_{MAX}$, in order to be able
3072 to choose $y'$, it is required that
3073 $x_{MAX}/2^q \leq 1$, and $q = m$ is
3074 the smallest integral choice of $q$ that will
3075 satisfy this constraint.
3076 With $q=m$,
3077 $L(1) = y_{MAX}$ requires
3078 $h_{MAX}/2^m \geq y_{MAX}$, and
3079 $h_{MAX} = 2^{m+n}-1$ (a bit-width
3080 of at least $m+n$ for $h$) is required.
3081 \end{proof}
3082
3083
3084 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3085 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3086 % (6) IMPLEMENTATION CONSIDERATIONS AND TECHNIQUES %
3087 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3088 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3089 \section{Implementation Techniques}
3090 \label{sec:imptechniques}
3091
3092 Practical microprocessors fall into the
3093 following categories, ranked from
3094 least capable to most capable.
3095
3096 \begin{generalenum}
3097
3098 \item Processors with shift and addition instructions.
3099
3100 \item Processors with shift, addition, and multiplication instructions.\footnote{To
3101 date, the authors have not encountered a processor with division instructions but no
3102 multiplication instructions.}
3103
3104 \item Processors with shift, addition, multiplication, and division instructions.
3105
3106 \end{generalenum}
3107
3108 Shift instructions,
3109 addition instructions,
3110 and multiplication instructions
3111 are always \emph{scaleable},
3112 meaning that operands of arbitrary
3113 size can be shifted, added, or multiplied by the
3114 repeated use of instructions which
3115 inherently accept smaller operands.
3116 Division instructions, however, are not scaleable. No general
3117 method exists to use processor division instructions to divide
3118 operands of arbitrary size.
3119
3120 For multiplication, certain values of $h$ can lead
3121 to especially economical implementations. Multiplication by
3122 an $h$ which
3123 is an integral power of two can be performed using
3124 shift instructions. Multiplication by an $h$
3125 whose bit pattern is very sparsely populated with
3126 1's can also lead to an economical implementation.
3127 For example, multiplication by $h=33_{10}=100001_2$
3128 can be performed using five left shifts and an addition.
3129 For division, a value of $k$ which is an integral power
3130 will lead to a very economical implementation.
3131
3132 The following steps are recommended to economize
3133 an $(hx+z)/k$
3134 linear scaling for implementation.
3135
3136 \begin{generalenum}
3137
3138 \item If the processor does not have a division instruction to
3139 directly support the integer division by $k$,
3140 use an $(hx+z)/2^q$ scaling rather than an $(hx+z)/k$ scaling (due
3141 to the high cost of division in software).
3142
3143 \item If the bit pattern of $h$ is sparsely populated with 1's, evaluate
3144 implementation of the multiplication via
3145 repeated left-shifting and addition.
3146
3147 \end{generalenum}
3148
3149
3150 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3151 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3152 % (7) DESIGN EXAMPLES %
3153 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3154 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3155 \section{Design Examples}
3156 \label{sec:designexamples}
3157
3158
3159 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3160 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3161 % (7)(B) CONVERSION FROM MPH TO KPH %
3162 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3163 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3164 \begin{example}
3165 \label{ex:convmphkphatend}
3166 (CONVERSION FROM MPH TO KPH) Devise an economical and
3167 accurate linear scaling algorithm
3168 from integral MPH to integral KPH which operates over a domain
3169 of $[0, 255]_{\intset{}}$ MPH (one unsigned byte) and delivers an
3170 unsigned byte in $[0,255]_{\intset{}}$ KPH, and
3171 bound the error introduced by the scaling,
3172 assuming that the input speed is quantized (already contains error).
3173 The error between actual speed (before input
3174 quantization) and the output of the algorithm
3175 must never be negative---i.e. the output of the algorithm must
3176 never \emph{under}state the speed. In the event that
3177 the result is too large for one byte, the result
3178 should be 255. Implement the algorithm on a TMS370
3179 CPU core, which is characterized by an 8$\times$8=16
3180 unsigned multiplication instruction and a 16$\times$8=8
3181 division instruction.
3182 \end{example}
3183
3184 \emph{Solution:}
3185 One mile is 1.6093 kilometers, thus $r_I = 1.6093$.
3186 Efficient implementation using the instruction
3187 set of the TMS370 is best done by a single multiplication
3188 instruction followed by a single division instruction, implying
3189 that $h_{MAX} = k_{MAX} = 255$. Applying
3190 Theorem \ref{thm:thmconstrainednumerator}
3191 yields $N'=159$, so it is only necessary to
3192 examine $F_{159}$ for the
3193 two enclosing rational numbers
3194 which meet the constraints on numerator and denominator.\footnote{Theorem \ref{thm:thmconstrainednumerator}
3195 must be applied with caution, as it only guarantees that the
3196 \emph{two enclosing} rational numbers are in $F_{159}$. Table \ref{tbl:fareymphtokph01}
3197 is included to show the construction of $F_{159}$---it should be noted that
3198 without further analysis there is no guarantee that there are not
3199 rational numbers which meet the constraints to the left of 243/151
3200 with $k>159$.}
3201 Building $F_{159}$ near 1.6093
3202 yields Table \ref{tbl:fareymphtokph01}.\footnote{Table
3203 \ref{tbl:fareymphtokph01} can be built using spreadsheet
3204 software to construct $F_{159}$ starting with
3205 the rational numbers
3206 1/1 and 160/159 and using
3207 (\ref{eq:eq0051}) and
3208 (\ref{eq:eq0052}) to build increasing Farey
3209 terms until $r_I$ is enclosed.}
3210
3211 \begin{table}
3212 \caption{$F_{159}$ Near 1.6093 (Example \ref{ex:convmphkphatend})}
3213 \label{tbl:fareymphtokph01}
3214 \begin{center}
3215 \begin{tabular}{|c|c|c|c|}
3216 \hline
3217 $h$ & $k$ & $h/k$ & Error \\
3218 \hline
3219 \hline
3220 214 & 133 & 1.60902256 & -0.00027744 \\
3221 \hline
3222 177 & 110 & 1.60909091 & -0.00020909 \\
3223 \hline
3224 140 & 87 & 1.60919540 & -0.00010460 \\
3225 \hline
3226 243 & 151 & 1.60927152 & -0.00002848 \\
3227 \hline
3228 103 & 64 & 1.60937500 & +0.00007500 \\
3229 \hline
3230 169 & 105 & 1.60952381 & +0.00022381 \\
3231 \hline
3232 235 & 146 & 1.60958904 & +0.00028904 \\
3233 \hline
3234 227 & 141 & 1.60992908 & +0.00062903 \\
3235 \hline
3236 \end{tabular}
3237 \end{center}
3238 \end{table}
3239
3240 From Table \ref{tbl:fareymphtokph01},
3241 the two rational numbers which enclose
3242 1.6093 are 243/151 and 103/64.
3243 Choosing $r_A = 243/151$\footnote{From
3244 Table \ref{tbl:fareymphtokph01},
3245 103/64 also appears to be
3246 an attractive rational number,
3247 because the division by 64 can be accomplished
3248 by shifting $hx+z$ right by 5 bits.
3249 However, with the TMS370, each shift of a
3250 16-bit operand requires two \texttt{RRC}
3251 instructions, for a total of 10 instructions
3252 at 8 clock cycles each, or 80 clock cycles
3253 (more than the \texttt{DIV}
3254 instruction). Therefore, 243/151 is the
3255 more attractive rational number.}
3256 and using
3257 $x_{MAX}=256$\footnote{A value of 256 rather
3258 than 255 must be used for $x_{MAX}$ because
3259 it is assumed that
3260 $x \in [0,256)$.} with
3261 $z = 395$ by (\ref{eq:eqkminusfzterm01})
3262 leads to the assembly-language shown
3263 in Fig. \ref{fig:tms370c8code243151}.
3264
3265 \begin{figure}
3266 \caption{TMS370 Solution To Example \ref{ex:convmphkphatend} Using The Rational
3267 Number 243/151}
3268 \label{fig:tms370c8code243151}
3269 \begin{verbatim}
3270
3271 MOV input, A ;12 cycles, load far input
3272 ;into A
3273 MPY #243, A ;45 cycles, multiply by 243,
3274 ;result in (MSB:LSB)=(A:B)
3275 ADD #139, B ;6 cycles, 139 = 395 mod 256
3276 ADC #1, A ;6 cycles, 1 = 395 div 256
3277 MOV #151, R02 ;8 cycles, set up for divide
3278 DIV R02, A ;Max 63 cycles, divide,
3279 ;quotient in A, carry set if
3280 ;overflow
3281 JNC NOOVERFLOW ;5 cycles if jump not taken
3282 ;7 cycles if jump taken
3283 ;Jump if div without overflow
3284 MOV #255, A ;6 cycles, replace div result
3285 ;if too large and won't fit in
3286 ;one byte. DIV instruction
3287 ;set C on overflow
3288 NOOVERFLOW: ;Label, no code generated
3289 MOV A, output ;10 cycles, move result to
3290 ;far output var
3291
3292 (Total: Max. 161 clocks, 53.7us with 12 Mhz
3293 crystal.)
3294 \end{verbatim}
3295 \end{figure}
3296
3297 From the problem statement, the input to the algorithm
3298 is assumed to be quantized (it already contains error),
3299 so (\ref{eq:eq0035b}) applies. Evaluating
3300 (\ref{eq:eq0035b}) with $r_A = 243/151$, $z=395$, $r_I = 1.6093$
3301 and $x_{MAX}=256$ yields $K(x)-F(x) \in (0.0060, 2.6159]$ KPH
3302 over the domain [0,256).
3303
3304
3305 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3306 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3307 % (7)(F) BATHROOM SCALE %
3308 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3309 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3310
3311 \begin{example}
3312 \label{ex:bathroomscale}
3313 (BATHROOM SCALE)
3314 A manufacturer wishes to build a family of
3315 electronic bathroom scales using linear transducers
3316 which convert weight to voltage. The voltage
3317 from a transducer is measured using a 10-bit
3318 A/D converter and a custom combinational logic integrated
3319 circuit which will multiply the integer
3320 $x \in [0, 2^{10}-1]_{\intset{}}$ from the A/D
3321 converter by a programmable calibration
3322 constant $h$, neglect a number $q$ of
3323 least significant bits of the product
3324 $hx$, and display the non-neglected
3325 bits as a weight, in integral pounds, for the user.
3326 In the event that the A/D converter is saturated
3327 ($x=2^{10}-1=1,023$), an overflow indicator will
3328 be displayed. The transducers to be used
3329 always produce exactly zero volts with no
3330 weight applied, but vary from 0.25 lbs. per A/D
3331 count to 0.35 lbs. per A/D count in their
3332 transfer characteristic. Market research has
3333 shown that users strongly dislike bathroom
3334 scales which overstate their weight; but simultaneously
3335 prefer that their weight not be understated by more
3336 than 2 lbs. In the design of the custom
3337 integrated circuit for the family of bathroom scales, what
3338 value of $q$ should be chosen? How accurate will
3339 each bathroom scale be?
3340 How many bits must be reserved for $h$, and
3341 what strategy should be
3342 used to choose
3343 $h$ based on the transfer characterisic
3344 $r_I$ of each transducer?
3345 \end{example}
3346
3347 \emph{Solution:}
3348 From the problem statement,
3349 $r_I \in [0.25, 0.35]$,
3350 $r_{IMAX} = 0.35$,
3351 $x_{MAX} = 1,023$\footnote{From the
3352 problem statement, $x=1,023$ will
3353 generate an overflow display, so we need
3354 not consider $x \in [1,023, \; 1,024)$.}, and it is
3355 required that
3356 $L(x)-F(x) \in [-2,0]$. It is also
3357 required that $r_A \leq r_I$
3358 (as in Eqs. \ref{eq:dbpora03}, \ref{eq:dbpora05}); otherwise
3359 it is possible that
3360 $\exists x \in [0,x_{MAX}]$, $L(x) > F(x)$, which
3361 contradicts the product requirements.
3362
3363 With $x_{MAX} = 1,023$,
3364 $\varepsilon_{SPAN} = 2$, and $r_{IMAX} = 0.35$,
3365 (\ref{eq:dbpora03ca}) yields $q=11$ as the
3366 minimum choice for $q$ to meet accuracy
3367 requirements.
3368
3369 With $x_{MAX} = 1,023$,
3370 $z=0$,
3371 $q=11$,
3372 $2^q = 2,048$,
3373 and $r_{IMAX} = 0.35$,
3374 (\ref{eq:dbpora03baa})
3375 predicts that
3376 $L(x)-F(x) \in (-1.84,0]$.
3377
3378 With
3379 $q=11$,
3380 $2^q = 2,048$, and
3381 $r_{IMAX} = 0.35$,
3382 (\ref{eq:dbpora03d})
3383 yields $h_{MAX} = 716$ and
3384 10 bits must be reserved
3385 in the custom integrated circuit
3386 for the calibration factor $h$.
3387 For each $r_I$ to be tabulated,
3388 $h$ should be chosen by (\ref{eq:dbpora03}):
3389 $h=\lfloor r_I 2^q \rfloor = \lfloor 2,048 r_I \rfloor$.
3390
3391
3392 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3393 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3394 % (8) CONCLUSION %
3395 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3396 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3397 \section{Conclusion}
3398
3399 The techniques presented in this paper
3400 demonstrate how linear scaling
3401 functions of the form $y = r_I x$
3402 ($r_I \in \realsetnonneg{}$,
3403 not necessarily $\in \ratsetnonneg$) can be
3404 implemented on inexpensive 4-bit and
3405 8-bit microcontrollers by
3406 approximating $r_I$ with a rational
3407 scaling factor $r_A = h/k$
3408 ($h \in \intsetnonneg{}$,
3409 $k \in \intsetpos{}$).
3410 Several methods for choosing $h$ and $k$
3411 and several implementation techniques were
3412 presented.
3413
3414 A detailed analysis of approximation error
3415 due to the inability to choose $r_A = r_I$ and
3416 due to the quantization inherent
3417 in digital systems and integer
3418 arithmetic was provided. It was shown that
3419 the approximation error
3420 can be bounded when it is known that the
3421 approximation will be used only over a domain of
3422 $[0, x_{MAX}]$, $x_{MAX} \in \intsetpos{}$.
3423 It was also shown that
3424 by introducing an integral parameter
3425 $z$,
3426 the error function could
3427 be adjusted to be
3428 never negative, never positive, or centered about zero.
3429
3430 For cases where $r_I$ is known
3431 at design time, three algorithms were presented
3432 that allow $h$ and $k$ to be chosen
3433 subject to the constraints
3434 $h \leq h_{MAX}$ and $k \leq k_{MAX}$
3435 so as to place $r_A = h/k$ as close as
3436 possible to $r_I$. For cases where $r_I$ is not
3437 precisely known at design time,
3438 methods were presented for designing
3439 tabulated scalings and bounding the approximation
3440 error introduced.
3441
3442 Important results from number theory were presented which
3443 show that although the worst-case error in placing
3444 $r_A$ decreases as $1/N$, the typical error decreases
3445 as $1/N^2$.
3446
3447 Techniques which allow linear approximations to be
3448 performed economically on microcontrollers of varying capability
3449 were also presented. It was shown how the form of $r_A=h/k$
3450 could be modified to improve software efficiency, enable use of only
3451 scaleable (non-division) instructions, or facilitate
3452 tabulation of scaling
3453 factors.
3454
3455
3456 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3457 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3458 % (9) ACKNOWLEDGEMENTS %
3459 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3460 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3461 %Need to retain e-mail addresses to contact all people who have contributed
3462 %to thank.
3463 %Greg Bachelis (greg@math.wayne.edu)
3464 %Robert Berman (rberman@math.wayne.edu)
3465 %Feng Lin (flin@ece.eng.wayne.edu)
3466 %Nick Sahinidis (nikos@uiuc.edu)
3467 %Adam Van Tuyl, (vantuyl@mast.queensu.ca)
3468 %Carl Schweiger (carl@titan.princeton.edu)
3469 %Ken Tindell (ktindell@ssx5.com)
3470 %Steve Vestal (vestal@htc.honeywell.com)
3471 %Bob Whitinger (bob@whitinger.net, bob.whitinger@sea.siemens.com)
3472 %David B. Stewart (dstewart@eng.umd.edu)
3473 %Johan Bengtsson (johanb@docs.uu.se)
3474 %Michael J. Burke (mburke@visteon.com)
3475 %Mark Endicott (mendicot@visteon.com)
3476 %David Eppstein (eppstein@ics.uci.edu)
3477 %Cliff Stallings (cliff@eng.wayne.edu)
3478 %Robert Kakos (robert@enterprise.eng.wayne.edu)
3479 %Klaus-Peter Zauner (kjz@cs.wayne.edu)
3480 %Karsten Tinnefeld (tinnefeld@ls2.cs.uni-dortmund.de)
3481 %Paulette Groen (pgroen@visteon.com)
3482 %Paula Smith (psmith77@visteon.com)
3483 %Mircea Munteanu (mmuntean@visteon.com)
3484 %Adam Gibson (adam.g@virgin.net)
3485 %Virgil (vmhjr@frii.com)
3486 %Bob Crosby (b-crosby@ti.com)
3487 %Una Smith (una.smith@yale.edu)
3488 %Andrea Blome (ablome@mail.cfigroup.com)
3489 %Axel Franke (Axel.Franke@physics.umu.se)
3490 %Yu-Tzu Tsai (ytsai@computer.org)
3491 %William J. Hagen (w.hagen@ieee.org)
3492 %
3493 %
3494 %
3495 %Need also to include Adam's Web site on my Web page,
3496 %http://archives.math.utk.edu/articles/atuyl/confrac/
3497 %
3498 %Need also to include David Eppstein's Web site
3499 %http://www.ics.uci.edu/~eppstein/
3500 %
3501 %
3502 \section{Acknowledgements}
3503
3504 We would like to gratefully acknowledge the assistance
3505 of Greg Bachelis, Robert Berman, Feng
3506 Lin, Nick Sahinidis, Adam Van Tuyl,
3507 Carl Schweiger, Ken Tindell, Steve Vestal,
3508 Bob Whitinger, and David B. Stewart
3509 in finding the areas of
3510 mathematics relevant to the rational number selection
3511 problem. We would also like to
3512 thank Johan Bengtsson, Michael J. Burke,
3513 Mark Endicott, David Eppstein, Mircea Munteanu,
3514 Adam Gibson, and Virgil (of the \texttt{sci.math.num-analysis} newsgroup)
3515 for insight into this problem; Cliff Stallings and
3516 Robert Kakos for support from Wayne State
3517 University's College Of Engineering; Paulette Groen and
3518 Paula Smith for support from Visteon;
3519 Yu-Tzu Tsai and William J. Hagen for support
3520 from the IEEE; Bob Crosby for support
3521 from Texas Instruments; Klaus-Peter Zauner, Andrea Blome,
3522 Una Smith, Karsten Tinnefeld, and
3523 Axel Franke for other tool
3524 and logistical support; and the management
3525 team at Visteon for allowing us to pursue this
3526 effort in the workplace.
3527
3528
3529 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3530 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3531 % (13) VARIABLES AND MATHEMATICAL NOTATION %
3532 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3533 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3534 \section{Definitions, Acronyms, Abbreviations, Variables And Mathematical Notation}
3535
3536 \begin{glossaryenum}
3537
3538 \item \mbox{\boldmath $ \lfloor \cdot \rfloor $}
3539
3540 Used to denote the \emph{floor($\cdot$)} function. The
3541 \emph{floor($\cdot$)}
3542 function is the largest integer not larger than the
3543 argument.
3544
3545 \item \mbox{\boldmath $\lceil \cdot \rceil$ }
3546
3547 Used to denote the \emph{ceiling($\cdot$)} function.
3548 The \emph{ceiling($\cdot$)} function
3549 is the smallest integer not smaller than the
3550 argument.
3551
3552 \item \mbox {\boldmath $a/b$}
3553
3554 An arbitrary rational number.
3555
3556 \item \textbf{coprime}
3557
3558 Two integers that share no prime factors are \emph{coprime}.
3559 \emph{Example:}
3560 6 and 7 are coprime, whereas 6 and 8 are not.
3561
3562 \item \mbox {\boldmath $ F_N $}
3563
3564 The Farey series of order $N$. The Farey series is the
3565 ordered set of all reduced rational numbers with a
3566 denominator not larger than $N$.
3567
3568 \item \textbf{greatest common divisor (g.c.d.)}
3569 The greatest common divisor of two integers is the largest
3570 integer which divides both integers without a remainder.
3571 \emph{Example:} the g.c.d. of 30 and 42 is 6.
3572
3573 \item \mbox{\boldmath $H/K$}, \mbox{\boldmath $h/k$},
3574 \mbox{\boldmath $h'/k'$}, \mbox{\boldmath $h''/k''$},
3575 \mbox{\boldmath $h_i/k_i$}
3576
3577 Terms in a Farey series of order $N$.
3578
3579 \item \textbf{irreducible}
3580
3581 A rational number $p/q$ where $p$ and $q$ are coprime
3582 is said to be \emph{irreducible}.
3583 Equivalently, it may be stated that $p$ and $q$ share no prime factors
3584 or that the greatest common divisor of
3585 $p$ and $q$ is 1.
3586
3587 \item \textbf{KPH}
3588
3589 Kilometers per hour.
3590
3591 \item \textbf{MPH}
3592
3593 Miles per hour.
3594
3595 \item \mbox{\boldmath $\intsetpos$}
3596
3597 The set of positive integers (natural numbers).
3598
3599 \item \mbox{\boldmath $\ratset$}
3600
3601 The set of rational numbers.
3602
3603 \item \mbox{\boldmath $\ratsetnonneg$}
3604
3605 The set of non-negative rational numbers.
3606
3607 \item \mbox{\boldmath $r_A$}
3608
3609 The rational number $h/k$ used to approximate
3610 an arbitrary real number $r_I$.
3611
3612 \item \mbox{\boldmath $r_I$}
3613
3614 The real number, which may or may not be rational,
3615 which is to be approximated by a rational number
3616 $r_A = h/k$.
3617
3618 \item \mbox{\boldmath $\realset$}
3619
3620 The set of real numbers.
3621
3622 \item \mbox{\boldmath $\realsetnonneg$}
3623
3624 The set of non-negative real numbers.
3625
3626 \item \textbf{reduced}
3627
3628 See \emph{irreducible}.
3629
3630 \item \mbox{\boldmath $s_k = p_k/q_k$}
3631
3632 The $k$th convergent of a continued fraction.
3633
3634 \item \mbox{\boldmath $x_{MAX}$}
3635
3636 The largest element of the domain for which the
3637 behavior of an approximation must be guaranteed.
3638 In this paper, most derivations assume
3639 that $x \in [0, x_{MAX}]$, $x_{MAX} \in \intsetpos{}$.
3640
3641 \item \mbox{\boldmath $\intset$}
3642
3643 The set of integers.
3644
3645 \item \mbox{\boldmath $\intsetnonneg$}
3646
3647 The set of non-negative integers.
3648
3649
3650 \end{glossaryenum}
3651
3652
3653 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3654 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3655 % (10) CONTACT INFORMATION %
3656 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3657 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3658 %\section{Contact}
3659 %
3660 %Additional supplemental materials (such as Excel
3661 %spreadsheets which generate Farey terms automatically)
3662 %are downloadable from http://www.daveashley.com.
3663 %E-mail addresses and home pages (where applicable)
3664 %for authors are supplied below.
3665 %David T. Ashley:
3666 % daveashley@daveashley.com
3667 % http://www.daveashley.com/
3668 %Joseph P. DeVoe
3669 % jdevoe@visteon.com
3670 %Cory Pratt
3671 % cpratt2@visteon.com
3672 %Karl Perttunen
3673 % kperttun@visteon.com
3674 %Anatoly Zhigljavsky
3675 % zhigljavskyaa@cardiff.ac.uk
3676 % http:\-//\-www.\-cf.\-ac.\-uk/\-uwcc/\-maths/\-zhig\-ljav\-skyaa/
3677 %
3678 %
3679 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3680 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3681 % (11) REFERENCES %
3682 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3683 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3684 \nocite{*}
3685 \bibliographystyle{IEEE_PQ}
3686 \begin{thebibliography}{1}
3687
3688 \bibitem{HardyAndWrightClassic}
3689 G.H. Hardy, E.M. Wright,
3690 \newblock{\em An Introduction To The Theory Of Numbers}, ISBN 0-19-853171-0.
3691
3692 \bibitem{Harman}
3693 G. Harman (1998) Metric number theory, Oxford University Press.
3694
3695 \bibitem{KargaevZ}
3696 P. Kargaev, A. Zhigljavsky (1966)
3697 Approximation of real numbers by rationals: some metric theorems,
3698 {\it Journal of Number Theory,} 61, 209-225.
3699
3700 \bibitem{KargaevZ1}
3701 P. Kargaev, A. Zhigljavsky (1967)
3702 Asymptotic distribution of the distance function to the Farey points
3703 {\it Journal of Number Theory,} 65, 130-149.
3704
3705 \bibitem{KhinchinClassic}
3706 A. Ya. Khinchin,
3707 \newblock{\em Continued Fractions}, University Of
3708 Chicago Press, 1964; Library Of Congress Catalog Card
3709 Number 64-15819.
3710
3711 \bibitem{LeVeque}
3712 William J. LeVeque,
3713 \newblock{\em Fundamentals Of Number Theory},
3714 Dover Publications, 1977,
3715 ISBN 0-486-68906-9.
3716
3717 \bibitem{OldsClassic}
3718 C. D. Olds,
3719 \newblock{\em Continued Fractions},
3720 Randam House, 1963,
3721 Library Of Congress Catalog Card Number 61-12185.
3722
3723 \bibitem{OreClassic}
3724 Oystein Ore,
3725 \newblock{\em Number Theory And Its History},
3726 ISBN 0-486-65620-9.
3727
3728 \bibitem{SchroederClassic}
3729 M. R. Schroeder,
3730 \newblock{\em Number Theory In Science And Communication},
3731 ISBN 3-540-62006-0.
3732
3733 \end{thebibliography}
3734
3735
3736 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3737 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3738 % (12) BIOGRAPHY %
3739 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3740 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3741 %The biography section applies only to the IEEE paper. Since the splitting
3742 %program is record-oriented but LaTeX is free-form, each line of the biographies
3743 %must be preceded by the _IEEE_ tag.
3744 \begin{biography}{David T. Ashley}
3745 (biography not yet included in document).
3746 \vspace{2.7cm}
3747 \end{biography}
3748 \begin{biography}{Joseph P. DeVoe}
3749 (biography not yet included in document).
3750 \vspace{2.7cm}
3751 \end{biography}
3752 \begin{biography}{Cory Pratt}
3753 (biography not yet included in document).
3754 \vspace{2.7cm}
3755 \end{biography}
3756 \begin{biography}{Karl Perttunen}
3757 (biography not yet included in document).
3758 \vspace{2.7cm}
3759 \end{biography}
3760 \begin{biography}{Anatoly Zhigljavsky}
3761 (biography not yet included in document).
3762 \vspace{2.7cm}
3763 \end{biography}
3764
3765 \begin{figure*}
3766 \caption{Version Control Information (For Reference Only---Will
3767 Be Removed Before Submission Of Paper)}
3768 \vspace{3.0mm}
3769 \begin{small}
3770 \texttt{\LaTeX{} compile date: \today{}.}
3771 \begin{verbatim}
3772 PVCS version control information:
3773 $Header: /cvsroot/esrg/sfesrg/esrgdstb/common/suppmatls/papers_articles/embedded_control/uc_math/rat_app/ieee_rap_2000.txt,v 1.1 2002/04/24 07:23:58 dtashley Exp $.
3774 \end{verbatim}
3775 \end{small}
3776 \end{figure*}
3777
3778 \end{document}
3779
3780
3781 %% $Log: ieee_rap_2000.txt,v $
3782 %% Revision 1.1 2002/04/24 07:23:58 dtashley
3783 %% Initial checkin.
3784 %%
3785 %%
3786 %% Rev 1.62 25 May 2000 14:05:22 dashley1
3787 %% TSE markers removed, as being considered
3788 %% by another journal.
3789 %%
3790 %% Rev 1.61 22 May 2000 11:27:40 dashley1
3791 %% TMS370C8 changed to TMS370 as per
3792 %% Bob Crosby's review.
3793 %%
3794 %% Rev 1.60 19 May 2000 13:41:02 dashley1
3795 %% Typo corrected. 966, not 9,666.
3796 %%
3797 %% Rev 1.59 16 May 2000 09:20:02 dashley1
3798 %% References to daveashley.com removed for
3799 %% now.
3800 %%
3801 %% Rev 1.58 02 May 2000 15:55:22 dashley1
3802 %% Add'l info added.
3803 %%
3804 %% Rev 1.57 02 May 2000 15:54:10 dashley1
3805 %% Stephany Gervasi's contact info added.
3806 %%
3807 %% Rev 1.56 20 Apr 2000 10:50:52 dashley1
3808 %% Newsgroup name corrected.
3809 %%
3810 %% Rev 1.55 20 Apr 2000 09:55:40 dashley1
3811 %% Virgil added to acknowledgments, but must
3812 %% check newsgroup name.
3813 %%
3814 %% Rev 1.54 20 Apr 2000 09:25:08 dashley1
3815 %% At home edits and trims.
3816 %%
3817 %% Rev 1.53 18 Apr 2000 15:07:26 dashley1
3818 %% Minor typo (missing ")") corrected.
3819 %%
3820 %% Rev 1.52 18 Apr 2000 10:42:40 dashley1
3821 %% Minor typo (an extra "the") corrected.
3822 %%
3823 %% Rev 1.51 17 Apr 2000 16:10:14 dashley1
3824 %% Minor correction.
3825 %%
3826 %% Rev 1.50 17 Apr 2000 16:03:10 dashley1
3827 %% Numerous minor corrections made from
3828 %% proofreading.
3829 %%
3830 %% Rev 1.49 17 Apr 2000 13:39:24 dashley1
3831 %% Adam Gibson added to acknowledgements.
3832 %%
3833 %% Rev 1.48 17 Apr 2000 10:14:38 dashley1
3834 %% At home edits, integration of Karl's conclusion.
3835 %%
3836 %% Rev 1.47 13 Apr 2000 10:16:30 dashley1
3837 %% Link for pubs changed.
3838 %%
3839 %% Rev 1.46 12 Apr 2000 14:04:54 dashley1
3840 %% Karsten Tinnefeld added to
3841 %% acknowledgements.
3842 %%
3843 %% Rev 1.45 12 Apr 2000 10:14:36 dashley1
3844 %% Edits to placement of r_A section,
3845 %% additional acknowledgements.
3846 %%
3847 %% Rev 1.44 11 Apr 2000 21:06:24 dashley1
3848 %% Partial evening edits--working on getting
3849 %% Section V finished.
3850 %%
3851 %% Rev 1.43 11 Apr 2000 10:34:04 dashley1
3852 %% Addition of VC information.
3853 %%
3854 %% Rev 1.42 11 Apr 2000 10:14:56 dashley1
3855 %% Minor edits to captions and last example.
3856 %%
3857 %% Rev 1.41 11 Apr 2000 09:52:56 dashley1
3858 %% At-home edits.
3859 %%
3860 %% Rev 1.40 10 Apr 2000 10:27:34 dashley1
3861 %% At-home edits.
3862 %%
3863 %% Rev 1.39 07 Apr 2000 10:39:32 dashley1
3864 %% Home edits.
3865 %%
3866 %% Rev 1.38 06 Apr 2000 10:59:02 dashley1
3867 %% Edits at home. Technical changes,
3868 %% changes in acknowledgements.
3869 %%
3870 %% Rev 1.37 05 Apr 2000 15:28:50 dashley1
3871 %% Acknowlegements section enhanced and
3872 %% slightly rearranged, conversation with
3873 %% Bill Hagen about copyright issues captured
3874 %% as comments in file so won't forget
3875 %% resolution of those issues.
3876 %%
3877 %% Rev 1.36 31 Mar 2000 12:00:48 dashley1
3878 %% Additional acknowledgements and
3879 %% hyperref notes added.
3880 %%
3881 %% Rev 1.35 28 Mar 2000 18:10:20 dashley1
3882 %% Integer factorization mistake corrected.
3883 %%
3884 %% Rev 1.34 28 Mar 2000 10:30:38 dashley1
3885 %% Safety check-in, plus 138 vs. 139 error
3886 %% discovered by Karl.
3887 %%
3888 %% Rev 1.33 13 Mar 2000 10:59:56 dashley1
3889 %% Safety check-in.
3890 %%
3891 %% Rev 1.32 09 Mar 2000 10:51:14 dashley1
3892 %% Getting closer to finishing last section.
3893 %%
3894 %% Rev 1.31 06 Mar 2000 11:51:38 dashley1
3895 %% Incremental changes.
3896 %%
3897 %% Rev 1.30 01 Mar 2000 11:47:04 dashley1
3898 %% Safety check-in.
3899 %%
3900 %% Rev 1.29 13 Feb 2000 10:49:38 dashley1
3901 %% "I" changed to "Z" for set of integers, Dr.
3902 %% Zhigljavsky's section moved as per his
3903 %% recommendation, other changes.
3904 %%
3905 %% Rev 1.28 12 Jan 2000 20:51:08 dashley1
3906 %% Dr. Zhigljavsky's changes integrated.
3907 %%
3908 %% Rev 1.27 10 Jan 2000 17:07:20 dashley1
3909 %% Minor note added about set notations.
3910 %%
3911 %% Rev 1.26 10 Jan 2000 16:50:56 dashley1
3912 %% Dr. Z's e-mail included as far as how to
3913 %% select the right nomenclature for sets of numbers,
3914 %% and Mircea added to acknowledgements.
3915 %%
3916 %% Rev 1.25 07 Jan 2000 19:17:56 dashley1
3917 %% Pasted e-mail in from Dr. Zhigljavsky, preparing
3918 %% to take home.
3919 %%
3920 %% Rev 1.24 03 Jan 2000 12:24:56 dashley1
3921 %% Typo, plus example 7 corrected.
3922 %%
3923 %% Rev 1.23 02 Jan 2000 15:45:00 dashley1
3924 %% Edits, reintegration of version from home.
3925 %%
3926 %% Rev 1.22 31 Dec 1999 19:07:58 dashley1
3927 %% "load" changed to "algorithm".
3928 %%
3929 %% Rev 1.21 31 Dec 1999 16:25:06 dashley1
3930 %% Corrections, moving archives to PVCS,
3931 %% Punch Web Groups archives now obsolete.
3932 %%
3933 %% Rev 1.20 31 Dec 1999 15:30:30 dashley1
3934 %%
3935 %%
3936 %% Rev 1.18 24 Oct 1999 13:01:38 dashley1
3937 %% David Eppstein added to acknowledgements.
3938 %%
3939 %% Rev 1.17 20 Oct 1999 13:22:18 dashley1
3940 %% Mark Endicott (who provided us with several
3941 %% initial suggestions and much insight) added
3942 %% to acknowledgements.
3943 %%
3944 %% Rev 1.16 19 Oct 1999 11:49:40 cpratt2
3945 %% Short explanation of "z". Replaced redundant
3946 %% paragraphs following (8) and (9) with meaningful
3947 %% text.
3948 %%
3949 %% Rev 1.15 19 Oct 1999 10:47:18 dashley1
3950 %% Equation and format changes.
3951 %%
3952 %% Rev 1.14 18 Oct 1999 12:07:58 dashley1
3953 %% Spelling of Greg Bachelis' name corrected.
3954 %%
3955 %% Rev 1.13 18 Oct 1999 12:04:54 dashley1
3956 %% Paulette Groen and Paula Smith added to
3957 %% acknowledgements.
3958 %%
3959 %% Rev 1.12 18 Oct 1999 10:29:02 dashley1
3960 %% Enhancements in several areas.
3961 %%
3962 %% Rev 1.11 15 Oct 1999 09:21:04 dashley1
3963 %% Many enhancements including removing all
3964 %% hard-coded cross-references and adding biography
3965 %% information.
3966 %%
3967 %% Rev 1.10 14 Oct 1999 15:40:18 dashley1
3968 %% Bibliography straightened out, other changes.
3969 %%
3970 %% Rev 1.9 14 Oct 1999 12:33:40 dashley1
3971 %% All equations and tables straightened out,
3972 %% references and glossary to go.
3973 %%
3974 %% Rev 1.8 14 Oct 1999 11:11:38 dashley1
3975 %% Many tables and equations corrected.
3976 %%
3977 %% Rev 1.7 13 Oct 1999 19:34:14 dashley1
3978 %% More equations completed.
3979 %%
3980 %% Rev 1.6 13 Oct 1999 18:44:34 dashley1
3981 %% Added comments as per outline, some progress
3982 %% in incorporating missing equations.
3983 %%
3984 %% Rev 1.5 11 Oct 1999 10:13:14 dashley1
3985 %% Comment delimiter situation straightened out.
3986 %%
3987 %% Rev 1.4 11 Oct 1999 10:10:00 dashley1
3988 %% Safety check-in after weekend work.
3989 %%
3990 %% Rev 1.3 07 Oct 1999 10:04:48 dashley1
3991 %%
3992 %%
3993 %% Rev 1.2 06 Oct 1999 18:47:28 dashley1
3994 %% Evening safety check-in.
3995 %%
3996 %% Rev 1.1 06 Oct 1999 14:48:30 dashley1
3997 %% Safety check-in, conversion up through equation
3998 %% 21 or so.
3999 %%
4000 %% Rev 1.0 06 Oct 1999 09:45:48 dashley1
4001 %% Initial revision.
4002 %%
4003 %% End of pq_paper.tex
4004

dashley@gmail.com
ViewVC Help
Powered by ViewVC 1.1.25