1 |
dashley |
140 |
%$Header$ |
2 |
|
|
|
3 |
|
|
\chapter{Rational Linear Approximation} |
4 |
|
|
|
5 |
|
|
\label{crat0} |
6 |
|
|
|
7 |
|
|
\beginchapterquote{``Die ganzen Zahlen hat der liebe Gott gemacht, |
8 |
|
|
alles andere ist Menschenwerk.''\footnote{German |
9 |
|
|
language: God made the integers; everything |
10 |
|
|
else was made by man.}} |
11 |
|
|
{Leopold Kronecker} |
12 |
|
|
|
13 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
14 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
15 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
16 |
|
|
\section{Introduction} |
17 |
|
|
%Section tag: INT0 |
18 |
|
|
\label{crat0:sint0} |
19 |
|
|
|
20 |
|
|
In this chapter, we consider practical applications of |
21 |
|
|
rational approximation. |
22 |
|
|
Chapters \cfryzeroxrefhyphen\ref{cfry0} and \ccfrzeroxrefhyphen\ref{ccfr0} |
23 |
|
|
have presented algorithms for finding |
24 |
|
|
the closest rational numbers to an arbitrary real number, |
25 |
|
|
subject to constraints on the numerator and denominator. |
26 |
|
|
The basis of these algorithms is complex and comes from number theory, and so |
27 |
|
|
these algorithms and their basis have been presented in separate chapters. |
28 |
|
|
|
29 |
|
|
In Section \ref{crat0:srla0}, rational linear approximation itself |
30 |
|
|
and associated error bounds are presented. By \emph{rational linear |
31 |
|
|
approximation} we mean simply the approximation of a line |
32 |
|
|
$y = r_I x$ ($y, r_I, x \in \vworkrealset$) by a line |
33 |
|
|
|
34 |
|
|
\begin{equation} |
35 |
|
|
\label{eq:crat0:sint0:01} |
36 |
|
|
y = \left\lfloor |
37 |
|
|
\frac{h \lfloor x \rfloor + z}{k} |
38 |
|
|
\right\rfloor , |
39 |
|
|
\end{equation} |
40 |
|
|
|
41 |
|
|
\noindent{}where we choose $h/k \approx r_I$ and optionally choose $z$ to |
42 |
|
|
shift the error introduced. Note that (\ref{eq:crat0:sint0:01}) is |
43 |
|
|
very economical for microcontroller instruction sets, since only integer |
44 |
|
|
arithmetic is required. We may choose $h/k$ from a Farey series (see |
45 |
|
|
Chapters \cfryzeroxrefhyphen\ref{cfry0} and \ccfrzeroxrefhyphen\ref{ccfr0}), or |
46 |
|
|
we may choose a ratio $h/2^q$ so that the division in (\ref{eq:crat0:sint0:01}) |
47 |
|
|
can be implemented |
48 |
|
|
by a bitwise right shift. |
49 |
|
|
|
50 |
|
|
Section \ref{crat0:srla0} discusses linear rational approximation |
51 |
|
|
in general, with a special eye on error analysis. |
52 |
|
|
|
53 |
|
|
Section \ref{crat0:spwi0} discusses piecewise linear rational approximation, |
54 |
|
|
which is the approximation of a curve or complex mapping by a |
55 |
|
|
number of joined line segments. |
56 |
|
|
|
57 |
|
|
Section \ref{crat0:sfdv0} discusses frequency division and rational counting. |
58 |
|
|
Such techniques share the same mathematical framework as rational linear |
59 |
|
|
approximation, and as with rational linear approximation the ratio |
60 |
|
|
involved may be chosen from a Farey series or with a denominator of $2^q$, depending |
61 |
|
|
on the algorithm employed. |
62 |
|
|
|
63 |
|
|
Section \ref{crat0:sbla0} discusses Bresenham's classic line algorithm, |
64 |
|
|
which is a practical application of rational linear approximation. |
65 |
|
|
|
66 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
67 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
68 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
69 |
|
|
\section{Rational Linear Approximation} |
70 |
|
|
%Section tag: RLA0 |
71 |
|
|
\label{crat0:srla0} |
72 |
|
|
|
73 |
|
|
It occurs frequently in embedded software design that one wishes to |
74 |
|
|
implement a linear scaling from a domain to a range of the form |
75 |
|
|
|
76 |
|
|
\begin{equation} |
77 |
|
|
\label{eq:crat0:srla0:01} |
78 |
|
|
f(x) = r_I x , |
79 |
|
|
\end{equation} |
80 |
|
|
|
81 |
|
|
\noindent{}where $r_I$ is the \emph{ideal} |
82 |
|
|
|
83 |
|
|
|
84 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
85 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
86 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
87 |
|
|
\subsection{Model Functions} |
88 |
|
|
%Section tag: mfu0 |
89 |
|
|
\label{crat0:srla0:smfu0} |
90 |
|
|
|
91 |
|
|
In general, we seek to approximate the ideal function |
92 |
|
|
|
93 |
|
|
|
94 |
|
|
\noindent{}by some less ideal function where |
95 |
|
|
|
96 |
|
|
\begin{itemize} |
97 |
|
|
\item $r_A \neq r_I$, although we seek to choose $r_A \approx r_I$. |
98 |
|
|
\item The input to the function, $x$, may already contain |
99 |
|
|
quantization error. |
100 |
|
|
\item Although $r_I x \in \vworkrealsetnonneg$, we must choose |
101 |
|
|
an integer as the function output. |
102 |
|
|
\end{itemize} |
103 |
|
|
|
104 |
|
|
In modeling quantization error, we use the floor function\index{floor function} |
105 |
|
|
($\lfloor\cdot\rfloor$) |
106 |
|
|
for algebraic simplicity. The floor function precisely |
107 |
|
|
describes the behavior of integer division instructions (where |
108 |
|
|
remainders are discarded), but may not describe other sources of |
109 |
|
|
quantization, such as quantization that occurs in A/D conversion. |
110 |
|
|
However, techniques identical to those presented in this |
111 |
|
|
section may be used when quantization is not best described |
112 |
|
|
by the floor function, and these results are left to the reader. |
113 |
|
|
|
114 |
|
|
Traditionally, because addition of integers is an inexpensive |
115 |
|
|
machine operation, a parameter $z \in \vworkintset$ may optionally |
116 |
|
|
be added to the product $hx$ in order to round or otherwise |
117 |
|
|
shift the result. |
118 |
|
|
|
119 |
|
|
If $x$ is assumed to be without error, the ideal function is |
120 |
|
|
given by (\ref{eq:crat0:srla0:smfu0:01}), whereas the function |
121 |
|
|
that can be economically implemented is |
122 |
|
|
|
123 |
|
|
\begin{equation} |
124 |
|
|
\label{eq:crat0:srla0:smfu0:02} |
125 |
|
|
g(x) = \left\lfloor \frac{hx + z}{k} \right\rfloor |
126 |
|
|
= |
127 |
|
|
\left\lfloor r_A x + \frac{z}{k} \right\rfloor . |
128 |
|
|
\end{equation} |
129 |
|
|
|
130 |
|
|
If, on the other hand, $x$ may be already quantized, |
131 |
|
|
the function that can actually be implemented is |
132 |
|
|
|
133 |
|
|
\begin{equation} |
134 |
|
|
\label{eq:crat0:srla0:smfu0:03} |
135 |
|
|
h(x) = \left\lfloor \frac{h \lfloor x \rfloor + z}{k} \right\rfloor |
136 |
|
|
= |
137 |
|
|
\left\lfloor r_A \lfloor x \rfloor + \frac{z}{k} \right\rfloor . |
138 |
|
|
\end{equation} |
139 |
|
|
|
140 |
|
|
|
141 |
|
|
|
142 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
143 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
144 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
145 |
|
|
\section[\protect\mbox{\protect$h/2^q$} and \protect\mbox{\protect$2^q/k$} Rational Linear Approximation] |
146 |
|
|
{\protect\mbox{\protect\boldmath$h/2^q$} and \protect\mbox{\protect\boldmath$2^q/k$} Rational Linear Approximation} |
147 |
|
|
%Section tag: HQQ0 |
148 |
|
|
\label{crat0:shqq0} |
149 |
|
|
|
150 |
|
|
\index{h/2q@$h/2^q$ rational linear approximation} |
151 |
|
|
\index{rational linear approximation!h/2q@$h/2^q$} |
152 |
|
|
The algorithms presented in |
153 |
|
|
Chapters \cfryzeroxrefhyphen\ref{cfry0} and \ccfrzeroxrefhyphen\ref{ccfr0} |
154 |
|
|
will always provide the rational number $h/k$ closest to |
155 |
|
|
an arbitrary real number $r_I$ subject to the constraints |
156 |
|
|
$h \leq h_{MAX}$ and $k \leq k_{MAX}$. |
157 |
|
|
|
158 |
|
|
However, because shifting in order |
159 |
|
|
to implement multiplication or division by a power of 2 |
160 |
|
|
is at least as fast (and often \emph{much} faster) |
161 |
|
|
on all processors as arbitrary multiplication or division, |
162 |
|
|
and because not all processors have multiplication and division instructions, |
163 |
|
|
it is worthwhile to examine choosing $h/k$ so that either $h$ or $k$ are |
164 |
|
|
powers of 2. |
165 |
|
|
|
166 |
|
|
There are thus three rational linear approximation techniques to be |
167 |
|
|
examined: |
168 |
|
|
|
169 |
|
|
\begin{enumerate} |
170 |
|
|
\item \emph{$h/k$ rational linear approximation}, in which an arbitrary |
171 |
|
|
$h \leq h_{MAX}$ and an arbitrary $k \leq k_{MAX}$ are used, |
172 |
|
|
with $r_A = h/k$. $h$ and $k$ can be chosen using the algorithms |
173 |
|
|
presented in Chapters \cfryzeroxrefhyphen\ref{cfry0} and \ccfrzeroxrefhyphen\ref{ccfr0}. |
174 |
|
|
Implementation of this technique would most often involve a single integer |
175 |
|
|
multiplication instruction to form the product $hx$, followed by an optional single |
176 |
|
|
addition instruction to form the sum $hx+z$, and then |
177 |
|
|
followed by by a single division instruction |
178 |
|
|
to form the quotient $\lfloor (hx+z)/k \rfloor$. Implementation may also less commonly involve |
179 |
|
|
multiplication, addition, and division of operands too large to be processed |
180 |
|
|
with single machine instructions. |
181 |
|
|
\item \emph{$h/2^q$ rational linear approximation}, in which an arbitrary |
182 |
|
|
$h \leq h_{MAX}$ and an integral power of two $k=2^q$ are used, with |
183 |
|
|
$r_A = h/2^q$. |
184 |
|
|
Implementation of this technique would most often involve a single integer |
185 |
|
|
multiplication instruction to form the product $hx$, followed by an optional single |
186 |
|
|
addition instruction to form the sum $hx+z$, and then |
187 |
|
|
followed by right shift instruction(s) |
188 |
|
|
to form the quotient $\lfloor (hx+z)/2^q \rfloor$. Implementation may also less commonly involve |
189 |
|
|
multiplication, addition, and right shift of operands too large to be processed |
190 |
|
|
with single machine instructions. |
191 |
|
|
\item \emph{$2^q/k$ rational linear approximation}, in which an integral |
192 |
|
|
power of two $h=2^q$ and an arbitrary $k \leq k_{MAX}$ are used, with |
193 |
|
|
$r_A = 2^q/k$. |
194 |
|
|
Implementation of this technique would most often involve left shift |
195 |
|
|
instruction(s) to form the product $2^qx$, followed by an optional single |
196 |
|
|
addition instruction to form the sum $2^qx+z$, and then |
197 |
|
|
followed by a single division instruction to form |
198 |
|
|
the quotient $\lfloor (2^qx+z)/k \rfloor$. Implementation may also less |
199 |
|
|
commonly involve |
200 |
|
|
left shift, addition, and division of operands too large to be processed |
201 |
|
|
with single machine instructions. |
202 |
|
|
\end{enumerate} |
203 |
|
|
|
204 |
|
|
We use the nomenclature ``\emph{$h/k$ rational linear approximation}'', |
205 |
|
|
``\emph{$h/2^q$ rational linear approximation}'', and |
206 |
|
|
``\emph{$2^q/k$ rational linear approximation}'' to identify the three |
207 |
|
|
techniques enumerated above. |
208 |
|
|
|
209 |
|
|
|
210 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
211 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
212 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
213 |
|
|
\subsection{Integer Arithmetic and Processor Instruction Set Characteristics} |
214 |
|
|
%Subsection tag: pis0 |
215 |
|
|
\label{crat0:shqq0:pis0} |
216 |
|
|
|
217 |
|
|
The following observations about integer arithmetic and about processors |
218 |
|
|
used in embedded control can be made: |
219 |
|
|
|
220 |
|
|
\begin{enumerate} |
221 |
|
|
\item \label{enum:crat0:shqq0:pis0:01:01a} |
222 |
|
|
\emph{Shifting is the fastest method of integer multiplication or division |
223 |
|
|
(by $2^q$ only), |
224 |
|
|
followed by utilization of the processor multiplication or division instructions (for arbitrary |
225 |
|
|
operands), |
226 |
|
|
followed by software implementation of multiplication or division (for arbitrary operands).} |
227 |
|
|
Relative costs vary depending on the processor, but the monotonic |
228 |
|
|
ordering always holds. |
229 |
|
|
$h/2^q$ and $2^q/k$ rational linear |
230 |
|
|
approximation are thus worthy of investigation. (Note also that in many practical |
231 |
|
|
applications of $h/2^q$ and $2^q/k$ rational linear approximation, |
232 |
|
|
the required shift is performed by |
233 |
|
|
addressing the operand with an offset, |
234 |
|
|
and so has no cost.) |
235 |
|
|
\item \label{enum:crat0:shqq0:pis0:01:01b} |
236 |
|
|
\emph{Shifting is $O(N)$ (where $N$ is the number of bits in the argument), |
237 |
|
|
but both |
238 |
|
|
multiplication and division are $O(N^2)$ for |
239 |
|
|
practical\footnote{\index{Karatsuba multiplication}Karatsuba |
240 |
|
|
multiplication, for example, is |
241 |
|
|
$O(N^{\log_2 3}) \approx O(N^{1.58}) \ll O(N^2)$. However, Karatsuba |
242 |
|
|
multiplication cannot be applied economically to the small |
243 |
|
|
operands that typically occur in embedded control work. It would |
244 |
|
|
be rare in embedded control applications |
245 |
|
|
for the length of a multiplication operand to exceed four |
246 |
|
|
times the length that is accommodated by a machine instruction; and this |
247 |
|
|
is far below the threshold at which Karatsuba multiplication is |
248 |
|
|
economical. Thus, for all intents and purposes in embedded control work, |
249 |
|
|
multiplication is $O(N^2)$.} operands (where |
250 |
|
|
$N$ is the number of bits in each |
251 |
|
|
operand).} It follows that $2^q/k$ and $h/2^q$ rational |
252 |
|
|
linear approximation |
253 |
|
|
will scale to large operands better than $h/k$ rational linear approximation. |
254 |
|
|
\item \label{enum:crat0:shqq0:pis0:01:02a} |
255 |
|
|
\emph{Integer division instructions take as long or longer than |
256 |
|
|
integer multiplication instructions.} In designing digital logic |
257 |
|
|
to implement basic integer arithmetic, division is the operation most difficult |
258 |
|
|
to perform economically.\footnote{For some processors, the penalty is extreme. |
259 |
|
|
For example, on the NEC V850 (a RISC processor), |
260 |
|
|
a division requires 36 clock cycles, |
261 |
|
|
whereas multiplication, addition, and subtraction each effectively |
262 |
|
|
require 1 clock cycle.} |
263 |
|
|
It follows that multiplication using operands that exceed the machine's word size |
264 |
|
|
is often far less expensive than division using operands that exceed the |
265 |
|
|
machine's word size. |
266 |
|
|
\item \label{enum:crat0:shqq0:pis0:01:03a} |
267 |
|
|
\emph{All processors that have an integer division instruction also |
268 |
|
|
have an integer multiplication instruction.} |
269 |
|
|
Phrased |
270 |
|
|
differently, no processor has an integer division instruction but no |
271 |
|
|
integer multiplication instruction. |
272 |
|
|
\end{enumerate} |
273 |
|
|
|
274 |
|
|
Enumerated items |
275 |
|
|
(\ref{enum:crat0:shqq0:pis0:01:01a}) through |
276 |
|
|
(\ref{enum:crat0:shqq0:pis0:01:03a}) above lead to the following conclusions. |
277 |
|
|
|
278 |
|
|
\begin{enumerate} |
279 |
|
|
\item $h/2^q$ rational linear approximation is likely to be implementable |
280 |
|
|
more efficiently on most processors than $h/k$ rational linear approximation. |
281 |
|
|
(\emph{Rationale:} shift instruction(s) or accessing a |
282 |
|
|
memory address with an offset |
283 |
|
|
is |
284 |
|
|
likely to be more economical than division, particularly if $k$ would exceed |
285 |
|
|
the native |
286 |
|
|
operand size of the processor.) |
287 |
|
|
\item $h/2^q$ rational linear approximation is likely to be a more useful |
288 |
|
|
technique than $2^q/k$ rational linear approximation. |
289 |
|
|
(\emph{Rationale:} the generally high cost of division compared to |
290 |
|
|
multiplication, and the existence of processors that possess a multiplication |
291 |
|
|
instruction but no division instruction.) |
292 |
|
|
\end{enumerate} |
293 |
|
|
|
294 |
|
|
|
295 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
296 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
297 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
298 |
|
|
\subsection[Design Procedure For \protect\mbox{\protect$h/2^q$} Rational Linear Approximations] |
299 |
|
|
{Design Procedure For \protect\mbox{\protect\boldmath$h/2^q$} Rational Linear Approximation} |
300 |
|
|
%Subsection tag: dph0 |
301 |
|
|
\label{crat0:shqq0:dph0} |
302 |
|
|
|
303 |
|
|
An $h/2^q$ rational linear approximation is parameterized by: |
304 |
|
|
|
305 |
|
|
\begin{itemize} |
306 |
|
|
\item The unsigned or signed nature of $h$ and $x$. (Rational linear approximations |
307 |
|
|
may involve either signed or unsigned domains and ranges. Furthermore, |
308 |
|
|
signed integers may be maintained using either 2's-complement |
309 |
|
|
or sign-magnitude representation, and the processor instruction set |
310 |
|
|
may or may not directly support signed multiplication.) |
311 |
|
|
\item $r_I$, the real number we wish to approximate by $r_A = h/2^q$. |
312 |
|
|
\item $x_{MAX}$, the maximum possible value of the input argument $x$. (Typically, |
313 |
|
|
software contains a test to clip the output if $x > x_{MAX}$.) |
314 |
|
|
\item $w_h$, the width in bits allowed for $h$. (Typically, $w_h$ is |
315 |
|
|
the maximum operand size of a machine multiplication instruction.) |
316 |
|
|
\item $w_r$, the width in bits allowed for the result $hx$. (Typically, |
317 |
|
|
$w_r$ is the maximum result size of a machine multiplication instruction.) |
318 |
|
|
\item The rounding mode when choosing $h$ (and thus effectively $r_A$) |
319 |
|
|
based on $r_I$. It is common to choose the |
320 |
|
|
closest value, |
321 |
|
|
$r_A=\lfloor r_I 2^q + 1/2 \rfloor/2^q$ |
322 |
|
|
or |
323 |
|
|
$r_A=\lceil r_I 2^q - 1/2 \rceil/2^q$, |
324 |
|
|
but other choices are possible. |
325 |
|
|
\item The rounding mode for the result (i.e. the choice of $z$ in |
326 |
|
|
Eq. \ref{eq:crat0:sint0:01}). |
327 |
|
|
\end{itemize} |
328 |
|
|
|
329 |
|
|
This section develops a design procedure for $h/2^q$ rational linear |
330 |
|
|
approximations with the most typical set of assumptions: unsigned arithmetic, |
331 |
|
|
$r_A=\lfloor r_I 2^q + 1/2 \rfloor/2^q$, |
332 |
|
|
and $z=0$. Design procedures for other scenarios are presented as exercises. |
333 |
|
|
|
334 |
|
|
By definition, $h$ is constrained in two ways: |
335 |
|
|
|
336 |
|
|
\begin{equation} |
337 |
|
|
\label{eq:crat0:shqq0:dph0:00} |
338 |
|
|
h \leq 2^{w_h} - 1 |
339 |
|
|
\end{equation} |
340 |
|
|
|
341 |
|
|
\noindent{}and |
342 |
|
|
|
343 |
|
|
\begin{equation} |
344 |
|
|
\label{eq:crat0:shqq0:dph0:01} |
345 |
|
|
h \leq \frac{2^{w_r} - 1}{x_{MAX}} . |
346 |
|
|
\end{equation} |
347 |
|
|
|
348 |
|
|
\noindent{}(\ref{eq:crat0:shqq0:dph0:00}) comes directly from the |
349 |
|
|
requirement that $h$ fit in $w_h$ bits. |
350 |
|
|
(\ref{eq:crat0:shqq0:dph0:01}) comes directly from the requirement |
351 |
|
|
that $hx$ fit in $w_r$ bits. |
352 |
|
|
(\ref{eq:crat0:shqq0:dph0:00}) and (\ref{eq:crat0:shqq0:dph0:01}) |
353 |
|
|
may be combined to form one inequality: |
354 |
|
|
|
355 |
|
|
\begin{equation} |
356 |
|
|
\label{eq:crat0:shqq0:dph0:02} |
357 |
|
|
h \leq \min \left( { 2^{w_h} - 1, \frac{2^{w_r} - 1}{x_{MAX}} } \right ) . |
358 |
|
|
\end{equation} |
359 |
|
|
|
360 |
|
|
If $q$ is known, the choice of $h$ that will be made so as to minimize |
361 |
|
|
$|r_A-r_I| = |h/2^q - r_I|$ is |
362 |
|
|
|
363 |
|
|
\begin{equation} |
364 |
|
|
\label{eq:crat0:shqq0:dph0:03} |
365 |
|
|
h=\left\lfloor r_I 2^q + \frac{1}{2} \right\rfloor . |
366 |
|
|
\end{equation} |
367 |
|
|
|
368 |
|
|
\noindent{}It is required that the choice of $h$ specified by |
369 |
|
|
(\ref{eq:crat0:shqq0:dph0:03}) meet |
370 |
|
|
(\ref{eq:crat0:shqq0:dph0:02}). Making the most pessimistic |
371 |
|
|
assumption about the rounding of $h$ and substituting into |
372 |
|
|
(\ref{eq:crat0:shqq0:dph0:02}) leads to |
373 |
|
|
|
374 |
|
|
\begin{equation} |
375 |
|
|
\label{eq:crat0:shqq0:dph0:04} |
376 |
|
|
r_I 2^q + \frac{1}{2} |
377 |
|
|
\leq |
378 |
|
|
\min \left( { 2^{w_h} - 1, \frac{2^{w_r} - 1}{x_{MAX}} } \right ) . |
379 |
|
|
\end{equation} |
380 |
|
|
|
381 |
|
|
\noindent{}Isolating $q$ in (\ref{eq:crat0:shqq0:dph0:04}) |
382 |
|
|
yields |
383 |
|
|
|
384 |
|
|
\begin{equation} |
385 |
|
|
\label{eq:crat0:shqq0:dph0:05} |
386 |
|
|
2^q |
387 |
|
|
\leq |
388 |
|
|
\frac{\min \left( { 2^{w_h} - 1, \frac{2^{w_r} - 1}{x_{MAX}} } \right ) - \frac{1}{2}} |
389 |
|
|
{r_I}. |
390 |
|
|
\end{equation} |
391 |
|
|
|
392 |
|
|
\noindent{}Solving |
393 |
|
|
(\ref{eq:crat0:shqq0:dph0:05}) |
394 |
|
|
for maximum value of $q$ that meets the constraint yields |
395 |
|
|
|
396 |
|
|
\begin{equation} |
397 |
|
|
\label{eq:crat0:shqq0:dph0:06} |
398 |
|
|
q= |
399 |
|
|
\left\lfloor |
400 |
|
|
{ |
401 |
|
|
\log_2 |
402 |
|
|
\left( |
403 |
|
|
{ |
404 |
|
|
\frac{\min \left( { 2^{w_h} - 1, \frac{2^{w_r} - 1}{x_{MAX}} } \right ) - \frac{1}{2}}{r_I} |
405 |
|
|
} |
406 |
|
|
\right) |
407 |
|
|
} |
408 |
|
|
\right\rfloor . |
409 |
|
|
\end{equation} |
410 |
|
|
|
411 |
|
|
\noindent{}(\ref{eq:crat0:shqq0:dph0:06}) |
412 |
|
|
can be rewritten for easier calculation using most calculators (which do |
413 |
|
|
not allow the direct evaluation of base-2 logarithms): |
414 |
|
|
|
415 |
|
|
\begin{equation} |
416 |
|
|
\label{eq:crat0:shqq0:dph0:07} |
417 |
|
|
q= |
418 |
|
|
\left\lfloor |
419 |
|
|
\frac |
420 |
|
|
{ |
421 |
|
|
{ |
422 |
|
|
\ln |
423 |
|
|
\left( |
424 |
|
|
{ |
425 |
|
|
\frac{\min \left( { 2^{w_h} - 1, \frac{2^{w_r} - 1}{x_{MAX}} } \right ) - \frac{1}{2}}{r_I} |
426 |
|
|
} |
427 |
|
|
\right) |
428 |
|
|
} |
429 |
|
|
} |
430 |
|
|
{\ln 2} |
431 |
|
|
\right\rfloor . |
432 |
|
|
\end{equation} |
433 |
|
|
|
434 |
|
|
\noindent{}Once $q$ is established using (\ref{eq:crat0:shqq0:dph0:07}), |
435 |
|
|
$h$ can be calculated using (\ref{eq:crat0:shqq0:dph0:03}). |
436 |
|
|
|
437 |
|
|
In embedded control work (as well as in operating system internals), |
438 |
|
|
$h/2^q$ rational linear approximations are often used in conjunction with |
439 |
|
|
tabulated constants or calibratable parameters |
440 |
|
|
where each constant or calibratable parameter may vary over a range of |
441 |
|
|
$[0, r_I]$, and where $r_I$ is the value used in the design procedure |
442 |
|
|
presented above. In these applications, the values of $h$ are |
443 |
|
|
tabulated, but $q$ is invariant (usually hard-coded) |
444 |
|
|
and is chosen at design time based on the upper bound $r_I$ |
445 |
|
|
of the interval $[0, r_I]$ in which each tabulated constant or calibratable |
446 |
|
|
parameter will fall. With $q$ fixed, |
447 |
|
|
$r_A$ can be adjusted in steps of $1/2^q$. |
448 |
|
|
|
449 |
|
|
If $r_I$ is invariant, a final design step may be to reduce the rational |
450 |
|
|
number $h/2^q$ by dividing some or all occurrences of 2 as a factor from both the |
451 |
|
|
numerator and denominator. With some processors and in some applications, this |
452 |
|
|
may save execution time by reducing the number of shift instructions that |
453 |
|
|
must be executed, reducing the execution time of the shift instructions |
454 |
|
|
that are executed, or allowing shifting via offset addressing. |
455 |
|
|
For example, on a byte-addressible machine, if the design procedure |
456 |
|
|
yields $h=608$ and $q=10$, it may be desirable to divide both $h$ and $2^q$ by 4 to |
457 |
|
|
yield $h=152$ and $q=8$, as this allows the shift by 8 to be done by fetching |
458 |
|
|
alternate bytes (rather than by actual shifting). In other applications, it may |
459 |
|
|
be desirable to remove \emph{all} occurrences of 2 as a prime factor |
460 |
|
|
from $h$. |
461 |
|
|
|
462 |
|
|
For an invariant $r_I$, a suitable design procedure is: |
463 |
|
|
|
464 |
|
|
\begin{enumerate} |
465 |
|
|
\item Choose $q$ using (\ref{eq:crat0:shqq0:dph0:07}). |
466 |
|
|
\item With $q$ fixed, choose $h$ using (\ref{eq:crat0:shqq0:dph0:03}). |
467 |
|
|
\item If economies can be achieved on the target processor, |
468 |
|
|
examine the possibility of removing some or all occurrences |
469 |
|
|
of 2 as a prime factor from $h$ and decreasing $q$. |
470 |
|
|
\end{enumerate} |
471 |
|
|
|
472 |
|
|
For tabulated or calibratable constants in the |
473 |
|
|
interval $[0,r_I]$, a suitable design procedure is to use the |
474 |
|
|
procedure presented immediately above but without the third step. |
475 |
|
|
Each tabulated value of $h$ is chosen using (\ref{eq:crat0:shqq0:dph0:03}). |
476 |
|
|
|
477 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
478 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
479 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
480 |
|
|
\subsection[Design Procedure For \protect\mbox{\protect$2^q/k$} Rational Linear Approximations] |
481 |
|
|
{Design Procedure For \protect\mbox{\protect\boldmath$2^q/k$} Rational Linear Approximation} |
482 |
|
|
%Subsection tag: dpk0 |
483 |
|
|
\label{crat0:shqq0:dpk0} |
484 |
|
|
|
485 |
|
|
TBD. |
486 |
|
|
|
487 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
488 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
489 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
490 |
|
|
\section{Piecewise Rational Linear Approximation} |
491 |
|
|
%Section tag: PWI0 |
492 |
|
|
\label{crat0:spwi0} |
493 |
|
|
|
494 |
|
|
TBD. |
495 |
|
|
|
496 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
497 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
498 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
499 |
|
|
\section[Frequency Division And Rational Counting] |
500 |
|
|
{Frequency Division And Rational Counting Techniques} |
501 |
|
|
%Section tag: FDV0 |
502 |
|
|
\label{crat0:sfdv0} |
503 |
|
|
|
504 |
|
|
\index{frequency division}\index{rational counting}\index{counting}% |
505 |
|
|
Often, software must ``divide down'' an execution rate. For example, |
506 |
|
|
an interrupt service routine may be scheduled by hardware every |
507 |
|
|
10ms, but may perform useful processing only every 50ms. This requires |
508 |
|
|
that the ISR maintain a counter and only perform useful processing |
509 |
|
|
every fifth invocation. This section deals with counting strategies |
510 |
|
|
used to achieve invocation frequency division and other similar results. |
511 |
|
|
|
512 |
|
|
Frequency division and |
513 |
|
|
rational counting techniques presented in this section find application |
514 |
|
|
primarily in the following scenarios: |
515 |
|
|
|
516 |
|
|
\begin{itemize} |
517 |
|
|
\item ISRs and other software components which must divide down |
518 |
|
|
their invocation rate. |
519 |
|
|
\item Pulse counting and scaling from encoders and other |
520 |
|
|
similar systems. |
521 |
|
|
\item The correction of inaccuracies in timebases (such as crystals |
522 |
|
|
which oscillate at a frequency different than the |
523 |
|
|
nominal rate). |
524 |
|
|
\end{itemize} |
525 |
|
|
|
526 |
|
|
Because the techniques presented must be usable with inexpensive |
527 |
|
|
microcontrollers, such techniques must meet these constraints: |
528 |
|
|
|
529 |
|
|
\begin{enumerate} |
530 |
|
|
\item \label{enum:01:crat0:sfdv0:econex} |
531 |
|
|
The counting techniques must be economical to execute on |
532 |
|
|
an inexpensive microcontroller. |
533 |
|
|
\item \label{enum:01:crat0:sfdv0:econcccalc} |
534 |
|
|
An inexpensive microcontroller must be capable of calculating any |
535 |
|
|
constants used as limits in counting (i.e. it cannot necessarily |
536 |
|
|
be assumed that a more powerful computer calculates these constants, |
537 |
|
|
and it cannot be assumed that these limits do not change on the fly). |
538 |
|
|
\end{enumerate} |
539 |
|
|
|
540 |
|
|
In this section, we analyze the behavior of several types of |
541 |
|
|
rational counting algorithms, supplied as Algorithms |
542 |
|
|
\ref{alg:crat0:sfdv0:01a} |
543 |
|
|
through |
544 |
|
|
\ref{alg:crat0:sfdv0:02a}. |
545 |
|
|
|
546 |
|
|
\begin{algorithm} |
547 |
|
|
\begin{verbatim} |
548 |
|
|
/* The constants K1 through K4, which parameterize the */ |
549 |
|
|
/* counting behavior, are assumed assigned elsewhere in */ |
550 |
|
|
/* the code. The solution is analyzed in terms of the */ |
551 |
|
|
/* parameters K1 through K4. */ |
552 |
|
|
/* */ |
553 |
|
|
/* We also place the following restrictions on K1 through */ |
554 |
|
|
/* K4: */ |
555 |
|
|
/* K1 : K1 <= K3 - K2. */ |
556 |
|
|
/* K2 : K4 > K2 > 0. */ |
557 |
|
|
/* K3 : No restrictions. */ |
558 |
|
|
/* K4 : K4 > K2 > 0. */ |
559 |
|
|
|
560 |
|
|
void base_rate_sub(void) |
561 |
|
|
{ |
562 |
|
|
static int state = K1; |
563 |
|
|
|
564 |
|
|
state += K2; |
565 |
|
|
|
566 |
|
|
if (state >= K3) |
567 |
|
|
{ |
568 |
|
|
state -= K4; |
569 |
|
|
A(); |
570 |
|
|
} |
571 |
|
|
} |
572 |
|
|
\end{verbatim} |
573 |
|
|
\caption{Rational Counting Algorithm For $K_2/K_4 < 1$} |
574 |
|
|
\label{alg:crat0:sfdv0:01a} |
575 |
|
|
\end{algorithm} |
576 |
|
|
|
577 |
|
|
\begin{algorithm} |
578 |
|
|
\begin{verbatim} |
579 |
|
|
/* The constants K1 through K4, which parameterize the */ |
580 |
|
|
/* counting behavior, are assumed assigned elsewhere in */ |
581 |
|
|
/* the code. The solution is analyzed in terms of the */ |
582 |
|
|
/* parameters K1 through K4. */ |
583 |
|
|
/* */ |
584 |
|
|
/* We also place the following restrictions on K1 through */ |
585 |
|
|
/* K4: */ |
586 |
|
|
/* K1 : K1 <= K3 - K2. */ |
587 |
|
|
/* K2 : K2 > 0. */ |
588 |
|
|
/* K3 : No restrictions. */ |
589 |
|
|
/* K4 : K4 > 0. */ |
590 |
|
|
|
591 |
|
|
void base_rate_sub(void) |
592 |
|
|
{ |
593 |
|
|
static int state = K1; |
594 |
|
|
|
595 |
|
|
state += K2; |
596 |
|
|
|
597 |
|
|
while (state >= K3) |
598 |
|
|
{ |
599 |
|
|
state -= K4; |
600 |
|
|
A(); |
601 |
|
|
} |
602 |
|
|
} |
603 |
|
|
\end{verbatim} |
604 |
|
|
\caption{Rational Counting Algorithm For $K_2/K_4 \geq 1$} |
605 |
|
|
\label{alg:crat0:sfdv0:01b} |
606 |
|
|
\end{algorithm} |
607 |
|
|
|
608 |
|
|
\begin{algorithm} |
609 |
|
|
\begin{verbatim} |
610 |
|
|
/* The constants K1, K2, and K4, which parameterize the */ |
611 |
|
|
/* counting behavior, are assumed assigned elsewhere in */ |
612 |
|
|
/* the code. The solution is analyzed in terms of the */ |
613 |
|
|
/* parameters K1 through K4. */ |
614 |
|
|
/* */ |
615 |
|
|
/* We also place the following restrictions on K1, K2, */ |
616 |
|
|
/* and K4: */ |
617 |
|
|
/* K1 : K1 >= 0. */ |
618 |
|
|
/* K2 : K4 > K2 > 0. */ |
619 |
|
|
/* K4 : K4 > K2 > 0. */ |
620 |
|
|
/* */ |
621 |
|
|
/* Special thanks to Chuck B. Falconer (of the */ |
622 |
|
|
/* comp.arch.embedded newsgroup) for this rational */ |
623 |
|
|
/* counting algorithm. */ |
624 |
|
|
/* */ |
625 |
|
|
/* Note below that the test against K3 does not exist, */ |
626 |
|
|
/* instead a test against zero is used, which many */ |
627 |
|
|
/* machine instruction sets will do as part of the */ |
628 |
|
|
/* subtraction (but perhaps this needs to be coded in */ |
629 |
|
|
/* A/L). This saves machine code and also eliminates */ |
630 |
|
|
/* one unnecessary degree of freedom (K3). */ |
631 |
|
|
|
632 |
|
|
void base_rate_sub(void) |
633 |
|
|
{ |
634 |
|
|
static int state = K1; |
635 |
|
|
|
636 |
|
|
if ((state -= K2) < 0) |
637 |
|
|
{ |
638 |
|
|
state += K4; |
639 |
|
|
A(); |
640 |
|
|
} |
641 |
|
|
} |
642 |
|
|
\end{verbatim} |
643 |
|
|
\caption{Zero-Test Rational Counting Algorithm For $K_2/K_4 < 1$} |
644 |
|
|
\label{alg:crat0:sfdv0:01c} |
645 |
|
|
\end{algorithm} |
646 |
|
|
|
647 |
|
|
\begin{algorithm} |
648 |
|
|
\begin{verbatim} |
649 |
|
|
;Special thanks to John Larkin (of the comp.arch.embedded |
650 |
|
|
;newsgroup) for this rational counting algorithm. |
651 |
|
|
; |
652 |
|
|
;This is the TMS-370C8 assembly-language version of the |
653 |
|
|
;algorithm. The algorithm is parameterized solely by |
654 |
|
|
;K1 and K2, with no restrictions on their values, because |
655 |
|
|
;the values are naturally constrained by the data types. |
656 |
|
|
;K1, which is the initial value of "state", is assumed |
657 |
|
|
;assigned elsewhere. The snippet shown here uses only |
658 |
|
|
;K2. |
659 |
|
|
MOV state, A ;Get "state". |
660 |
|
|
ADD #K2, A ;Increase by K2. Carry flag |
661 |
|
|
;will be set if rollover to or |
662 |
|
|
;past zero. |
663 |
|
|
PUSH ST ;Save carry flag. |
664 |
|
|
MOV A, state ;Move new value back. |
665 |
|
|
POP ST ;Restore carry flag. |
666 |
|
|
JNC done ;If didn't roll, don't run sub. |
667 |
|
|
CALL A_SUBROUTINE ;Run sub. |
668 |
|
|
done: |
669 |
|
|
|
670 |
|
|
/* This is the 'C' version of the algorithm. It is not */ |
671 |
|
|
/* as easy or efficient in 'C' to detect rollover. */ |
672 |
|
|
|
673 |
|
|
void base_rate_sub(void) |
674 |
|
|
{ |
675 |
|
|
static unsigned int state = K1; |
676 |
|
|
unsigned int old_state; |
677 |
|
|
|
678 |
|
|
old_state = state; |
679 |
|
|
state += K2; |
680 |
|
|
if (state < old_state) |
681 |
|
|
{ |
682 |
|
|
A(); |
683 |
|
|
} |
684 |
|
|
} |
685 |
|
|
\end{verbatim} |
686 |
|
|
\caption{$2^q$ Rollover Rational Counting Algorithm} |
687 |
|
|
\label{alg:crat0:sfdv0:01d} |
688 |
|
|
\end{algorithm} |
689 |
|
|
|
690 |
|
|
\begin{algorithm} |
691 |
|
|
\begin{verbatim} |
692 |
|
|
/* The constants K1 through K4, which parameterize the */ |
693 |
|
|
/* counting behavior, are assumed assigned elsewhere in */ |
694 |
|
|
/* the code. The solution is analyzed in terms of the */ |
695 |
|
|
/* parameters K1 through K4. */ |
696 |
|
|
/* */ |
697 |
|
|
/* We also place the following restrictions on K1 through */ |
698 |
|
|
/* K4: */ |
699 |
|
|
/* K1 : K1 <= K3. */ |
700 |
|
|
/* K2 : K2 > 0. */ |
701 |
|
|
/* K3 : No restrictions. */ |
702 |
|
|
/* K4 : K4 > 0. */ |
703 |
|
|
|
704 |
|
|
void base_rate_sub(void) |
705 |
|
|
{ |
706 |
|
|
static unsigned int state = K1; |
707 |
|
|
|
708 |
|
|
if (state >= K3) |
709 |
|
|
{ |
710 |
|
|
state -= K4; |
711 |
|
|
A(); |
712 |
|
|
} |
713 |
|
|
else |
714 |
|
|
{ |
715 |
|
|
state += K2; |
716 |
|
|
B(); |
717 |
|
|
} |
718 |
|
|
} |
719 |
|
|
\end{verbatim} |
720 |
|
|
\caption{Rational Counting Algorithm With \texttt{else} Clause} |
721 |
|
|
\label{alg:crat0:sfdv0:02a} |
722 |
|
|
\end{algorithm} |
723 |
|
|
|
724 |
|
|
|
725 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
726 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
727 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
728 |
|
|
\subsection[Properties Of Algorithm \ref{alg:crat0:sfdv0:01a}] |
729 |
|
|
{Properties Of Rational Counting Algorithm \ref{alg:crat0:sfdv0:01a}} |
730 |
|
|
%Section tag: PRC0 |
731 |
|
|
\label{crat0:sfdv0:sprc0} |
732 |
|
|
|
733 |
|
|
Algorithm \ref{alg:crat0:sfdv0:01a} |
734 |
|
|
is used frequently in microcontroller |
735 |
|
|
software. A base rate subroutine\footnote{For brevity, we usually |
736 |
|
|
call this just the \emph{base subroutine}.} (named ``\texttt{base\_rate\_sub()}'' |
737 |
|
|
in the algorithm) is called at a periodic rate, and subroutine |
738 |
|
|
``\texttt{A()}'' is called at a lesser rate. |
739 |
|
|
We are interested in determining the relationships between the rates |
740 |
|
|
as a function of $K_1$, $K_2$, $K_3$, and $K_4$; and we are interested |
741 |
|
|
in developing other properties. |
742 |
|
|
|
743 |
|
|
Notationally when analyzing rational counting algorithms, we agree |
744 |
|
|
that $state_n$ denotes the value of the \texttt{state} variable |
745 |
|
|
after the $n$th invocation and before the $n+1$'th invocation |
746 |
|
|
of the base rate subroutine. |
747 |
|
|
Using this convention with Algorithm \ref{alg:crat0:sfdv0:01a}, |
748 |
|
|
$state_0 = K_1$.\footnote{Algorithm \ref{alg:crat0:sfdv0:01a} |
749 |
|
|
requires a knowledge of |
750 |
|
|
`C' to fully understand. The \texttt{static} keyword ensures that the |
751 |
|
|
variable \texttt{state} is initialized only once, at the time the program |
752 |
|
|
is loaded. \texttt{state} is \emph{not} initialized each time the |
753 |
|
|
base subroutine runs.} |
754 |
|
|
|
755 |
|
|
We can first easily derive the number of initial invocations of |
756 |
|
|
the base subroutine before ``\texttt{A()}'' is called for the first |
757 |
|
|
time. |
758 |
|
|
|
759 |
|
|
\begin{vworklemmastatement} |
760 |
|
|
\label{lem:crat0:sfdv0:sprc0:01} |
761 |
|
|
$N_{STARTUP}$, the number of invocations of the base subroutine |
762 |
|
|
in Algorithm \ref{alg:crat0:sfdv0:01a} before ``\texttt{A()}'' is called |
763 |
|
|
for the first time, is given by |
764 |
|
|
|
765 |
|
|
\begin{equation} |
766 |
|
|
\label{eq:lem:crat0:sfdv0:sprc0:01:01} |
767 |
|
|
N_{STARTUP} = |
768 |
|
|
\left\lceil |
769 |
|
|
{ |
770 |
|
|
\frac{-K_1 - K_2 + K_3}{K_2} |
771 |
|
|
} |
772 |
|
|
\right\rceil . |
773 |
|
|
\end{equation} |
774 |
|
|
\end{vworklemmastatement} |
775 |
|
|
\begin{vworklemmaproof} |
776 |
|
|
The value of \texttt{state} after the $n$th invocation |
777 |
|
|
is $state_n = K_1 + n K_2$. In order for the test in the |
778 |
|
|
\texttt{if()} statement not to be met, we require that |
779 |
|
|
|
780 |
|
|
\begin{equation} |
781 |
|
|
\label{eq:lem:crat0:sfdv0:sprc0:01:02} |
782 |
|
|
K_1 + n K_2 < K_3 |
783 |
|
|
\end{equation} |
784 |
|
|
|
785 |
|
|
\noindent{}or equivalently that |
786 |
|
|
|
787 |
|
|
\begin{equation} |
788 |
|
|
\label{eq:lem:crat0:sfdv0:sprc0:01:03} |
789 |
|
|
n < \frac{K_3 - K_1}{K_2} . |
790 |
|
|
\end{equation} |
791 |
|
|
|
792 |
|
|
Solving (\ref{eq:lem:crat0:sfdv0:sprc0:01:03}) for the largest |
793 |
|
|
value of $n \in \vworkintset$ which still meets the criterion |
794 |
|
|
yields (\ref{eq:lem:crat0:sfdv0:sprc0:01:01}). Note that |
795 |
|
|
the derivation of (\ref{eq:lem:crat0:sfdv0:sprc0:01:01}) requires |
796 |
|
|
that the restrictions on $K_1$ through $K_4$ documented in |
797 |
|
|
Algorithm \ref{alg:crat0:sfdv0:01a} be met. |
798 |
|
|
\end{vworklemmaproof} |
799 |
|
|
\begin{vworklemmaparsection}{Remarks} |
800 |
|
|
Note that if one chooses $K_1 > K_3 - K_2$ (in contradiction to the |
801 |
|
|
restrictions in Algorithm \ref{alg:crat0:sfdv0:01a}), it is possible |
802 |
|
|
to devise a counting scheme (and results analogous to this lemma) where |
803 |
|
|
``\texttt{A()}'' is run a number of times before it is |
804 |
|
|
\emph{not} run for the first time. The construction of an analogous |
805 |
|
|
lemma is the topic of Exercise \ref{exe:crat0:sexe0:01}. |
806 |
|
|
\end{vworklemmaparsection} |
807 |
|
|
|
808 |
|
|
\begin{vworklemmastatement} |
809 |
|
|
\label{lem:crat0:sfdv0:sprc0:02} |
810 |
|
|
Let $N_I$ be the number of times the Algorithm |
811 |
|
|
\ref{alg:crat0:sfdv0:01a} base subroutine |
812 |
|
|
is called, let $N_O$ be the number of times the |
813 |
|
|
``\texttt{A()}'' subroutine is called, let |
814 |
|
|
$f_I$ be the frequency of invocation of the |
815 |
|
|
Algorithm \ref{alg:crat0:sfdv0:01a} base subroutine, and let |
816 |
|
|
$f_O$ be the frequency of invocation of |
817 |
|
|
``\texttt{A()}''. Provided the constraints |
818 |
|
|
on $K_1$ through $K_4$ documented in |
819 |
|
|
Algorithm \ref{alg:crat0:sfdv0:01a} are met, |
820 |
|
|
|
821 |
|
|
\begin{equation} |
822 |
|
|
\label{eq:lem:crat0:sfdv0:sprc0:02:01} |
823 |
|
|
\lim_{N_I\rightarrow\infty}\frac{N_O}{N_I} |
824 |
|
|
= |
825 |
|
|
\frac{f_O}{f_I} |
826 |
|
|
= |
827 |
|
|
\frac{K_2}{K_4} . |
828 |
|
|
\end{equation} |
829 |
|
|
\end{vworklemmastatement} |
830 |
|
|
\begin{vworklemmaproof} |
831 |
|
|
(\ref{eq:lem:crat0:sfdv0:sprc0:02:01}) indicates that once |
832 |
|
|
the initial delay (determined by $K_1$ and $K_3$) has finished, |
833 |
|
|
$N_O/N_I$ will converge on a steady-state value of |
834 |
|
|
$K_2/K_4$. |
835 |
|
|
|
836 |
|
|
Assume that $K_1=0$ and $K_3=K_4$. The |
837 |
|
|
conditional subtraction then calculates |
838 |
|
|
$state \bmod K_4$. After the $n$th |
839 |
|
|
invocation of the base subroutine, the value |
840 |
|
|
of \texttt{state} will be |
841 |
|
|
|
842 |
|
|
\begin{equation} |
843 |
|
|
\label{eq:lem:crat0:sfdv0:sprc0:02:02} |
844 |
|
|
state_n|_{K_1=0, K_3=K_4} = n K_2 \bmod K_4 . |
845 |
|
|
\end{equation} |
846 |
|
|
|
847 |
|
|
Assume that for two distinct values of |
848 |
|
|
$n \in \vworkintsetnonneg$, $n_1$ and $n_2$, |
849 |
|
|
the value of the \texttt{state} variable is the same: |
850 |
|
|
|
851 |
|
|
\begin{equation} |
852 |
|
|
\label{eq:lem:crat0:sfdv0:sprc0:02:03} |
853 |
|
|
n_1 K_2 \bmod K_4 = n_2 K_2 \bmod K_4. |
854 |
|
|
\end{equation} |
855 |
|
|
|
856 |
|
|
Then |
857 |
|
|
|
858 |
|
|
\begin{equation} |
859 |
|
|
\label{eq:lem:crat0:sfdv0:sprc0:02:04} |
860 |
|
|
(n_2 - n_1) K_2 = i K_4, \; \exists i \in \vworkintsetpos . |
861 |
|
|
\end{equation} |
862 |
|
|
|
863 |
|
|
However, we have no knowledge of whether $K_2$ and $K_4$ are |
864 |
|
|
coprime (they are not required to be). We may rewrite |
865 |
|
|
(\ref{eq:lem:crat0:sfdv0:sprc0:02:04}) equivalently as |
866 |
|
|
|
867 |
|
|
\begin{equation} |
868 |
|
|
\label{eq:lem:crat0:sfdv0:sprc0:02:05} |
869 |
|
|
(n_2 - n_1) \frac{K_2}{\gcd(K_2, K_4)} = i \frac{K_4}{\gcd(K_2, K_4)}, |
870 |
|
|
\; \exists i \in \vworkintsetpos |
871 |
|
|
\end{equation} |
872 |
|
|
|
873 |
|
|
where of course by definition |
874 |
|
|
|
875 |
|
|
\begin{equation} |
876 |
|
|
\label{eq:lem:crat0:sfdv0:sprc0:02:06} |
877 |
|
|
\gcd \left( { \frac{K_2}{\gcd(K_2, K_4)}, \frac{K_4}{\gcd(K_2, K_4)} } \right) = 1. |
878 |
|
|
\end{equation} |
879 |
|
|
|
880 |
|
|
In order to satisfy (\ref{eq:lem:crat0:sfdv0:sprc0:02:05}), |
881 |
|
|
$n_2 - n_1$ must contain all of the prime factors of |
882 |
|
|
$K_4/\gcd(K_2,K_4)$ in at least the same multiplicities, |
883 |
|
|
and it follows that the set of values |
884 |
|
|
of $n_2-n_1$ that satisfies |
885 |
|
|
(\ref{eq:lem:crat0:sfdv0:sprc0:02:03}) is |
886 |
|
|
precisely the set of multiples of $K_4/\gcd(K_2,K_4)$: |
887 |
|
|
|
888 |
|
|
\begin{equation} |
889 |
|
|
\label{eq:lem:crat0:sfdv0:sprc0:02:07} |
890 |
|
|
n_2 - n_1 = j \frac{K_4}{\gcd(K_2, K_4)}, \; \exists j \in \vworkintsetpos . |
891 |
|
|
\end{equation} |
892 |
|
|
|
893 |
|
|
Examining (\ref{eq:lem:crat0:sfdv0:sprc0:02:02}), it can |
894 |
|
|
also be seen that |
895 |
|
|
|
896 |
|
|
\begin{equation} |
897 |
|
|
\label{eq:lem:crat0:sfdv0:sprc0:02:08} |
898 |
|
|
\gcd(K_2, K_4) \vworkdivides (n K_2 \bmod K_4), |
899 |
|
|
\end{equation} |
900 |
|
|
|
901 |
|
|
and so |
902 |
|
|
|
903 |
|
|
\begin{eqnarray} |
904 |
|
|
\label{eq:lem:crat0:sfdv0:sprc0:02:09} |
905 |
|
|
& n K_2 \bmod K_4 \in & \\ |
906 |
|
|
\nonumber |
907 |
|
|
& \{ 0, \gcd(K_2, K_4), 2 \gcd(K_2, K_4), \ldots , K_4 - \gcd(K_2, K_4) \} , & |
908 |
|
|
\end{eqnarray} |
909 |
|
|
|
910 |
|
|
a set which contains exactly $K_4/\gcd(K_2, K_4)$ elements. |
911 |
|
|
|
912 |
|
|
Thus we've established by the pigeonhole principle |
913 |
|
|
that the sequence of the |
914 |
|
|
values of the variable \texttt{state} |
915 |
|
|
specified by (\ref{eq:lem:crat0:sfdv0:sprc0:02:02}) |
916 |
|
|
repeats perfectly with periodicity $K_4/\gcd(K_2, K_4)$, |
917 |
|
|
and we've established that in one period, every element of the set |
918 |
|
|
specified in (\ref{eq:lem:crat0:sfdv0:sprc0:02:09}) appears exactly |
919 |
|
|
once. (However, we have not specified the order in which the |
920 |
|
|
elements appear, but this is not important for this lemma. In general |
921 |
|
|
the elements appear out of the order shown in |
922 |
|
|
Eq. \ref{eq:lem:crat0:sfdv0:sprc0:02:09}.) |
923 |
|
|
|
924 |
|
|
To establish the frequency with which the test against |
925 |
|
|
$K_4$ is met, note that if $state_n + K_2 \geq K_4$, then |
926 |
|
|
|
927 |
|
|
\begin{eqnarray} |
928 |
|
|
\label{eq:lem:crat0:sfdv0:sprc0:02:10} |
929 |
|
|
& \displaystyle{state_n \in \left\{ \frac{K_4-K_2}{\gcd(K_2,K_4)} \gcd(K_2, K_4), \right.} & \\ |
930 |
|
|
\nonumber & \displaystyle{\left. \left(\frac{K_4-K_2}{\gcd(K_2,K_4)} + 1 \right) \gcd(K_2, K_4), \ldots , |
931 |
|
|
K_4 - \gcd(K_2, K_4)\right\} ,} & |
932 |
|
|
\end{eqnarray} |
933 |
|
|
|
934 |
|
|
which has a cardinality $K_2/K_4$ that of the set in |
935 |
|
|
(\ref{eq:lem:crat0:sfdv0:sprc0:02:09}). Since the |
936 |
|
|
\texttt{state} variable cycles through the set in |
937 |
|
|
(\ref{eq:lem:crat0:sfdv0:sprc0:02:09}) with perfect periodicity and since |
938 |
|
|
$K_2/K_4$ of the set elements lead to the \texttt{if()} statement |
939 |
|
|
test being |
940 |
|
|
met, (\ref{eq:lem:crat0:sfdv0:sprc0:02:01}) is also met as |
941 |
|
|
$N_I\rightarrow\infty$. |
942 |
|
|
|
943 |
|
|
Note that if $K_1 \neq 0$, it simply changes the startup |
944 |
|
|
behavior of the rational counting. So long as $K_2 < K_4$, |
945 |
|
|
Algorithm \ref{alg:crat0:sfdv0:01a} will reach a steady state where |
946 |
|
|
(\ref{eq:lem:crat0:sfdv0:sprc0:02:01}) holds. |
947 |
|
|
Note that if $K_3 \neq K_4$, it simply ``shifts'' the sets |
948 |
|
|
specified in (\ref{eq:lem:crat0:sfdv0:sprc0:02:09}) |
949 |
|
|
and (\ref{eq:lem:crat0:sfdv0:sprc0:02:10}), but |
950 |
|
|
(\ref{eq:lem:crat0:sfdv0:sprc0:02:01}) still holds. |
951 |
|
|
The lemma has thus been proved |
952 |
|
|
for every case. (We have neglected to give |
953 |
|
|
the formal proof as required by the definition of a limit that |
954 |
|
|
for any arbitrarily small error $\epsilon$, a |
955 |
|
|
finite $N_I$ can be found so that |
956 |
|
|
the error is at or below $\epsilon$; however the skeptical reader |
957 |
|
|
is encouraged to complete Exercise \ref{exe:crat0:sexe0:02}.) |
958 |
|
|
\end{vworklemmaproof} |
959 |
|
|
\begin{vworklemmaparsection}{Remarks} |
960 |
|
|
It is possible to view the long-term accuracy of |
961 |
|
|
Algorithm \ref{alg:crat0:sfdv0:01a} in terms of a limit, as is done in |
962 |
|
|
(\ref{eq:lem:crat0:sfdv0:sprc0:02:01}). However, it is also |
963 |
|
|
possible to observe that $K_1$ and $K_3$ set a delay until |
964 |
|
|
the counting algorithm reaches steady state. |
965 |
|
|
With $K_3=K_4$, the attainment of |
966 |
|
|
steady state is characterized by the \texttt{state} variable |
967 |
|
|
being assigned for the first time to one of the values in |
968 |
|
|
(\ref{eq:lem:crat0:sfdv0:sprc0:02:09}). Once in steady state, |
969 |
|
|
the algorithm cycles with perfect periodic behavior through all of the |
970 |
|
|
$K_4/\gcd(K_2,K_4)$ elements in |
971 |
|
|
(\ref{eq:lem:crat0:sfdv0:sprc0:02:09}), but not necessarily in |
972 |
|
|
the order shown in the equation. |
973 |
|
|
During this period of length $K_4/\gcd(K_2,K_4)$, |
974 |
|
|
exactly $K_2/\gcd(K_2,K_4)$ invocations of the base |
975 |
|
|
subroutine result in |
976 |
|
|
subroutine ``\texttt{A()}'' being run, and exactly |
977 |
|
|
$(K_4-K_2)/\gcd(K_2,K_4)$ do not. Thus, after reaching steady-state the |
978 |
|
|
algorithm has \emph{perfect} accuracy if one considers periods of |
979 |
|
|
length $K_4/\gcd(K_2,K_4)$. |
980 |
|
|
\end{vworklemmaparsection} |
981 |
|
|
%\vworklemmafooter{} |
982 |
|
|
|
983 |
|
|
\begin{vworklemmastatement} |
984 |
|
|
\label{lem:crat0:sfdv0:sprc0:04} |
985 |
|
|
If $K_3=K_4$, $K_1=0$, and |
986 |
|
|
$\gcd(K_2, K_4)=1$\footnote{\label{footnote:lem:crat0:sfdv0:sprc0:04:01}If |
987 |
|
|
$\gcd(K_2, K_4) > 1$, then by Theorem |
988 |
|
|
\cprizeroxrefhyphen\ref{thm:cpri0:ppn0:00a} the largest |
989 |
|
|
value that $n K_2 \bmod K_4$ can attain is |
990 |
|
|
$K_4-\gcd(K_2, K_4)$ and the interval in |
991 |
|
|
(\ref{eq:lem:crat0:sfdv0:sprc0:04:01}) is correspondingly |
992 |
|
|
smaller. (\ref{eq:lem:crat0:sfdv0:sprc0:04:01}) is |
993 |
|
|
technically correct but not as conservative as possible. |
994 |
|
|
This is a minor point and we do not dwell on it.}, the error between |
995 |
|
|
the approximation to $N_O$ implemented by |
996 |
|
|
Algorithm \ref{alg:crat0:sfdv0:01a} and the ``ideal'' mapping is always |
997 |
|
|
in the set |
998 |
|
|
|
999 |
|
|
\begin{equation} |
1000 |
|
|
\label{eq:lem:crat0:sfdv0:sprc0:04:01} |
1001 |
|
|
\left[ - \frac{K_4 - 1}{K_4} , 0 \right] , |
1002 |
|
|
\end{equation} |
1003 |
|
|
|
1004 |
|
|
and no algorithm can be constructed to |
1005 |
|
|
confine the error to a smaller interval. |
1006 |
|
|
\end{vworklemmastatement} |
1007 |
|
|
\begin{vworklemmaproof} |
1008 |
|
|
With $K_1=0$ and $K_3 = K_4$, it can be verified analytically that |
1009 |
|
|
the total number of times the function ``\texttt{A()}'' has been |
1010 |
|
|
invoked up to and including the $n$th invocation of the base subroutine |
1011 |
|
|
is |
1012 |
|
|
|
1013 |
|
|
\begin{equation} |
1014 |
|
|
\label{eq:lem:crat0:sfdv0:sprc0:04:02} |
1015 |
|
|
N_O = \left\lfloor \frac{n K_2}{K_4} \right\rfloor . |
1016 |
|
|
\end{equation} |
1017 |
|
|
|
1018 |
|
|
On the other hand, the ``ideal'' number of invocations, which |
1019 |
|
|
we denote $\overline{N_O}$, is given by |
1020 |
|
|
|
1021 |
|
|
\begin{equation} |
1022 |
|
|
\label{eq:lem:crat0:sfdv0:sprc0:04:03} |
1023 |
|
|
\overline{N_O} = \frac{n K_2}{K_4} . |
1024 |
|
|
\end{equation} |
1025 |
|
|
|
1026 |
|
|
Quantization of the rational number in (\ref{eq:lem:crat0:sfdv0:sprc0:04:02}) |
1027 |
|
|
can introduce an error of up to $-(K_4-1)/K_4$, therefore |
1028 |
|
|
|
1029 |
|
|
\begin{equation} |
1030 |
|
|
\label{eq:lem:crat0:sfdv0:sprc0:04:04} |
1031 |
|
|
N_O - \overline{N_O} = |
1032 |
|
|
\left\lfloor \frac{n K_2}{K_4} \right\rfloor - \frac{n K_2}{K_4} |
1033 |
|
|
\in \left[ - \frac{K_4 - 1}{K_4} , 0 \right] . |
1034 |
|
|
\end{equation} |
1035 |
|
|
|
1036 |
|
|
This proves the error bound for Algorithm \ref{alg:crat0:sfdv0:01a}. |
1037 |
|
|
The proof that there can be no better algorithm is the topic |
1038 |
|
|
of Exercise \ref{exe:crat0:sexe0:06}. |
1039 |
|
|
\end{vworklemmaproof} |
1040 |
|
|
\begin{vworklemmaparsection}{Remarks} |
1041 |
|
|
Algorithm \ref{alg:crat0:sfdv0:01a} is \emph{optimal} in the |
1042 |
|
|
sense that no algorithm can achieve a tighter error |
1043 |
|
|
bound than (\ref{eq:lem:crat0:sfdv0:sprc0:04:01}). As |
1044 |
|
|
demonstrated in Exercises \ref{exe:crat0:sexe0:04} |
1045 |
|
|
and \ref{exe:crat0:sexe0:05}, $K_1 \neq 0$ can be chosen |
1046 |
|
|
to shift the interval in (\ref{eq:lem:crat0:sfdv0:sprc0:04:01}), but |
1047 |
|
|
the span of the interval cannot be reduced. |
1048 |
|
|
\end{vworklemmaparsection} |
1049 |
|
|
\vworklemmafooter{} |
1050 |
|
|
|
1051 |
|
|
Lemmas \ref{lem:crat0:sfdv0:sprc0:02} |
1052 |
|
|
and \ref{lem:crat0:sfdv0:sprc0:04} have demonstrated that the ratio of |
1053 |
|
|
counts $N_O/N_I$ will asymptotically |
1054 |
|
|
approach $K_2/K_4$ |
1055 |
|
|
(i.e. the long-term accuracy of Algorithm \ref{alg:crat0:sfdv0:01a} |
1056 |
|
|
is \emph{perfect}). |
1057 |
|
|
However, |
1058 |
|
|
for many applications it is also desirable to have a lack of |
1059 |
|
|
``bursty'' behavior. We demonstrate the lack of bursty |
1060 |
|
|
behavior in the following lemma. |
1061 |
|
|
|
1062 |
|
|
\begin{vworklemmastatement} |
1063 |
|
|
\label{lem:crat0:sfdv0:sprc0:03} |
1064 |
|
|
For Algorithm \ref{alg:crat0:sfdv0:01a}, once steady |
1065 |
|
|
state has been achieved, the number of consecutive |
1066 |
|
|
base subroutine invocations during which subroutine |
1067 |
|
|
``\texttt{A()}'' is executed is always in the set |
1068 |
|
|
|
1069 |
|
|
\begin{equation} |
1070 |
|
|
\label{eq:lem:crat0:sfdv0:sprc0:03:01} |
1071 |
|
|
\left\{ |
1072 |
|
|
\left\lfloor \frac{K_2}{K_4 - K_2} \right\rfloor , |
1073 |
|
|
\left\lceil \frac{K_2}{K_4 - K_2} \right\rceil |
1074 |
|
|
\right\} \cap \vworkintsetpos, |
1075 |
|
|
\end{equation} |
1076 |
|
|
|
1077 |
|
|
which contains one integer if $K_2/K_4 \leq 1/2$ or $(K_4-K_2) \vworkdivides K_2$, |
1078 |
|
|
or two integers otherwise. |
1079 |
|
|
|
1080 |
|
|
Once steady state has been achieved, the number of |
1081 |
|
|
consecutive base function invocations during which |
1082 |
|
|
subroutine ``\texttt{A()}'' is not executed is |
1083 |
|
|
always in the set |
1084 |
|
|
|
1085 |
|
|
\begin{equation} |
1086 |
|
|
\label{eq:lem:crat0:sfdv0:sprc0:03:02} |
1087 |
|
|
\left\{ |
1088 |
|
|
\left\lfloor \frac{K_4-K_2}{K_2} \right\rfloor , |
1089 |
|
|
\left\lceil \frac{K_4-K_2}{K_2} \right\rceil |
1090 |
|
|
\right\} \cap \vworkintsetpos, |
1091 |
|
|
\end{equation} |
1092 |
|
|
|
1093 |
|
|
which contains one integer if $K_2/K_4 \geq 1/2$ or $K_2 \vworkdivides K_4$, |
1094 |
|
|
or two integers otherwise. |
1095 |
|
|
\end{vworklemmastatement} |
1096 |
|
|
\begin{vworklemmaproof} |
1097 |
|
|
As before in Lemma \ref{lem:crat0:sfdv0:sprc0:02} |
1098 |
|
|
for convenience and without |
1099 |
|
|
loss of generality, assume $K_3=K_4$ and |
1100 |
|
|
$K_1=0$. Then after a transient period |
1101 |
|
|
determined by $K_1$ and $K_3$, the \texttt{state} |
1102 |
|
|
variable will be assigned one of the values in |
1103 |
|
|
(\ref{eq:lem:crat0:sfdv0:sprc0:02:09}) and cycle through |
1104 |
|
|
those values in an unestablished order but with perfect |
1105 |
|
|
periodicity. To accomplish this proof, we must establish |
1106 |
|
|
something about the order in which the \texttt{state} variable attains |
1107 |
|
|
the values in the set in (\ref{eq:lem:crat0:sfdv0:sprc0:02:09}). |
1108 |
|
|
|
1109 |
|
|
We can partition the set in (\ref{eq:lem:crat0:sfdv0:sprc0:02:09}) |
1110 |
|
|
into two sets; the set of values of \texttt{state} for which if the |
1111 |
|
|
base subroutine is invoked with \texttt{state} in this set, subroutine |
1112 |
|
|
``\texttt{A()}'' will not be invoked (we call this set $\phi_1$), |
1113 |
|
|
and the set of values of \texttt{state} for which if the |
1114 |
|
|
base subroutine is invoked with \texttt{state} in this set, subroutine |
1115 |
|
|
``\texttt{A()}'' will be invoked (we call this set $\phi_2$). |
1116 |
|
|
$\phi_1$ and $\phi_2$ are identified below. |
1117 |
|
|
|
1118 |
|
|
\begin{eqnarray} |
1119 |
|
|
\label{eq:lem:crat0:sfdv0:sprc0:03:03} |
1120 |
|
|
& \phi_1 = & \\ |
1121 |
|
|
\nonumber & |
1122 |
|
|
\displaystyle{\left\{ |
1123 |
|
|
0, \gcd(K_2, K_4), 2 \gcd(K_2, K_4), \ldots , |
1124 |
|
|
\left(\frac{K_4-K_2}{\gcd(K_2,K_4)} - 1 \right) \gcd(K_2, K_4) |
1125 |
|
|
\right\}} & |
1126 |
|
|
\end{eqnarray} |
1127 |
|
|
|
1128 |
|
|
\begin{eqnarray} |
1129 |
|
|
\label{eq:lem:crat0:sfdv0:sprc0:03:04} |
1130 |
|
|
& \displaystyle{ |
1131 |
|
|
\phi_2 = \left\{\left(\frac{K_4-K_2}{\gcd(K_2,K_4)}\right) \gcd(K_2, K_4),\right.} & \\ |
1132 |
|
|
\nonumber & \displaystyle{\left. |
1133 |
|
|
\left(\frac{K_4-K_2}{\gcd(K_2,K_4)} + 1 \right) \gcd(K_2, K_4) , |
1134 |
|
|
\ldots , |
1135 |
|
|
K_4 - \gcd(K_2, K_4) |
1136 |
|
|
\right\}} & |
1137 |
|
|
\end{eqnarray} |
1138 |
|
|
|
1139 |
|
|
We can also make the following four additional useful observations |
1140 |
|
|
about $\phi_1$ and $\phi_2$. Note that |
1141 |
|
|
(\ref{eq:lem:crat0:sfdv0:sprc0:03:07}) and |
1142 |
|
|
(\ref{eq:lem:crat0:sfdv0:sprc0:03:08}) become equality |
1143 |
|
|
if $\gcd(K_2, K_4) = 1$. |
1144 |
|
|
|
1145 |
|
|
\begin{equation} |
1146 |
|
|
\label{eq:lem:crat0:sfdv0:sprc0:03:05} |
1147 |
|
|
n(\phi_1) = \frac{K_4 - K_2}{\gcd(K_2, K_4)} |
1148 |
|
|
\end{equation} |
1149 |
|
|
|
1150 |
|
|
\begin{equation} |
1151 |
|
|
\label{eq:lem:crat0:sfdv0:sprc0:03:06} |
1152 |
|
|
n(\phi_2) = \frac{K_2}{\gcd(K_2, K_4)} |
1153 |
|
|
\end{equation} |
1154 |
|
|
|
1155 |
|
|
\begin{equation} |
1156 |
|
|
\label{eq:lem:crat0:sfdv0:sprc0:03:07} |
1157 |
|
|
\phi_1 \subseteq \{ 0, 1, \ldots , K_4 - K_2 - 1 \} |
1158 |
|
|
\end{equation} |
1159 |
|
|
|
1160 |
|
|
\begin{equation} |
1161 |
|
|
\label{eq:lem:crat0:sfdv0:sprc0:03:08} |
1162 |
|
|
\phi_2 \subseteq \{K_4 - K_2, \ldots , K_4 - 1 \} |
1163 |
|
|
\end{equation} |
1164 |
|
|
|
1165 |
|
|
We first prove (\ref{eq:lem:crat0:sfdv0:sprc0:03:01}). |
1166 |
|
|
If $state_n \in \phi_2$ at the time the base function |
1167 |
|
|
is invoked, then |
1168 |
|
|
``\texttt{A()}'' will be invoked. We also know that |
1169 |
|
|
since $state_n \in \phi_2$, $state_n + K_2 \geq K_4$, so |
1170 |
|
|
|
1171 |
|
|
\begin{equation} |
1172 |
|
|
\label{eq:lem:crat0:sfdv0:sprc0:03:09} |
1173 |
|
|
state_{n+1} \;\; =|_{state_n \in \phi_2} \;\; state_n - (K_4 - K_2) . |
1174 |
|
|
\end{equation} |
1175 |
|
|
|
1176 |
|
|
Thus so long as $state_n \in \phi_2$, $state_{n+1} < state_n$ |
1177 |
|
|
as specified above in (\ref{eq:lem:crat0:sfdv0:sprc0:03:09}). |
1178 |
|
|
With each invocation of the base subroutine, \texttt{state} will |
1179 |
|
|
``walk downward'' through $\phi_2$. It can |
1180 |
|
|
also be observed that when \texttt{state} drops below the smallest |
1181 |
|
|
element of $\phi_2$, the next value of \texttt{state} will |
1182 |
|
|
be in $\phi_1$. |
1183 |
|
|
|
1184 |
|
|
Note also that although the downward walk specified in |
1185 |
|
|
(\ref{eq:lem:crat0:sfdv0:sprc0:03:09}) walks downward in absolute steps |
1186 |
|
|
of $K_4-K_2$, this corresponds to $(K_4-K_2) / \gcd(K_2, K_4)$ |
1187 |
|
|
\emph{elements} of $\phi_2$, since the elements of $\phi_2$ are |
1188 |
|
|
separated by $\gcd(K_2, K_4)$. |
1189 |
|
|
|
1190 |
|
|
Given the ``downward walk'' specified in (\ref{eq:lem:crat0:sfdv0:sprc0:03:09}), |
1191 |
|
|
the only question to be answered is how many consecutive values of |
1192 |
|
|
\texttt{state}, separated by $K_4-K_2$ (or $(K_4-K_2)/\gcd(K_2, K_4)$ elements), |
1193 |
|
|
can ``fit'' into |
1194 |
|
|
$\phi_2$. Considering that $n(\phi_2) = K_2/\gcd(K_2, K_4)$ |
1195 |
|
|
(Eq. \ref{eq:lem:crat0:sfdv0:sprc0:03:06}) and that the |
1196 |
|
|
downward step represents $(K_4-K_2)/\gcd(K_2, K_4)$ set elements, |
1197 |
|
|
(\ref{eq:lem:crat0:sfdv0:sprc0:03:01}) comes immediately by |
1198 |
|
|
a graphical argument. |
1199 |
|
|
|
1200 |
|
|
We now prove (\ref{eq:lem:crat0:sfdv0:sprc0:03:02}). |
1201 |
|
|
This can be proved using exactly the same arguments |
1202 |
|
|
as for (\ref{eq:lem:crat0:sfdv0:sprc0:03:01}), but |
1203 |
|
|
considering the upward walk through $\phi_1$ rather |
1204 |
|
|
than the downward walk through $\phi_2$. |
1205 |
|
|
|
1206 |
|
|
As with Lemma \ref{lem:crat0:sfdv0:sprc0:02}, |
1207 |
|
|
note that the choices of $K_1$ and $K_3$ do not |
1208 |
|
|
materially affect the proof above. $K_1$ and |
1209 |
|
|
$K_3$ only set a delay until the rational counting |
1210 |
|
|
algorithm reaches steady state. $K_3$ only shifts |
1211 |
|
|
the sets $\phi_1$ and $\phi_2$. |
1212 |
|
|
\end{vworklemmaproof} |
1213 |
|
|
\begin{vworklemmaparsection}{Remark \#1} |
1214 |
|
|
This lemma proves an \emph{extremely} important property for the |
1215 |
|
|
usability of Algorithm \ref{alg:crat0:sfdv0:01a}. It says that once |
1216 |
|
|
steady state has been reached, the variability in the number of consecutive |
1217 |
|
|
times ``\texttt{A()}'' is run or not run is at most one count. |
1218 |
|
|
\end{vworklemmaparsection} |
1219 |
|
|
\begin{vworklemmaparsection}{Remark \#2} |
1220 |
|
|
It is probably also possible to construct a rational counting algorithm |
1221 |
|
|
so that the number of consecutive times ``\texttt{A()}'' is run is constant, |
1222 |
|
|
but the algorithm achieves long-term accuracy by varying only the number |
1223 |
|
|
of consecutive times ``\texttt{A()}'' is not run (or vice-versa), but this |
1224 |
|
|
is not done here. |
1225 |
|
|
\end{vworklemmaparsection} |
1226 |
|
|
\begin{vworklemmaparsection}{Remark \#3} |
1227 |
|
|
There is no requirement that $K_2$ and $K_4$ be coprime. In fact, as |
1228 |
|
|
demonstrated later, it may be advantageous to choose a large $K_2$ and |
1229 |
|
|
$K_4$ to approximate a simple ratio so that very fine adjustments can be |
1230 |
|
|
made. For example, if the ideal ratio is 1/2, it may be desirable |
1231 |
|
|
in some applications to |
1232 |
|
|
choose $K_2$=1,000 and $K_4$=2,000 so that fine adjustments can be made |
1233 |
|
|
by slightly perturbing $K_2$ or $K_4$. One might adjust 1,000/2,000 downward |
1234 |
|
|
to 999/2,000 or upward to 1,001/2,000 by modifying $K_2$ |
1235 |
|
|
(both very fine adjustments). |
1236 |
|
|
\end{vworklemmaparsection} |
1237 |
|
|
\begin{vworklemmaparsection}{Remark \#4} |
1238 |
|
|
The most common choice of $K_1$ in practice is 0. If $K_1=0$ is chosen, |
1239 |
|
|
it can be shown that the number of initial invocations of the |
1240 |
|
|
base subroutine is in the set identified in |
1241 |
|
|
(\ref{eq:lem:crat0:sfdv0:sprc0:03:01}). |
1242 |
|
|
(See Exercise \ref{exe:crat0:sexe0:07}.) |
1243 |
|
|
\end{vworklemmaparsection} |
1244 |
|
|
\vworklemmafooter{} |
1245 |
|
|
|
1246 |
|
|
For microcontroller work, it is considered |
1247 |
|
|
a desirable property that software components be resilient |
1248 |
|
|
to state upset |
1249 |
|
|
(see Section \chgrzeroxrefhyphen\ref{chgr0:sdda0:srob0}). |
1250 |
|
|
It can be observed that Algorithm \ref{alg:crat0:sfdv0:01a} will |
1251 |
|
|
exhibit very anomalous behavior if \texttt{state} is upset to a very negative |
1252 |
|
|
value. One possible correction to this shortcoming is illustrated |
1253 |
|
|
in Figure \ref{fig:crat0:sfdv0:sprc0:01}. Other possible |
1254 |
|
|
corrections are the topic of Exercise \ref{exe:crat0:sexe0:08}. |
1255 |
|
|
|
1256 |
|
|
\begin{figure} |
1257 |
|
|
\begin{verbatim} |
1258 |
|
|
/* The constants K1 through K4, which parameterize the */ |
1259 |
|
|
/* counting behavior, are assumed assigned elsewhere in */ |
1260 |
|
|
/* the code. The solution is analyzed in terms of the */ |
1261 |
|
|
/* parameters K1 through K4. */ |
1262 |
|
|
/* */ |
1263 |
|
|
/* We also place the following restrictions on K1 through */ |
1264 |
|
|
/* K4: */ |
1265 |
|
|
/* K1 : K1 <= K3 - K2. */ |
1266 |
|
|
/* K2 : K4 > K2 > 0. */ |
1267 |
|
|
/* K3 : No restrictions. */ |
1268 |
|
|
/* K4 : K4 > K2 > 0. */ |
1269 |
|
|
|
1270 |
|
|
void base_rate_func(void) |
1271 |
|
|
{ |
1272 |
|
|
static int state = K1; |
1273 |
|
|
|
1274 |
|
|
state += K2; |
1275 |
|
|
|
1276 |
|
|
if ((state < K1) || (state >= K3)) |
1277 |
|
|
{ |
1278 |
|
|
state -= K4; |
1279 |
|
|
A(); |
1280 |
|
|
} |
1281 |
|
|
} |
1282 |
|
|
\end{verbatim} |
1283 |
|
|
\caption{Algorithm \ref{alg:crat0:sfdv0:01a} With State Upset Shortcoming |
1284 |
|
|
Corrected} |
1285 |
|
|
\label{fig:crat0:sfdv0:sprc0:01} |
1286 |
|
|
\end{figure} |
1287 |
|
|
|
1288 |
|
|
\begin{vworkexamplestatement} |
1289 |
|
|
\label{ex:crat0:sfdv0:sprc0:01} |
1290 |
|
|
Determine the behavior of Algorithm \ref{alg:crat0:sfdv0:01a} with |
1291 |
|
|
$K_1=0$, $K_2=30$, and $K_3=K_4=50$. |
1292 |
|
|
\end{vworkexamplestatement} |
1293 |
|
|
\begin{vworkexampleparsection}{Solution} |
1294 |
|
|
We first predict the behavior, and then trace the algorithm to |
1295 |
|
|
verify whether the predictions are accurate. |
1296 |
|
|
|
1297 |
|
|
We make the following predictions: |
1298 |
|
|
|
1299 |
|
|
\begin{itemize} |
1300 |
|
|
\item The steady state sequence of invocations of ``\texttt{A()}'' will |
1301 |
|
|
be periodic with period |
1302 |
|
|
$K_4/\gcd(K_2, K_4) = 50/10 = 5$, as described |
1303 |
|
|
in Lemma \ref{lem:crat0:sfdv0:sprc0:02}. |
1304 |
|
|
\item The number of initial invocations of the |
1305 |
|
|
base subroutine in which ``\texttt{A()}'' |
1306 |
|
|
is not run will be |
1307 |
|
|
$\lceil (K_4 - K_2) / K_2 \rceil = \lceil 2/3 \rceil = 1$, |
1308 |
|
|
as described in Remark \#4 of |
1309 |
|
|
Lemma \ref{lem:crat0:sfdv0:sprc0:03} and in the solution to |
1310 |
|
|
Exercise \ref{exe:crat0:sexe0:07}. |
1311 |
|
|
\item In steady state, the number of consecutive invocations of the |
1312 |
|
|
base subroutine during which ``\texttt{A()}'' |
1313 |
|
|
is not executed will always be 1, as |
1314 |
|
|
described in Equation \ref{eq:lem:crat0:sfdv0:sprc0:03:02} of |
1315 |
|
|
Lemma \ref{lem:crat0:sfdv0:sprc0:03}. |
1316 |
|
|
(Applying Eq. \ref{eq:lem:crat0:sfdv0:sprc0:03:02} |
1317 |
|
|
yields \ |
1318 |
|
|
$\{ \lfloor 20/30 \rfloor , \lceil 20/30 \rceil \} \cap \vworkintsetpos % |
1319 |
|
|
= \{ 0,1 \} \cap \{1, 2, \ldots \} = \{ 1 \}$.) |
1320 |
|
|
\item In steady state, the number of consecutive invocations of the |
1321 |
|
|
base subroutine during which ``\texttt{A()}'' |
1322 |
|
|
is executed will always be 1 or 2, as |
1323 |
|
|
described in Equation \ref{eq:lem:crat0:sfdv0:sprc0:03:01} of |
1324 |
|
|
Lemma \ref{lem:crat0:sfdv0:sprc0:03}. |
1325 |
|
|
(Applying Eq. \ref{eq:lem:crat0:sfdv0:sprc0:03:01} |
1326 |
|
|
yields \ |
1327 |
|
|
$\{ \lfloor 30/20 \rfloor , \lceil 30/20 \rceil \} \cap \vworkintsetpos % |
1328 |
|
|
= \{ 1,2 \} \cap \{1, 2, \ldots \} = \{ 1,2 \}$.) |
1329 |
|
|
\item The rational counting algorithm will have |
1330 |
|
|
perfect long-term accuracy. |
1331 |
|
|
\end{itemize} |
1332 |
|
|
|
1333 |
|
|
We can verify the predictions above by tracing the behavior of |
1334 |
|
|
Algorithm \ref{alg:crat0:sfdv0:01a}. We adopt the convention |
1335 |
|
|
that $A_n = 1$ if subroutine ``\texttt{A()}'' is invoked during |
1336 |
|
|
the $n$th invocation of the base subroutine. |
1337 |
|
|
Table \ref{tbl:crat0:sfdv0:sprc0:01} |
1338 |
|
|
contains the results of tracing Algorithm \ref{alg:crat0:sfdv0:01a} |
1339 |
|
|
with $K_1=0$, $K_2=30$, and $K_3=K_4=50$. |
1340 |
|
|
|
1341 |
|
|
\begin{table} |
1342 |
|
|
\caption{Trace Of Algorithm \ref{alg:crat0:sfdv0:01a} With |
1343 |
|
|
$K_1=0$, $K_2=30$, And $K_3=K_4=50$ (Example \ref{ex:crat0:sfdv0:sprc0:01})} |
1344 |
|
|
\label{tbl:crat0:sfdv0:sprc0:01} |
1345 |
|
|
\begin{center} |
1346 |
|
|
\begin{tabular}{|c|c|c|} |
1347 |
|
|
\hline |
1348 |
|
|
Index ($n$) & $state_n$ & $A_n$ \\ |
1349 |
|
|
\hline |
1350 |
|
|
\hline |
1351 |
|
|
0 & 0 & N/A \\ |
1352 |
|
|
\hline |
1353 |
|
|
1 & 30 & 0 \\ |
1354 |
|
|
\hline |
1355 |
|
|
2 & 10 & 1 \\ |
1356 |
|
|
\hline |
1357 |
|
|
3 & 40 & 0 \\ |
1358 |
|
|
\hline |
1359 |
|
|
4 & 20 & 1 \\ |
1360 |
|
|
\hline |
1361 |
|
|
5 & 0 & 1 \\ |
1362 |
|
|
\hline |
1363 |
|
|
6 & 30 & 0 \\ |
1364 |
|
|
\hline |
1365 |
|
|
7 & 10 & 1 \\ |
1366 |
|
|
\hline |
1367 |
|
|
8 & 40 & 0 \\ |
1368 |
|
|
\hline |
1369 |
|
|
9 & 20 & 1 \\ |
1370 |
|
|
\hline |
1371 |
|
|
10 & 0 & 1 \\ |
1372 |
|
|
\hline |
1373 |
|
|
\end{tabular} |
1374 |
|
|
\end{center} |
1375 |
|
|
\end{table} |
1376 |
|
|
|
1377 |
|
|
It can be verfied from the table that all of the |
1378 |
|
|
predicted properties are exhibited by the |
1379 |
|
|
algorithm. |
1380 |
|
|
\end{vworkexampleparsection} |
1381 |
|
|
\vworkexamplefooter{} |
1382 |
|
|
|
1383 |
|
|
A second characteristic of Algorithm \ref{alg:crat0:sfdv0:01a} |
1384 |
|
|
that should be analyzed carefully is the behavior |
1385 |
|
|
of the algorithm if parameters $K_2$ and $K_4$ are adjusted |
1386 |
|
|
``on the fly''. ``On-the-fly'' adjustment |
1387 |
|
|
raises the following concerns. We assume for convenience |
1388 |
|
|
that $K_1=0$ and $K_3=K_4$. |
1389 |
|
|
|
1390 |
|
|
\begin{enumerate} |
1391 |
|
|
\item \label{enum:crat0:sfdv0:sprc0:01:01} |
1392 |
|
|
\textbf{Critical section protocol:} if the |
1393 |
|
|
rational counting algorithm is implemented in a process which |
1394 |
|
|
is asynchronous to the process which desires to change |
1395 |
|
|
$K_2$ and $K_4$, what precautions must be taken? |
1396 |
|
|
\item \label{enum:crat0:sfdv0:sprc0:01:02} |
1397 |
|
|
\textbf{Anomalous behavior:} will the rational |
1398 |
|
|
counting algorithm behave in a \emph{very} unexpected way |
1399 |
|
|
if $K_2$ and $K_4$ are changed on the fly? |
1400 |
|
|
\item \label{enum:crat0:sfdv0:sprc0:01:03} |
1401 |
|
|
\textbf{Preservation of accuracy:} even if the behavior |
1402 |
|
|
exhibited is not \emph{extremely} anomalous, how should |
1403 |
|
|
$K_2$ and $K_4$ be modified on the fly so as to preserve the |
1404 |
|
|
maximum accuracy? |
1405 |
|
|
\end{enumerate} |
1406 |
|
|
|
1407 |
|
|
\textbf{(Concern \#\ref{enum:crat0:sfdv0:sprc0:01:02}):} It can be observed |
1408 |
|
|
with Algorithm \ref{alg:crat0:sfdv0:01a} that neither increasing |
1409 |
|
|
nor decreasing $K_2$ nor $K_4$ on the fly |
1410 |
|
|
will lead to \emph{highly} anomalous |
1411 |
|
|
behavior. Each invocation of the algorithm will map |
1412 |
|
|
\texttt{state} back into the set identified in |
1413 |
|
|
(\ref{eq:lem:crat0:sfdv0:sprc0:02:09}). Thus on-the-fly changes |
1414 |
|
|
to $K_2$ and $K_4$ will establish the rational counting algorithm |
1415 |
|
|
immediately into steady-state behavior, and the result will not be |
1416 |
|
|
\emph{highly} anomalous if such on-the-fly changes are not |
1417 |
|
|
made very often. |
1418 |
|
|
|
1419 |
|
|
\textbf{(Concern \#\ref{enum:crat0:sfdv0:sprc0:01:03}):} It can be deduced |
1420 |
|
|
from |
1421 |
|
|
(\ref{eq:lem:crat0:sfdv0:sprc0:04:02}), |
1422 |
|
|
(\ref{eq:lem:crat0:sfdv0:sprc0:04:03}), and |
1423 |
|
|
(\ref{eq:lem:crat0:sfdv0:sprc0:04:04}) that the value of the |
1424 |
|
|
\texttt{state} variable in Algorithm \ref{alg:crat0:sfdv0:01a} |
1425 |
|
|
satisfies the relationship |
1426 |
|
|
|
1427 |
|
|
\begin{equation} |
1428 |
|
|
\label{eq:crat0:sfdv0:sprc0:01} |
1429 |
|
|
\overline{N_O} - N_O = \frac{state}{K_4} ; |
1430 |
|
|
\end{equation} |
1431 |
|
|
|
1432 |
|
|
\noindent{}in other words, the \texttt{state} variable |
1433 |
|
|
contains the remainder of an effective division by $K_4$ |
1434 |
|
|
and thus maintains the fractional part of $\overline{N_O}$. |
1435 |
|
|
Altering $K_4$ on the fly to a new value |
1436 |
|
|
(say, $\overline{K_4}$) may be problematic, because |
1437 |
|
|
to preserve the current fractional part |
1438 |
|
|
of $\overline{N_O}$, one must adjust it for |
1439 |
|
|
the new denominator $\overline{K_4}$. This requires |
1440 |
|
|
solving the equation |
1441 |
|
|
|
1442 |
|
|
\begin{equation} |
1443 |
|
|
\label{eq:crat0:sfdv0:sprc0:02} |
1444 |
|
|
\frac{state}{K_4} = \frac{n}{\;\;\overline{K_4}\;\;} |
1445 |
|
|
\end{equation} |
1446 |
|
|
|
1447 |
|
|
\noindent{}for $n$ which must be an integer to avoid |
1448 |
|
|
loss of information. In general, |
1449 |
|
|
this would require that $K_4 \vworkdivides \overline{K_4}$, |
1450 |
|
|
a constraint which would be rarely met. Thus, for high-precision |
1451 |
|
|
applications where a new rational counting rate should become effective |
1452 |
|
|
seamlessly, the best strategy would seem to be to modify $K_2$ only. |
1453 |
|
|
It can be verified that modifying $K_2$ on the fly accomplishes |
1454 |
|
|
a perfect rate transition. |
1455 |
|
|
|
1456 |
|
|
\textbf{(Concern \#\ref{enum:crat0:sfdv0:sprc0:01:01}):} In microcontroller work, |
1457 |
|
|
ordinal data types often represent machine-native data types. In such cases, |
1458 |
|
|
it may be possible for one process to set $K_2$ or $K_4$ |
1459 |
|
|
for another process that is asynchronous with respect to it by relying |
1460 |
|
|
on the atomicity of machine instructions (i.e. without formal mutual |
1461 |
|
|
exclusion protocol). However, in other cases where the ordinal data types |
1462 |
|
|
of $K_2$ or $K_4$ are larger than can be accomodated by |
1463 |
|
|
a single machine instruction or where $K_2$ and $K_4$ must be modified |
1464 |
|
|
together atomically, mutual exclusion protocol should be used to |
1465 |
|
|
prevent anomalous behavior due to race conditions (see |
1466 |
|
|
Exercise \ref{exe:crat0:sexe0:14}). |
1467 |
|
|
|
1468 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1469 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1470 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1471 |
|
|
\subsection[Properties Of Algorithm \ref{alg:crat0:sfdv0:01b}] |
1472 |
|
|
{Properties Of Rational Counting Algorithm \ref{alg:crat0:sfdv0:01b}} |
1473 |
|
|
%Section tag: PRC1 |
1474 |
|
|
\label{crat0:sfdv0:sprc1} |
1475 |
|
|
|
1476 |
|
|
Algorithm \ref{alg:crat0:sfdv0:01a} |
1477 |
|
|
has the disadvantage that it requires $K_2/K_4 < 1$ (i.e. it can only |
1478 |
|
|
decrease frequency, but never increase frequency). This deficiency |
1479 |
|
|
can be corrected by using |
1480 |
|
|
Algorithm \ref{alg:crat0:sfdv0:01b}. |
1481 |
|
|
|
1482 |
|
|
Note that Algorithm \ref{alg:crat0:sfdv0:01b} will properly deal with $K_2$ and |
1483 |
|
|
$K_4$ chosen such that $0 < K_2/K_4 < \infty$. |
1484 |
|
|
|
1485 |
|
|
The most common reason that one may want a counting algorithm |
1486 |
|
|
that will correctly handle |
1487 |
|
|
$K_2/K_4 \geq 1$ is to conveniently handle $K_2/K_4 \approx 1$. |
1488 |
|
|
In practice, $K_2/K_4$ may represent a quantity that is |
1489 |
|
|
normally very close to |
1490 |
|
|
1 but may also be slightly less than or slightly greater than 1. |
1491 |
|
|
For example, one may use $K_2/K_4 \approx 1$ to correct for a |
1492 |
|
|
crystal or a resonator which deviates slightly from its nominal |
1493 |
|
|
frequency. We illustrate this with the following example. |
1494 |
|
|
|
1495 |
|
|
\begin{vworkexamplestatement} |
1496 |
|
|
\label{ex:crat0:sfdv0:sprc1:01} |
1497 |
|
|
A microcontroller software load keeps time via an interrupt |
1498 |
|
|
service routine that runs every 1ms, but this frequency may be |
1499 |
|
|
off by as much as 1 part in 10,000 due to variations in |
1500 |
|
|
crystal or resonator manufacture. The interrupt service routine |
1501 |
|
|
updates a counter which represents the number of milliseconds elapsed since |
1502 |
|
|
the software load was reset. Devise a rational counting strategy |
1503 |
|
|
based on Algorithm \ref{alg:crat0:sfdv0:01b} |
1504 |
|
|
which will allow the time accuracy to be trimmed to within |
1505 |
|
|
one second per year or less by adjusting only $K_4$, and implement the counting strategy |
1506 |
|
|
in software. |
1507 |
|
|
\end{vworkexamplestatement} |
1508 |
|
|
\begin{vworkexampleparsection}{Solution} |
1509 |
|
|
$K_2/K_4$ will be nominally very close to 1 ($K_2 \approx K_4$). |
1510 |
|
|
If we assume that each year has 365.2422\footnote{The period of the earth's |
1511 |
|
|
rotation about the sun is not an integral number of days, which is why the |
1512 |
|
|
rules for leap years exist. Ironically, the assignment of leap years is itself |
1513 |
|
|
a problem very similar to the rational counting problems discussed in this chapter.} days |
1514 |
|
|
($\approx$ 31,556,926 seconds), then choosing |
1515 |
|
|
$K_2 \approx K_4 = 31,556,926$ will yield satisfactory results. |
1516 |
|
|
If we may need to compensate for up to 1 part in 10,000 of crystal or resonator |
1517 |
|
|
inaccuracy, we may need to adjust $K_2$ as low as 0.9999 $\times$ 31,556,926 $\approx$ |
1518 |
|
|
31,553,770 (to compensate for a fast |
1519 |
|
|
crystal or resonator) or as |
1520 |
|
|
high as 1.0001 $\times$ 31,556,926 |
1521 |
|
|
$\approx$ 31,560,082 |
1522 |
|
|
(to compensate for a slow crystal or resonator). Choosing |
1523 |
|
|
$K_4 = 31,556,926$ yields the convenient relationship that each |
1524 |
|
|
count in $K_2$ corresponds to one second per year. |
1525 |
|
|
|
1526 |
|
|
\begin{figure} |
1527 |
|
|
\begin{verbatim} |
1528 |
|
|
/* The constants K1 through K4, which parameterize the */ |
1529 |
|
|
/* counting behavior, are assumed assigned elsewhere in */ |
1530 |
|
|
/* the code. */ |
1531 |
|
|
/* */ |
1532 |
|
|
/* The variable time_count below is the number of milli- */ |
1533 |
|
|
/* seconds since the software was reset. */ |
1534 |
|
|
int time_count = 0; |
1535 |
|
|
|
1536 |
|
|
/* It is assumed that the base rate subroutine below is */ |
1537 |
|
|
/* called every millisecond (or, at least what should be */ |
1538 |
|
|
/* every millisecond of the crystal or resonator were */ |
1539 |
|
|
/* perfect). */ |
1540 |
|
|
|
1541 |
|
|
void base_rate_sub(void) |
1542 |
|
|
{ |
1543 |
|
|
static int state = K1; |
1544 |
|
|
|
1545 |
|
|
state += K2; |
1546 |
|
|
|
1547 |
|
|
while (state >= K3) |
1548 |
|
|
{ |
1549 |
|
|
state -= K4; |
1550 |
|
|
time_count++; |
1551 |
|
|
} |
1552 |
|
|
} |
1553 |
|
|
\end{verbatim} |
1554 |
|
|
\caption{Algorithm \ref{alg:crat0:sfdv0:01b} Applied To Timekeeping |
1555 |
|
|
(Example \ref{ex:crat0:sfdv0:sprc1:01})} |
1556 |
|
|
\label{fig:ex:crat0:sfdv0:sprc1:01:01} |
1557 |
|
|
\end{figure} |
1558 |
|
|
|
1559 |
|
|
Figure \ref{fig:ex:crat0:sfdv0:sprc1:01:01} provides an illustration |
1560 |
|
|
of Algorithm \ref{alg:crat0:sfdv0:01b} applied in this scenario. |
1561 |
|
|
We assume that $K_4$ contains the constant value 31,556,926 |
1562 |
|
|
and that $K_2$ is modified about this value either downwards or upwards |
1563 |
|
|
to trim the timekeeping. Note that Algorithm \ref{alg:crat0:sfdv0:01b} will correctly |
1564 |
|
|
handle $K_2 \geq K_4$. |
1565 |
|
|
|
1566 |
|
|
Also note in the implementation illustrated in Figure |
1567 |
|
|
\ref{fig:ex:crat0:sfdv0:sprc1:01:01} that large integers (27 bits or more) |
1568 |
|
|
are required. (See also Exercise \ref{exe:crat0:sexe0:09}). |
1569 |
|
|
\end{vworkexampleparsection} |
1570 |
|
|
\vworkexamplefooter{} |
1571 |
|
|
|
1572 |
|
|
It may not be obvious whether Algorithm \ref{alg:crat0:sfdv0:01b} has the |
1573 |
|
|
same or similar desirable properties as Algorithm \ref{alg:crat0:sfdv0:01a} |
1574 |
|
|
presented |
1575 |
|
|
in Lemmas |
1576 |
|
|
\ref{lem:crat0:sfdv0:sprc0:01}, |
1577 |
|
|
\ref{lem:crat0:sfdv0:sprc0:02}, |
1578 |
|
|
\ref{lem:crat0:sfdv0:sprc0:04}, |
1579 |
|
|
and |
1580 |
|
|
\ref{lem:crat0:sfdv0:sprc0:03}. |
1581 |
|
|
Algorithm \ref{alg:crat0:sfdv0:01b} does have these desirable |
1582 |
|
|
properties, and these properties are presented as |
1583 |
|
|
Lemmas \ref{lem:crat0:sfdv0:sprc1:01}, |
1584 |
|
|
\ref{lem:crat0:sfdv0:sprc1:02}, |
1585 |
|
|
\ref{lem:crat0:sfdv0:sprc1:03}, and |
1586 |
|
|
\ref{lem:crat0:sfdv0:sprc1:04}. |
1587 |
|
|
The proofs of these lemmas are identical or very similar to the proofs |
1588 |
|
|
of Lemmas |
1589 |
|
|
\ref{lem:crat0:sfdv0:sprc0:01}, |
1590 |
|
|
\ref{lem:crat0:sfdv0:sprc0:02}, |
1591 |
|
|
\ref{lem:crat0:sfdv0:sprc0:04}, |
1592 |
|
|
and |
1593 |
|
|
\ref{lem:crat0:sfdv0:sprc0:03}; |
1594 |
|
|
and so these proofs when not identical are presented as exercises. |
1595 |
|
|
Note that Algorithm \ref{alg:crat0:sfdv0:01b} behaves identically to |
1596 |
|
|
Algorithm \ref{alg:crat0:sfdv0:01a} when $K_2 < K_4$, and the |
1597 |
|
|
case of $K_2=K_4$ is trivial, so in general only |
1598 |
|
|
the behavior when $K_2 > K_4$ remains to be proved. |
1599 |
|
|
|
1600 |
|
|
\begin{vworklemmastatement} |
1601 |
|
|
\label{lem:crat0:sfdv0:sprc1:01} |
1602 |
|
|
$N_{STARTUP}$, the number of invocations of the base subroutine |
1603 |
|
|
in Algorithm \ref{alg:crat0:sfdv0:01b} before ``\texttt{A()}'' is called |
1604 |
|
|
for the first time, is given by |
1605 |
|
|
|
1606 |
|
|
\begin{equation} |
1607 |
|
|
\label{eq:lem:crat0:sfdv0:sprc1:01:01} |
1608 |
|
|
N_{STARTUP} = |
1609 |
|
|
\left\lceil |
1610 |
|
|
{ |
1611 |
|
|
\frac{-K_1 - K_2 + K_3}{K_2} |
1612 |
|
|
} |
1613 |
|
|
\right\rceil . |
1614 |
|
|
\end{equation} |
1615 |
|
|
\end{vworklemmastatement} |
1616 |
|
|
\begin{vworklemmaproof} |
1617 |
|
|
The proof is identical to the proof of Lemma |
1618 |
|
|
\ref{lem:crat0:sfdv0:sprc0:01}. |
1619 |
|
|
\end{vworklemmaproof} |
1620 |
|
|
|
1621 |
|
|
|
1622 |
|
|
\begin{vworklemmastatement} |
1623 |
|
|
\label{lem:crat0:sfdv0:sprc1:02} |
1624 |
|
|
Let $N_I$ be the number of times the Algorithm \ref{alg:crat0:sfdv0:01b} |
1625 |
|
|
base subroutine |
1626 |
|
|
is called, let $N_O$ be the number of times the |
1627 |
|
|
``\texttt{A()}'' subroutine is called, let |
1628 |
|
|
$f_I$ be the frequency of invocation of the |
1629 |
|
|
Algorithm \ref{alg:crat0:sfdv0:01a} base subroutine, and let |
1630 |
|
|
$f_O$ be the frequency of invocation of |
1631 |
|
|
``\texttt{A()}''. |
1632 |
|
|
|
1633 |
|
|
\begin{equation} |
1634 |
|
|
\label{eq:lem:crat0:sfdv0:sprc1:02:01} |
1635 |
|
|
\lim_{N_I\rightarrow\infty}\frac{N_O}{N_I} |
1636 |
|
|
= |
1637 |
|
|
\frac{f_O}{f_I} |
1638 |
|
|
= |
1639 |
|
|
\frac{K_2}{K_4} . |
1640 |
|
|
\end{equation} |
1641 |
|
|
\end{vworklemmastatement} |
1642 |
|
|
\begin{vworklemmaproof} |
1643 |
|
|
See Exercise \ref{exe:crat0:sexe0:10}. |
1644 |
|
|
\end{vworklemmaproof} |
1645 |
|
|
|
1646 |
|
|
\begin{vworklemmastatement} |
1647 |
|
|
\label{lem:crat0:sfdv0:sprc1:03} |
1648 |
|
|
If $K_3=K_4$, $K_1=0$, and $\gcd(K_2, K_4)=1$\footnote{See also |
1649 |
|
|
footnote \ref{footnote:lem:crat0:sfdv0:sprc0:04:01} in this chapter.}, the error between |
1650 |
|
|
the approximation to $N_O$ implemented by Algorithm \ref{alg:crat0:sfdv0:01b} |
1651 |
|
|
and the ``ideal'' mapping is always |
1652 |
|
|
in the set |
1653 |
|
|
|
1654 |
|
|
\begin{equation} |
1655 |
|
|
\label{eq:lem:crat0:sfdv0:sprc1:03:01} |
1656 |
|
|
\left[ - \frac{K_4 - 1}{K_4} , 0 \right] , |
1657 |
|
|
\end{equation} |
1658 |
|
|
|
1659 |
|
|
and no algorithm can be constructed to |
1660 |
|
|
confine the error to a smaller interval. |
1661 |
|
|
\end{vworklemmastatement} |
1662 |
|
|
\begin{vworklemmaproof} |
1663 |
|
|
The proof is identical to the proof of Lemma \ref{lem:crat0:sfdv0:sprc0:04}. |
1664 |
|
|
\end{vworklemmaproof} |
1665 |
|
|
|
1666 |
|
|
\begin{vworklemmastatement} |
1667 |
|
|
\label{lem:crat0:sfdv0:sprc1:04} |
1668 |
|
|
For Algorithm \ref{alg:crat0:sfdv0:01b} |
1669 |
|
|
with |
1670 |
|
|
$K_2 \geq K_4$, once steady |
1671 |
|
|
state has been achieved (see Exercise |
1672 |
|
|
\ref{exe:crat0:sexe0:13}), each invocation of the |
1673 |
|
|
base subroutine will result in |
1674 |
|
|
a number of invocations of |
1675 |
|
|
``\texttt{A()}'' which is in the set |
1676 |
|
|
|
1677 |
|
|
\begin{equation} |
1678 |
|
|
\label{eq:lem:crat0:sfdv0:sprc1:04:01} |
1679 |
|
|
\left\{ |
1680 |
|
|
\left\lfloor \frac{K_2}{K_4} \right\rfloor , |
1681 |
|
|
\left\lceil \frac{K_2}{K_4} \right\rceil |
1682 |
|
|
\right\}, |
1683 |
|
|
\end{equation} |
1684 |
|
|
|
1685 |
|
|
which contains one integer if $K_4 \vworkdivides K_2$, |
1686 |
|
|
or two integers otherwise. With $K_2 < K_4$, |
1687 |
|
|
the behavior will be as specified in Lemma |
1688 |
|
|
\ref{lem:crat0:sfdv0:sprc0:03}. |
1689 |
|
|
\end{vworklemmastatement} |
1690 |
|
|
\begin{vworklemmaproof} |
1691 |
|
|
See Exercise \ref{exe:crat0:sexe0:12}. |
1692 |
|
|
\end{vworklemmaproof} |
1693 |
|
|
\begin{vworklemmaparsection}{Remark} |
1694 |
|
|
Note that Lemma \ref{lem:crat0:sfdv0:sprc0:03} |
1695 |
|
|
and this lemma specify different aspects of behavior, |
1696 |
|
|
which is why (\ref{eq:lem:crat0:sfdv0:sprc0:03:01}) |
1697 |
|
|
and (\ref{eq:lem:crat0:sfdv0:sprc0:03:02}) take |
1698 |
|
|
different forms than |
1699 |
|
|
(\ref{eq:lem:crat0:sfdv0:sprc1:04:01}). |
1700 |
|
|
Lemma \ref{lem:crat0:sfdv0:sprc0:03} specifies the number of consecutive |
1701 |
|
|
invocations of the base subroutine for which ``\texttt{A()}'' |
1702 |
|
|
will be run, but with $K_2 \geq K_4$ it does not make sense to |
1703 |
|
|
specify behavior in this way since ``\texttt{A()}'' will be run |
1704 |
|
|
on \emph{every} invocation of the base subroutine. This lemma specifies |
1705 |
|
|
the number of times ``\texttt{A()}'' will be run on a \emph{single} |
1706 |
|
|
invocation of the base subroutine (which is not meaningful if |
1707 |
|
|
$K_2 < K_4$ since the result will always be 0 or 1). |
1708 |
|
|
\end{vworklemmaparsection} |
1709 |
|
|
%\vworklemmafooter{} |
1710 |
|
|
|
1711 |
|
|
|
1712 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1713 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1714 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1715 |
|
|
\subsection[Properties Of Algorithm \ref{alg:crat0:sfdv0:01c}] |
1716 |
|
|
{Properties Of Rational Counting Algorithm \ref{alg:crat0:sfdv0:01c}} |
1717 |
|
|
%Section tag: PRX0 |
1718 |
|
|
\label{crat0:sfdv0:sprx0} |
1719 |
|
|
|
1720 |
|
|
Algorithm \ref{alg:crat0:sfdv0:01c}\footnote{Algorithm \ref{alg:crat0:sfdv0:01c} |
1721 |
|
|
was contributed in March, 2003 |
1722 |
|
|
by Chuck B. Falconer \cite{bibref:i:chuckbfalconer} |
1723 |
|
|
via the |
1724 |
|
|
\texttt{comp.arch.embedded} \cite{bibref:n:comparchembedded} |
1725 |
|
|
newsgroup.} |
1726 |
|
|
is a variant of Algorithm \ref{alg:crat0:sfdv0:01a} |
1727 |
|
|
which has one fewer |
1728 |
|
|
degrees of freedom than Algorithms \ref{alg:crat0:sfdv0:01a} |
1729 |
|
|
and \ref{alg:crat0:sfdv0:01b} and can be implemented |
1730 |
|
|
more efficiently under most instruction sets. Algorithm \ref{alg:crat0:sfdv0:01c} |
1731 |
|
|
is superior to Algorithms \ref{alg:crat0:sfdv0:01a} |
1732 |
|
|
and \ref{alg:crat0:sfdv0:01b} |
1733 |
|
|
from a computational efficiency |
1734 |
|
|
point of view, but is less intuitive. |
1735 |
|
|
|
1736 |
|
|
The superiority in computational efficiency of Algorithm \ref{alg:crat0:sfdv0:01c} |
1737 |
|
|
comes from the possibility of using an implicit test against zero |
1738 |
|
|
(rather than an explicit |
1739 |
|
|
test against $K_3$, as is found in Algorithms \ref{alg:crat0:sfdv0:01a} |
1740 |
|
|
and \ref{alg:crat0:sfdv0:01b}). |
1741 |
|
|
Many machine instruction sets automatically set flags to indicate a negative |
1742 |
|
|
result when the |
1743 |
|
|
subtraction of $K_2$ is performed, thus often allowing a conditional branch |
1744 |
|
|
without an additional instruction. Whether an instruction will be saved in |
1745 |
|
|
the code of Figure \ref{fig:crat0:sfdv0:01c} depends on the sophistication |
1746 |
|
|
of the `C' compiler, but of course if the algorithm were coded in |
1747 |
|
|
assembly-language an instruction could be saved on most processors. |
1748 |
|
|
|
1749 |
|
|
The properties of rational counting Algorithm \ref{alg:crat0:sfdv0:01c} are nearly |
1750 |
|
|
identical to those of Algorithm \ref{alg:crat0:sfdv0:01a}, |
1751 |
|
|
and we prove the important properties |
1752 |
|
|
now. |
1753 |
|
|
|
1754 |
|
|
\begin{vworklemmastatement} |
1755 |
|
|
\label{lem:crat0:sfdv0:sprx0:01} |
1756 |
|
|
$N_{STARTUP}$, the number of invocations of the base subroutine |
1757 |
|
|
in Algorithm \ref{alg:crat0:sfdv0:01c} before ``\texttt{A()}'' is called |
1758 |
|
|
for the first time, is given by |
1759 |
|
|
|
1760 |
|
|
\begin{equation} |
1761 |
|
|
\label{eq:lem:crat0:sfdv0:sprx0:01:01} |
1762 |
|
|
N_{STARTUP} = |
1763 |
|
|
\left\lfloor |
1764 |
|
|
{ |
1765 |
|
|
\frac{K_1}{K_2} |
1766 |
|
|
} |
1767 |
|
|
\right\rfloor . |
1768 |
|
|
\end{equation} |
1769 |
|
|
\end{vworklemmastatement} |
1770 |
|
|
\begin{vworklemmaproof} |
1771 |
|
|
The value of \texttt{state} when tested against |
1772 |
|
|
zero in the \texttt{if()} statement during the $n$th invocation |
1773 |
|
|
of the base subroutine is $K_1 - n K_2$. In order for the test |
1774 |
|
|
not to be met on the $n$th invocation |
1775 |
|
|
of the base subroutine, we require that |
1776 |
|
|
|
1777 |
|
|
\begin{equation} |
1778 |
|
|
\label{eq:lem:crat0:sfdv0:sprx0:01:02} |
1779 |
|
|
K_1 - n K_2 \geq 0 |
1780 |
|
|
\end{equation} |
1781 |
|
|
|
1782 |
|
|
\noindent{}or equivalently that |
1783 |
|
|
|
1784 |
|
|
\begin{equation} |
1785 |
|
|
\label{eq:lem:crat0:sfdv0:sprx0:01:03} |
1786 |
|
|
n \leq \frac{K_1}{K_2} . |
1787 |
|
|
\end{equation} |
1788 |
|
|
|
1789 |
|
|
Solving (\ref{eq:lem:crat0:sfdv0:sprx0:01:03}) for the |
1790 |
|
|
largest value of $n \in \vworkintset$ which still meets the criterion |
1791 |
|
|
yields (\ref{eq:lem:crat0:sfdv0:sprx0:01:01}). Note that |
1792 |
|
|
the derivation of (\ref{eq:lem:crat0:sfdv0:sprx0:01:01}) requires |
1793 |
|
|
that the restrictions on $K_1$, $K_2$, and $K_3$ documented in |
1794 |
|
|
Figure \ref{fig:crat0:sfdv0:01c} be met. |
1795 |
|
|
\end{vworklemmaproof} |
1796 |
|
|
|
1797 |
|
|
\begin{vworklemmastatement} |
1798 |
|
|
\label{lem:crat0:sfdv0:sprx0:02} |
1799 |
|
|
Let $N_I$ be the number of times the Algorithm \ref{alg:crat0:sfdv0:01c} |
1800 |
|
|
base subroutine |
1801 |
|
|
is called, let $N_O$ be the number of times the |
1802 |
|
|
``\texttt{A()}'' subroutine is called, let |
1803 |
|
|
$f_I$ be the frequency of invocation of the |
1804 |
|
|
Algorithm \ref{alg:crat0:sfdv0:01a} |
1805 |
|
|
base subroutine, and let |
1806 |
|
|
$f_O$ be the frequency of invocation of |
1807 |
|
|
``\texttt{A()}''. Provided the constraints |
1808 |
|
|
on $K_1$, $K_2$, and $K_3$ documented in |
1809 |
|
|
Figure \ref{fig:crat0:sfdv0:01c} are met, |
1810 |
|
|
|
1811 |
|
|
\begin{equation} |
1812 |
|
|
\label{eq:lem:crat0:sfdv0:sprx0:02:01} |
1813 |
|
|
\lim_{N_I\rightarrow\infty}\frac{N_O}{N_I} |
1814 |
|
|
= |
1815 |
|
|
\frac{f_O}{f_I} |
1816 |
|
|
= |
1817 |
|
|
\frac{K_2}{K_4} . |
1818 |
|
|
\end{equation} |
1819 |
|
|
\end{vworklemmastatement} |
1820 |
|
|
\begin{vworklemmaproof} |
1821 |
|
|
(\ref{eq:lem:crat0:sfdv0:sprx0:02:01}) indicates that once |
1822 |
|
|
an initial delay (determined by $K_1$) has finished, |
1823 |
|
|
$N_O/N_I$ will converge on a steady-state value of |
1824 |
|
|
$K_2/K_4$. |
1825 |
|
|
|
1826 |
|
|
The most straightforward way to analyze Algorithm \ref{alg:crat0:sfdv0:01c} |
1827 |
|
|
is to show how an algorithm already |
1828 |
|
|
understood (Algorithm \ref{alg:crat0:sfdv0:01a}) |
1829 |
|
|
can be transformed to |
1830 |
|
|
Algorithm \ref{alg:crat0:sfdv0:01c} |
1831 |
|
|
in a way where the analysis of Algorithm \ref{alg:crat0:sfdv0:01a} |
1832 |
|
|
also applies to Algorithm \ref{alg:crat0:sfdv0:01c}. |
1833 |
|
|
Figure \ref{fig:lem:crat0:sfdv0:sprx0:02:01} shows |
1834 |
|
|
how such a transformation can be performed in |
1835 |
|
|
four steps. |
1836 |
|
|
|
1837 |
|
|
\begin{figure} |
1838 |
|
|
(a) Algorithm \ref{alg:crat0:sfdv0:01a} unchanged. |
1839 |
|
|
$state_{a,n} \in \{0, 1, \ldots, K_4 - 1 \}$. |
1840 |
|
|
\begin{verbatim} |
1841 |
|
|
state += K2; |
1842 |
|
|
if (state >= K4) |
1843 |
|
|
{ |
1844 |
|
|
state -= K4; |
1845 |
|
|
A(); |
1846 |
|
|
} |
1847 |
|
|
\end{verbatim} |
1848 |
|
|
(b) ``\texttt{>=}'' changed to ``\texttt{>}''. $state_{b,n} \in \{1, 2, \ldots, K_4 \}$, |
1849 |
|
|
$state_{b,n} = state_{a,n} + 1$. |
1850 |
|
|
\begin{verbatim} |
1851 |
|
|
state += K2; |
1852 |
|
|
if (state > K4) |
1853 |
|
|
{ |
1854 |
|
|
state -= K4; |
1855 |
|
|
A(); |
1856 |
|
|
} |
1857 |
|
|
\end{verbatim} |
1858 |
|
|
(c) Test against $K_4$ changed to test against zero. |
1859 |
|
|
$state_{c,n} \in \{-K_4 + 1, -K_4 + 2, \ldots, 0 \}$, |
1860 |
|
|
$state_{c,n} = state_{b,n} - K_4$. |
1861 |
|
|
\begin{verbatim} |
1862 |
|
|
state += K2; |
1863 |
|
|
if (state > 0) |
1864 |
|
|
{ |
1865 |
|
|
state -= K4; |
1866 |
|
|
A(); |
1867 |
|
|
} |
1868 |
|
|
\end{verbatim} |
1869 |
|
|
(d) Sign inversion. |
1870 |
|
|
$state_{d,n} \in \{ 0, 1, \ldots, K_4 - 1 \}$, |
1871 |
|
|
$state_{d,n} = - state_{c,n}$. |
1872 |
|
|
\begin{verbatim} |
1873 |
|
|
state -= K2; |
1874 |
|
|
if (state < 0) |
1875 |
|
|
{ |
1876 |
|
|
state += K4; |
1877 |
|
|
A(); |
1878 |
|
|
} |
1879 |
|
|
\end{verbatim} |
1880 |
|
|
(e) `C' expression rearrangement. |
1881 |
|
|
$state_{e,n} \in \{ 0, 1, \ldots, K_4 - 1 \}$, |
1882 |
|
|
$state_{e,n} = state_{d,n}$. |
1883 |
|
|
\begin{verbatim} |
1884 |
|
|
if ((state -= K2) < 0) |
1885 |
|
|
{ |
1886 |
|
|
state += K4; |
1887 |
|
|
A(); |
1888 |
|
|
} |
1889 |
|
|
\end{verbatim} |
1890 |
|
|
\caption{4-Step Transformation Of Algorithm \ref{alg:crat0:sfdv0:01a} |
1891 |
|
|
To Algorithm \ref{alg:crat0:sfdv0:01c}} |
1892 |
|
|
\label{fig:lem:crat0:sfdv0:sprx0:02:01} |
1893 |
|
|
\end{figure} |
1894 |
|
|
|
1895 |
|
|
In Figure \ref{fig:lem:crat0:sfdv0:sprx0:02:01}, each of the |
1896 |
|
|
four steps required to transform from Algorithm \ref{alg:crat0:sfdv0:01a} to |
1897 |
|
|
Algorithm \ref{alg:crat0:sfdv0:01c} includes an equation to transform the |
1898 |
|
|
\texttt{state} variable. Combining all of these |
1899 |
|
|
transformations yields |
1900 |
|
|
|
1901 |
|
|
\begin{eqnarray} |
1902 |
|
|
\label{eq:lem:crat0:sfdv0:sprx0:02:02} |
1903 |
|
|
state_{e,n} & = & K_4 - 1 - state_{a,n} \\ |
1904 |
|
|
\label{eq:lem:crat0:sfdv0:sprx0:02:03} |
1905 |
|
|
state_{a,n} & = & K_4 - 1 - state_{e,n} |
1906 |
|
|
\end{eqnarray} |
1907 |
|
|
|
1908 |
|
|
We thus see that Figure \ref{fig:lem:crat0:sfdv0:sprx0:02:01}(a) |
1909 |
|
|
(corresponding to Algorithm \ref{alg:crat0:sfdv0:01a}) and |
1910 |
|
|
Figure \ref{fig:lem:crat0:sfdv0:sprx0:02:01}(e) |
1911 |
|
|
(corresponding to Algorithm \ref{alg:crat0:sfdv0:01c}) have |
1912 |
|
|
\texttt{state} semantics which involve the same range |
1913 |
|
|
but a reversed order. (\ref{eq:lem:crat0:sfdv0:sprx0:02:01}) |
1914 |
|
|
follows directly from this observation and from |
1915 |
|
|
Lemma \ref{lem:crat0:sfdv0:sprc0:02}. |
1916 |
|
|
\end{vworklemmaproof} |
1917 |
|
|
%\vworklemmafooter{} |
1918 |
|
|
|
1919 |
|
|
\begin{vworklemmastatement} |
1920 |
|
|
\label{lem:crat0:sfdv0:sprx0:03} |
1921 |
|
|
If $K_1=0$ and $\gcd(K_2, K_4)=1$\footnote{See also |
1922 |
|
|
footnote \ref{footnote:lem:crat0:sfdv0:sprc0:04:01} in this chapter.}, the error between |
1923 |
|
|
the approximation to $N_O$ implemented by Algorithm \ref{alg:crat0:sfdv0:01c} |
1924 |
|
|
and the ``ideal'' mapping is always |
1925 |
|
|
in the set |
1926 |
|
|
|
1927 |
|
|
\begin{equation} |
1928 |
|
|
\label{eq:lem:crat0:sfdv0:sprx0:03:01} |
1929 |
|
|
\left[ 0, \frac{K_4 - 1}{K_4} \right] , |
1930 |
|
|
\end{equation} |
1931 |
|
|
|
1932 |
|
|
and no algorithm can be constructed to |
1933 |
|
|
confine the error to a smaller interval. |
1934 |
|
|
\end{vworklemmastatement} |
1935 |
|
|
\begin{vworklemmaproof} |
1936 |
|
|
Using the duality illustrated by |
1937 |
|
|
(\ref{eq:lem:crat0:sfdv0:sprx0:02:02}) and |
1938 |
|
|
(\ref{eq:lem:crat0:sfdv0:sprx0:02:03}), |
1939 |
|
|
starting Algorithm \ref{alg:crat0:sfdv0:01c} with |
1940 |
|
|
$state_0=0$ will yield a dual state vector |
1941 |
|
|
with respect to starting Algorithm \ref{alg:crat0:sfdv0:01a} with |
1942 |
|
|
$state_0=K_4-1$. Thus, |
1943 |
|
|
|
1944 |
|
|
\begin{equation} |
1945 |
|
|
\label{eq:lem:crat0:sfdv0:sprx0:03:02} |
1946 |
|
|
N_O = \left\lfloor \frac{n K_2 + K_4 - 1}{K_4} \right\rfloor . |
1947 |
|
|
\end{equation} |
1948 |
|
|
|
1949 |
|
|
Using this altered value of $N_O$ in (\ref{eq:lem:crat0:sfdv0:sprc0:04:04}) |
1950 |
|
|
leads directly to (\ref{eq:lem:crat0:sfdv0:sprx0:03:01}). |
1951 |
|
|
|
1952 |
|
|
The proof that there can be no better algorithm is identical |
1953 |
|
|
to the same proof for Lemma \ref{lem:crat0:sfdv0:sprc0:04} (Exercise \ref{exe:crat0:sexe0:06}). |
1954 |
|
|
\end{vworklemmaproof} |
1955 |
|
|
%\vworklemmafooter{} |
1956 |
|
|
|
1957 |
|
|
\begin{vworklemmastatement} |
1958 |
|
|
\label{lem:crat0:sfdv0:sprx0:04} |
1959 |
|
|
For Algorithm \ref{alg:crat0:sfdv0:01c}, once steady |
1960 |
|
|
state has been achieved, the number of consecutive |
1961 |
|
|
base subroutine invocations during which subroutine |
1962 |
|
|
``\texttt{A()}'' is executed is always in the set |
1963 |
|
|
|
1964 |
|
|
\begin{equation} |
1965 |
|
|
\label{eq:lem:crat0:sfdv0:sprx0:04:01} |
1966 |
|
|
\left\{ |
1967 |
|
|
\left\lfloor \frac{K_2}{K_4 - K_2} \right\rfloor , |
1968 |
|
|
\left\lceil \frac{K_2}{K_4 - K_2} \right\rceil |
1969 |
|
|
\right\} \cap \vworkintsetpos, |
1970 |
|
|
\end{equation} |
1971 |
|
|
|
1972 |
|
|
which contains one integer if $K_2/K_4 \leq 1/2$ or $(K_4-K_2) \vworkdivides K_2$, |
1973 |
|
|
or two integers otherwise. |
1974 |
|
|
|
1975 |
|
|
Once steady state has been achieved, the number of |
1976 |
|
|
consecutive base function invocations during which |
1977 |
|
|
subroutine ``\texttt{A()}'' is not executed is |
1978 |
|
|
always in the set |
1979 |
|
|
|
1980 |
|
|
\begin{equation} |
1981 |
|
|
\label{eq:lem:crat0:sfdv0:sprx0:04:02} |
1982 |
|
|
\left\{ |
1983 |
|
|
\left\lfloor \frac{K_4-K_2}{K_2} \right\rfloor , |
1984 |
|
|
\left\lceil \frac{K_4-K_2}{K_2} \right\rceil |
1985 |
|
|
\right\} \cap \vworkintsetpos, |
1986 |
|
|
\end{equation} |
1987 |
|
|
|
1988 |
|
|
which contains one integer if $K_2/K_4 \geq 1/2$ or $K_2 \vworkdivides K_4$, |
1989 |
|
|
or two integers otherwise. |
1990 |
|
|
\end{vworklemmastatement} |
1991 |
|
|
\begin{vworklemmaproof} |
1992 |
|
|
The proof comes directly from the duality between algorithm |
1993 |
|
|
Algorithms \ref{alg:crat0:sfdv0:01a} |
1994 |
|
|
and \ref{alg:crat0:sfdv0:01c} established in the |
1995 |
|
|
proof of Lemma \ref{lem:crat0:sfdv0:sprx0:01}, so that the results |
1996 |
|
|
from Lemma \ref{lem:crat0:sfdv0:sprc0:03} apply without modification. |
1997 |
|
|
\end{vworklemmaproof} |
1998 |
|
|
\vworklemmafooter{} |
1999 |
|
|
|
2000 |
|
|
|
2001 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
2002 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
2003 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
2004 |
|
|
\subsection[Properties Of Algorithm \ref{alg:crat0:sfdv0:01d}] |
2005 |
|
|
{Properties Of Rational Counting Algorithm \ref{alg:crat0:sfdv0:01d}} |
2006 |
|
|
%Section tag: PRX1 |
2007 |
|
|
\label{crat0:sfdv0:sprx1} |
2008 |
|
|
|
2009 |
|
|
Algorithm \ref{alg:crat0:sfdv0:01d}\footnote{Algorithm \ref{alg:crat0:sfdv0:01d} |
2010 |
|
|
was contributed in March, 2003 |
2011 |
|
|
by John Larkin \cite{bibref:i:johnlarkin} |
2012 |
|
|
via the |
2013 |
|
|
\texttt{comp.arch.embedded} \cite{bibref:n:comparchembedded} |
2014 |
|
|
newsgroup.} |
2015 |
|
|
(Figure \ref{fig:crat0:sfdv0:01d}) is a further |
2016 |
|
|
economization of Algorithms \ref{alg:crat0:sfdv0:01a} |
2017 |
|
|
through \ref{alg:crat0:sfdv0:01c} that can be made by eliminating |
2018 |
|
|
the addition or subtraction of $K_4$ and test against $K_3$ |
2019 |
|
|
and instead using the |
2020 |
|
|
inherent machine integer size of $W$ bits to perform |
2021 |
|
|
arithmetic modulo $2^W$. Thus, effectively, Algorithm \ref{alg:crat0:sfdv0:01d} |
2022 |
|
|
is equivalent to Algorithm \ref{alg:crat0:sfdv0:01a} with |
2023 |
|
|
$K_4 = K_3 = 2^W$. |
2024 |
|
|
|
2025 |
|
|
Figure \ref{fig:crat0:sfdv0:01d} shows both |
2026 |
|
|
assembly-language (Texas Instruments TMS-370C8) and |
2027 |
|
|
`C' implementations of the algorithm. The assembly-language |
2028 |
|
|
version uses the carry flag of the processor and thus |
2029 |
|
|
is \emph{very} efficient. Because `C' does not have access |
2030 |
|
|
to the processor flags, the 'C' version is less efficient. |
2031 |
|
|
The ``less than'' comparison when |
2032 |
|
|
using unsigned integers is equivalent to a rollover test. |
2033 |
|
|
|
2034 |
|
|
It is easy to see from the figure that Algorithm \ref{alg:crat0:sfdv0:01d} |
2035 |
|
|
is equivalent in all |
2036 |
|
|
respects to Algorithm \ref{alg:crat0:sfdv0:01a} with |
2037 |
|
|
$K_3 = K_4$ fixed at $2^W$. It is not necessary to enforce any constraints |
2038 |
|
|
on $K_2$ because $K_2 < K_3 = K_4 = 2^W$ due to the inherent size of |
2039 |
|
|
a machine integer. Note that unlike Algorithms \ref{alg:crat0:sfdv0:01a} |
2040 |
|
|
through \ref{alg:crat0:sfdv0:01c} which allow $K_2$ and $K_4$ to be chosen independently |
2041 |
|
|
and from the Farey series of appropriate order, Algorithm \ref{alg:crat0:sfdv0:01c} |
2042 |
|
|
only allows |
2043 |
|
|
$K_2/K_4$ of the form $K_2/2^W$. |
2044 |
|
|
|
2045 |
|
|
The properties below follow immediately |
2046 |
|
|
from the properties of Algorithm \ref{alg:crat0:sfdv0:01a}. |
2047 |
|
|
|
2048 |
|
|
\begin{vworklemmastatement} |
2049 |
|
|
\label{lem:crat0:sfdv0:sprx1:01} |
2050 |
|
|
$N_{STARTUP}$, the number of invocations of the base subroutine |
2051 |
|
|
in Algorithm \ref{alg:crat0:sfdv0:01d} before ``\texttt{A()}'' is called |
2052 |
|
|
for the first time, is given by |
2053 |
|
|
|
2054 |
|
|
\begin{equation} |
2055 |
|
|
\label{eq:lem:crat0:sfdv0:sprx1:01:01} |
2056 |
|
|
N_{STARTUP} = |
2057 |
|
|
\left\lfloor |
2058 |
|
|
{ |
2059 |
|
|
\frac{2^W - K_1 - 1}{K_2} |
2060 |
|
|
} |
2061 |
|
|
\right\rfloor . |
2062 |
|
|
\end{equation} |
2063 |
|
|
\end{vworklemmastatement} |
2064 |
|
|
\begin{vworklemmaproof} |
2065 |
|
|
The value of \texttt{state} after the $n$th invocation |
2066 |
|
|
is $state_n = K_1 + n K_2$. In order for the test in the |
2067 |
|
|
\texttt{if()} statement not to be met, we require that |
2068 |
|
|
|
2069 |
|
|
\begin{equation} |
2070 |
|
|
\label{eq:lem:crat0:sfdv0:sprx1:01:02} |
2071 |
|
|
K_1 + n K_2 \leq 2^W - 1 |
2072 |
|
|
\end{equation} |
2073 |
|
|
|
2074 |
|
|
\noindent{}or equivalently that |
2075 |
|
|
|
2076 |
|
|
\begin{equation} |
2077 |
|
|
\label{eq:lem:crat0:sfdv0:sprx1:01:03} |
2078 |
|
|
n \leq \frac{2^W - K_1 - 1}{K_2} . |
2079 |
|
|
\end{equation} |
2080 |
|
|
|
2081 |
|
|
Solving (\ref{eq:lem:crat0:sfdv0:sprx1:01:03}) for the largest |
2082 |
|
|
value of $n \in \vworkintset$ which still meets the criterion |
2083 |
|
|
yields (\ref{eq:lem:crat0:sfdv0:sprx1:01:01}). |
2084 |
|
|
\end{vworklemmaproof} |
2085 |
|
|
|
2086 |
|
|
\begin{vworklemmastatement} |
2087 |
|
|
\label{lem:crat0:sfdv0:sprx1:02} |
2088 |
|
|
Let $N_I$ be the number of times the Algorithm \ref{alg:crat0:sfdv0:01d} base subroutine |
2089 |
|
|
is called, let $N_O$ be the number of times the |
2090 |
|
|
``\texttt{A()}'' subroutine is called, let |
2091 |
|
|
$f_I$ be the frequency of invocation of the |
2092 |
|
|
Algorithm \ref{alg:crat0:sfdv0:01d} base subroutine, and let |
2093 |
|
|
$f_O$ be the frequency of invocation of |
2094 |
|
|
``\texttt{A()}''. Then |
2095 |
|
|
|
2096 |
|
|
\begin{equation} |
2097 |
|
|
\label{eq:lem:crat0:sfdv0:sprx1:02:01} |
2098 |
|
|
\lim_{N_I\rightarrow\infty}\frac{N_O}{N_I} |
2099 |
|
|
= |
2100 |
|
|
\frac{f_O}{f_I} |
2101 |
|
|
= |
2102 |
|
|
\frac{K_2}{2^W} , |
2103 |
|
|
\end{equation} |
2104 |
|
|
|
2105 |
|
|
where $W$ is the number of bits in a machine unsigned integer. |
2106 |
|
|
Note that $K_2 < 2^W$ since $K_2 \in \{ 0, 1, \ldots , 2^W-1 \}$. |
2107 |
|
|
\end{vworklemmastatement} |
2108 |
|
|
\begin{vworklemmaproof} |
2109 |
|
|
The proof is identical to the proof of |
2110 |
|
|
Lemma \ref{lem:crat0:sfdv0:sprc0:02} with $K_3=K_4=2^W$. |
2111 |
|
|
Note that Algorithm \ref{alg:crat0:sfdv0:01a} calculates $n K_2 \bmod K_4$ by |
2112 |
|
|
subtraction, whereas Algorithm \ref{alg:crat0:sfdv0:01d} calculates |
2113 |
|
|
$n K_2 \bmod 2^W$ by the properties of a $W$-bit counter |
2114 |
|
|
which is allowed to roll over. |
2115 |
|
|
\end{vworklemmaproof} |
2116 |
|
|
%\vworklemmafooter{} |
2117 |
|
|
|
2118 |
|
|
|
2119 |
|
|
\begin{vworklemmastatement} |
2120 |
|
|
\label{lem:crat0:sfdv0:sprx1:03} |
2121 |
|
|
If $\gcd(K_2, 2^W)=1$\footnote{See also footnote \ref{footnote:lem:crat0:sfdv0:sprc0:04:01} |
2122 |
|
|
in this chapter. Note also that in this context the condition $\gcd(K_2, 2^W)=1$ |
2123 |
|
|
is equivalent to the condition that $K_2$ be odd.}, the error between |
2124 |
|
|
the approximation to $N_O$ implemented by Algorithm \ref{alg:crat0:sfdv0:01d} |
2125 |
|
|
and the ``ideal'' mapping is always |
2126 |
|
|
in the set |
2127 |
|
|
|
2128 |
|
|
\begin{equation} |
2129 |
|
|
\label{eq:lem:crat0:sfdv0:sprx1:03:01} |
2130 |
|
|
\left[ - \frac{2^W - 1}{2^W} , 0 \right] , |
2131 |
|
|
\end{equation} |
2132 |
|
|
|
2133 |
|
|
and no algorithm can be constructed to |
2134 |
|
|
confine the error to a smaller interval. |
2135 |
|
|
\end{vworklemmastatement} |
2136 |
|
|
\begin{vworklemmaproof} |
2137 |
|
|
The proof is identical to the proof of Lemma |
2138 |
|
|
\ref{lem:crat0:sfdv0:sprc0:04} with $K_4 = 2^W$. |
2139 |
|
|
\end{vworklemmaproof} |
2140 |
|
|
%\vworklemmafooter{} |
2141 |
|
|
|
2142 |
|
|
\begin{vworklemmastatement} |
2143 |
|
|
\label{lem:crat0:sfdv0:sprx1:04} |
2144 |
|
|
For Algorithm \ref{alg:crat0:sfdv0:01d} |
2145 |
|
|
(Figure \ref{fig:crat0:sfdv0:01d}), once steady |
2146 |
|
|
state has been achieved, the number of consecutive |
2147 |
|
|
base subroutine invocations during which subroutine |
2148 |
|
|
``\texttt{A()}'' is executed is always in the set |
2149 |
|
|
|
2150 |
|
|
\begin{equation} |
2151 |
|
|
\label{eq:lem:crat0:sfdv0:sprx1:04:01} |
2152 |
|
|
\left\{ |
2153 |
|
|
\left\lfloor \frac{K_2}{2^W - K_2} \right\rfloor , |
2154 |
|
|
\left\lceil \frac{K_2}{2^W - K_2} \right\rceil |
2155 |
|
|
\right\} \cap \vworkintsetpos, |
2156 |
|
|
\end{equation} |
2157 |
|
|
|
2158 |
|
|
which contains one integer if $K_2/2^W \leq 1/2$ or $(2^W-K_2) \vworkdivides K_2$, |
2159 |
|
|
or two integers otherwise. |
2160 |
|
|
|
2161 |
|
|
Once steady state has been achieved, the number of |
2162 |
|
|
consecutive base function invocations during which |
2163 |
|
|
subroutine ``\texttt{A()}'' is not executed is |
2164 |
|
|
always in the set |
2165 |
|
|
|
2166 |
|
|
\begin{equation} |
2167 |
|
|
\label{eq:lem:crat0:sfdv0:sprx1:04:02} |
2168 |
|
|
\left\{ |
2169 |
|
|
\left\lfloor \frac{2^W-K_2}{K_2} \right\rfloor , |
2170 |
|
|
\left\lceil \frac{2^W-K_2}{K_2} \right\rceil |
2171 |
|
|
\right\} \cap \vworkintsetpos, |
2172 |
|
|
\end{equation} |
2173 |
|
|
|
2174 |
|
|
which contains one integer if $K_2/2^W \geq 1/2$ or $K_2 \vworkdivides 2^W$, |
2175 |
|
|
or two integers otherwise. |
2176 |
|
|
\end{vworklemmastatement} |
2177 |
|
|
\begin{vworklemmaproof} |
2178 |
|
|
The proof is identical to the proof of Lemma |
2179 |
|
|
\ref{lem:crat0:sfdv0:sprc0:03} with $K_4 = 2^W$. |
2180 |
|
|
\end{vworklemmaproof} |
2181 |
|
|
\vworklemmafooter{} |
2182 |
|
|
|
2183 |
|
|
|
2184 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
2185 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
2186 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
2187 |
|
|
\subsection[Properties Of Algorithm \ref{alg:crat0:sfdv0:02a}] |
2188 |
|
|
{Properties Of Rational Counting Algorithm \ref{alg:crat0:sfdv0:02a}} |
2189 |
|
|
%Section tag: PRC2 |
2190 |
|
|
\label{crat0:sfdv0:sprc2} |
2191 |
|
|
|
2192 |
|
|
Another useful rational counting algorithm is Algorithm \ref{alg:crat0:sfdv0:02a}. |
2193 |
|
|
At first glance, it may appear that Algorithm \ref{alg:crat0:sfdv0:02a} |
2194 |
|
|
is qualitatively |
2195 |
|
|
different than Algorithms \ref{alg:crat0:sfdv0:01a} |
2196 |
|
|
and \ref{alg:crat0:sfdv0:01b}. |
2197 |
|
|
However, as the following lemmas demonstrate, Algorithm \ref{alg:crat0:sfdv0:02a} |
2198 |
|
|
can be easily rearranged to be in the form |
2199 |
|
|
of Algorithm \ref{alg:crat0:sfdv0:01a}. |
2200 |
|
|
|
2201 |
|
|
\begin{vworklemmastatement} |
2202 |
|
|
\label{lem:crat0:sfdv0:sprc2:01} |
2203 |
|
|
$N_{STARTUP}$, the number of invocations of the base subroutine |
2204 |
|
|
in Algorithm \ref{alg:crat0:sfdv0:02a} before ``\texttt{A()}'' is called |
2205 |
|
|
for the first time, is given by |
2206 |
|
|
|
2207 |
|
|
\begin{equation} |
2208 |
|
|
\label{eq:lem:crat0:sfdv0:sprc2:01:01} |
2209 |
|
|
N_{STARTUP} = |
2210 |
|
|
\left\lceil |
2211 |
|
|
{ |
2212 |
|
|
\frac{K_3 - K_1}{K_2} |
2213 |
|
|
} |
2214 |
|
|
\right\rceil . |
2215 |
|
|
\end{equation} |
2216 |
|
|
\end{vworklemmastatement} |
2217 |
|
|
\begin{vworklemmaproof} |
2218 |
|
|
The value of \texttt{state} after the $n$th invocation |
2219 |
|
|
is $K_1 + n K_2$. In order for the test in the |
2220 |
|
|
\texttt{if()} statement to be met on the $n+1$'th invocation |
2221 |
|
|
of the base subroutine, we require that |
2222 |
|
|
|
2223 |
|
|
\begin{equation} |
2224 |
|
|
\label{eq:lem:crat0:sfdv0:sprc2:01:02} |
2225 |
|
|
K_1 + n K_2 \geq K_3 |
2226 |
|
|
\end{equation} |
2227 |
|
|
|
2228 |
|
|
\noindent{}or equivalently that |
2229 |
|
|
|
2230 |
|
|
\begin{equation} |
2231 |
|
|
\label{eq:lem:crat0:sfdv0:sprc2:01:03} |
2232 |
|
|
n \geq \frac{K_3 - K_1}{K_2} . |
2233 |
|
|
\end{equation} |
2234 |
|
|
|
2235 |
|
|
Solving (\ref{eq:lem:crat0:sfdv0:sprc2:01:03}) for the smallest |
2236 |
|
|
value of $n \in \vworkintset$ which still meets the criterion |
2237 |
|
|
yields (\ref{eq:lem:crat0:sfdv0:sprc2:01:01}). Note that |
2238 |
|
|
the derivation of (\ref{eq:lem:crat0:sfdv0:sprc2:01:01}) requires |
2239 |
|
|
that the restrictions on $K_1$ through $K_4$ documented in |
2240 |
|
|
Figure \ref{fig:crat0:sfdv0:02a} be met. |
2241 |
|
|
\end{vworklemmaproof} |
2242 |
|
|
|
2243 |
|
|
\begin{vworklemmastatement} |
2244 |
|
|
\label{lem:crat0:sfdv0:sprc2:02} |
2245 |
|
|
Let $N_I$ be the number of times the Algorithm \ref{alg:crat0:sfdv0:02a} base subroutine |
2246 |
|
|
is called, let $N_{OA}$ be the number of times the |
2247 |
|
|
``\texttt{A()}'' subroutine is called, let |
2248 |
|
|
$f_I$ be the frequency of invocation of the |
2249 |
|
|
Algorithm \ref{alg:crat0:sfdv0:02a} base subroutine, and let |
2250 |
|
|
$f_{OA}$ be the frequency of invocation of |
2251 |
|
|
``\texttt{A()}''. Then, the proportion of times the |
2252 |
|
|
``\texttt{A()}'' subroutine is called is given by |
2253 |
|
|
|
2254 |
|
|
\begin{equation} |
2255 |
|
|
\label{eq:lem:crat0:sfdv0:sprc2:02:01} |
2256 |
|
|
\lim_{N_I\rightarrow\infty}\frac{N_{OA}}{N_I} |
2257 |
|
|
= |
2258 |
|
|
\frac{f_{OA}}{f_I} |
2259 |
|
|
= |
2260 |
|
|
\frac{K_2}{K_4 + K_2} , |
2261 |
|
|
\end{equation} |
2262 |
|
|
|
2263 |
|
|
and the proportion of times the ``\texttt{B()}'' subroutine is called |
2264 |
|
|
is given by |
2265 |
|
|
|
2266 |
|
|
\begin{equation} |
2267 |
|
|
\label{eq:lem:crat0:sfdv0:sprc2:02:02} |
2268 |
|
|
\lim_{N_I\rightarrow\infty}\frac{N_{OB}}{N_I} |
2269 |
|
|
= |
2270 |
|
|
\frac{f_{OB}}{f_I} |
2271 |
|
|
= |
2272 |
|
|
1 - \frac{f_{OA}}{f_I} |
2273 |
|
|
= |
2274 |
|
|
\frac{K_4}{K_4 + K_2} . |
2275 |
|
|
\end{equation} |
2276 |
|
|
\end{vworklemmastatement} |
2277 |
|
|
\begin{vworklemmaproof} |
2278 |
|
|
As in Lemma \ref{} and without |
2279 |
|
|
loss of generality, we assume for analytic |
2280 |
|
|
convenience that $K_1=0$ and $K_3=K_4$. Note that |
2281 |
|
|
$K_1$ and $K_3$ influence only the transient startup |
2282 |
|
|
behavior of the algorithm. |
2283 |
|
|
|
2284 |
|
|
It can be observed from the algorithm that once steady |
2285 |
|
|
state is achieved, \texttt{state} will be confined to the set |
2286 |
|
|
|
2287 |
|
|
\begin{equation} |
2288 |
|
|
\label{eq:lem:crat0:sfdv0:sprc2:02:10} |
2289 |
|
|
state \in \{ 0, 1, \ldots , K_4 + K_2 - 1 \} . |
2290 |
|
|
\end{equation} |
2291 |
|
|
|
2292 |
|
|
It is certainly possible to use results from |
2293 |
|
|
number theory and analyze which values in the |
2294 |
|
|
set (\ref{eq:lem:crat0:sfdv0:sprc2:02:10}) can be |
2295 |
|
|
attained and the order in which they can be attained. |
2296 |
|
|
However, an easier approach is to observe that |
2297 |
|
|
Algorithm \ref{alg:crat0:sfdv0:02a} |
2298 |
|
|
can be rearranged to take the form of |
2299 |
|
|
rational counting Algorithm \ref{alg:crat0:sfdv0:01a}. |
2300 |
|
|
This rearranged |
2301 |
|
|
algorithm is presented as |
2302 |
|
|
Figure \ref{fig:lem:crat0:sfdv0:sprc2:02:01}. Note that the |
2303 |
|
|
algorithm is rearranged only for easier analysis. |
2304 |
|
|
|
2305 |
|
|
\begin{figure} |
2306 |
|
|
\begin{verbatim} |
2307 |
|
|
void base_rate_sub(void) |
2308 |
|
|
{ |
2309 |
|
|
static unsigned int state = K1; |
2310 |
|
|
|
2311 |
|
|
state += K2; |
2312 |
|
|
|
2313 |
|
|
if (state >= (K4 + K2)) |
2314 |
|
|
{ |
2315 |
|
|
state -= (K4 + K2); |
2316 |
|
|
A(); |
2317 |
|
|
} |
2318 |
|
|
else |
2319 |
|
|
{ |
2320 |
|
|
B(); |
2321 |
|
|
} |
2322 |
|
|
} |
2323 |
|
|
\end{verbatim} |
2324 |
|
|
\caption{Algorithm \ref{alg:crat0:sfdv0:02a} Modified To Resemble Algorithm \ref{alg:crat0:sfdv0:01a} |
2325 |
|
|
(Proof Of Lemma \ref{lem:crat0:sfdv0:sprc2:02})} |
2326 |
|
|
\label{fig:lem:crat0:sfdv0:sprc2:02:01} |
2327 |
|
|
\end{figure} |
2328 |
|
|
|
2329 |
|
|
In Figure \ref{fig:lem:crat0:sfdv0:sprc2:02:01}, the |
2330 |
|
|
statement ``\texttt{state += K2}'' has been removed from the |
2331 |
|
|
\texttt{else} clause and placed above the \texttt{if()} statement, |
2332 |
|
|
and other constants have been adjusted accordingly. |
2333 |
|
|
It can be observed that the figure |
2334 |
|
|
is structurally identical to rational counting algorithm, except for the |
2335 |
|
|
\texttt{else} clause (which does not affect the counting behavior) and |
2336 |
|
|
the specific constants for testing and incrementation. |
2337 |
|
|
|
2338 |
|
|
In Figure \ref{fig:lem:crat0:sfdv0:sprc2:02:01}, as contrasted with |
2339 |
|
|
Algorithm \ref{alg:crat0:sfdv0:01a}, ``$K_4 + K_2$'' takes the |
2340 |
|
|
place of $K_4$. $\gcd(K_2, K_4 + K_2) = \gcd(K_2, K_4)$ |
2341 |
|
|
(see Lemma \cprizeroxrefhyphen\ref{lem:cpri0:gcd0:01}), so the |
2342 |
|
|
results from |
2343 |
|
|
\end{vworklemmaproof} |
2344 |
|
|
|
2345 |
|
|
\begin{vworklemmastatement} |
2346 |
|
|
\label{lem:crat0:sfdv0:sprc2:03} |
2347 |
|
|
If $K_3=K_4$, $K_1=0$, and $\gcd(K_2, K_4)=1$, the error between |
2348 |
|
|
the approximation to $N_O$ implemented by Algorithm \ref{alg:crat0:sfdv0:01b} |
2349 |
|
|
and the ``ideal'' mapping is always |
2350 |
|
|
in the set |
2351 |
|
|
|
2352 |
|
|
\begin{equation} |
2353 |
|
|
\label{eq:lem:crat0:sfdv0:sprc2:03:01} |
2354 |
|
|
\left[ - \frac{K_4 - 1}{K_4} , 0 \right] , |
2355 |
|
|
\end{equation} |
2356 |
|
|
|
2357 |
|
|
and no algorithm can be constructed to |
2358 |
|
|
confine the error to a smaller interval. |
2359 |
|
|
\end{vworklemmastatement} |
2360 |
|
|
\begin{vworklemmaproof} |
2361 |
|
|
The proof is identical to Lemma \ref{lem:crat0:sfdv0:sprc0:04}. |
2362 |
|
|
\end{vworklemmaproof} |
2363 |
|
|
|
2364 |
|
|
|
2365 |
|
|
|
2366 |
|
|
|
2367 |
|
|
|
2368 |
|
|
|
2369 |
|
|
|
2370 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
2371 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
2372 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
2373 |
|
|
\section{Bresenham's Line Algorithm} |
2374 |
|
|
%Section tag: BLA0 |
2375 |
|
|
\label{crat0:sbla0} |
2376 |
|
|
|
2377 |
|
|
\index{Bresenham's line algorithm}\emph{Bresenham's line algorithm} is a |
2378 |
|
|
very efficient algorithm for drawing lines on devices that have |
2379 |
|
|
a rectangular array of pixels which can be individually illuminated. |
2380 |
|
|
Bresenham's line algorithm is efficient for small microcontrollers |
2381 |
|
|
because it relies only |
2382 |
|
|
on integer addition, subtraction, shifting, and comparison. |
2383 |
|
|
|
2384 |
|
|
Bresenham's line algorithm is presented for two reasons: |
2385 |
|
|
|
2386 |
|
|
\begin{itemize} |
2387 |
|
|
\item The algorithm is useful for drawing lines on LCD |
2388 |
|
|
displays and other devices typically controlled by |
2389 |
|
|
microcontrollers. |
2390 |
|
|
\item The algorithm is an [extremely optimized] application |
2391 |
|
|
of the rational |
2392 |
|
|
counting algorithms presented in this chapter. |
2393 |
|
|
\end{itemize} |
2394 |
|
|
|
2395 |
|
|
\begin{figure} |
2396 |
|
|
\begin{center} |
2397 |
|
|
\begin{huge} |
2398 |
|
|
Figure Space Reserved |
2399 |
|
|
\end{huge} |
2400 |
|
|
\end{center} |
2401 |
|
|
\caption{Raster Grid For Development Of Bresenham's Line Algorithm} |
2402 |
|
|
\label{fig:crat0:sbla0:01} |
2403 |
|
|
\end{figure} |
2404 |
|
|
|
2405 |
|
|
Assume that we wish to draw a line from $(0,0)$ to $(x_f, y_f)$ on |
2406 |
|
|
a raster device (Figure \ref{fig:crat0:sbla0:01}). For simplicity of |
2407 |
|
|
development, assume that $y_f \leq x_f$ (i.e. that the slope $m \leq 1$). |
2408 |
|
|
|
2409 |
|
|
For each value of $x \in \vworkintset$, the ideal value of $y$ is given |
2410 |
|
|
by |
2411 |
|
|
|
2412 |
|
|
\begin{equation} |
2413 |
|
|
\label{eq:crat0:sbla0:01} |
2414 |
|
|
y = mx = \frac{y_f}{x_f} x = \frac{y_f x}{x_f} . |
2415 |
|
|
\end{equation} |
2416 |
|
|
|
2417 |
|
|
\noindent{}However, on a raster device, we must usually |
2418 |
|
|
choose an inexact pixel to illuminate, since it is typically |
2419 |
|
|
rare that $x_f \vworkdivides y_f x$. If |
2420 |
|
|
$x_f \vworkdivides y_f x$, then the ideal value of $y$ is |
2421 |
|
|
an integer, and we choose to illuminate |
2422 |
|
|
$(x, (y_f x)/x_f)$. However, if $x_f \vworknotdivides y_f x$, |
2423 |
|
|
then we must choose either a pixel with the same y-coordinate |
2424 |
|
|
as the previous pixel (we call this choice `D') or the pixel |
2425 |
|
|
with a y-coordinate one greater than the previous pixel (we |
2426 |
|
|
call this choice `U'). |
2427 |
|
|
The fractional part of the quotient |
2428 |
|
|
$(y_f x) / x_f$ indicates whether D or U is closer to the ideal line. |
2429 |
|
|
If $y_f x \bmod x_f \geq x_f/2$, we choose U, otherwise we choose D |
2430 |
|
|
(note that the decision to choose U in the equality case is arbitrary). |
2431 |
|
|
|
2432 |
|
|
Using the rational approximation techniques presented in |
2433 |
|
|
Section \ref{crat0:sfdv0}, it is straightforward to |
2434 |
|
|
develop an algorithm, which is presented as the code |
2435 |
|
|
in Figure \ref{fig:crat0:sbla0:02}. |
2436 |
|
|
Note that this code will only work if $m = y_f/x_f \leq 1$. |
2437 |
|
|
|
2438 |
|
|
\begin{figure} |
2439 |
|
|
\begin{verbatim} |
2440 |
|
|
/* Draws a line from (0,0) to (x_f,y_f) on a raster */ |
2441 |
|
|
/* device. */ |
2442 |
|
|
|
2443 |
|
|
void bresenham_line(int x_f, int y_f) |
2444 |
|
|
{ |
2445 |
|
|
int d=0; /* The modulo counter. */ |
2446 |
|
|
int x=0, y=0; |
2447 |
|
|
/* x- and y-coordinates currently being */ |
2448 |
|
|
/* evaluated. */ |
2449 |
|
|
int d_old; /* Remembers previous value of d. */ |
2450 |
|
|
|
2451 |
|
|
plotpoint(0,0); /* Plot initial point. */ |
2452 |
|
|
while (x <= x_f) |
2453 |
|
|
{ |
2454 |
|
|
d_old = d; |
2455 |
|
|
d += y_f; |
2456 |
|
|
if (d >= x_f) |
2457 |
|
|
d -= x_f; |
2458 |
|
|
x++; |
2459 |
|
|
if ( |
2460 |
|
|
( |
2461 |
|
|
(d == 0) && (d_old < x_f/2) |
2462 |
|
|
) |
2463 |
|
|
|| |
2464 |
|
|
( |
2465 |
|
|
(d >= x_f/2) |
2466 |
|
|
&& |
2467 |
|
|
((d_old < x_f/2) || (d_old >= d)) |
2468 |
|
|
) |
2469 |
|
|
) |
2470 |
|
|
y++; |
2471 |
|
|
plotpoint(x,y); |
2472 |
|
|
} |
2473 |
|
|
} |
2474 |
|
|
\end{verbatim} |
2475 |
|
|
\caption{First Attempt At A Raster Device Line Algorithm |
2476 |
|
|
Using Rational Counting Techniques} |
2477 |
|
|
\label{fig:crat0:sbla0:02} |
2478 |
|
|
\end{figure} |
2479 |
|
|
|
2480 |
|
|
There are a few efficiency refinements that can be made to |
2481 |
|
|
the code in Figure \ref{fig:crat0:sbla0:02}, but overall |
2482 |
|
|
it is a very efficient algorithm. Note that |
2483 |
|
|
nearly all compilers will handle the integer |
2484 |
|
|
division by two using a shift |
2485 |
|
|
operation rather than a division. |
2486 |
|
|
|
2487 |
|
|
We can however substantially simplify and economize the code of |
2488 |
|
|
Figure \ref{fig:crat0:sbla0:02} by using the technique |
2489 |
|
|
presented in Figures \ref{fig:crat0:sfdv0:fab0:03} and |
2490 |
|
|
\ref{fig:crat0:sfdv0:fab0:04}, and this improved code is |
2491 |
|
|
presented as Figure \ref{fig:crat0:sbla0:03}. |
2492 |
|
|
|
2493 |
|
|
\begin{figure} |
2494 |
|
|
\begin{verbatim} |
2495 |
|
|
/* Draws a line from (0,0) to (x_f,y_f) on a raster */ |
2496 |
|
|
/* device. */ |
2497 |
|
|
|
2498 |
|
|
void bresenham_line(int x_f, int y_f) |
2499 |
|
|
{ |
2500 |
|
|
int d=y_f; /* Position of the ideal line minus */ |
2501 |
|
|
/* the position of the line we are */ |
2502 |
|
|
/* drawing, in units of 1/x_f. The */ |
2503 |
|
|
/* initialization value is y_f because */ |
2504 |
|
|
/* the algorithm is looking one pixel */ |
2505 |
|
|
/* ahead in the x direction, so we */ |
2506 |
|
|
/* begin at x=1. */ |
2507 |
|
|
int x=0, y=0; |
2508 |
|
|
/* x- and y-coordinates currently being */ |
2509 |
|
|
/* evaluated. */ |
2510 |
|
|
plotpoint(0,0); /* Plot initial point. */ |
2511 |
|
|
while (x <= x_f) |
2512 |
|
|
{ |
2513 |
|
|
x++; /* We move to the right regardless. */ |
2514 |
|
|
if (d >= x_f/2) |
2515 |
|
|
{ |
2516 |
|
|
/* The "U" choice. We must jump up a pixel */ |
2517 |
|
|
/* to keep up with the ideal line. */ |
2518 |
|
|
d += (y_f - x_f); |
2519 |
|
|
y++; /* Jump up a pixel. */ |
2520 |
|
|
} |
2521 |
|
|
else /* d < x_f/2 */ |
2522 |
|
|
{ |
2523 |
|
|
/* The "D" choice. Distance is not large */ |
2524 |
|
|
/* enough to jump up a pixel. */ |
2525 |
|
|
d += y_f; |
2526 |
|
|
} |
2527 |
|
|
plotpoint(x,y); |
2528 |
|
|
} |
2529 |
|
|
} |
2530 |
|
|
\end{verbatim} |
2531 |
|
|
\caption{Second Attempt At A Raster Device Line Algorithm |
2532 |
|
|
Using Rational Counting Techniques} |
2533 |
|
|
\label{fig:crat0:sbla0:03} |
2534 |
|
|
\end{figure} |
2535 |
|
|
|
2536 |
|
|
In order to understand the code of Figure \ref{fig:crat0:sbla0:03}, |
2537 |
|
|
it is helpful to view the problem in an alternate way. |
2538 |
|
|
For any $x \in \vworkintset$, let |
2539 |
|
|
$d$ be the distance between the position of the ideal line |
2540 |
|
|
(characterized by $y = y_f x / x_f$) and |
2541 |
|
|
the actual pixel which will be illuminated. It is easy to |
2542 |
|
|
observe that: |
2543 |
|
|
|
2544 |
|
|
\begin{itemize} |
2545 |
|
|
\item When drawing a raster line, if one proceeds from |
2546 |
|
|
$(x, y)$ to $(x+1, y)$ (i.e. makes the ``D'' choice), |
2547 |
|
|
$d$ will increase by $y_f/x_f$. |
2548 |
|
|
\item When drawing a raster line, if one proceeds from |
2549 |
|
|
$(x,y)$ to $(x+1, y+1)$ (i.e. makes the ``U'' choice), |
2550 |
|
|
$d$ will increase by $(y_f - x_f)/x_f$. (The increase |
2551 |
|
|
of $y_f/x_f$ comes about because the ideal line proceeds |
2552 |
|
|
upward from $x$ to $x+1$, while the decrease of $x_f/x_f = 1$ |
2553 |
|
|
comes about because the line being drawn jumps upward by one |
2554 |
|
|
unit, thus tending to ``catch'' the ideal line.) |
2555 |
|
|
\end{itemize} |
2556 |
|
|
|
2557 |
|
|
The code of Figure \ref{fig:crat0:sbla0:03} implements the |
2558 |
|
|
two observations above in a straightforward way. $d$ is maintained |
2559 |
|
|
in units of $1/x_f$, and when ``U'' is chosen over ``D'' whenever |
2560 |
|
|
the gap between the ideal line and the current row of pixels |
2561 |
|
|
being drawn becomes too large. |
2562 |
|
|
|
2563 |
|
|
The code in Figure \ref{fig:crat0:sbla0:03} does however contain logical |
2564 |
|
|
and performance problems which should be corrected: |
2565 |
|
|
|
2566 |
|
|
\begin{itemize} |
2567 |
|
|
\item The test of $d$ against $x_f/2$ will perform as intended. |
2568 |
|
|
For example, if $d=2$ and $x_f=5$, the test |
2569 |
|
|
``\texttt{d >= x\_f/2}'' in the code will evaluate true |
2570 |
|
|
although the actual condition is false. To correct this |
2571 |
|
|
defect, the units of $d$ should be changed from |
2572 |
|
|
$1/x_f$ to $1/(2 x_f)$. |
2573 |
|
|
\item The quantity $y_f - x_f$ is calculated repeatedly. This |
2574 |
|
|
calculation should be moved out of the \emph{while()} loop. |
2575 |
|
|
\item The test against $x_f$ may be more economical if changed to |
2576 |
|
|
a test against 0 (but this requires a different initialization |
2577 |
|
|
assignment for $d$). |
2578 |
|
|
\end{itemize} |
2579 |
|
|
|
2580 |
|
|
Figure \ref{fig:crat0:sbla0:04} corrects these defects |
2581 |
|
|
from Figure \ref{fig:crat0:sbla0:03}. |
2582 |
|
|
Figure \ref{fig:crat0:sbla0:04} is essentially the Bresenham |
2583 |
|
|
line algorithm, except that it only draws starting from the |
2584 |
|
|
origin and will only draw a line with a slope |
2585 |
|
|
$m = y_f/x_f \leq 1$. |
2586 |
|
|
|
2587 |
|
|
\begin{figure} |
2588 |
|
|
\begin{verbatim} |
2589 |
|
|
/* Draws a line from (0,0) to (x_f,y_f) on a raster */ |
2590 |
|
|
/* device. */ |
2591 |
|
|
|
2592 |
|
|
void bresenham_line(int x_f, int y_f) |
2593 |
|
|
{ |
2594 |
|
|
int d = 2 * y_f - x_f; |
2595 |
|
|
/* Position of the ideal line minus */ |
2596 |
|
|
/* the position of the line we are */ |
2597 |
|
|
/* drawing, in units of 1/(2 * x_f). */ |
2598 |
|
|
/* Initialization value of 2 * y_f is */ |
2599 |
|
|
/* because algorithm is looking one */ |
2600 |
|
|
/* pixel ahead. Value of -x_f is from */ |
2601 |
|
|
/* shifting the midpoint test (the */ |
2602 |
|
|
/* "if" statement below) downward to a */ |
2603 |
|
|
/* test against zero. */ |
2604 |
|
|
int dD = 2 * y_f; |
2605 |
|
|
int dU = dD - x_f; |
2606 |
|
|
/* Amounts to add to d if "D" and "U" */ |
2607 |
|
|
/* pixels are chosen, respectively. */ |
2608 |
|
|
/* Calculated here outside of loop. */ |
2609 |
|
|
int x=0, y=0; |
2610 |
|
|
/* x- and y-coordinates currently being */ |
2611 |
|
|
/* evaluated. */ |
2612 |
|
|
plotpoint(0,0); /* Plot initial point. */ |
2613 |
|
|
while (x <= x_f) |
2614 |
|
|
{ |
2615 |
|
|
x++; /* We move to the right regardless. */ |
2616 |
|
|
if (d >= 0) |
2617 |
|
|
{ |
2618 |
|
|
/* The "U" choice. We must jump up a pixel */ |
2619 |
|
|
/* to keep up with the ideal line. */ |
2620 |
|
|
d += dU; |
2621 |
|
|
y++; /* Jump up a pixel. */ |
2622 |
|
|
} |
2623 |
|
|
else /* d < 0 */ |
2624 |
|
|
{ |
2625 |
|
|
/* The "D" choice. Distance is not large */ |
2626 |
|
|
/* enough to jump up a pixel. */ |
2627 |
|
|
d += dD; |
2628 |
|
|
} |
2629 |
|
|
plotpoint(x,y); |
2630 |
|
|
} |
2631 |
|
|
} |
2632 |
|
|
\end{verbatim} |
2633 |
|
|
\caption{Third Attempt At A Raster Device Line Algorithm |
2634 |
|
|
Using Rational Counting Techniques} |
2635 |
|
|
\label{fig:crat0:sbla0:04} |
2636 |
|
|
\end{figure} |
2637 |
|
|
|
2638 |
|
|
|
2639 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
2640 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
2641 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
2642 |
|
|
\section{Authors And Acknowledgements} |
2643 |
|
|
%Section tag: ACK0 |
2644 |
|
|
This chapter was primarily written by |
2645 |
|
|
\index{Ashley, David T.} David T. Ashley |
2646 |
|
|
\cite{bibref:i:daveashley}. |
2647 |
|
|
|
2648 |
|
|
We would like to gratefully acknowledge the assistance of |
2649 |
|
|
\index{Falconer, Chuck B.} Chuck B. Falconer \cite{bibref:i:chuckbfalconer}, |
2650 |
|
|
\index{Hoffmann, Klaus} Klaus Hoffmann \cite{bibref:i:klaushoffmann}, |
2651 |
|
|
\index{Larkin, John} John Larkin \cite{bibref:i:johnlarkin}, |
2652 |
|
|
\index{Smith, Thad} Thad Smith \cite{bibref:i:thadsmith}, |
2653 |
|
|
and |
2654 |
|
|
\index{Voipio, Tauno} Tauno Voipio \cite{bibref:i:taunovoipio} |
2655 |
|
|
for insight into rational counting approaches, contributed via the |
2656 |
|
|
\texttt{sci.math} \cite{bibref:n:scimathnewsgroup} |
2657 |
|
|
and |
2658 |
|
|
\texttt{comp.arch.embedded} \cite{bibref:n:comparchembedded} |
2659 |
|
|
newsgroups. |
2660 |
|
|
|
2661 |
|
|
|
2662 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
2663 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
2664 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
2665 |
|
|
\section{Exercises} |
2666 |
|
|
%Section tag: EXE0 |
2667 |
|
|
|
2668 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
2669 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
2670 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
2671 |
|
|
\subsection[\protect\mbox{\protect$h/2^q$} and \protect\mbox{\protect$2^q/k$} Rational Linear Approximation] |
2672 |
|
|
{\protect\mbox{\protect\boldmath$h/2^q$} and \protect\mbox{\protect\boldmath$2^q/k$} Rational Linear Approximation} |
2673 |
|
|
|
2674 |
|
|
\begin{vworkexercisestatement} |
2675 |
|
|
\label{exe:crat0:sexe0:a01} |
2676 |
|
|
Derive equations analogous to (\ref{eq:crat0:shqq0:dph0:03}) |
2677 |
|
|
and (\ref{eq:crat0:shqq0:dph0:07}) if $r_A$ is chosen |
2678 |
|
|
without rounding, i.e. |
2679 |
|
|
$h=\lfloor r_I 2^q \rfloor$ and therefore |
2680 |
|
|
$r_A=\lfloor r_I 2^q \rfloor/2^q$. |
2681 |
|
|
\end{vworkexercisestatement} |
2682 |
|
|
\vworkexercisefooter{} |
2683 |
|
|
|
2684 |
|
|
\begin{vworkexercisestatement} |
2685 |
|
|
\label{exe:crat0:sexe0:a02} |
2686 |
|
|
Derive equations analogous to (\ref{eq:crat0:shqq0:dph0:03}) |
2687 |
|
|
and (\ref{eq:crat0:shqq0:dph0:07}) if |
2688 |
|
|
$z$ is chosen for rounding with the midpoint case rounded |
2689 |
|
|
down, i.e. $z=2^{q-1}-1$, and applied as in |
2690 |
|
|
(\ref{eq:crat0:sint0:01}). |
2691 |
|
|
\end{vworkexercisestatement} |
2692 |
|
|
\vworkexercisefooter{} |
2693 |
|
|
|
2694 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
2695 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
2696 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
2697 |
|
|
\subsection{Rational Counting} |
2698 |
|
|
|
2699 |
|
|
|
2700 |
|
|
\begin{vworkexercisestatement} |
2701 |
|
|
\label{exe:crat0:sexe0:01} |
2702 |
|
|
For Algorithm \ref{alg:crat0:sfdv0:01a}, |
2703 |
|
|
assume that one chooses $K_1 > K_3 - K_2$ (in contradiction to the |
2704 |
|
|
restrictions in Figure \ref{fig:crat0:sfdv0:01a}). |
2705 |
|
|
Derive a result similar to Lemma \ref{lem:crat0:sfdv0:sprc0:01} |
2706 |
|
|
for the number of base subroutine invocations in which |
2707 |
|
|
``\texttt{A()}'' is run before it is |
2708 |
|
|
\emph{not} run for the first time. |
2709 |
|
|
\end{vworkexercisestatement} |
2710 |
|
|
\vworkexercisefooter{} |
2711 |
|
|
|
2712 |
|
|
\begin{vworkexercisestatement} |
2713 |
|
|
\label{exe:crat0:sexe0:02} |
2714 |
|
|
This will be the $\epsilon$ lemma proof. |
2715 |
|
|
\end{vworkexercisestatement} |
2716 |
|
|
\vworkexercisefooter{} |
2717 |
|
|
|
2718 |
|
|
\begin{vworkexercisestatement} |
2719 |
|
|
\label{exe:crat0:sexe0:03} |
2720 |
|
|
Rederive appropriate results similar to |
2721 |
|
|
Lemma \ref{lem:crat0:sfdv0:sprc0:04} in the case where |
2722 |
|
|
$\gcd(K_2, K_4) > 1$. |
2723 |
|
|
\end{vworkexercisestatement} |
2724 |
|
|
\vworkexercisefooter{} |
2725 |
|
|
|
2726 |
|
|
\begin{vworkexercisestatement} |
2727 |
|
|
\label{exe:crat0:sexe0:04} |
2728 |
|
|
Rederive appropriate results similar to |
2729 |
|
|
Lemma \ref{lem:crat0:sfdv0:sprc0:04} in the case where |
2730 |
|
|
$K_1 \neq 0$. |
2731 |
|
|
\end{vworkexercisestatement} |
2732 |
|
|
\vworkexercisefooter{} |
2733 |
|
|
|
2734 |
|
|
\begin{vworkexercisestatement} |
2735 |
|
|
\label{exe:crat0:sexe0:05} |
2736 |
|
|
Rederive appropriate results similar to |
2737 |
|
|
Lemma \ref{lem:crat0:sfdv0:sprc0:04} in the case where |
2738 |
|
|
$\gcd(K_2, K_4) > 1$ and $K_1 \neq 0$. |
2739 |
|
|
\end{vworkexercisestatement} |
2740 |
|
|
\vworkexercisefooter{} |
2741 |
|
|
|
2742 |
|
|
\begin{vworkexercisestatement} |
2743 |
|
|
\label{exe:crat0:sexe0:06} |
2744 |
|
|
For Lemma \ref{lem:crat0:sfdv0:sprc0:04}, |
2745 |
|
|
complete the missing proof: |
2746 |
|
|
show that if $\gcd(K_2, K_4) = 1$, no algorithm can |
2747 |
|
|
lead to a tighter bound than (\ref{eq:lem:crat0:sfdv0:sprc0:04:01}). |
2748 |
|
|
\textbf{Hint:} start with the observation |
2749 |
|
|
that with |
2750 |
|
|
$\gcd(K_2, K_4) = 1$, $n K_2 \bmod K_4$ will attain every value in |
2751 |
|
|
the set $\{ 0, \ldots , K_4-1 \}$. |
2752 |
|
|
\end{vworkexercisestatement} |
2753 |
|
|
\vworkexercisefooter{} |
2754 |
|
|
|
2755 |
|
|
\begin{vworkexercisestatement} |
2756 |
|
|
\label{exe:crat0:sexe0:07} |
2757 |
|
|
For Lemma \ref{lem:crat0:sfdv0:sprc0:03}, |
2758 |
|
|
show that if $K_1=0$, the number of initial invocations |
2759 |
|
|
of the base subroutine before ``\texttt{A()}'' is first |
2760 |
|
|
called is in the set specified in |
2761 |
|
|
(\ref{eq:lem:crat0:sfdv0:sprc0:03:01}). |
2762 |
|
|
\end{vworkexercisestatement} |
2763 |
|
|
\vworkexercisefooter{} |
2764 |
|
|
|
2765 |
|
|
\begin{vworkexercisestatement} |
2766 |
|
|
\label{exe:crat0:sexe0:08} |
2767 |
|
|
Develop other techniques to correct the state upset vulnerability |
2768 |
|
|
of Algorithm \ref{alg:crat0:sfdv0:01a} besides |
2769 |
|
|
the technique illustrated in |
2770 |
|
|
Figure \ref{fig:crat0:sfdv0:sprc0:01}. |
2771 |
|
|
\end{vworkexercisestatement} |
2772 |
|
|
\vworkexercisefooter{} |
2773 |
|
|
|
2774 |
|
|
\begin{vworkexercisestatement} |
2775 |
|
|
\label{exe:crat0:sexe0:09} |
2776 |
|
|
Show for Example \ref{ex:crat0:sfdv0:sprc1:01} that integers of at least |
2777 |
|
|
27 bits are required. |
2778 |
|
|
\end{vworkexercisestatement} |
2779 |
|
|
\vworkexercisefooter{} |
2780 |
|
|
|
2781 |
|
|
\begin{vworkexercisestatement} |
2782 |
|
|
\label{exe:crat0:sexe0:10} |
2783 |
|
|
Prove Lemma \ref{lem:crat0:sfdv0:sprc1:02}. |
2784 |
|
|
\end{vworkexercisestatement} |
2785 |
|
|
\vworkexercisefooter{} |
2786 |
|
|
|
2787 |
|
|
\begin{vworkexercisestatement} |
2788 |
|
|
\label{exe:crat0:sexe0:12} |
2789 |
|
|
Prove Lemma \ref{lem:crat0:sfdv0:sprc1:04}. |
2790 |
|
|
\end{vworkexercisestatement} |
2791 |
|
|
\vworkexercisefooter{} |
2792 |
|
|
|
2793 |
|
|
\begin{vworkexercisestatement} |
2794 |
|
|
\label{exe:crat0:sexe0:13} |
2795 |
|
|
Define the term \emph{steady state} as used in |
2796 |
|
|
Lemma \ref{lem:crat0:sfdv0:sprc1:04} in terms of |
2797 |
|
|
set membership of the \texttt{state} variable. |
2798 |
|
|
\end{vworkexercisestatement} |
2799 |
|
|
\vworkexercisefooter{} |
2800 |
|
|
|
2801 |
|
|
\begin{vworkexercisestatement} |
2802 |
|
|
\label{exe:crat0:sexe0:14} |
2803 |
|
|
For Algorithm \ref{alg:crat0:sfdv0:01a}, devise examples of anomalous behavior due to |
2804 |
|
|
race conditions that may occur if $K_2$ and/or $K_4$ are set in a process |
2805 |
|
|
which is asynchronous with respect to the process which implements the |
2806 |
|
|
rational counting algorithm if mutual exclusion protocol is not |
2807 |
|
|
implemented. |
2808 |
|
|
\end{vworkexercisestatement} |
2809 |
|
|
\vworkexercisefooter{} |
2810 |
|
|
|
2811 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
2812 |
|
|
\vfill |
2813 |
|
|
\noindent\begin{figure}[!b] |
2814 |
|
|
\noindent\rule[-0.25in]{\textwidth}{1pt} |
2815 |
|
|
\begin{tiny} |
2816 |
|
|
\begin{verbatim} |
2817 |
|
|
$RCSfile: c_rat0.tex,v $ |
2818 |
|
|
$Source: /home/dashley/cvsrep/e3ft_gpl01/e3ft_gpl01/dtaipubs/esrgubka/c_rat0/c_rat0.tex,v $ |
2819 |
|
|
$Revision: 1.28 $ |
2820 |
|
|
$Author: dtashley $ |
2821 |
|
|
$Date: 2004/02/22 19:27:48 $ |
2822 |
|
|
\end{verbatim} |
2823 |
|
|
\end{tiny} |
2824 |
|
|
\noindent\rule[0.25in]{\textwidth}{1pt} |
2825 |
|
|
\end{figure} |
2826 |
|
|
|
2827 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
2828 |
|
|
% $Log: c_rat0.tex,v $ |
2829 |
|
|
% Revision 1.28 2004/02/22 19:27:48 dtashley |
2830 |
|
|
% Edits. |
2831 |
|
|
% |
2832 |
|
|
% Revision 1.27 2004/02/22 15:01:53 dtashley |
2833 |
|
|
% Edits. |
2834 |
|
|
% |
2835 |
|
|
% Revision 1.26 2003/12/06 17:48:49 dtashley |
2836 |
|
|
% Final edits before move back to SourceForge. |
2837 |
|
|
% |
2838 |
|
|
% Revision 1.25 2003/04/08 01:21:16 dtashley |
2839 |
|
|
% Checkin after major ripup to mechanism for documenting algorithms. |
2840 |
|
|
% |
2841 |
|
|
% Revision 1.24 2003/04/07 09:38:23 dtashley |
2842 |
|
|
% Safety checkin before major tearup with algorithms. |
2843 |
|
|
% |
2844 |
|
|
% Revision 1.23 2003/04/04 04:05:40 dtashley |
2845 |
|
|
% Safety checkin before another major edit. |
2846 |
|
|
% |
2847 |
|
|
% Revision 1.22 2003/04/03 19:49:36 dtashley |
2848 |
|
|
% Global corrections to typeface of "gcd" made as per Jan-Hinnerk Reichert's |
2849 |
|
|
% recommendation. |
2850 |
|
|
% |
2851 |
|
|
% Revision 1.21 2003/04/03 19:33:13 dtashley |
2852 |
|
|
% Substantial edits. Safety checkin. Preparing to make corrections to |
2853 |
|
|
% gcd typeface pointed out my Jan-Hinnerk Reichert. |
2854 |
|
|
% |
2855 |
|
|
% Revision 1.20 2003/04/02 08:21:16 dtashley |
2856 |
|
|
% Substantial edits, safety checkin. |
2857 |
|
|
% |
2858 |
|
|
% Revision 1.19 2003/03/30 05:37:20 dtashley |
2859 |
|
|
% Evening safety checkin. Substantial edits. |
2860 |
|
|
% |
2861 |
|
|
% Revision 1.18 2003/03/28 07:24:16 dtashley |
2862 |
|
|
% Safety checkin, substantial edits. |
2863 |
|
|
% |
2864 |
|
|
% Revision 1.17 2003/03/25 05:31:40 dtashley |
2865 |
|
|
% Substantial edits, safety checkin. |
2866 |
|
|
% |
2867 |
|
|
% Revision 1.16 2003/03/21 06:34:54 dtashley |
2868 |
|
|
% Major revisions. Safety checkin. |
2869 |
|
|
% |
2870 |
|
|
% Revision 1.15 2003/03/18 06:20:48 dtashley |
2871 |
|
|
% Substantial edits, safety checkin. |
2872 |
|
|
% |
2873 |
|
|
% Revision 1.14 2003/03/13 06:28:36 dtashley |
2874 |
|
|
% Substantial progress, edits. |
2875 |
|
|
% |
2876 |
|
|
% Revision 1.13 2003/03/08 04:11:19 dtashley |
2877 |
|
|
% Friday evening safety checkin. |
2878 |
|
|
% |
2879 |
|
|
% Revision 1.12 2003/03/05 02:37:34 dtashley |
2880 |
|
|
% Safety checkin before major edits. |
2881 |
|
|
% |
2882 |
|
|
% Revision 1.11 2003/03/03 23:50:44 dtashley |
2883 |
|
|
% Substantial edits. Safety checkin. |
2884 |
|
|
% |
2885 |
|
|
% Revision 1.10 2002/04/27 00:21:04 dtashley |
2886 |
|
|
% Substantial edits--preparing for review. |
2887 |
|
|
% |
2888 |
|
|
% Revision 1.9 2002/04/26 03:47:22 dtashley |
2889 |
|
|
% Substantial edits. |
2890 |
|
|
% |
2891 |
|
|
% Revision 1.8 2002/04/23 02:58:53 dtashley |
2892 |
|
|
% Edits. |
2893 |
|
|
% |
2894 |
|
|
% Revision 1.7 2002/04/22 07:27:32 dtashley |
2895 |
|
|
% Preparing to work on desktop computer again. |
2896 |
|
|
% |
2897 |
|
|
% Revision 1.6 2002/04/22 04:47:30 dtashley |
2898 |
|
|
% Preparing to work on laptop. |
2899 |
|
|
% |
2900 |
|
|
% Revision 1.5 2002/04/22 02:11:54 dtashley |
2901 |
|
|
% Preparing to resume work on desktop. |
2902 |
|
|
% |
2903 |
|
|
% Revision 1.4 2002/04/22 00:14:56 dtashley |
2904 |
|
|
% Edits before resuming work on desktop. |
2905 |
|
|
% |
2906 |
|
|
% Revision 1.3 2002/04/21 23:05:09 dtashley |
2907 |
|
|
% Version control information straightened out. |
2908 |
|
|
% |
2909 |
|
|
%End of file C_RAT0.TEX |