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

Contents of /pubs/books/ucbka/trunk/c_cil0/c_cil0.tex

Parent Directory Parent Directory | Revision Log Revision Log


Revision 277 - (show annotations) (download) (as text)
Tue Aug 13 02:35:39 2019 UTC (4 years, 11 months ago) by dashley
File MIME type: application/x-tex
File size: 109825 byte(s)
Change keyword substitution (migration from cvs to svn).
Add quotation.
1 %$Header$
2
3 \chapter[\ccilzeroshorttitle{}]{\ccilzerolongtitle{}}
4
5 \label{ccil0}
6
7 \beginchapterquote{``If our ancestors had invented arithmetic by counting with
8 their two fists or their eight fingers, instead of their
9 ten `digits', we would never have to worry about
10 writing binary-decimal conversion routines.
11 (And we would perhaps never have learned as much about
12 number systems.)''}
13 {Donald E. Knuth, \cite[p. 319]{bibref:b:knuthclassic2ndedvol2}}
14
15 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
16 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
17 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
18 \section{Introduction}
19 %Section tag: INT0
20 \label{ccil0:sint0}
21
22 Low-cost microcontrollers have no support for floating-point arithmetic,
23 and so integer arithmetic and fixed-point arithmetic are used nearly exclusively
24 in embedded systems. The ability to implement integer arithmetic
25 economically is a critical skill in the development of embedded
26 systems.
27
28 Integer arithmetic algorithms are critically important in embedded
29 systems for the following reasons:
30
31 \begin{itemize}
32 \item Mistakes in the implementation of arithmetic are frequently
33 responsible for product problems. (Mistakes are not confined
34 to obvious errors---errors such as filters which do not converge
35 on their input are also responsible for product problems.)
36 \item Floating-point arithmetic is not available or ill-advised
37 for nearly all small embedded systems for the following reasons:
38 \begin{itemize}
39 \item Low-cost microcontrollers do not possess hardware support for
40 floating-point arithmetic.
41 \item Implementation of floating-point arithmetic in software is
42 computationally expensive.
43 \item Implementation of floating-point arithmetic in software may
44 require large floating-point libraries, typically consuming
45 1K-4K of ROM.
46 \item Safety-critical software standards typically prohibit the
47 use of floating-point arithmetic.
48 \end{itemize}
49 \item Integer arithmetic algorithms (other than addition and subtraction)
50 are quite tedious and error-prone for a software developer to design, implement, and
51 unit test. The implementation of such algorithms represents
52 cost and risk. Cost and risk benefits are achieved if the algorithms in detail are
53 available in advance (thus precluding design activities), or
54 better yet if ready-to-use integer algorithm libraries are available.
55 \end{itemize}
56
57 This chapter describes the more fundamental principles and algorithms
58 (representation, fixed-point arithmetic, treatment of overflow, comparison,
59 addition, subtraction, multiplication, and division). A section
60 (Section \ref{ccil0:smim0}) is also included
61 on miscellaneous mappings involving integers which
62 are not numerical in intent.
63 Chapter %\cdtazeroxrefhyphen\cdtazerovolarabic{}
64 TBD
65 describes more complicated
66 integer algorithms and techniques (discrete-time operations
67 such as filtering, integration, and differentiation as well as more
68 complex functions such as square root). The split between these two chapters
69 is arbitrary; and in fact the material could have been divided differently
70 or combined.
71
72 Treatment of the topics in this chapter is largely in accordance with
73 Knuth \cite{bibref:b:knuthclassic2ndedvol2}. The principal issues in
74 the implementation of integer algorithms are:
75
76 \begin{itemize}
77 \item \textbf{How to use the arithmetic [or other] instructions provided by the machine to
78 operate on larger operands.} Microcontrollers typically provide arithmetic
79 instructions (comparison, shifting, addition, subtraction, and often but not
80 always multiplication and/or division) that operate on 8-bit or 16-bit integers.
81 A key question
82 is how small-operand instructions ``scale up''---that is, if and how they can
83 be used to assist in the implementation of integer arithmetic for much larger
84 operands.
85 \item \textbf{The order of the algorithm involved.} The order of algorithms
86 is a complicated issue when applied to microcontroller work. Many sophisticated
87 algorithms have a breakpoint below which they are less economical than
88 an inferior algorithm. Some applications (such as generating cryptographic keys
89 when integers thousands of bits long must be tested for primality) will
90 benefit from sophisticated algorithms becuase the operand sizes are large enough
91 to pass any such breakpoints. However, in microcontroller work, the need to manipulate
92 integers longer than 64 bits is very rare; thus, the breakpoints that indicate the
93 use of more sophisticated algorithms may not be reached. In microcontroller work,
94 depending on the operand sizes, there are circumstances in which an
95 $O(n^2)$ algorithm may be preferable to an $O(\log n)$ algorithm. Generally,
96 the order of algorithms must be balanced against operand sizes.
97 \end{itemize}
98
99 We do diverge from Knuth in some areas. The most prominent divergence is
100 in the proofs offered for some important theorems and lemmas. Knuth
101 employs contrapositive proof formats in many circumstances, whereas we prefer
102 to use linear proofs that are more understandable to engineers and microcontroller
103 software developers.
104
105 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
106 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
107 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
108 \section[Paradigms And Principles]
109 {Paradigms And Principles Of Microcontroller Arithmetic}
110 %Section tag: PPM0
111 \label{ccil0:sppm0}
112
113 How should one think about microcontroller arithmetic? What principles
114 guide us in its design and implementation? In this section,
115 we provide some general principles and paradigms of thought.
116
117
118 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
119 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
120 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
121 \subsection{Microcontroller Arithmetic As An Accident Of Silicon Design}
122 %Subsection tag: MAS0
123 \label{ccil0:sppm0:smas0}
124
125 In chapters
126 \cfryzeroxrefhyphen{}\ref{cfry0},
127 \ccfrzeroxrefhyphen{}\ref{ccfr0},
128 and
129 \cratzeroxrefhyphen{}\ref{crat0}
130 we consider rational approximation,
131 both in the form $h/k$ and $h/2^q$. Both forms of rational approximation
132 tend to be effective because we know that all modern processors possess
133 shift instructions, most possess integer multiply instructions, and many
134 possess integer divide instructions. In other words, the design
135 of the machine instruction set drives the strategies for implementation
136 of arithmetic, and makes some strategies attractive.
137
138 Similarly, the observation that all microcontrollers provide instructions
139 for integer arithmetic creates the attractiveness of fixed-point arithmetic.
140
141 Thus, we might view our approaches to microcontroller arithmetic as
142 an ``accident'' of silicon design, or as being driven by silicon
143 design.
144
145 Generally, we seek to determine the best way to use the primitive
146 operations provided by the machine (the instruction set) to
147 accomplish the mappings of interest.
148
149 The ``classic'' algorithms
150 presented by Knuth
151 Knuth (\cite[pp. 265-284]{bibref:b:knuthclassic2ndedvol2}) are especially
152 designed to use the ``small'' addition, subtraction, multiplication, and
153 division provided by the machine to add, subtract, multiply, and divide arbitrarily
154 large integers. In
155 \cite[pp. 265-266]{bibref:b:knuthclassic2ndedvol2}) Knuth writes:
156
157 \begin{quote}
158 \emph{The most important fact to understand about extended-precision numbers
159 is that they may be regarded as numbers written in radix-$w$ notation,
160 where $w$ is the computer's word size. For example, an integer that
161 fills 10 words on a computer whose word size is $w=10^{10}$ has 100
162 decimal digits; but we will consider it to be a 10-place number to
163 the base $10^{10}$. This viewpoint is justified for the same reason
164 that we may convert, say, from binary to hexadecimal notation,
165 simply by grouping the bits together.}
166
167 \emph{In these terms, we are given the following primitive operations to work with:}
168
169 \begin{itemize}
170 \item \emph{a$_0$) addition or subtraction of one-place integers, giving a one-place
171 answer and a carry;}
172 \item \emph{b$_0$) multiplication of a one-place integer by another one-place integer,
173 giving a two place answer;}
174 \item \emph{c$_0$) division of a two-place integer by a one-place integer,
175 provided that the quotient is a one-place integer, and yielding
176 also a one-place remainder.}
177 \end{itemize}
178
179 \noindent{}\emph{By adjusting the word size, if necessary, nearly all computers
180 will have these three operations available; so we will construct algorithms
181 (a), (b), and (c) mentioned above in terms of the primitive operations
182 (a$_0$), (b$_0$), and (c$_0$).}
183
184 \emph{Since we are visualizing extended-precision integers as base $b$ numbers, it is
185 sometimes helpful to think of the situation when $b = 10$, and to imagine
186 that we are doing the arithmetic by hand. Then operation (a$_0$) is analogous
187 to memorizing the addition table; (b$_0$) is analogous to memorizing the
188 multiplication table, and (c$_0$) is essentially memorizing the multiplication
189 table in reverse. The more complicated operations (a), (b), (c) on
190 high-precision numbers can now be done using simple addition, subraction,
191 multiplication, and long-division procedures that children are taught
192 in elementary school.}
193 \end{quote}
194
195 The critical issue for implementation of integer arithmetic with large operands
196 is how to use small-operand instructions to operate on larger operands---in other words,
197 how to ``scale up'' the capability provided by the instruction set.
198
199
200 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
201 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
202 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
203 \subsection{Microcontroller Arithmetic As A Mapping From Quantized Domain To
204 Quantized Range}
205 %Subsection tag: MAM0
206 \label{ccil0:sppm0:smam0}
207
208 Microcontroller software accepts inputs which are quantized. In nearly all cases,
209 this involves a mapping from $\vworkrealset$ to $\vworkintset$. Often, because
210 microcontroller products are optimized for cost, the quantization hardware
211 delivers quite poor precision, frequently less than 8 bits.
212
213 When a quantized input is accepted, it defines an inquality. Knowledge of
214 the quantized input (an integer) confines the actual input (a real
215 number, before
216 quantization) to an interval. With a low-cost hardware design, the
217 interval can be fairly large. Usually, by adding cost, the
218 interval can be made smaller.
219
220 Microcontroller outputs tend to be quantized as well, so it is
221 accurate to also characterize outputs as integers. For example, a PWM signal
222 generated by a microcontroller or the output of a D/A converter is
223 controlled by data that is an integer. Like inputs, often the ``granularity''
224 with which outputs can be controlled is quite coarse---again, 8 bits or
225 less is not uncommon.
226
227 Thus, we may view microcontroller software as a mapping from poor-quality
228 inputs to poor-quality outputs.
229
230 In such a framework, where the nature of inputs and outputs introduces
231 substantial error, it is imperative not to introduce additional error
232 in computer arithmetic. In other words, given inputs which are
233 integers, the responsibility of the software is to choose the best
234 integers as outputs. Usually this means that calculations should be
235 devised so as not to lose any information (i.e.
236 not to lose remainders, for example). Losing information is usually
237 equivalent to not being able to make the most correct mapping from input
238 to output. ``Lossy'' arithmetic can degrade the performance of a system,
239 since poor arithmetic may compound an inexpensive hardware design.
240
241
242 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
243 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
244 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
245 \subsection{Microcontroller Arithmetic As A Simulation Of Continuous Controllers}
246 %Subsection tag: MAE0
247 \label{ccil0:sppm0:smae0}
248
249 Control systems have not always employed digital controllers.
250 Many books and web sites (see \cite{bibref:w:historycontrol01}, for example)
251 discuss the historical development of feedback control. Controllers
252 have not historically been digital, or even electronic.
253 Early controllers for governing steam devices or windmills were
254 ultimately mechanical, and relied upon inertia or other physical
255 properties. It is possible to realize abstract notions
256 (integrators, differentiators, gains) using hydraulic systems or other mechanical systems;
257 and in fact hydraulic feedback controllers were used in early rockets
258 and aircraft. Very naturally, abstract notions (integrators,
259 differentiators, gains) can be implemented using analog
260 electronic components. The most common implementations involve
261 operational amplifiers, and the behavior of such implementations comes
262 very close to the ideal mathematical models.
263
264 Mechanical, hydraulic, and non-digital electronic controllers have
265 one very desirable characteristic---\emph{clipping}. If, for example,
266 one provides an analog differentiator with a $dV/dt$ which
267 is too large, the output that the differentiator can
268 provide is limited, usually by the supply voltage available to an operational
269 amplifier.
270 The differentiator \emph{must} clip.
271
272 Clipping often leads to behavior which is close to what
273 intuition would expect (i.e. we would present
274 clipping as an occasional advantage). For example, if an input to
275 an analog control system suffers a failure, the behavior
276 the of the controller is limited, as is its internal
277 state. Similarly, when the
278 input is restored, the controller will usually recover
279 in a reasonable time because the
280 state of the controller (typically maintained in capacitors) is limited
281 in the magnitude it can attain.
282
283 We might view a digital controller as an emulation of
284 an analog controller. We may want to cause the
285 controller to have limits (i.e. rails) internally, for
286 example to prevent excessive integrator ``windup''. We discuss
287 this further in Section \ref{ccil0:sode0}.
288
289
290 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
291 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
292 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
293 \section{Practical Design Issues}
294 %Section tag: PDI0
295 \label{ccil0:spdi0}
296
297 In this section, we consider practical issues surrounding the design
298 and construction of a set of integer arithmetic subroutines.
299 In practice, such a collection of subroutines is likely to be
300 arranged into a library. The purpose of the library would be to
301 free the clients (or callers) of the library from the complexity of
302 large integer calculations.
303
304 The design decisions surrounding the construction of a library vary in
305 the objectivity with which they can be approached. Some design decisions
306 (such as the best mechanism for passing parameters) can be approached
307 rigorously because the measures of goodness are unequivocal (minimal ROM consumption
308 or execution time, for example). However, other design decisions, particulary the
309 decision of the exact nature of the interface between an arithmetic library and
310 its clients, are more subjective. One size does \emph{not} fit all.
311
312
313 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
314 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
315 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
316 \subsection{Parameter Passing And Temporary Storage Mechanisms}
317 %Subsection tag: PPM0
318 \label{ccil0:spdi0:sppm0}
319
320 In small microcontroller work, the desire to save ROM and execution time
321 may lead to inelegant software construction. Because an arithmetic library
322 used in microcontroller work may be called from many different places
323 throughout ROM, serious thought should be given to optimizing the
324 parameter passing mechanisms, even perhaps at the expense of elegance.
325 The way in which the arithmetic library allocates temporary storage is
326 also a point of concern, because the most elegant way of allocating temporary
327 storage (on the stack) may either not be feasible (because of the possibility
328 of stack overflow) or may not be efficient (because the addressing modes of
329 the machine make data on the stack inefficient to address). In this section
330 we discuss both parameter passing and temporary storage mechanisms.
331
332 In the remainder of the discussion, we make the following assumptions
333 about software architecture.
334
335 \begin{enumerate}
336 \item \textbf{The arithmetic library need not be re-entrant.}
337 Most ``small'' microcontroller software loads use a non-preemptive
338 scheduling paradigm, so this is a reasonable assumption. We also
339 make the reasonable assumption that ISR's may not make calls into
340 the arithmetic library.
341 \item \textbf{Dynamic memory allocation, other than on the stack,
342 is not allowed by the software architecture.} This is also
343 a reasonable assumption in ``small'' microcontroller software.
344 \end{enumerate}
345
346 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
347 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
348 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
349 \subsubsection{Parameter Passing Mechanisms}
350 %Subsubsection tag: PPM0
351 \label{ccil0:spdi0:sppm0:sppm0}
352
353 If an arithmetic library exists in a microcontroller software load,
354 it may be called many times throughout ROM. Thus, the parameter
355 passing mechanisms chosen may have a large effect on ROM consumption
356 (due to the setup required for each subroutine call multiplied by
357 many instances throughout ROM) and execution time
358 (because in microcontroller software longer instructions nearly always
359 require more time). Because of the criticality of ROM consumption,
360 parameter passing mechanisms that lack elegance may be attractive.
361
362 In the category of parameter passing, we also include the way in which
363 return value(s) are passed back to the caller.
364
365 The following parameter-passing mechanisms may be employed:
366
367 \begin{enumerate}
368 \item \textbf{Pass by value as storage class \emph{automatic}.}
369 The most common scenario is that the arithmetic
370 library is written in assembly-language to be called from
371 `C', and so the assembly-language subroutines must adhere to the
372 parameter-passing conventions used by the compiler.
373 This usually means that the entire input or output value
374 will be passed in CPU registers or on the stack. Somewhat rarely,
375 a compiler will pass parameters in static locations.\footnote{The
376 usual reason for a `C' compiler to pass parameters in static locations
377 is because the instruction set of the machine was not designed for
378 higher-level languages, and references to [usually \emph{near}] memory
379 are cheaper than stack references. Such compilers also typically
380 analyze the calling tree of the program where possible and use this
381 information to overlay the parameter-passing memory areas of
382 subroutines that cannot be active simultaneously. Without the ability
383 to analyze the calling tree and make overlay decisions based on it,
384 memory would be exhausted, because each subroutine would need to have its
385 own static storage for parameters and local variables.}
386 \item \textbf{Pass by reference.}
387 Typically, it is convenient to pass pointer(s) to area(s) of memory
388 containing input operands, and also a pointer to an area of memory
389 owned by the caller which is written with the result by the arithmetic subroutine.
390 The efficiency of this approach depends on the compiler and the instruction
391 set of the machine. If the instruction set of the machine cannot
392 make effective use of pointers or stack frames, an arithmetic subroutine
393 might be constructed so that it first copies the operands to a static area of memory
394 reserved for the arithmetic library, then performs the necessary arithmetic
395 operations on the operands in the static area,
396 then copies the result(s) back to the area owned by the caller.
397 \item \textbf{Pass by common data block.}
398 In some cases, it may be preferable to reserve a block of memory in which to
399 pass parameters to arithmetic library functions, and from which to retrieve
400 results after an arithmetic library function returns. The allocation of such
401 a static memory block may be done manually\footnote{Note to self: need to
402 include gentleman's agreements on memory usage in my note on software architecture.}
403 or automatically (by development tools which can analyze the function calling tree and
404 manage the overlaying).
405 \end{enumerate}
406
407
408
409 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
410 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
411 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
412 \subsubsection{Temporary Storage Mechanisms}
413 %Subsubsection tag: TSM0
414 \label{ccil0:spdi0:sppm0:stsm0}
415
416 Need to indicate clearly on section on software architectures the
417 primary temporary storage mechanisms:
418
419 \begin{itemize}
420 \item Stack.
421 \item Memory block with overlay functionality.
422 \end{itemize}
423
424 Need to expand software architecture section to cover this, so don't
425 discuss here.
426
427
428 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
429 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
430 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
431 \subsection{Reporting Of Overflow, Underflow, And Domain Errors}
432 %Subsection tag: OUD0
433 \label{ccil0:spdi0:soud0}
434
435 Long integer data types used in microcontroller work are typically
436 of a static size (they cannot grow in size in as operations are
437 performed on them). The reason for the typical static sizes is that
438 dynamic allocation (except for allocation and
439 deallocation on the stack as subroutines
440 are called and return) is rarely used in small microcontroller work.
441 It will come about in the normal usage of an integer arithmetic
442 library that an attempt will be made to operate on integers in
443 a way which generates an overflow, generates an
444 underflow, or
445 represents a domain error (division by zero or
446 square root of a negative integer, for example).
447 An important design decision is how such normal exceptions should be
448 handled.
449
450 Possible design decisions in this area are:
451
452 \begin{enumerate}
453 \item \label{enum:ccil0:spdi0:soud0:01:01}
454 \textbf{To design arithmetic subroutines so that exceptions are not
455 possible.}
456 For example, multiplying an $m$-word integer by an $n$-word integer
457 will always generate an integer that will fit within $m+n$ words.
458 If a multiplication subroutine is designed so that the caller must
459 provide an $m$-word operand and an $n$-word operand and a pointer to
460 an $(m+n)$-word area of memory for the result, an overflow cannot occur.
461 Such a design decision essentially pushes overflow detection back up to
462 the callers of arithmetic subroutines.
463 \item \label{enum:ccil0:spdi0:soud0:01:02}
464 \textbf{To design arithmetic subroutines so that exceptions are possible,
465 but not to detect the exceptions, thus providing an implementation that
466 will produce incorrect results with some operand data values.}
467 For example, if an arithmetic subroutine is designed to add an $m$-word
468 operand to another $m$-word operand to produce an $m$-word result, overflow
469 is possible. A design decision to fail to detect such exceptions pushes
470 the responsibility up to the callers of the arithmetic subroutines.
471 Callers must devise a method for not calling arithmetic subroutines
472 with data values that will cause an exception, or else to detect an exception
473 when it has occurred.
474 \item \label{enum:ccil0:spdi0:soud0:01:03}
475 \textbf{To ``rail'' the result in response to an exception.}
476 It was stated earlier that analog control system functional blocks
477 built with operational
478 amplifiers typically have an output which cannot go beyond the
479 supply rails. One may implement similar behavior in arithmetic subroutines.
480 In an addition subroutine which adds two $m$-word operands to produce an
481 $m$-word result (with each word having $w$ bits), it would be natural to
482 return $2^{mw}-1$ in the event of an overflow in a positive direction and
483 $-2^{mw}$ in the event of an overlfow in a negative direction. Note that
484 the caller will not be able to distinguish a ``rail'' value which represents
485 a valid result from a ``rail'' value substituted to indicate an exception.
486 \item \label{enum:ccil0:spdi0:soud0:01:04}
487 \textbf{To reserve special result data values to indicate exceptions.}
488 Depending on the arithmetic subroutine being implemented, it may be possible
489 to reserve certain result data values to indicate exceptions. This approach
490 is often awkward, as most mathematical subroutines are naturally defined so that
491 all bit patterns in the memory reserved for the result are valid numbers.
492 Additionally, with long result data values, it may not be economical to
493 compare the result against the reserved exception values. Thus, this is seldom
494 an optimal way to deal with exceptions.
495
496 Additionally, if this approach is employed, the semantics of how exception
497 values combine with other exception values and data values must be decided.
498 \item \label{enum:ccil0:spdi0:soud0:01:05}
499 \textbf{To return exception codes to the caller separate from the result data.}
500 In the `C' language, pointers are often used to supply an arithmetic subroutine
501 with the input operands and to provide the arithmetic subroutine with a location
502 (which belongs to the caller) in which to store the result data. Thus, the return
503 value of the arithmetic subroutine (normally assigned through the subroutine name)
504 is often available to return exception codes. For example,
505 a `C' function may be defined as
506
507 \begin{verbatim}
508 unsigned char int128_add(INT128 *result,
509 INT128 *arg1,
510 INT128 *arg2),
511 \end{verbatim}
512
513 leaving the returned \texttt{unsigned char} value available to return
514 exception information. Note that this arrangement has the following advantages:
515
516 \begin{enumerate}
517 \item All bit patterns in the result data memory area area available
518 as data bit patterns.
519 \item The exception data is very economical to test, because it is placed
520 in a machine-native data type.
521 \item The exception data can easily be discarded or by the caller if desired.
522 \item All decisions about how to handle exceptions are left to the caller.
523 \end{enumerate}
524 \item \label{enum:ccil0:spdi0:soud0:01:06}
525 \textbf{To maintain exception data with each result integer.}
526 It is possible to reserve bits for exception information which are part of the
527 long integer data type. This exception state essentially conveys
528 \emph{NaN}\footnote{\emph{N}ot \emph{a} \emph{n}umber.} information---integers with
529 exception information set are not true numbers, but rather they are different from the
530 true result in some way. As with (\ref{enum:ccil0:spdi0:soud0:01:04}), the
531 semantics of how to combine NaN values and NaN values with ordinary non-NaN numbers
532 must be defined.
533 \item \label{enum:ccil0:spdi0:soud0:01:07}
534 \textbf{To maintain a global exception state variable.}
535 A variable or set of variables can be reserved which hold the
536 exception information, if any, from the most recent call to
537 a function in the arithmetic library.
538
539 To save CPU cycles, the arithmetic library can
540 be designed so that it will assign the global exception state variable only if an
541 exception occurs---the caller then has the responsibility of clearing the exception
542 state variable before making any call into the arithmetic library where the
543 exception result is of interest. The interface between the caller and the library
544 can be further optimized if the library only OR's data into the variable containing
545 the exception state. Using this optimization, the caller can clear the exception state
546 variable, make several calls into the arithmetic library, and then retrieve a meaningful
547 exception state variable value summarizing several arithmetic operations.
548 \item \label{enum:ccil0:spdi0:soud0:01:08}
549 \textbf{Hybrid approaches.}
550 The approaches (\ref{enum:ccil0:spdi0:soud0:01:01})
551 through (\ref{enum:ccil0:spdi0:soud0:01:07}) can be combined.
552 For example, approach (\ref{enum:ccil0:spdi0:soud0:01:03})
553 might be combined with approach (\ref{enum:ccil0:spdi0:soud0:01:05})
554 so that exceptions are ``railed'', but the caller may also be made
555 aware that an exception has occured. Many hybrid approaches are possible.
556 \end{enumerate}
557
558
559 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
560 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
561 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
562 \subsection{Semantics Of Combining Overflow, Underflow, And Domain Errors}
563 %Subsection tag: CMB0
564 \label{ccil0:spdi0:scmb0}
565
566 For control system arithmetic, some form of clipping as suggested
567 in Section \ref{ccil0:sppm0:smae0} is probably the
568 best approach. Definitely, an overflow should generate a result
569 which is the largest representable integer, and an
570 underflow should generate a result which is the smallest
571 representable integer.
572
573 In addition to treating an overflow by clipping, it may be
574 advantageous to reserve a flag in the representation of a
575 multiple-precision integer to record that an overflow has occured and been clipped.
576 Some functions which accept the integer as input may be interested
577 in the value of such a flag, where othere---perhaps most---may
578 not.
579
580 The correct course of action in the event of a domain error (such
581 as division by zero) is less clear. It is noteworthy that in a
582 normal control system, domain errors cannot occur (but overflows
583 can).
584
585 The best approach when a domain error is involved probably
586 depends on the basis for the underlying calculation. For
587 example, if integer division is used as part of a
588 strategy for software ratiometric conversion, a value
589 of zero in the denominator probably represents extreme electrical
590 noise, and the most sane approach may be to replace the
591 denominator by one. However, in other contexts it may be appropriate
592 to think in terms of
593
594 \begin{equation}
595 \lim_{k \rightarrow 0^+} \frac{kn}{kd}
596 \end{equation}
597
598 \noindent{}or
599
600 \begin{equation}
601 \lim_{k \rightarrow 0^-} \frac{kn}{kd} .
602 \end{equation}
603
604 Put in other terms, there is not a clear ``one solution
605 meets all needs'' approach to dealing with domain
606 errors.
607
608 As in the case of overflows, it may be advantageous to reserve a bit
609 flag to signal that a domain error has occured and that the result
610 is not valid or not reliable. Note that floating point chips
611 (such as the 80x87) provide similar indications of domain errors.
612
613 It may also be advantageous to adopt conventions for how
614 overflow or domain error flags propagate through binary or
615 unary operators. For example, if two numbers are multiplied, and
616 one of the two has the overflow flag set, it may be wise set the
617 overflow flag in the result. A scheme for how warning
618 flags propagate may be beneficial.
619
620
621 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
622 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
623 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
624 \subsection{Variable Versus Constant Subroutine Execution Time}
625 %Subsection tag: VVC0
626 \label{ccil0:spdi0:svvc0}
627
628 As a design goal of an embedded system, we seek to minimize the
629 timing variability of software components. An arithmetic subroutine
630 that with a high probability takes a short time to execute and with a
631 low probability takes a long time to execute, and where the execution
632 time is data dependent, is a serious risk. An embedded software product
633 may pass all release testing, but then fail in the field because of
634 specific data values used in calculations.
635
636 A very conservative design goal would be to design every arithmetic subroutine
637 to require exactly the same execution time, regardless of data values.
638 This goal is not practical because machine instructions themselves
639 usually have a variable execution time, particularly for multiplication
640 and division instructions. A fallback goal would be to avoid
641 large differences between minimum and maximum execution time, without
642 increasing the maximum execution time. A very practical step to take
643 (using division as an example)
644 is to insert artifical delays into easily detectable exception cases (such as
645 division by zero) so that the exception case takes as long as the
646 minimum time for a division with valid operands.
647
648
649 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
650 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
651 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
652 \section{Fixed-Point Arithmetic}
653 %Section tag: FPA0
654 \label{ccil0:sfpa0}
655
656 \emph{Fixed-point arithmetic}\index{fixed-point arithmetic}
657 is a scheme for the representation
658 of engineering quantities (conceptually real numbers with optional
659 units) by integers so that calculations can be performed
660 on these quantitites using [usually multiple-precision]
661 integer arithmetic.
662
663 In discussing fixed-point arithmetic,
664 we must be careful to distinguish between the
665 \emph{represented value} (the engineering quantity)
666 and the \emph{representation} (the integer which represents
667 the engineering quantity). In most cases, we must also
668 be careful to devise a system to track the units of the
669 represented values, as, especially with control systems,
670 the units of represented values (due to integration and
671 differentiation) can become very complex
672 and mistakes are easy to make.
673
674 Fixed-point arithmetic is the dominant paradigm of construction
675 for calculations in small microcontroller systems. It may not be
676 clear why this should be so or what advantages it offers [over
677 floating-point arithmetic]. The reasons for
678 this predominance are:
679
680 \begin{itemize}
681 \item Fixed-point calculations tend to be very efficient, because
682 they make direct use of the integer arithmetic instructions in the
683 microcontroller's instruction set. On the other hand, floating-point
684 arithmetic operations tend to be much slower.
685
686 \item Floating-point calculations typically require a floating-point
687 library, which may consume at least several hundred bytes
688 of ROM.
689
690 \item Some safety-critical software standards prohibit the use of
691 floating-point arithmetic because it can result in nebulous
692 behavior. Fixed-point arithmetic avoids these concerns.
693 \end{itemize}
694
695 In order to carry out fixed-point arithmetic---that is, in order to
696 operate on engineering quantities as integers---we
697 require that the relationship between the
698 represented value and the representation be of the form
699
700 \begin{equation}
701 \label{eq:ccil0:sfpa0:00}
702 x = r_I u + \Psi,
703 \end{equation}
704
705 \noindent{}where $x \in \vworkrealset$ (possibly with units) is the represented
706 value, $u \in \vworkintset$ is the representation,
707 $r_I \in \vworkrealset$ is the scaling factor (possibly with
708 units), and $\Psi \in \vworkrealset$ (possibly with units) is the offset.
709 Note that the units of $r_I$, $\Psi$, and $x$ must match.
710
711 We further require that $r_I \vworkdivides{} \Psi$\footnote{We \emph{are}
712 aware that this is an abuse of nomenclature, as
713 `$\vworkdivides$' (``divides'') is traditionally only applied to integers.}
714 (i.e. that $\Psi$ be an
715 integral multiple of $r_I$)
716 so that the offset in the represented value corresponds to an integer
717 in the representation. Without this restriction, we could not remove the
718 offset from the representation with integer subtraction only. Note that
719 we do \emph{not} require that $r_I$ or $\Psi$ be rational, although
720 they must both be rational or both be irrational in order to satisfy
721 (\ref{eq:ccil0:sfpa0:00}).
722
723 In (\ref{eq:ccil0:sfpa0:00}), since we've required that $r_I \vworkdivides{} \Psi$,
724 we can replace $\Psi$ by
725
726 \begin{equation}
727 \label{eq:ccil0:sfpa0:00b}
728 \psi = \frac{\Psi}{r_I}
729 \end{equation}
730
731 \noindent{}to obtain
732
733 \begin{equation}
734 \label{eq:ccil0:sfpa0:01}
735 x = r_I (u + \psi),
736 \end{equation}
737
738 \noindent{}where $\psi \in \vworkintset$ is the offset in representational
739 counts.
740
741 Note that we can also easily obtain the following relationships from the
742 defining equations (\ref{eq:ccil0:sfpa0:00}),
743 (\ref{eq:ccil0:sfpa0:00b}), and (\ref{eq:ccil0:sfpa0:01}).
744
745 \begin{equation}
746 \label{eq:ccil0:sfpa0:02}
747 u = \frac{x - \Psi}{r_I} = \frac{x}{r_I} - \psi
748 \end{equation}
749
750 \begin{equation}
751 \label{eq:ccil0:sfpa0:03}
752 \psi = \frac{\Psi}{r_I}
753 \Longleftrightarrow
754 \Psi = r_I \psi
755 \Longleftrightarrow
756 r_I = \frac{\Psi}{\psi}
757 \end{equation}
758
759
760 For example, in a 16-bit signed integer (which inherently may range
761 from -32768 to 32767 inclusive), one might used a fixed-point
762 representation of 100 integer counts per $^\circ$C ($r_I = 0.01 \; ^\circ$C)
763 with an offset of 100$^\circ$C ($\Psi$ = 100$^\circ$C or equivalently
764 $\psi$ = 10000), giving
765 a representational range from -227.68$^\circ$C to 427.67$^\circ$C inclusive.
766
767 If $r_I = 2^N, \; N \in \vworkintset$, then the radix point of the represented
768 value is positioned
769 between two bits of the representation---this arrangement may have computational
770 advantages
771 if the whole and fractional parts of the represented value need to be separated
772 easily in the representation. Note also that if $r_I = 2^{WN}$ where $W$ is the
773 machine integer size of the computer (in bits), then the radix point of the represented value
774 occurs between two addressable machine integers of the representation, which can be convenient.
775 However, we do not require for our definition of a fixed-point representation that
776 $r_I$ be an integral power of two; and in fact we do not even require by our
777 definition that $r_I$ be rational. Note that in general our definition above is the
778 weakest set of conditions so that real-world engineering values can be manipulated
779 using integer operations performed upon the representation.
780
781
782 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
783 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
784 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
785 \section{Representation Of Integers}
786 %Section Tag: ROI0
787 \label{ccil0:sroi0}
788
789 In this section, we discuss common representations of integers, both
790 \emph{machine} integers and \emph{synthetic long} integers.
791 By \emph{representation} we mean the mapping between the abstract
792 mathematical notion of an integer and the way it is stored in the computer
793 (voltage levels and the programming model).
794 Although
795 in Knuth's development of integer arithmetic
796 \cite{bibref:b:knuthclassic2ndedvol2}
797 it is assumed that
798 integers may be represented in any base, we don't require such generality
799 in practice and in this work we confine ourselves for the most
800 part to $b=2^n$, and often to $n = 8i$, $i \in \vworkintsetpos$. The assumption
801 of $b=2^n$ characterizes all modern digital computers, and we feel comfortable
802 making this assumption throughout the work. However, the assumption
803 $n = 8i$, $i \in \vworkintsetpos$ does not hold universally, and so we
804 most often do not make this assumption.
805
806 By \emph{machine} integer, we mean an integer upon which the computer
807 can operate in a single instruction (such as to add, increment,
808 load, store, etc.). For most microcontrollers, machine integers are
809 either 8 or 16 bits in size. The representation of a machine integer
810 is designed and specified by the microcontroller manufacturer. In principle,
811 nothing would prevent a microcontroller manufacturer from devising
812 and implementing a novel way of representing machine integers and supporting
813 this novel representation with an instruction set. However, in
814 practice, all machine integers are either simple unsigned integers or two's
815 complement signed integers. In addition to the efficiency of these
816 representations with respect to the design of digital logic, these representations
817 are so standard and so pervasive that they are universally tacitly assumed.
818 For example, ``\texttt{if (i \& 0x1)}'' is an accepted C-language
819 idiom for ``if $i$ is odd'', and it is expected that such code will
820 work on all platforms.
821
822 By \emph{synthetic long} integer, we mean an integer of
823 arbitrary\footnote{By \emph{arbitrary}, we do not necessarily mean that
824 the integer can grow to be arbitrarily large in magnitude, or that
825 its maximum size is not known at compile time. We mean \emph{arbitrarily}
826 longer than a machine integer. Multiple-precision arithmetic libraries
827 can be divided into two classes---those that fix the size of the integers
828 at compile time, and those that use dynamic allocation and allow integers to
829 grow as needed at run time. The former category
830 is normally used for small microcontroller work, whereas the latter category
831 (such as the GNU MP Library \cite{bibref:s:gnumultipleprecisionarithmeticlibrary})
832 is normally used in scientific and number theoretic calculation and on
833 more powerful platforms than microcontrollers. The representational concepts
834 we present here apply to both categories.}
835 length that is formed by concatenating machine integers. There is some
836 subjectivity in deciding the representation of multiple-precision integers,
837 and we discuss in the subsections
838 \ref{ccil0:sroi0:srou0} and
839 \ref{ccil0:sroi0:sros0} which immediately follow.
840
841
842 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
843 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
844 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
845 \subsection{Representation Of Unsigned Integers}
846 %Subsection Tag: ROU0
847 \label{ccil0:sroi0:srou0}
848
849 Unsigned machine integers are always represented as an ordered
850 array of bits (Figure \ref{fig:ccil0:sroi0:srou0:00}). For an
851 $m$-bit unsigned integer $u$, we denote these bits $u_{[m-1]}$ through
852 $u_{[0]}$, with $u_{[m-1]}$ the most significant bit. The value
853 of $u$ is the sum of the values of each bit multiplied
854 by the power of 2 it represents:
855
856 \begin{figure}
857 \centering
858 \includegraphics[width=4.6in]{c_cil0/uintrep1.eps}
859 \caption{Representation Of Unsigned Machine Integers}
860 \label{fig:ccil0:sroi0:srou0:00}
861 \end{figure}
862
863 \begin{equation}
864 \label{eq:ccil0:sroi0:srou0:00}
865 u = \sum_{i=0}^{m-1} u_{[i]} 2^i .
866 \end{equation}
867
868 In general, an $m$-bit unsigned integer can assume the values of
869 0 through $2^m - 1$, so that
870
871 \begin{equation}
872 \label{eq:ccil0:sroi0:srou0:01}
873 u \in \{0, \ldots{} , 2^m - 1 \} .
874 \end{equation}
875
876 Unsigned synthetic long integers are always represented as an array
877 of unsigned machine integers.
878 Consistent with the GMP \cite{bibref:s:gnumultipleprecisionarithmeticlibrary},
879 we call each element of the array a \emph{limb} and we call the size of
880 each limb the \emph{limbsize}. This usage is very close to what Knuth
881 calls the \emph{word}size $w$ in the excerpt presented in
882 Section \ref{ccil0:sppm0:smas0}.
883
884 Microcontroller processors are more likely than more powerful processors to have
885 a non-orthogonal instruction set, and so the limbsize may not be consistent between
886 operations in an arithmetic library.
887 With some processors, the appropriate limbsize may vary depending on the operation being
888 performed.
889 For example, a microcontroller processor may be able to add two 16-bit integers to
890 obtain a 16-bit result plus a carry, but only be able to multiply two 8-bit integers to
891 obtain a 16-bit result (thus, the appropriate limbsize for addition may be
892 16 bits while the appropriate limbsize for multiplication may be 8 bits).
893 In such cases, it is usually most efficient to add using 16-bit limbs but
894 multiply using 8-bit limbs. Adding using 8-bit limbs on a machine which will
895 support 16-bit additions is not normally a good design decision---even if the
896 machine supports an 8-bit addition instruction which is faster than the 16-bit addition
897 instruction, $m/2$ 16-bit additions will nearly always be faster than
898 $m$ 8-bit additions. Using different limbsizes within the same arithmetic library
899 may require some consideration of alignment and
900 endian issues, but these are implementation details
901 which are easily solved.
902
903 We view a synthetic long unsigned integer as an array of limbs (machine integers)
904 of some size, and we agree that we will not address the array in any other way than
905 by loading and storing limbs of this size.\footnote{Well \ldots{} not quite.
906 In software for large computers (personal computers and workstations) with an
907 orthogonal instruction set, we may be able to adhere to this rule. However,
908 with microcontrollers, arithmetic libraries which are optimized
909 may break this rule.} In particular, because
910 computers may be ``big-endian'' or ``little-endian'', loading and storing
911 smaller units than limbs may lead in
912 a worst case to software defects or in a best case to non-portable code.
913
914 Assume that $w$ is the number of bits in a limb.
915 Notationally, we denote an unsigned
916 synthetic long integer as an array of $m$ limbs
917 $u_{m-1}$ through $u_0$, each containing $w$ bits,
918 with $u_0$ the least significant machine integer.
919 We may also define $b=2^w$ (consistent with Knuth's
920 notation).
921 The value of
922 such a synthetic long machine integer is
923
924 \begin{equation}
925 \label{eq:ccil0:sroi0:srou0:02}
926 u = \sum_{i=0}^{m-1} u_{i} 2^{wi}
927 =
928 \sum_{i=0}^{m-1} u_{i} b^i.
929 \end{equation}
930
931 As an alternative, we may write the value as the sum of the bit-values,
932
933 \begin{equation}
934 \label{eq:ccil0:sroi0:srou0:03}
935 u = \sum_{i=0}^{wm-1} u_{[i]} 2^{i} .
936 \end{equation}
937
938 Naturally, the range of such a synthetic long integer is
939
940 \begin{equation}
941 \label{eq:ccil0:sroi0:srou0:04}
942 u \in \{0, \ldots{} , 2^{wm} - 1 \} .
943 \end{equation}
944
945 In storing an unsigned synthetic long machine integer, the most natural way
946 to order the array of limbs depends on whether dynamic memory allocation is
947 used by the arithmetic library. In microcontroller work, where arithmetic
948 library subroutines typically operate on fixed-size operands and produce
949 fixed-size results, storing
950 limbs most significant limb first (i.e. in `C', so that element \texttt{[0]}
951 of the array of limbs contains the most significant limb) may be natural
952 and convenient. However, this ordering would lead to computational waste in a library such
953 as the GMP \cite{bibref:s:gnumultipleprecisionarithmeticlibrary} where integers
954 may grow arbitrarily large and the library may need to reallocate long synthetic
955 integers to contain more limbs, as each reallocation would need to be followed
956 by a memory copy to align the integer's existing limbs to the end of the array.
957 For libraries such as the GMP, it is more practical to store limbs
958 least-significant limb first, as it eliminates the need to copy memory
959 when reallocations are done.
960
961
962
963 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
964 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
965 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
966 \subsection{Representation Of Signed Integers}
967 %Subsection Tag: ROS0
968 \label{ccil0:sroi0:sros0}
969
970 Signed machine integers are always represented in two's complement form on modern
971 processors. This representation is universal because of the digital logic
972 conveniences---the same addition and subtraction mappings which are correct
973 for unsigned machine integers are also correct for signed machine integers,
974 although the criteria for overflow and comparison are
975 different.
976
977 Most readers are familiar with two's complement representation, so we will not
978 belabor it. However, we will present essential properties.
979 When two's complement representation is used in an $m$-bit machine integer $u$:
980
981 \begin{enumerate}
982 \item All bit patterns with $u_{[m-1]} = 0$ represent non-negative integers, and
983 represent the same integer as if the representation were unsigned.
984 \item All bit patterns with $u_{[m-1]} = 1$ represent negative numbers; specifically
985 $u_{[m-2:0]} - 2^{m-1}$; i.e.
986
987 \begin{equation}
988 \label{eq:ccil0:sroi0:sros0:00}
989 u = - u_{[m-1]} 2^{m-1} + \sum_{i=0}^{m-2} u_{[i]} 2^i .
990 \end{equation}
991
992 \item $u \in \{-2^{m-1}, \ldots{}, 2^{m-1}-1 \}$.
993 \item All bit patterns represent a unique integer.
994 \item For any integer except $-2^{m-1}$,
995 negation can be performed by forming the one's complement (complementing
996 every bit), then adding one. To see why this is true algebraically, note that
997
998 \end{enumerate}
999
1000
1001 However, let us observe that the value of an
1002 $m$-bit two's complement
1003 machine integer is
1004
1005
1006 In general, an $m$-bit signed machine integer can assume the values of
1007 $-2^{m-1}$ through $2^{m-1} - 1$, so that
1008
1009 \begin{equation}
1010 \label{eq:ccil0:sroi0:sros0:01}
1011 u \in \{-2^{m-1}, \ldots{} , 2^{m-1} - 1 \} .
1012 \end{equation}
1013
1014 There are [at least] two different representations of signed
1015 multiple-precision integers:
1016
1017 \begin{itemize}
1018 \item Two's complement representation.
1019 \item Sign-magnitude representation.
1020 \end{itemize}
1021
1022 There are two different representations commonly used
1023 for signed multiple-precision integers because two's complement
1024 representation is not ideal for multiplication and division, although
1025 it is ideal for addition and subtraction. For multiple-precision
1026 integer arithmetic, sign-magnitude representation is more common.
1027
1028 In two's complement representation of multiple-precision integers,
1029 the representation is the same as suggested by
1030 (\ref{eq:ccil0:sroi0:sros0:00}), except
1031 more bits are involved. For a two's complement representation
1032 of a number consisting of $n$ machine integers with $W$ bits per
1033 machine integer,
1034
1035 \begin{equation}
1036 \label{eq:ccil0:sroi0:sros0:02}
1037 u = - u_{B(Wn-1)} 2^{Wn-1} + \sum_{i=0}^{Wn-2} u_{B(i)} 2^i .
1038 \end{equation}
1039
1040 Because we would like to know how to compare signed multiple-precision
1041 integers in two's complement representation, we can gain some
1042 insight into the representation by rewriting
1043 (\ref{eq:ccil0:sroi0:sros0:02}) in terms of machine integers:
1044
1045 \begin{equation}
1046 \label{eq:ccil0:sroi0:sros0:03}
1047 u = - u_{B(Wn-1)} 2^{Wn-1}
1048 +
1049 \sum_{i=W(m-1)}^{Wn-2} u_{B(i)} 2^i
1050 +
1051 \sum_{i=0}^{m-2} u_{i} 2^{Wi} .
1052 \end{equation}
1053
1054 (\ref{eq:ccil0:sroi0:sros0:03}) gives some insight into the
1055 relative values of multiple-precision signed two's complement
1056 integers with respect to the values of the machine integers
1057 that comprise them. We discuss this further in
1058 Section \ref{ccil0:scsi0}.
1059
1060 In sign-magnitude representation of multiple-precision signed two's
1061 complement integers, an integer $u$ is represented as a sign
1062 bit (usually a value of one indicates negativity), and a magnitude,
1063 which is $|u|$. Unlike two's complement representation,
1064 sign-magnitude representation, has two representations of zero---a positive
1065 one and a negative one. Either a canonical form for zero should be
1066 adopted, or both values should be treated identically.
1067
1068 Assuming that the sign bit is stored in the most significant bit position,
1069 it is easy to deduce that the value of a multiple-precision
1070 signed two's complement integer in sign-magnitude representation is
1071
1072 \begin{equation}
1073 \label{eq:ccil0:sros0:srou0:04}
1074 u = (-1)^{u_{B(m-1)}} \sum_{i=0}^{m-2} u_{B(i)} 2^i .
1075 \end{equation}
1076
1077 Sign-magnitude representation is especially convenient because
1078 it allows machine instructions which accept unsigned operands to be used
1079 to make calculations involving signed integers.
1080
1081
1082
1083 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1084 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1085 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1086 \section{Characteristics Of Practical Processors}
1087 %Section tag: CPP
1088 \label{ccil0:scpp0}
1089
1090 Before discussing specific algorithms, it is necessary to
1091 discuss the construction of practical processors---how such a processor
1092 manipulates machine integers. We accept as a typical processor the
1093 TMS-370C8, an 8-bit microcontroller manufactured by
1094 Texas Instruments.
1095
1096 \begin{figure}
1097 \centering
1098 \includegraphics[width=4.6in]{c_cil0/t370flag.eps}
1099 \caption{Texas Instruments TMS-370C8 Flags}
1100 \label{fig:ccil0:scpp0:00}
1101 \end{figure}
1102
1103 \begin{figure}
1104 \centering
1105 \includegraphics[width=4.6in]{c_cil0/t370cjmp.eps}
1106 \caption{Texas Instruments TMS-370C8 Conditional Jump Instructions}
1107 \label{fig:ccil0:scpp0:01}
1108 \end{figure}
1109
1110 A typical microcontroller allows operations on machine integers
1111 in the following steps:
1112
1113 \begin{itemize}
1114 \item A machine instruction is performed on one or two machine
1115 integer operands (for example: addition, subtraction,
1116 multiplication, division, increment, decrement, complement,
1117 negation, or comparison). This machine instruction may
1118 produce a result, and usually sets a number of condition flags that
1119 reflect the nature and validity of the result (Is it zero?
1120 Is it negative? Did the result overflow?). As an
1121 example, the condition
1122 flags of the TMS-370C8 are shown in Figure \ref{fig:ccil0:scpp0:00}.
1123 .
1124 \item A conditional branch instruction is used to branch conditionally
1125 based on the state of the condition flags. The definition of
1126 the condition flags and the way in which the conditional
1127 branch instruction utilizes them is designed to provide a
1128 way to treat both unsigned and signed machine integers.
1129 As an example, the way in which the conditional
1130 jump instructions of the TMS-370C8 use the flags
1131 is shown in Figure \ref{fig:ccil0:scpp0:01}.
1132 \end{itemize}
1133
1134 It is not too often necessary to understand in detail
1135 the Boolean relationships that govern how machine integers are
1136 added, subtracted, and compared; and how signed comparisons differ
1137 from unsigned comparisons. In most cases, it is adequate to
1138 rely on the design of the microcontroller. However, we do present
1139 rudimentary observations in this section.
1140
1141
1142
1143 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1144 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1145 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1146 \section{Comparison Of Integers}
1147
1148
1149 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1150 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1151 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1152 \subsection{Comparison Of Unsigned Integers}
1153
1154
1155 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1156 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1157 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1158 \subsection{Comparison Of Signed Integers}
1159 %Section Tag: CSI0
1160 \label{ccil0:scsi0}
1161
1162
1163 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1164 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1165 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1166 \section{Integer Addition}
1167 %Section tag: IAD0
1168 \label{ccil0:siad0}
1169
1170 Addition of two $m$-bit integers is a combinational function---that is,
1171 the inputs uniquely determine the output. Addition of binary
1172 numbers is performed
1173
1174
1175 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1176 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1177 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1178 \subsection{Hardware Implementation Of Addition}
1179
1180
1181 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1182 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1183 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1184 \subsection{Addition Of Unsigned Operands}
1185
1186
1187 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1188 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1189 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1190 \subsection{Addition Of Signed Operands}
1191
1192
1193 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1194 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1195 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1196 \section {Integer Subtraction}
1197
1198
1199 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1200 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1201 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1202 \subsection{Hardware Implementation Of Subtraction}
1203
1204
1205 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1206 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1207 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1208 \subsection{Subtraction Of Unsigned Operands}
1209
1210
1211 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1212 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1213 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1214 \subsection{Subtraction Of Signed Operands}
1215
1216
1217
1218 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1219 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1220 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1221 \section{Integer Multiplication}
1222
1223
1224 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1225 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1226 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1227 \subsection{Hardware Implementation Of Multiplication}
1228
1229
1230 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1231 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1232 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1233 \subsection{Multiplication Of Unsigned Operands}
1234
1235
1236 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1237 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1238 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1239 \subsection{Multiplication Of Signed Operands}
1240
1241
1242
1243 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1244 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1245 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1246 \section{Integer Division}
1247 \label{ccil0:sidv0}
1248
1249 \index{division}\index{integer division}In this section,
1250 we discuss the best known methods of dividing integers using
1251 typical microcontroller instruction sets. In general, given
1252 two arbitrary integers $p$ and $q$, we are interested in determining
1253 their quotient $q=\lfloor{}p/q\rfloor$ and remainder
1254 $r=p\bmod{}q$ as economically as possible.
1255
1256
1257 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1258 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1259 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1260 \subsection{Hardware Implementation Of Division}
1261
1262
1263 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1264 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1265 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1266 \subsection{General Unsigned Division Without A Machine Division Instruction}
1267 \label{ccil0:sidv0:sgdn0}
1268
1269
1270 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1271 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1272 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1273 \subsection{General Unsigned Division With A Machine Division Instruction}
1274 \label{ccil0:sidv0:sgdu0}
1275
1276 As mentioned many places in this work, efficiency in microcontroller software
1277 involves phrasing computational problems in a way which makes good use of
1278 the machine instruction set. In Section \ref{ccil0:sidv0:sgdn0} we discussed
1279 the classic shift-compare-subtract algorithm for division. This algorithm
1280 is far from efficient. A reasonable question to ask is whether we can
1281 leverage ``small'' division capability (provided by the machine instruction set)
1282 to accomplish ``large'' divisions (those which we require in practice).
1283 It ends up that this is possible: the technique involved is effectively
1284 to use machine division instructions to estimate the highest-order bits of
1285 the quotient based on the highest-order bits of the dividend and divisor.
1286
1287 Knuth's discussion of division
1288 algorithms \cite[pp. 270-275]{bibref:b:knuthclassic2ndedvol2} is the
1289 basis for most of the material in this subsection. However, Knuth has
1290 a gift for terseness that is sometimes a curse for the reader, and so
1291 we take more time than Knuth to explain certain results.
1292
1293 First, as a starting point, we present \emph{Algorithm D} from
1294 Knuth \cite[pp. 272-273]{bibref:b:knuthclassic2ndedvol2}. Then,
1295 we justify the algorithm and explain why it is valid. Finally,
1296 we supply implementation advice for microcontroller instruction sets.
1297
1298 \begin{vworkalgorithmstatementpar}{Arbitrary Unsigned Division Using
1299 Machine Unsigned Division Instructions}
1300 \label{alg:ccil0:sidv0:sgdu0:01}
1301 (From Knuth \cite[pp. 272-273]{bibref:b:knuthclassic2ndedvol2})
1302 Given nonnegative integers $u=(u_{m+n-1} \ldots{} u_1 u_0)_b$
1303 and $v=(v_{n-1} \ldots{} v_1 v_0)_b$, where
1304 $v_{n-1} \neq 0$ and $n > 1$, we form the radix-$b$ quotient
1305 $\lfloor{}u/v\rfloor{} = (q_m q_{m-1} \ldots{} q_0)_b$ and
1306 the remainder $u \bmod v = (r_{n-1} \ldots{} r_1 r_0)_b$. When
1307 $n=1$, the simpler algorithm of
1308 Subsection \ref{ccil0:sidv0:sldm0}
1309 should be used.
1310
1311 \begin{algblvl0}
1312 \item \label{enumstep:alg:ccil0:sidv0:sgdu0:01:01}
1313 [Normalize.] Set $d \gets \lfloor{}b/(v_{n-1} + 1)\rfloor$.
1314 Then set $(u_{m+n} u_{m+n-1} \ldots{} u_1 u_0)_b$ equal to
1315 $(u_{m+n-1} \ldots{} u_1 u_0)_b$ times $d$; similarly,
1316 set $(v_{n-1} \ldots{} v_1 v_0)_b$ equal to
1317 $(v_{n-1} \ldots{} v_1 v_0)_b$ times $d$. (Notice the introduction
1318 of a new digit position $u_{m+n}$ at the left of
1319 $u_{m+n-1}$; if $d=1$, all we need to do in this step is set
1320 $u_{m+n} \gets 0$. On a binary computer it may be preferable
1321 to choose $d$ to be a power of 2 instead of using the value
1322 suggested here; any value of $d$ that results in
1323 $v_{n-1} \geq \lfloor{}b/2\rfloor$ will suffice. See also
1324 exercise 37.)
1325 \item \label{enumstep:alg:ccil0:sidv0:sgdu0:01:02}
1326 [Initialize $j$.] Set $j \gets m$. (The loop on $j$,
1327 steps
1328 \ref{enumstep:alg:ccil0:sidv0:sgdu0:01:03}
1329 through
1330 \ref{enumstep:alg:ccil0:sidv0:sgdu0:01:07},
1331 will be essentially a division of
1332 $(u_{j+n} \ldots{} u_{j+1} u_j)_b$ by $(v_{n-1} \ldots{} v_1 v_0)_b$ to
1333 get a single quotient digit $q_j$; see Figure \ref{fig:alg:ccil0:sidv0:sgdu0:01:01}.)
1334
1335 \begin{figure}
1336 \centering
1337 \includegraphics[width=4.6in]{c_cil0/kdfc01.eps}
1338 \caption{Flowchart For Algorithm \ref{alg:ccil0:sidv0:sgdu0:01} (From \cite[p. 273]{bibref:b:knuthclassic2ndedvol2})}
1339 \label{fig:alg:ccil0:sidv0:sgdu0:01:01}
1340 \end{figure}
1341
1342 \item \label{enumstep:alg:ccil0:sidv0:sgdu0:01:03}
1343 [Calculate $\hat{q}$.] Set
1344 $\hat{q} \gets \lfloor{}u_{j+n}b + u_{j+n-1})/v_{n-1}\rfloor$ and
1345 let $\hat{r}$ be the remainder, $(u_{j+n}b + u_{j+n-1}) \bmod v_{n-1}$.
1346 Now test if $\hat{q} = b$ or $\hat{q} v_{n-2} > b\hat{r} + u_{j+n-2}$;
1347 if so, decrease $\hat{q}$ by 1, increase $\hat{r}$ by $v_{n-1}$, and repeat
1348 this test if $\hat{r} < b$. (The test of $v_{n-2}$ determines at high
1349 speed most of the cases in which the trial value $\hat{q}$ is one too large,
1350 and it eliminates \emph{all} cases where $\hat{q}$ is two too large;
1351 see exercises 19, 20, 21.)
1352 \item \label{enumstep:alg:ccil0:sidv0:sgdu0:01:04}
1353 [Multiply and subtract.] Replace $(u_{j+n} u_{j+n-1} \ldots{} u_j)_b$ by
1354
1355 \begin{equation}
1356 \nonumber
1357 (u_{j+n} u_{j+n-1} \ldots{} u_j)_b - \hat{q} (0 v_{n-1} \ldots{} v_1 v_0)_b.
1358 \end{equation}
1359
1360 This computation consists of a simple multiplication by a one-place number,
1361 combined with a subtraction. The digits $(u_{j+n}, u_{j+n-1}, \ldots{}, u_j)$
1362 should be kept positive; if the result of this step is actually negative,
1363 $(u_{j+n} u_{j+n-1} \ldots{} u_j)_b$ should be left as the true
1364 value plus $b^{n+1}$, namely as the $b$'s complement of the true value, and
1365 a ``borrow'' to the left should be remembered.
1366 \item \label{enumstep:alg:ccil0:sidv0:sgdu0:01:05}
1367 [Test remainder.] Set $q_j \gets \hat{q}$. If the result of step
1368 \ref{enumstep:alg:ccil0:sidv0:sgdu0:01:04} was negative, go to
1369 step \ref{enumstep:alg:ccil0:sidv0:sgdu0:01:06}; otherwise go on to
1370 step \ref{enumstep:alg:ccil0:sidv0:sgdu0:01:07}.
1371 \item \label{enumstep:alg:ccil0:sidv0:sgdu0:01:06}
1372 [Add back.] (The probability that this step is necessary is very small, on the
1373 order of only $2/b$, as shown in exercise 21; test data to activate this step
1374 should therefore be specifically contrived when debugging.) Decrease
1375 $q_j$ by 1, and add $(0 v_{n-1} \ldots v_1 v_0)_b$ to
1376 $(u_{j+n} u_{j+n-1} \ldots{} u_{j+1} u_j)_b$. (A carry will occur to the left of
1377 $u_{j+n}$, and it should be ignored since it cancels with the borrow that
1378 occured in step \ref{enumstep:alg:ccil0:sidv0:sgdu0:01:04}.)
1379 \item \label{enumstep:alg:ccil0:sidv0:sgdu0:01:07}
1380 [Loop on $j$.] Decrease $j$ by one. Now if $j \geq 0$, go back to step
1381 \ref{enumstep:alg:ccil0:sidv0:sgdu0:01:03}.
1382 \item \label{enumstep:alg:ccil0:sidv0:sgdu0:01:08}
1383 [Unnormalize.] Now $(q_m \ldots{} q_1 q_0)_b$ is the desired quotient, and
1384 the desired remainder may be obtained by dividing
1385 $(u_{n-1} \ldots{} u_1 u_0)_b$ by $d$.
1386 \end{algblvl0}
1387 \end{vworkalgorithmstatementpar}
1388 \vworkalgorithmfooter{}
1389
1390 The general idea of Algorithm \ref{alg:ccil0:sidv0:sgdu0:01} is that
1391 digits (machine words) of the quotient $q$ can be successively estimated
1392 based on the first digits of the dividend and divisor. Knuth
1393 \cite[p. 271]{bibref:b:knuthclassic2ndedvol2} explores the properties of
1394 the digit estimate
1395
1396 \begin{equation}
1397 \label{eq:ccil0:sidv0:sgdu0:01}
1398 \hat{q} = \min \left( {\left\lfloor{\frac{u_n b + u_{n-1}}{v_{n-1}}}\right\rfloor, b-1} \right).
1399 \end{equation}
1400
1401 The first point to make about an estimate in the form of
1402 (\ref{eq:ccil0:sidv0:sgdu0:01}) is that it can only be accomplished
1403 efficiently if the machine-native division instruction supports
1404 overflow detection, since it is possible that
1405 $(u_n b + u_{n-1})/v_{n-1} \geq b$, even if
1406 $u/v < b$, as is shown by the following example.
1407
1408 \begin{vworkexamplestatement}
1409 \label{ex:ccil0:sidv0:sgdu0:01:01}
1410 Assume that we wish to apply the estimate of $\hat{q}$ provided by
1411 (\ref{eq:ccil0:sidv0:sgdu0:01})
1412 to $u=16,776,704$ and $v=65,535$. Demonstrate that a machine division
1413 overflow will occur when estimating the first digit, assuming a processor
1414 that can divide a 16-bit dividend by an 8-bit divisor to produce an 8-bit
1415 quotient.
1416 \end{vworkexamplestatement}
1417 \begin{vworkexampleparsection}{Solution}
1418 Note that according to Knuth's intention, the word size on such a machine
1419 is 8 bits. Thus, $b=256$. Note that $u/v = 255 + 255/256 < b = 256$, as
1420 required by Knuth's precondition. However, although $u/v < b$,
1421 $u = [255 \; 254 \; 0] [256^2 \; 256 \; 1]^T = [u_2 u_1 u_0] [b^2 b^1 b^0]^T$ and
1422 $v = [255 \; 255] [256 \; 1]^T = [v_1 v_0] [b^1 b^0]^T$, so that calculating
1423 an estimate $\hat{q}$ as required by (\ref{eq:ccil0:sidv0:sgdu0:01}),
1424 $(u_n b + u_{n-1})/v_{n-1} = 65,534/255 = 256 + 254/255 \geq b$, is a division
1425 overflow for a single machine division instruction. Thus, it follows that
1426 a machine with division overflow detection can quickly determine that $b-1$ from
1427 (\ref{eq:ccil0:sidv0:sgdu0:01}) is the minimum, whereas a machine without
1428 division overflow
1429 detection would have to use several additional machine instructions to make
1430 this determination.
1431 \end{vworkexampleparsection}
1432 \vworkexamplefooter{}
1433
1434 The second thing to establish about $\hat{q}$ as defined by
1435 (\ref{eq:ccil0:sidv0:sgdu0:01}) is how ``good'' of an estimate
1436 $\hat{q}$ is---how much information, exactly, about $q$ can we
1437 obtain by examining the first two words of $u$ and the first
1438 word of $v$?
1439
1440 We first establish in the following lemma that our estimate of
1441 $q$, $\hat{q}$, can be no less than $q$.
1442
1443 \begin{vworklemmastatementpar}{\mbox{\boldmath$\hat{q} \geq q$}}
1444 \label{lem:ccil0:sidv0:sgdu0:01}
1445 The estimate of $q$ provided by (\ref{eq:ccil0:sidv0:sgdu0:01}),
1446 $\hat{q}$ is always at least as great as the actual value of
1447 $q$, i.e. $\hat{q} \geq q$.
1448 \end{vworklemmastatementpar}
1449 \begin{vworklemmaproof}
1450 Knowledge of $u_{n}$, $u_{n-1}$, and $v_{n-1}$ necessarily confine
1451 the intervals in which the actual values of $u$ and $v$ may be;
1452 specifically:\footnote{In
1453 (\ref{eq:lem:ccil0:sidv0:sgdu0:01:04})
1454 and
1455 (\ref{eq:lem:ccil0:sidv0:sgdu0:01:07}),
1456 we use statements of the form ``$x = x$'' as an idiom for
1457 ``$x$ is known''.}
1458
1459 \begin{eqnarray}
1460 \label{eq:lem:ccil0:sidv0:sgdu0:01:01}
1461 u & = & \sum_{i=0}^{n} u_i b^i \\
1462 \label{eq:lem:ccil0:sidv0:sgdu0:01:02}
1463 & = & u_n b^n + u_{n-1} b^{n-1} + \ldots{} + u_2 b^2 + u_1 b + u_0 \\
1464 \label{eq:lem:ccil0:sidv0:sgdu0:01:03}
1465 & = & (u_n b + u_{n-1}) b^{n-1} + \ldots{} + u_2 b^2 + u_1 b + u_0
1466 \end{eqnarray}
1467
1468 \begin{eqnarray}
1469 \nonumber & (u_n = u_n \wedge u_{n-1} = u_{n-1}) & \\
1470 \label{eq:lem:ccil0:sidv0:sgdu0:01:04}
1471 & \vworkvimp & \\
1472 \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 &
1473 \end{eqnarray}
1474
1475 \begin{eqnarray}
1476 \label{eq:lem:ccil0:sidv0:sgdu0:01:05}
1477 v & = & \sum_{i=0}^{n-1} v_i b^i \\
1478 \label{eq:lem:ccil0:sidv0:sgdu0:01:06}
1479 & = & v_{n-1} b^{n-1} + v_{n-2} b^{n-2} + \ldots{} + v_2 b^2 + v_1 b + v_0
1480 \end{eqnarray}
1481
1482 \begin{equation}
1483 \label{eq:lem:ccil0:sidv0:sgdu0:01:07}
1484 (v_{n-1} = v_{n-1})
1485 \vworkhimp
1486 v_{n-1} b^{n-1} \leq v \leq v_{n-1} b^{n-1} + b^{n-1} - 1
1487 \end{equation}
1488
1489 (\ref{eq:lem:ccil0:sidv0:sgdu0:01:04}) and
1490 (\ref{eq:lem:ccil0:sidv0:sgdu0:01:07}) reflect the uncertainties in the
1491 values of $u$ and $v$ respectively because only the first digit(s) of
1492 $u$ and $v$ are being considered in forming the estimate $\hat{q}$.
1493
1494 By definition, the actual value of $q$ is $\lfloor{}u/v\rfloor$. For a
1495 rational function $f(u,v) = u/v$ where $u \in [u_{min}, u_{max}]$ and
1496 $v \in [v_{min}, v_{max}]$, the minimum value of $u/v$ occurs at
1497 $u_{min}/v_{max}$, and the maximum value of $u/v$ occurs at
1498 $u_{max}/v_{min}$. We can therefore write that
1499
1500 \begin{equation}
1501 \label{eq:lem:ccil0:sidv0:sgdu0:01:08}
1502 \left\lfloor{\frac{(u_n b + u_{n-1}) b^{n-1}}{v_{n-1} b^{n-1} + b^{n-1} - 1}}\right\rfloor
1503 \leq
1504 q
1505 \leq
1506 \left\lfloor{\frac{(u_n b + u_{n-1}) b^{n-1} + b^{n-1} - 1}{v_{n-1} b^{n-1}}}\right\rfloor .
1507 \end{equation}
1508
1509 In other words, knowledge of $u_{n}$, $u_{n-1}$, and $v_{n-1}$ confines $q$ to the
1510 interval indicated in (\ref{eq:lem:ccil0:sidv0:sgdu0:01:08}). We must prove that,
1511 given a specific $u_{n}$, $u_{n-1}$, and $v_{n-1}$, $\hat{q}$ is at least as large as
1512 the upper bound in (\ref{eq:lem:ccil0:sidv0:sgdu0:01:08}); otherwise we could find a
1513 $q$ such that $q > \hat{q}$. We can algebraically manipulate the upper bound in
1514 in (\ref{eq:lem:ccil0:sidv0:sgdu0:01:08}) to yield
1515
1516 \begin{equation}
1517 \label{eq:lem:ccil0:sidv0:sgdu0:01:09}
1518 \left\lfloor{\frac{(u_n b + u_{n-1}) b^{n-1}}{v_{n-1} b^{n-1} + b^{n-1} - 1}}\right\rfloor
1519 \leq
1520 q
1521 \leq
1522 \left\lfloor{\frac{u_n b + u_{n-1} + \frac{b^{n-1}-1}{b^{n-1}}}{v_{n-1}}}\right\rfloor .
1523 \end{equation}
1524
1525 In (\ref{eq:lem:ccil0:sidv0:sgdu0:01:09}), since $(b^{n-1}-1)/b^{n-1} < 1$ and since
1526 $u_n b + u_{n-1}$ is an integer, we can conclude that
1527 $\lfloor u_n b + u_{n-1} + (b^{n-1}-1)/b^{n-1} \rfloor = \lfloor u_n b + u_{n-1} \rfloor$
1528 and hence that
1529
1530 \begin{equation}
1531 \label{eq:lem:ccil0:sidv0:sgdu0:01:10}
1532 q
1533 \leq
1534 \left\lfloor{\frac{u_n b + u_{n-1} + \frac{b^{n-1}-1}{b^{n-1}}}{v_{n-1}}}\right\rfloor
1535 =
1536 \left\lfloor{\frac{u_n b + u_{n-1}}{v_{n-1}}}\right\rfloor
1537 =
1538 \hat{q} .
1539 \end{equation}
1540
1541 Therefore, $\hat{q} \geq q$.
1542 \end{vworklemmaproof}
1543 \vworklemmafooter{}
1544
1545 Lemma \ref{lem:ccil0:sidv0:sgdu0:01} establishes that
1546 a digit estimate $\hat{q}$ based on the first digit of the
1547 divisor $v$ can be no less than the actual digit $q$, i.e.
1548 $\hat{q}-q \geq 0$. However, we must also establish an upper bound
1549 on $\hat{q}-q$.
1550
1551 Intuitively, based on
1552 (\ref{eq:lem:ccil0:sidv0:sgdu0:01:06}), we might guess that
1553 if $v_{n-1}$ is small, the estimate $\hat{q}$ may be quite
1554 poor, as the interval to which the actual value of $v$ is confined
1555 may be quite large. This fact is the basis for the normalization
1556 step [\ref{enumstep:alg:ccil0:sidv0:sgdu0:01:01}] in Algorithm
1557 \ref{alg:ccil0:sidv0:sgdu0:01}. We now prove a useful result
1558 for how much $u, v$ must be normalized so that $\hat{q}-q \leq 2$.
1559
1560 \begin{vworklemmastatementpar}{Normalization Requirement So That
1561 \mbox{\boldmath$\hat{q} - q \leq 2$}}
1562 \label{lem:ccil0:sidv0:sgdu0:02}
1563 If $v_{n-1} \geq \lfloor b/2 \rfloor$ and $\hat{q}$ is chosen as
1564 indicated in (\ref{eq:ccil0:sidv0:sgdu0:01}), then
1565 $0 \leq \hat{q} - q \leq 2$.
1566 \end{vworklemmastatementpar}
1567 \begin{vworklemmaproof}
1568 The lower limit on $\hat{q} - q$ is proved in Lemma \ref{lem:ccil0:sidv0:sgdu0:01}.
1569 We now seek only to prove that $\hat{q} - q \leq 2$.
1570 By definition of $\hat{q}$ and $q$,
1571
1572 \begin{equation}
1573 \label{eq:lem:ccil0:sidv0:sgdu0:02:01}
1574 \hat{q} - q = \left\lfloor {\frac{u_n b + u_{n-1}}{v_{n-1}}} \right\rfloor
1575 - \left\lfloor {\frac{u}{v}} \right\rfloor
1576 \end{equation}
1577
1578 When only nonnegative integers are involved,
1579 (\cmtnzeroxrefhyphen\ref{eq:cmtn0:sfcf0:02})
1580 supplies an exact expression for the floor of a
1581 ratio of integers. Using (\cmtnzeroxrefhyphen\ref{eq:cmtn0:sfcf0:02}),
1582 (\ref{eq:lem:ccil0:sidv0:sgdu0:02:01}) can be decomposed into
1583
1584 \begin{equation}
1585 \label{eq:lem:ccil0:sidv0:sgdu0:02:02}
1586 \hat{q} - q = \frac{u_n b + u_{n-1}}{v_{n-1}}
1587 - \frac{(u_n b + u_{n-1}) \bmod v_{n-1}}{v_{n-1}}
1588 - \frac{u}{v}
1589 + \frac{u \bmod v}{v} .
1590 \end{equation}
1591
1592 \noindent{}Note that (\ref{eq:lem:ccil0:sidv0:sgdu0:02:02}) is an exact
1593 expression (rather than an
1594 inequality).
1595
1596 Note in (\ref{eq:lem:ccil0:sidv0:sgdu0:02:02}) that
1597 $(u_n b + u_{n-1}) \bmod v_{n-1} \in [0, v_{n-1}-1]$, and that in general
1598 there is no reason to expect it cannot be zero. Thus, we can assume that
1599 it \emph{is} zero, which will maximize $\hat{q}-q$. We can thus convert
1600 (\ref{eq:lem:ccil0:sidv0:sgdu0:02:02}) into the inequality
1601
1602 \begin{equation}
1603 \label{eq:lem:ccil0:sidv0:sgdu0:02:03}
1604 \hat{q} - q \leq \frac{u_n b + u_{n-1}}{v_{n-1}}
1605 - \frac{u}{v}
1606 + \frac{u \bmod v}{v} .
1607 \end{equation}
1608
1609 In (\ref{eq:lem:ccil0:sidv0:sgdu0:02:03}) we can also observe that
1610 $(u \bmod v)/v \in [0, (v-1)/v]$. If we replace this expression with
1611 ``1'' (which is unattainable, but barely), this will change the relational
1612 operator from ``$\leq$'' to ``$<$'':
1613
1614 \begin{equation}
1615 \label{eq:lem:ccil0:sidv0:sgdu0:02:04}
1616 \hat{q} - q < \frac{u_n b + u_{n-1}}{v_{n-1}}
1617 - \frac{u}{v}
1618 + 1 .
1619 \end{equation}
1620
1621 The result we wish to show is that with $v_{n-1} \geq \lfloor b/2 \rfloor$,
1622 $\hat{q}-q \leq 2$. To simplify the subsequent algebraic manipulations, note in
1623 (\ref{eq:lem:ccil0:sidv0:sgdu0:02:04}) that
1624
1625 \begin{eqnarray}
1626 \label{eq:lem:ccil0:sidv0:sgdu0:02:05}
1627 & \hat{q} - q \leq 2 & \\
1628 \nonumber & \vworkvertequiv & \\
1629 \label{eq:lem:ccil0:sidv0:sgdu0:02:06}
1630 & \displaystyle \frac{u_n b + u_{n-1}}{v_{n-1}}
1631 - \frac{u}{v}
1632 + 1 \leq 3 & \\
1633 \nonumber & \vworkvertequiv & \\
1634 \label{eq:lem:ccil0:sidv0:sgdu0:02:07}
1635 & \displaystyle \frac{u_n b + u_{n-1}}{v_{n-1}}
1636 - \frac{u}{v} \leq 2 &
1637 \end{eqnarray}
1638
1639 (\ref{eq:lem:ccil0:sidv0:sgdu0:02:06}) may be counterintuitive, so
1640 further explanation is offered here. Since $\hat{q} \in \vworkintset$ and $q \in \vworkintset$,
1641 $\hat{q}-q \in \vworkintset$. Thus, proving
1642 (\ref{eq:lem:ccil0:sidv0:sgdu0:02:06}) or
1643 (\ref{eq:lem:ccil0:sidv0:sgdu0:02:07}) proves that
1644 $\hat{q}-q \in \{ \ldots, -1, 0, 1, 2 \}$ (however, by
1645 Lemma \ref{lem:ccil0:sidv0:sgdu0:01}, $\hat{q}-q \geq 0$, so in fact
1646 what would be proved is that $\hat{q}-q \in \{ 0, 1, 2 \}$). For
1647 algebraic simplicity,
1648 we choose to prove (\ref{eq:lem:ccil0:sidv0:sgdu0:02:07}).
1649
1650 First, adjust numerator and denominator of the first term in
1651 (\ref{eq:lem:ccil0:sidv0:sgdu0:02:07}) by $b^{n-1}$ so that the terms more closely
1652 resemble $u$ and $v$ in
1653 (\ref{eq:lem:ccil0:sidv0:sgdu0:01:02})
1654 and
1655 (\ref{eq:lem:ccil0:sidv0:sgdu0:01:06}):
1656
1657 \begin{equation}
1658 \label{eq:lem:ccil0:sidv0:sgdu0:02:08}
1659 \frac{u_n b^n + u_{n-1} b^{n-1}}{v_{n-1} b^{n-1}}
1660 - \frac{u}{v} \leq 2 .
1661 \end{equation}
1662
1663 For logical implication to be maintained,
1664 we must make the most pessimistic choices and assumptions possible in
1665 (\ref{eq:lem:ccil0:sidv0:sgdu0:02:08}) in order to maximize the value
1666 of the left side of the inequality.
1667 The first assumption to be made is the error in estimating
1668 $u$ and $v$ based on their most significant digits. It can be
1669 seen that (\ref{eq:lem:ccil0:sidv0:sgdu0:02:08}) will be maximized if:
1670
1671 \begin{itemize}
1672 \item We assume that $u = u_{n} b^n + u_{n-1} b^{n-1}$ (i.e. that we estimate
1673 $u$ precisely).
1674 \item We assume that $v = v_{n-1} b^{n-1} + b^{n-1} - 1$ (i.e. that
1675 we underestimate $v$ by the maximum amount possible).
1676 \item We minimize the value of $v_{n-1} b^{n-1}$.
1677 \end{itemize}
1678
1679 Assuming that $u$ is estimated precisely yields
1680
1681 \begin{equation}
1682 \label{eq:lem:ccil0:sidv0:sgdu0:02:09}
1683 \frac{u}{v_{n-1} b^{n-1}}
1684 - \frac{u}{v} \leq 2 .
1685 \end{equation}
1686
1687 Assuming that $v$ is underestimated by the maximum amount possible
1688 yields
1689
1690 \begin{equation}
1691 \label{eq:lem:ccil0:sidv0:sgdu0:02:10}
1692 \frac{u}{v - b^{n-1} + 1}
1693 - \frac{u}{v} \leq 2 .
1694 \end{equation}
1695
1696 Finally, with $b$ and $v$ fixed, $u$ can be maximized by noting that
1697 $u \leq bv - 1$ (by the problem assumption that the quotient is a single digit).
1698 However, for algebraic simplicity, we make the substitution $u=bv$ (rather than
1699 $u=bv-1$), since the weaker upper bound is strong enough to prove the
1700 first result we seek.
1701
1702 \begin{equation}
1703 \label{eq:lem:ccil0:sidv0:sgdu0:02:11}
1704 \frac{bv}{v - b^{n-1} + 1}
1705 - \frac{bv}{v} \leq 2
1706 \end{equation}
1707
1708 \begin{equation}
1709 \label{eq:lem:ccil0:sidv0:sgdu0:02:12}
1710 \frac{bv}{v - b^{n-1} + 1}
1711 - b \leq 2
1712 \end{equation}
1713
1714 Solving (\ref{eq:lem:ccil0:sidv0:sgdu0:02:12})
1715 for $v$ yields
1716
1717 \begin{equation}
1718 \label{eq:lem:ccil0:sidv0:sgdu0:02:13}
1719 v \geq \frac{b^n}{2} + b^{n-1} - \frac{1}{b} - 1
1720 \end{equation}
1721
1722 Again using the assumption that $v$ is underestimated by the maximum amount
1723 possible, we may make the substitution that $v = v_{n-1} b^{n-1} + b^{n-1} -1$,
1724 leading to
1725
1726 \begin{equation}
1727 \label{eq:lem:ccil0:sidv0:sgdu0:02:13b}
1728 v_{n-1} \geq \frac{b}{2} - \frac{1}{2 b^{n-2}} .
1729 \end{equation}
1730
1731 There are two cases to consider: $b$ even and $b$ odd. If $b$ is even, the
1732 proof is complete, as $\lfloor b/2 \rfloor = b/2$ and the choice of
1733 $v_{n-1} = \lfloor b/2 \rfloor$ will automatically satisfy
1734 (\ref{eq:lem:ccil0:sidv0:sgdu0:02:13b}). However, if $b$ is odd,
1735 $\lfloor b/2 \rfloor = b/2 - 1/2 < b/2 - 1/2b^{n-2}$, violating
1736 (\ref{eq:lem:ccil0:sidv0:sgdu0:02:13b}),
1737 and so we need to
1738 further examine this case.
1739
1740 If $b$ is odd and $v_{n-1} = \lfloor b/2 \rfloor$, then
1741 $v_{n-1} = b/2 - 1/2$, violating (\ref{eq:lem:ccil0:sidv0:sgdu0:02:13b}).
1742 However, any larger choice of $v_{n-1}$ (such as
1743 $\lfloor b/2 \rfloor + 1$, $\lfloor b/2 \rfloor + 2$, etc.) satisfies
1744 (\ref{eq:lem:ccil0:sidv0:sgdu0:02:13b}); so that it remains only to prove
1745 the $v_{n-1} = \lfloor b/2 \rfloor = b/2 - 1/2$
1746 case.
1747
1748 If $v_{n-1} = \lfloor b/2 \rfloor = b/2 - 1/2$, then
1749
1750 \begin{eqnarray}
1751 \label{eq:lem:ccil0:sidv0:sgdu0:02:14}
1752 v & \in & \left[
1753 \left( \frac{b}{2} - \frac{1}{2}\right) b^{n-1},
1754 \left( \frac{b}{2} - \frac{1}{2}\right) b^{n-1} + b^{n-1} - 1
1755 \right] \\
1756 \nonumber & = &
1757 \left[
1758 \frac{b^n}{2} - \frac{b^{n-1}}{2},
1759 \frac{b^n}{2} + \frac{b^{n-1}}{2} -1
1760 \right] .
1761 \end{eqnarray}
1762
1763 Note in this case that the estimation error ($v - v_{n-1}b^{n-1}$) and the
1764 value of $v$ are not independent; and in fact it is this aspect
1765 of the problem that has led to the violation of
1766 (\ref{eq:lem:ccil0:sidv0:sgdu0:02:13b}) with $b$ odd and
1767 $v_{n-1} = \lfloor b/2 \rfloor$.
1768
1769 In order to prove the case of $b$ odd and $v = \lfloor b/2 \rfloor = b/2 - 1/2$,
1770 we must reexamine some simplifying assumptions made earlier in order to obtain
1771 tighter inequalities. In (\ref{eq:lem:ccil0:sidv0:sgdu0:02:02}), we can no
1772 longer accept the maximum of $(u \bmod v)/v$ as one; instead we construct the
1773 tighter inequality
1774
1775 \begin{eqnarray}
1776 \label{eq:lem:ccil0:sidv0:sgdu0:02:15}
1777 & \displaystyle \hat{q} - q \leq \frac{u_n b + u_{n-1}}{v_{n-1}}
1778 - \frac{u}{v}
1779 + \frac{u \bmod v}{v} & \\
1780 \nonumber & \vworkvimp & \\
1781 \label{eq:lem:ccil0:sidv0:sgdu0:02:16}
1782 & \displaystyle \hat{q} - q \leq \frac{u_n b + u_{n-1}}{v_{n-1}}
1783 - \frac{u}{v}
1784 + \frac{v-1}{v} , &
1785 \end{eqnarray}
1786
1787 which leads to
1788
1789 \begin{equation}
1790 \label{eq:lem:ccil0:sidv0:sgdu0:02:17}
1791 \frac{u_n b + u_{n-1}}{v_{n-1}}
1792 - \frac{u+1}{v}
1793 < 2 .
1794 \end{equation}
1795
1796 In order to maximize the left-hand side of
1797 (\ref{eq:lem:ccil0:sidv0:sgdu0:02:17}), we assume that we
1798 estimate $u$ exactly so that $u = u_n b^n + u_{n-1} b^{n-1}$,
1799 yielding
1800
1801 \begin{equation}
1802 \label{eq:lem:ccil0:sidv0:sgdu0:02:18}
1803 \frac{u}{v_{n-1} b^{n-1}}
1804 - \frac{u+1}{v}
1805 < 2 .
1806 \end{equation}
1807
1808 We also assume that $u$ is the maximum value
1809 possible, $u=bv-1$, leading to
1810
1811 \begin{equation}
1812 \label{eq:lem:ccil0:sidv0:sgdu0:02:19}
1813 \frac{bv-1}{v_{n-1} b^{n-1}}
1814 - b
1815 < 2 .
1816 \end{equation}
1817
1818 Finally, we assume that $v$ is the upper limit in
1819 (\ref{eq:lem:ccil0:sidv0:sgdu0:02:14}),
1820 $v=b^n/2 + b^{n-1}/2 - 1$, and substitute the known value of
1821 $v_{n-1}$ for the case being proved, $v_{n-1} = b/2-1/2$, yielding
1822
1823 \begin{equation}
1824 \label{eq:lem:ccil0:sidv0:sgdu0:02:20}
1825 \frac{b \left( \frac{b^n}{2} + \frac{b^{n-1}}{2} - 1 \right) - 1}
1826 {\left( \frac{b}{2} - \frac{1}{2} \right) b^{n-1}}
1827 - b
1828 < 2 .
1829 \end{equation}
1830
1831 Simplification of (\ref{eq:lem:ccil0:sidv0:sgdu0:02:20})
1832 will establish that it is always true. This completes the proof.
1833 \end{vworklemmaproof}
1834 \vworklemmafooter{}
1835
1836 Lemmas \ref{lem:ccil0:sidv0:sgdu0:01} and
1837 \ref{lem:ccil0:sidv0:sgdu0:02},
1838 standing alone, lead to a good implementation of
1839 division without any further results. If it is known that
1840 $0 \leq \hat{q} - q \leq 2$, Algorithm \ref{alg:ccil0:sidv0:sgdu0:01}
1841 can be trivially modified to only calculate
1842 $\hat{q}$ (omitting the additional tests in Step \ref{enumstep:alg:ccil0:sidv0:sgdu0:01:03}),
1843 and then
1844 to include up to two add-back steps
1845 (duplication of Step \ref{enumstep:alg:ccil0:sidv0:sgdu0:01:06}).
1846 Although such an algorithm would be
1847 satisfactory, it has the disadvantage that the add-back steps would
1848 be executed very frequently, slowing the algorithm substantially, especially
1849 for long operands.
1850 We now show that the additional tests in Step \ref{enumstep:alg:ccil0:sidv0:sgdu0:01:03} of
1851 Algorithm \ref{alg:ccil0:sidv0:sgdu0:01} can eliminate
1852 altogether the case of $\hat{q}-q = 2$ (Lemma \ref{lem:ccil0:sidv0:sgdu0:03}), and
1853 can with a probability close to unity eliminate the
1854 case of $\hat{q}-q = 1$ (Lemmas \ref{lem:ccil0:sidv0:sgdu0:04}
1855 and \ref{lem:ccil0:sidv0:sgdu0:05}). Together these tests, which are present in
1856 the statement of Algorithm \ref{alg:ccil0:sidv0:sgdu0:01},
1857 reduce add-back (Step \ref{enumstep:alg:ccil0:sidv0:sgdu0:01:06}) to rare occurrence, and create a more
1858 efficient algorithm than would be possible with the
1859 results of Lemmas \ref{lem:ccil0:sidv0:sgdu0:01} and \ref{lem:ccil0:sidv0:sgdu0:02} alone.
1860
1861 \begin{vworklemmastatementpar}
1862 {\mbox{\boldmath$\hat{q} v_{n-2} \leq b \hat{r} + u_{j+n-2} \vworkhimp 0 \leq \hat{q} - q \leq 1$}}
1863 \label{lem:ccil0:sidv0:sgdu0:03}
1864 If the divisor normalization requirement ($v_{n-1} \geq \lfloor b/2 \rfloor$) as specified in
1865 Step \ref{enumstep:alg:ccil0:sidv0:sgdu0:01:01} of
1866 Algorithm \ref{alg:ccil0:sidv0:sgdu0:01} is met, then
1867
1868 \begin{equation}
1869 \label{eq:lem:ccil0:sidv0:sgdu0:03:01}
1870 \hat{q} v_{n-2} \leq b \hat{r} + u_{j+n-2} \vworkhimp 0 \leq \hat{q} - q \leq 1 .
1871 \end{equation}
1872 \end{vworklemmastatementpar}
1873 \begin{vworklemmaproof}
1874 For reference, note that:
1875
1876 \begin{eqnarray}
1877 \label{eq:lem:ccil0:sidv0:sgdu0:03:02}
1878 u & = & u_{j+n} b^{j+n} + u_{j+n-1} b^{j+n-1} + \ldots{} + u_1 b + u_0 \\
1879 \label{eq:lem:ccil0:sidv0:sgdu0:03:03}
1880 v & = & v_{n-1} b^{n-1} + v_{n-2} b^{n-2} + \ldots{} + v_1 b + v_0
1881 \end{eqnarray}
1882
1883 By definition, we the remainder
1884 $\hat{r}$ has the value
1885 $\hat{r} = u_{j+n} b + u_{j+n-1} - \hat{q} v_{n-1}$. Substituting this value
1886 into (\ref{eq:lem:ccil0:sidv0:sgdu0:03:01}) produces
1887
1888 \begin{equation}
1889 \label{eq:lem:ccil0:sidv0:sgdu0:03:04}
1890 \hat{q} v_{n-2} \leq b (u_{j+n} b + u_{j+n-1} - \hat{q} v_{n-1}) + u_{j+n-2} ,
1891 \end{equation}
1892
1893 and solving for $\hat{q}$ yields
1894
1895 \begin{equation}
1896 \label{eq:lem:ccil0:sidv0:sgdu0:03:05}
1897 \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}}.
1898 \end{equation}
1899
1900 It is known from Lemma \ref{lem:ccil0:sidv0:sgdu0:01} that the type of estimate
1901 represented by the floor of the right-hand size of (\ref{eq:lem:ccil0:sidv0:sgdu0:03:05})
1902 can be no less than $q$, leading to
1903
1904 \begin{eqnarray}
1905 \label{eq:lem:ccil0:sidv0:sgdu0:03:06}
1906 & \displaystyle q \leq \hat{q}
1907 \leq
1908 \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 & \\
1909 \nonumber & \displaystyle \leq
1910 \frac{u_{j+n} b^2 + u_{j+n-1}b + u_{j+n-2}}{v_{n-1}b + v_{n-2}}. &
1911 \end{eqnarray}
1912
1913 Because $q, \hat{q} \in \vworkintset$, it is only necessary to prove that
1914
1915 \begin{equation}
1916 \label{eq:lem:ccil0:sidv0:sgdu0:03:07}
1917 \frac{u_{j+n} b^2 + u_{j+n-1}b + u_{j+n-2}}{v_{n-1}b + v_{n-2}} -
1918 \left\lfloor \frac{u}{v} \right\rfloor
1919 < 2
1920 \end{equation}
1921
1922 in order to prove that $\hat{q}-q \leq 1$. Using
1923 (\cmtnzeroxrefhyphen\ref{eq:cmtn0:sfcf0:02}),
1924 (\ref{eq:lem:ccil0:sidv0:sgdu0:03:07}) can be rewritten as
1925
1926 \begin{equation}
1927 \label{eq:lem:ccil0:sidv0:sgdu0:03:08}
1928 \frac{u_{j+n} b^2 + u_{j+n-1}b + u_{j+n-2}}{v_{n-1}b + v_{n-2}} -
1929 \frac{u}{v} -
1930 \frac{u \bmod v}{v}
1931 < 2 .
1932 \end{equation}
1933
1934 In order for implication to hold, we must make the most pessimistic
1935 assumptions about $u \bmod v$ (those which maximize it). The maximum value
1936 of $u \bmod v$ is $v-1$, leading to
1937
1938 \begin{equation}
1939 \label{eq:lem:ccil0:sidv0:sgdu0:03:09}
1940 \frac{u_{j+n} b^2 + u_{j+n-1}b + u_{j+n-2}}{v_{n-1}b + v_{n-2}} -
1941 \frac{u + 1}{v}
1942 < 1 .
1943 \end{equation}
1944
1945 In order to maximize the left side of (\ref{}),
1946 we must assume that $u$ is maximized, $v$ is minimized,
1947
1948
1949 \end{vworklemmaproof}
1950 \vworklemmafooter{}
1951
1952 \begin{vworklemmastatementpar}
1953 {\mbox{\boldmath$\hat{q} v_{n-2} > b \hat{r} + u_{n-2} \vworkhimp q < \hat{q}$}}
1954 \label{lem:ccil0:sidv0:sgdu0:04}
1955 Given $\hat{q} > 0$, an estimate of $q$, and the remainder
1956 based on the estimate, $\hat{r} = u_n b + u_{n-1} - \hat{q} v_{n-1}$,
1957
1958 \begin{equation}
1959 \label{eq:lem:ccil0:sidv0:sgdu0:04:01}
1960 \hat{q} v_{n-2} > b \hat{r} + u_{n-2} \vworkhimp \hat{q} > q .
1961 \end{equation}
1962 \end{vworklemmastatementpar}
1963 \begin{vworklemmaproof}
1964 We make the assumption that $v_{n-1}$ and $v_{n-2}$ are not both 0.
1965 $v_{n-1} > 0$ is guaranteed by
1966 the normalization of
1967 $v$ in Algorithm \ref{alg:ccil0:sidv0:sgdu0:01}.
1968
1969 \begin{equation}
1970 \label{eq:lem:ccil0:sidv0:sgdu0:04:02}
1971 \hat{q} v_{n-2} > b \hat{r} + u_{n-2}
1972 \end{equation}
1973
1974 \begin{equation}
1975 \label{eq:lem:ccil0:sidv0:sgdu0:04:03}
1976 \hat{q} v_{n-2} > b (u_n b + u_{n-1} - \hat{q} v_{n-1}) + u_{n-2}
1977 \end{equation}
1978
1979 Solving (\ref{eq:lem:ccil0:sidv0:sgdu0:04:03}) for $\hat{q}$ yields
1980
1981 \begin{equation}
1982 \label{eq:lem:ccil0:sidv0:sgdu0:04:04}
1983 \hat{q}
1984 >
1985 \frac{u_n b^2 + u_{n-1} b + u_{n-2}}{v_{n-1} b + v_{n-2}}
1986 \geq
1987 \left\lfloor {\frac{u_n b^2 + u_{n-1} b + u_{n-2}}{v_{n-1} b + v_{n-2}}} \right\rfloor
1988 .
1989 \end{equation}
1990
1991 Note that the right-hand term of
1992 (\ref{eq:lem:ccil0:sidv0:sgdu0:04:04})
1993 is similar in form to the estimate $\hat{q}$ in
1994 Lemma \ref{lem:ccil0:sidv0:sgdu0:01}, where it is proved that
1995 $\hat{q} \geq q$. It is possible to use identical algebraic technique
1996 as is used in Lemma \ref{lem:ccil0:sidv0:sgdu0:01} in order to prove that
1997
1998 \begin{equation}
1999 \label{eq:lem:ccil0:sidv0:sgdu0:04:05}
2000 \left\lfloor {\frac{u_n b^2 + u_{n-1} b + u_{n-2}}{v_{n-1} b + v_{n-2}}} \right\rfloor
2001 \geq q,
2002 \end{equation}
2003
2004 and it follows that
2005
2006 \begin{equation}
2007 \label{eq:lem:ccil0:sidv0:sgdu0:04:06}
2008 \hat{q}
2009 >
2010 \frac{u_n b^2 + u_{n-1} b + u_{n-2}}{v_{n-1} b + v_{n-2}}
2011 \geq
2012 \left\lfloor {\frac{u_n b^2 + u_{n-1} b + u_{n-2}}{v_{n-1} b + v_{n-2}}} \right\rfloor
2013 \geq q,
2014 \end{equation}
2015
2016 and thus $\hat{q} > q$.
2017 \end{vworklemmaproof}
2018 \vworklemmafooter{}
2019
2020 \begin{vworklemmastatementpar}
2021 {Add-back occurs with approximate probability \mbox{\boldmath$2/b$}}
2022 \label{lem:ccil0:sidv0:sgdu0:05}
2023 The estimate of $q$ provided by (\ref{eq:ccil0:sidv0:sgdu0:01}),
2024 \end{vworklemmastatementpar}
2025 \begin{vworklemmaproof}
2026 \end{vworklemmaproof}
2027 \vworklemmafooter{}
2028
2029
2030 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2031 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2032 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2033 \subsection{Division Of Signed Operands}
2034
2035
2036 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2037 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2038 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2039 \subsection{Large Dividends With Machine-Native Divisors}
2040 \label{ccil0:sidv0:sldm0}
2041
2042 Division of arbitrary-sized operands (Section \ref{ccil0:sidv0:sgdu0}) is
2043 a costly operation. In many practical applications, we are able to exploit
2044 data sizes of operands or special relationships between the values of
2045 operands to use the instruction set of the machine more effectively.
2046 In this subsection, we investigate what optimizations we may achieve when:
2047
2048 \begin{itemize}
2049 \item We wish to calculate the quotient and remainder of
2050 unsigned integers $p$ and $q$: $p/q$ and
2051 $p \bmod{} q$; \emph{and}
2052 \item The machine possesses unsigned division instructions
2053 which provide both a quotient and a remainder from
2054 a division; \emph{and}
2055 \item The bitsize of the divisor $q$ is not larger than can
2056 be accomodated (as a divisor) by machine division instructions.
2057 \end{itemize}
2058
2059 Processors which possess integer division instructions usually
2060 possess one of two types of instructions:
2061
2062 \begin{itemize}
2063 \item Instructions where the the divisor, quotient and remainder are
2064 $Q$ bits, but the dividend is $2Q$ bits (we call these
2065 ``large dividend'' instructions). For example, an
2066 instruction which accepts a 16-bit dividend and an
2067 8-bit divisor to produce an 8-bit quotient and an 8-bit remainder is
2068 typical.
2069 With such instructions, overflow is possible, and is always detectable.
2070 However, in this subsection we never describe algorithms which detect
2071 overflow---instead, we arrange for data values which cannot generate an
2072 overflow.
2073 \item Instructions where the dividend, divisor, quotient, and remainder
2074 are all $Q$ bits (we call these ``small dividend'' instructions).
2075 With such instructions, overflow is not possible.
2076 \end{itemize}
2077
2078 We call the bitsize $Q$ a \emph{chunk}. We use \emph{chunk} rather than
2079 \emph{word} because the chunksize and wordsize in general are not
2080 required to be the same.
2081
2082 For the remainder of this discussion, we assume large dividend
2083 instructions (the first category above).
2084 The algorithms developed can be implemented on small dividend machines
2085 by halving data sizes so that the divisor fills no more than half
2086 of the available bits.
2087
2088 We assume that we are interested in calculating the integer quotient
2089 $\lfloor{}p/q\rfloor$ and remainder $p \bmod{} q$ of two unsigned
2090 integers $p$ and $q$, where $p$ is of size $P$ bits and $q$ is
2091 of size $Q$ bits. For simplicity and without detracting from the
2092 generality of the solution, we assume that $Q \vworkdivides{} P$.
2093
2094 We then seek to calculate
2095
2096 \begin{eqnarray}
2097 \label{eq:ccil0:sidv0:sldm0:001}
2098 \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]}} \\
2099 \nonumber & = & \frac{\sum_{i=0}^{P/Q-1} 2^{iQ} p_{[i]}}{q_{[0]}} .
2100 \end{eqnarray}
2101
2102 \noindent{}Using the integer identity
2103
2104 \begin{equation}
2105 \label{eq:ccil0:sidv0:sldm0:002}
2106 \frac{a}{b} = \left\lfloor{\frac{a}{b}}\right\rfloor + \frac{a \bmod b}{b} ,
2107 \end{equation}
2108
2109 \noindent{}we can reform (\ref{eq:ccil0:sidv0:sldm0:001}) into
2110
2111 \begin{eqnarray}
2112 \nonumber
2113 \frac{p}{q} & = & 2^{P-Q} \left\lfloor{\frac{p_{[P/Q-1]}}{q_{[0]}}}\right\rfloor \\
2114 \label{eq:ccil0:sidv0:sldm0:003}
2115 & + & 2^{P-Q} \frac{p_{[P/Q-1]}\bmod q_{[0]}}{q_{[0]}}
2116 + 2^{P-2Q} \frac{p_{[P/Q-2]}}{q_{[0]}} \\
2117 \nonumber & + & \frac{\sum_{i=0}^{P/Q-3} 2^{iQ} p_{[i]}}{q_{[0]}} ,
2118 \end{eqnarray}
2119
2120 \noindent{}which can be polished slightly to yield
2121
2122 \begin{eqnarray}
2123 \nonumber
2124 \frac{p}{q} & = & 2^{P-Q} \left\lfloor{\frac{p_{[P/Q-1]}}{q_{[0]}}}\right\rfloor \\
2125 \label{eq:ccil0:sidv0:sldm0:004}
2126 & + & 2^{P-2Q} \frac{2^Q (p_{[P/Q-1]}\bmod q_{[0]}) + p_{[P/Q-2]}}{q_{[0]}} \\
2127 \nonumber & + & \frac{\sum_{i=0}^{P/Q-3} 2^{iQ} p_{[i]}}{q_{[0]}} .
2128 \end{eqnarray}
2129
2130 Note in (\ref{eq:ccil0:sidv0:sldm0:004}) that the first term,
2131 $\lfloor{}p_{[P/Q-1]} / q_{[0]}\rfloor$, as well as
2132 a portion of the second term, $p_{[P/Q-1]}\bmod q_{[0]}$, can be
2133 calculated using a single machine division instruction with
2134 $p_{[P/Q-1]}$ as the dividend and $q_{[0]}$ as the divisor.
2135 Note also that multiplication of an integer by a power of 2
2136 can be achieved by placing the integer correctly within the
2137 result. In this regard note that $Q=8$ or $Q=16$ are
2138 the most typical cases, and so the placement can be achieved simply
2139 by selecting the correct memory address.
2140
2141 It is initially unclear whether we can evaluate or reduce the fraction in the
2142 second term of (\ref{eq:ccil0:sidv0:sldm0:004}),
2143 $[2^Q (p_{[P/Q-1]}\bmod q_{[0]}) + p_{[P/Q-2]}] / q_{[0]}$,
2144 using a single large dividend machine instruction, because
2145 the upper chunk of the dividend is populated with non-zero bits
2146 (specifically, $p_{[P/Q-1]}\bmod q_{[0]}$), and it seems that
2147 a division overflow may be possible. However, with some thought,
2148 it is clear that $p_{[P/Q-1]}\bmod q_{[0]} \leq q_{[0]} - 1$ and
2149 $p_{[P/Q-2]} \leq 2^Q - 1$, thus the largest numerator possible
2150 is $2^Q q_{[0]} - 1$, which, when divided by $q_{[0]}$, will result
2151 in a quotient and remainder of $2^Q - 1$. Thus, no division overflow
2152 can occur, and the fraction in the
2153 second term of (\ref{eq:ccil0:sidv0:sldm0:004}) can be evaluated
2154 using a large divisor integer machine instruction.
2155
2156 The fraction in the
2157 second term of (\ref{eq:ccil0:sidv0:sldm0:004}) can be simplified
2158 using (\ref{eq:ccil0:sidv0:sldm0:002}) to yield:
2159
2160 \begin{eqnarray}
2161 \nonumber
2162 \frac{p}{q} & = & 2^{P-Q} \left\lfloor{\frac{p_{[P/Q-1]}}{q_{[0]}}}\right\rfloor \\
2163 \label{eq:ccil0:sidv0:sldm0:005}
2164 & + & 2^{P-2Q} \left\lfloor{\frac{2^Q (p_{[P/Q-1]}\bmod q_{[0]}) + p_{[P/Q-2]}}{q_{[0]}}}\right\rfloor \\
2165 \nonumber & + & 2^{P-2Q} \frac{(2^Q (p_{[P/Q-1]}\bmod q_{[0]}) + p_{[P/Q-2]}) \bmod q_{[0]}}{q_{[0]}} \\
2166 \nonumber & + & \frac{\sum_{i=0}^{P/Q-3} 2^{iQ} p_{[i]}}{q_{[0]}} .
2167 \end{eqnarray}
2168
2169 The process of combining adjacent terms can be continued until all
2170 divisions and modulo operations necessary can be carried out using
2171 long dividend division instructions. If we envision a
2172 long-dividend division instruction as a functional block that
2173 accepts a $2Q$-bit dividend and a $Q$-bit divisor to produce a
2174 $Q$-bit quotient and a $Q$-bit remainder
2175 (Figure \ref{fig:ccil0:sidv0:sldm0:00}), then we can draw the
2176 entire division as outlined by (\ref{eq:ccil0:sidv0:sldm0:005})
2177 as shown in Figure \ref{fig:ccil0:sidv0:sldm0:01}.
2178
2179 \begin{figure}
2180 \centering
2181 \includegraphics[width=4.6in]{c_cil0/lddvblk.eps}
2182 \caption{Long Dividend Division Machine Instruction As A Functional Block}
2183 \label{fig:ccil0:sidv0:sldm0:00}
2184 \end{figure}
2185
2186 \begin{figure}
2187 \centering
2188 \includegraphics[width=4.6in]{c_cil0/ldmnblk.eps}
2189 \caption{Long Dividend/Machine-Native Divisor Division In Functional Block Form}
2190 \label{fig:ccil0:sidv0:sldm0:01}
2191 \end{figure}
2192
2193 The following example illustrates how to apply the technique.
2194
2195 \begin{vworkexamplestatement}
2196 \label{ex:ccil0:sidv0:sldm0:01}
2197 Implement 32/8 unsigned division on the TMS370C8 processor, which is
2198 characterized by a 16/8 division instruction.
2199 \end{vworkexamplestatement}
2200 \begin{vworkexampleparsection}{Solution}
2201 It would be possible to prepare an implementation directly from
2202 Figure \ref{fig:ccil0:sidv0:sldm0:01}: however, it may be
2203 more instructive to work through a solution without the
2204 aid of this figure.
2205
2206 In the case of the TMS370C8, the chunk size $Q$ is 8 bits; therefore
2207 $Q=8$. The problem statement indicates that we must accept 32-bit dividends;
2208 therefore $P=32$. Thus
2209
2210 \begin{equation}
2211 \label{eq:ex:ccil0:sidv0:sldm0:01:001}
2212 p = 2^{24} p_{[3]} + 2^{16} p_{[2]} + 2^{8} p_{[1]} + p_{[0]}
2213 \end{equation}
2214
2215 \noindent{}and
2216
2217 \begin{equation}
2218 \label{eq:ex:ccil0:sidv0:sldm0:01:002}
2219 q = q_{[0]} .
2220 \end{equation}
2221
2222 \noindent{}Thus the quotient and remainder we would like to determine,
2223 $\lfloor p/q \rfloor$ and $p \bmod q$, can be obtained by repeated
2224 application of (\ref{eq:ccil0:sidv0:sldm0:002}) as shown
2225 in Equations (\ref{eq:ex:ccil0:sidv0:sldm0:01:003})
2226 through (\ref{eq:ex:ccil0:sidv0:sldm0:01:011}).
2227
2228 \begin{equation}
2229 \label{eq:ex:ccil0:sidv0:sldm0:01:003}
2230 \frac{p}{q}
2231 =
2232 \frac{2^{24} p_{[3]} + 2^{16} p_{[2]} + 2^{8} p_{[1]} + p_{[0]}}{q_{[0]}}
2233 \end{equation}
2234
2235 \begin{equation}
2236 \label{eq:ex:ccil0:sidv0:sldm0:01:004}
2237 \frac{p}{q}
2238 =
2239 2^{24} \frac{p_{[3]}}{q_{[0]}}
2240 +
2241 2^{16} \frac{p_{[2]}}{q_{[0]}}
2242 +
2243 2^{8} \frac{p_{[1]}}{q_{[0]}}
2244 +
2245 \frac{p_{[0]}}{q_{[0]}}
2246 \end{equation}
2247
2248 \begin{equation}
2249 \label{eq:ex:ccil0:sidv0:sldm0:01:005}
2250 \frac{p}{q}
2251 =
2252 2^{24} \left\lfloor{\frac{p_{[3]}}{q_{[0]}}}\right\rfloor
2253 +
2254 2^{24} \frac{(p_{[3]} \bmod q_{[0]})}{q_{[0]}}
2255 +
2256 2^{16} \frac{p_{[2]}}{q_{[0]}}
2257 +
2258 2^{8} \frac{p_{[1]}}{q_{[0]}}
2259 +
2260 \frac{p_{[0]}}{q_{[0]}}
2261 \end{equation}
2262
2263 \begin{equation}
2264 \label{eq:ex:ccil0:sidv0:sldm0:01:006}
2265 \frac{p}{q}
2266 =
2267 2^{24} \left\lfloor{\frac{p_{[3]}}{q_{[0]}}}\right\rfloor
2268 +
2269 2^{16} \frac{2^8 (p_{[3]} \bmod q_{[0]}) + p_{[2]}}{q_{[0]}}
2270 +
2271 2^{8} \frac{p_{[1]}}{q_{[0]}}
2272 +
2273 \frac{p_{[0]}}{q_{[0]}}
2274 \end{equation}
2275
2276 \begin{eqnarray}
2277 \label{eq:ex:ccil0:sidv0:sldm0:01:007}
2278 \frac{p}{q} & = & 2^{24} \left\lfloor{\frac{p_{[3]}}{q_{[0]}}}\right\rfloor
2279 +
2280 2^{16} \left\lfloor{\frac{2^8 (p_{[3]} \bmod q_{[0]}) + p_{[2]}}{q_{[0]}}}\right\rfloor \\
2281 \nonumber & + &
2282 2^{16} \frac{(2^8 (p_{[3]} \bmod q_{[0]}) + p_{[2]}) \bmod q_{[0]}}{q_{[0]}}
2283 +
2284 2^{8} \frac{p_{[1]}}{q_{[0]}}
2285 +
2286 \frac{p_{[0]}}{q_{[0]}}
2287 \end{eqnarray}
2288
2289 \begin{eqnarray}
2290 \label{eq:ex:ccil0:sidv0:sldm0:01:008}
2291 \frac{p}{q} & = & 2^{24} \left\lfloor{\frac{p_{[3]}}{q_{[0]}}}\right\rfloor
2292 +
2293 2^{16} \left\lfloor{\frac{2^8 (p_{[3]} \bmod q_{[0]}) + p_{[2]}}{q_{[0]}}}\right\rfloor \\
2294 \nonumber & + &
2295 2^{8} \frac{2^8((2^8 (p_{[3]} \bmod q_{[0]}) + p_{[2]}) \bmod q_{[0]}) + p_{[1]}}{q_{[0]}}
2296 +
2297 \frac{p_{[0]}}{q_{[0]}}
2298 \end{eqnarray}
2299
2300 \begin{eqnarray}
2301 \nonumber\frac{p}{q} & = & 2^{24} \left\lfloor{\frac{p_{[3]}}{q_{[0]}}}\right\rfloor
2302 +
2303 2^{16} \left\lfloor{\frac{2^8 (p_{[3]} \bmod q_{[0]}) + p_{[2]}}{q_{[0]}}}\right\rfloor \\
2304 \label{eq:ex:ccil0:sidv0:sldm0:01:009}
2305 & + &
2306 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 \\
2307 \nonumber & + &
2308 2^{8} \frac{(2^8((2^8 (p_{[3]} \bmod q_{[0]}) + p_{[2]}) \bmod q_{[0]}) + p_{[1]}) \bmod q_{[0]}}{q_{[0]}} \\
2309 \nonumber & + &
2310 \frac{p_{[0]}}{q_{[0]}}
2311 \end{eqnarray}
2312
2313 \begin{eqnarray}
2314 \nonumber\frac{p}{q} & = & 2^{24} \left\lfloor{\frac{p_{[3]}}{q_{[0]}}}\right\rfloor
2315 +
2316 2^{16} \left\lfloor{\frac{2^8 (p_{[3]} \bmod q_{[0]}) + p_{[2]}}{q_{[0]}}}\right\rfloor \\
2317 \label{eq:ex:ccil0:sidv0:sldm0:01:010}
2318 & + &
2319 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 \\
2320 \nonumber & + &
2321 \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]}}
2322 \end{eqnarray}
2323
2324 \begin{eqnarray}
2325 \nonumber & \displaystyle \frac{p}{q} = 2^{24} \left\lfloor{\frac{p_{[3]}}{q_{[0]}}}\right\rfloor
2326 +
2327 2^{16} \left\lfloor{\frac{2^8 (p_{[3]} \bmod q_{[0]}) + p_{[2]}}{q_{[0]}}}\right\rfloor & \\
2328 \label{eq:ex:ccil0:sidv0:sldm0:01:011}
2329 & \displaystyle +
2330 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 & \\
2331 \nonumber & \displaystyle +
2332 \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 + & \\
2333 \nonumber
2334 & \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]}}
2335 &
2336 \end{eqnarray}
2337
2338 Note several things about the implementation suggested by
2339 (\ref{eq:ex:ccil0:sidv0:sldm0:01:011}):
2340
2341 \begin{itemize}
2342 \item No addition or multiplication is required to calculate terms such as
2343 $2^8 (p_{[3]} \bmod q_{[0]}) + p_{[2]}$. The high-order byte of the
2344 large dividend can be stuffed with $p_{[3]} \bmod q_{[0]}$ and
2345 the low-order byte with $p_{[2]}$.
2346 \item No addition or multiplication is required to calculate the
2347 result $\lfloor p/q \rfloor$.
2348 Note in (\ref{eq:ex:ccil0:sidv0:sldm0:01:011}) that the results are
2349 conveniently grouped as bytes with multipliers of $2^{24}$,
2350 $2^{16}$, $2^8$, and $2^0=1$. The terms can simply be placed into
2351 the appropriate byte, as a way of multplication by the appropriate
2352 power of 2. Note also that each term is guaranteed to be
2353 $\in \{0, 1, 2, \ldots{} , 255\}$, by the argument presented
2354 earlier for (\ref{eq:ccil0:sidv0:sldm0:004}). Thus, the
2355 addition will result in no carries, and each result byte can simply
2356 be placed directly in the correct memory location---addition is
2357 not necessary.
2358 \item Four machine division instructions are required, and the remainder
2359 is produced automatically by the fourth instruction.
2360 \end{itemize}
2361
2362 An implemenation for the TMS370C8 is supplied as Figure
2363 \ref{fig:ex:ccil0:sidv0:sldm0:01:01}. A block diagram of the data
2364 flow for this implementation is supplied as
2365 Figure \ref{fig:ex:ccil0:sidv0:sldm0:01:02}.
2366 \end{vworkexampleparsection}
2367 \vworkexamplefooter{}
2368
2369 \begin{figure}
2370 \begin{verbatim}
2371 ;Assume that byte memory locations p3, p2, p1, and p0 contain the
2372 ;32-bit unsigned dividend, and byte q0 contains the 8-bit unsigned
2373 ;divisor. Assume also that the result quotient will be placed
2374 ;in byte memory locations d3, d2, d1, and d0; and that the
2375 ;remainder will be placed in the byte memory location r0. Further
2376 ;assume that all memory locations are in the register file (near).
2377 CLR A ;High-order chunk of large divisor
2378 ;must be 0.
2379 MOV p3, B ;Load the low-order chunk of divisor.
2380 DIV q0, A ;Perform the first division.
2381 MOV A, d3 ;Quotient becomes this part of the
2382 ;result.
2383 MOV B, A ;Remainder becomes high-order chunk of
2384 ;next division.
2385 MOV p2, B ;Next byte becomes low-order chunk.
2386 DIV q0, A ;Do the second division.
2387 MOV A, d2 ;Quotient becomes this part of the
2388 ;result.
2389 MOV B, A ;Remainder becomes high-order chunk of
2390 ;next division.
2391 MOV p1, B ;Next byte becomes low-order chunk.
2392 DIV q0, A ;Do the third division.
2393 MOV A, d1 ;Quotient becomes this part of the
2394 ;result.
2395 MOV B, A ;Remainder becomes high-order chunk of
2396 ;next division.
2397 MOV p0, B ;Next byte becomes low-order chunk.
2398 DIV q0, A ;Do the fourth division.
2399 MOV A, d0 ;Quotient becomes this part of the
2400 ;result.
2401 MOV B, r0 ;This is the remainder, which could be used
2402 ;for rounding.
2403 \end{verbatim}
2404 \caption{TMS370C8 Code Snippet Illustrating Unsigned 32/8
2405 Division Using Unsigned 16/8
2406 Machine Instructions (Example \ref{ex:ccil0:sidv0:sldm0:01})}
2407 \label{fig:ex:ccil0:sidv0:sldm0:01:01}
2408 \end{figure}
2409
2410 \begin{figure}
2411 \centering
2412 \includegraphics[width=4.6in]{c_cil0/t370dmp.eps}
2413 \caption{Block Diagram Of Data Flow Of Figure \ref{fig:ex:ccil0:sidv0:sldm0:01:01}}
2414 \label{fig:ex:ccil0:sidv0:sldm0:01:02}
2415 \end{figure}
2416
2417
2418 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2419 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2420 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2421 \section{Miscellaneous Integer Mappings}
2422 %Section tag: MIM0
2423 \label{ccil0:smim0}
2424
2425 Embedded system work and ROM constraints often inspire a great deal
2426 of cleverness in the selection of instructions to perform mappings or
2427 tests. In this section, we discuss integer mappings (i.e. functions)
2428 for which economical implementations are known; and in the next section
2429 (Section \ref{ccil0:smit0})
2430 we discuss integer tests for which economical implementations are known.
2431
2432 To the best of our knowledge, there is no way to derive these mappings
2433 and tests---they have been collected from many software developers and
2434 come from human intuition and experience.
2435
2436
2437 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2438 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2439 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2440 \subsection{Lowest-Order Bit}
2441 %Subsection tag: LIB0
2442 \label{ccil0:smim0:slib0}
2443
2444 \index{lowest-order bit}
2445 \index{least significant bit}
2446
2447 The mapping
2448
2449 \texttt{mask = x \& -x}
2450
2451 \noindent{}is the most economical way known to extract the
2452 lowest-order bit set in an integer \texttt{x}, or
2453 0 if no bits are set.\footnote{This mapping was contributed by
2454 David Baker (\texttt{bakerda@engin.umich.edu})
2455 and Raul Selgado (\texttt{rselgado@visteon.com}).} Since most processors have an instruction to form the
2456 two's complement of an integer, this mapping usually requires only
2457 two arithmetic instructions.
2458
2459 When implementing this mapping in assembly-language on processors without a
2460 two's complement instruction, two other possible implementations are:
2461
2462 \begin{itemize}
2463 \item \texttt{mask = x \& ($\sim$x + 1)}
2464 \item \texttt{mask = x \& ((x \^{ } -1) + 1)}
2465 \end{itemize}
2466
2467
2468 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2469 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2470 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2471 \section{Miscellaneous Integer Tests}
2472 %Section tag: MIT0
2473 \label{ccil0:smit0}
2474
2475 \subsection{Power Of 2}
2476 %Subsection tag: PTW0
2477 \label{ccil0:smit0:sptw0}
2478
2479 \index{power of two}
2480 \index{2N@$2^N$}
2481
2482 The test
2483
2484 \texttt{(x \& (x-1) == 0) \&\& (x != 0)}
2485
2486 \noindent{}is the most economical way known to
2487 test whether an integer is a positive power of two
2488 (1, 2, 4, 8, 16, etc.).\footnote{The test appeared as part of
2489 a discussion on
2490 the GMP mailing list in 2002.}
2491
2492
2493 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2494 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2495 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2496 \section{Exercises}
2497
2498 \begin{vworkexercisestatement}
2499 \label{exe:ccil0:sexe0:01}
2500 Show that any $m$-bit two's complement integer $u_{[m-1:0]}$ except
2501 $-2^{m-1}$ can be negated by forming the one's complement, then adding one.
2502 \end{vworkexercisestatement}
2503
2504
2505
2506 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2507 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2508 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2509 \vfill
2510 \noindent\begin{figure}[!b]
2511 \noindent\rule[-0.25in]{\textwidth}{1pt}
2512 \begin{tiny}
2513 \begin{verbatim}
2514 $HeadURL$
2515 $Revision$
2516 $Date$
2517 $Author$
2518 \end{verbatim}
2519 \end{tiny}
2520 \noindent\rule[0.25in]{\textwidth}{1pt}
2521 \end{figure}
2522
2523 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2524 %
2525 %End of file C_CIL0.TEX

Properties

Name Value
svn:eol-style native
svn:keywords Author Date Id Revision URL Header

dashley@gmail.com
ViewVC Help
Powered by ViewVC 1.1.25