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

Parent Directory | Revision Log

Revision **27** -
(**show annotations**)
(**download**)

*Sat Oct 8 07:04:15 2016 UTC*
(7 years, 9 months ago)
by *dashley*

File MIME type: text/plain

File size: 142554 byte(s)

File MIME type: text/plain

File size: 142554 byte(s)

Initial commit.

1 | %% $Header: /cvsroot/esrg/sfesrg/esrgdstb/common/suppmatls/papers_articles/embedded_control/uc_math/rat_app/ieee_rap_2000.txt,v 1.1 2002/04/24 07:23:58 dtashley Exp $ |

2 | % |

3 | %Made liaison with Stephany Gervasi at IEEE Computer; |

4 | %she now accepts initial papers for review (Yu-Tzu's old |

5 | %job). Must give her .PS or .PDF on initial submission. Best e-mail |

6 | %is tse@computer.org. Her physical mailing address is exactly |

7 | %the same as Yu-Tzu's, below. |

8 | %================================================================== |

9 | %Made liaison with Yu-Tzu Tsai at IEEE Computer, the contact |

10 | %information for where she works is below. Final |

11 | %manuscript should be submitted to her as .PDF |

12 | %or .PS electronically. I was also advised that paper |

13 | %should not exceed 20 pages. |

14 | % |

15 | %Her e-mail is YTSAI@COMPUTER.ORG. |

16 | % |

17 | %Publications Office |

18 | %10662 Los Vaqueros Circle |

19 | %P. O. Box 3014 |

20 | %Los Alamitos, CA 90720-1264 |

21 | %Phone: +1-714-821-8380 |

22 | %FAX: +1-714-821-4010 |

23 | %Publications Orders: +1-800-272-6657 |

24 | % |

25 | %=================================================================== |

26 | %Notes from conversation with Joe on 12/31/99. |

27 | % |

28 | % a)Joe indicated to change "load" to algorithm on p.1. Done. |

29 | % |

30 | % b)Joe indicated that the quantization error for a rational number |

31 | % could be compactly expressed as (a mod b)/b. We might want to |

32 | % include this, but it may not assist in the error analysis, but |

33 | % it may be useful as a way of thinking. |

34 | % |

35 | % c)Joe indicated that for equations (10) and (11), the the sign |

36 | % seemed inconsistent with the subsequent equations. We should |

37 | % discuss and resolve this. |

38 | % |

39 | %%01/10/00: Pasting in e-mail from Dr. Zhigljavsky for reference. |

40 | %% |

41 | %%Concerning |

42 | %%"I" to denote the set of integers, |

43 | %%your collegues is right, the standard notation is: |

44 | %% |

45 | %%Z for the set of all integers |

46 | %%Z_{+} for the set of non-negative integers |

47 | %%N for the set of positive integers (1,2,3,...) |

48 | %%R for reals |

49 | %% |

50 | %%They are actually not standard R,Z,N. To generate proper ones one |

51 | %%should use |

52 | %% |

53 | %%\usepackage{amsfonts} |

54 | %% |

55 | %%and then, in the mathematical mode, type |

56 | %% |

57 | %%\Bbb{R} |

58 | %% |

59 | %%\Bbb{N} |

60 | %%or |

61 | %%\Bbb{Z} |

62 | %% |

63 | %%rather than just R,Z or N. |

64 | %% |

65 | %%Dave's Note: LaTeX warned me that \Bbb{} is outdated, and to use \mathbb{} instead. It appears that |

66 | %%\Bbb{} is no longer fully supported, as it gives Greek symbols where there should be none, appears |

67 | %%to be a bug because \Bbb{} no longer supported, so will use \mathbb{}, which does not have this |

68 | %%bug. |

69 | %% |

70 | %%Dave's Second Note: Was advised by Robert Berman |

71 | %%that normally Q used for rationals, sometimes P or I for irrationals, all in those alternate typefaces |

72 | %%similar to R, Z, etc. |

73 | %%May want to adopt those for brevity. He also advised that some flexibility in |

74 | %%definitions, as long as this is made clear. |

75 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |

76 | %%Notes on using the "hyperref" package. |

77 | %% |

78 | %%On about 03/30/00, the hyperref package was tested, and the results were impressive. It |

79 | %%causes generation of a PostScript file that, when distilled using Acrobat Distiller, |

80 | %%contains bookmarks. A newsgroup posting from Una Smith was very helpful. |

81 | %% |

82 | %%Here are the important points from Una's post: |

83 | %% |

84 | %%The last package invoked must be the hyperref package, |

85 | %% \usepackage[ps2pdf]{hyperref} |

86 | %% |

87 | %%This must be immediately followed by the following line to deal with |

88 | %%a bug in hyperref which will be fixed later. |

89 | %% \let\x\undefined |

90 | %% |

91 | %%There must be a file hyperref.cfg with the following contents: |

92 | %% \hypersetup{% |

93 | %% backref=false, |

94 | %% colorlinks=false, |

95 | %% pageanchor=false, |

96 | %% bookmarks=true, |

97 | %% bookmarksopen=true}% |

98 | %% |

99 | %%Una's e-mail is UNA.SMITH@YALE.EDU |

100 | %% |

101 | %%It is also noteworthy that there may be errors on the first few compilations because of |

102 | %%(I'm guessing) different formats on the .AUX files. |

103 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |

104 | %%Notes from conversation with Bill Hagen on 04/05/00. |

105 | %% |

106 | %%I had sent an e-mail to Bill with four questions about what is and what is not allowed under |

107 | %%IEEE copyright. Bill answered my questions on the phone so he won't respond to the E-mail. |

108 | %% |

109 | %% a)E-mailing ... don't worry about it so long as the purpose is research collaboration or |

110 | %% sharing paper. |

111 | %% |

112 | %% b)Postal mailing ... don't worry about it so long as it is for research collaboration or |

113 | %% sharing paper and not a "for profit" or "vending" thing. |

114 | %% |

115 | %% c)Teaching an internal corporate class. Bill indicated that he does not believe the IEEE |

116 | %% would have a problem with it, but that it might be best to have an exchange of letters |

117 | %% before this is done. In other words, probably Visteon would not have to pay the copyright |

118 | %% fees "per student", but need to confirm via more formal mechanism. This would also |

119 | %% ease any concerns by our corporate librarian. |

120 | %% |

121 | %% d)Use of material in a book ... Bill does not believe there will be a problem so long as |

122 | %% it is my own material (not a DIFFERENT IEEE paper); but, again, a more formal mechanism |

123 | %% might be advised, i.e. an exchange of letters. This might also ease any concerns by |

124 | %% a publisher. |

125 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |

126 | %%Not sure what notation to use for the set of rational numbers. I believe (if memory |

127 | %%serves me correctly), that "Q" can be used, but don't remember for sure. To protect |

128 | %%for this, will define a new LaTeX command so can change all occurences in one place |

129 | %%until we have talked and confirmed with Dr. Zhigljavsky. In fact, will define all |

130 | %%sets this way just in case there needs to be a global change. |

131 | %% |

132 | %%Sets of real numbers. |

133 | \newcommand{\realset}{{\mathbb{R}}} |

134 | \newcommand{\realsetnonneg}{{\mathbb{R}^+}} |

135 | %% |

136 | %%Sets of integers. |

137 | \newcommand{\intset}{{\mathbb{Z}}} |

138 | \newcommand{\intsetnonneg}{{\mathbb{Z}^+}} |

139 | \newcommand{\intsetpos}{{\mathbb{N}}} |

140 | %% |

141 | %%Sets of rational numbers. |

142 | \newcommand{\ratset}{{\mathbb{Q}}} |

143 | \newcommand{\ratsetnonneg}{{\mathbb{Q}^+}} |

144 | %% |

145 | %%Sets of irrational numbers. |

146 | \newcommand{\irratset}{{\mathbb{error}}} |

147 | \newcommand{\irratsetnonneg}{{\mathbb{error}^+}} |

148 | |

149 | |

150 | |

151 | %%Not sure what Greek letter to use to denote the difference |

152 | %%at the terminal L(x_{MAX}). For that reason will |

153 | %%leave that option open and define it as a new command, |

154 | %%so it can be changed in one place. |

155 | \newcommand{\lxtermdifffuncsymbol}{\psi} |

156 | |

157 | |

158 | |

159 | |

160 | % STYLE FILES, ETC. % |

161 | |

162 | |

163 | \documentclass[twocolumn]{ieee_pq} %!PN |

164 | |

165 | \usepackage{amsfonts} |

166 | \usepackage{amsmath} |

167 | |

168 | \usepackage{graphicx} |

169 | |

170 | %Using hyperref reserved for generating a .PDF only. |

171 | %\usepackage[ps2pdf]{hyperref} |

172 | %\let\x\undefined |

173 | |

174 | \def\BibTeX{{\rm B\kern-.05em{\sc i\kern-.025em b}\kern-.08em |

175 | T\kern-.1667em\lower.7ex\hbox{E}\kern-.125emX}} |

176 | |

177 | |

178 | |

179 | |

180 | % NEW NUMBERED ENVIRONMENTS (THEOREMS, EXAMPLES, ETC.) % |

181 | |

182 | |

183 | \newtheorem{algorithm}{Algorithm} |

184 | |

185 | \newtheorem{example}{Example} |

186 | |

187 | \newtheorem{theorem}{Theorem} |

188 | |

189 | |

190 | |

191 | |

192 | % NEW ENVIRONMENT DEFINITIONS % |

193 | |

194 | |

195 | %The "itemize" environment defined by the IEEE style files didn't seem to have |

196 | %quite the right appearance for presenting our algorithms. For this reason, the |

197 | %following environments were defined. Level 0 is flush left with bullets, Level 1 |

198 | %is slightly more indented, etc. |

199 | \newenvironment{alglvl0}{\begin{list} |

200 | {$\bullet$}{\setlength{\labelwidth}{3mm}\setlength{\leftmargin}{6mm}}} |

201 | {\end{list}} |

202 | \newenvironment{alglvl1}{\begin{list} |

203 | {$\bullet$}{\setlength{\labelwidth}{3mm}\setlength{\leftmargin}{6mm}}} |

204 | {\end{list}} |

205 | |

206 | %The following environment is intended for listing properties (of continued fractions, |

207 | %convergents, etc.). |

208 | \newenvironment{propenum}{\begin{list} |

209 | {$\bullet$}{\setlength{\labelwidth}{3mm}\setlength{\leftmargin}{6mm}}} |

210 | {\end{list}} |

211 | |

212 | %The following environment is intended for general enumeration. |

213 | \newenvironment{generalenum}{\begin{list} |

214 | {$\bullet$}{\setlength{\labelwidth}{3mm}\setlength{\leftmargin}{6mm}}} |

215 | {\end{list}} |

216 | |

217 | %The following environment is intended for general enumeration with a slight indent. |

218 | \newenvironment{generalenumindent01}{\begin{list} |

219 | {$\bullet$}{\setlength{\labelwidth}{3mm}\setlength{\leftmargin}{12mm}}} |

220 | {\end{list}} |

221 | |

222 | |

223 | |

224 | %The following environment is for the glossary at the end. |

225 | \newenvironment{glossaryenum}{\begin{list} |

226 | {}{\setlength{\labelwidth}{0mm} |

227 | \setlength{\leftmargin}{4mm} |

228 | \setlength{\itemindent}{-4mm} |

229 | \setlength{\parsep}{0.85mm}}} |

230 | {\end{list}} |

231 | |

232 | |

233 | |

234 | |

235 | % SET THE PAGE NUMBER % |

236 | |

237 | |

238 | \setcounter{page}{99} |

239 | |

240 | |

241 | |

242 | |

243 | % HYPHENATION EXCEPTION RULES % |

244 | |

245 | |

246 | %\hyphenation{http:-//-www.-cf.-ac.-uk/-uwcc/-maths/-zhig-ljavskyaa/} |

247 | \hyphenation{micro-con-trol-ler} |

248 | \hyphenation{rat-io-met-ric} |

249 | \hyphenation{rat-ion-al} |

250 | \hyphenation{Zhig-ljav-sky} |

251 | |

252 | |

253 | |

254 | |

255 | % START OF DOCUMENT % |

256 | |

257 | |

258 | \begin{document} |

259 | |

260 | \thispagestyle{empty} |

261 | |

262 | %\begin{centering} |

263 | |

264 | \begin{large} |

265 | |

266 | \textbf{December 8, 2000:} This paper |

267 | is distributed with the \emph{IjuTools} suite. |

268 | The paper contained on the following pages was rejected by ``\emph{IEEE Transactions On Computers}'' in 2000. |

269 | Therefore, the five authors listed hold the copyright. |

270 | \LaTeX{} source code is also included in this distribution. The five authors hereby waive all rights under |

271 | copyright law and grant permission to reproduce or use this paper and the accompanying |

272 | \LaTeX{} source code, in whole or in part, for any purpose whatsoever, |

273 | commercial or non-commercial, with no requirement for |

274 | renumeration of the authors, and no requirement to cite or otherwise supply the identity |

275 | of the authors. |

276 | |

277 | Under Adobe Arobat 3, some subscripts in this paper disappear when printed. Adobe Acrobat 4 |

278 | or its successors are recommended for printing. |

279 | \end{large} |

280 | |

281 | %\end{centering} |

282 | |

283 | \cleardoublepage |

284 | |

285 | \title{Economical Implementation Of Linear Scaling Functions |

286 | In Microcontroller Software Using Rational Number |

287 | Approximation Techniques} |

288 | |

289 | \author{David T. Ashley, |

290 | Joseph P. DeVoe, |

291 | Cory Pratt, |

292 | Karl Perttunen, |

293 | Anatoly Zhigljavsky |

294 | \thanks{D.T. Ashley, J.P. DeVoe, C. Pratt, and K. |

295 | Perttunen are with Visteon Automotive |

296 | Systems in Dearborn, Michigan, USA. E-mail: |

297 | \{dashley1, jdevoe, cpratt2, kperttun\}@visteon.com. |

298 | Anatoly Zhigljavsky is with Cardiff University, |

299 | Cardiff, UK. |

300 | E-mail: zhigljavskyaa@cardiff.ac.uk.}} |

301 | |

302 | \markboth{ }{ } |

303 | |

304 | \maketitle |

305 | |

306 | |

307 | |

308 | |

309 | |

310 | % (1) ABSTRACT AND KEYWORDS % |

311 | |

312 | |

313 | \begin{abstract} |

314 | Inexpensive microcontrollers are widely used in |

315 | vehicles, consumer |

316 | electronics, laboratory equipment, and medical equipment. |

317 | A significant problem in the design of software |

318 | for these devices |

319 | is the efficient and reliable implementation of |

320 | arithmetic. In this paper, |

321 | techniques are developed to use an |

322 | instruction set typical of an |

323 | inexpensive microcontroller to economically approximate |

324 | linear scaling functions of the form |

325 | $f(x)=r_{I}x$ ($r_{I}$ non-negative and real but |

326 | not necessarily rational) |

327 | in the first quadrant using a rational approximation factor |

328 | $r_{A}=h/k$. |

329 | Methods and considerations in choosing $h$ and $k$ are |

330 | developed, and error terms are derived which bound the |

331 | error introduced by the rational approximation. |

332 | \end{abstract} |

333 | |

334 | |

335 | \begin{keywords} |

336 | Microcontroller arithmetic, linear scaling, rational approximation, Farey series, |

337 | continued fractions. |

338 | \end{keywords} |

339 | |

340 | |

341 | |

342 | % (2) INTRODUCTION % |

343 | |

344 | |

345 | \section{Introduction} |

346 | \PARstart{L}{ow-cost} microcontrollers provide |

347 | weak instruction sets, and a significant |

348 | design challenge in the development of |

349 | software for these devices is the |

350 | economical implementation of arithmetic. |

351 | This paper presents techniques which are |

352 | suitable for economically implementing |

353 | high-precision linear scalings using |

354 | instructions which are characteristic of |

355 | inexpensive 4-bit and 8-bit microcontrollers. |

356 | |

357 | This paper is confined |

358 | to the approximation of linear |

359 | scalings of the form |

360 | $y=r_{I}x$ ($r_I \in \realsetnonneg{}$, not |

361 | necessarily $\in \ratsetnonneg{}$) |

362 | by linear scalings of the form $y=hx/k$ |

363 | ($h \in \intsetnonneg{}$, $k \in \intsetpos{}$). |

364 | In |

365 | Section \ref{sec:analysisapproxerr}, |

366 | error terms for rational approximations |

367 | are derived without regard for how |

368 | integers $h$ and $k$ are chosen. |

369 | In |

370 | Section \ref{sec:methodshkchoose}, |

371 | results from |

372 | number theory are presented which give |

373 | insight into how to choose rational |

374 | numbers $h/k$ for use as scaling factors. |

375 | In |

376 | Section \ref{sec:probresults}, |

377 | probabilistic results from number theory are |

378 | presented outlining how close |

379 | to a real $r_I$ a rational |

380 | $r_A = h/k$ can typically be chosen. |

381 | In |

382 | Section \ref{sec:tabscalingfactors}, |

383 | a special case in which |

384 | $k$ is chosen as an integral power of |

385 | two is developed with the aim of providing a |

386 | framework for tabulating scaling factors. |

387 | In |

388 | Section \ref{sec:imptechniques}, |

389 | practical techniques for economically |

390 | implementing rational scaling functions |

391 | using inexpensive microcontroller |

392 | instruction sets are presented. |

393 | In Section \ref{sec:designexamples}, |

394 | design examples which illustrate |

395 | the techniques are presented. |

396 | |

397 | |

398 | |

399 | % (3) ANALYSIS OF APPROXIMATION ERROR (WITHOUT REGARD FOR HOW R_A IS CHOSEN) % |

400 | |

401 | |

402 | \section{Analysis Of Approximation Error} |

403 | \label{sec:analysisapproxerr} |

404 | |

405 | A function $y=r_{I}x$ |

406 | ($r_{I} \in \realsetnonneg{}$, |

407 | not necessarily $\in \ratsetnonneg{}$) |

408 | is to be approximated |

409 | by a function $y=r_{A}x$; |

410 | $r_{A}=h/k$, $\in \ratsetnonneg$.\footnote{Mnemonic for $r_I$ and $r_A$: |

411 | \emph{I}=ideal, \emph{A}=actual.} |

412 | In this section, error terms are |

413 | developed which bound |

414 | the error introduced when |

415 | $f(x)=r_{I}x$ is approximated |

416 | by $f(x)=r_{A}x$ in the first |

417 | quadrant only ($x \in \realsetnonneg{}$). |

418 | |

419 | |

420 | |

421 | |

422 | % (2)(A) MODEL FUNCTIONS % |

423 | |

424 | |

425 | \subsection{Model Functions} |

426 | |

427 | (\ref{eq:eq0001}) through |

428 | (\ref{eq:eq0003}) provide |

429 | models of the function |

430 | to be approximated |

431 | which vary in whether |

432 | the domain is real or |

433 | integral, and in |

434 | whether the range is |

435 | real or integral. |

436 | The \emph{floor($\cdot{}$)} function, |

437 | denoted $\lfloor \cdot{} \rfloor$, |

438 | is used to model |

439 | the effect of quantization, |

440 | such as occurs when a real argument |

441 | is quantized for implementation |

442 | using integer arithmetic, or |

443 | when the fractional |

444 | part of a quotient is |

445 | discarded.\footnote{The \emph{ceiling($\cdot{}$)} function, denoted |

446 | $\lceil \cdot{} \rceil$, is also used and appears in many algebraic |

447 | results throughout the paper. There is often ambiguity in how |

448 | the \emph{floor($\cdot{}$)} and |

449 | \emph{ceiling($\cdot{}$)} functions are defined for negative |

450 | arguments. Here, |

451 | $\lfloor -1.1 \rfloor = \lceil -2.1 \rceil = -2$.} |

452 | |

453 | In practical problems, |

454 | the domain and range may |

455 | be integral rather |

456 | than real for either |

457 | practical or conceptual reasons. |

458 | As an example of |

459 | a domain which is |

460 | integral for \emph{practical} |

461 | reasons, consider an embedded |

462 | software algorithm which has access |

463 | only to integral data |

464 | (as might happen with |

465 | integral vehicle speed |

466 | reported to an embedded software algorithm |

467 | over a network). |

468 | In this case, |

469 | the behavior of the software |

470 | may be specified only over |

471 | $\intsetnonneg$, as it is |

472 | impossible to excite the |

473 | software with non-integral |

474 | values. It may also happen that |

475 | the domain is \emph{conceptually} |

476 | integral, as occurs when the |

477 | input argument is a count or other |

478 | inherently integral quantity. |

479 | The range may also be integral for |

480 | similar practical or conceptual reasons. |

481 | |

482 | (\ref{eq:eq0001}) provides a model of the ideal |

483 | function to be approximated when |

484 | both domain and range are the |

485 | non-negative real numbers. |

486 | |

487 | \begin{equation} |

488 | \label{eq:eq0001} |

489 | F(x)=r_{I}x |

490 | \end{equation} |

491 | |

492 | (\ref{eq:eq0002}) provides a model |

493 | of the ideal function to be |

494 | approximated when the function |

495 | is to be evaluated on a domain |

496 | of non-negative integers only. |

497 | |

498 | \begin{equation} |

499 | \label{eq:eq0002} |

500 | G(x)= r_{I} \lfloor x \rfloor |

501 | \end{equation} |

502 | |

503 | (\ref{eq:eq0004}) provides |

504 | a model of the ideal |

505 | function to be |

506 | approximated when |

507 | only the range is integral. |

508 | |

509 | \begin{equation} |

510 | \label{eq:eq0004} |

511 | H(x)=\lfloor r_{I}x\rfloor |

512 | \end{equation} |

513 | |

514 | (\ref{eq:eq0003}) provides |

515 | a model of the ideal |

516 | function to be aproximated |

517 | when both the |

518 | domain and range are the |

519 | non-negative integers. |

520 | |

521 | \begin{equation} |

522 | \label{eq:eq0003} |

523 | I(x)=\lfloor r_{I}\lfloor x\rfloor\rfloor |

524 | \end{equation} |

525 | |

526 | (\ref{eq:eq0005}) defines $r_{A}$, |

527 | the rational number used |

528 | to approximate $r_{I}$. |

529 | $h/k$ is always assumed reduced. |

530 | |

531 | \begin{equation} |

532 | \label{eq:eq0005} |

533 | r_{A}=\frac{h}{k}; \; h \in \intsetnonneg; \; k \in \intsetpos |

534 | \end{equation} |

535 | |

536 | (\ref{eq:eq0006}) provides |

537 | a model of the function which is |

538 | used to approximate |

539 | (\ref{eq:eq0001}), |

540 | (\ref{eq:eq0002}), |

541 | (\ref{eq:eq0004}), |

542 | or |

543 | (\ref{eq:eq0003}). |

544 | The approximation |

545 | always has an integral domain and range. |

546 | |

547 | \begin{equation} |

548 | \label{eq:eq0006} |

549 | J(x) = \left\lfloor {r_A \left\lfloor x \right\rfloor } \right\rfloor |

550 | = \left\lfloor {\frac{{h\left\lfloor x \right\rfloor }}{k}} \right\rfloor |

551 | \end{equation} |

552 | |

553 | (\ref{eq:eq0007}) |

554 | defines an enhancement to |

555 | (\ref{eq:eq0006}). |

556 | The approximation error introduced |

557 | can be shifted using integral parameter $z$. |

558 | |

559 | \begin{equation} |

560 | \label{eq:eq0007} |

561 | K(x) = \left\lfloor {\frac{{h\left\lfloor x \right\rfloor |

562 | + z}}{k}} \right\rfloor ; \; z \in \intset{} |

563 | \end{equation} |

564 | |

565 | (\ref{eq:eq0009}) and (\ref{eq:eq0009b}) |

566 | are special cases of (\ref{eq:eq0006}) and (\ref{eq:eq0007}) |

567 | which are useful |

568 | in microcontroller work, since division by a power of two can be achieved |

569 | very economically using right-shift instructions. |

570 | |

571 | \begin{equation} |

572 | \label{eq:eq0009} |

573 | L(x) = \left\lfloor {\frac{{h\left\lfloor x \right\rfloor }}{{2^q }}} \right\rfloor ; |

574 | \; k = 2^q ; \;r_A = \frac{h}{{2^q }} |

575 | \end{equation} |

576 | |

577 | \begin{equation} |

578 | \label{eq:eq0009b} |

579 | M(x) = \left\lfloor {\frac{{h\left\lfloor x \right\rfloor } + z }{{2^q }}} \right\rfloor; |

580 | \; k = 2^q ; \; r_A = \frac{h}{{2^q }} |

581 | \end{equation} |

582 | |

583 | |

584 | |

585 | |

586 | % (3)(B)METHODS OF ERROR ANALYSIS % |

587 | |

588 | |

589 | \subsection{Methods Of Error Analysis} |

590 | |

591 | Quantization of a real argument which is not necessarily |

592 | rational is treated by noting that |

593 | quantization introduces an error |

594 | $\varepsilon \in [0,1)$ (Eq. \ref{eq:dtaea0001}). |

595 | |

596 | \begin{equation} |

597 | \label{eq:dtaea0001} |

598 | \left\lfloor x \right\rfloor = x - \varepsilon ;\;\varepsilon \in [0,1) |

599 | \end{equation} |

600 | |

601 | Quantization of a rational argument $a/b$ is treated by |

602 | noting that the largest quantization error |

603 | $\varepsilon$ occurs when |

604 | $a$ is one less than an integral multiple of $b$ |

605 | (Eq. \ref{eq:dtaea0002}).\footnote{Strictly speaking, |

606 | $\varepsilon \in \left\{ 0, \frac{1}{b}, \ldots, |

607 | \frac{b-2}{b}, \frac{b-1}{b} \right\}$; however, since |

608 | only the smallest and largest values are of interest, |

609 | (\ref{eq:dtaea0002}) is used.} |

610 | |

611 | \begin{equation} |

612 | \label{eq:dtaea0002} |

613 | \left\lfloor \frac{a}{b} \right\rfloor |

614 | = \frac{a}{b} - \varepsilon ; \; \; \varepsilon \in \left[0, \frac{b-1}{b} \right] |

615 | \end{equation} |

616 | |

617 | Since a difference of integers must also be |

618 | an integer, results on differences of quantized values |

619 | are constrained further by intersection with the set of integers. |

620 | Care must be taken in the intersection of an interval |

621 | with the |

622 | set of integers, as the |

623 | distinction between an open interval and a closed |

624 | interval is significant. The identities |

625 | in (\ref{eq:dtaea0003}) through |

626 | (\ref{eq:dtaea0006}) are employed.\footnote{In (\ref{eq:dtaea0003}) |

627 | through (\ref{eq:dtaea0006}) and throughout the paper, |

628 | a subscript of $\intset{}$ is used to denote that |

629 | a set may contain only integers.} |

630 | |

631 | \begin{equation} |

632 | \label{eq:dtaea0003} |

633 | {[ x , y ] \cap \intset{} = [ \lceil x \rceil , \lfloor y \rfloor ]}_{\intset{}} |

634 | \end{equation} |

635 | |

636 | \begin{equation} |

637 | \label{eq:dtaea0004} |

638 | {[ x , y ) \cap \intset{} = [ \lceil x \rceil , \lceil y-1 \rceil ]}_{\intset{}} |

639 | \end{equation} |

640 | |

641 | \begin{equation} |

642 | \label{eq:dtaea0005} |

643 | {( x , y ] \cap \intset{} = [ \lfloor x+1 \rfloor , \lfloor y \rfloor ]}_{\intset{}} |

644 | \end{equation} |

645 | |

646 | \begin{equation} |

647 | \label{eq:dtaea0006} |

648 | {( x , y ) \cap \intset{} = [ \lfloor x+1 \rfloor , \lceil y-1 \rceil ]}_{\intset{}} |

649 | \end{equation} |

650 | |

651 | |

652 | |

653 | |

654 | % (3)(C)ERROR ANALYSIS OF {J(X),K(X)}-I(X) % |

655 | |

656 | |

657 | \subsection{Error Analysis Of $ \{ J(x),K(x) \} - I(x)$} |

658 | |

659 | (\ref{eq:eq0006}) is a |

660 | special case of (\ref{eq:eq0007}), |

661 | so the difference function |

662 | $K(x)-I(x)$ with $z=0$ |

663 | is $J(x)-I(x)$. For this reason it is not necessary |

664 | to derive $J(x)-I(x)$ separately. |

665 | The difference function (or error function) is the |

666 | difference between the ideal model function |

667 | with integral domain and range [$I(x)$], and the |

668 | approximation function with integral domain and range |

669 | [$J(x)$ or $K(x)$] (Eq. \ref{eq:eq0010}). |

670 | |

671 | \begin{equation} |

672 | \label{eq:eq0010} |

673 | K(x) - I(x) = \left\lfloor {\frac{{h\left\lfloor x \right\rfloor |

674 | + z}}{k}} \right\rfloor |

675 | - \left\lfloor {r_I \left\lfloor x \right\rfloor } \right\rfloor |

676 | \end{equation} |

677 | |

678 | The inner \emph{floor($\cdot{}$)} function can be removed |

679 | with the understanding that |

680 | the difference function |

681 | will be evaluated on a |

682 | domain of integers only (\ref{eq:eq0011}). |

683 | |

684 | \begin{equation} |

685 | \label{eq:eq0011} |

686 | K(x) - I(x) = \left\lfloor {\frac{{hx |

687 | + z}}{k}} \right\rfloor |

688 | - \left\lfloor {r_I x} \right\rfloor ;\quad x \in \intsetnonneg{} |

689 | \end{equation} |

690 | |

691 | Quantization (two occurrences of the |

692 | \emph{floor($\cdot{}$)} function) |

693 | can be modeled as introducing |

694 | errors $\varepsilon_1$ and $\varepsilon_2$ |

695 | (\ref{eq:eq0012}). |

696 | Because the domain is integral, |

697 | the largest quantization error in |

698 | $\varepsilon_{1}$ occurs when $hx+z$ |

699 | is one less than an integral multiple of $k$, |

700 | hence $\varepsilon _1 \in \left[ {0,\frac{{k - 1}}{k}} \right]$. |

701 | Because $r_{I}$ may be irrational, |

702 | $\varepsilon_{2}\in [0,1)$. |

703 | |

704 | \begin{figure*} |

705 | \begin{equation} |

706 | \label{eq:eq0012} |

707 | K(x) - I(x) = |

708 | \frac{{hx + z}}{k} - \varepsilon _1 - r_I x + \varepsilon _2 ;\;x \in \intsetnonneg{}; |

709 | \;\; |

710 | \varepsilon _1 \in \left[ {0,\frac{{k - 1}}{k}} \right];\;\;\varepsilon _2 \in \left[ {0,1} \right) |

711 | \end{equation} |

712 | \end{figure*} |

713 | |

714 | Choosing the extremes |

715 | of $\varepsilon_{1}$ and $\varepsilon_{2}$ |

716 | so as to minimize and maximize the |

717 | difference function |

718 | bounds the approximation error (\ref{eq:eq0014}). |

719 | |

720 | \begin{figure*} |

721 | \begin{equation} |

722 | \label{eq:eq0014} |

723 | K(x) - I(x) \in |

724 | \left[ {(r_A - r_I )x + \frac{z}{k} - |

725 | \frac{{k - 1}}{k},(r_A - r_I )x + \frac{z}{k} + 1} \right) |

726 | \end{equation} |

727 | \end{figure*} |

728 | |

729 | (\ref{eq:eq0014}) may |

730 | be intersected with the set of integers, |

731 | because the result, a difference of integers, |

732 | must also be an integer (\ref{eq:eq0015}). |

733 | |

734 | \begin{figure*} |

735 | \begin{equation} |

736 | \label{eq:eq0015} |

737 | K(x) - I(x) \in |

738 | \left[ {\left\lceil {(r_A - r_I )x + \frac{z}{k} - |

739 | \frac{{k - 1}}{k}} \right\rceil , |

740 | \left\lceil {(r_A - r_I )x + \frac{z}{k}} \right\rceil } \right]_{\intset{}} |

741 | \end{equation} |

742 | \end{figure*} |

743 | |

744 | With $z=0$, (\ref{eq:eq0015}) supplies $J(x)-I(x)$ (\ref{eq:eq0016}). |

745 | |

746 | \begin{figure*} |

747 | \begin{equation} |

748 | \label{eq:eq0016} |

749 | J(x) - I(x) \in |

750 | \left[ {\left\lceil {(r_A - r_I )x - |

751 | \frac{{k - 1}}{k}} \right\rceil , |

752 | \left\lceil {(r_A - r_I )x} \right\rceil } \right]_{\intset{}} |

753 | \end{equation} |

754 | \end{figure*} |

755 | |

756 | $r_{A}$ must almost always |

757 | be chosen unequal to $r_{I}$, |

758 | and as a result the approximation error is |

759 | larger for larger $x$. Most |

760 | approximations are used only in a |

761 | restricted domain, and it is useful |

762 | to know the upper bound on approximation |

763 | error when the approximation |

764 | is used only in an interval |

765 | $[0,x_{MAX}]_{\intset{}}$, $x_{MAX} \in \intsetpos{}$.\footnote{Throughout |

766 | the paper, it is assumed that $x_{MAX} \in \intsetpos{}$.} |

767 | These upper bounds can be obtained by |

768 | substitution into (\ref{eq:eq0015}), |

769 | and are presented as (\ref{eq:eq0017}). |

770 | Note that the second case of (\ref{eq:eq0017}) |

771 | may not be distinct, |

772 | depending on the choice of $z$. |

773 | |

774 | \begin{figure*} |

775 | \begin{equation} |

776 | \label{eq:eq0017} |

777 | \left. {K(x) - I(x)} \right|_{x \in [0,x_{MAX} ]_{\intset{}}} \in |

778 | \left\{ {\begin{array}{*{20}l} |

779 | {\left[ {\left\lceil {(r_A - r_I )x_{MAX} + \frac{z}{k} - \frac{{k - 1}}{k}} |

780 | \right\rceil , \left\lceil {\frac{z}{k}} \right\rceil} \right]_{\intset{}} ,} \hfill & {r_A \le r_I - \frac{z+1}{{x_{MAX} k}}} \\ |

781 | \\ |

782 | { \left[ {0, \left\lceil {\frac{z}{k} } \right\rceil} \right]_{\intset{}},} \hfill & {r_I - \frac{z+1}{{x_{MAX} k}} < r_A \le r_I } \\ |

783 | \\ |

784 | \left[ { \left\lceil {\frac{z}{k} - \frac{k-1}{k}} \right\rceil , \left\lceil {\frac{z}{k}} \right\rceil } \right]_{\intset{}} , \hfill & {r_A = r_I} \\ |

785 | \\ |

786 | {\left[ { \left\lceil {\frac{z}{k} - \frac{k-1}{k}} \right\rceil , |

787 | \left\lceil {(r_A - r_I )x_{MAX} + \frac{z}{k} } \right\rceil } \right]_{\intset{}} ,} |

788 | \hfill & {r_A > r_I } \\ |

789 | \end{array}} \right. |

790 | \end{equation} |

791 | \end{figure*} |

792 | |

793 | With $z=0$, analogous results for $J(x)-I(x)$ |

794 | are obtained (\ref{eq:eq0018}). |

795 | |

796 | \begin{figure*} |

797 | \begin{equation} |

798 | \label{eq:eq0018} |

799 | \left. {J(x) - I(x)} \right|_{x \in [0,x_{MAX} ]_{\intset{}}} \in |

800 | \left\{ {\begin{array}{*{20}l} |

801 | {\left[ {\left\lceil {(r_A - r_I )x_{MAX} - \frac{{k - 1}}{k}} \right\rceil ,0} |

802 | \right]_{\intset{}} ,} \hfill & {r_A \le r_I - \frac{1}{{x_{MAX} k}}} \\ |

803 | \\ |

804 | {\{ 0\} ,} \hfill & {r_I - \frac{1}{{x_{MAX} k}} < r_A \le r_I } \\ |

805 | \\ |

806 | {\left[ {0,\left\lceil {(r_A - r_I )x_{MAX} } \right\rceil } \right]_{\intset{}} ,} |

807 | \hfill & {r_A > r_I } \\ |

808 | \end{array}} \right. |

809 | \end{equation} |

810 | \end{figure*} |

811 | |

812 | In practice, there are three useful choices of the |

813 | parameter $z$. (\ref{eq:eq0019}) |

814 | supplies the choice of $z$ which will assure that the |

815 | approximation error is never negative. (\ref{eq:eq0020}) supplies |

816 | the choice of $z$ which will assure that the approximation error |

817 | is never positive. (\ref{eq:eq0021}) |

818 | supplies the choice of $z$ which will |

819 | center the approximation error about zero. |

820 | |

821 | \begin{equation} |

822 | \label{eq:eq0019} |

823 | z_{NONEG} = \left\{ {\begin{array}{*{20}c} |

824 | {\left\lceil {(r_I - r_A )x_{MAX} k} \right\rceil ,} |

825 | \hfill & {} \hfill & {r_A < r_I } \hfill \\ |

826 | {0,} \hfill & {} \hfill & {r_A \ge r{}_I} \hfill \\ |

827 | \end{array}} \right. |

828 | \end{equation} |

829 | |

830 | \begin{equation} |

831 | \label{eq:eq0020} |

832 | z_{NOPOS} = \left\{ {\begin{array}{*{20}c} |

833 | {0,} \hfill & {} \hfill & {r_A \le r_I } \hfill \\ |

834 | {\left\lfloor {(r_I - r_A )x_{MAX} k} \right\rfloor ,} |

835 | \hfill & {} \hfill & {r_A > r{}_I} \hfill \\ |

836 | \end{array}} \right. |

837 | \end{equation} |

838 | |

839 | \begin{equation} |

840 | \label{eq:eq0021} |

841 | z_{CENTER} = \left\lfloor {\frac{{(r_I - r_A )x_{MAX} k}}{2}} \right\rfloor |

842 | \end{equation} |

843 | |

844 | \begin{example} |

845 | In a vehicle software load, vehicle speed |

846 | is received in network messages as |

847 | integral KPH, and is to be converted to MPH and |

848 | retransmitted over a second network as integral MPH. |

849 | If $r_{A}$=59/95$\approx$0.62105263 is used to approximate |

850 | $r_{I}\approx$ 0.6214 (the ideal conversion factor |

851 | from KPH to MPH), how much error might be introduced by |

852 | this rational approximation (vs. |

853 | retransmitting the quantized product of $r_I$ |

854 | and the received vehicle speed) for received |

855 | vehicle speeds up to 255 KPH? |

856 | \end{example} |

857 | |

858 | \emph{Solution:} In this example, |

859 | the domain is integral and the range |

860 | is integral, so (\ref{eq:eq0018}) |

861 | applies with $x_{MAX}=255$. |

862 | The first row of (\ref{eq:eq0018}) |

863 | predicts that the error |

864 | will always be in $[-1,0]_{\intset{}}$=\{-1,0\}, |

865 | so that the calculated integral |

866 | MPH may be up to one count less than |

867 | implied by $I(x)$ with $r_{I}=0.6214$. |

868 | |

869 | |

870 | |

871 | |

872 | % (3)(D)ERROR ANALYSIS OF {J(X),K(X)}-G(X) % |

873 | |

874 | |

875 | \subsection{Error Analysis Of $\{ J(x),K(x) \} - G(x)$ } |

876 | |

877 | Because (\ref{eq:eq0006}) is a special |

878 | case of (\ref{eq:eq0007}), |

879 | the difference function $K(x)-G(x)$ with $z=0$ |

880 | is $J(x)-G(x)$; hence |

881 | there is no need to derive $J(x)-G(x)$ |

882 | explicitly. |

883 | |

884 | \begin{equation} |

885 | \label{eq:eq0022} |

886 | K(x) - G(x) = \left\lfloor {\frac{{h\left\lfloor x \right\rfloor |

887 | + z}}{k}} \right\rfloor - r_I \left\lfloor x \right\rfloor |

888 | \end{equation} |

889 | |

890 | The inner \emph{floor($\cdot{}$)} |

891 | function of (\ref{eq:eq0022}) can be removed with the |

892 | understanding that the difference function will be |

893 | evaluated on a domain of |

894 | integers only (\ref{eq:eq0023}). |

895 | The difference |

896 | function (\ref{eq:eq0023}) is real |

897 | (not required to be rational or integral). |

898 | |

899 | \begin{equation} |

900 | \label{eq:eq0023} |

901 | K(x) - G(x) = \left\lfloor {\frac{{hx |

902 | + z}}{k}} \right\rfloor - r_I x;\quad x \in \intsetnonneg{} |

903 | \end{equation} |

904 | |

905 | The arguments which support the |

906 | derivation of (\ref{eq:eq0011}) through |

907 | (\ref{eq:eq0021}) also support the derivation |

908 | of (\ref{eq:eq0023}) through (\ref{eq:eq0030}). |

909 | (\ref{eq:eq0028}), (\ref{eq:eq0029}), and (\ref{eq:eq0030}) |

910 | supply choices of the parameter $z$ |

911 | which ensure that the difference |

912 | function is never negative, |

913 | never positive, and |

914 | centered about zero, respectively. |

915 | |

916 | \begin{figure*} |

917 | \begin{equation} |

918 | \label{eq:eq0024} |

919 | K(x) - G(x) \in |

920 | \left[ {(r_A - r_I )x + \frac{z}{k} - \frac{{k - 1}}{k},(r_A - r_I )x + |

921 | \frac{z}{k}} \right] |

922 | \end{equation} |

923 | \end{figure*} |

924 | |

925 | \begin{figure*} |

926 | \begin{equation} |

927 | \label{eq:eq0025} |

928 | \left. {K(x) - G(x)} \right|_{x \in [0,x_{MAX} ]_{\intset{}}} \in |

929 | \left\{ {\begin{array}{*{20}c} |

930 | {\left[ {(r_A - r_I )x_{MAX} + \frac{z}{k} - \frac{{k - 1}}{k},\frac{z}{k}} \right] ,} |

931 | \hfill & {r_A < r_I } \hfill \\ |

932 | \\ |

933 | {\left[ {\frac{z}{k} - \frac{{k - 1}}{k},\frac{z}{k}} \right] ,} \hfill & {r_A = r_I } |

934 | \hfill \\ |

935 | \\ |

936 | {\left[ {\frac{z}{k} - \frac{{k - 1}}{k},(r_A - r_I )x_{MAX} + \frac{z}{k}} \right] ,} |

937 | \hfill & {r_A > r_I } \hfill \\ |

938 | \end{array}} \right. |

939 | \end{equation} |

940 | \end{figure*} |

941 | |

942 | \begin{figure*} |

943 | \begin{equation} |

944 | \label{eq:eq0026} |

945 | J(x) - G(x) \in |

946 | \left[ {(r_A - r_I )x - \frac{{k - 1}}{k},(r_A - r_I )x} \right] |

947 | \end{equation} |

948 | \end{figure*} |

949 | |

950 | \begin{figure*} |

951 | \begin{equation} |

952 | \label{eq:eq0027} |

953 | \left. {J(x) - G(x)} \right|_{x \in [0,x_{MAX} ]_{\intset{}}} \in |

954 | \left\{ {\begin{array}{*{20}c} |

955 | {\left[ {(r_A - r_I )x_{MAX} - \frac{{k - 1}}{k},0} \right] ,} \hfill & {r_A < r_I } |

956 | \hfill \\ |

957 | \\ |

958 | {\left[ { - \frac{{k - 1}}{k},0} \right] ,} \hfill & {r_A = r_I } \hfill \\ |

959 | \\ |

960 | {\left[ { - \frac{{k - 1}}{k},(r_A - r_I )x_{MAX} } \right] ,} \hfill & {r_A > r_I } |

961 | \hfill \\ |

962 | \end{array}} \right. |

963 | \end{equation} |

964 | \end{figure*} |

965 | |

966 | \begin{figure*} |

967 | \begin{equation} |

968 | \label{eq:eq0028} |

969 | z_{NONEG} = \left\{ {\begin{array}{ll} |

970 | {\left\lceil {(r_I - r_A )x_{MAX} k + k - 1} \right\rceil ,} & {r_A < r_I } \\ |

971 | & \\ |

972 | {k-1,} \hfill & {r_A \ge r{}_I} \\ |

973 | \end{array}} \right. |

974 | \end{equation} |

975 | \end{figure*} |

976 | |

977 | \begin{equation} |

978 | \label{eq:eq0029} |

979 | z_{NOPOS} = \left\{ {\begin{array}{*{20}c} |

980 | {0,} \hfill & {} \hfill & {r_A \le r_I } \hfill \\ |

981 | {\left\lfloor {(r_I - r_A )x_{MAX} k} \right\rfloor ,} \hfill & {} \hfill & {r_A > r{}_I} |

982 | \hfill \\ |

983 | \end{array}} \right. |

984 | \end{equation} |

985 | |

986 | \begin{equation} |

987 | \label{eq:eq0030} |

988 | z_{CENTER} = \left\lfloor {\frac{{(r_I - r_A )x_{MAX} k + k}}{2}} \right\rfloor |

989 | \end{equation} |

990 | |

991 | |

992 | |

993 | % (3)(E)ERROR ANALYSIS OF {J(X),K(X)}-H(X) % |

994 | |

995 | |

996 | \subsection{Error Analysis Of $ \{ J(x),K(x) \} - H(x)$} |

997 | |

998 | Because (\ref{eq:eq0006}) is a special case of (\ref{eq:eq0007}), |

999 | the difference function $K(x)-H(x)$ with $z=0$ |

1000 | is $J(x)-H(x)$; hence there is no |

1001 | need to derive $J(x)-H(x)$ explicitly. |

1002 | |

1003 | \begin{equation} |

1004 | \label{eq:eq0037} |

1005 | K(x) - H(x) = \left\lfloor {\frac{{h\left\lfloor x \right\rfloor |

1006 | + z}}{k}} \right\rfloor - \left\lfloor {r_I x} \right\rfloor |

1007 | \end{equation} |

1008 | |

1009 | (\ref{eq:eq0037}) corresponds to the |

1010 | approximation error introduced when a function with |

1011 | a real domain and integral range is approximated using a |

1012 | function with an integral domain and range. The error |

1013 | term supplied by (\ref{eq:eq0037}) is integral. |

1014 | |

1015 | The three quantizations in (\ref{eq:eq0037}) can be treated |

1016 | by introducing $\varepsilon_{1}$, $\varepsilon_{2}$, and $\varepsilon_{3}$ |

1017 | (\ref{eq:eq0038}). |

1018 | |

1019 | \begin{figure*} |

1020 | \begin{equation} |

1021 | \label{eq:eq0038} |

1022 | K(x) - H(x) = \frac{{h(x - \varepsilon _1 ) + z}}{k} - \varepsilon _2 - r_I x + \varepsilon _3 |

1023 | ; \;\; |

1024 | \varepsilon _1 \in [0,1) |

1025 | ; \;\; |

1026 | \varepsilon _2 \in \left[ {0,\frac{{k - 1}}{k}} \right] |

1027 | ; \;\; |

1028 | \varepsilon _3 \in [0,1) |

1029 | \end{equation} |

1030 | \end{figure*} |

1031 | |

1032 | Evaluating (\ref{eq:eq0038}) at the |

1033 | extremes of $\varepsilon_{1}$, |

1034 | $\varepsilon_{2}$, |

1035 | and $\varepsilon_{3}$ leads |

1036 | to (\ref{eq:eq0042}). |

1037 | |

1038 | \begin{figure*} |

1039 | \begin{equation} |

1040 | \label{eq:eq0042} |

1041 | K(x) - H(x) \in |

1042 | \left( {(r_A - r_I )x - r_A + \frac{z}{k} - \frac{{k - 1}}{k},(r_A - r_I )x + |

1043 | \frac{z}{k} + 1} \right) |

1044 | \end{equation} |

1045 | \end{figure*} |

1046 | |

1047 | Intersection of (\ref{eq:eq0042}) with the set |

1048 | of integers leads to (\ref{eq:eq0042b}). |

1049 | |

1050 | \begin{figure*} |

1051 | \begin{equation} |

1052 | \label{eq:eq0042b} |

1053 | K(x) - H(x) \in |

1054 | { |

1055 | \left[ |

1056 | { |

1057 | { |

1058 | \left\lfloor |

1059 | { |

1060 | (r_A - r_I) x - r_A + \frac{z}{k} + \frac{1}{k} |

1061 | } |

1062 | \right\rfloor |

1063 | } |

1064 | , |

1065 | { |

1066 | \left\lceil |

1067 | { |

1068 | (r_A - r_I) x + \frac{z}{k} |

1069 | } |

1070 | \right\rceil |

1071 | } |

1072 | } |

1073 | \right] |

1074 | }_{\intset{}} |

1075 | \end{equation} |

1076 | \end{figure*} |

1077 | |

1078 | Evaluating (\ref{eq:eq0042b}) at the |

1079 | extremes of $[0,x_{MAX}]$ |

1080 | yields (\ref{eq:eq0043}). With $z=0$, (\ref{eq:eq0043}) |

1081 | supplies $J(x) - H(x)$ (Eq. \ref{eq:eq0044}). |

1082 | |

1083 | \begin{figure*} |

1084 | \begin{equation} |

1085 | \label{eq:eq0043} |

1086 | \left. {K(x) - H(x)} \right|_{x \in [0,x_{MAX} ] } \in |

1087 | \left\{ {\begin{array}{*{20}l} |

1088 | {\left[ {\left\lfloor {(r_A - r_I )x_{MAX} - r_A + \frac{z}{k} + \frac{1}{k}} |

1089 | \right\rfloor ,\left\lceil {\frac{z}{k}} \right\rceil } \right] _{\intset{}} ,} |

1090 | \hfill & {r_A < r_I } \\ |

1091 | \\ |

1092 | {\left[ {\left\lfloor { - r_A + \frac{z}{k} + \frac{1}{k}} \right\rfloor , |

1093 | \left\lceil {\frac{z}{k}} \right\rceil } \right] _{\intset{}} ,} |

1094 | \hfill & {r_A = r_I }\\ |

1095 | \\ |

1096 | {\left[ {\left\lfloor { - r_A + \frac{z}{k} + \frac{1}{k}} \right\rfloor , |

1097 | \left\lceil {(r_A - r_I )x_{MAX} + \frac{z}{k}} \right\rceil } \right] _{\intset{}},} |

1098 | \hfill & {r_A > r_I } \\ |

1099 | \end{array}} \right. |

1100 | \end{equation} |

1101 | \end{figure*} |

1102 | |

1103 | \begin{figure*} |

1104 | \begin{equation} |

1105 | \label{eq:eq0044} |

1106 | \left. {J(x) - H(x)} \right|_{x \in [0,x_{MAX} ] } \in |

1107 | \left\{ {\begin{array}{*{20}l} |

1108 | {\left[ {\left\lfloor {(r_A - r_I )x_{MAX} - r_A + \frac{1}{k}} |

1109 | \right\rfloor , 0 } \right] _{\intset{}} ,} |

1110 | \hfill & {r_A < r_I } \\ |

1111 | \\ |

1112 | {\left[ {\left\lfloor { - r_A + \frac{1}{k}} \right\rfloor , |

1113 | { 0 } } \right] _{\intset{}} ,} |

1114 | \hfill & {r_A = r_I }\\ |

1115 | \\ |

1116 | {\left[ {\left\lfloor { - r_A + \frac{1}{k}} \right\rfloor , |

1117 | \left\lceil {(r_A - r_I )x_{MAX}} \right\rceil } \right] _{\intset{}},} |

1118 | \hfill & {r_A > r_I } \\ |

1119 | \end{array}} \right. |

1120 | \end{equation} |

1121 | \end{figure*} |

1122 | |

1123 | (\ref{eq:eq0044a}), (\ref{eq:eq0044b}), and (\ref{eq:eq0044c}) |

1124 | supply choices of the parameter $z$ which |

1125 | ensure that the difference function is never negative, |

1126 | never positive, and centered about zero, respectively. |

1127 | |

1128 | \begin{figure*} |

1129 | \begin{equation} |

1130 | \label{eq:eq0044a} |

1131 | z_{NONEG} = \left\{ {\begin{array}{ll} |

1132 | {\left\lceil {(r_I - r_A )x_{MAX} k + r_A k - 1} \right\rceil ,} & {r_A < r_I } \\ |

1133 | & \\ |

1134 | {\lceil r_A k-1 \rceil ,} \hfill & {r_A \ge r_I} \\ |

1135 | \end{array}} \right. |

1136 | \end{equation} |

1137 | \end{figure*} |

1138 | |

1139 | \begin{equation} |

1140 | \label{eq:eq0044b} |

1141 | z_{NOPOS} = \left\{ {\begin{array}{*{20}c} |

1142 | {0,} \hfill & {} \hfill & {r_A \le r_I } \hfill \\ |

1143 | {\left\lfloor {(r_I - r_A )x_{MAX} k} \right\rfloor ,} \hfill & {} \hfill & {r_A > r{}_I} |

1144 | \hfill \\ |

1145 | \end{array}} \right. |

1146 | \end{equation} |

1147 | |

1148 | \begin{equation} |

1149 | \label{eq:eq0044c} |

1150 | z_{CENTER} |

1151 | = |

1152 | \left\lfloor {\frac{{(r_I - r_A )x_{MAX} k + r_A k}}{2}} \right\rfloor |

1153 | \end{equation} |

1154 | |

1155 | |

1156 | |

1157 | |

1158 | % (3)(F)ERROR ANALYSIS OF {J(X),K(X)}-F(X) % |

1159 | |

1160 | |

1161 | \subsection{Error Analysis Of $ \{ J(x), K(x) \} - F(x)$} |

1162 | |

1163 | Because (\ref{eq:eq0006}) is a special case of (\ref{eq:eq0007}), |

1164 | the difference function $K(x)-F(x)$ with $z=0$ is |

1165 | $J(x)-F(x)$; hence there is no |

1166 | need to derive $J(x)-F(x)$ explicitly. |

1167 | |

1168 | \begin{equation} |

1169 | \label{eq:eq0031} |

1170 | K(x) - F(x) = \left\lfloor {\frac{{h\left\lfloor x \right\rfloor |

1171 | + z}}{k}} \right\rfloor - r_I x |

1172 | \end{equation} |

1173 | |

1174 | (\ref{eq:eq0031}) corresponds to the approximation |

1175 | error introduced when a function with a |

1176 | real domain and range is approximated |

1177 | using a function with an integral domain and range. |

1178 | The error term supplied by (\ref{eq:eq0031}) |

1179 | is real rather than integral. |

1180 | |

1181 | The two quantizations in (\ref{eq:eq0031}) |

1182 | can be treated by introducing $\varepsilon_{1}$ |

1183 | and $\varepsilon_{2}$ (\ref{eq:eq0032}). |

1184 | |

1185 | \begin{figure*} |

1186 | \begin{equation} |

1187 | \label{eq:eq0032} |

1188 | K(x) - F(x) = \frac{{h(x - \varepsilon _1 ) + z}}{k} - \varepsilon _2 - r_I x |

1189 | ; \; |

1190 | \varepsilon _1 \in [0,1) |

1191 | ; \; |

1192 | \varepsilon _2 \in \left[ {0,\frac{{k - 1}}{k}} \right] |

1193 | \end{equation} |

1194 | \end{figure*} |

1195 | |

1196 | Choosing the extremes of |

1197 | $\varepsilon_{1}$ and $\varepsilon_{2}$ |

1198 | so as to minimize and maximize the difference |

1199 | function bounds the approximation error (\ref{eq:eq0035}). |

1200 | |

1201 | \begin{figure*} |

1202 | \begin{equation} |

1203 | \label{eq:eq0035} |

1204 | K(x) - F(x) \in |

1205 | \left( {(r_A - r_I )x - r_A + \frac{z}{k} - \frac{{k - 1}}{k},(r_A - r_I )x + |

1206 | \frac{z}{k}} \right] |

1207 | \end{equation} |

1208 | \end{figure*} |

1209 | |

1210 | Minimizing and maximizing (\ref{eq:eq0035}) over |

1211 | a domain of $[0,x_{MAX}]$ gives (\ref{eq:eq0035b}). With |

1212 | $z=0$, (\ref{eq:eq0035b}) supplies $J(x)-F(x)$ (Eq. \ref{eq:eq0036}). |

1213 | |

1214 | |

1215 | \begin{figure*} |

1216 | \begin{equation} |

1217 | \label{eq:eq0035b} |

1218 | \left. {K(x) - F(x)} \right|_{x \in [0,x_{MAX} ]} \in |

1219 | \left\{ {\begin{array}{*{20}c} |

1220 | {\left( {(r_A - r_I )x_{MAX} - r_A + \frac{z}{k }- \frac{{k - 1}}{k}, \frac{z}{k}} \right],} |

1221 | \hfill & {r_A < r_I } \hfill \\ |

1222 | \\ |

1223 | {\left( { - r_A + \frac{z}{k} - \frac{{k - 1}}{k}, \frac{z}{k}} \right],} \hfill & {r_A = r_I } \hfill \\ |

1224 | \\ |

1225 | {\left( { - r_A + \frac{z}{k} - \frac{{k - 1}}{k},(r_A - r_I )x_{MAX} + \frac{z}{k}} \right] ,} |

1226 | \hfill & {r_A > r_I } \hfill \\ |

1227 | \end{array}} \right. |

1228 | \end{equation} |

1229 | \end{figure*} |

1230 | |

1231 | |

1232 | \begin{figure*} |

1233 | \begin{equation} |

1234 | \label{eq:eq0036} |

1235 | \left. {J(x) - F(x)} \right|_{x \in [0,x_{MAX} ]} \in |

1236 | \left\{ {\begin{array}{*{20}c} |

1237 | {\left( {(r_A - r_I )x_{MAX} - r_A - \frac{{k - 1}}{k},0} \right],} |

1238 | \hfill & {r_A < r_I } \hfill \\ |

1239 | \\ |

1240 | {\left( { - r_A - \frac{{k - 1}}{k},0} \right],} \hfill & {r_A = r_I } \hfill \\ |

1241 | \\ |

1242 | {\left( { - r_A - \frac{{k - 1}}{k},(r_A - r_I )x_{MAX} } \right] ,} |

1243 | \hfill & {r_A > r_I } \hfill \\ |

1244 | \end{array}} \right. |

1245 | \end{equation} |

1246 | \end{figure*} |

1247 | |

1248 | (\ref{eq:eqkminusfzterm01}), |

1249 | (\ref{eq:eqkminusfzterm02}), and |

1250 | (\ref{eq:eqkminusfzterm03}) supply choices of the |

1251 | parameter $z$ which ensure that the difference function |

1252 | is never negative, never positive, and centered |

1253 | about zero, respectively. |

1254 | |

1255 | \begin{figure*} |

1256 | \begin{equation} |

1257 | \label{eq:eqkminusfzterm01} |

1258 | z_{NONEG} = \left\{ {\begin{array}{ll} |

1259 | {\left\lceil {(r_I - r_A) x_{MAX} k + r_A k + k - 1} \right\rceil ,} & {r_A < r_I } \\ |

1260 | & \\ |

1261 | {\left\lceil {r_A k + k - 1} \right\rceil ,} & {r_A \ge r{}_I}\\ |

1262 | \end{array}} \right. |

1263 | \end{equation} |

1264 | \end{figure*} |

1265 | |

1266 | \begin{equation} |

1267 | \label{eq:eqkminusfzterm02} |

1268 | z_{NOPOS} = \left\{ {\begin{array}{*{20}c} |

1269 | {0,} \hfill & {} \hfill & {r_A \le r_I } \hfill \\ |

1270 | {\left\lfloor {(r_I - r_A )x_{MAX} k} \right\rfloor ,} |

1271 | \hfill & {} \hfill & {r_A > r{}_I} \hfill \\ |

1272 | \end{array}} \right. |

1273 | \end{equation} |

1274 | |

1275 | \begin{equation} |

1276 | \label{eq:eqkminusfzterm03} |

1277 | z_{CENTER} |

1278 | = |

1279 | \left\lfloor {\frac{{(r_I - r_A )x_{MAX} k + r_A k + k}}{2}} \right\rfloor |

1280 | \end{equation} |

1281 | |

1282 | |

1283 | |

1284 | |

1285 | % (4) METHODS OF CHOOSING H AND K TO MATCH R_I WITH AN R_A % |

1286 | |

1287 | |

1288 | \section{Methods Of Choosing $h$ And $k$} |

1289 | \label{sec:methodshkchoose} |

1290 | |

1291 | |

1292 | |

1293 | |

1294 | % (4)(A)INTRODUCTION TO THE SECTION, GENERAL REMARKS % |

1295 | |

1296 | |

1297 | In this section, algorithms for choosing |

1298 | $h$ and $k$ subject to the constraints $h \leq h_{MAX}$ and |

1299 | $k \leq k_{MAX}$ in order to place $r_{A}=h/k$ |

1300 | close to $r_{I}$ are presented. The algorithms are presented |

1301 | in order of increasing sophistication |

1302 | (and efficiency).\footnote{Although |

1303 | it won't be shown in this paper, |

1304 | if $N = k_{MAX}$ is the maximum allowable denominator, |

1305 | Algorithm \ref{alg:algstartingatint} |

1306 | is $O(N^2)$, |

1307 | Algorithm \ref{alg:algstartingatprime} is |

1308 | $O(N)$, and the continued fraction |

1309 | algorithm is $O(log N)$.} |

1310 | |

1311 | |

1312 | |

1313 | |

1314 | |

1315 | |

1316 | |

1317 | % (4)(C)FAREY SERIES AND RELATED THEOREMS) % |

1318 | |

1319 | |

1320 | \subsection{Farey Series Methods Of Choosing $h$ And $k$} |

1321 | |

1322 | The \emph{Farey series |

1323 | of order $N$}, denoted $F_{N}$, |

1324 | is the ordered set of all irreducible |

1325 | rational numbers $h/k$ in the interval |

1326 | [0,1] |

1327 | with a denominator $k\leq k_{MAX}$. |

1328 | As an example, the Farey series of |

1329 | order 5, $F_5$, is shown in (\ref{eq:eq0045}). |

1330 | |

1331 | \begin{equation} |

1332 | \label{eq:eq0045} |

1333 | F_5 = \left\{ {\frac{0}{1},\frac{1}{5},\frac{1}{4}, |

1334 | \frac{1}{3},\frac{2}{5},\frac{1}{2}, |

1335 | \frac{3}{5},\frac{2}{3},\frac{3}{4}, |

1336 | \frac{4}{5},\frac{1}{1}} \right\} |

1337 | \end{equation} |

1338 | |

1339 | The distribution of Farey rational numbers in |

1340 | [0,1] is repeated |

1341 | in any |

1342 | $[n,n+1]$, $n\in \intset$; so that the distribution of |

1343 | Farey rationals in [0,1] supplies complete |

1344 | information about the distribution in |

1345 | all of $\realset$.\footnote{We |

1346 | occasionally abuse the proper nomenclature by referring |

1347 | to sequential rational numbers outside the |

1348 | interval [0,1] as Farey terms or as part of |

1349 | $F_N$, which, technically, they are not. |

1350 | All of the results presented in |

1351 | this paper can be shown to apply |

1352 | everywhere in $\realset$, so this abuse |

1353 | is not harmful.} |

1354 | |

1355 | \begin{theorem} |

1356 | \label{thm:thm01} |

1357 | If $H/K$ and $h/k$ are two successive terms of $F_{N}$, |

1358 | then: |

1359 | \end{theorem} |

1360 | |

1361 | \begin{equation} |

1362 | \label{eq:eq0048} |

1363 | K h - H k = 1 |

1364 | \end{equation} |

1365 | |

1366 | \emph{Note:} This condition is necessary but not |

1367 | sufficient for $h/k$ to be the Farey successor of $H/K$. |

1368 | In general, there is |

1369 | more than one $h/k$ with $k \leq k_{MAX}$ such that $Kh - Hk = 1$. |

1370 | |

1371 | \begin{proof} |

1372 | See \cite{HardyAndWrightClassic} p.23, \cite{LeVeque} p.222. |

1373 | \end{proof} |

1374 | |

1375 | \begin{theorem} |

1376 | \label{thm:thm03} |

1377 | If $H/K$ and $h/k$ are two successive terms of $F_{N}$, then: |

1378 | \end{theorem} |

1379 | |

1380 | \begin{equation} |

1381 | \label{eq:eq0050} |

1382 | K + k > N |

1383 | \end{equation} |

1384 | |

1385 | \emph{Note:} This condition is necessary but not |

1386 | sufficient for $h/k$ to be the Farey successor of $H/K$. |

1387 | |

1388 | \begin{proof} |

1389 | See \cite{HardyAndWrightClassic} p.23. |

1390 | \end{proof} |

1391 | |

1392 | \begin{theorem} |

1393 | \label{thm:thm04} |

1394 | If $h_{j-2}/k_{j-2}$, $h_{j-1}/k_{j-1}$, and $h_{j}/k_{j}$ |

1395 | are three consecutive terms of $F_{N}$, then: |

1396 | \end{theorem} |

1397 | |

1398 | \begin{equation} |

1399 | \label{eq:eq0051} |

1400 | h_{j} = \left\lfloor {\frac{{k_{j-2} |

1401 | + N}}{{k_{j - 1} }}} \right\rfloor h_{j - 1} - h_{j-2} |

1402 | \end{equation} |

1403 | |

1404 | \begin{equation} |

1405 | \label{eq:eq0052} |

1406 | k_{j} = \left\lfloor {\frac{{k_{j-2} + N}}{{k_{j |

1407 | - 1} }}} \right\rfloor k_{j - 1} - k_{j-2} |

1408 | \end{equation} |

1409 | |

1410 | \emph{Notes:} (1)Theorem \ref{thm:thm04} gives |

1411 | recursive formulas for |

1412 | generating successive terms in $F_N$ |

1413 | if two consecutive terms are known. |

1414 | (2)Equations (\ref{eq:eq0051}) and |

1415 | (\ref{eq:eq0052}) can be solved to |

1416 | allow generation of terms in the decreasing direction |

1417 | (\ref{eq:eq0053}, \ref{eq:eq0054}). |

1418 | |

1419 | \begin{equation} |

1420 | \label{eq:eq0053} |

1421 | h_j = \left\lfloor {\frac{{k_{j + 2} + N}}{{k_{j + 1} }}} \right\rfloor h_{j + 1} - h_{j + 2} |

1422 | \end{equation} |

1423 | |

1424 | \begin{equation} |

1425 | \label{eq:eq0054} |

1426 | k_j = \left\lfloor {\frac{{k_{j + 2} + N}}{{k_{j + 1} }}} \right\rfloor k_{j + 1} - k_{j + 2} |

1427 | \end{equation} |

1428 | |

1429 | \begin{proof} |

1430 | See \cite{SchroederClassic} p.83. |

1431 | \end{proof} |

1432 | |

1433 | In general, given only a single irreducible rational number $h/k$, |

1434 | there is no method to find the immediate |

1435 | predecessor or successor in $F_N$ without some |

1436 | iteration (Eqns. \ref{eq:eq0051}, |

1437 | \ref{eq:eq0052}, |

1438 | \ref{eq:eq0053}, and \ref{eq:eq0054} require |

1439 | two successive elements). However, if the |

1440 | irreducible rational number is an integer $i=i/1$, the |

1441 | predecessor and successor in $F_N$ are $(i N - 1)/N$ and |

1442 | $(i N + 1)/N$, so it is convenient to build $F_N$ |

1443 | in either direction starting |

1444 | at an integer. This suggests an algorithm for |

1445 | finding the closest rational numbers in |

1446 | $F_N$ to an $r_I$ when $N$ is small. |

1447 | |

1448 | \begin{algorithm}\label{alg:algstartingatint}\end{algorithm} |

1449 | \begin{alglvl0} |

1450 | \item Choose an integer $i$ as either |

1451 | $\lfloor{}r_I\rfloor$ or $\lceil{}r_I\rceil$. |

1452 | \item If $i=\lfloor{}r_I\rfloor$ is chosen, use |

1453 | $h_{j-2}/k_{j-2} = i/1$, $h_{j-1}/k_{j-1} = (i N + 1)/N$ |

1454 | and use (\ref{eq:eq0051}) and (\ref{eq:eq0052}) |

1455 | to build successive increasing |

1456 | terms in $F_N$ until |

1457 | the terms which enclose $r_I$ are found. |

1458 | If $i=\lceil{}r_I\rceil$ is chosen, use |

1459 | $h_{j+2}/k_{j+2} = i/1$, $h_{j+1}/k_{j+1} = (i N - 1)/N$ |

1460 | and use (\ref{eq:eq0053}) |

1461 | and (\ref{eq:eq0054}) to build successive |

1462 | decreasing terms in $F_N$ until |

1463 | the terms which enclose $r_I$ are |

1464 | found.\footnote{This procedure is easily carried |

1465 | out with spreadsheet software, such as |

1466 | \emph{Microsoft Excel}.} |

1467 | \end{alglvl0} |

1468 | |

1469 | The following additional theorem is presented, |

1470 | which can be useful in finding the next term |

1471 | of $F_N$ given only a single term. |

1472 | |

1473 | \begin{theorem} |

1474 | \label{thm:thm05} |

1475 | If $H/K$ is a term of $F_{N}$, |

1476 | the immediate successor of $H/K$ |

1477 | in $F_{N}$ is the $h/k$ satisfying |

1478 | $Kh-Hk=1$ with the largest |

1479 | denominator $k\leq N$. |

1480 | \end{theorem} |

1481 | |

1482 | \begin{proof} |

1483 | Any potential successor of $H/K$ |

1484 | which meets $Kh-Hk=1$ can be formed |

1485 | by adding $1/Kk$ to $H/K$ |

1486 | (\ref{eq:eq0055}, \ref{eq:eq0056}). |

1487 | |

1488 | \begin{eqnarray} |

1489 | \label{eq:eq0055} |

1490 | & Kh - Hk = 1 & \\ |

1491 | & \Downarrow & \nonumber \\ |

1492 | \label{eq:eq0056} |

1493 | & \displaystyle {\frac{h}{k} = \frac{{1 + Hk}}{{Kk}} = \frac{H}{K} + \frac{1}{{Kk}}} & |

1494 | \end{eqnarray} |

1495 | |

1496 | If $h/k$ and $h'/k'$ both |

1497 | satisfy $Kh-Hk=1$ with $k'<k\leq{}N$, then |

1498 | $H/K<h/k<h'/k'$. Thus the $h/k$ |

1499 | with the largest denominator $\leq N$ |

1500 | that meets $Kh-Hk=1$ is the successor |

1501 | in $F_{N}$ to $H/K$. |

1502 | \end{proof} |

1503 | |

1504 | |

1505 | |

1506 | % (4)(D)ALGORITHM 1: BUILD F_N AND SURROUND R_I % |

1507 | |

1508 | |

1509 | |

1510 | |

1511 | |

1512 | |

1513 | |

1514 | |

1515 | % (4)(E)ALGORITHM 2: BUILD F_N STARTING AT P/K_MAX % |

1516 | |

1517 | |

1518 | Finding the Farey successor from a single Farey |

1519 | term $\notin \intset{}$ |

1520 | is labor-intensive and not easily done |

1521 | without a computer for even moderate $N$. |

1522 | Theorems \ref{thm:thm01}, \ref{thm:thm03}, |

1523 | and \ref{thm:thm05} outline a computationally |

1524 | tractable way (Algorithm \ref{alg:algstartingatprime}) |

1525 | to use a computer to |

1526 | form the successor in $F_{N}$ given |

1527 | only a single Farey term, even for large $N$. |

1528 | Once two successive Farey terms are known, |

1529 | Theorem \ref{thm:thm04} can be applied to |

1530 | generate additional terms at low cost. |

1531 | Algorithm \ref{alg:algstartingatprime} |

1532 | below outlines a method to |

1533 | economically find Farey terms on the left |

1534 | and right of a real number. |

1535 | |

1536 | \begin{algorithm}\label{alg:algstartingatprime}\end{algorithm} |

1537 | \begin{alglvl0} |

1538 | \item Choose a prime number $\alpha\ll N$. $\alpha$ is |

1539 | the number of denominators that a computer |

1540 | can test against $Kh-Hk=1$ in a practical period of |

1541 | time.\footnote{Useful primes at each order of |

1542 | magnitude are 11; 101; 1,009; 10,007; |

1543 | 100,003; 1,000,003; and 10,000,019.} |

1544 | \item Choose a rational number $h'/\alpha$ to the left of $r_{I}$ |

1545 | ($h'=\lfloor r_{I}\alpha\rfloor$ is usually a good choice). |

1546 | \item Because $\alpha$ is prime, |

1547 | $h'/\alpha$ is not reducible unless |

1548 | $h'/\alpha$ is an integer. |

1549 | \item Denote the Farey term succeeding $h'/\alpha$ as $h/k$. |

1550 | Theorem \ref{thm:thm03} asserts |

1551 | that $\alpha +k>N$, implying that |

1552 | $k>N-\alpha$. |

1553 | \item Apply Theorems \ref{thm:thm01} and \ref{thm:thm05}. |

1554 | Search downward |

1555 | from $k=N$ to $k=N-\alpha +1$ for an $h/k$ which satisfies |

1556 | Theorem \ref{thm:thm01}. |

1557 | This will require at most $\alpha$ iterations. |

1558 | \item $h'/\alpha$ and $h/k$ are now known to be successive Farey |

1559 | terms in $F_N$ to the left of $r_I$. |

1560 | Theorem \ref{thm:thm04} can be employed to economically |

1561 | generate successive Farey terms until $r_I$ is enclosed. |

1562 | \end{alglvl0} |

1563 | |

1564 | |

1565 | |

1566 | |

1567 | |

1568 | % (4)(F)FRAMEWORK OF CONTINUED FRACTIONS % |

1569 | |

1570 | |

1571 | |

1572 | |

1573 | |

1574 | |

1575 | % (4)(F)(i)DEFINITION OF A CONTINUED FRACTION % |

1576 | |

1577 | |

1578 | \subsection{Continued Fraction Methods Of Choosing $h$ And $k$} |

1579 | |

1580 | For selection of a suitable rational number from $F_N$ when |

1581 | $N$ is a few hundred or less, building $F_N$ |

1582 | starting at an integer (Algorithm \ref{alg:algstartingatint}) |

1583 | or at a rational number with a large |

1584 | prime denominator (Algorithm \ref{alg:algstartingatprime}) |

1585 | are practical techniques.\footnote{\label{footnote:exceldaveashleyfootnote}\emph{Microsoft Excel}, |

1586 | which maintains |

1587 | integers with 48 bits of precision, can be used to |

1588 | build $F_N$ and select a suitable rational number |

1589 | for at least $N \approx 2^{24}$. (Multiplying |

1590 | two 24-bit numbers yields a 48-bit result, and so \emph{Excel} |

1591 | should be usable until at least order $\approx 2^{24}$.)} |

1592 | However, the number of elements of $F_N$ is approximately |

1593 | $3N^2/\pi^2$; and so for large $N$, $\realset{}$ is |

1594 | too dense with Farey rationals to economically search. |

1595 | |

1596 | A more direct algorithm for locating |

1597 | the Farey neighbors of an arbitrary real |

1598 | $r_I$ |

1599 | comes from the study of \emph{continued fractions} |

1600 | (a topic in number theory). |

1601 | |

1602 | A \emph{finite simple continued fraction} is a fraction in the form |

1603 | of (\ref{eq:eq0057}), where $a_0 \in \intsetnonneg$ |

1604 | and $a_{k} \in \intsetpos$ for $k > 0$. A continued fraction |

1605 | in the form of (\ref{eq:eq0057}) is denoted $[a_0; a_1, a_2, \ldots, a_n]$. |

1606 | |

1607 | \begin{figure*} |

1608 | \begin{equation} |

1609 | \label{eq:eq0057} |

1610 | a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 |

1611 | + \cfrac{1}{\;\;\;\;\;\;\;\;\;\;\;\;\;\;\ldots + \cfrac{1}{a_n}}}} |

1612 | = |

1613 | [a_0; a_1, a_2, \ldots , a_n] |

1614 | \end{equation} |

1615 | \end{figure*} |

1616 | |

1617 | Continued fractions provide an alternate apparatus for |

1618 | representing real numbers. The form of (\ref{eq:eq0057}) has |

1619 | important properties which are presented without proof. |

1620 | |

1621 | \begin{propenum} |

1622 | \item Every rational number can be represented by a finite |

1623 | simple continued fraction $[a_{0};a_{1},a_{2},\ldots{} ,a_{n}]$. |

1624 | \item Each unique $[a_{0};a_{1},a_{2},\ldots{} ,a_{n}]$ corresponds to a |

1625 | uniquely valued rational number, so long as |

1626 | $a_{n}\neq 1$.\footnote{If $a_n=1$, the continued fraction |

1627 | can be reduced in order by |

1628 | one, and $a_{n-1}$ can be increased by one while |

1629 | still preserving the value of the continued fraction. |

1630 | The restriction that the |

1631 | final element $a_n \neq 1$ is necessary to guarantee that |

1632 | each uniquely valued |

1633 | rational number has a unique finite simple continued fraction |

1634 | representation.} |

1635 | \end{propenum} |

1636 | |

1637 | |

1638 | |

1639 | % (4)(F)(ii) ALGORITHM 3: FORMING A CONTINUED FRACTION FROM AN IRRATIONAL NUMBER % |

1640 | |

1641 | |

1642 | |

1643 | |

1644 | |

1645 | |

1646 | |

1647 | % (4)(F)(iii) ALGORITHM 4: FORMING A CONTINUED FRACTION FROM A RATIONAL NUMBER % |

1648 | |

1649 | |

1650 | Without proof, we present the following procedure for |

1651 | finding the continued fraction representation of an arbitrary |

1652 | non-negative rational number $a/b$. |

1653 | |

1654 | \begin{algorithm}\label{alg:akgenalg}\end{algorithm} |

1655 | \begin{alglvl0} |

1656 | \item Start with $k=0$, dividend=$a$, divisor=$b$. |

1657 | |

1658 | \item Repeat |

1659 | |

1660 | \begin{alglvl1} |

1661 | \item Carry out the division of dividend/divisor to form an |

1662 | integer quotient $a_k$ and an integer remainder. |

1663 | |

1664 | \item The divisor from the current iteration becomes the dividend |

1665 | for the next iteration, and the remainder from the current |

1666 | iteration becomes the divisor for the next iteration. |

1667 | |

1668 | \item Increment $k$. |

1669 | |

1670 | \end{alglvl1} |

1671 | |

1672 | \item Until (remainder is zero). |

1673 | \end{alglvl0} |

1674 | |

1675 | Without proof, we present the following properties of |

1676 | Algorithm \ref{alg:akgenalg}. |

1677 | |

1678 | \begin{propenum} |

1679 | \item The algorithm will produce the same continued |

1680 | fraction representation $[a_{0};a_{1},a_{2},\ldots{} ,a_{n}]$ |

1681 | for any $(ia)/(ib)$, $i \in \intsetpos{}$, i.e. |

1682 | the rational number $a/b$ need not be reduced before |

1683 | applying the algorithm. |

1684 | \item The algorithm will always terminate (i.e. the |

1685 | continued fraction representation |

1686 | $[a_{0};a_{1},a_{2},\ldots{} ,a_{n}]$ will be |

1687 | finite). |

1688 | \item The last non-zero remainder will be the greatest |

1689 | common divisor of $a$ and $b$.% |

1690 | { } |

1691 | \end{propenum} |

1692 | |

1693 | \begin{example} |

1694 | Find the continued fraction representation |

1695 | of $a/b$=3,362,997/2,924,082. |

1696 | \end{example} |

1697 | |

1698 | \emph{Solution:} Table \ref{tbl:cfexplrgratnum01} shows the application of |

1699 | Algorithm \ref{alg:akgenalg} |

1700 | to form the continued fraction representation of |

1701 | $a/b$. |

1702 | |

1703 | \begin{table} |

1704 | \caption{Continued Fraction Representation Of $3,362,997/2,924,082$} |

1705 | \label{tbl:cfexplrgratnum01} |

1706 | \begin{center} |

1707 | \begin{tabular}{|c|c|c|c|c|} |

1708 | \hline |

1709 | Index (k) & Dividend & Divisor & $a_{k}$ & Remainder \\ |

1710 | \hline |

1711 | \hline |

1712 | 0 & 3,362,997 & 2,924,082 & 1 & 438,915 \\ |

1713 | \hline |

1714 | 1 & 2,924,082 & 438,915 & 6 & 290,592 \\ |

1715 | \hline |

1716 | 2 & 438,915 & 290,592 & 1 & 148,323 \\ |

1717 | \hline |

1718 | 3 & 290,592 & 148,323 & 1 & 142,269 \\ |

1719 | \hline |

1720 | 4 & 148,323 & 142,269 & 1 & 6,054 \\ |

1721 | \hline |

1722 | 5 & 142,269 & 6,054 & 23 & 3,027 \\ |

1723 | \hline |

1724 | 6 & 6,054 & 3,027 & 2 & 0 \\ |

1725 | \hline |

1726 | \end{tabular} |

1727 | \end{center} |

1728 | \end{table} |

1729 | |

1730 | Table \ref{tbl:cfexplrgratnum01} |

1731 | implies that the continued fraction representation of |

1732 | $a/b$ = 3,362,997/2,924,082 is $[1;6,1,1,1,23,2]$. |

1733 | |

1734 | \begin{figure*} |

1735 | \begin{equation} |

1736 | \label{eq:eq0058} |

1737 | \frac{{{\rm 3,362,997}}}{{{\rm 2,924,082}}} = |

1738 | 1 + \cfrac{1}{{6 + \cfrac{1}{{1 + \cfrac{1}{{1 + \cfrac{1}{{1 + \cfrac{1}{{23 + \cfrac{1}{2}}}}}}}}}}} |

1739 | = |

1740 | a_0 + \cfrac{1}{{a_1 + \cfrac{1}{{a_2 + \cfrac{1}{{a_3 + \cfrac{1}{{a_4 + \cfrac{1}{{a_5 + \cfrac{1}{a_6}}}}}}}}}}} |

1741 | = |

1742 | [1; 6, 1, 1, 1, 23, 2] |

1743 | \end{equation} |

1744 | \end{figure*} |

1745 | |

1746 | Note in Table \ref{tbl:cfexplrgratnum01} |

1747 | that the final non-zero remainder is 3,027, |

1748 | the g.c.d. of 3,362,997 and 2,924,082. |

1749 | |

1750 | Irrational numbers also have a continued fraction representation, |

1751 | but this representation is necessarily infinite (non-terminating). |

1752 | |

1753 | An algorithm does exist for obtaining the continued |

1754 | fraction representation of an irrational number; but in practice the |

1755 | algorithm must be carried out symbolically (which |

1756 | can be difficult and not amenable to automation). |

1757 | For this reason, only the algorithm for obtaining the |

1758 | continued fraction representation of |

1759 | \emph{rational} numbers is presented here. |

1760 | Using a rational number as close as |

1761 | practical\footnote{Let $\alpha$ be |

1762 | the irrational number to be approximated, |

1763 | let $a/b$ be the rational number used as an approximation |

1764 | of $\alpha$ when applying Algorithm \ref{alg:akgenalg}, and let |

1765 | $H/K$ and $h/k$ be the two Farey neighbors identified |

1766 | through Theorem \ref{thm:thm06}. |

1767 | In a worst case, $\alpha < H/K < a/b < h/k$ or |

1768 | $H/K < a/b < h/k < \alpha$. In such cases, the misidentification |

1769 | of the two Farey neighbors is not detectable (because $\alpha$ |

1770 | is not known precisely enough, otherwise a more precise |

1771 | $a/b$ would have been used). In \emph{all} |

1772 | cases, $H/K < a/b < h/k$.} |

1773 | to the irrational number to be approximated |

1774 | (such as using 3141592654/1000000000 for $\pi$, as is done in |

1775 | Example \ref{example:examplepi01}) is the |

1776 | recommended technique. |

1777 | |

1778 | |

1779 | |

1780 | % (4)(F)(v) CONVERGENTS OF A CONTINUED FRACTION % |

1781 | |

1782 | |

1783 | The \emph{kth convergent} of a finite simple continued fraction |

1784 | $[a_{0};a_{1},a_{2},\ldots{},a_{n}]$, |

1785 | denoted $s_{k} = p_k/q_k$, is the rational number corresponding to the |

1786 | continued fraction $[a_{0};a_{1},a_{2},\ldots{},a_{k}]$, |

1787 | $k \leq n$. |

1788 | |

1789 | Each convergent $s_{k}$ is a rational number with a |

1790 | numerator $p_{k}$ and denominator $q_{k}$. |

1791 | Eqns. (\ref{eq:eq0059}) through (\ref{eq:eq0064}) |

1792 | define the canonical way to |

1793 | construct all $s_{k}=p_{k}/q_{k}$ from all $a_{k}$. |

1794 | |

1795 | \begin{equation} |

1796 | \label{eq:eq0059} |

1797 | p_{ - 1} = 1 |

1798 | \end{equation} |

1799 | |

1800 | \begin{equation} |

1801 | \label{eq:eq0060} |

1802 | q_{ - 1} = 0 |

1803 | \end{equation} |

1804 | |

1805 | \begin{equation} |

1806 | \label{eq:eq0061} |

1807 | p_0 = a_0 = \left\lfloor {r_I } \right\rfloor |

1808 | \end{equation} |

1809 | |

1810 | \begin{equation} |

1811 | \label{eq:eq0062} |

1812 | q_0 = 1 |

1813 | \end{equation} |

1814 | |

1815 | \begin{equation} |

1816 | \label{eq:eq0063} |

1817 | p_k = a_k p_{k - 1} + p_{k - 2} |

1818 | \end{equation} |

1819 | |

1820 | \begin{equation} |

1821 | \label{eq:eq0064} |

1822 | q_k = a_k q_{k - 1} + q_{k - 2} |

1823 | \end{equation} |

1824 | |

1825 | When $p_{k}$ and $q_{k}$ (the numerator and denominator of the |

1826 | $k$th convergent $s_{k}$) are formed as specified by (\ref{eq:eq0059}) |

1827 | through (\ref{eq:eq0064}), convergents $s_{k}=p_{k}/q_{k}$ have the following |

1828 | properties, which are presented without proof. |

1829 | |

1830 | \begin{propenum} |

1831 | |

1832 | \item Each even-ordered convergent |

1833 | $s_{k} = p_k/q_k = [a_{0}; a_{1}, a_{2}, \ldots{}, a_{k}]$ |

1834 | is less than $[a_{0}; a_{1}, a_{2}, \ldots{}, a_{n}]$, and |

1835 | each odd-ordered convergent $s_{k}$ is greater than |

1836 | $[a_{0}; a_{1}, a_{2}, \ldots{}, a_{n}]$, |

1837 | with the exception of the final convergent $s_{k}$, $k=n$, |

1838 | which is equal to $[a_{0}; a_{1}, a_{2}, \ldots{}, a_{n}]$. |

1839 | |

1840 | \item Each convergent is irreducible; that is, $p_k$ and |

1841 | $q_k$ are coprime. |

1842 | |

1843 | \item Each $q_{k}$ is greater than $q_{k-1}$; that is, the denominators |

1844 | of convergents are ever-increasing. |

1845 | |

1846 | \end{propenum} |

1847 | |

1848 | \begin{example} |

1849 | Find all convergents of the continued |

1850 | fraction representation of $a/b$=3,362,997/2,924,082; shown in |

1851 | Example 2 to be |

1852 | $[a_0;a_1,a_2,a_3,a_4,a_5,a_6]$=[1;6,1,1,1,23,2] |

1853 | \end{example} |

1854 | |

1855 | \emph{Solution:} Table \ref{tbl:convcfexplrgratnum01} |

1856 | shows the results of the |

1857 | application of equations (\ref{eq:eq0059}) |

1858 | through (\ref{eq:eq0064}) to form all |

1859 | convergents. |

1860 | |

1861 | \begin{table} |

1862 | \caption{Convergents Of Continued Fraction |

1863 | Representation Of $3,362,997/2,924,082$} |

1864 | \label{tbl:convcfexplrgratnum01} |

1865 | \begin{center} |

1866 | \begin{tabular}{|c|c|c|c|} |

1867 | \hline |

1868 | Index (k) & $a_{k}$ & $p_{k}$ & $q_{k}$ \\ |

1869 | \hline |

1870 | \hline |

1871 | -1 & Not defined & 1 & 0 \\ |

1872 | \hline |

1873 | 0 & 1 & 1 & 1 \\ |

1874 | \hline |

1875 | 1 & 6 & 7 & 6 \\ |

1876 | \hline |

1877 | 2 & 1 & 8 & 7 \\ |

1878 | \hline |

1879 | 3 & 1 & 15 & 13 \\ |

1880 | \hline |

1881 | 4 & 1 & 23 & 20 \\ |

1882 | \hline |

1883 | 5 & 23 & 544 & 473 \\ |

1884 | \hline |

1885 | 6 & 2 & 1,111 & 966 \\ |

1886 | \hline |

1887 | \end{tabular} |

1888 | \end{center} |

1889 | \end{table} |

1890 | |

1891 | Note that the final convergent, $s_{6}$=$p_{6}/q_{6}$=1,111/966 is |

1892 | the reduced form of $a/b$. Note also that all convergents |

1893 | $s_{k}=p_{k}/q_{k}$ are irreducible. It may also be verified that each |

1894 | even-ordered convergent is less than $a/b$, and that each odd-ordered |

1895 | convergent is greater than $a/b$, with the exception of |

1896 | the final convergent, which is equal to $a/b$. |

1897 | |

1898 | |

1899 | |

1900 | |

1901 | % (4)(F)(VI) THEOREM: USING CONTINUED FRACTIONS TO FIND FAREY NEIGHBORS % |

1902 | |

1903 | |

1904 | \begin{theorem} |

1905 | \label{thm:thm06} |

1906 | For a non-negative rational number $a/b$ not in |

1907 | $F_N$ which has a |

1908 | continued fraction representation |

1909 | $[a_0;a_1,a_2,\ldots{} ,a_n]$, the |

1910 | highest-order convergent $s_k = p_k/q_k$ with $q_k \leq N$ is one |

1911 | neighbor\footnote{By neighbors in $F_N$ we mean the rational numbers |

1912 | in $F_N$ immediately to the left and immediately to the right |

1913 | of $a/b$.} |

1914 | in $F_N$ to $a/b$, and the other neighbor in $F_N$ is given by |

1915 | (\ref{eq:eq0065}).\footnote{We were not able to locate |

1916 | Theorem \ref{thm:thm06} or a proof in print, |

1917 | but this theorem is known within the number theory community. |

1918 | It appears on the Web |

1919 | page of David Eppstein in the form of a |

1920 | `C'-language computer program, |

1921 | \texttt{http://www.ics.uci.edu/\~{}{}eppstein/numth/frap.c}.} |

1922 | \end{theorem} |

1923 | |

1924 | \begin{equation} |

1925 | \label{eq:eq0065} |

1926 | \frac{{\displaystyle{\left\lfloor {\frac{{N - q_{k - 1} }}{{q_k }}} \right\rfloor} |

1927 | p_k + p_{k - 1} }}{{\displaystyle{\left\lfloor {\frac{{N - q_{k - 1} }}{{q_k }}} |

1928 | \right\rfloor} q_k + q_{k - 1} }} |

1929 | \end{equation} |

1930 | |

1931 | \begin{proof} |

1932 | First, it is proved that the highest-order |

1933 | convergent $s_k = p_k/q_k$ with $q_k \leq N$ is one of the two |

1934 | neighbors to $a/b$ in $F_N$. Note that $s_k \in F_N$, since $s_k$ is rational |

1935 | and reduced with denominator not exceeding $N$. |

1936 | By theorem (\cite{KhinchinClassic}, Theorem 9, p. 9), the upper bound on the |

1937 | difference between $a/b$ and $s_k$ is given by (\ref{eq:eq0066}). |

1938 | |

1939 | \begin{equation} |

1940 | \label{eq:eq0066} |

1941 | \left| {\frac{a}{b} - \frac{{p_k }}{{q_k }}} \right| < \frac{1}{{q_k q_{k + 1} }} |

1942 | \end{equation} |

1943 | |

1944 | For two consecutive terms in $F_N$, $Kh-Hk=1$. |

1945 | For a Farey neighbor $H/K$ to $s_k$ in $F_N$, (\ref{eq:eq0067}) must hold. |

1946 | |

1947 | \begin{equation} |

1948 | \label{eq:eq0067} |

1949 | \frac{1}{q_k N} \leq \left| {\frac{H}{K} - \frac{p_k}{q_k}} \right| |

1950 | \end{equation} |

1951 | |

1952 | $q_{k+1}>N$, because $q_{k+1}>q_k$ and $p_k/q_k$ was chosen to be the |

1953 | highest-order convergent with $q_k\leq N$. Using this knowledge and |

1954 | combining (\ref{eq:eq0066}) and (\ref{eq:eq0067}) leads to |

1955 | (\ref{eq:eq0069}). |

1956 | |

1957 | \begin{equation} |

1958 | \label{eq:eq0069} |

1959 | \left| {\frac{a}{b} - \frac{{p_k }}{{q_k }}} \right| < \frac{1}{{q_k q_{k + 1} }} |

1960 | < |

1961 | \frac{1}{q_k N} \leq \left| {\frac{H}{K} - \frac{p_k}{q_k}} \right| |

1962 | \end{equation} |

1963 | |

1964 | This proves that $s_k$ is one neighbor to $a/b$ in $F_N$. |

1965 | The apparatus of continued fractions ensures that the |

1966 | highest order convergent $s_k$ with $q_k\leq N$ is closer to $a/b$ than |

1967 | to any neighboring term in $F_N$. Thus, there is |

1968 | no intervening term of $F_N$ between $s_k$ and $a/b$. |

1969 | If $k$ is even, $s_k<a/b$, and if $k$ is |

1970 | odd, $s_k>a/b$. |

1971 | |

1972 | It must be proved that (\ref{eq:eq0065}) is the other Farey |

1973 | neighbor. (\ref{eq:eq0065}) is of the form (\ref{eq:eq0071}), |

1974 | where $i \in \intsetnonneg$. |

1975 | |

1976 | \begin{equation} |

1977 | \label{eq:eq0071} |

1978 | \frac{{ip_k + p_{k - 1} }}{{iq_k + q_{k - 1} }} |

1979 | \end{equation} |

1980 | |

1981 | If $k$ is even, $s_k < a/b$, and the two Farey terms enclosing $a/b$, in |

1982 | order, are given in the first clause |

1983 | of (\ref{eq:eq0072}). If $k$ is odd, |

1984 | $s_k > a/b$, and the two Farey terms enclosing $a/b$, in order, are |

1985 | given in the second clause of (\ref{eq:eq0072}). |

1986 | |

1987 | \begin{equation} |

1988 | \label{eq:eq0072} |

1989 | \begin{array}{ll} |

1990 | \left\{ \displaystyle{{\frac{{p_k }}{{q_k }},\frac{{ip_k + p_{k - 1} }}{{iq_k + q_{k - 1} }}}} \right\} |

1991 | & |

1992 | (k \; even) |

1993 | \\ & \\ |

1994 | \left\{ \displaystyle{{\frac{{ip_k + p_{k - 1} }}{{iq_k + q_{k - 1} }},\frac{{p_k }}{{q_k }}}} \right\} |

1995 | & |

1996 | (k \; odd) |

1997 | \\ |

1998 | \end{array} |

1999 | \end{equation} |

2000 | |

2001 | In either clause of (\ref{eq:eq0072}), |

2002 | applying the $Kh - Hk = 1$ test, (\ref{eq:eq0074}), gives the |

2003 | result of 1, since by theorem |

2004 | (\cite{KhinchinClassic}, Theorem 2, p. 5), |

2005 | $q_kp_{k-1}-p_kq_{k-1}=(-1)^k$, with the |

2006 | exponent of $k$ compensating |

2007 | for the ordering difference between |

2008 | the two clauses of |

2009 | (\ref{eq:eq0072}), as shown in (\ref{eq:eq0075}). |

2010 | |

2011 | \begin{figure*} |

2012 | \begin{equation} |

2013 | \label{eq:eq0074} |

2014 | \begin{array}{*{20}c} |

2015 | {(q_k )(ip_k + p_{k - 1} ) - (p_k )(iq_k + q_{k - 1} ) = 1,} \hfill & {{\rm (k \; even)}} \hfill \\ |

2016 | {(iq_k + q_{k - 1} )(p_k ) - (ip_k + p_{k - 1} )(q_k ) = 1,} \hfill & {{\rm (k \; odd)}} \hfill \\ |

2017 | \end{array} |

2018 | \end{equation} |

2019 | \end{figure*} |

2020 | |

2021 | \begin{equation} |

2022 | \label{eq:eq0075} |

2023 | \begin{array}{*{20}c} |

2024 | {q_k p_{k - 1} - p_k q_{k - 1} = ( - 1)^k = 1,} \hfill & {{\rm (k \; even)}} \hfill \\ |

2025 | {q_{k - 1} p_k - p_{k - 1} q_k = - ( - 1)^k = 1,} \hfill & {{\rm (k \; odd)}} \hfill \\ |

2026 | \end{array} |

2027 | \end{equation} |

2028 | |

2029 | Thus, every potential Farey neighbor of the form (\ref{eq:eq0071}) |

2030 | meets the $Kh - Hk = 1$ test. In order to show |

2031 | that (\ref{eq:eq0065}) is the |

2032 | companion Farey neighbor to $p_k/q_k$, it is only necessary |

2033 | to show that a term meeting the $Hk-Hk=1$ test with a |

2034 | larger denominator still not greater than $N$ cannot exist |

2035 | (Theorem \ref{thm:thm05}). |

2036 | |

2037 | It must first be established that a |

2038 | rational number of the form (\ref{eq:eq0071}) |

2039 | is irreducible. This result comes directly from (\ref{eq:eq0074}) and |

2040 | (\ref{eq:eq0075}), since if the numerator |

2041 | and denominator of (\ref{eq:eq0065}) or |

2042 | (\ref{eq:eq0071}) are not coprime, the difference of 1 is |

2043 | not possible. |

2044 | |

2045 | The denominator of (\ref{eq:eq0065}) |

2046 | can be rewritten as (\ref{eq:eq0076}). |

2047 | |

2048 | \begin{equation} |

2049 | \label{eq:eq0076} |

2050 | N - \left[ {\left( {N - q_{k - 1} } \right)\bmod q_k } \right] \in \left\{ {N - q_k + 1,...,N} \right\} |

2051 | \end{equation} |

2052 | |

2053 | Finally, it must be shown that if one irreducible |

2054 | rational number---namely, the rational number given by |

2055 | (\ref{eq:eq0065})---with a denominator |

2056 | $\in \{ N-q_k+1,\ldots{} ,N \}$ meets the $Kh - Hk = 1$ |

2057 | test, there can be no other irreducible rational number |

2058 | in $F_N$ with a larger |

2059 | denominator which also meets this test. |

2060 | |

2061 | Let $c/d$ be the irreducible rational number given by |

2062 | (\ref{eq:eq0065}), with $d$ already shown |

2063 | above to be $\in \{N - q_k + 1,...,N\}$. |

2064 | Since $c/d$ and $s_k = p_k/q_k$ meet the $Kh - Hk = 1$ test, |

2065 | (\ref{eq:eq0076b}) follows. |

2066 | |

2067 | \begin{equation} |

2068 | \label{eq:eq0076b} |

2069 | c = \frac{1}{q_k} + \frac{p_k d}{q_k}; \; c \in \intset{} |

2070 | \end{equation} |

2071 | |

2072 | $c$ as shown in (\ref{eq:eq0076b}) is necessarily an |

2073 | integer. Assume that $d \in \intset{}$ is to be perturbed by |

2074 | some amount $\Delta \in \intset{}$ to form a different |

2075 | integer $d + \Delta \in \intset{}$. In order for the $Kh - Hk = 1$ test |

2076 | to be met with the new choice of denominator |

2077 | $d + \Delta$, (\ref{eq:eq0076c}) is required. |

2078 | |

2079 | \begin{equation} |

2080 | \label{eq:eq0076c} |

2081 | \frac{1}{q_k} + \frac{p_k d}{q_k} + \frac{p_k \Delta}{q_k} \in \intset{} |

2082 | \end{equation} |

2083 | |

2084 | Comparing (\ref{eq:eq0076b}) with (\ref{eq:eq0076c}), it can be seen |

2085 | that since the first two terms of (\ref{eq:eq0076c}) sum to an integer, |

2086 | (\ref{eq:eq0076c}) implies that |

2087 | $p_k \Delta / q_k \in \intset{}$. |

2088 | $p_k$ and $q_k$ |

2089 | are coprime, and so in order for $q_k$ to divide $p_k \Delta$ with |

2090 | no remainder, $\Delta$ must contain at least every prime factor of |

2091 | $q_k$, which implies that $\Delta \geq q_k$. Noting that the |

2092 | denominator of (\ref{eq:eq0065}) is necessarily |

2093 | $d \in \{N - q_k + 1,...,N\}$, any positive perturbation |

2094 | $\Delta \geq q_k$ will form a $d + \Delta > N$. Thus, |

2095 | no other irreducible rational number in $F_N$ besides that given |

2096 | by (\ref{eq:eq0065}) with a larger denominator |

2097 | $\leq N$ and which meets the $Kh - Hk = 1$ test can exist; therefore |

2098 | (\ref{eq:eq0065}) is the other enclosing Farey neighbor to |

2099 | $a/b$ in $F_N$. |

2100 | \end{proof} |

2101 | |

2102 | \begin{example} |

2103 | \label{example:examplepi01} |

2104 | Find the members of $F_{65535}$ immediately |

2105 | before and immediately after $\pi$. |

2106 | \end{example} |

2107 | |

2108 | \emph{Solution:} $\pi$ is transcendental and cannot be expressed |

2109 | as a rational number. Using 3141592654/1000000000 |

2110 | as a rational approximation to $\pi$ and applying |

2111 | Algorithm \ref{alg:akgenalg} |

2112 | yields Table \ref{tbl:cfexpansrapppi}. |

2113 | |

2114 | \begin{table} |

2115 | \caption{Continued Fraction Representation Of 3,141,592,654/1,000,000,000 |

2116 | (A Rational Approximation To $\pi$)} |

2117 | \label{tbl:cfexpansrapppi} |

2118 | \begin{center} |

2119 | \begin{tabular}{|c|c|c|c|c|} |

2120 | \hline |

2121 | \small{Index} & \small{Dividend} & \small{Divisor} & $a_k$ & \small{Remainder} \\ |

2122 | \small{(k)} & & & & \\ |

2123 | \hline |

2124 | \hline |

2125 | \small{0} & \small{3,141,592,654} & \small{1,000,000,000} & \small{3} & \small{141,592,654} \\ |

2126 | \hline |

2127 | \small{1} & \small{1,000,000,000} & \small{141,592,654} & \small{7} & \small{8,851,422} \\ |

2128 | \hline |

2129 | \small{2} & \small{141,592,654} & \small{8,851,422} & \small{15} & \small{8,821,324} \\ |

2130 | \hline |

2131 | \small{3} & \small{8,851,422} & \small{8,821,324} & \small{1} & \small{30,098} \\ |

2132 | \hline |

2133 | \small{4} & \small{8,821,324} & \small{30,098} & \small{293} & \small{2,610} \\ |

2134 | \hline |

2135 | \small{5} & \small{30,098} & \small{2,610} & \small{11} & \small{1,388} \\ |

2136 | \hline |

2137 | \small{6} & \small{2,610} & \small{1,388} & \small{1} & \small{1,222} \\ |

2138 | \hline |

2139 | \small{7} & \small{1,388} & \small{1,222} & \small{1} & \small{166} \\ |

2140 | \hline |

2141 | \small{8} & \small{1,222} & \small{166} & \small{7} & \small{60} \\ |

2142 | \hline |

2143 | \small{9} & \small{166} & \small{60} & \small{2} & \small{46} \\ |

2144 | \hline |

2145 | \small{10} & \small{60} & \small{46} & \small{1} & \small{14} \\ |

2146 | \hline |

2147 | \small{11} & \small{46} & \small{14} & \small{3} & \small{4} \\ |

2148 | \hline |

2149 | \small{12} & \small{14} & \small{4} & \small{3} & \small{2} \\ |

2150 | \hline |

2151 | \small{13} & \small{4} & \small{2} & \small{2} & \small{0} \\ |

2152 | \hline |

2153 | \end{tabular} |

2154 | \end{center} |

2155 | \end{table} |

2156 | |

2157 | |

2158 | Table \ref{tbl:cfconvofpi} shows the formation of the convergents |

2159 | of the continued fraction |

2160 | representation of the |

2161 | rational approximation to $\pi$ using (\ref{eq:eq0059}) through (\ref{eq:eq0064}). |

2162 | |

2163 | \begin{table} |

2164 | \caption{Convergents Of Continued Fraction Representation Of |

2165 | 3,141,592,654/1,000,000,000 (A Rational Approximation |

2166 | To $\pi$)} |

2167 | \label{tbl:cfconvofpi} |

2168 | \begin{center} |

2169 | \begin{tabular}{|c|c|c|c|} |

2170 | \hline |

2171 | Index (k) & $a_{k}$ & $p_{k}$ & $q_{k}$ \\ |

2172 | \hline |

2173 | \hline |

2174 | -1 & Not defined & 1 & 0 \\ |

2175 | \hline |

2176 | 0 & 3 & 3 & 1 \\ |

2177 | \hline |

2178 | 1 & 7 & 22 & 7 \\ |

2179 | \hline |

2180 | 2 & 15 & 333 & 106 \\ |

2181 | \hline |

2182 | 3 & 1 & 355 & 113 \\ |

2183 | \hline |

2184 | 4 & 293 & 104,348 & 33,215 \\ |

2185 | \hline |

2186 | 5 & 11 & 1,148,183 & 365,478 \\ |

2187 | \hline |

2188 | 6 & 1 & 1,252,531 & 398,693 \\ |

2189 | \hline |

2190 | 7 & 1 & 2,400,714 & 764,171 \\ |

2191 | \hline |

2192 | 8 & 7 & 18,057,529 & 5,747,890 \\ |

2193 | \hline |

2194 | 9 & 2 & 38,515,772 & 12,259,951 \\ |

2195 | \hline |

2196 | 10 & 1 & 56,573,301 & 18,007,841 \\ |

2197 | \hline |

2198 | 11 & 3 & 208,235,675 & 66,283,474 \\ |

2199 | \hline |

2200 | 12 & 3 & 681,280,326 & 216,858,263 \\ |

2201 | \hline |

2202 | 13 & 2 & 1,570,796,327 & 500,000,000 \\ |

2203 | \hline |

2204 | \end{tabular} |

2205 | \end{center} |

2206 | \end{table} |

2207 | |

2208 | By Theorem \ref{thm:thm06}, one Farey neighbor is the convergent |

2209 | with the largest denominator not greater than 65,535. |

2210 | From Table \ref{tbl:cfconvofpi}, this convergent is $s_4$ = $p_4/q_4$ = |

2211 | 104,348/33,215 (and note that since this is an |

2212 | even-ordered convergent, it will be less than $a/b$). Also by |

2213 | Theorem \ref{thm:thm06}, applying equation |

2214 | (\ref{eq:eq0065}), the other Farey |

2215 | neighbor is 104,703/33,328. |

2216 | |

2217 | |

2218 | |

2219 | |

2220 | % (4)(F)CASE OF CONSTRAINED h % |

2221 | |

2222 | |

2223 | \subsection{Case Of Constrained $h$} |

2224 | |

2225 | In a practical design problem, a rational approximation |

2226 | will typically be implemented by multiplying the input |

2227 | argument $x$ by $h$, adding an offset $z$, then dividing |

2228 | by $k$. Efficiency will often depend on being able to |

2229 | implement multiplication, addition, or |

2230 | division using single machine instructions, which are |

2231 | constrained in the size of the operands they can accomodate. |

2232 | |

2233 | The results from number theory presented earlier are based |

2234 | only on the constraint $k \leq k_{MAX}$, i.e. only the constraint |

2235 | on the denominator is considered. However, in practical problems, |

2236 | the numerator is also typically constrained, usually by the |

2237 | size of operands that an integer multiplication instruction |

2238 | can accomodate. |

2239 | |

2240 | $r_I$, $h_{MAX}$, and $k_{MAX}$ |

2241 | can be specified so that the restriction on the numerator |

2242 | is the dominant constraint, which |

2243 | does not allow the Farey series of order |

2244 | $N=k_{MAX}$ to be economically |

2245 | used to find the best rational approximation to $r_{I}$, |

2246 | because $F_{k_{MAX}}$ near $r_I$ will contain |

2247 | predominantly terms with |

2248 | numerators violating $h \leq h_{MAX}$. |

2249 | |

2250 | To provide for a more economical search for the best |

2251 | rational approximations when the numerator is constrained, |

2252 | Theorem \ref{thm:thmconstrainednumerator} is presented. |

2253 | |

2254 | \begin{theorem} |

2255 | \label{thm:thmconstrainednumerator} |

2256 | Given a positive |

2257 | real number $r_I$ and constraints |

2258 | on a rational approximation $h/k$ to $r_I$, |

2259 | $0 \leq h \leq h_{MAX}$ and $0 < k \leq k_{MAX}$, the closest |

2260 | rational numbers to $r_I$ on the left and right |

2261 | subject to the constraints lie |

2262 | in $F_{N'}$, with $N'$ chosen as in (\ref{eq:eqconsth:aa}). |

2263 | \end{theorem} |

2264 | |

2265 | \begin{equation} |

2266 | \label{eq:eqconsth:aa} |

2267 | N'=\left\lfloor |

2268 | { |

2269 | \frac{h_{MAX}}{r_I } + 1 |

2270 | } |

2271 | \right\rfloor |

2272 | \end{equation} |

2273 | |

2274 | \begin{proof} |

2275 | Note that by (\ref{eq:eqconsth:aa}), |

2276 | $N' > h_{MAX}/r_I$, for all choices |

2277 | of $h_{MAX}$ and $r_I$. |

2278 | |

2279 | If $r_I \leq h_{MAX}/k_{MAX}$, $N' > k_{MAX}$; |

2280 | therefore $F_{N'} \supset F_{k_{MAX}}$, |

2281 | and the theorem is true. |

2282 | |

2283 | If $r_I > h_{MAX}/k_{MAX}$, then $h_{MAX}/N' < r_I$. |

2284 | Note that $h_{MAX}/N'$ or its reduced form if it |

2285 | is reducible is necessarily in $F_{N'}$. Any |

2286 | rational number $a/b > h_{MAX}/N'$ with $b>N'$ |

2287 | must also have $a > h_{MAX}$, which violates |

2288 | the constraints. Therefore, any $a/b$ such |

2289 | that $h_{MAX}/N' < a/b < r_I$ must lie |

2290 | in $F_{N'}$, and the closest rational number |

2291 | to $r_I$ on the right subject to the constraints |

2292 | must also lie in $F_{N'}$. |

2293 | \end{proof} |

2294 | |

2295 | \begin{example} |

2296 | \label{ex:expiconstrainednumandden} |

2297 | Find the two best rational approximations to $\pi$ subject to |

2298 | $h_{MAX} = 255$ and $k_{MAX} = 255$. |

2299 | \end{example} |

2300 | |

2301 | \emph{Solution:} In this problem, both the numerator and |

2302 | denominator are constrained. The constrained numerator is |

2303 | not treated directly by the results from number theory. |

2304 | Applying (\ref{eq:eqconsth:aa}) gives $N'$=82, thus it is only necessary |

2305 | to examine $F_{82}$ for best approximations to $\pi$ which |

2306 | meet both constraints. Building $F_{82}$ yields 245/78 and |

2307 | 22/7 as the two best rational approximations to $\pi$ |

2308 | under the constraints. |

2309 | |

2310 | |

2311 | |

2312 | |

2313 | % (4)(B)HOW CLOSE WE CAN USUALLY GET TO R_I WHEN CHOOSING R_A % |

2314 | |

2315 | |

2316 | \section{Probabilistic Results On $ | R_I - R_A | $} |

2317 | \label{sec:probresults} |

2318 | |

2319 | In this section we consider different asymptotics for |

2320 | the precision of the approximation of an arbitrary $r_I$ by a fraction |

2321 | $r_A= h/k$ with $k \leq k_{ \rm MAX }$. For simplicity of notation |

2322 | we |

2323 | denote $\alpha= r_I$ and $N=k_{ \rm MAX }$ and assume, without |

2324 | loss of generality, that |

2325 | $ \alpha \in [0,1]$. |

2326 | |

2327 | We are thus interested in the asymptotic behaviour, when $N |

2328 | \rightarrow \infty$, |

2329 | of the quantity |

2330 | $$ |

2331 | %\begin{equation} |

2332 | \label{eq:dist} |

2333 | \rho_N(\alpha) = \min_{h/k \in F_N} \left|\alpha - h/k\right|\, , |

2334 | $$ |

2335 | %\end{equation} |

2336 | which is the distance between $\alpha$ and $F_N$, the Farey |

2337 | series of order $N$. |

2338 | |

2339 | The worst--case scenario is not very interesting: from the |

2340 | construction of the Farey series |

2341 | we observe that for a fixed $N$ the longest intervals between the |

2342 | neighbours of $F_N$ |

2343 | are $[0,1/N]$ and $[1-1/N,1]$ and therefore for all $N$ |

2344 | \begin{equation} |

2345 | \label{eq:max_error} |

2346 | \max_{\alpha \in [0,1]} \rho_N(\alpha) = \frac{1}{2N}\, . |

2347 | \end{equation} |

2348 | (This supremum is achieved at the points $1/(2N)$ and $1-1/(2N)$.) |

2349 | |

2350 | Such behaviour of $\rho_N(\alpha)$ is however not typical: as we |

2351 | shall see below, |

2352 | typical values of the approiximation error $\rho_N(\alpha)$ are |

2353 | much smaller. |

2354 | |

2355 | Let us first consider the behaviour of $\rho_N(\alpha)$ for almost all |

2356 | $\alpha \in [0,1]$.\footnote{ A statement is true |

2357 | for almost all $\alpha \in [0,1]$ if the measure of the set where this |

2358 | statement is wrong has measure zero.} |

2359 | We then have, see \cite{KargaevZ} and also \cite{Harman}, |

2360 | that for almost all $\alpha \in [0,1]$ and any $\varepsilon >0$, |

2361 | (\ref{eq:liminf}) and (\ref{eq:limsup}) hold. |

2362 | |

2363 | \begin{figure*} |

2364 | \begin{equation} |

2365 | \label{eq:liminf} |

2366 | \lim_{N\rightarrow\infty}\rho_N(\alpha) N^2 \log^{1+\varepsilon} N = |

2367 | + \infty, \quad |

2368 | \liminf_{N\rightarrow\infty} \rho_N(\alpha) N^2 \log N = 0 |

2369 | \end{equation} |

2370 | \end{figure*} |

2371 | |

2372 | \begin{figure*} |

2373 | \begin{equation} |

2374 | \label{eq:limsup} |

2375 | \limsup_{N\rightarrow\infty} \frac{ \rho_N(\alpha) N^2 }{ \log N } = + |

2376 | \infty, \quad |

2377 | \lim_{N\rightarrow\infty} \frac{ \rho_N(\alpha) N^2 }{ |

2378 | \log^{1+\varepsilon} N } = 0 |

2379 | \end{equation} |

2380 | \end{figure*} |

2381 | |

2382 | Even more is true: in (\ref{eq:liminf}) and (\ref{eq:limsup}) |

2383 | one can replace $\log N$ by $\log N \log \log N $, $\log N \log \log |

2384 | N \log \log \log N$ and so on. |

2385 | Analogously, $\log^{1+\varepsilon} N$ could be replaced by |

2386 | $\log N (\log \log N)^{1+\varepsilon} $, $\log N \log \log N (\log \log |

2387 | \log N)^{1+\varepsilon}$ and so on. |

2388 | |

2389 | These statements are analogues of Khinchin's metric theorem, |

2390 | the classic result |

2391 | in the metric number theory, see e.g. \cite{Harman}. |

2392 | |

2393 | The asymptotic distribution of the suitably normalised |

2394 | $\rho_N(\alpha)$ |

2395 | was derived in \cite{KargaevZ1}. A main result of this |

2396 | paper is that |

2397 | the sequence of functions |

2398 | $N^2\rho_N(\alpha)$ converges in distribution, when $N\rightarrow |

2399 | \infty$, |

2400 | to the probability measure on $[0, \infty)$ with the density given |

2401 | by (\ref{eq:dens-ab}). |

2402 | |

2403 | \begin{figure*} |

2404 | \begin{equation} |

2405 | \label{eq:dens-ab} |

2406 | {p}(\tau) = |

2407 | \left\{\begin{array}{ll} |

2408 | 6/\pi^2 & \mbox{ if $0 \leq \tau \leq \frac{1}{2}$ }\\ |

2409 | & \\ |

2410 | \frac{6}{\pi^2 \tau} \left(1 + \log \tau - \tau |

2411 | \right) & \mbox{ if $\frac{1}{2}\leq \tau\leq 2 $ } \\ |

2412 | & \\ |

2413 | \frac{ 3}{\pi^2 \tau}\left(2\log(2 \tau)\! |

2414 | -\!4\log(\sqrt{\tau}\!+\!\sqrt{\tau\!-\!2})\! |

2415 | -\! (\sqrt{\tau}\!-\!\sqrt{\tau\!-\!2})^2 \right) |

2416 | & \mbox{ if $2 \leq \tau < \infty $ } |

2417 | \end{array} |

2418 | \right. |

2419 | \end{equation} |

2420 | \end{figure*} |

2421 | |

2422 | This means that |

2423 | for all $a,A$ |

2424 | such that |

2425 | $0<a<A<\infty$, |

2426 | (\ref{eq:davedrzinsert01}) applies, |

2427 | where |

2428 | {\rm `meas'} denotes for the standard Lebesgue measure on $[0,1]$. |

2429 | |

2430 | \begin{figure*} |

2431 | \begin{equation} |

2432 | \label{eq:davedrzinsert01} |

2433 | {\rm meas} \{ \alpha \in [0,1]: \;a < N^2 \rho_N(\alpha) \leq A \} |

2434 | \rightarrow |

2435 | \int_a^A {p}(\tau) d \tau\, |

2436 | \;\;{\rm as}\; N \rightarrow \infty |

2437 | \end{equation} |

2438 | \end{figure*} |

2439 | |

2440 | Another result in \cite{KargaevZ1} concerns the asymptotic |

2441 | behavior |

2442 | of the moments of the approximation error $\rho_N(\alpha) $. It |

2443 | says that |

2444 | for any $\delta\neq 0$ and $N \rightarrow \infty$, |

2445 | (\ref{eq:moments}) applies, |

2446 | where $\zeta(\cdot)$ and B$(\cdot,\cdot)$ |

2447 | are the Riemann zeta--function and the Beta--function, |

2448 | correspondingly. |

2449 | |

2450 | |

2451 | \begin{figure*} |

2452 | \begin{equation} |

2453 | \label{eq:moments} |

2454 | \hspace{-8mm} |

2455 | { |

2456 | %\textstile |

2457 | \small |

2458 | \frac{\delta+1}{2} |

2459 | } |

2460 | \int_0^1 \rho_N^{\delta} (\alpha) d \alpha = |

2461 | \left\{\begin{array}{ll} |

2462 | \infty & \mbox{if $ \delta \leq -1 $}\\ |

2463 | & \\ |

2464 | % \frac{6}{\delta^2 (\delta+1)\pi^2 } \left(2^{-\delta} + |

2465 | \frac{3}{\delta^2 \pi^2 } \left(2^{-\delta} + |

2466 | \delta 2^{\delta+2} {\rm B}(\!-\delta,\frac{1}{2}) \right) |

2467 | N^{-2\delta}\left(1\! +\! o(1)\right) |

2468 | & \mbox{if $-1\!<\!\delta\!<\!1, \delta\! \neq\! 0$ }\\ |

2469 | & \\ |

2470 | \frac{3}{\pi^2} N^{-2} \log N + |

2471 | O\left( N^{-2} \right) |

2472 | & \mbox{if $\delta =1 $ }\\ |

2473 | & \\ |

2474 | %\frac{2^{1-\delta}}{1+\delta} |

2475 | 2^{-\delta} |

2476 | \frac{\zeta(\delta)}{ \zeta(\delta+1)} |

2477 | N^{-\delta-1}+ |

2478 | O\left( N^{-2\delta} \right) |

2479 | & \mbox{if $\delta >1$ } |

2480 | \end{array} |

2481 | \right. |

2482 | \end{equation} |

2483 | \end{figure*} |

2484 | |

2485 | In particular, the average of the approximation error $\rho_N |

2486 | (\alpha)$ asymptotically equals |

2487 | \begin{equation} |

2488 | \label{eq:average_as} |

2489 | \int_{0}^1 \rho_N(\alpha) d\alpha = \frac{3}{\pi^2} \frac{\log N}{N^2} + |

2490 | O\left(\frac{1}{N^2}\right), |

2491 | \;\;\;\; N\rightarrow \infty \,. |

2492 | \end{equation} |

2493 | |

2494 | Comparison of (\ref{eq:average_as}) |

2495 | with (\ref{eq:limsup}) shows that the |

2496 | asymptotic behavior of the average approximation error $\int |

2497 | \rho_N(\alpha) d\alpha$ |

2498 | resembles the behavior of the superior limit of $\rho_N(\alpha)$. |

2499 | Even this limit |

2500 | decreases much faster than the maximum error $\max_{\alpha } |

2501 | \rho_N(\alpha)$, see |

2502 | (\ref{eq:max_error}): for typical $\alpha$ the rate of decrease of |

2503 | $\rho_N(\alpha)$, when $ N\rightarrow \infty ,$ |

2504 | is, roughly speaking, $N^{-2}$ rather than $N^{-1}$, the error for the |

2505 | worst combination of $\alpha$ and $N$. |

2506 | |

2507 | |

2508 | |

2509 | % (5) TABULATED VALUES AND THE H=2^Q CASE % |

2510 | |

2511 | |

2512 | \section{Tabulated Scaling Factors} |

2513 | \label{sec:tabscalingfactors} |

2514 | |

2515 | Choosing $r_{A}=h/k$ using Farey series techniques as |

2516 | outlined in Section \ref{sec:methodshkchoose} |

2517 | is a suitable solution |

2518 | when $r_I$ is invariant and known at the time |

2519 | the scaling function is designed. |

2520 | The error terms developed allow |

2521 | prediction of the maximum approximation error over a |

2522 | domain $[0,x_{MAX}]$ when a specific $r_{A}\approx r_I$ is chosen. |

2523 | |

2524 | A different problem which occurs in practice is |

2525 | the need to tabulate scaling factors in ROM or EEPROM. |

2526 | These scaling factors (which represent $r_A$) may depend |

2527 | on sensor or actuator calibrations and are not known |

2528 | precisely in advance at the time |

2529 | the software is designed, and so the technique of choosing |

2530 | and evaluating a |

2531 | rational number $r_A$ at design time |

2532 | as presented earlier cannot be |

2533 | applied. |

2534 | |

2535 | |

2536 | |

2537 | \subsection{Method Of Tabulating Scaling Factors} |

2538 | |

2539 | The previous sections have concentrated on scaling factors |

2540 | expressed as an arbitrary rational number $h/k$. |

2541 | However, it is usually not practical to tabulate scaling factors |

2542 | as rational numbers with an arbitrary denominator $k$ for the following |

2543 | reasons. |

2544 | |

2545 | \begin{generalenum} |

2546 | \item Not all processors have division instructions, |

2547 | and division in software (as |

2548 | would be required with an arbitrary |

2549 | tabulated denominator $k$) is expensive. |

2550 | \item Even for processors with division |

2551 | instructions, if the required maximum |

2552 | arbitrary denominator $k$ exceeds |

2553 | the size which can be accomodated |

2554 | by the division instructions, there is no general way to perform |

2555 | a division of large operands |

2556 | using small division instructions (a solution |

2557 | involving arbitrary division is not |

2558 | scaleable). |

2559 | \item The rational elements of $F_N$ are irregularly spaced |

2560 | in $\realset$. The worst case occurs near integers, |

2561 | where the elements are $1/N$ apart. Allowing arbitrary tabulated |

2562 | rational |

2563 | numbers $r_A = h/k$ means that in some regions of $\realset{}$, |

2564 | $r_A$ can be placed very close to $r_I$, whereas in other |

2565 | regions, the maximum error may degrade to $|r_A - r_I| \leq 1/2N$. |

2566 | This irregular error is usually not useful in engineering endeavors, |

2567 | as the worst-case error must typically be assumed. The division by |

2568 | an arbitrary tabulated $k$ carries computational cost but |

2569 | a limited engineering |

2570 | benefit. |

2571 | \end{generalenum} |

2572 | |

2573 | The method of tabulating scaling factors presented in this paper is to |

2574 | create scaling factors of the form $h/2^q$, so that the denominator is |

2575 | an integral power of two. This approach has the following advantages. |

2576 | |

2577 | \begin{generalenum} |

2578 | \item The required multiplication by $h$ is scaleable, allowing large $h$ when |

2579 | necessary. |

2580 | \item The division by $2^q$ is economically performed using right shift |

2581 | instructions, which every processor has, and which are |

2582 | scaleable. |

2583 | \end{generalenum} |

2584 | |

2585 | |

2586 | \subsection{Design Approaches For $h/2^q$ Tabulated Linear Scalings} |

2587 | |

2588 | Fig. \ref{figthreeelementsofchoice} shows the three elements of design |

2589 | choice in engineering an $h/2^q$ tabulated linear scaling. |

2590 | If any two of these elements are fixed, the third can be derived. |

2591 | The \emph{Maximum Approximation Error} |

2592 | (A) |

2593 | is the maximum approximation error that |

2594 | can be tolerated for any element of the domain and |

2595 | any tabulated $r_A$. The |

2596 | \emph{Domain And Range Of Approximation} |

2597 | (B) |

2598 | are the domain over which |

2599 | the approximation will be used, and the range which must be reachable |

2600 | by the appropriate choice of tabulated scaling factor $h$. |

2601 | The \emph{Data Size Of Tabulated $h$ And Value Of $q$, $2^q$} |

2602 | (C) |

2603 | are the number of bits which must be reserved for each |

2604 | tabulated $h$, and the number of bits by which the multiplication |

2605 | result $hx$ must be right-shifted (this value is typically hard-coded |

2606 | into the scaling strategy). |

2607 | |

2608 | \begin{figure} |

2609 | \caption{Three Elements Of Design Choice In Tabulated Linear $h/2^q$ Scaling Design} |

2610 | \label{figthreeelementsofchoice} |

2611 | \begin{picture}(240,167) |

2612 | |

2613 | \put(76,120){\line(1,0){100}} |

2614 | \put(141,35){\line(1,1){62}} |

2615 | \put(121,35){\line(-1,1){62}} |

2616 | |

2617 | \put(35,133){\makebox(0,0){(A) Maximum}} |

2618 | \put(35,121){\makebox(0,0){Approximation}} |

2619 | \put(35,109){\makebox(0,0){Error}} |

2620 | |

2621 | \put(217,133){\makebox(0,0){(B) Domain}} |

2622 | \put(217,121){\makebox(0,0){And Range Of}} |

2623 | \put(217,109){\makebox(0,0){Approximation}} |

2624 | |

2625 | \put(126,24){\makebox(0,0){(C) Data Size Of Tabulated $h$}} |

2626 | \put(126,12){\makebox(0,0){And Value Of $q$, $2^q$}} |

2627 | |

2628 | \end{picture} |

2629 | \end{figure} |

2630 | |

2631 | The most typical case for beginning a design is that |

2632 | (A) (Fig. \ref{figthreeelementsofchoice}) |

2633 | and |

2634 | (B) are known, so that |

2635 | (C) |

2636 | can be derived. A less typical case for beginning |

2637 | a design is that (B) |

2638 | and (C) |

2639 | are tentatively known, so that (A) can |

2640 | be derived (and if this error is unacceptable, the tentative design |

2641 | must be reevaluated). Although it is possible to make the |

2642 | necessary derivations, it never occurs in practice that |

2643 | a design begins with (A) and |

2644 | (C), |

2645 | with the intent of deriving |

2646 | (B). For this |

2647 | reason, only the first two cases are discussed in this paper. |

2648 | |

2649 | |

2650 | \subsection{Design By Placement Of $r_A$} |

2651 | |

2652 | A useful paradigm of design is to consider the problem of engineering |

2653 | a tabulated $h/2^q$ scaling in terms of what abilities we preserve |

2654 | for placing $r_A$ with respect to $r_I$. |

2655 | |

2656 | \begin{figure} |

2657 | \caption{Specification Of Domain And Possible Values Of $r_I$ As Triangular |

2658 | Region} |

2659 | \label{fig:specdomainrangetriangular} |

2660 | |

2661 | \begin{picture}(240,130) |

2662 | |

2663 | \put(20,20){\line(1,0){142}} |

2664 | \put(20,20){\line(0,1){97}} |

2665 | \put(20,20){\line(3,2){142}} |

2666 | |

2667 | \put(162,20){\dashbox{.5}(0,97)} |

2668 | \put(8,75){\makebox(0,0){$\scriptstyle L(x)$}} |

2669 | |

2670 | \put(93,12){\makebox(0,0){$\scriptstyle x$}} |

2671 | \put(163,12){\makebox(0,0){$\scriptstyle x_{MAX}$}} |

2672 | \put(210,115){\makebox(0,0){$\scriptstyle (x_{MAX}, \lfloor r_{IMAX} x_{MAX}\rfloor)$}} |

2673 | |

2674 | \put(110, 55){\makebox(0,0){\small{Triangular}}} |

2675 | \put(110, 45){\makebox(0,0){\small{Region Of}}} |

2676 | \put(110, 35){\makebox(0,0){\small{Tabulated Approximation}}} |

2677 | |

2678 | \end{picture} |

2679 | \end{figure} |

2680 | |

2681 | Assume that at design time, |

2682 | we know that the linear scaling will be |

2683 | used over the domain $[0,x_{MAX}]$, $x_{MAX} \in \intsetpos{}$, |

2684 | and that $0 \leq r_I \leq r_{IMAX}$ for all of the $r_I$ we |

2685 | wish to tabulate. This establishes a triangular region in |

2686 | which the approximation will be used |

2687 | (Fig. \ref{fig:specdomainrangetriangular}). |

2688 | |

2689 | The forms of $L(x)$ and $M(x)$ |

2690 | (Eqns. \ref{eq:eq0009}, \ref{eq:eq0009b}) reveal that |

2691 | a specific choice of $q$ allows the selection of $r_A$ |

2692 | in steps of $1/2^q$. With $q$ selected, |

2693 | there are four obvious choices for placement of $r_A$ |

2694 | (\ref{dbpora01aa00}, \ref{dbpora01aa01}, |

2695 | \ref{dbpora01aa02}, \ref{dbpora01aa03}), with almost no |

2696 | practical distinction between (\ref{dbpora01aa01}) |

2697 | and (\ref{dbpora01aa02}). For brevity, only |

2698 | (\ref{dbpora01aa00}) will be developed---i.e. we |

2699 | will consider only placing $r_A$ at or to the left |

2700 | of $r_I$. Also for brevity, only |

2701 | $F(x)$ as a model function will be |

2702 | considered. All other cases can be developed |

2703 | using similar methods. |

2704 | |

2705 | \begin{equation} |

2706 | \label{dbpora01aa00} |

2707 | r_I - \frac{1}{2^q} < r_A \leq r_I |

2708 | \end{equation} |

2709 | |

2710 | \begin{equation} |

2711 | \label{dbpora01aa01} |

2712 | r_I - \frac{1}{2^{q+1}} \leq r_A < r_I + \frac{1}{2^{q+1}} |

2713 | \end{equation} |

2714 | |

2715 | \begin{equation} |

2716 | \label{dbpora01aa02} |

2717 | r_I - \frac{1}{2^{q+1}} < r_A \leq r_I + \frac{1}{2^{q+1}} |

2718 | \end{equation} |

2719 | |

2720 | \begin{equation} |

2721 | \label{dbpora01aa03} |

2722 | r_I \leq r_A < r_I + \frac{1}{2^q} |

2723 | \end{equation} |

2724 | |

2725 | Placing $r_A$ consistently at or to the left |

2726 | of $r_I$ (\ref{dbpora01aa00}) will be accomplished |

2727 | if $h$ is chosen by (\ref{eq:dbpora03}). |

2728 | |

2729 | \begin{equation} |

2730 | \label{eq:dbpora03} |

2731 | h = \left\lfloor {r_I 2^q} \right\rfloor |

2732 | \end{equation} |

2733 | |

2734 | When $h$ is selected using (\ref{eq:dbpora03}), |

2735 | $r_A \leq r_I$ and (\ref{eq:dbpora05}) applies. |

2736 | |

2737 | \begin{equation} |

2738 | \label{eq:dbpora05} |

2739 | r_A - r_I \in \left( { - \frac{1}{2^q} , 0 } \right] |

2740 | \end{equation} |

2741 | |

2742 | To obtain a relationship |

2743 | (B,C)$\to$(A) (Fig. \ref{figthreeelementsofchoice}), |

2744 | (\ref{eq:dbpora05}) may be |

2745 | substituted into (\ref{eq:eq0035b}) |

2746 | to yield (\ref{eq:dbpora03baa}). |

2747 | |

2748 | \begin{figure*} |

2749 | \begin{equation} |

2750 | \label{eq:dbpora03baa} |

2751 | \left. {M(x) - F(x)} \right|_{x \in [0,x_{MAX}], r_A - r_I \in \left( {- \frac{1}{2^q}, 0} \right] } |

2752 | \in |

2753 | \left( {\frac{- x_{MAX} + z + 1}{2^q} - r_{IMAX} - 1, \frac{z}{2^q}} \right] |

2754 | \end{equation} |

2755 | \end{figure*} |

2756 | |

2757 | To obtain a relationship (A,B)$\to$(C), define |

2758 | $\varepsilon_{SPAN}$ as the |

2759 | maximum span of error with a fixed |

2760 | $z$ and fixed $r_I$ as $x$ is allowed to vary |

2761 | throughout $[0,x_{MAX}]$ (Eq. \ref{eq:eq0035b}). It can be shown |

2762 | by solving (\ref{eq:eq0035b}) that |

2763 | $q$ must be chosen so as to meet (\ref{eq:dbpora03ba}) if |

2764 | the error span is not to exceed |

2765 | $\varepsilon_{SPAN}$. (\ref{eq:dbpora03ca}) supplies the |

2766 | smallest choice of $q$ which |

2767 | satisfies (\ref{eq:dbpora03ba}). |

2768 | |

2769 | \begin{equation} |

2770 | \label{eq:dbpora03ba} |

2771 | q \geq \log{}_2 \left( {\frac{x_{MAX} - 1}{\varepsilon{}_{SPAN} - r_{IMAX} - 1}} \right) |

2772 | \end{equation} |

2773 | |

2774 | \begin{figure*} |

2775 | \begin{equation} |

2776 | \label{eq:dbpora03ca} |

2777 | q |

2778 | = |

2779 | \left\lceil |

2780 | { |

2781 | \log{}_2 \left( {\frac{x_{MAX} - 1}{\varepsilon{}_{SPAN} - r_{IMAX} - 1}} \right) |

2782 | } |

2783 | \right\rceil |

2784 | = |

2785 | \left\lceil |

2786 | { |

2787 | \frac |

2788 | { |

2789 | { |

2790 | \ln{} \left( \displaystyle{{\frac{x_{MAX} - 1}{\varepsilon{}_{SPAN} - r_{IMAX} - 1}}} \right) |

2791 | } |

2792 | } |

2793 | { |

2794 | \ln 2 |

2795 | } |

2796 | } |

2797 | \right\rceil |

2798 | \end{equation} |

2799 | \end{figure*} |

2800 | |

2801 | |

2802 | $q$ may be chosen larger than |

2803 | suggested by (\ref{eq:dbpora03ca}), but not smaller, |

2804 | while still meeting (\ref{eq:dbpora03ba}). In practice, |

2805 | this may be done because it is economical |

2806 | to choose $q$ to be a multiple of eight so that |

2807 | the division by $2^q$ is accomplished by ignoring |

2808 | the least significant byte(s) of $hx+z$, rather than by |

2809 | shifting. (This technique, however, will eliminate |

2810 | shifting at the expense of $h_{MAX}$, and |

2811 | usually only makes sense when $h_{MAX}$ can be |

2812 | increased without choosing different |

2813 | processor instructions |

2814 | to calculate $hx+z$.) |

2815 | |

2816 | Once $q$ is fixed, $h_{MAX}$ can be |

2817 | calculated. Substituting $r_I = r_{IMAX}$ |

2818 | into (\ref{eq:dbpora03}) yields (\ref{eq:dbpora03d}). |

2819 | |

2820 | \begin{equation} |

2821 | \label{eq:dbpora03d} |

2822 | h_{MAX} = \left\lfloor {r_{IMAX} 2^q} \right\rfloor |

2823 | \end{equation} |

2824 | |

2825 | |

2826 | |

2827 | \subsection{Design By Placement Of $L(x_{MAX})$} |

2828 | |

2829 | A second useful paradigm of design is to |

2830 | consider the problem of engineering a |

2831 | tabulated $h/2^q$ scaling in terms of what abilities |

2832 | we preserve for placing the terminal point |

2833 | $L(x_{MAX})$ with respect to the terminal |

2834 | point of the model function $I(x)$, $I(x_{MAX})$, |

2835 | $\lxtermdifffuncsymbol{}_L \leq 0 \leq \lxtermdifffuncsymbol{}_U$, |

2836 | so that (\ref{eq:errplace02a}) is met |

2837 | (Fig \ref{fig:specdomainrangerectangular}). |

2838 | |

2839 | \begin{eqnarray} |

2840 | \label{eq:errplace02a} |

2841 | & |

2842 | I(x_{MAX}) + \lxtermdifffuncsymbol{}_L |

2843 | \leq |

2844 | L(x_{MAX}) |

2845 | \leq |

2846 | I(x_{MAX}) + \lxtermdifffuncsymbol{}_U |

2847 | & |

2848 | \\ |

2849 | & \displaystyle{\Downarrow} & \nonumber |

2850 | \\ |

2851 | \label{eq:errplace02b} |

2852 | & |

2853 | r_A - r_I \in |

2854 | \left( |

2855 | { |

2856 | \displaystyle |

2857 | { |

2858 | \frac{\lxtermdifffuncsymbol{}_L - 1}{x_{MAX}}, |

2859 | \frac{\lxtermdifffuncsymbol{}_U + 1}{x_{MAX}} |

2860 | } |

2861 | } \right) |

2862 | & |

2863 | \end{eqnarray} |

2864 | |

2865 | \begin{figure} |

2866 | \caption{Specification Of Domain And Possible Values Of $r_I$ As Rectangular |

2867 | Region}\begin{picture}(240,140) |

2868 | \label{fig:specdomainrangerectangular} |

2869 | |

2870 | \put(25,20){\line(1,0){142}} |

2871 | \put(25,20){\line(0,1){110}} |

2872 | \put(25,20){\line(3,2){142}} |

2873 | \put(25,20){\line(5,2){142}} |

2874 | |

2875 | \put(167,20){\dashbox{.5}(0,110)} |

2876 | \put(25,130){\dashbox{.5}(142,0)} |

2877 | \put(12,75){\makebox(0,0){$\scriptstyle L(x)$}} |

2878 | \put(12,130){\makebox(0,0){$\scriptstyle y_{MAX}$}} |

2879 | |

2880 | \put(98,12){\makebox(0,0){$\scriptstyle x$}} |

2881 | \put(168,12){\makebox(0,0){$\scriptstyle x_{MAX}$}} |

2882 | |

2883 | \put(212,115){\makebox(0,0){$\scriptstyle (x_{MAX}, I(x_{MAX})+ \lxtermdifffuncsymbol{}_U)$}} |

2884 | \put(204,96){\makebox(0,0){$\scriptstyle (x_{MAX}, L(x_{MAX}))$}} |

2885 | \put(212,77){\makebox(0,0){$\scriptstyle (x_{MAX}, I(x_{MAX})+ \lxtermdifffuncsymbol{}_L)$}} |

2886 | |

2887 | \put(167,115){\circle*{4}} |

2888 | \put(167,96){\circle*{4}} |

2889 | \put(167,77){\circle*{4}} |

2890 | |

2891 | \put(55, 120){\makebox(0,0){\small{Rectangular}}} |

2892 | \put(55, 110){\makebox(0,0){\small{Region Of}}} |

2893 | \put(55, 100){\makebox(0,0){\small{Required}}} |

2894 | \put(55, 90){\makebox(0,0){\small{Placeability}}} |

2895 | |

2896 | \end{picture} |

2897 | \end{figure} |

2898 | |

2899 | (\ref{eq:errplace02a}) places restrictions |

2900 | on the relationship between |

2901 | $r_A$ and $r_I$, and implies (\ref{eq:errplace02b}). |

2902 | This implication is |

2903 | not reversible. |

2904 | |

2905 | For brevity, only $F(x)$ will be considered |

2906 | as a model function and only |

2907 | $L(x)$ will be considered as an approximation. |

2908 | To obtain a relationship |

2909 | which shows how the choice of |

2910 | $\lxtermdifffuncsymbol{}_L$ |

2911 | and |

2912 | $\lxtermdifffuncsymbol{}_U$ |

2913 | affect the error function |

2914 | $L(x) - F(x)$, |

2915 | (\ref{eq:errplace02b}) may be substituted |

2916 | into (\ref{eq:eq0035b}) to |

2917 | yield (\ref{eq:dbpolxmax01}). |

2918 | |

2919 | \begin{figure*} |

2920 | \begin{equation} |

2921 | \label{eq:dbpolxmax01} |

2922 | \left. {L(x) - F(x)} |

2923 | \right|_{ |

2924 | x \in [0,x_{MAX}], |

2925 | r_A - r_I \in |

2926 | \left( |

2927 | { |

2928 | \frac{\lxtermdifffuncsymbol{}_L - 1}{x_{MAX}}, |

2929 | \frac{\lxtermdifffuncsymbol{}_U + 1}{x_{MAX}} |

2930 | } |

2931 | \right) |

2932 | } |

2933 | \in |

2934 | \left( |

2935 | { |

2936 | \lxtermdifffuncsymbol{}_L - 1 - r_A - \frac{2^q - 1}{2^q}, |

2937 | \lxtermdifffuncsymbol{}_L + 1 |

2938 | } |

2939 | \right) |

2940 | \end{equation} |

2941 | \end{figure*} |

2942 | |

2943 | The ability to place the target |

2944 | point $L(x_{MAX})$ in the interval |

2945 | indicated in (\ref{eq:errplace02a}) requires (\ref{eq:errplace03}). Solving |

2946 | for $q$ leads to the constraint in |

2947 | (\ref{eq:errplace04}) and the smallest possible choice |

2948 | of $q$ in (\ref{eq:errplace05}). |

2949 | |

2950 | \begin{equation} |

2951 | \label{eq:errplace03} |

2952 | \frac{1}{2^q} \leq \frac{\lxtermdifffuncsymbol{}_U - \lxtermdifffuncsymbol{}_L + 1}{x_{MAX}} |

2953 | \end{equation} |

2954 | |

2955 | \begin{equation} |

2956 | \label{eq:errplace04} |

2957 | q \geq \log_2 \left({\frac{x_{MAX}}{\lxtermdifffuncsymbol{}_U - \lxtermdifffuncsymbol{}_L + 1}} \right) |

2958 | \end{equation} |

2959 | |

2960 | \begin{figure*} |

2961 | \begin{equation} |

2962 | \label{eq:errplace05} |

2963 | q = \left\lceil {\log _2 \left( {\frac{x_{MAX}}{\lxtermdifffuncsymbol{}_U - \lxtermdifffuncsymbol{}_L + 1}} \right) } \right\rceil |

2964 | = \left\lceil {\frac{\ln \left( \displaystyle{{\frac{x_{MAX}}{\lxtermdifffuncsymbol{}_U - \lxtermdifffuncsymbol{}_L + 1}}} \right) }{\ln 2}} \right\rceil |

2965 | \end{equation} |

2966 | \end{figure*} |

2967 | |

2968 | With $q$ chosen by (\ref{eq:errplace04}) |

2969 | or (\ref{eq:errplace05}), $h$ can be chosen by |

2970 | (\ref{eq:errplace07}) so as to meet (\ref{eq:errplace02a}). |

2971 | |

2972 | \begin{equation} |

2973 | \label{eq:errplace07} |

2974 | h = \left\lceil {\frac{2^{q} \left( {\left\lfloor {r_I x_{MAX}} \right\rfloor} + \lxtermdifffuncsymbol{}_L\right)}{x_{MAX}}} \right\rceil |

2975 | \end{equation} |

2976 | |

2977 | (\ref{eq:errplace03}) through (\ref{eq:errplace05}) |

2978 | give useful rules of thumb |

2979 | for sizing $q$ based on allowed variability in |

2980 | $L(x_{MAX})$. There are two |

2981 | additional useful practical applications for the paradigm |

2982 | of thought |

2983 | (\emph{observation} implies \emph{scaling factor}), |

2984 | and for the equations themselves. |

2985 | |

2986 | The first additional practical application (for the |

2987 | paradigm of thought) is in the error analysis of |

2988 | self-calibrating systems. In Example |

2989 | \ref{ex:bathroomscale}, it is assumed that we |

2990 | precisely know |

2991 | the transfer characteristics of each |

2992 | bathroom scale transducer and can thereby |

2993 | choose $h$. A practical bathroom scale |

2994 | is more likely to be self-calibrating, so that |

2995 | at manufacture |

2996 | a known calibration weight $x_{CAL} \in \realsetnonneg{}$ |

2997 | can be placed on the |

2998 | scale and the scale itself will determine the |

2999 | transfer characteristics of the transducer |

3000 | and choose $h$.\footnote{In this discussion |

3001 | and in (\ref{eq:errselfcal01}) and (\ref{eq:errselfcal02}), |

3002 | $r_I$ is taken to be the transfer characteristic of |

3003 | of the transducer; whereas in Example \ref{ex:bathroomscale}, |

3004 | $1/r_I$ is the transfer characteristic of the transducer, |

3005 | and $r_I$ is the desired transfer characteristic of the |

3006 | linear scaling in the software.} |

3007 | For a self-calibrating scale, |

3008 | an important question is if a known calibration |

3009 | weight $x_{CAL}$ is placed on the scale and produces an |

3010 | A/D converter count $y_{CAL} = H(x_{CAL})$, how much can be inferred |

3011 | about the underlying $r_I$ of the transducer? It can be shown |

3012 | that the implication relationship in |

3013 | (\ref{eq:errselfcal01}) and (\ref{eq:errselfcal02}) applies. |

3014 | This self-calibration uncertainty should not be neglected |

3015 | in error analyses. Note in (\ref{eq:errselfcal02}) |

3016 | that the self-calibration |

3017 | uncertainty in $r_I$ decreases with increasing |

3018 | $x_{CAL}$, which is consistent with intuition. |

3019 | |

3020 | \begin{eqnarray} |

3021 | \label{eq:errselfcal01} |

3022 | & |

3023 | y_{CAL} = H(x_{CAL}) = \lfloor r_I x_{CAL} \rfloor |

3024 | & |

3025 | \\ |

3026 | & \displaystyle{\Downarrow} & \nonumber |

3027 | \\ |

3028 | \label{eq:errselfcal02} |

3029 | & |

3030 | r_I \in |

3031 | \left[ |

3032 | { |

3033 | \displaystyle |

3034 | { |

3035 | \frac{y_{CAL}}{x_{CAL}}, \frac{y_{CAL}}{x_{CAL}} + \frac{1}{x_{CAL}} |

3036 | } |

3037 | } |

3038 | \right) |

3039 | & |

3040 | \end{eqnarray} |

3041 | |

3042 | The second additional practical application |

3043 | (for the equations) is the special case of |

3044 | $\lxtermdifffuncsymbol{}_L = \lxtermdifffuncsymbol{}_U = 0$, |

3045 | which is useful in devising |

3046 | a tabulated linear scaling for |

3047 | piecewise linear functions when |

3048 | the linear segments must join neatly, or when the required |

3049 | accuracy of a linear scaling is not known |

3050 | precisely in advance and a reasonable |

3051 | default tabulated scaling strategy must be chosen. |

3052 | Theorem \ref{thm:fullplaceability} |

3053 | supplies a choice of $q$ and a result |

3054 | about $h_{MAX}$ which is useful in such cases. |

3055 | |

3056 | \begin{theorem} |

3057 | \label{thm:fullplaceability} |

3058 | Given a rational linear scaling of |

3059 | the form (\ref{eq:eq0009}) with an $m$-bit |

3060 | domain and an $n$-bit range, |

3061 | choosing $q=m$ and |

3062 | $h_{MAX} = 2^{m+n} - 1$ |

3063 | (i.e. choosing a data width of |

3064 | $m+n$ bits for $h$) will allow |

3065 | an $h$ to be chosen |

3066 | so that $L(x') = y'$ for any |

3067 | $x' \in [1, x_{MAX} = 2^m - 1]_\intset{}, \; y' \in [0, y_{MAX} = 2^n - 1]_\intset{}$. |

3068 | \end{theorem} |

3069 | |

3070 | \begin{proof} |

3071 | At $x' = x_{MAX}$, in order to be able |

3072 | to choose $y'$, it is required that |

3073 | $x_{MAX}/2^q \leq 1$, and $q = m$ is |

3074 | the smallest integral choice of $q$ that will |

3075 | satisfy this constraint. |

3076 | With $q=m$, |

3077 | $L(1) = y_{MAX}$ requires |

3078 | $h_{MAX}/2^m \geq y_{MAX}$, and |

3079 | $h_{MAX} = 2^{m+n}-1$ (a bit-width |

3080 | of at least $m+n$ for $h$) is required. |

3081 | \end{proof} |

3082 | |

3083 | |

3084 | |

3085 | |

3086 | % (6) IMPLEMENTATION CONSIDERATIONS AND TECHNIQUES % |

3087 | |

3088 | |

3089 | \section{Implementation Techniques} |

3090 | \label{sec:imptechniques} |

3091 | |

3092 | Practical microprocessors fall into the |

3093 | following categories, ranked from |

3094 | least capable to most capable. |

3095 | |

3096 | \begin{generalenum} |

3097 | |

3098 | \item Processors with shift and addition instructions. |

3099 | |

3100 | \item Processors with shift, addition, and multiplication instructions.\footnote{To |

3101 | date, the authors have not encountered a processor with division instructions but no |

3102 | multiplication instructions.} |

3103 | |

3104 | \item Processors with shift, addition, multiplication, and division instructions. |

3105 | |

3106 | \end{generalenum} |

3107 | |

3108 | Shift instructions, |

3109 | addition instructions, |

3110 | and multiplication instructions |

3111 | are always \emph{scaleable}, |

3112 | meaning that operands of arbitrary |

3113 | size can be shifted, added, or multiplied by the |

3114 | repeated use of instructions which |

3115 | inherently accept smaller operands. |

3116 | Division instructions, however, are not scaleable. No general |

3117 | method exists to use processor division instructions to divide |

3118 | operands of arbitrary size. |

3119 | |

3120 | For multiplication, certain values of $h$ can lead |

3121 | to especially economical implementations. Multiplication by |

3122 | an $h$ which |

3123 | is an integral power of two can be performed using |

3124 | shift instructions. Multiplication by an $h$ |

3125 | whose bit pattern is very sparsely populated with |

3126 | 1's can also lead to an economical implementation. |

3127 | For example, multiplication by $h=33_{10}=100001_2$ |

3128 | can be performed using five left shifts and an addition. |

3129 | For division, a value of $k$ which is an integral power |

3130 | will lead to a very economical implementation. |

3131 | |

3132 | The following steps are recommended to economize |

3133 | an $(hx+z)/k$ |

3134 | linear scaling for implementation. |

3135 | |

3136 | \begin{generalenum} |

3137 | |

3138 | \item If the processor does not have a division instruction to |

3139 | directly support the integer division by $k$, |

3140 | use an $(hx+z)/2^q$ scaling rather than an $(hx+z)/k$ scaling (due |

3141 | to the high cost of division in software). |

3142 | |

3143 | \item If the bit pattern of $h$ is sparsely populated with 1's, evaluate |

3144 | implementation of the multiplication via |

3145 | repeated left-shifting and addition. |

3146 | |

3147 | \end{generalenum} |

3148 | |

3149 | |

3150 | |

3151 | |

3152 | % (7) DESIGN EXAMPLES % |

3153 | |

3154 | |

3155 | \section{Design Examples} |

3156 | \label{sec:designexamples} |

3157 | |

3158 | |

3159 | |

3160 | |

3161 | % (7)(B) CONVERSION FROM MPH TO KPH % |

3162 | |

3163 | |

3164 | \begin{example} |

3165 | \label{ex:convmphkphatend} |

3166 | (CONVERSION FROM MPH TO KPH) Devise an economical and |

3167 | accurate linear scaling algorithm |

3168 | from integral MPH to integral KPH which operates over a domain |

3169 | of $[0, 255]_{\intset{}}$ MPH (one unsigned byte) and delivers an |

3170 | unsigned byte in $[0,255]_{\intset{}}$ KPH, and |

3171 | bound the error introduced by the scaling, |

3172 | assuming that the input speed is quantized (already contains error). |

3173 | The error between actual speed (before input |

3174 | quantization) and the output of the algorithm |

3175 | must never be negative---i.e. the output of the algorithm must |

3176 | never \emph{under}state the speed. In the event that |

3177 | the result is too large for one byte, the result |

3178 | should be 255. Implement the algorithm on a TMS370 |

3179 | CPU core, which is characterized by an 8$\times$8=16 |

3180 | unsigned multiplication instruction and a 16$\times$8=8 |

3181 | division instruction. |

3182 | \end{example} |

3183 | |

3184 | \emph{Solution:} |

3185 | One mile is 1.6093 kilometers, thus $r_I = 1.6093$. |

3186 | Efficient implementation using the instruction |

3187 | set of the TMS370 is best done by a single multiplication |

3188 | instruction followed by a single division instruction, implying |

3189 | that $h_{MAX} = k_{MAX} = 255$. Applying |

3190 | Theorem \ref{thm:thmconstrainednumerator} |

3191 | yields $N'=159$, so it is only necessary to |

3192 | examine $F_{159}$ for the |

3193 | two enclosing rational numbers |

3194 | which meet the constraints on numerator and denominator.\footnote{Theorem \ref{thm:thmconstrainednumerator} |

3195 | must be applied with caution, as it only guarantees that the |

3196 | \emph{two enclosing} rational numbers are in $F_{159}$. Table \ref{tbl:fareymphtokph01} |

3197 | is included to show the construction of $F_{159}$---it should be noted that |

3198 | without further analysis there is no guarantee that there are not |

3199 | rational numbers which meet the constraints to the left of 243/151 |

3200 | with $k>159$.} |

3201 | Building $F_{159}$ near 1.6093 |

3202 | yields Table \ref{tbl:fareymphtokph01}.\footnote{Table |

3203 | \ref{tbl:fareymphtokph01} can be built using spreadsheet |

3204 | software to construct $F_{159}$ starting with |

3205 | the rational numbers |

3206 | 1/1 and 160/159 and using |

3207 | (\ref{eq:eq0051}) and |

3208 | (\ref{eq:eq0052}) to build increasing Farey |

3209 | terms until $r_I$ is enclosed.} |

3210 | |

3211 | \begin{table} |

3212 | \caption{$F_{159}$ Near 1.6093 (Example \ref{ex:convmphkphatend})} |

3213 | \label{tbl:fareymphtokph01} |

3214 | \begin{center} |

3215 | \begin{tabular}{|c|c|c|c|} |

3216 | \hline |

3217 | $h$ & $k$ & $h/k$ & Error \\ |

3218 | \hline |

3219 | \hline |

3220 | 214 & 133 & 1.60902256 & -0.00027744 \\ |

3221 | \hline |

3222 | 177 & 110 & 1.60909091 & -0.00020909 \\ |

3223 | \hline |

3224 | 140 & 87 & 1.60919540 & -0.00010460 \\ |

3225 | \hline |

3226 | 243 & 151 & 1.60927152 & -0.00002848 \\ |

3227 | \hline |

3228 | 103 & 64 & 1.60937500 & +0.00007500 \\ |

3229 | \hline |

3230 | 169 & 105 & 1.60952381 & +0.00022381 \\ |

3231 | \hline |

3232 | 235 & 146 & 1.60958904 & +0.00028904 \\ |

3233 | \hline |

3234 | 227 & 141 & 1.60992908 & +0.00062903 \\ |

3235 | \hline |

3236 | \end{tabular} |

3237 | \end{center} |

3238 | \end{table} |

3239 | |

3240 | From Table \ref{tbl:fareymphtokph01}, |

3241 | the two rational numbers which enclose |

3242 | 1.6093 are 243/151 and 103/64. |

3243 | Choosing $r_A = 243/151$\footnote{From |

3244 | Table \ref{tbl:fareymphtokph01}, |

3245 | 103/64 also appears to be |

3246 | an attractive rational number, |

3247 | because the division by 64 can be accomplished |

3248 | by shifting $hx+z$ right by 5 bits. |

3249 | However, with the TMS370, each shift of a |

3250 | 16-bit operand requires two \texttt{RRC} |

3251 | instructions, for a total of 10 instructions |

3252 | at 8 clock cycles each, or 80 clock cycles |

3253 | (more than the \texttt{DIV} |

3254 | instruction). Therefore, 243/151 is the |

3255 | more attractive rational number.} |

3256 | and using |

3257 | $x_{MAX}=256$\footnote{A value of 256 rather |

3258 | than 255 must be used for $x_{MAX}$ because |

3259 | it is assumed that |

3260 | $x \in [0,256)$.} with |

3261 | $z = 395$ by (\ref{eq:eqkminusfzterm01}) |

3262 | leads to the assembly-language shown |

3263 | in Fig. \ref{fig:tms370c8code243151}. |

3264 | |

3265 | \begin{figure} |

3266 | \caption{TMS370 Solution To Example \ref{ex:convmphkphatend} Using The Rational |

3267 | Number 243/151} |

3268 | \label{fig:tms370c8code243151} |

3269 | \begin{verbatim} |

3270 | |

3271 | MOV input, A ;12 cycles, load far input |

3272 | ;into A |

3273 | MPY #243, A ;45 cycles, multiply by 243, |

3274 | ;result in (MSB:LSB)=(A:B) |

3275 | ADD #139, B ;6 cycles, 139 = 395 mod 256 |

3276 | ADC #1, A ;6 cycles, 1 = 395 div 256 |

3277 | MOV #151, R02 ;8 cycles, set up for divide |

3278 | DIV R02, A ;Max 63 cycles, divide, |

3279 | ;quotient in A, carry set if |

3280 | ;overflow |

3281 | JNC NOOVERFLOW ;5 cycles if jump not taken |

3282 | ;7 cycles if jump taken |

3283 | ;Jump if div without overflow |

3284 | MOV #255, A ;6 cycles, replace div result |

3285 | ;if too large and won't fit in |

3286 | ;one byte. DIV instruction |

3287 | ;set C on overflow |

3288 | NOOVERFLOW: ;Label, no code generated |

3289 | MOV A, output ;10 cycles, move result to |

3290 | ;far output var |

3291 | |

3292 | (Total: Max. 161 clocks, 53.7us with 12 Mhz |

3293 | crystal.) |

3294 | \end{verbatim} |

3295 | \end{figure} |

3296 | |

3297 | From the problem statement, the input to the algorithm |

3298 | is assumed to be quantized (it already contains error), |

3299 | so (\ref{eq:eq0035b}) applies. Evaluating |

3300 | (\ref{eq:eq0035b}) with $r_A = 243/151$, $z=395$, $r_I = 1.6093$ |

3301 | and $x_{MAX}=256$ yields $K(x)-F(x) \in (0.0060, 2.6159]$ KPH |

3302 | over the domain [0,256). |

3303 | |

3304 | |

3305 | |

3306 | |

3307 | % (7)(F) BATHROOM SCALE % |

3308 | |

3309 | |

3310 | |

3311 | \begin{example} |

3312 | \label{ex:bathroomscale} |

3313 | (BATHROOM SCALE) |

3314 | A manufacturer wishes to build a family of |

3315 | electronic bathroom scales using linear transducers |

3316 | which convert weight to voltage. The voltage |

3317 | from a transducer is measured using a 10-bit |

3318 | A/D converter and a custom combinational logic integrated |

3319 | circuit which will multiply the integer |

3320 | $x \in [0, 2^{10}-1]_{\intset{}}$ from the A/D |

3321 | converter by a programmable calibration |

3322 | constant $h$, neglect a number $q$ of |

3323 | least significant bits of the product |

3324 | $hx$, and display the non-neglected |

3325 | bits as a weight, in integral pounds, for the user. |

3326 | In the event that the A/D converter is saturated |

3327 | ($x=2^{10}-1=1,023$), an overflow indicator will |

3328 | be displayed. The transducers to be used |

3329 | always produce exactly zero volts with no |

3330 | weight applied, but vary from 0.25 lbs. per A/D |

3331 | count to 0.35 lbs. per A/D count in their |

3332 | transfer characteristic. Market research has |

3333 | shown that users strongly dislike bathroom |

3334 | scales which overstate their weight; but simultaneously |

3335 | prefer that their weight not be understated by more |

3336 | than 2 lbs. In the design of the custom |

3337 | integrated circuit for the family of bathroom scales, what |

3338 | value of $q$ should be chosen? How accurate will |

3339 | each bathroom scale be? |

3340 | How many bits must be reserved for $h$, and |

3341 | what strategy should be |

3342 | used to choose |

3343 | $h$ based on the transfer characterisic |

3344 | $r_I$ of each transducer? |

3345 | \end{example} |

3346 | |

3347 | \emph{Solution:} |

3348 | From the problem statement, |

3349 | $r_I \in [0.25, 0.35]$, |

3350 | $r_{IMAX} = 0.35$, |

3351 | $x_{MAX} = 1,023$\footnote{From the |

3352 | problem statement, $x=1,023$ will |

3353 | generate an overflow display, so we need |

3354 | not consider $x \in [1,023, \; 1,024)$.}, and it is |

3355 | required that |

3356 | $L(x)-F(x) \in [-2,0]$. It is also |

3357 | required that $r_A \leq r_I$ |

3358 | (as in Eqs. \ref{eq:dbpora03}, \ref{eq:dbpora05}); otherwise |

3359 | it is possible that |

3360 | $\exists x \in [0,x_{MAX}]$, $L(x) > F(x)$, which |

3361 | contradicts the product requirements. |

3362 | |

3363 | With $x_{MAX} = 1,023$, |

3364 | $\varepsilon_{SPAN} = 2$, and $r_{IMAX} = 0.35$, |

3365 | (\ref{eq:dbpora03ca}) yields $q=11$ as the |

3366 | minimum choice for $q$ to meet accuracy |

3367 | requirements. |

3368 | |

3369 | With $x_{MAX} = 1,023$, |

3370 | $z=0$, |

3371 | $q=11$, |

3372 | $2^q = 2,048$, |

3373 | and $r_{IMAX} = 0.35$, |

3374 | (\ref{eq:dbpora03baa}) |

3375 | predicts that |

3376 | $L(x)-F(x) \in (-1.84,0]$. |

3377 | |

3378 | With |

3379 | $q=11$, |

3380 | $2^q = 2,048$, and |

3381 | $r_{IMAX} = 0.35$, |

3382 | (\ref{eq:dbpora03d}) |

3383 | yields $h_{MAX} = 716$ and |

3384 | 10 bits must be reserved |

3385 | in the custom integrated circuit |

3386 | for the calibration factor $h$. |

3387 | For each $r_I$ to be tabulated, |

3388 | $h$ should be chosen by (\ref{eq:dbpora03}): |

3389 | $h=\lfloor r_I 2^q \rfloor = \lfloor 2,048 r_I \rfloor$. |

3390 | |

3391 | |

3392 | |

3393 | |

3394 | % (8) CONCLUSION % |

3395 | |

3396 | |

3397 | \section{Conclusion} |

3398 | |

3399 | The techniques presented in this paper |

3400 | demonstrate how linear scaling |

3401 | functions of the form $y = r_I x$ |

3402 | ($r_I \in \realsetnonneg{}$, |

3403 | not necessarily $\in \ratsetnonneg$) can be |

3404 | implemented on inexpensive 4-bit and |

3405 | 8-bit microcontrollers by |

3406 | approximating $r_I$ with a rational |

3407 | scaling factor $r_A = h/k$ |

3408 | ($h \in \intsetnonneg{}$, |

3409 | $k \in \intsetpos{}$). |

3410 | Several methods for choosing $h$ and $k$ |

3411 | and several implementation techniques were |

3412 | presented. |

3413 | |

3414 | A detailed analysis of approximation error |

3415 | due to the inability to choose $r_A = r_I$ and |

3416 | due to the quantization inherent |

3417 | in digital systems and integer |

3418 | arithmetic was provided. It was shown that |

3419 | the approximation error |

3420 | can be bounded when it is known that the |

3421 | approximation will be used only over a domain of |

3422 | $[0, x_{MAX}]$, $x_{MAX} \in \intsetpos{}$. |

3423 | It was also shown that |

3424 | by introducing an integral parameter |

3425 | $z$, |

3426 | the error function could |

3427 | be adjusted to be |

3428 | never negative, never positive, or centered about zero. |

3429 | |

3430 | For cases where $r_I$ is known |

3431 | at design time, three algorithms were presented |

3432 | that allow $h$ and $k$ to be chosen |

3433 | subject to the constraints |

3434 | $h \leq h_{MAX}$ and $k \leq k_{MAX}$ |

3435 | so as to place $r_A = h/k$ as close as |

3436 | possible to $r_I$. For cases where $r_I$ is not |

3437 | precisely known at design time, |

3438 | methods were presented for designing |

3439 | tabulated scalings and bounding the approximation |

3440 | error introduced. |

3441 | |

3442 | Important results from number theory were presented which |

3443 | show that although the worst-case error in placing |

3444 | $r_A$ decreases as $1/N$, the typical error decreases |

3445 | as $1/N^2$. |

3446 | |

3447 | Techniques which allow linear approximations to be |

3448 | performed economically on microcontrollers of varying capability |

3449 | were also presented. It was shown how the form of $r_A=h/k$ |

3450 | could be modified to improve software efficiency, enable use of only |

3451 | scaleable (non-division) instructions, or facilitate |

3452 | tabulation of scaling |

3453 | factors. |

3454 | |

3455 | |

3456 | |

3457 | |

3458 | % (9) ACKNOWLEDGEMENTS % |

3459 | |

3460 | |

3461 | %Need to retain e-mail addresses to contact all people who have contributed |

3462 | %to thank. |

3463 | %Greg Bachelis (greg@math.wayne.edu) |

3464 | %Robert Berman (rberman@math.wayne.edu) |

3465 | %Feng Lin (flin@ece.eng.wayne.edu) |

3466 | %Nick Sahinidis (nikos@uiuc.edu) |

3467 | %Adam Van Tuyl, (vantuyl@mast.queensu.ca) |

3468 | %Carl Schweiger (carl@titan.princeton.edu) |

3469 | %Ken Tindell (ktindell@ssx5.com) |

3470 | %Steve Vestal (vestal@htc.honeywell.com) |

3471 | %Bob Whitinger (bob@whitinger.net, bob.whitinger@sea.siemens.com) |

3472 | %David B. Stewart (dstewart@eng.umd.edu) |

3473 | %Johan Bengtsson (johanb@docs.uu.se) |

3474 | %Michael J. Burke (mburke@visteon.com) |

3475 | %Mark Endicott (mendicot@visteon.com) |

3476 | %David Eppstein (eppstein@ics.uci.edu) |

3477 | %Cliff Stallings (cliff@eng.wayne.edu) |

3478 | %Robert Kakos (robert@enterprise.eng.wayne.edu) |

3479 | %Klaus-Peter Zauner (kjz@cs.wayne.edu) |

3480 | %Karsten Tinnefeld (tinnefeld@ls2.cs.uni-dortmund.de) |

3481 | %Paulette Groen (pgroen@visteon.com) |

3482 | %Paula Smith (psmith77@visteon.com) |

3483 | %Mircea Munteanu (mmuntean@visteon.com) |

3484 | %Adam Gibson (adam.g@virgin.net) |

3485 | %Virgil (vmhjr@frii.com) |

3486 | %Bob Crosby (b-crosby@ti.com) |

3487 | %Una Smith (una.smith@yale.edu) |

3488 | %Andrea Blome (ablome@mail.cfigroup.com) |

3489 | %Axel Franke (Axel.Franke@physics.umu.se) |

3490 | %Yu-Tzu Tsai (ytsai@computer.org) |

3491 | %William J. Hagen (w.hagen@ieee.org) |

3492 | % |

3493 | % |

3494 | % |

3495 | %Need also to include Adam's Web site on my Web page, |

3496 | %http://archives.math.utk.edu/articles/atuyl/confrac/ |

3497 | % |

3498 | %Need also to include David Eppstein's Web site |

3499 | %http://www.ics.uci.edu/~eppstein/ |

3500 | % |

3501 | % |

3502 | \section{Acknowledgements} |

3503 | |

3504 | We would like to gratefully acknowledge the assistance |

3505 | of Greg Bachelis, Robert Berman, Feng |

3506 | Lin, Nick Sahinidis, Adam Van Tuyl, |

3507 | Carl Schweiger, Ken Tindell, Steve Vestal, |

3508 | Bob Whitinger, and David B. Stewart |

3509 | in finding the areas of |

3510 | mathematics relevant to the rational number selection |

3511 | problem. We would also like to |

3512 | thank Johan Bengtsson, Michael J. Burke, |

3513 | Mark Endicott, David Eppstein, Mircea Munteanu, |

3514 | Adam Gibson, and Virgil (of the \texttt{sci.math.num-analysis} newsgroup) |

3515 | for insight into this problem; Cliff Stallings and |

3516 | Robert Kakos for support from Wayne State |

3517 | University's College Of Engineering; Paulette Groen and |

3518 | Paula Smith for support from Visteon; |

3519 | Yu-Tzu Tsai and William J. Hagen for support |

3520 | from the IEEE; Bob Crosby for support |

3521 | from Texas Instruments; Klaus-Peter Zauner, Andrea Blome, |

3522 | Una Smith, Karsten Tinnefeld, and |

3523 | Axel Franke for other tool |

3524 | and logistical support; and the management |

3525 | team at Visteon for allowing us to pursue this |

3526 | effort in the workplace. |

3527 | |

3528 | |

3529 | |

3530 | |

3531 | % (13) VARIABLES AND MATHEMATICAL NOTATION % |

3532 | |

3533 | |

3534 | \section{Definitions, Acronyms, Abbreviations, Variables And Mathematical Notation} |

3535 | |

3536 | \begin{glossaryenum} |

3537 | |

3538 | \item \mbox{\boldmath $ \lfloor \cdot \rfloor $} |

3539 | |

3540 | Used to denote the \emph{floor($\cdot$)} function. The |

3541 | \emph{floor($\cdot$)} |

3542 | function is the largest integer not larger than the |

3543 | argument. |

3544 | |

3545 | \item \mbox{\boldmath $\lceil \cdot \rceil$ } |

3546 | |

3547 | Used to denote the \emph{ceiling($\cdot$)} function. |

3548 | The \emph{ceiling($\cdot$)} function |

3549 | is the smallest integer not smaller than the |

3550 | argument. |

3551 | |

3552 | \item \mbox {\boldmath $a/b$} |

3553 | |

3554 | An arbitrary rational number. |

3555 | |

3556 | \item \textbf{coprime} |

3557 | |

3558 | Two integers that share no prime factors are \emph{coprime}. |

3559 | \emph{Example:} |

3560 | 6 and 7 are coprime, whereas 6 and 8 are not. |

3561 | |

3562 | \item \mbox {\boldmath $ F_N $} |

3563 | |

3564 | The Farey series of order $N$. The Farey series is the |

3565 | ordered set of all reduced rational numbers with a |

3566 | denominator not larger than $N$. |

3567 | |

3568 | \item \textbf{greatest common divisor (g.c.d.)} |

3569 | The greatest common divisor of two integers is the largest |

3570 | integer which divides both integers without a remainder. |

3571 | \emph{Example:} the g.c.d. of 30 and 42 is 6. |

3572 | |

3573 | \item \mbox{\boldmath $H/K$}, \mbox{\boldmath $h/k$}, |

3574 | \mbox{\boldmath $h'/k'$}, \mbox{\boldmath $h''/k''$}, |

3575 | \mbox{\boldmath $h_i/k_i$} |

3576 | |

3577 | Terms in a Farey series of order $N$. |

3578 | |

3579 | \item \textbf{irreducible} |

3580 | |

3581 | A rational number $p/q$ where $p$ and $q$ are coprime |

3582 | is said to be \emph{irreducible}. |

3583 | Equivalently, it may be stated that $p$ and $q$ share no prime factors |

3584 | or that the greatest common divisor of |

3585 | $p$ and $q$ is 1. |

3586 | |

3587 | \item \textbf{KPH} |

3588 | |

3589 | Kilometers per hour. |

3590 | |

3591 | \item \textbf{MPH} |

3592 | |

3593 | Miles per hour. |

3594 | |

3595 | \item \mbox{\boldmath $\intsetpos$} |

3596 | |

3597 | The set of positive integers (natural numbers). |

3598 | |

3599 | \item \mbox{\boldmath $\ratset$} |

3600 | |

3601 | The set of rational numbers. |

3602 | |

3603 | \item \mbox{\boldmath $\ratsetnonneg$} |

3604 | |

3605 | The set of non-negative rational numbers. |

3606 | |

3607 | \item \mbox{\boldmath $r_A$} |

3608 | |

3609 | The rational number $h/k$ used to approximate |

3610 | an arbitrary real number $r_I$. |

3611 | |

3612 | \item \mbox{\boldmath $r_I$} |

3613 | |

3614 | The real number, which may or may not be rational, |

3615 | which is to be approximated by a rational number |

3616 | $r_A = h/k$. |

3617 | |

3618 | \item \mbox{\boldmath $\realset$} |

3619 | |

3620 | The set of real numbers. |

3621 | |

3622 | \item \mbox{\boldmath $\realsetnonneg$} |

3623 | |

3624 | The set of non-negative real numbers. |

3625 | |

3626 | \item \textbf{reduced} |

3627 | |

3628 | See \emph{irreducible}. |

3629 | |

3630 | \item \mbox{\boldmath $s_k = p_k/q_k$} |

3631 | |

3632 | The $k$th convergent of a continued fraction. |

3633 | |

3634 | \item \mbox{\boldmath $x_{MAX}$} |

3635 | |

3636 | The largest element of the domain for which the |

3637 | behavior of an approximation must be guaranteed. |

3638 | In this paper, most derivations assume |

3639 | that $x \in [0, x_{MAX}]$, $x_{MAX} \in \intsetpos{}$. |

3640 | |

3641 | \item \mbox{\boldmath $\intset$} |

3642 | |

3643 | The set of integers. |

3644 | |

3645 | \item \mbox{\boldmath $\intsetnonneg$} |

3646 | |

3647 | The set of non-negative integers. |

3648 | |

3649 | |

3650 | \end{glossaryenum} |

3651 | |

3652 | |

3653 | |

3654 | |

3655 | % (10) CONTACT INFORMATION % |

3656 | |

3657 | |

3658 | %\section{Contact} |

3659 | % |

3660 | %Additional supplemental materials (such as Excel |

3661 | %spreadsheets which generate Farey terms automatically) |

3662 | %are downloadable from http://www.daveashley.com. |

3663 | %E-mail addresses and home pages (where applicable) |

3664 | %for authors are supplied below. |

3665 | %David T. Ashley: |

3666 | % daveashley@daveashley.com |

3667 | % http://www.daveashley.com/ |

3668 | %Joseph P. DeVoe |

3669 | % jdevoe@visteon.com |

3670 | %Cory Pratt |

3671 | % cpratt2@visteon.com |

3672 | %Karl Perttunen |

3673 | % kperttun@visteon.com |

3674 | %Anatoly Zhigljavsky |

3675 | % zhigljavskyaa@cardiff.ac.uk |

3676 | % http:\-//\-www.\-cf.\-ac.\-uk/\-uwcc/\-maths/\-zhig\-ljav\-skyaa/ |

3677 | % |

3678 | % |

3679 | |

3680 | |

3681 | % (11) REFERENCES % |

3682 | |

3683 | |

3684 | \nocite{*} |

3685 | \bibliographystyle{IEEE_PQ} |

3686 | \begin{thebibliography}{1} |

3687 | |

3688 | \bibitem{HardyAndWrightClassic} |

3689 | G.H. Hardy, E.M. Wright, |

3690 | \newblock{\em An Introduction To The Theory Of Numbers}, ISBN 0-19-853171-0. |

3691 | |

3692 | \bibitem{Harman} |

3693 | G. Harman (1998) Metric number theory, Oxford University Press. |

3694 | |

3695 | \bibitem{KargaevZ} |

3696 | P. Kargaev, A. Zhigljavsky (1966) |

3697 | Approximation of real numbers by rationals: some metric theorems, |

3698 | {\it Journal of Number Theory,} 61, 209-225. |

3699 | |

3700 | \bibitem{KargaevZ1} |

3701 | P. Kargaev, A. Zhigljavsky (1967) |

3702 | Asymptotic distribution of the distance function to the Farey points |

3703 | {\it Journal of Number Theory,} 65, 130-149. |

3704 | |

3705 | \bibitem{KhinchinClassic} |

3706 | A. Ya. Khinchin, |

3707 | \newblock{\em Continued Fractions}, University Of |

3708 | Chicago Press, 1964; Library Of Congress Catalog Card |

3709 | Number 64-15819. |

3710 | |

3711 | \bibitem{LeVeque} |

3712 | William J. LeVeque, |

3713 | \newblock{\em Fundamentals Of Number Theory}, |

3714 | Dover Publications, 1977, |

3715 | ISBN 0-486-68906-9. |

3716 | |

3717 | \bibitem{OldsClassic} |

3718 | C. D. Olds, |

3719 | \newblock{\em Continued Fractions}, |

3720 | Randam House, 1963, |

3721 | Library Of Congress Catalog Card Number 61-12185. |

3722 | |

3723 | \bibitem{OreClassic} |

3724 | Oystein Ore, |

3725 | \newblock{\em Number Theory And Its History}, |

3726 | ISBN 0-486-65620-9. |

3727 | |

3728 | \bibitem{SchroederClassic} |

3729 | M. R. Schroeder, |

3730 | \newblock{\em Number Theory In Science And Communication}, |

3731 | ISBN 3-540-62006-0. |

3732 | |

3733 | \end{thebibliography} |

3734 | |

3735 | |

3736 | |

3737 | |

3738 | % (12) BIOGRAPHY % |

3739 | |

3740 | |

3741 | %The biography section applies only to the IEEE paper. Since the splitting |

3742 | %program is record-oriented but LaTeX is free-form, each line of the biographies |

3743 | %must be preceded by the _IEEE_ tag. |

3744 | \begin{biography}{David T. Ashley} |

3745 | (biography not yet included in document). |

3746 | \vspace{2.7cm} |

3747 | \end{biography} |

3748 | \begin{biography}{Joseph P. DeVoe} |

3749 | (biography not yet included in document). |

3750 | \vspace{2.7cm} |

3751 | \end{biography} |

3752 | \begin{biography}{Cory Pratt} |

3753 | (biography not yet included in document). |

3754 | \vspace{2.7cm} |

3755 | \end{biography} |

3756 | \begin{biography}{Karl Perttunen} |

3757 | (biography not yet included in document). |

3758 | \vspace{2.7cm} |

3759 | \end{biography} |

3760 | \begin{biography}{Anatoly Zhigljavsky} |

3761 | (biography not yet included in document). |

3762 | \vspace{2.7cm} |

3763 | \end{biography} |

3764 | |

3765 | \begin{figure*} |

3766 | \caption{Version Control Information (For Reference Only---Will |

3767 | Be Removed Before Submission Of Paper)} |

3768 | \vspace{3.0mm} |

3769 | \begin{small} |

3770 | \texttt{\LaTeX{} compile date: \today{}.} |

3771 | \begin{verbatim} |

3772 | PVCS version control information: |

3773 | $Header: /cvsroot/esrg/sfesrg/esrgdstb/common/suppmatls/papers_articles/embedded_control/uc_math/rat_app/ieee_rap_2000.txt,v 1.1 2002/04/24 07:23:58 dtashley Exp $. |

3774 | \end{verbatim} |

3775 | \end{small} |

3776 | \end{figure*} |

3777 | |

3778 | \end{document} |

3779 | |

3780 | |

3781 | %% $Log: ieee_rap_2000.txt,v $ |

3782 | %% Revision 1.1 2002/04/24 07:23:58 dtashley |

3783 | %% Initial checkin. |

3784 | %% |

3785 | %% |

3786 | %% Rev 1.62 25 May 2000 14:05:22 dashley1 |

3787 | %% TSE markers removed, as being considered |

3788 | %% by another journal. |

3789 | %% |

3790 | %% Rev 1.61 22 May 2000 11:27:40 dashley1 |

3791 | %% TMS370C8 changed to TMS370 as per |

3792 | %% Bob Crosby's review. |

3793 | %% |

3794 | %% Rev 1.60 19 May 2000 13:41:02 dashley1 |

3795 | %% Typo corrected. 966, not 9,666. |

3796 | %% |

3797 | %% Rev 1.59 16 May 2000 09:20:02 dashley1 |

3798 | %% References to daveashley.com removed for |

3799 | %% now. |

3800 | %% |

3801 | %% Rev 1.58 02 May 2000 15:55:22 dashley1 |

3802 | %% Add'l info added. |

3803 | %% |

3804 | %% Rev 1.57 02 May 2000 15:54:10 dashley1 |

3805 | %% Stephany Gervasi's contact info added. |

3806 | %% |

3807 | %% Rev 1.56 20 Apr 2000 10:50:52 dashley1 |

3808 | %% Newsgroup name corrected. |

3809 | %% |

3810 | %% Rev 1.55 20 Apr 2000 09:55:40 dashley1 |

3811 | %% Virgil added to acknowledgments, but must |

3812 | %% check newsgroup name. |

3813 | %% |

3814 | %% Rev 1.54 20 Apr 2000 09:25:08 dashley1 |

3815 | %% At home edits and trims. |

3816 | %% |

3817 | %% Rev 1.53 18 Apr 2000 15:07:26 dashley1 |

3818 | %% Minor typo (missing ")") corrected. |

3819 | %% |

3820 | %% Rev 1.52 18 Apr 2000 10:42:40 dashley1 |

3821 | %% Minor typo (an extra "the") corrected. |

3822 | %% |

3823 | %% Rev 1.51 17 Apr 2000 16:10:14 dashley1 |

3824 | %% Minor correction. |

3825 | %% |

3826 | %% Rev 1.50 17 Apr 2000 16:03:10 dashley1 |

3827 | %% Numerous minor corrections made from |

3828 | %% proofreading. |

3829 | %% |

3830 | %% Rev 1.49 17 Apr 2000 13:39:24 dashley1 |

3831 | %% Adam Gibson added to acknowledgements. |

3832 | %% |

3833 | %% Rev 1.48 17 Apr 2000 10:14:38 dashley1 |

3834 | %% At home edits, integration of Karl's conclusion. |

3835 | %% |

3836 | %% Rev 1.47 13 Apr 2000 10:16:30 dashley1 |

3837 | %% Link for pubs changed. |

3838 | %% |

3839 | %% Rev 1.46 12 Apr 2000 14:04:54 dashley1 |

3840 | %% Karsten Tinnefeld added to |

3841 | %% acknowledgements. |

3842 | %% |

3843 | %% Rev 1.45 12 Apr 2000 10:14:36 dashley1 |

3844 | %% Edits to placement of r_A section, |

3845 | %% additional acknowledgements. |

3846 | %% |

3847 | %% Rev 1.44 11 Apr 2000 21:06:24 dashley1 |

3848 | %% Partial evening edits--working on getting |

3849 | %% Section V finished. |

3850 | %% |

3851 | %% Rev 1.43 11 Apr 2000 10:34:04 dashley1 |

3852 | %% Addition of VC information. |

3853 | %% |

3854 | %% Rev 1.42 11 Apr 2000 10:14:56 dashley1 |

3855 | %% Minor edits to captions and last example. |

3856 | %% |

3857 | %% Rev 1.41 11 Apr 2000 09:52:56 dashley1 |

3858 | %% At-home edits. |

3859 | %% |

3860 | %% Rev 1.40 10 Apr 2000 10:27:34 dashley1 |

3861 | %% At-home edits. |

3862 | %% |

3863 | %% Rev 1.39 07 Apr 2000 10:39:32 dashley1 |

3864 | %% Home edits. |

3865 | %% |

3866 | %% Rev 1.38 06 Apr 2000 10:59:02 dashley1 |

3867 | %% Edits at home. Technical changes, |

3868 | %% changes in acknowledgements. |

3869 | %% |

3870 | %% Rev 1.37 05 Apr 2000 15:28:50 dashley1 |

3871 | %% Acknowlegements section enhanced and |

3872 | %% slightly rearranged, conversation with |

3873 | %% Bill Hagen about copyright issues captured |

3874 | %% as comments in file so won't forget |

3875 | %% resolution of those issues. |

3876 | %% |

3877 | %% Rev 1.36 31 Mar 2000 12:00:48 dashley1 |

3878 | %% Additional acknowledgements and |

3879 | %% hyperref notes added. |

3880 | %% |

3881 | %% Rev 1.35 28 Mar 2000 18:10:20 dashley1 |

3882 | %% Integer factorization mistake corrected. |

3883 | %% |

3884 | %% Rev 1.34 28 Mar 2000 10:30:38 dashley1 |

3885 | %% Safety check-in, plus 138 vs. 139 error |

3886 | %% discovered by Karl. |

3887 | %% |

3888 | %% Rev 1.33 13 Mar 2000 10:59:56 dashley1 |

3889 | %% Safety check-in. |

3890 | %% |

3891 | %% Rev 1.32 09 Mar 2000 10:51:14 dashley1 |

3892 | %% Getting closer to finishing last section. |

3893 | %% |

3894 | %% Rev 1.31 06 Mar 2000 11:51:38 dashley1 |

3895 | %% Incremental changes. |

3896 | %% |

3897 | %% Rev 1.30 01 Mar 2000 11:47:04 dashley1 |

3898 | %% Safety check-in. |

3899 | %% |

3900 | %% Rev 1.29 13 Feb 2000 10:49:38 dashley1 |

3901 | %% "I" changed to "Z" for set of integers, Dr. |

3902 | %% Zhigljavsky's section moved as per his |

3903 | %% recommendation, other changes. |

3904 | %% |

3905 | %% Rev 1.28 12 Jan 2000 20:51:08 dashley1 |

3906 | %% Dr. Zhigljavsky's changes integrated. |

3907 | %% |

3908 | %% Rev 1.27 10 Jan 2000 17:07:20 dashley1 |

3909 | %% Minor note added about set notations. |

3910 | %% |

3911 | %% Rev 1.26 10 Jan 2000 16:50:56 dashley1 |

3912 | %% Dr. Z's e-mail included as far as how to |

3913 | %% select the right nomenclature for sets of numbers, |

3914 | %% and Mircea added to acknowledgements. |

3915 | %% |

3916 | %% Rev 1.25 07 Jan 2000 19:17:56 dashley1 |

3917 | %% Pasted e-mail in from Dr. Zhigljavsky, preparing |

3918 | %% to take home. |

3919 | %% |

3920 | %% Rev 1.24 03 Jan 2000 12:24:56 dashley1 |

3921 | %% Typo, plus example 7 corrected. |

3922 | %% |

3923 | %% Rev 1.23 02 Jan 2000 15:45:00 dashley1 |

3924 | %% Edits, reintegration of version from home. |

3925 | %% |

3926 | %% Rev 1.22 31 Dec 1999 19:07:58 dashley1 |

3927 | %% "load" changed to "algorithm". |

3928 | %% |

3929 | %% Rev 1.21 31 Dec 1999 16:25:06 dashley1 |

3930 | %% Corrections, moving archives to PVCS, |

3931 | %% Punch Web Groups archives now obsolete. |

3932 | %% |

3933 | %% Rev 1.20 31 Dec 1999 15:30:30 dashley1 |

3934 | %% |

3935 | %% |

3936 | %% Rev 1.18 24 Oct 1999 13:01:38 dashley1 |

3937 | %% David Eppstein added to acknowledgements. |

3938 | %% |

3939 | %% Rev 1.17 20 Oct 1999 13:22:18 dashley1 |

3940 | %% Mark Endicott (who provided us with several |

3941 | %% initial suggestions and much insight) added |

3942 | %% to acknowledgements. |

3943 | %% |

3944 | %% Rev 1.16 19 Oct 1999 11:49:40 cpratt2 |

3945 | %% Short explanation of "z". Replaced redundant |

3946 | %% paragraphs following (8) and (9) with meaningful |

3947 | %% text. |

3948 | %% |

3949 | %% Rev 1.15 19 Oct 1999 10:47:18 dashley1 |

3950 | %% Equation and format changes. |

3951 | %% |

3952 | %% Rev 1.14 18 Oct 1999 12:07:58 dashley1 |

3953 | %% Spelling of Greg Bachelis' name corrected. |

3954 | %% |

3955 | %% Rev 1.13 18 Oct 1999 12:04:54 dashley1 |

3956 | %% Paulette Groen and Paula Smith added to |

3957 | %% acknowledgements. |

3958 | %% |

3959 | %% Rev 1.12 18 Oct 1999 10:29:02 dashley1 |

3960 | %% Enhancements in several areas. |

3961 | %% |

3962 | %% Rev 1.11 15 Oct 1999 09:21:04 dashley1 |

3963 | %% Many enhancements including removing all |

3964 | %% hard-coded cross-references and adding biography |

3965 | %% information. |

3966 | %% |

3967 | %% Rev 1.10 14 Oct 1999 15:40:18 dashley1 |

3968 | %% Bibliography straightened out, other changes. |

3969 | %% |

3970 | %% Rev 1.9 14 Oct 1999 12:33:40 dashley1 |

3971 | %% All equations and tables straightened out, |

3972 | %% references and glossary to go. |

3973 | %% |

3974 | %% Rev 1.8 14 Oct 1999 11:11:38 dashley1 |

3975 | %% Many tables and equations corrected. |

3976 | %% |

3977 | %% Rev 1.7 13 Oct 1999 19:34:14 dashley1 |

3978 | %% More equations completed. |

3979 | %% |

3980 | %% Rev 1.6 13 Oct 1999 18:44:34 dashley1 |

3981 | %% Added comments as per outline, some progress |

3982 | %% in incorporating missing equations. |

3983 | %% |

3984 | %% Rev 1.5 11 Oct 1999 10:13:14 dashley1 |

3985 | %% Comment delimiter situation straightened out. |

3986 | %% |

3987 | %% Rev 1.4 11 Oct 1999 10:10:00 dashley1 |

3988 | %% Safety check-in after weekend work. |

3989 | %% |

3990 | %% Rev 1.3 07 Oct 1999 10:04:48 dashley1 |

3991 | %% |

3992 | %% |

3993 | %% Rev 1.2 06 Oct 1999 18:47:28 dashley1 |

3994 | %% Evening safety check-in. |

3995 | %% |

3996 | %% Rev 1.1 06 Oct 1999 14:48:30 dashley1 |

3997 | %% Safety check-in, conversion up through equation |

3998 | %% 21 or so. |

3999 | %% |

4000 | %% Rev 1.0 06 Oct 1999 09:45:48 dashley1 |

4001 | %% Initial revision. |

4002 | %% |

4003 | %% End of pq_paper.tex |

4004 |

dashley@gmail.com | ViewVC Help |

Powered by ViewVC 1.1.25 |