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 |
|