trunk/c_cil0/c_cil0.tex

%$Header: /home/dashley/cvsrep/e3ft_gpl01/e3ft_gpl01/dtaipubs/esrgubka/c_cil0/c_cil0.tex,v 1.24 2003/11/03 02:14:24 dtashley Exp $

\chapter[\ccilzeroshorttitle{}]{\ccilzerolongtitle{}}

\label{ccil0}

\beginchapterquote{``If our ancestors had invented arithmetic by counting with
                     their two fists or their eight fingers, instead of their
                     ten `digits', we would never have to worry about
                     writing binary-decimal conversion routines.
                     (And we would perhaps never have learned as much about
                     number systems.)''}
                     {Donald E. Knuth, \cite[p. 319]{bibref:b:knuthclassic2ndedvol2}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}
%Section tag: INT0
\label{ccil0:sint0}

Low-cost microcontrollers have no support for floating-point arithmetic,
and so integer arithmetic and fixed-point arithmetic are used nearly exclusively
in embedded systems.  The ability to implement integer arithmetic
economically is a critical skill in the development of embedded
systems.

Integer arithmetic algorithms are critically important in embedded
systems for the following reasons:

\begin{itemize}
\item Mistakes in the implementation of arithmetic are frequently
      responsible for product problems.  (Mistakes are not confined
      to obvious errors---errors such as filters which do not converge
      on their input are also responsible for product problems.)
\item Floating-point arithmetic is not available or ill-advised
      for nearly all small embedded systems for the following reasons:
      \begin{itemize}
      \item Low-cost microcontrollers do not possess hardware support for
            floating-point arithmetic.
      \item Implementation of floating-point arithmetic in software is
            computationally expensive.
      \item Implementation of floating-point arithmetic in software may
            require large floating-point libraries, typically consuming
            1K-4K of ROM.
      \item Safety-critical software standards typically prohibit the
            use of floating-point arithmetic.
      \end{itemize}
\item Integer arithmetic algorithms (other than addition and subtraction)
      are quite tedious and error-prone for a software developer to design, implement, and
      unit test.  The implementation of such algorithms represents
      cost and risk.  Cost and risk benefits are achieved if the algorithms in detail are 
      available in advance (thus precluding design activities), or
      better yet if ready-to-use integer algorithm libraries are available.
\end{itemize}

This chapter describes the more fundamental principles and algorithms
(representation, fixed-point arithmetic, treatment of overflow, comparison,
addition, subtraction, multiplication, and division).  A section 
(Section \ref{ccil0:smim0}) is also included 
on miscellaneous mappings involving integers which
are not numerical in intent.
Chapter %\cdtazeroxrefhyphen\cdtazerovolarabic{} 
TBD
describes more complicated 
integer algorithms and techniques (discrete-time operations
such as filtering, integration, and differentiation as well as more
complex functions such as square root).  The split between these two chapters
is arbitrary; and in fact the material could have been divided differently
or combined.

Treatment of the topics in this chapter is largely in accordance with
Knuth \cite{bibref:b:knuthclassic2ndedvol2}.  The principal issues in 
the implementation of integer algorithms are:

\begin{itemize}
\item \textbf{How to use the arithmetic [or other] instructions provided by the machine to
      operate on larger operands.}  Microcontrollers typically provide arithmetic
      instructions (comparison, shifting, addition, subtraction, and often but not
      always multiplication and/or division) that operate on 8-bit or 16-bit integers.  
      A key question
      is how small-operand instructions ``scale up''---that is, if and how they can
      be used to assist in the implementation of integer arithmetic for much larger 
      operands.
\item \textbf{The order of the algorithm involved.}  The order of algorithms
      is a complicated issue when applied to microcontroller work.  Many sophisticated
      algorithms have a breakpoint below which they are less economical than
      an inferior algorithm.  Some applications (such as generating cryptographic keys
      when integers thousands of bits long must be tested for primality) will
      benefit from sophisticated algorithms becuase the operand sizes are large enough
      to pass any such breakpoints.  However, in microcontroller work, the need to manipulate
      integers longer than 64 bits is very rare; thus, the breakpoints that indicate the
      use of more sophisticated algorithms may not be reached.  In microcontroller work,
      depending on the operand sizes, there are circumstances in which an
      $O(n^2)$ algorithm may be preferable to an $O(\log n)$ algorithm.  Generally,
      the order of algorithms must be balanced against operand sizes.
\end{itemize}

We do diverge from Knuth in some areas.  The most prominent divergence is
in the proofs offered for some important theorems and lemmas.  Knuth 
employs contrapositive proof formats in many circumstances, whereas we prefer
to use linear proofs that are more understandable to engineers and microcontroller
software developers.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section[Paradigms And Principles]
        {Paradigms And Principles Of Microcontroller Arithmetic}
%Section tag: PPM0
\label{ccil0:sppm0}

How should one think about microcontroller arithmetic?  What principles
guide us in its design and implementation?  In this section,
we provide some general principles and paradigms of thought.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Microcontroller Arithmetic As An Accident Of Silicon Design}
%Subsection tag: MAS0
\label{ccil0:sppm0:smas0}

In chapters
\cfryzeroxrefhyphen{}\ref{cfry0},
\ccfrzeroxrefhyphen{}\ref{ccfr0},
and 
\cratzeroxrefhyphen{}\ref{crat0} 
we consider rational approximation,
both in the form $h/k$ and $h/2^q$.  Both forms of rational approximation
tend to be effective because we know that all modern processors possess
shift instructions, most possess integer multiply instructions, and many 
possess integer divide instructions.  In other words, the design
of the machine instruction set drives the strategies for implementation
of arithmetic, and makes some strategies attractive.

Similarly, the observation that all microcontrollers provide instructions
for integer arithmetic creates the attractiveness of fixed-point arithmetic.

Thus, we might view our approaches to microcontroller arithmetic as 
an ``accident'' of silicon design, or as being driven by silicon
design.

Generally, we seek to determine the best way to use the primitive
operations provided by the machine (the instruction set) to 
accomplish the mappings of interest.

The ``classic'' algorithms 
presented by Knuth 
Knuth (\cite[pp. 265-284]{bibref:b:knuthclassic2ndedvol2}) are especially
designed to use the ``small'' addition, subtraction, multiplication, and
division provided by the machine to add, subtract, multiply, and divide arbitrarily
large integers.  In 
\cite[pp. 265-266]{bibref:b:knuthclassic2ndedvol2}) Knuth writes:

\begin{quote}
\emph{The most important fact to understand about extended-precision numbers
is that they may be regarded as numbers written in radix-$w$ notation,
where $w$ is the computer's word size.  For example, an integer that
fills 10 words on a computer whose word size is $w=10^{10}$ has 100
decimal digits; but we will consider it to be a 10-place number to
the base $10^{10}$.  This viewpoint is justified for the same reason
that we may convert, say, from binary to hexadecimal notation,
simply by grouping the bits together.}

\emph{In these terms, we are given the following primitive operations to work with:}

\begin{itemize}
\item \emph{a$_0$) addition or subtraction of one-place integers, giving a one-place
             answer and a carry;}
\item \emph{b$_0$) multiplication of a one-place integer by another one-place integer,
             giving a two place answer;}
\item \emph{c$_0$) division of a two-place integer by a one-place integer, 
             provided that the quotient is a one-place integer, and yielding
                            also a one-place remainder.}
\end{itemize}

\noindent{}\emph{By adjusting the word size, if necessary, nearly all computers
will have these three operations available; so we will construct algorithms
(a), (b), and (c) mentioned above in terms of the primitive operations
(a$_0$), (b$_0$), and (c$_0$).}

\emph{Since we are visualizing extended-precision integers as base $b$ numbers, it is
sometimes helpful to think of the situation when $b = 10$, and to imagine
that we are doing the arithmetic by hand.  Then operation (a$_0$) is analogous
to memorizing the addition table; (b$_0$) is analogous to memorizing the 
multiplication table, and (c$_0$) is essentially memorizing the multiplication
table in reverse.  The more complicated operations (a), (b), (c) on
high-precision numbers can now be done using simple addition, subraction,
multiplication, and long-division procedures that children are taught
in elementary school.}
\end{quote}

The critical issue for implementation of integer arithmetic with large operands
is how to use small-operand instructions to operate on larger operands---in other words,
how to ``scale up'' the capability provided by the instruction set. 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Microcontroller Arithmetic As A Mapping From Quantized Domain To
            Quantized Range}
%Subsection tag: MAM0
\label{ccil0:sppm0:smam0}

Microcontroller software accepts inputs which are quantized.  In nearly all cases,
this involves a mapping from $\vworkrealset$ to $\vworkintset$.  Often, because
microcontroller products are optimized for cost, the quantization hardware
delivers quite poor precision, frequently less than 8 bits.  

When a quantized input is accepted, it defines an inquality.  Knowledge of
the quantized input (an integer) confines the actual input (a real
number, before 
quantization) to an interval.  With a low-cost hardware design, the
interval can be fairly large.  Usually, by adding cost, the
interval can be made smaller.

Microcontroller outputs tend to be quantized as well, so it is
accurate to also characterize outputs as integers.  For example, a PWM signal
generated by a microcontroller or the output of a D/A converter is
controlled by data that is an integer.  Like inputs, often the ``granularity''
with which outputs can be controlled is quite coarse---again, 8 bits or
less is not uncommon.

Thus, we may view microcontroller software as a mapping from poor-quality
inputs to poor-quality outputs.

In such a framework, where the nature of inputs and outputs introduces
substantial error, it is imperative not to introduce additional error
in computer arithmetic.  In other words, given inputs which are 
integers, the responsibility of the software is to choose the best 
integers as outputs.  Usually this means that calculations should be
devised so as not to lose any information (i.e.
not to lose remainders, for example).  Losing information is usually
equivalent to not being able to make the most correct mapping from input
to output.  ``Lossy'' arithmetic can degrade the performance of a system,
since poor arithmetic may compound an inexpensive hardware design.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Microcontroller Arithmetic As A Simulation Of Continuous Controllers}
%Subsection tag: MAE0
\label{ccil0:sppm0:smae0}

Control systems have not always employed digital controllers.
Many books and web sites (see \cite{bibref:w:historycontrol01}, for example)
discuss the historical development of feedback control.  Controllers
have not historically been digital, or even electronic.
Early controllers for governing steam devices or windmills were
ultimately mechanical, and relied upon inertia or other physical
properties.  It is possible to realize abstract notions
(integrators, differentiators, gains) using hydraulic systems or other mechanical systems;
and in fact hydraulic feedback controllers were used in early rockets
and aircraft.  Very naturally, abstract notions (integrators,
differentiators, gains) can be implemented using analog
electronic components.  The most common implementations involve
operational amplifiers, and the behavior of such implementations comes
very close to the ideal mathematical models.

Mechanical, hydraulic, and non-digital electronic controllers have
one very desirable characteristic---\emph{clipping}.  If, for example,
one provides an analog differentiator with a $dV/dt$ which
is too large, the output that the differentiator can 
provide is limited, usually by the supply voltage available to an operational
amplifier.
The differentiator \emph{must} clip.

Clipping often leads to behavior which is close to what
intuition would expect (i.e. we would present 
clipping as an occasional advantage).  For example, if an input to
an analog control system suffers a failure, the behavior
the of the controller is limited, as is its internal
state.  Similarly, when the
input is restored, the controller will usually recover 
in a reasonable time because the
state of the controller (typically maintained in capacitors) is limited
in the magnitude it can attain.

We might view a digital controller as an emulation of
an analog controller.  We may want to cause the
controller to have limits (i.e. rails) internally, for
example to prevent excessive integrator ``windup''.  We discuss
this further in Section \ref{ccil0:sode0}.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Practical Design Issues}
%Section tag: PDI0
\label{ccil0:spdi0}

In this section, we consider practical issues surrounding the design
and construction of a set of integer arithmetic subroutines.
In practice, such a collection of subroutines is likely to be
arranged into a library.  The purpose of the library would be to
free the clients (or callers) of the library from the complexity of 
large integer calculations.

The design decisions surrounding the construction of a library vary in
the objectivity with which they can be approached.  Some design decisions
(such as the best mechanism for passing parameters) can be approached
rigorously because the measures of goodness are unequivocal (minimal ROM consumption
or execution time, for example).  However, other design decisions, particulary the
decision of the exact nature of the interface between an arithmetic library and
its clients, are more subjective.  One size does \emph{not} fit all.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Parameter Passing And Temporary Storage Mechanisms}
%Subsection tag: PPM0
\label{ccil0:spdi0:sppm0}

In small microcontroller work, the desire to save ROM and execution time
may lead to inelegant software construction.  Because an arithmetic library
used in microcontroller work may be called from many different places 
throughout ROM, serious thought should be given to optimizing the 
parameter passing mechanisms, even perhaps at the expense of elegance.
The way in which the arithmetic library allocates temporary storage is
also a point of concern, because the most elegant way of allocating temporary
storage (on the stack) may either not be feasible (because of the possibility
of stack overflow) or may not be efficient (because the addressing modes of
the machine make data on the stack inefficient to address).  In this section
we discuss both parameter passing and temporary storage mechanisms.

In the remainder of the discussion, we make the following assumptions
about software architecture.

\begin{enumerate}
\item \textbf{The arithmetic library need not be re-entrant.}
      Most ``small'' microcontroller software loads use a non-preemptive
      scheduling paradigm, so this is a reasonable assumption.  We also
      make the reasonable assumption that ISR's may not make calls into 
      the arithmetic library.
\item \textbf{Dynamic memory allocation, other than on the stack,
      is not allowed by the software architecture.}  This is also
      a reasonable assumption in ``small'' microcontroller software.
\end{enumerate}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Parameter Passing Mechanisms}
%Subsubsection tag: PPM0
\label{ccil0:spdi0:sppm0:sppm0}

If an arithmetic library exists in a microcontroller software load,
it may be called many times throughout ROM.  Thus, the parameter 
passing mechanisms chosen may have a large effect on ROM consumption
(due to the setup required for each subroutine call multiplied by
many instances throughout ROM) and execution time
(because in microcontroller software longer instructions nearly always
require more time).  Because of the criticality of ROM consumption,
parameter passing mechanisms that lack elegance may be attractive.

In the category of parameter passing, we also include the way in which
return value(s) are passed back to the caller.

The following parameter-passing mechanisms may be employed:

\begin{enumerate}
\item \textbf{Pass by value as storage class \emph{automatic}.}
      The most common scenario is that the arithmetic
      library is written in assembly-language to be called from
      `C', and so the assembly-language subroutines must adhere to the
      parameter-passing conventions used by the compiler.
      This usually means that the entire input or output value
      will be passed in CPU registers or on the stack.  Somewhat rarely, 
      a compiler will pass parameters in static locations.\footnote{The
      usual reason for a `C' compiler to pass parameters in static locations
      is because the instruction set of the machine was not designed for
      higher-level languages, and references to [usually \emph{near}] memory
      are cheaper than stack references.  Such compilers also typically 
      analyze the calling tree of the program where possible and use this
      information to overlay the parameter-passing memory areas of 
      subroutines that cannot be active simultaneously.  Without the ability
      to analyze the calling tree and make overlay decisions based on it,
      memory would be exhausted, because each subroutine would need to have its
      own static storage for parameters and local variables.}
\item \textbf{Pass by reference.}
      Typically, it is convenient to pass pointer(s) to area(s) of memory
      containing input operands, and also a pointer to an area of memory
      owned by the caller which is written with the result by the arithmetic subroutine.
      The efficiency of this approach depends on the compiler and the instruction
      set of the machine.  If the instruction set of the machine cannot 
      make effective use of pointers or stack frames, an arithmetic subroutine
      might be constructed so that it first copies the operands to a static area of memory
      reserved for the arithmetic library, then performs the necessary arithmetic
      operations on the operands in the static area, 
      then copies the result(s) back to the area owned by the caller.
\item \textbf{Pass by common data block.}
      In some cases, it may be preferable to reserve a block of memory in which to
      pass parameters to arithmetic library functions, and from which to retrieve
      results after an arithmetic library function returns.  The allocation of such
      a static memory block may be done manually\footnote{Note to self:  need to
      include gentleman's agreements on memory usage in my note on software architecture.}
      or automatically (by development tools which can analyze the function calling tree and
      manage the overlaying).
\end{enumerate}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Temporary Storage Mechanisms}
%Subsubsection tag: TSM0
\label{ccil0:spdi0:sppm0:stsm0}

Need to indicate clearly on section on software architectures the
primary temporary storage mechanisms:

\begin{itemize}
\item Stack.
\item Memory block with overlay functionality.
\end{itemize}

Need to expand software architecture section to cover this, so don't
discuss here.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Reporting Of Overflow, Underflow, And Domain Errors}
%Subsection tag: OUD0
\label{ccil0:spdi0:soud0}

Long integer data types used in microcontroller work are typically
of a static size (they cannot grow in size in as operations are 
performed on them).  The reason for the typical static sizes is that
dynamic allocation (except for allocation and
deallocation on the stack as subroutines
are called and return) is rarely used in small microcontroller work.
It will come about in the normal usage of an integer arithmetic 
library that an attempt will be made to operate on integers in
a way which generates an overflow, generates an
underflow, or
represents a domain error (division by zero or
square root of a negative integer, for example).
An important design decision is how such normal exceptions should be
handled.

Possible design decisions in this area are:

\begin{enumerate}
\item \label{enum:ccil0:spdi0:soud0:01:01}
      \textbf{To design arithmetic subroutines so that exceptions are not
      possible.}  
      For example, multiplying an $m$-word integer by an $n$-word integer
      will always generate an integer that will fit within $m+n$ words.
      If a multiplication subroutine is designed so that the caller must
      provide an $m$-word operand and an $n$-word operand and a pointer to
      an $(m+n)$-word area of memory for the result, an overflow cannot occur.
      Such a design decision essentially pushes overflow detection back up to
      the callers of arithmetic subroutines.
\item \label{enum:ccil0:spdi0:soud0:01:02}
      \textbf{To design arithmetic subroutines so that exceptions are possible,
      but not to detect the exceptions, thus providing an implementation that
      will produce incorrect results with some operand data values.}
      For example, if an arithmetic subroutine is designed to add an $m$-word
      operand to another $m$-word operand to produce an $m$-word result, overflow
      is possible.  A design decision to fail to detect such exceptions pushes
      the responsibility up to the callers of the arithmetic subroutines.
      Callers must devise a method for not calling arithmetic subroutines
      with data values that will cause an exception, or else to detect an exception
      when it has occurred.
\item \label{enum:ccil0:spdi0:soud0:01:03}
      \textbf{To ``rail'' the result in response to an exception.}  
      It was stated earlier that analog control system functional blocks
      built with operational 
      amplifiers typically have an output which cannot go beyond the 
      supply rails.  One may implement similar behavior in arithmetic subroutines.
      In an addition subroutine which adds two $m$-word operands to produce an
      $m$-word result (with each word having $w$ bits), it would be natural to 
      return $2^{mw}-1$ in the event of an overflow in a positive direction and 
      $-2^{mw}$ in the event of an overlfow in a negative direction.  Note that
      the caller will not be able to distinguish a ``rail'' value which represents
      a valid result from a ``rail'' value substituted to indicate an exception.
\item \label{enum:ccil0:spdi0:soud0:01:04}
      \textbf{To reserve special result data values to indicate exceptions.}
      Depending on the arithmetic subroutine being implemented, it may be possible
      to reserve certain result data values to indicate exceptions.  This approach
      is often awkward, as most mathematical subroutines are naturally defined so that
      all bit patterns in the memory reserved for the result are valid numbers.
      Additionally, with long result data values, it may not be economical to
      compare the result against the reserved exception values.  Thus, this is seldom
      an optimal way to deal with exceptions.

      Additionally, if this approach is employed, the semantics of how exception
      values combine with other exception values and data values must be decided.
\item \label{enum:ccil0:spdi0:soud0:01:05}
      \textbf{To return exception codes to the caller separate from the result data.}
      In the `C' language, pointers are often used to supply an arithmetic subroutine
      with the input operands and to provide the arithmetic subroutine with a location
      (which belongs to the caller) in which to store the result data.  Thus, the return
      value of the arithmetic subroutine (normally assigned through the subroutine name)
      is often available to return exception codes.  For example,
      a `C' function may be defined as 

      \begin{verbatim}
      unsigned char int128_add(INT128 *result, 
                               INT128 *arg1, 
                               INT128 *arg2),
      \end{verbatim}

      leaving the returned \texttt{unsigned char} value available to return
      exception information.  Note that this arrangement has the following advantages:

      \begin{enumerate}
      \item All bit patterns in the result data memory area area available
            as data bit patterns.
      \item The exception data is very economical to test, because it is placed
            in a machine-native data type.
      \item The exception data can easily be discarded or by the caller if desired.
      \item All decisions about how to handle exceptions are left to the caller. 
      \end{enumerate}
\item \label{enum:ccil0:spdi0:soud0:01:06}
      \textbf{To maintain exception data with each result integer.}
      It is possible to reserve bits for exception information which are part of the
      long integer data type.  This exception state essentially conveys 
      \emph{NaN}\footnote{\emph{N}ot \emph{a} \emph{n}umber.} information---integers with
      exception information set are not true numbers, but rather they are different from the
      true result in some way.  As with (\ref{enum:ccil0:spdi0:soud0:01:04}), the 
      semantics of how to combine NaN values and NaN values with ordinary non-NaN numbers
      must be defined.
\item \label{enum:ccil0:spdi0:soud0:01:07}
      \textbf{To maintain a global exception state variable.}
      A variable or set of variables can be reserved which hold the
      exception information, if any, from the most recent call to 
      a function in the arithmetic library.
      
      To save CPU cycles, the arithmetic library can 
      be designed so that it will assign the global exception state variable only if an 
      exception occurs---the caller then has the responsibility of clearing the exception
      state variable before making any call into the arithmetic library where the 
      exception result is of interest.  The interface between the caller and the library
      can be further optimized if the library only OR's data into the variable containing
      the exception state.  Using this optimization, the caller can clear the exception state 
      variable, make several calls into the arithmetic library, and then retrieve a meaningful
      exception state variable value summarizing several arithmetic operations.
\item \label{enum:ccil0:spdi0:soud0:01:08}
      \textbf{Hybrid approaches.}
      The approaches (\ref{enum:ccil0:spdi0:soud0:01:01})
      through (\ref{enum:ccil0:spdi0:soud0:01:07}) can be combined.
      For example, approach (\ref{enum:ccil0:spdi0:soud0:01:03})
      might be combined with approach (\ref{enum:ccil0:spdi0:soud0:01:05})
      so that exceptions are ``railed'', but the caller may also be made
      aware that an exception has occured.  Many hybrid approaches are possible.
\end{enumerate}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Semantics Of Combining Overflow, Underflow, And Domain Errors}
%Subsection tag: CMB0
\label{ccil0:spdi0:scmb0}

For control system arithmetic, some form of clipping as suggested
in Section \ref{ccil0:sppm0:smae0} is probably the 
best approach.  Definitely, an overflow should generate a result
which is the largest representable integer, and an
underflow should generate a result which is the smallest
representable integer.

In addition to treating an overflow by clipping, it may be 
advantageous to reserve a flag in the representation of a
multiple-precision integer to record that an overflow has occured and been clipped.
Some functions which accept the integer as input may be interested
in the value of such a flag, where othere---perhaps most---may
not.

The correct course of action in the event of a domain error (such
as division by zero) is less clear.  It is noteworthy that in a
normal control system, domain errors cannot occur (but overflows
can).

The best approach when a domain error is involved probably 
depends on the basis for the underlying calculation.  For
example, if integer division is used as part of a 
strategy for software ratiometric conversion, a value
of zero in the denominator probably represents extreme electrical
noise, and the most sane approach may be to replace the
denominator by one.  However, in other contexts it may be appropriate
to think in terms of 

\begin{equation}
\lim_{k \rightarrow 0^+} \frac{kn}{kd}
\end{equation}

\noindent{}or

\begin{equation}
\lim_{k \rightarrow 0^-} \frac{kn}{kd} .
\end{equation}

Put in other terms, there is not a clear ``one solution
meets all needs'' approach to dealing with domain
errors.

As in the case of overflows, it may be advantageous to reserve a bit
flag to signal that a domain error has occured and that the result
is not valid or not reliable.  Note that floating point chips
(such as the 80x87) provide similar indications of domain errors.

It may also be advantageous to adopt conventions for how 
overflow or domain error flags propagate through binary or
unary operators.  For example, if two numbers are multiplied, and
one of the two has the overflow flag set, it may be wise set the
overflow flag in the  result.  A scheme for how warning
flags propagate may be beneficial.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Variable Versus Constant Subroutine Execution Time}
%Subsection tag: VVC0
\label{ccil0:spdi0:svvc0}

As a design goal of an embedded system, we seek to minimize the
timing variability of software components.  An arithmetic subroutine
that with a high probability takes a short time to execute and with a
low probability takes a long time to execute, and where the execution
time is data dependent, is a serious risk.  An embedded software product 
may pass all release testing, but then fail in the field because of 
specific data values used in calculations.

A very conservative design goal would be to design every arithmetic subroutine
to require exactly the same execution time, regardless of data values.
This goal is not practical because machine instructions themselves
usually have a variable execution time, particularly for multiplication
and division instructions.  A fallback goal would be to avoid
large differences between minimum and maximum execution time, without
increasing the maximum execution time.  A very practical step to take
(using division as an example) 
is to insert artifical delays into easily detectable exception cases (such as
division by zero) so that the exception case takes as long as the 
minimum time for a division with valid operands.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Fixed-Point Arithmetic}
%Section tag: FPA0
\label{ccil0:sfpa0}

\emph{Fixed-point arithmetic}\index{fixed-point arithmetic} 
is a scheme for the representation
of engineering quantities (conceptually real numbers with optional
units) by integers so that calculations can be performed
on these quantitites using [usually multiple-precision]
integer arithmetic.

In discussing fixed-point arithmetic,
we must be careful to distinguish between the 
\emph{represented value} (the engineering quantity)
and the \emph{representation} (the integer which represents 
the engineering quantity).  In most cases, we must also
be careful to devise a system to track the units of the 
represented values, as, especially with control systems,
the units of represented values (due to integration and 
differentiation) can become very complex
and mistakes are easy to make.

Fixed-point arithmetic is the dominant paradigm of construction
for calculations in small microcontroller systems.  It may not be
clear why this should be so or what advantages it offers [over
floating-point arithmetic].  The reasons for
this predominance are:

\begin{itemize}
\item Fixed-point calculations tend to be very efficient, because
      they make direct use of the integer arithmetic instructions in the
      microcontroller's instruction set.  On the other hand, floating-point
      arithmetic operations tend to be much slower.

\item Floating-point calculations typically require a floating-point
      library, which may consume at least several hundred bytes
      of ROM.

\item Some safety-critical software standards prohibit the use of 
      floating-point arithmetic because it can result in nebulous
      behavior.  Fixed-point arithmetic avoids these concerns.
\end{itemize}

In order to carry out fixed-point arithmetic---that is, in order to
operate on engineering quantities as integers---we 
require that the relationship between the 
represented value and the representation be of the form

\begin{equation}
\label{eq:ccil0:sfpa0:00}
x = r_I u + \Psi,
\end{equation}

\noindent{}where $x \in \vworkrealset$ (possibly with units) is the represented
value, $u \in \vworkintset$ is the representation, 
$r_I \in \vworkrealset$ is the scaling factor (possibly with
units), and $\Psi \in \vworkrealset$ (possibly with units) is the offset.
Note that the units of $r_I$, $\Psi$, and $x$  must match.

We further require that $r_I \vworkdivides{} \Psi$\footnote{We \emph{are}
aware that this is an abuse of nomenclature, as 
`$\vworkdivides$' (``divides'') is traditionally only applied to integers.} 
(i.e. that $\Psi$ be an
integral multiple of $r_I$)
so that the offset in the represented value corresponds to an integer
in the representation.  Without this restriction, we could not remove the
offset from the representation with integer subtraction only.  Note that
we do \emph{not} require that $r_I$ or $\Psi$ be rational, although
they must both be rational or both be irrational in order to satisfy
(\ref{eq:ccil0:sfpa0:00}).

In (\ref{eq:ccil0:sfpa0:00}), since we've required that $r_I \vworkdivides{} \Psi$, 
we can replace $\Psi$ by 

\begin{equation}
\label{eq:ccil0:sfpa0:00b}
\psi = \frac{\Psi}{r_I}
\end{equation}

\noindent{}to obtain

\begin{equation}
\label{eq:ccil0:sfpa0:01}
x = r_I (u + \psi),
\end{equation}

\noindent{}where $\psi \in \vworkintset$ is the offset in representational
counts.

Note that we can also easily obtain the following relationships from the
defining equations (\ref{eq:ccil0:sfpa0:00}), 
(\ref{eq:ccil0:sfpa0:00b}), and (\ref{eq:ccil0:sfpa0:01}).

\begin{equation}
\label{eq:ccil0:sfpa0:02}
u = \frac{x - \Psi}{r_I} = \frac{x}{r_I} - \psi
\end{equation}

\begin{equation}
\label{eq:ccil0:sfpa0:03}
\psi = \frac{\Psi}{r_I}
\Longleftrightarrow
\Psi = r_I \psi
\Longleftrightarrow
r_I = \frac{\Psi}{\psi}
\end{equation}


For example, in a 16-bit signed integer (which inherently may range
from -32768 to 32767 inclusive), one might used a fixed-point
representation of 100 integer counts per $^\circ$C ($r_I = 0.01 \; ^\circ$C)
with an offset of 100$^\circ$C ($\Psi$ = 100$^\circ$C or equivalently
$\psi$ = 10000), giving
a representational range from -227.68$^\circ$C to 427.67$^\circ$C inclusive.

If $r_I = 2^N, \; N \in \vworkintset$, then the radix point of the represented 
value is positioned 
between two bits of the representation---this arrangement may have computational
advantages
if the whole and fractional parts of the represented value need to be separated
easily in the representation.  Note also that if $r_I = 2^{WN}$ where $W$ is the 
machine integer size of the computer (in bits), then the radix point of the represented value
occurs between two addressable machine integers of the representation, which can be convenient.
However, we do not require for our definition of a fixed-point representation that 
$r_I$ be an integral power of two; and in fact we do not even require by our
definition that $r_I$ be rational.  Note that in general our definition above is the
weakest set of conditions so that real-world engineering values can be manipulated
using integer operations performed upon the representation.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Representation Of Integers}
%Section Tag: ROI0
\label{ccil0:sroi0}

In this section, we discuss common representations of integers, both
\emph{machine} integers and \emph{synthetic long} integers.  
By \emph{representation} we mean the mapping between the abstract
mathematical notion of an integer and the way it is stored in the computer
(voltage levels and the programming model). 
Although
in Knuth's development of integer arithmetic
\cite{bibref:b:knuthclassic2ndedvol2}
 it is assumed that 
integers may be represented in any base, we don't require such generality
in practice and in this work we confine ourselves for the most
part to $b=2^n$, and often to $n = 8i$, $i \in \vworkintsetpos$.  The assumption
of $b=2^n$ characterizes all modern digital computers, and we feel comfortable
making this assumption throughout the work.  However, the assumption 
$n = 8i$, $i \in \vworkintsetpos$ does not hold universally, and so we
most often do not make this assumption.

By \emph{machine} integer, we mean an integer upon which the computer
can operate in a single instruction (such as to add, increment,
load, store, etc.).  For most microcontrollers, machine integers are
either 8 or 16 bits in size.  The representation of a machine integer
is designed and specified by the microcontroller manufacturer.  In principle,
nothing would prevent a microcontroller manufacturer from devising
and implementing a novel way of representing machine integers and supporting
this novel representation with an instruction set.  However, in 
practice, all machine integers are either simple unsigned integers or two's
complement signed integers.  In addition to the efficiency of these
representations with respect to the design of digital logic, these representations
are so standard and so pervasive that they are universally tacitly assumed.
For example, ``\texttt{if (i \& 0x1)}'' is an accepted C-language
idiom for ``if $i$ is odd'', and it is expected that such code will
work on all platforms.

By \emph{synthetic long} integer, we mean an integer of 
arbitrary\footnote{By \emph{arbitrary}, we do not necessarily mean that
the integer can grow to be arbitrarily large in magnitude, or that
its maximum size is not known at compile time.  We mean \emph{arbitrarily}
longer than a machine integer.  Multiple-precision arithmetic libraries
can be divided into two classes---those that fix the size of the integers
at compile time, and those that use dynamic allocation and allow integers to
grow as needed at run time.  The former category
is normally used for small microcontroller work, whereas the latter category
(such as the GNU MP Library \cite{bibref:s:gnumultipleprecisionarithmeticlibrary})
is normally used in scientific and number theoretic calculation and on 
more powerful platforms than microcontrollers.  The representational concepts
we present here apply to both categories.}
length that is formed by concatenating machine integers.  There is some
subjectivity in deciding the representation of multiple-precision integers,
and we discuss in the subsections
\ref{ccil0:sroi0:srou0} and
\ref{ccil0:sroi0:sros0} which immediately follow.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Representation Of Unsigned Integers}
%Subsection Tag: ROU0
\label{ccil0:sroi0:srou0}

Unsigned machine integers are always represented as an ordered 
array of bits (Figure \ref{fig:ccil0:sroi0:srou0:00}).  For an
$m$-bit unsigned integer $u$, we denote these bits $u_{[m-1]}$ through
$u_{[0]}$, with $u_{[m-1]}$ the most significant bit.  The value
of $u$ is the sum of the values of each bit multiplied
by the power of 2 it represents:

\begin{figure}
\centering
\includegraphics[width=4.6in]{c_cil0/uintrep1.eps}
\caption{Representation Of Unsigned Machine Integers}
\label{fig:ccil0:sroi0:srou0:00}
\end{figure}

\begin{equation}
\label{eq:ccil0:sroi0:srou0:00}
u = \sum_{i=0}^{m-1} u_{[i]} 2^i .
\end{equation}

In general, an $m$-bit unsigned integer can assume the values of 
0 through $2^m - 1$, so that

\begin{equation}
\label{eq:ccil0:sroi0:srou0:01}
u \in \{0, \ldots{} , 2^m - 1 \} .
\end{equation}

Unsigned synthetic long integers are always represented as an array
of unsigned machine integers.  
Consistent with the GMP \cite{bibref:s:gnumultipleprecisionarithmeticlibrary},
we call each element of the array a \emph{limb} and we call the size of
each limb the \emph{limbsize}.  This usage is very close to what Knuth
calls the \emph{word}size $w$ in the excerpt presented in 
Section \ref{ccil0:sppm0:smas0}.

Microcontroller processors are more likely than more powerful processors to have
a non-orthogonal instruction set, and so the limbsize may not be consistent between
operations in an arithmetic library.
With some processors, the appropriate limbsize may vary depending on the operation being
performed.  
For example, a microcontroller processor may be able to add two 16-bit integers to
obtain a 16-bit result plus a carry, but only be able to multiply two 8-bit integers to 
obtain a 16-bit result (thus, the appropriate limbsize for addition may be 
16 bits while the appropriate limbsize for multiplication may be 8 bits).
In such cases, it is usually most efficient to add using 16-bit limbs but
multiply using 8-bit limbs.  Adding using 8-bit limbs on a machine which will
support 16-bit additions is not normally a good design decision---even if the 
machine supports an 8-bit addition instruction which is faster than the 16-bit addition
instruction, $m/2$ 16-bit additions will nearly always be faster than 
$m$ 8-bit additions.  Using different limbsizes within the same arithmetic library
may require some consideration of alignment and 
endian issues, but these are implementation details
which are easily solved.

We view a synthetic long unsigned integer as an array of limbs (machine integers)
of some size, and we agree that we will not address the array in any other way than
by loading and storing limbs of this size.\footnote{Well \ldots{} not quite.
In software for large computers (personal computers and workstations) with an
orthogonal instruction set, we may be able to adhere to this rule.  However,
with microcontrollers, arithmetic libraries which are optimized
may break this rule.}  In particular, because
computers may be ``big-endian'' or ``little-endian'', loading and storing 
smaller units than limbs may lead in
a worst case to software defects or in a best case to non-portable code.

Assume that $w$ is the number of bits in a limb.
Notationally, we denote an unsigned
synthetic long integer as an array of $m$ limbs
$u_{m-1}$ through $u_0$, each containing $w$ bits,
with $u_0$ the least significant machine integer.  
We may also define $b=2^w$ (consistent with Knuth's
notation).
The value of
such a synthetic long machine integer is

\begin{equation}
\label{eq:ccil0:sroi0:srou0:02}
u = \sum_{i=0}^{m-1} u_{i} 2^{wi} 
=
\sum_{i=0}^{m-1} u_{i} b^i.
\end{equation}

As an alternative, we may write the value as the sum of the bit-values,

\begin{equation}
\label{eq:ccil0:sroi0:srou0:03}
u = \sum_{i=0}^{wm-1} u_{[i]} 2^{i} .
\end{equation}

Naturally, the range of such a synthetic long integer is

\begin{equation}
\label{eq:ccil0:sroi0:srou0:04}
u \in \{0, \ldots{} , 2^{wm} - 1 \} .
\end{equation}

In storing an unsigned synthetic long machine integer, the most natural way
to order the array of limbs depends on whether dynamic memory allocation is
used by the arithmetic library.  In microcontroller work, where arithmetic
library subroutines typically operate on fixed-size operands and produce
fixed-size results, storing 
limbs most significant limb first (i.e. in `C', so that element \texttt{[0]}
of the array of limbs contains the most significant limb) may be natural
and convenient.  However, this ordering would lead to computational waste in a library such
as the GMP \cite{bibref:s:gnumultipleprecisionarithmeticlibrary} where integers
may grow arbitrarily large and the library may need to reallocate long synthetic
integers to contain more limbs, as each reallocation would need to be followed
by a memory copy to align the integer's existing limbs to the end of the array.
For libraries such as the GMP, it is more practical to store limbs 
least-significant limb first, as it eliminates the need to copy memory 
when reallocations are done.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Representation Of Signed Integers}
%Subsection Tag: ROS0
\label{ccil0:sroi0:sros0}

Signed machine integers are always represented in two's complement form on modern
processors.  This representation is universal because of the digital logic 
conveniences---the same addition and subtraction mappings which are correct 
for unsigned machine integers are also correct for signed machine integers, 
although the criteria for overflow and comparison are
different.

Most readers are familiar with two's complement representation, so we will not
belabor it.  However, we will present essential properties.
When two's complement representation is used in an $m$-bit machine integer $u$:

\begin{enumerate}
\item All bit patterns with $u_{[m-1]} = 0$ represent non-negative integers, and 
      represent the same integer as if the representation were unsigned.
\item All bit patterns with $u_{[m-1]} = 1$ represent negative numbers; specifically
      $u_{[m-2:0]} - 2^{m-1}$; i.e.

      \begin{equation}
      \label{eq:ccil0:sroi0:sros0:00}
      u = - u_{[m-1]} 2^{m-1} + \sum_{i=0}^{m-2} u_{[i]} 2^i .
      \end{equation}

\item $u \in \{-2^{m-1}, \ldots{}, 2^{m-1}-1 \}$.
\item All bit patterns represent a unique integer.
\item For any integer except $-2^{m-1}$, 
      negation can be performed by forming the one's complement (complementing
      every bit), then adding one.  To see why this is true algebraically, note that

\end{enumerate}


However, let us observe that the value of an
$m$-bit two's complement
machine integer is


In general, an $m$-bit signed machine integer can assume the values of 
$-2^{m-1}$ through $2^{m-1} - 1$, so that

\begin{equation}
\label{eq:ccil0:sroi0:sros0:01}
u \in \{-2^{m-1}, \ldots{} , 2^{m-1} - 1 \} .
\end{equation}

There are [at least] two different representations of signed 
multiple-precision integers:

\begin{itemize}
\item Two's complement representation.
\item Sign-magnitude representation.
\end{itemize}

There are two different representations commonly used 
for signed multiple-precision integers because two's complement
representation is not ideal for multiplication and division, although
it is ideal for addition and subtraction.  For multiple-precision
integer arithmetic, sign-magnitude representation is more common.

In two's complement representation of multiple-precision integers,
the representation is the same as suggested by 
(\ref{eq:ccil0:sroi0:sros0:00}), except
more bits are involved.  For a two's complement representation
of a number consisting of $n$ machine integers with $W$ bits per
machine integer,

\begin{equation}
\label{eq:ccil0:sroi0:sros0:02}
u = - u_{B(Wn-1)} 2^{Wn-1} + \sum_{i=0}^{Wn-2} u_{B(i)} 2^i .
\end{equation}

Because we would like to know how to compare signed multiple-precision
integers in two's complement representation, we can gain some
insight into the representation by rewriting 
(\ref{eq:ccil0:sroi0:sros0:02}) in terms of machine integers:

\begin{equation}
\label{eq:ccil0:sroi0:sros0:03}
u = - u_{B(Wn-1)} 2^{Wn-1} 
+ 
\sum_{i=W(m-1)}^{Wn-2} u_{B(i)} 2^i 
+
\sum_{i=0}^{m-2} u_{i} 2^{Wi} .
\end{equation}

(\ref{eq:ccil0:sroi0:sros0:03}) gives some insight into the
relative values of multiple-precision signed two's complement
integers with respect to the values of the machine integers
that comprise them.  We discuss this further in
Section \ref{ccil0:scsi0}.

In sign-magnitude representation of multiple-precision signed two's
complement integers, an integer $u$ is represented as a sign
bit (usually a value of one indicates negativity), and a magnitude, 
which is $|u|$.  Unlike two's complement representation,
sign-magnitude representation, has two representations of zero---a positive
one and a negative one.  Either a canonical form for zero should be
adopted, or both values should be treated identically.

Assuming that the sign bit is stored in the most significant bit position,
it is easy to deduce that the value of a multiple-precision
signed two's complement integer in sign-magnitude representation is

\begin{equation}
\label{eq:ccil0:sros0:srou0:04}
u = (-1)^{u_{B(m-1)}} \sum_{i=0}^{m-2} u_{B(i)} 2^i .
\end{equation}

Sign-magnitude representation is especially convenient because
it allows machine instructions which accept unsigned operands to be used
to make calculations involving signed integers.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Characteristics Of Practical Processors}
%Section tag: CPP
\label{ccil0:scpp0}

Before discussing specific algorithms, it is necessary to 
discuss the construction of practical processors---how such a processor
manipulates machine integers.  We accept as a typical processor the
TMS-370C8, an 8-bit microcontroller manufactured by 
Texas Instruments.

\begin{figure}
\centering
\includegraphics[width=4.6in]{c_cil0/t370flag.eps}
\caption{Texas Instruments TMS-370C8 Flags}
\label{fig:ccil0:scpp0:00}
\end{figure}

\begin{figure}
\centering
\includegraphics[width=4.6in]{c_cil0/t370cjmp.eps}
\caption{Texas Instruments TMS-370C8 Conditional Jump Instructions}
\label{fig:ccil0:scpp0:01}
\end{figure}

A typical microcontroller allows operations on machine integers
in the following steps:

\begin{itemize}
\item A machine instruction is performed on one or two machine 
      integer operands (for example:  addition, subtraction, 
      multiplication, division, increment, decrement, complement,
      negation, or comparison).  This machine instruction may
      produce a result, and usually sets a number of condition flags that
      reflect the nature and validity of the result (Is it zero?
      Is it negative?  Did the result overflow?).  As an
      example, the condition
      flags of the TMS-370C8 are shown in Figure \ref{fig:ccil0:scpp0:00}.
      .
\item A conditional branch instruction is used to branch conditionally
      based on the state of the condition flags.  The definition of
      the condition flags and the way in which the conditional
      branch instruction utilizes them is designed to provide a
      way to treat both unsigned and signed machine integers.
      As an example, the way in which the conditional
      jump instructions of the TMS-370C8 use the flags
      is shown in Figure \ref{fig:ccil0:scpp0:01}.
\end{itemize}

It is not too often necessary to understand in detail
the Boolean relationships that govern how machine integers are
added, subtracted, and compared; and how signed comparisons differ
from unsigned comparisons.  In most cases, it is adequate to
rely on the design of the microcontroller.  However, we do present
rudimentary observations in this section.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Comparison Of Integers}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Comparison Of Unsigned Integers}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Comparison Of Signed Integers}
%Section Tag: CSI0
\label{ccil0:scsi0}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Integer Addition}
%Section tag: IAD0
\label{ccil0:siad0}

Addition of two $m$-bit integers is a combinational function---that is,
the inputs uniquely determine the output.  Addition of binary 
numbers is performed 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Hardware Implementation Of Addition}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Addition Of Unsigned Operands}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Addition Of Signed Operands}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section {Integer Subtraction}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Hardware Implementation Of Subtraction}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Subtraction Of Unsigned Operands}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Subtraction Of Signed Operands}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Integer Multiplication}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Hardware Implementation Of Multiplication}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Multiplication Of Unsigned Operands}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Multiplication Of Signed Operands}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Integer Division}
\label{ccil0:sidv0}

\index{division}\index{integer division}In this section,
we discuss the best known methods of dividing integers using
typical microcontroller instruction sets.  In general, given
two arbitrary integers $p$ and $q$, we are interested in determining
their quotient $q=\lfloor{}p/q\rfloor$ and remainder
$r=p\bmod{}q$ as economically as possible.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Hardware Implementation Of Division}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{General Unsigned Division Without A Machine Division Instruction}
\label{ccil0:sidv0:sgdn0}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{General Unsigned Division With A Machine Division Instruction}
\label{ccil0:sidv0:sgdu0}

As mentioned many places in this work, efficiency in microcontroller software
involves phrasing computational problems in a way which makes good use of
the machine instruction set.  In Section \ref{ccil0:sidv0:sgdn0} we discussed
the classic shift-compare-subtract algorithm for division.  This algorithm
is far from efficient.  A reasonable question to ask is whether we can
leverage ``small'' division capability (provided by the machine instruction set)
to accomplish ``large'' divisions (those which we require in practice).
It ends up that this is possible:  the technique involved is effectively
to use machine division instructions to estimate the highest-order bits of 
the quotient based on the highest-order bits of the dividend and divisor.

Knuth's discussion of division 
algorithms \cite[pp. 270-275]{bibref:b:knuthclassic2ndedvol2} is the
basis for most of the material in this subsection.  However, Knuth has
a gift for terseness that is sometimes a curse for the reader, and so
we take more time than Knuth to explain certain results.

First, as a starting point, we present \emph{Algorithm D} from
Knuth \cite[pp. 272-273]{bibref:b:knuthclassic2ndedvol2}.  Then,
we justify the algorithm and explain why it is valid.  Finally,
we supply implementation advice for microcontroller instruction sets.

\begin{vworkalgorithmstatementpar}{Arbitrary Unsigned Division Using 
Machine Unsigned Division Instructions}
\label{alg:ccil0:sidv0:sgdu0:01}
(From Knuth \cite[pp. 272-273]{bibref:b:knuthclassic2ndedvol2})
Given nonnegative integers $u=(u_{m+n-1} \ldots{} u_1 u_0)_b$
and $v=(v_{n-1} \ldots{} v_1 v_0)_b$, where
$v_{n-1} \neq 0$ and $n > 1$, we form the radix-$b$ quotient
$\lfloor{}u/v\rfloor{} = (q_m q_{m-1} \ldots{} q_0)_b$ and
the remainder $u \bmod v = (r_{n-1} \ldots{} r_1 r_0)_b$.  When
$n=1$, the simpler algorithm of 
Subsection \ref{ccil0:sidv0:sldm0}
should be used. 

\begin{algblvl0}
\item \label{enumstep:alg:ccil0:sidv0:sgdu0:01:01}
      [Normalize.] Set $d \gets \lfloor{}b/(v_{n-1} + 1)\rfloor$.
      Then set $(u_{m+n} u_{m+n-1} \ldots{} u_1 u_0)_b$ equal to 
      $(u_{m+n-1} \ldots{} u_1 u_0)_b$ times $d$; similarly,
      set $(v_{n-1} \ldots{} v_1 v_0)_b$ equal to 
      $(v_{n-1} \ldots{} v_1 v_0)_b$ times $d$.  (Notice the introduction
      of a new digit position $u_{m+n}$ at the left of
      $u_{m+n-1}$; if $d=1$, all we need to do in this step is set
      $u_{m+n} \gets 0$.  On a binary computer it may be preferable
      to choose $d$ to be a power of 2 instead of using the value
      suggested here; any value of $d$ that results in
      $v_{n-1} \geq \lfloor{}b/2\rfloor$ will suffice.  See also
      exercise 37.)
\item \label{enumstep:alg:ccil0:sidv0:sgdu0:01:02}
      [Initialize $j$.]  Set $j \gets m$.  (The loop on $j$,
      steps 
      \ref{enumstep:alg:ccil0:sidv0:sgdu0:01:03} 
      through 
      \ref{enumstep:alg:ccil0:sidv0:sgdu0:01:07}, 
      will be essentially a division of 
      $(u_{j+n} \ldots{} u_{j+1} u_j)_b$ by $(v_{n-1} \ldots{} v_1 v_0)_b$ to
      get a single quotient digit $q_j$; see Figure \ref{fig:alg:ccil0:sidv0:sgdu0:01:01}.)

\begin{figure}
\centering
\includegraphics[width=4.6in]{c_cil0/kdfc01.eps}
\caption{Flowchart For Algorithm \ref{alg:ccil0:sidv0:sgdu0:01} (From \cite[p. 273]{bibref:b:knuthclassic2ndedvol2})}
\label{fig:alg:ccil0:sidv0:sgdu0:01:01}
\end{figure}

\item \label{enumstep:alg:ccil0:sidv0:sgdu0:01:03}
      [Calculate $\hat{q}$.]  Set
      $\hat{q} \gets \lfloor{}u_{j+n}b + u_{j+n-1})/v_{n-1}\rfloor$ and
      let $\hat{r}$ be the remainder, $(u_{j+n}b + u_{j+n-1}) \bmod v_{n-1}$.
      Now test if $\hat{q} = b$ or $\hat{q} v_{n-2} > b\hat{r} + u_{j+n-2}$;
      if so, decrease $\hat{q}$ by 1, increase $\hat{r}$ by $v_{n-1}$, and repeat
      this test if $\hat{r} < b$.  (The test of $v_{n-2}$ determines at high
      speed most of the cases in which the trial value $\hat{q}$ is one too large,
      and it eliminates \emph{all} cases where $\hat{q}$ is two too large;
      see exercises 19, 20, 21.)
\item \label{enumstep:alg:ccil0:sidv0:sgdu0:01:04}
      [Multiply and subtract.]  Replace $(u_{j+n} u_{j+n-1} \ldots{} u_j)_b$ by

      \begin{equation}
      \nonumber
      (u_{j+n} u_{j+n-1} \ldots{} u_j)_b - \hat{q} (0 v_{n-1} \ldots{} v_1 v_0)_b. 
      \end{equation}

      This computation consists of a simple multiplication by a one-place number,
      combined with a subtraction.  The digits $(u_{j+n}, u_{j+n-1}, \ldots{}, u_j)$
      should be kept positive; if the result of this step is actually negative, 
      $(u_{j+n} u_{j+n-1} \ldots{} u_j)_b$ should be left as the true
      value plus $b^{n+1}$, namely as the $b$'s complement of the true value, and 
      a ``borrow'' to the left should be remembered.
\item \label{enumstep:alg:ccil0:sidv0:sgdu0:01:05}
      [Test remainder.]  Set $q_j \gets \hat{q}$.  If the result of step 
      \ref{enumstep:alg:ccil0:sidv0:sgdu0:01:04} was negative, go to
      step \ref{enumstep:alg:ccil0:sidv0:sgdu0:01:06}; otherwise go on to
      step \ref{enumstep:alg:ccil0:sidv0:sgdu0:01:07}.
\item \label{enumstep:alg:ccil0:sidv0:sgdu0:01:06}
      [Add back.]  (The probability that this step is necessary is very small, on the 
      order of only $2/b$, as shown in exercise 21; test data to activate this step
      should therefore be specifically contrived when debugging.)  Decrease 
      $q_j$ by 1, and add $(0 v_{n-1} \ldots v_1 v_0)_b$ to
      $(u_{j+n} u_{j+n-1} \ldots{} u_{j+1} u_j)_b$.  (A carry will occur to the left of
      $u_{j+n}$, and it should be ignored since it cancels with the borrow that
      occured in step \ref{enumstep:alg:ccil0:sidv0:sgdu0:01:04}.) 
\item \label{enumstep:alg:ccil0:sidv0:sgdu0:01:07}
      [Loop on $j$.]  Decrease $j$ by one.  Now if $j \geq 0$, go back to step
      \ref{enumstep:alg:ccil0:sidv0:sgdu0:01:03}.
\item \label{enumstep:alg:ccil0:sidv0:sgdu0:01:08}
      [Unnormalize.]  Now $(q_m \ldots{} q_1 q_0)_b$ is the desired quotient, and
      the desired remainder may be obtained by dividing 
      $(u_{n-1} \ldots{} u_1 u_0)_b$ by $d$.
\end{algblvl0}
\end{vworkalgorithmstatementpar}
\vworkalgorithmfooter{}

The general idea of Algorithm \ref{alg:ccil0:sidv0:sgdu0:01} is that 
digits (machine words) of the quotient $q$ can be successively estimated 
based on the first digits of the dividend and divisor.  Knuth
\cite[p. 271]{bibref:b:knuthclassic2ndedvol2} explores the properties of
the digit estimate 

\begin{equation}
\label{eq:ccil0:sidv0:sgdu0:01}
\hat{q} = \min \left( {\left\lfloor{\frac{u_n b + u_{n-1}}{v_{n-1}}}\right\rfloor, b-1} \right).
\end{equation}

The first point to make about an estimate in the form of 
(\ref{eq:ccil0:sidv0:sgdu0:01}) is that it can only be accomplished
efficiently if the machine-native division instruction supports
overflow detection, since it is possible that
$(u_n b + u_{n-1})/v_{n-1} \geq b$, even if 
$u/v < b$, as is shown by the following example.

\begin{vworkexamplestatement}
\label{ex:ccil0:sidv0:sgdu0:01:01}
Assume that we wish to apply the estimate of $\hat{q}$ provided by 
(\ref{eq:ccil0:sidv0:sgdu0:01})
to $u=16,776,704$ and $v=65,535$.  Demonstrate that a machine division
overflow will occur when estimating the first digit, assuming a processor
that can divide a 16-bit dividend by an 8-bit divisor to produce an 8-bit
quotient.
\end{vworkexamplestatement}
\begin{vworkexampleparsection}{Solution}
Note that according to Knuth's intention, the word size on such a machine
is 8 bits.  Thus, $b=256$.  Note that $u/v = 255 + 255/256 < b = 256$, as
required by Knuth's precondition.  However, although $u/v < b$, 
$u = [255 \; 254 \; 0] [256^2 \; 256 \; 1]^T = [u_2 u_1 u_0] [b^2 b^1 b^0]^T$ and 
$v = [255 \; 255] [256 \; 1]^T = [v_1 v_0] [b^1 b^0]^T$, so that calculating
an estimate $\hat{q}$ as required by (\ref{eq:ccil0:sidv0:sgdu0:01}),
$(u_n b + u_{n-1})/v_{n-1} = 65,534/255 = 256 + 254/255 \geq b$, is a division
overflow for a single machine division instruction.  Thus, it follows that 
a machine with division overflow detection can quickly determine that $b-1$ from
(\ref{eq:ccil0:sidv0:sgdu0:01}) is the minimum, whereas a machine without 
division overflow
detection would have to use several additional machine instructions to make
this determination.
\end{vworkexampleparsection}
\vworkexamplefooter{}

The second thing to establish about $\hat{q}$ as defined by 
(\ref{eq:ccil0:sidv0:sgdu0:01}) is how ``good'' of an estimate 
$\hat{q}$ is---how much information, exactly, about $q$ can we
obtain by examining the first two words of $u$ and the first
word of $v$?

We first establish in the following lemma that our estimate of
$q$, $\hat{q}$, can be no less than $q$.

\begin{vworklemmastatementpar}{\mbox{\boldmath$\hat{q} \geq q$}}
\label{lem:ccil0:sidv0:sgdu0:01}
The estimate of $q$ provided by (\ref{eq:ccil0:sidv0:sgdu0:01}),
$\hat{q}$ is always at least as great as the actual value of 
$q$, i.e. $\hat{q} \geq q$.
\end{vworklemmastatementpar}
\begin{vworklemmaproof}
Knowledge of $u_{n}$, $u_{n-1}$, and $v_{n-1}$ necessarily confine
the intervals in which the actual values of $u$ and $v$ may be;
specifically:\footnote{In
(\ref{eq:lem:ccil0:sidv0:sgdu0:01:04})
and 
(\ref{eq:lem:ccil0:sidv0:sgdu0:01:07}),
we use statements of the form ``$x = x$'' as an idiom for
``$x$ is known''.}

\begin{eqnarray}
\label{eq:lem:ccil0:sidv0:sgdu0:01:01}
u & = & \sum_{i=0}^{n} u_i b^i   \\
\label{eq:lem:ccil0:sidv0:sgdu0:01:02}
  & = & u_n b^n + u_{n-1} b^{n-1} + \ldots{} + u_2 b^2 + u_1 b + u_0   \\
\label{eq:lem:ccil0:sidv0:sgdu0:01:03}
  & = & (u_n b + u_{n-1}) b^{n-1} + \ldots{} + u_2 b^2 + u_1 b + u_0
\end{eqnarray}

\begin{eqnarray}
\nonumber & (u_n = u_n \wedge u_{n-1} = u_{n-1}) & \\
\label{eq:lem:ccil0:sidv0:sgdu0:01:04}
& \vworkvimp & \\
\nonumber & (u_n b + u_{n-1}) b^{n-1} \leq u \leq (u_n b + u_{n-1}) b^{n-1} + b^{n-1} - 1 &
\end{eqnarray}

\begin{eqnarray}
\label{eq:lem:ccil0:sidv0:sgdu0:01:05}
v & = & \sum_{i=0}^{n-1} v_i b^i   \\
\label{eq:lem:ccil0:sidv0:sgdu0:01:06}
& = & v_{n-1} b^{n-1} + v_{n-2} b^{n-2} + \ldots{} + v_2 b^2 + v_1 b + v_0 
\end{eqnarray}

\begin{equation}
\label{eq:lem:ccil0:sidv0:sgdu0:01:07}
(v_{n-1} = v_{n-1})
\vworkhimp
v_{n-1} b^{n-1} \leq v \leq v_{n-1} b^{n-1} + b^{n-1} - 1 
\end{equation}

(\ref{eq:lem:ccil0:sidv0:sgdu0:01:04}) and
(\ref{eq:lem:ccil0:sidv0:sgdu0:01:07}) reflect the uncertainties in the 
values of $u$ and $v$ respectively because only the first digit(s) of
$u$ and $v$ are being considered in forming the estimate $\hat{q}$.

By definition, the actual value of $q$ is $\lfloor{}u/v\rfloor$.  For a 
rational function $f(u,v) = u/v$ where $u \in [u_{min}, u_{max}]$ and
$v \in [v_{min}, v_{max}]$, the minimum value of $u/v$ occurs at 
$u_{min}/v_{max}$, and the maximum value of $u/v$ occurs at
$u_{max}/v_{min}$.  We can therefore write that

\begin{equation}
\label{eq:lem:ccil0:sidv0:sgdu0:01:08}
\left\lfloor{\frac{(u_n b + u_{n-1}) b^{n-1}}{v_{n-1} b^{n-1} + b^{n-1} - 1}}\right\rfloor
\leq
q
\leq
\left\lfloor{\frac{(u_n b + u_{n-1}) b^{n-1} + b^{n-1} - 1}{v_{n-1} b^{n-1}}}\right\rfloor .
\end{equation} 

In other words, knowledge of $u_{n}$, $u_{n-1}$, and $v_{n-1}$ confines $q$ to the 
interval indicated in (\ref{eq:lem:ccil0:sidv0:sgdu0:01:08}).  We must prove that,
given a specific $u_{n}$, $u_{n-1}$, and $v_{n-1}$, $\hat{q}$ is at least as large as
the upper bound in (\ref{eq:lem:ccil0:sidv0:sgdu0:01:08}); otherwise we could find a
$q$ such that $q > \hat{q}$.  We can algebraically manipulate the upper bound in 
in (\ref{eq:lem:ccil0:sidv0:sgdu0:01:08}) to yield

\begin{equation}
\label{eq:lem:ccil0:sidv0:sgdu0:01:09}
\left\lfloor{\frac{(u_n b + u_{n-1}) b^{n-1}}{v_{n-1} b^{n-1} + b^{n-1} - 1}}\right\rfloor
\leq
q
\leq
\left\lfloor{\frac{u_n b + u_{n-1} + \frac{b^{n-1}-1}{b^{n-1}}}{v_{n-1}}}\right\rfloor .
\end{equation} 

In (\ref{eq:lem:ccil0:sidv0:sgdu0:01:09}), since $(b^{n-1}-1)/b^{n-1} < 1$ and since
$u_n b + u_{n-1}$ is an integer, we can conclude that
$\lfloor u_n b + u_{n-1} + (b^{n-1}-1)/b^{n-1} \rfloor = \lfloor u_n b + u_{n-1} \rfloor$
and hence that

\begin{equation}
\label{eq:lem:ccil0:sidv0:sgdu0:01:10}
q
\leq
\left\lfloor{\frac{u_n b + u_{n-1} + \frac{b^{n-1}-1}{b^{n-1}}}{v_{n-1}}}\right\rfloor 
=
\left\lfloor{\frac{u_n b + u_{n-1}}{v_{n-1}}}\right\rfloor 
=
\hat{q} .
\end{equation} 

Therefore, $\hat{q} \geq q$.
\end{vworklemmaproof}
\vworklemmafooter{}

Lemma \ref{lem:ccil0:sidv0:sgdu0:01} establishes that 
a digit estimate $\hat{q}$ based on the first digit of the
divisor $v$ can be no less than the actual digit $q$, i.e.
$\hat{q}-q \geq 0$.  However, we must also establish an upper bound
on $\hat{q}-q$.

Intuitively, based on
(\ref{eq:lem:ccil0:sidv0:sgdu0:01:06}), we might guess that
if $v_{n-1}$ is small, the estimate $\hat{q}$ may be quite
poor, as the interval to which the actual value of $v$ is confined
may be quite large.  This fact is the basis for the normalization
step [\ref{enumstep:alg:ccil0:sidv0:sgdu0:01:01}] in Algorithm
\ref{alg:ccil0:sidv0:sgdu0:01}.  We now prove a useful result
for how much $u, v$ must be normalized so that $\hat{q}-q \leq 2$.

\begin{vworklemmastatementpar}{Normalization Requirement So That 
                               \mbox{\boldmath$\hat{q} - q \leq 2$}}
\label{lem:ccil0:sidv0:sgdu0:02}
If $v_{n-1} \geq \lfloor b/2 \rfloor$ and $\hat{q}$ is chosen as
indicated in (\ref{eq:ccil0:sidv0:sgdu0:01}), then 
$0 \leq \hat{q} - q \leq 2$.
\end{vworklemmastatementpar}
\begin{vworklemmaproof}
The lower limit on $\hat{q} - q$ is proved in Lemma \ref{lem:ccil0:sidv0:sgdu0:01}.
We now seek only to prove that $\hat{q} - q \leq 2$.
By definition of $\hat{q}$ and $q$, 

\begin{equation}
\label{eq:lem:ccil0:sidv0:sgdu0:02:01}
\hat{q} - q  =    \left\lfloor {\frac{u_n b + u_{n-1}}{v_{n-1}}} \right\rfloor 
                  - \left\lfloor {\frac{u}{v}} \right\rfloor 
\end{equation}

When only nonnegative integers are involved, 
(\cmtnzeroxrefhyphen\ref{eq:cmtn0:sfcf0:02}) 
supplies an exact expression for the floor of a 
ratio of integers.  Using (\cmtnzeroxrefhyphen\ref{eq:cmtn0:sfcf0:02}),
(\ref{eq:lem:ccil0:sidv0:sgdu0:02:01}) can be decomposed into

\begin{equation}
\label{eq:lem:ccil0:sidv0:sgdu0:02:02}
\hat{q} - q  =    \frac{u_n b + u_{n-1}}{v_{n-1}}
                - \frac{(u_n b + u_{n-1}) \bmod v_{n-1}}{v_{n-1}}
                - \frac{u}{v}
                + \frac{u \bmod v}{v} . 
\end{equation}

\noindent{}Note that (\ref{eq:lem:ccil0:sidv0:sgdu0:02:02}) is an exact 
expression (rather than an
inequality).

Note in (\ref{eq:lem:ccil0:sidv0:sgdu0:02:02}) that
$(u_n b + u_{n-1}) \bmod v_{n-1} \in [0, v_{n-1}-1]$, and that in general
there is no reason to expect it cannot be zero.  Thus, we can assume that
it \emph{is} zero, which will maximize $\hat{q}-q$.  We can thus convert
(\ref{eq:lem:ccil0:sidv0:sgdu0:02:02}) into the inequality

\begin{equation}
\label{eq:lem:ccil0:sidv0:sgdu0:02:03}
\hat{q} - q  \leq \frac{u_n b + u_{n-1}}{v_{n-1}}
                - \frac{u}{v}
                + \frac{u \bmod v}{v} . 
\end{equation}

In (\ref{eq:lem:ccil0:sidv0:sgdu0:02:03}) we can also observe that
$(u \bmod v)/v \in [0, (v-1)/v]$.  If we replace this expression with 
``1'' (which is unattainable, but barely), this will change the relational
operator from ``$\leq$'' to ``$<$'':

\begin{equation}
\label{eq:lem:ccil0:sidv0:sgdu0:02:04}
\hat{q} - q  <    \frac{u_n b + u_{n-1}}{v_{n-1}}
                - \frac{u}{v}
                + 1 . 
\end{equation}

The result we wish to show is that with $v_{n-1} \geq \lfloor b/2 \rfloor$,
$\hat{q}-q \leq 2$.  To simplify the subsequent algebraic manipulations, note in 
(\ref{eq:lem:ccil0:sidv0:sgdu0:02:04}) that

\begin{eqnarray}
\label{eq:lem:ccil0:sidv0:sgdu0:02:05}
          & \hat{q} - q  \leq 2 &  \\    
\nonumber & \vworkvertequiv     &  \\
\label{eq:lem:ccil0:sidv0:sgdu0:02:06}
          & \displaystyle \frac{u_n b + u_{n-1}}{v_{n-1}}
                - \frac{u}{v}
                + 1 \leq 3 &          \\
\nonumber & \vworkvertequiv     &  \\
\label{eq:lem:ccil0:sidv0:sgdu0:02:07}
          & \displaystyle \frac{u_n b + u_{n-1}}{v_{n-1}}
                - \frac{u}{v} \leq 2    &
\end{eqnarray}

(\ref{eq:lem:ccil0:sidv0:sgdu0:02:06}) may be counterintuitive, so
further explanation is offered here.  Since $\hat{q} \in \vworkintset$ and $q \in \vworkintset$,
$\hat{q}-q \in \vworkintset$.  Thus, proving 
(\ref{eq:lem:ccil0:sidv0:sgdu0:02:06}) or
(\ref{eq:lem:ccil0:sidv0:sgdu0:02:07}) proves that
$\hat{q}-q \in \{ \ldots, -1, 0, 1, 2 \}$ (however, by 
Lemma \ref{lem:ccil0:sidv0:sgdu0:01}, $\hat{q}-q \geq 0$, so in fact
what would be proved is that $\hat{q}-q \in \{ 0, 1, 2 \}$).  For 
algebraic simplicity,
we choose to prove (\ref{eq:lem:ccil0:sidv0:sgdu0:02:07}).

First, adjust numerator and denominator of the first term in 
(\ref{eq:lem:ccil0:sidv0:sgdu0:02:07}) by $b^{n-1}$ so that the terms more closely 
resemble $u$ and $v$ in 
(\ref{eq:lem:ccil0:sidv0:sgdu0:01:02}) 
and 
(\ref{eq:lem:ccil0:sidv0:sgdu0:01:06}):

\begin{equation}
\label{eq:lem:ccil0:sidv0:sgdu0:02:08}
\frac{u_n b^n + u_{n-1} b^{n-1}}{v_{n-1} b^{n-1}}
                - \frac{u}{v} \leq 2 .
\end{equation}

For logical implication to be maintained,
we must make the most pessimistic choices and assumptions possible in 
(\ref{eq:lem:ccil0:sidv0:sgdu0:02:08}) in order to maximize the value
of the left side of the inequality.
The first assumption to be made is the error in estimating
$u$ and $v$ based on their most significant digits.  It can be
seen that (\ref{eq:lem:ccil0:sidv0:sgdu0:02:08}) will be maximized if:

\begin{itemize}
\item We assume that $u = u_{n} b^n + u_{n-1} b^{n-1}$ (i.e. that we estimate
      $u$ precisely).
\item We assume that $v = v_{n-1} b^{n-1} + b^{n-1} - 1$ (i.e. that
      we underestimate $v$ by the maximum amount possible).
\item We minimize the value of $v_{n-1} b^{n-1}$.
\end{itemize}

Assuming that $u$ is estimated precisely yields

\begin{equation}
\label{eq:lem:ccil0:sidv0:sgdu0:02:09}
\frac{u}{v_{n-1} b^{n-1}}
                - \frac{u}{v} \leq 2 .
\end{equation}

Assuming that $v$ is underestimated by the maximum amount possible
yields

\begin{equation}
\label{eq:lem:ccil0:sidv0:sgdu0:02:10}
\frac{u}{v - b^{n-1} + 1}
                - \frac{u}{v} \leq 2 .
\end{equation}

Finally, with $b$ and $v$ fixed, $u$ can be maximized by noting that 
$u \leq bv - 1$ (by the problem assumption that the quotient is a single digit).
However, for algebraic simplicity, we make the substitution $u=bv$ (rather than 
$u=bv-1$), since the weaker upper bound is strong enough to prove the 
first result we seek.

\begin{equation}
\label{eq:lem:ccil0:sidv0:sgdu0:02:11}
\frac{bv}{v - b^{n-1} + 1}
                - \frac{bv}{v} \leq 2
\end{equation}

\begin{equation}
\label{eq:lem:ccil0:sidv0:sgdu0:02:12}
\frac{bv}{v - b^{n-1} + 1}
                - b \leq 2
\end{equation}

Solving (\ref{eq:lem:ccil0:sidv0:sgdu0:02:12})
for $v$ yields

\begin{equation}
\label{eq:lem:ccil0:sidv0:sgdu0:02:13}
v \geq \frac{b^n}{2} + b^{n-1} - \frac{1}{b} - 1
\end{equation}

Again using the assumption that $v$ is underestimated by the maximum amount
possible, we may make the substitution that $v = v_{n-1} b^{n-1} + b^{n-1} -1$,
leading to

\begin{equation}
\label{eq:lem:ccil0:sidv0:sgdu0:02:13b}
v_{n-1} \geq \frac{b}{2} - \frac{1}{2 b^{n-2}} .
\end{equation}

There are two cases to consider:  $b$ even and $b$ odd.  If $b$ is even, the
proof is complete, as $\lfloor b/2 \rfloor = b/2$ and the choice of 
$v_{n-1} = \lfloor b/2 \rfloor$ will automatically satisfy
(\ref{eq:lem:ccil0:sidv0:sgdu0:02:13b}).  However, if $b$ is odd, 
$\lfloor b/2 \rfloor = b/2 - 1/2 < b/2 - 1/2b^{n-2}$, violating
(\ref{eq:lem:ccil0:sidv0:sgdu0:02:13b}),
and so we need to
further examine this case.

If $b$ is odd and $v_{n-1} = \lfloor b/2 \rfloor$, then 
$v_{n-1} = b/2 - 1/2$, violating (\ref{eq:lem:ccil0:sidv0:sgdu0:02:13b}).
However, any larger choice of $v_{n-1}$ (such as
$\lfloor b/2 \rfloor + 1$, $\lfloor b/2 \rfloor + 2$, etc.) satisfies
(\ref{eq:lem:ccil0:sidv0:sgdu0:02:13b}); so that it remains only to prove
the $v_{n-1} = \lfloor b/2 \rfloor = b/2 - 1/2$
case.

If $v_{n-1} = \lfloor b/2 \rfloor = b/2 - 1/2$, then

\begin{eqnarray}
\label{eq:lem:ccil0:sidv0:sgdu0:02:14}
v & \in & \left[ 
\left( \frac{b}{2} - \frac{1}{2}\right) b^{n-1},
\left( \frac{b}{2} - \frac{1}{2}\right) b^{n-1} + b^{n-1} - 1
\right] \\
\nonumber & = &
\left[
\frac{b^n}{2} - \frac{b^{n-1}}{2},
\frac{b^n}{2} + \frac{b^{n-1}}{2} -1
\right] .
\end{eqnarray}

Note in this case that the estimation error ($v - v_{n-1}b^{n-1}$) and the
value of $v$ are not independent; and in fact it is this aspect
of the problem that has led to the violation of 
(\ref{eq:lem:ccil0:sidv0:sgdu0:02:13b}) with $b$ odd and 
$v_{n-1} = \lfloor b/2 \rfloor$.

In order to prove the case of $b$ odd and $v = \lfloor b/2 \rfloor = b/2 - 1/2$, 
we must reexamine some simplifying assumptions made earlier in order to obtain
tighter inequalities.  In (\ref{eq:lem:ccil0:sidv0:sgdu0:02:02}), we can no
longer accept the maximum of $(u \bmod v)/v$ as one; instead we construct the 
tighter inequality

\begin{eqnarray}
\label{eq:lem:ccil0:sidv0:sgdu0:02:15}
& \displaystyle \hat{q} - q \leq  \frac{u_n b + u_{n-1}}{v_{n-1}}
                - \frac{u}{v}
                + \frac{u \bmod v}{v} & \\
\nonumber &  \vworkvimp & \\
\label{eq:lem:ccil0:sidv0:sgdu0:02:16}
& \displaystyle \hat{q} - q \leq  \frac{u_n b + u_{n-1}}{v_{n-1}}
                - \frac{u}{v}
                + \frac{v-1}{v} , &
\end{eqnarray}

which leads to

\begin{equation}
\label{eq:lem:ccil0:sidv0:sgdu0:02:17}
\frac{u_n b + u_{n-1}}{v_{n-1}}
                - \frac{u+1}{v}
                < 2 .
\end{equation}

In order to maximize the left-hand side of
(\ref{eq:lem:ccil0:sidv0:sgdu0:02:17}), we assume that we
estimate $u$ exactly so that $u = u_n b^n + u_{n-1} b^{n-1}$,
yielding

\begin{equation}
\label{eq:lem:ccil0:sidv0:sgdu0:02:18}
\frac{u}{v_{n-1} b^{n-1}}
                - \frac{u+1}{v}
                < 2 .
\end{equation}

We also assume that $u$ is the maximum value
possible, $u=bv-1$, leading to

\begin{equation}
\label{eq:lem:ccil0:sidv0:sgdu0:02:19}
\frac{bv-1}{v_{n-1} b^{n-1}}
                - b
                < 2 .
\end{equation}

Finally, we assume that $v$ is the upper limit in
(\ref{eq:lem:ccil0:sidv0:sgdu0:02:14}),
$v=b^n/2 + b^{n-1}/2 - 1$, and substitute the known value of
$v_{n-1}$ for the case being proved, $v_{n-1} = b/2-1/2$, yielding

\begin{equation}
\label{eq:lem:ccil0:sidv0:sgdu0:02:20}
\frac{b \left( \frac{b^n}{2} + \frac{b^{n-1}}{2} - 1 \right) - 1}
{\left( \frac{b}{2} - \frac{1}{2} \right) b^{n-1}}
                - b
                < 2 .
\end{equation}
 
Simplification of (\ref{eq:lem:ccil0:sidv0:sgdu0:02:20})
will establish that it is always true.  This completes the proof.
\end{vworklemmaproof}
\vworklemmafooter{}

Lemmas \ref{lem:ccil0:sidv0:sgdu0:01} and
\ref{lem:ccil0:sidv0:sgdu0:02}, 
standing alone, lead to a good implementation of 
division without any further results.  If it is known that
$0 \leq \hat{q} - q \leq 2$, Algorithm \ref{alg:ccil0:sidv0:sgdu0:01}
can be trivially modified to only calculate
$\hat{q}$ (omitting the additional tests in Step \ref{enumstep:alg:ccil0:sidv0:sgdu0:01:03}), 
and then
to include up to two add-back steps
(duplication of Step \ref{enumstep:alg:ccil0:sidv0:sgdu0:01:06}).  
Although such an algorithm would be 
satisfactory, it has the disadvantage that the add-back steps would
be executed very frequently, slowing the algorithm substantially, especially
for long operands.
We now show that the additional tests in Step \ref{enumstep:alg:ccil0:sidv0:sgdu0:01:03} of 
Algorithm \ref{alg:ccil0:sidv0:sgdu0:01} can eliminate 
altogether the case of $\hat{q}-q = 2$ (Lemma \ref{lem:ccil0:sidv0:sgdu0:03}), and 
can with a probability close to unity eliminate the
case of $\hat{q}-q = 1$ (Lemmas \ref{lem:ccil0:sidv0:sgdu0:04} 
and \ref{lem:ccil0:sidv0:sgdu0:05}).  Together these tests, which are present in 
the statement of Algorithm \ref{alg:ccil0:sidv0:sgdu0:01},
reduce add-back (Step \ref{enumstep:alg:ccil0:sidv0:sgdu0:01:06}) to rare occurrence, and create a more
efficient algorithm than would be possible with the
results of Lemmas \ref{lem:ccil0:sidv0:sgdu0:01} and \ref{lem:ccil0:sidv0:sgdu0:02} alone.

\begin{vworklemmastatementpar}
{\mbox{\boldmath$\hat{q} v_{n-2} \leq b \hat{r} + u_{j+n-2} \vworkhimp 0 \leq \hat{q} - q \leq 1$}}
\label{lem:ccil0:sidv0:sgdu0:03}
If the divisor normalization requirement ($v_{n-1} \geq \lfloor b/2 \rfloor$) as specified in
Step \ref{enumstep:alg:ccil0:sidv0:sgdu0:01:01} of
Algorithm \ref{alg:ccil0:sidv0:sgdu0:01} is met, then

\begin{equation}
\label{eq:lem:ccil0:sidv0:sgdu0:03:01}
\hat{q} v_{n-2} \leq b \hat{r} + u_{j+n-2} \vworkhimp 0 \leq \hat{q} - q \leq 1 .
\end{equation}
\end{vworklemmastatementpar}
\begin{vworklemmaproof}
For reference, note that:

\begin{eqnarray}
\label{eq:lem:ccil0:sidv0:sgdu0:03:02}
u & = & u_{j+n} b^{j+n} + u_{j+n-1} b^{j+n-1} + \ldots{} + u_1 b + u_0 \\
\label{eq:lem:ccil0:sidv0:sgdu0:03:03}
v & = & v_{n-1} b^{n-1} + v_{n-2} b^{n-2} + \ldots{} + v_1 b + v_0
\end{eqnarray}

By definition, we the remainder
$\hat{r}$ has the value
$\hat{r} = u_{j+n} b + u_{j+n-1} - \hat{q} v_{n-1}$.  Substituting this value
into (\ref{eq:lem:ccil0:sidv0:sgdu0:03:01}) produces

\begin{equation}
\label{eq:lem:ccil0:sidv0:sgdu0:03:04}
\hat{q} v_{n-2} \leq b (u_{j+n} b + u_{j+n-1} - \hat{q} v_{n-1}) + u_{j+n-2} ,
\end{equation}

and solving for $\hat{q}$ yields

\begin{equation}
\label{eq:lem:ccil0:sidv0:sgdu0:03:05}
\hat{q} \leq  \frac{u_{j+n} b^2 + u_{j+n-1}b + u_{j+n-2}}{v_{n-1}b + v_{n-2}}.
\end{equation}

It is known from Lemma \ref{lem:ccil0:sidv0:sgdu0:01} that the type of estimate
represented by the floor of the right-hand size of (\ref{eq:lem:ccil0:sidv0:sgdu0:03:05})
can be no less than $q$, leading to

\begin{eqnarray}
\label{eq:lem:ccil0:sidv0:sgdu0:03:06}
& \displaystyle q  \leq  \hat{q}
\leq
\left\lfloor { \frac{u_{j+n} b^2 + u_{j+n-1}b + u_{j+n-2}}{v_{n-1}b + v_{n-2}} } \right\rfloor & \\
\nonumber & \displaystyle \leq  
\frac{u_{j+n} b^2 + u_{j+n-1}b + u_{j+n-2}}{v_{n-1}b + v_{n-2}}. &
\end{eqnarray}

Because $q, \hat{q} \in \vworkintset$, it is only necessary to prove that

\begin{equation}
\label{eq:lem:ccil0:sidv0:sgdu0:03:07}
\frac{u_{j+n} b^2 + u_{j+n-1}b + u_{j+n-2}}{v_{n-1}b + v_{n-2}} -
\left\lfloor \frac{u}{v} \right\rfloor
< 2
\end{equation}

in order to prove that $\hat{q}-q \leq 1$.  Using
(\cmtnzeroxrefhyphen\ref{eq:cmtn0:sfcf0:02}), 
(\ref{eq:lem:ccil0:sidv0:sgdu0:03:07}) can be rewritten as

\begin{equation}
\label{eq:lem:ccil0:sidv0:sgdu0:03:08}
\frac{u_{j+n} b^2 + u_{j+n-1}b + u_{j+n-2}}{v_{n-1}b + v_{n-2}} -
\frac{u}{v} -
\frac{u \bmod v}{v}
< 2 .
\end{equation}

In order for implication to hold, we must make the most pessimistic
assumptions about $u \bmod v$ (those which maximize it).  The maximum value
of $u \bmod v$ is $v-1$, leading to

\begin{equation}
\label{eq:lem:ccil0:sidv0:sgdu0:03:09}
\frac{u_{j+n} b^2 + u_{j+n-1}b + u_{j+n-2}}{v_{n-1}b + v_{n-2}} -
\frac{u + 1}{v}
< 1 .
\end{equation}

In order to maximize the left side of (\ref{}),
we must assume that $u$ is maximized, $v$ is minimized, 


\end{vworklemmaproof}
\vworklemmafooter{}

\begin{vworklemmastatementpar}
{\mbox{\boldmath$\hat{q} v_{n-2} > b \hat{r} + u_{n-2} \vworkhimp q < \hat{q}$}}
\label{lem:ccil0:sidv0:sgdu0:04}
Given $\hat{q} > 0$, an estimate of $q$, and the remainder
based on the estimate, $\hat{r} = u_n b + u_{n-1} - \hat{q} v_{n-1}$,

\begin{equation}
\label{eq:lem:ccil0:sidv0:sgdu0:04:01}
\hat{q} v_{n-2} > b \hat{r} + u_{n-2} \vworkhimp \hat{q} > q .
\end{equation}
\end{vworklemmastatementpar}
\begin{vworklemmaproof}
We make the assumption that $v_{n-1}$ and $v_{n-2}$ are not both 0.
$v_{n-1} > 0$ is guaranteed by
the  normalization of 
$v$ in Algorithm \ref{alg:ccil0:sidv0:sgdu0:01}.

\begin{equation}
\label{eq:lem:ccil0:sidv0:sgdu0:04:02}
\hat{q} v_{n-2} > b \hat{r} + u_{n-2}
\end{equation}

\begin{equation}
\label{eq:lem:ccil0:sidv0:sgdu0:04:03}
\hat{q} v_{n-2} > b (u_n b + u_{n-1} - \hat{q} v_{n-1}) + u_{n-2}
\end{equation}

Solving (\ref{eq:lem:ccil0:sidv0:sgdu0:04:03}) for $\hat{q}$ yields

\begin{equation}
\label{eq:lem:ccil0:sidv0:sgdu0:04:04}
\hat{q} 
>
\frac{u_n b^2 + u_{n-1} b + u_{n-2}}{v_{n-1} b + v_{n-2}}
\geq
\left\lfloor {\frac{u_n b^2 + u_{n-1} b + u_{n-2}}{v_{n-1} b + v_{n-2}}} \right\rfloor
.
\end{equation}

Note that the right-hand term of 
(\ref{eq:lem:ccil0:sidv0:sgdu0:04:04})
is similar in form to the estimate $\hat{q}$ in
Lemma \ref{lem:ccil0:sidv0:sgdu0:01}, where it is proved that
$\hat{q} \geq q$.  It is possible to use identical algebraic technique
as is used in Lemma \ref{lem:ccil0:sidv0:sgdu0:01} in order to prove that

\begin{equation}
\label{eq:lem:ccil0:sidv0:sgdu0:04:05}
\left\lfloor {\frac{u_n b^2 + u_{n-1} b + u_{n-2}}{v_{n-1} b + v_{n-2}}} \right\rfloor
\geq q,
\end{equation}

and it follows that

\begin{equation}
\label{eq:lem:ccil0:sidv0:sgdu0:04:06}
\hat{q} 
>
\frac{u_n b^2 + u_{n-1} b + u_{n-2}}{v_{n-1} b + v_{n-2}}
\geq
\left\lfloor {\frac{u_n b^2 + u_{n-1} b + u_{n-2}}{v_{n-1} b + v_{n-2}}} \right\rfloor
\geq q,
\end{equation}

and thus $\hat{q} > q$.
\end{vworklemmaproof}
\vworklemmafooter{}

\begin{vworklemmastatementpar}
{Add-back occurs with approximate probability \mbox{\boldmath$2/b$}}
\label{lem:ccil0:sidv0:sgdu0:05}
The estimate of $q$ provided by (\ref{eq:ccil0:sidv0:sgdu0:01}),
\end{vworklemmastatementpar}
\begin{vworklemmaproof}
\end{vworklemmaproof}
\vworklemmafooter{}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Division Of Signed Operands}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Large Dividends With Machine-Native Divisors}
\label{ccil0:sidv0:sldm0}

Division of arbitrary-sized operands (Section \ref{ccil0:sidv0:sgdu0}) is
a costly operation.  In many practical applications, we are able to exploit
data sizes of operands or special relationships between the values of
operands to use the instruction set of the machine more effectively.
In this subsection, we investigate what optimizations we may achieve when:

\begin{itemize}
\item We wish to calculate the quotient and remainder of
      unsigned integers $p$ and $q$:  $p/q$ and 
      $p \bmod{} q$; \emph{and}
\item The machine possesses unsigned division instructions
      which provide both a quotient and a remainder from 
      a division; \emph{and}
\item The bitsize of the divisor $q$ is not larger than can
      be accomodated (as a divisor) by machine division instructions.
\end{itemize}

Processors which possess integer division instructions usually
possess one of two types of instructions:

\begin{itemize}
\item Instructions where the the divisor, quotient and remainder are
      $Q$ bits, but the dividend is $2Q$ bits (we call these
      ``large dividend'' instructions).  For example, an
      instruction which accepts a 16-bit dividend and an
      8-bit divisor to produce an 8-bit quotient and an 8-bit remainder is
      typical.
      With such instructions, overflow is possible, and is always detectable.
      However, in this subsection we never describe algorithms which detect
      overflow---instead, we arrange for data values which cannot generate an
      overflow.
\item Instructions where the dividend, divisor, quotient, and remainder
      are all $Q$ bits (we call these ``small dividend'' instructions).  
      With such instructions, overflow is not possible.
\end{itemize}

We call the bitsize $Q$ a \emph{chunk}.  We use \emph{chunk} rather than
\emph{word} because the chunksize and wordsize in general are not
required to be the same.

For the remainder of this discussion, we assume large dividend 
instructions (the first category above).
The algorithms developed can be implemented on small dividend machines
by halving data sizes so that the divisor fills no more than half
of the available bits.

We assume that we are interested in calculating the integer quotient 
$\lfloor{}p/q\rfloor$ and remainder $p \bmod{} q$ of two unsigned
integers $p$ and $q$, where $p$ is of size $P$ bits and $q$ is
of size $Q$ bits.  For simplicity and without detracting from the
generality of the solution, we assume that $Q \vworkdivides{} P$.

We then seek to calculate

\begin{eqnarray}
\label{eq:ccil0:sidv0:sldm0:001}
\frac{p}{q} & = & \frac{2^{P-Q} p_{[P/Q-1]} + 2^{P-2Q} p_{[P/Q-2]} + \ldots{} + 2^{Q} p_{[1]} + p_{[0]}}{q_{[0]}} \\
\nonumber       & = & \frac{\sum_{i=0}^{P/Q-1} 2^{iQ} p_{[i]}}{q_{[0]}} .
\end{eqnarray}

\noindent{}Using the integer identity

\begin{equation}
\label{eq:ccil0:sidv0:sldm0:002}
\frac{a}{b} = \left\lfloor{\frac{a}{b}}\right\rfloor + \frac{a \bmod b}{b} ,
\end{equation}

\noindent{}we can reform (\ref{eq:ccil0:sidv0:sldm0:001}) into

\begin{eqnarray}
\nonumber
\frac{p}{q} & = &   2^{P-Q} \left\lfloor{\frac{p_{[P/Q-1]}}{q_{[0]}}}\right\rfloor \\
\label{eq:ccil0:sidv0:sldm0:003}
            & + &   2^{P-Q} \frac{p_{[P/Q-1]}\bmod q_{[0]}}{q_{[0]}}
                  + 2^{P-2Q} \frac{p_{[P/Q-2]}}{q_{[0]}}  \\
\nonumber   & + &   \frac{\sum_{i=0}^{P/Q-3} 2^{iQ} p_{[i]}}{q_{[0]}} ,
\end{eqnarray}

\noindent{}which can be polished slightly to yield

\begin{eqnarray}
\nonumber
\frac{p}{q} & = &   2^{P-Q} \left\lfloor{\frac{p_{[P/Q-1]}}{q_{[0]}}}\right\rfloor \\
\label{eq:ccil0:sidv0:sldm0:004}
            & + &   2^{P-2Q} \frac{2^Q (p_{[P/Q-1]}\bmod q_{[0]}) + p_{[P/Q-2]}}{q_{[0]}} \\
\nonumber   & + &   \frac{\sum_{i=0}^{P/Q-3} 2^{iQ} p_{[i]}}{q_{[0]}} .
\end{eqnarray}

Note in (\ref{eq:ccil0:sidv0:sldm0:004}) that the first term, 
$\lfloor{}p_{[P/Q-1]} / q_{[0]}\rfloor$, as well as
a portion of the second term, $p_{[P/Q-1]}\bmod q_{[0]}$, can be 
calculated using a single machine division instruction with
$p_{[P/Q-1]}$ as the dividend and $q_{[0]}$ as the divisor.
Note also that multiplication of an integer by a power of 2
can be achieved by placing the integer correctly within the 
result.  In this regard note that $Q=8$ or $Q=16$ are
the most typical cases, and so the placement can be achieved simply
by selecting the correct memory address.

It is initially unclear whether we can evaluate or reduce the fraction in the 
second term of (\ref{eq:ccil0:sidv0:sldm0:004}),
$[2^Q (p_{[P/Q-1]}\bmod q_{[0]}) + p_{[P/Q-2]}] / q_{[0]}$,
using a single large dividend machine instruction, because
the upper chunk of the dividend is populated with non-zero bits
(specifically, $p_{[P/Q-1]}\bmod q_{[0]}$), and it seems that 
a division overflow may be possible.  However, with some thought,
it is clear that $p_{[P/Q-1]}\bmod q_{[0]} \leq q_{[0]} - 1$ and 
$p_{[P/Q-2]} \leq 2^Q - 1$, thus the largest numerator possible
is $2^Q q_{[0]} - 1$, which, when divided by $q_{[0]}$, will result
in a quotient and remainder of $2^Q - 1$.  Thus, no division overflow
can occur, and the fraction in the  
second term of (\ref{eq:ccil0:sidv0:sldm0:004}) can be evaluated
using a large divisor integer machine instruction.

The fraction in the 
second term of (\ref{eq:ccil0:sidv0:sldm0:004}) can be simplified 
using (\ref{eq:ccil0:sidv0:sldm0:002}) to yield:

\begin{eqnarray}
\nonumber
\frac{p}{q} & = &   2^{P-Q} \left\lfloor{\frac{p_{[P/Q-1]}}{q_{[0]}}}\right\rfloor \\
\label{eq:ccil0:sidv0:sldm0:005}
            & + &   2^{P-2Q} \left\lfloor{\frac{2^Q (p_{[P/Q-1]}\bmod q_{[0]}) + p_{[P/Q-2]}}{q_{[0]}}}\right\rfloor \\
\nonumber   & + &   2^{P-2Q} \frac{(2^Q (p_{[P/Q-1]}\bmod q_{[0]}) + p_{[P/Q-2]}) \bmod q_{[0]}}{q_{[0]}} \\
\nonumber   & + &   \frac{\sum_{i=0}^{P/Q-3} 2^{iQ} p_{[i]}}{q_{[0]}} .
\end{eqnarray}

The process of combining adjacent terms can be continued until all
divisions and modulo operations necessary can be carried out using
long dividend division instructions.  If we envision a 
long-dividend division instruction as a functional block that
accepts a $2Q$-bit dividend and a $Q$-bit divisor to produce a
$Q$-bit quotient and a $Q$-bit remainder
(Figure \ref{fig:ccil0:sidv0:sldm0:00}), then we can draw the
entire division as outlined by (\ref{eq:ccil0:sidv0:sldm0:005})
as shown in Figure \ref{fig:ccil0:sidv0:sldm0:01}.

\begin{figure}
\centering
\includegraphics[width=4.6in]{c_cil0/lddvblk.eps}
\caption{Long Dividend Division Machine Instruction As A Functional Block}
\label{fig:ccil0:sidv0:sldm0:00}
\end{figure}

\begin{figure}
\centering
\includegraphics[width=4.6in]{c_cil0/ldmnblk.eps}
\caption{Long Dividend/Machine-Native Divisor Division In Functional Block Form}
\label{fig:ccil0:sidv0:sldm0:01}
\end{figure}

The following example illustrates how to apply the technique.

\begin{vworkexamplestatement}
\label{ex:ccil0:sidv0:sldm0:01}
Implement 32/8 unsigned division on the TMS370C8 processor, which is
characterized by a 16/8 division instruction.
\end{vworkexamplestatement}
\begin{vworkexampleparsection}{Solution}
It would be possible to prepare an implementation directly from
Figure \ref{fig:ccil0:sidv0:sldm0:01}:  however, it may be 
more instructive to work through a solution without the
aid of this figure.

In the case of the TMS370C8, the chunk size $Q$ is 8 bits; therefore
$Q=8$.  The problem statement indicates that we must accept 32-bit dividends;
therefore $P=32$.  Thus

\begin{equation}
\label{eq:ex:ccil0:sidv0:sldm0:01:001}
p = 2^{24} p_{[3]} + 2^{16} p_{[2]} + 2^{8} p_{[1]} + p_{[0]}
\end{equation}

\noindent{}and

\begin{equation}
\label{eq:ex:ccil0:sidv0:sldm0:01:002}
q = q_{[0]} .
\end{equation}

\noindent{}Thus the quotient and remainder we would like to determine,
$\lfloor p/q \rfloor$ and $p \bmod q$, can be obtained by repeated
application of (\ref{eq:ccil0:sidv0:sldm0:002}) as shown
in Equations (\ref{eq:ex:ccil0:sidv0:sldm0:01:003}) 
through (\ref{eq:ex:ccil0:sidv0:sldm0:01:011}).

\begin{equation}
\label{eq:ex:ccil0:sidv0:sldm0:01:003}
\frac{p}{q} 
=
\frac{2^{24} p_{[3]} + 2^{16} p_{[2]} + 2^{8} p_{[1]} + p_{[0]}}{q_{[0]}}
\end{equation}

\begin{equation}
\label{eq:ex:ccil0:sidv0:sldm0:01:004}
\frac{p}{q} 
=
2^{24} \frac{p_{[3]}}{q_{[0]}}
+
2^{16} \frac{p_{[2]}}{q_{[0]}}
+
2^{8} \frac{p_{[1]}}{q_{[0]}}
+
\frac{p_{[0]}}{q_{[0]}}
\end{equation}

\begin{equation}
\label{eq:ex:ccil0:sidv0:sldm0:01:005}
\frac{p}{q} 
=
2^{24} \left\lfloor{\frac{p_{[3]}}{q_{[0]}}}\right\rfloor
+
2^{24} \frac{(p_{[3]} \bmod q_{[0]})}{q_{[0]}}
+
2^{16} \frac{p_{[2]}}{q_{[0]}}
+
2^{8} \frac{p_{[1]}}{q_{[0]}}
+
\frac{p_{[0]}}{q_{[0]}}
\end{equation}

\begin{equation}
\label{eq:ex:ccil0:sidv0:sldm0:01:006}
\frac{p}{q} 
=
2^{24} \left\lfloor{\frac{p_{[3]}}{q_{[0]}}}\right\rfloor
+
2^{16} \frac{2^8 (p_{[3]} \bmod q_{[0]}) + p_{[2]}}{q_{[0]}}
+
2^{8} \frac{p_{[1]}}{q_{[0]}}
+
\frac{p_{[0]}}{q_{[0]}}
\end{equation}

\begin{eqnarray}
\label{eq:ex:ccil0:sidv0:sldm0:01:007}
\frac{p}{q} & = & 2^{24} \left\lfloor{\frac{p_{[3]}}{q_{[0]}}}\right\rfloor
+
2^{16} \left\lfloor{\frac{2^8 (p_{[3]} \bmod q_{[0]}) + p_{[2]}}{q_{[0]}}}\right\rfloor \\
\nonumber & + &
2^{16} \frac{(2^8 (p_{[3]} \bmod q_{[0]}) + p_{[2]}) \bmod q_{[0]}}{q_{[0]}}
+
2^{8} \frac{p_{[1]}}{q_{[0]}}
+
\frac{p_{[0]}}{q_{[0]}}
\end{eqnarray}

\begin{eqnarray}
\label{eq:ex:ccil0:sidv0:sldm0:01:008}
\frac{p}{q} & = & 2^{24} \left\lfloor{\frac{p_{[3]}}{q_{[0]}}}\right\rfloor
+
2^{16} \left\lfloor{\frac{2^8 (p_{[3]} \bmod q_{[0]}) + p_{[2]}}{q_{[0]}}}\right\rfloor \\
\nonumber & + &
2^{8} \frac{2^8((2^8 (p_{[3]} \bmod q_{[0]}) + p_{[2]}) \bmod q_{[0]}) + p_{[1]}}{q_{[0]}}
+
\frac{p_{[0]}}{q_{[0]}}
\end{eqnarray}

\begin{eqnarray}
\nonumber\frac{p}{q} & = & 2^{24} \left\lfloor{\frac{p_{[3]}}{q_{[0]}}}\right\rfloor
+
2^{16} \left\lfloor{\frac{2^8 (p_{[3]} \bmod q_{[0]}) + p_{[2]}}{q_{[0]}}}\right\rfloor \\
\label{eq:ex:ccil0:sidv0:sldm0:01:009}
 & + &
2^{8} \left\lfloor{\frac{2^8((2^8 (p_{[3]} \bmod q_{[0]}) + p_{[2]}) \bmod q_{[0]}) + p_{[1]}}{q_{[0]}}}\right\rfloor \\
\nonumber & + &
2^{8} \frac{(2^8((2^8 (p_{[3]} \bmod q_{[0]}) + p_{[2]}) \bmod q_{[0]}) + p_{[1]}) \bmod q_{[0]}}{q_{[0]}} \\
\nonumber & + &
\frac{p_{[0]}}{q_{[0]}}
\end{eqnarray}

\begin{eqnarray}
\nonumber\frac{p}{q} & = & 2^{24} \left\lfloor{\frac{p_{[3]}}{q_{[0]}}}\right\rfloor
+
2^{16} \left\lfloor{\frac{2^8 (p_{[3]} \bmod q_{[0]}) + p_{[2]}}{q_{[0]}}}\right\rfloor \\
\label{eq:ex:ccil0:sidv0:sldm0:01:010}
 & + &
2^{8} \left\lfloor{\frac{2^8((2^8 (p_{[3]} \bmod q_{[0]}) + p_{[2]}) \bmod q_{[0]}) + p_{[1]}}{q_{[0]}}}\right\rfloor \\
\nonumber & + &
\frac{2^8((2^8((2^8 (p_{[3]} \bmod q_{[0]}) + p_{[2]}) \bmod q_{[0]}) + p_{[1]}) \bmod q_{[0]}) + p_{[0]}}{q_{[0]}}
\end{eqnarray}

\begin{eqnarray}
\nonumber & \displaystyle \frac{p}{q} =  2^{24} \left\lfloor{\frac{p_{[3]}}{q_{[0]}}}\right\rfloor
+
2^{16} \left\lfloor{\frac{2^8 (p_{[3]} \bmod q_{[0]}) + p_{[2]}}{q_{[0]}}}\right\rfloor & \\
\label{eq:ex:ccil0:sidv0:sldm0:01:011}
 & \displaystyle + 
2^{8} \left\lfloor{\frac{2^8((2^8 (p_{[3]} \bmod q_{[0]}) + p_{[2]}) \bmod q_{[0]}) + p_{[1]}}{q_{[0]}}}\right\rfloor & \\
\nonumber & \displaystyle + 
\left\lfloor{\frac{2^8((2^8((2^8 (p_{[3]} \bmod q_{[0]}) + p_{[2]}) \bmod q_{[0]}) + p_{[1]}) \bmod q_{[0]}) + p_{[0]}}{q_{[0]}}}\right\rfloor + & \\
\nonumber 
& \displaystyle \frac{(2^8((2^8((2^8 (p_{[3]} \bmod q_{[0]}) + p_{[2]}) \bmod q_{[0]}) + p_{[1]}) \bmod q_{[0]}) + p_{[0]}) \bmod q_{[0]}}{q_{[0]}}
&
\end{eqnarray}

Note several things about the implementation suggested by 
(\ref{eq:ex:ccil0:sidv0:sldm0:01:011}):

\begin{itemize}
\item No addition or multiplication is required to calculate terms such as
      $2^8 (p_{[3]} \bmod q_{[0]}) + p_{[2]}$.  The high-order byte of the
      large dividend can be stuffed with $p_{[3]} \bmod q_{[0]}$ and
      the low-order byte with $p_{[2]}$.
\item No addition or multiplication is required to calculate the 
      result $\lfloor p/q \rfloor$.
      Note in (\ref{eq:ex:ccil0:sidv0:sldm0:01:011}) that the results are
      conveniently grouped as bytes with multipliers of $2^{24}$, 
      $2^{16}$, $2^8$, and $2^0=1$.  The terms can simply be placed into
      the appropriate byte, as a way of multplication by the appropriate
      power of 2.  Note also that each term is guaranteed to be
      $\in \{0, 1, 2, \ldots{} , 255\}$, by the argument presented
      earlier for (\ref{eq:ccil0:sidv0:sldm0:004}).  Thus, the
      addition will result in no carries, and each result byte can simply
      be placed directly in the correct memory location---addition is
      not necessary.
\item Four machine division instructions are required, and the remainder
      is produced automatically by the fourth instruction.
\end{itemize}

An implemenation for the TMS370C8 is supplied as Figure
\ref{fig:ex:ccil0:sidv0:sldm0:01:01}.  A block diagram of the data
flow for this implementation is supplied as 
Figure \ref{fig:ex:ccil0:sidv0:sldm0:01:02}.
\end{vworkexampleparsection}
\vworkexamplefooter{}

\begin{figure}
\begin{verbatim}
;Assume that byte memory locations p3, p2, p1, and p0 contain the
;32-bit unsigned dividend, and byte q0 contains the 8-bit unsigned
;divisor.  Assume also that the result quotient will be placed
;in byte memory locations d3, d2, d1, and d0; and that the
;remainder will be placed in the byte memory location r0.  Further
;assume that all memory locations are in the register file (near).
        CLR A        ;High-order chunk of large divisor
                     ;must be 0.
        MOV p3, B    ;Load the low-order chunk of divisor.
        DIV q0, A    ;Perform the first division.
        MOV A,  d3   ;Quotient becomes this part of the
                     ;result.
        MOV B,  A    ;Remainder becomes high-order chunk of
                     ;next division.
        MOV p2, B    ;Next byte becomes low-order chunk.
        DIV q0, A    ;Do the second division.
        MOV A,  d2   ;Quotient becomes this part of the
                     ;result.
        MOV B,  A    ;Remainder becomes high-order chunk of
                     ;next division.
        MOV p1, B    ;Next byte becomes low-order chunk.
        DIV q0, A    ;Do the third division.
        MOV A,  d1   ;Quotient becomes this part of the
                     ;result.
        MOV B,  A    ;Remainder becomes high-order chunk of
                     ;next division.
        MOV p0, B    ;Next byte becomes low-order chunk.
        DIV q0, A    ;Do the fourth division.
        MOV A,  d0   ;Quotient becomes this part of the
                     ;result.
        MOV B,  r0   ;This is the remainder, which could be used
                     ;for rounding.
\end{verbatim}
\caption{TMS370C8 Code Snippet Illustrating Unsigned 32/8 
         Division Using Unsigned 16/8
         Machine Instructions (Example \ref{ex:ccil0:sidv0:sldm0:01})}
\label{fig:ex:ccil0:sidv0:sldm0:01:01}
\end{figure}

\begin{figure}
\centering
\includegraphics[width=4.6in]{c_cil0/t370dmp.eps}
\caption{Block Diagram Of Data Flow Of Figure \ref{fig:ex:ccil0:sidv0:sldm0:01:01}}
\label{fig:ex:ccil0:sidv0:sldm0:01:02}
\end{figure}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Miscellaneous Integer Mappings}
%Section tag: MIM0
\label{ccil0:smim0}

Embedded system work and ROM constraints often inspire a great deal
of cleverness in the selection of instructions to perform mappings or
tests.  In this section, we discuss integer mappings (i.e. functions)
for which economical implementations are known; and in the next section
(Section \ref{ccil0:smit0})
we discuss integer tests for which economical implementations are known.

To the best of our knowledge, there is no way to derive these mappings
and tests---they have been collected from many software developers and
come from human intuition and experience.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Lowest-Order Bit}
%Subsection tag: LIB0
\label{ccil0:smim0:slib0}

\index{lowest-order bit}
\index{least significant bit}

The mapping

\texttt{mask = x \& -x}

\noindent{}is the most economical way known to extract the 
lowest-order bit set in an integer \texttt{x}, or 
0 if no bits are set.\footnote{This mapping was contributed by 
David Baker (\texttt{bakerda@engin.umich.edu}) 
and Raul Selgado (\texttt{rselgado@visteon.com}).}  Since most processors have an instruction to form the
two's complement of an integer, this mapping usually requires only
two arithmetic instructions.

When implementing this mapping in assembly-language on processors without a
two's complement instruction, two other possible implementations are:

\begin{itemize}
\item \texttt{mask = x \& ($\sim$x + 1)}
\item \texttt{mask = x \& ((x \^{ } -1) + 1)}
\end{itemize}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Miscellaneous Integer Tests}
%Section tag: MIT0
\label{ccil0:smit0}

\subsection{Power Of 2}
%Subsection tag: PTW0
\label{ccil0:smit0:sptw0}

\index{power of two}
\index{2N@$2^N$}

The test

\texttt{(x \& (x-1) == 0) \&\& (x != 0)}

\noindent{}is the most economical way known to 
test whether an integer is a positive power of two 
(1, 2, 4, 8, 16, etc.).\footnote{The test appeared as part of
a discussion on 
the GMP mailing list in 2002.}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Exercises}

\begin{vworkexercisestatement}
\label{exe:ccil0:sexe0:01}
Show that any $m$-bit two's complement integer $u_{[m-1:0]}$ except
$-2^{m-1}$ can be negated by forming the one's complement, then adding one.
\end{vworkexercisestatement}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\vfill
\noindent\begin{figure}[!b]
\noindent\rule[-0.25in]{\textwidth}{1pt}
\begin{tiny}
\begin{verbatim}
$RCSfile: c_cil0.tex,v $
$Source: /home/dashley/cvsrep/e3ft_gpl01/e3ft_gpl01/dtaipubs/esrgubka/c_cil0/c_cil0.tex,v $
$Revision: 1.24 $
$Author: dtashley $
$Date: 2003/11/03 02:14:24 $
\end{verbatim}
\end{tiny}
\noindent\rule[0.25in]{\textwidth}{1pt}
\end{figure}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% $Log: c_cil0.tex,v $
% Revision 1.24  2003/11/03 02:14:24  dtashley
% All duplicate labels as flagged by LaTeX removed.  Additional files added
% to Microsoft Visual Studio edit context.
%
% Revision 1.23  2002/08/26 17:57:03  dtashley
% Additional solutions chapter added.  Precautionary checkin to be sure
% that I've captured all changes.
%
% Revision 1.22  2002/08/25 13:18:21  dtashley
% Edits.
%
% Revision 1.21  2002/08/22 00:33:33  dtashley
% Have made aesthetic changes in CFRY0 and CCFR0.  Checking in all before
% rebuild of book.
%
% Revision 1.20  2002/08/21 09:12:11  dtashley
% Safety checkin.
%
% Revision 1.19  2002/08/19 05:06:45  dtashley
% Substantial progress in integer numerics chapter.  Preparing to
% work at home.
%
% Revision 1.18  2002/08/10 07:34:48  dtashley
% Checkin before resuming work on a lemma at home.
%
% Revision 1.17  2002/08/09 03:13:42  dtashley
% Significant lemma proved, and other progress.
%
% Revision 1.16  2002/08/06 22:15:24  dtashley
% Substantial lemma proof progress.
%
% Revision 1.15  2002/08/05 01:28:33  dtashley
% Lemma demonstrating that 0 \leq \hat{q}-q \leq 2 completed.
%
% Revision 1.14  2002/08/03 23:04:57  dtashley
% Safety checkin.  Having difficulty:  may have solved the wrong
% problem.
%
% Revision 1.13  2002/08/01 01:31:24  dtashley
% Safety checkin.  Having difficulty completing an alternate version of
% Knuth's proof about the accuracy of quotient estimates based on first
% digits of dividend and divisor.
%
% Revision 1.12  2002/07/31 04:38:31  dtashley
% Edits to basic integer algorithms chapter, safety checkin.
%
% Revision 1.11  2002/07/29 16:30:08  dtashley
% Safety checkin before moving work back to WSU server Kalman.
%
% Revision 1.10  2002/07/26 20:39:43  dtashley
% Safety checkin.
%
% Revision 1.9  2002/07/26 14:58:01  dtashley
% Safety checkin.
%
% Revision 1.8  2002/07/21 16:19:28  dtashley
% Finalization of material about integer division when dividend is
% long but divisor is same as data size that machine can use as
% divisor natively.
%
% Revision 1.7  2002/07/20 23:01:45  dtashley
% Adding material about division with large dividend and machine-native
% divisor.
%
% Revision 1.6  2002/06/11 04:34:19  dtashley
% Information for David Baker added.
%
% Revision 1.5  2002/06/08 05:50:25  dtashley
% Added missing tilde.  Can't get it to be same size as other
% characters--need to research that.
%
% Revision 1.4  2002/06/07 02:08:32  dtashley
% Section added for integer mappings and tests.  Mapping for lowest-order
% bit set from Raul Selgado and Dave (last name presently unknown)
% at Visteon added.  Test for power of 2 added.
%
% Revision 1.3  2001/08/31 23:11:17  dtashley
% End of August 2001 safety check-in.
%
% Revision 1.2  2001/08/27 20:06:08  dtashley
% Edits and substantial re-organization.
%
% Revision 1.1  2001/08/25 22:51:25  dtashley
% Complex re-organization of book.
%
%End of file C_CIL0.TEX