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

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

Parent Directory Parent Directory | Revision Log Revision Log | View Patch Patch

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