/[dtapublic]/pubs/books/ucbka/trunk/c_rat0/c_rat0.tex
ViewVC logotype

Annotation of /pubs/books/ucbka/trunk/c_rat0/c_rat0.tex

Parent Directory Parent Directory | Revision Log Revision Log


Revision 6 - (hide annotations) (download) (as text)
Fri Oct 7 01:36:46 2016 UTC (8 years, 2 months ago) by dashley
File MIME type: application/x-tex
File size: 111163 byte(s)
Initial commit after migrating from CVS.
1 dashley 6 %$Header: /home/dashley/cvsrep/e3ft_gpl01/e3ft_gpl01/dtaipubs/esrgubka/c_rat0/c_rat0.tex,v 1.28 2004/02/22 19:27:48 dtashley Exp $
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

dashley@gmail.com
ViewVC Help
Powered by ViewVC 1.1.25