/[dtapublic]/pubs/papers/20070526_cpu08_divu16_by_u16/cpu08div16by16a.tex
ViewVC logotype

Annotation of /pubs/papers/20070526_cpu08_divu16_by_u16/cpu08div16by16a.tex

Parent Directory Parent Directory | Revision Log Revision Log


Revision 10 - (hide annotations) (download) (as text)
Fri Oct 7 03:23:35 2016 UTC (8 years, 1 month ago) by dashley
File MIME type: application/x-tex
File size: 22866 byte(s)
Commit of u16 = u16 / u16 analysis for the CPU08.
1 dashley 10 %$Header: /home/dashley/cvsrep/e3ft_gpl01/e3ft_gpl01/dtaipubs/cron/2007/cpu08div16by16a/cpu08div16by16a.tex,v 1.12 2007/05/26 18:25:46 dashley Exp $
2     %
3     \documentclass[letterpaper,10pt,titlepage]{article}
4     %
5     %\pagestyle{headings}
6     %
7     \usepackage{amsmath}
8     \usepackage{amsfonts}
9     \usepackage{amssymb}
10     \usepackage[ansinew]{inputenc}
11     \usepackage[OT1]{fontenc}
12     \usepackage{graphicx}
13     %\usepackage{makeidx}
14     %
15     %Contributed by Robin Fairbairns of the comp.text.tex newsgroup. I have no
16     %idea how it works ... but it gives a working \bdiv.
17     %
18     \makeatletter
19     \def\bdiv{%
20     \nonscript\mskip-\medmuskip\mkern5mu%
21     \mathbin{\operator@font div}\penalty900\mkern5mu%
22     \nonscript\mskip-\medmuskip}
23     \makeatother
24     %
25     %
26     \begin{document}
27     \title{Notes on Economical 16/16 = 16 Unsigned Integer Division on the Freescale CPU08}
28     \author{\vspace{1cm}\\David T. Ashley\\\texttt{dta@e3ft.com}\\\vspace{1cm}}
29     \date{\vspace*{8mm}\small{Version Control $ $Revision: 1.12 $ $ \\
30     Version Control $ $Date: 2007/05/26 18:25:46 $ $ (UTC) \\
31     $ $RCSfile: cpu08div16by16a.tex,v $ $ \\
32     \LaTeX{} Compilation Date: \today{}}}
33     \maketitle
34    
35     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
36     %
37     \begin{abstract}
38     This document contains my notes on attempting to optimize
39     the 16 = 16/16 unsigned integer division subroutine distributed with
40     a Freescale CPU08 compiler. I attempted to replace the standard
41     shift-compare-subtract algorithm with Knuth's algorithm.
42    
43     In the end, the attempt was mostly a failure. There seemed to be no way
44     to gain the execution time advantages of Knuth's algorithm without increasing
45     FLASH size. (The goal would have been to obtain more favorable
46     execution time \emph{and} FLASH size, rather than a tradeoff.)
47     \end{abstract}
48    
49     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
50    
51     \section{Introduction and Overview}
52     \label{siov0}
53    
54     The fundamental goal of practical computer integer arithmetic is to obtain
55     an exact result using machine instructions that are as fast and compact as
56     possible.
57    
58     For three of the four fundamental operations (addition, subtraction, and
59     multiplication), it is intuitively obvious to most programmers how to
60     use existing machine instructions to operate on operands that are larger
61     than the machine instructions can accommodate.
62    
63     The fourth fundamental operation (division), however, is less well understood
64     by a typical programmer than the other three. It is not obvious to most
65     programmers how to use machine division instructions to divide integers larger
66     than the native machine division instructions will accommodate.
67    
68     In 2007, I noticed that the integer division library functions associated with
69     a particular \emph{C} compiler were of the shift-compare-subtract variety.
70     As the CPU08 has a 16/16=8 native division instruction, I suspected but was not
71     sure that the 16/16=16 division function could be improved.
72    
73     Note that for a library function used by a \emph{C} compiler, it may not
74     be necessary (although it may be desirable) to calculate the quotient and the
75     remainder at the same time. An algorithm that calculates the quotient but
76     does not calculate the remainder, or vice-versa, may be acceptable for
77     use by compiled code.
78    
79     Although I haven't examined the \emph{C} standards, I doubt that there is
80     any special requirement for the quotient or remainder calculated when
81     the denominator is zero. The only requirement is probably that the calculation
82     not continue indefinitely (i.e. not an infinite loop).
83    
84     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
85    
86     \section{Nomenclature and Notation}
87     \label{snom0}
88    
89     I use the nomenclature ``16/16=16 division'' to denote a division function that
90     accepts a 16-bit unsigned numerator and a 16-bit unsigned denominator; and
91     produces either/both a 16-bit quotient and a 16-bit remainder.
92    
93     I use $n$ to denote the numerator, $d$ to denote the denominator, $q$ to denote
94     the integer quotient, and $r$ to denote the remainder.
95    
96     Any of the 16-bit quantities can be subscripted with ``H'' or ``L'' to denote
97     the most-significant or least-significant byte. For example,
98    
99     \begin{equation}
100     \label{eq:snom0:01}
101     n = 2^8 n_H + n_L .
102     \end{equation}
103    
104     Within any of the 16-bit quantities, bits are subscripted in the traditional fashion.
105     For example,
106    
107     \begin{equation}
108     \label{eq:snom0:02}
109     n = \sum_{i=0}^{15} 2^i n_i .
110     \end{equation}
111    
112     Within any of the 8-bit quantities, bits are also subscripted in the traditional fashion.
113     For example,
114    
115     \begin{equation}
116     \label{eq:snom0:03}
117     n = 2^8 \sum_{i=0}^{7} 2^i n_{H_i} + \sum_{i=0}^{7} 2^i n_{L_i}
118     = \sum_{i=0}^{7} 2^{i+8} n_{H_i} + \sum_{i=0}^{7} 2^i n_{L_i} .
119     \end{equation}
120    
121     Because only non-negative integers are involved, \emph{floor()} and
122     \emph{div} are used interchangeably, i.e.
123    
124     \begin{equation}
125     \label{eq:snom0:04}
126     \left\lfloor \frac{a}{b} \right\rfloor = a \bdiv b, \;\; a,b \geq 0 .
127     \end{equation}
128    
129     An identity that is frequently used in this document is
130    
131     \begin{eqnarray}
132     \label{eq:snom0:05}
133     \frac{a}{b} & = & a \bdiv b + \frac{a \bmod b}{b} \\
134     \label{eq:snom0:06}
135     & = & \left\lfloor \frac{a}{b} \right\rfloor + \frac{a \bmod b}{b} .
136     \end{eqnarray}
137    
138    
139     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
140    
141     \section{Analysis of Existing Code}
142     \label{saec0}
143    
144     This section presents an analysis of the behavior and characteristics of
145     the existing code.
146    
147    
148     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
149    
150     \subsection{Listing}
151     \label{saec0:slec0}
152    
153     The existing code is reproduced below, with line numbers.
154    
155     \begin{verbatim}
156     001: c_umod:
157     002: bsr c_udiv ; divide
158     003: pshh ; transfer MSB
159     004: pula ; in place
160     005: sta c_reg
161     006: txa ; LSB in place
162     007: rts ; and return
163     008: ;
164     009: c_udiv:
165     010: psha ; save NL
166     011: pshh ; DH on the stack
167     012: tst 1,sp ; test zero
168     013: bne full ; full division
169     014: pulh ; clean stack
170     015: cpx c_reg ; compare DL with NH
171     016: bls half ; half division
172     017: lda c_reg ; NH
173     018: psha ; in
174     019: pulh ; H
175     020: pula ; NL in A
176     021: div ; DL in X, divide
177     022: clr c_reg ; QH is zero
178     023: fini:
179     024: pshh ; move RL
180     025: pulx ; in X
181     026: clrh ; RH is zero
182     027: rts ; and return
183     028: half:
184     029: lda c_reg ; NH in A
185     030: clrh ; 1st divide 8 X 8
186     031: div ; divide
187     032: sta c_reg ; QH in place
188     033: pula ; complete dividend with NL
189     034: div ; divide
190     035: bra fini ; complete remainder
191     036: full:
192     037: pshx ; save DL
193     038: ldx #8 ; counter
194     039: clra ; Extention
195     040: pshx ; save on
196     041: psha ; the stack
197     042: tsx ; stack addressed by H:X
198     043: bcl:
199     044: lsl 4,x ; shift E:NH:NL
200     045: rol c_reg ; left
201     046: rola
202     047: sta 0,x ; store E
203     048: cmp 3,x ; compare DH
204     049: blo next ; too low, continue
205     050: bne ok ; ok to subtract
206     051: lda c_reg ; compare NH
207     052: sub 2,x ; with DL
208     053: bhs ok2 ; ok, complete result
209     054: lda 0,x ; restore value
210     055: bra next ; and continue
211     056: ok:
212     057: lda c_reg ; substract D
213     058: sub 2,x ; from E:NH
214     059: ok2:
215     060: sta c_reg ; in place
216     061: lda 0,x
217     062: sbc 3,x
218     063: inc 4,x ; set result bit
219     064: next:
220     065: dbnz 1,x,bcl ; count down and loop
221     066: sta 0,x ; store E
222     067: pulh ; RH in place
223     068: ais #3 ; clean up stack
224     069: ldx c_reg ; RL in place
225     070: pula ; QL in place
226     071: clr c_reg ; QH is zero
227     072: rts ; and return
228     \end{verbatim}
229    
230    
231     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
232    
233     \subsection{Algorithmic Analysis}
234     \label{saec0:saan0}
235    
236     The algorithm is divided into two cases:
237    
238     \begin{itemize}
239     \item Case I: $d_H = 0$ (lines 14-35).
240     \item Case II: $d_H > 0$ (lines 36-72).
241     \end{itemize}
242    
243    
244     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
245    
246     \subsubsection{Case I}
247     \label{saec0:saan0:scas0}
248    
249     In the case of $d_H = 0$, the division is 16/8:
250    
251     \begin{eqnarray}
252     \label{eq:saec0:saan0:scas0:01}
253     \frac{2^8 n_H + n_L}{d_L} & = & \frac{2^8 n_H}{d_L} + \frac{n_L}{d_L} \\
254     \label{eq:saec0:saan0:scas0:02}
255     & = & 2^8 \left( n_H \bdiv d_L + \frac{n_H \bmod d_L}{d_L} \right) + \frac{n_L}{d_L} \\
256     \label{eq:saec0:saan0:scas0:03}
257     & = & 2^8 (n_H \bdiv d_L) + \frac{2^8 (n_H \bmod d_L) + n_L}{d_L}
258     \end{eqnarray}
259    
260     (\ref{eq:saec0:saan0:scas0:03}) is an exact expression involving rational numbers.
261     However, we don't want to calculate the left side of (\ref{eq:saec0:saan0:scas0:03});
262     rather, we wish to calculate its \emph{floor()}\@. Applying the
263     \emph{floor()} function to both sides of (\ref{eq:saec0:saan0:scas0:03}) yields:
264    
265     \begin{equation}
266     \label{eq:saec0:saan0:scas0:04}
267     \left\lfloor \frac{2^8 n_H + n_L}{d_L} \right\rfloor
268     =
269     2^8 (n_H \bdiv d_L) + \left\lfloor \frac{2^8 (n_H \bmod d_L) + n_L}{d_L} \right\rfloor .
270     \end{equation}
271    
272     Note that (\ref{eq:saec0:saan0:scas0:04}) is in a form
273     that can be readily evaluated using a processor with 16/8 division
274     capability; so long as
275    
276     \begin{equation}
277     \label{eq:saec0:saan0:scas0:05}
278     \frac{2^8 (n_H \bmod d_L) + n_L}{d_L} < 2^8 ,
279     \end{equation}
280    
281     \noindent{}a fact that can be easily verified by the reader.
282    
283     (\ref{eq:saec0:saan0:scas0:04}) can be readily evaluated by a processor with
284     16/8 division capability because such a division instruction always provides
285     both quotient and remainder. It is easy to see that (\ref{eq:saec0:saan0:scas0:04})
286     can be evaluated with a division, a re-staging of bytes, and a second division.
287    
288     If (\ref{eq:saec0:saan0:scas0:04}) is evaluated as suggested, it needs to be verified
289     whether the remainder of the second division is the same as the remainder
290     of the larger division, i.e.
291    
292     \begin{equation}
293     \label{eq:saec0:saan0:scas0:06}
294     (2^8 n_H + n_L) \bmod d_L =? ((2^8 \bmod d_L) + n_L) \bmod d_L.
295     \end{equation}
296    
297     The question of whether (\ref{eq:saec0:saan0:scas0:06}) is an
298     equality is the question of whether
299    
300     \begin{equation}
301     \label{eq:saec0:saan0:scas0:07}
302     ka \bmod b = (k (a \bmod b)) \bmod b .
303     \end{equation}
304    
305     In order to prove or disprove (\ref{eq:saec0:saan0:scas0:07}),
306     decompose $a$ into $ib + j$. Then, since $kib \bmod b = 0$,
307    
308     \begin{eqnarray}
309     \label{eq:saec0:saan0:scas0:08}
310     k (ib + j) \bmod b & = & k j \bmod b \\
311     \label{eq:saec0:saan0:scas0:09}
312     k j \bmod b & = & k j \bmod b .
313     \end{eqnarray}
314    
315     Thus, if (\ref{eq:saec0:saan0:scas0:04}) is evaluated as suggested (with
316     two divisions), the final remainder will be the same as the remainder for the
317     original division. (\ref{eq:saec0:saan0:scas0:04}) will, in fact, deliver both
318     the quotient and remainder economically.
319    
320     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
321    
322     \subsubsection{Case II}
323     \label{saec0:saan0:scas1}
324    
325     The case of $d_H > 0$ (\S{}\ref{saec0:slec0}, lines 36-72) is conventional
326     shift-compare-subtract division. Only eight iterations of the loop are required
327     because with $d_H > 0$, $d \geq 2^8$, and $n/d < 2^8$.
328    
329    
330     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
331    
332     \subsection{Timing Analysis}
333     \label{saec0:stan0}
334    
335     The code of \S{}\ref{saec0:slec0} is reproduced below, with instruction
336     timing (number of clocks) and FLASH requirements (number of bytes) added
337     as (clocks/bytes). It was determined that \emph{c\_reg} resides
338     in zero-page (i.e. \emph{direct}) memory.
339    
340     \begin{verbatim}
341     001: c_umod:
342     002: bsr c_udiv 4/2 ; divide
343     003: pshh ; transfer MSB
344     004: pula 2/1 ; in place
345     005: sta c_reg 3/2
346     006: txa 1/1 ; LSB in place
347     007: rts 4/1 ; and return
348     008: ;
349     009: c_udiv:
350     010: psha 2/1 ; save NL
351     011: pshh 2/1 ; DH on the stack
352     012: tst 1,sp 4/3 ; test zero
353     013: bne full 3/2 ; full division
354     014: pulh 2/1 ; clean stack
355     015: cpx c_reg 3/2 ; compare DL with NH
356     016: bls half 3/2 ; half division
357     017: lda c_reg 3/2 ; NH
358     018: psha 2/1 ; in
359     019: pulh 2/1 ; H
360     020: pula 2/1 ; NL in A
361     021: div 7/1 ; DL in X, divide
362     022: clr c_reg 3/2 ; QH is zero
363     023: fini:
364     024: pshh 2/1 ; move RL
365     025: pulx 2/1 ; in X
366     026: clrh 1/1 ; RH is zero
367     027: rts 4/1 ; and return
368     028: half:
369     029: lda c_reg 3/2 ; NH in A
370     030: clrh 1/1 ; 1st divide 8 X 8
371     031: div 7/1 ; divide
372     032: sta c_reg 3/2 ; QH in place
373     033: pula 2/1 ; complete dividend with NL
374     034: div 7/1 ; divide
375     035: bra fini 3/2 ; complete remainder
376     036: full:
377     037: pshx 2/1 ; save DL
378     038: ldx #8 2/2 ; counter
379     039: clra 1/1 ; Extention
380     040: pshx 2/1 ; save on
381     041: psha 2/1 ; the stack
382     042: tsx 2/1 ; stack addressed by H:X
383     043: bcl:
384     044: lsl 4,x 4/2 ; shift E:NH:NL
385     045: rol c_reg 4/2 ; left
386     046: rola 1/1
387     047: sta 0,x 2/1 ; store E
388     048: cmp 3,x 3/2 ; compare DH
389     049: blo next 3/2 ; too low, continue
390     050: bne ok 3/2 ; ok to subtract
391     051: lda c_reg 3/2 ; compare NH
392     052: sub 2,x 3/2 ; with DL
393     053: bhs ok2 3/2 ; ok, complete result
394     054: lda 0,x 2/1 ; restore value
395     055: bra next 3/2 ; and continue
396     056: ok:
397     057: lda c_reg 3/2 ; substract D
398     058: sub 2,x 3/2 ; from E:NH
399     059: ok2:
400     060: sta c_reg 3/2 ; in place
401     061: lda 0,x 2/1
402     062: sbc 3,x 3/2
403     063: inc 4,x 3/2 ; set result bit
404     064: next:
405     065: dbnz 1,x,bcl 5/3 ; count down and loop
406     066: sta 0,x 2/1 ; store E
407     067: pulh 2/1 ; RH in place
408     068: ais #3 2/2 ; clean up stack
409     069: ldx c_reg 3/2 ; RL in place
410     070: pula 2/1 ; QL in place
411     071: clr c_reg 3/2 ; QH is zero
412     072: rts 4/1 ; and return
413     \end{verbatim}
414    
415     There are three distinct timing cases for the \emph{c\_udiv} function:
416    
417     \begin{enumerate}
418     \item $d_H = 0$ and $n_H < d_L$:
419     47 clocks are required, representing straight flow of the
420     instructions from line 10 through line 27.
421     \item $d_H = 0$ and $n_H \geq d_L$: 54 clocks are required.
422     \item $d_H > 0$ and every bit of the quotient is 1, in which case
423     400 clocks are required. This represents 22 clocks up through
424     line 42, 45 clocks $\times$ 8 in the lines from 43 through 65, and
425     18 clocks in the lines from 66 through 72.
426     \end{enumerate}
427    
428    
429     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
430    
431     \subsection{FLASH/RAM Consumption Analysis}
432     \label{saec0:sfra0}
433    
434     From \S{}\ref{saec0:stan0}, 93 bytes of FLASH are used. Only one byte
435     of RAM is used (\emph{c\_reg}, probably shared with other functions
436     as well).
437    
438    
439     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
440    
441     \section{Potential Optimizations}
442     \label{spop0}
443    
444    
445     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
446    
447     \subsection{Potential Case I Optimizations}
448     \label{spop0:scas0}
449    
450     This section corresponds to \emph{Case I} of \S{}\ref{saec0:saan0:scas0}.
451    
452     The most obvious observation about the code (\S{}\ref{saec0:slec0}) is that
453     division instructions are very inexpensive on the CPU08---7 clock cycles,
454     or about 2 typical instructions. Branching based on
455     $n_H \geq d_L$
456     (\S{}\ref{saec0:slec0}, lines 15-16)
457     may cost more in the test, the branch, and in other
458     data transfer overhead than is saved. It may make sense to apply the
459     full formula in (\ref{eq:saec0:saan0:scas0:04}) in all cases where
460     $d_H = 0$.
461    
462     When $d_H = 0$, and if one assumes normal distribution of data, the expected
463     value of execution time is about $(47+54)/2 = 50.5$ clocks.\footnote{If the
464     data is assumed normally distributed, $n_H$ has about a 0.5 probability of being at least as large
465     as $d_L$.}
466    
467     The code below combines two of the three timing cases into one by ignoring the
468     relationship between $n_H$ and $d_L$.
469    
470     \begin{verbatim}
471     ;Condition at function entry:
472     ;N_H in 1,SP
473     ;N_L in A
474     ;D_H in H
475     ;D_L in X
476     ;
477     ;Condition at function exit:
478     ;Q_H in c_reg
479     ;Q_L in A
480     ;R_H in H
481     ;R_L in X
482     ;
483     c_udiv:
484     psha 2/1 ; save NL
485     pshh 2/1 ; DH on the stack
486     tst 1,sp 4/3 ; test zero
487     bne full 3/2 ; full division
488     ;
489     ;From here on we're committed to the division with
490     ;arbitary numerator, and denominator <= 255.
491     ; N_H at 3,sp
492     ; N_L at 2,sp
493     ; D_H at 1,sp
494     ;
495     clrh 1/1
496     lda 3,sp 4/3 ; H:A now contains N_H
497     div 7/1 ; divide
498     sta c_reg 3/2 ; QH in place
499     lda 2,sp 4/3 ; complete dividend with NL
500     div 7/1 ; divide. Q_L in A, R_L in H
501     pshh 2/1 ; move RL
502     pulx 2/1 ; in X
503     clrh 1/1 ; RH is zero
504     ais #3 2/2 ; clean stack
505     rts 4/1 ; and return
506     \end{verbatim}
507    
508     Although the code does raise the minimum execution time from 47 to
509     48 clocks:
510    
511     \begin{itemize}
512     \item It lowers the expected value of the $d_H=0$ execution time from
513     50.5 to 48 clocks.
514     \item It saves approximately 15 bytes of FLASH.
515     \end{itemize}
516    
517     This optimization is recommended.
518    
519    
520     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
521    
522     \subsection{Potential Case II Optimizations}
523     \label{spop0:scas1}
524    
525     This section corresponds to \emph{Case II} of \S{}\ref{saec0:saan0:scas1}.
526    
527     I sent an e-mail to an engineer at the compiler manufacturer indicating
528     that:
529    
530     \begin{itemize}
531     \item I believed \emph{Case I} could be optimized as indicated earlier
532     in the document.
533     \item I believed \emph{Case II} could be optimized by applying Knuth's
534     algorithm.
535     \end{itemize}
536    
537     The reply I received from the compiler manufacturer was that:
538    
539     \begin{itemize}
540     \item There was agreeement about \emph{Case I}.
541     \item \emph{Case II} may be a little faster using Knuth's algorithm, but would
542     definitely be larger (code used to evaluate the application of Knuth's
543     algorithm was also provided).
544     \end{itemize}
545    
546     In the test code provided by the compiler manufacturer, the approach used was
547     to obtain a trial quotient and then to subtract the divisor from the remainder
548     up to twice to adjust the quotient up to 2 counts downward (Knuth's algorithm).
549    
550     I did try a different approach (to iterate on the quotient and to reconstruct
551     $q \times d$ with decreasing $q$). This approach promised to be slightly more
552     compact because $q \times d$ reconstruction was reutilized. However, it worked out
553     to occupy about 153 bytes rather than 103 for the shift-compare-subtract
554     algorithm (timing was not examined). (This test code is version-controlled
555     in the same directory as this \LaTeX{} document.)
556    
557     At this point I agree with the
558     compiler manufacturer
559     that there is a tradeoff between size and speed (it seems
560     nearly impossible to get both).
561    
562     In any reimplementation of this algorithm, will probably need to choose between
563     size and speed. I believe there is some possibility to reduce the reimplementation
564     from 153 bytes, but not down to 103 bytes.
565    
566     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
567     \end{document}
568     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
569     % $Log: cpu08div16by16a.tex,v $
570     % Revision 1.12 2007/05/26 18:25:46 dashley
571     % Edits to incorporate final thoughts (for now) and test code results.
572     %
573     % Revision 1.11 2007/05/21 16:49:40 dashley
574     % \bdiv functionality as suggested by Robin Fairbairns added.
575     %
576     % Revision 1.10 2007/05/18 15:53:59 dashley
577     % Edits.
578     %
579     % Revision 1.9 2007/05/18 02:02:56 dashley
580     % Edits.
581     %
582     % Revision 1.8 2007/05/18 02:02:10 dashley
583     % Edits.
584     %
585     % Revision 1.7 2007/05/18 01:40:20 dashley
586     % Edits.
587     %
588     % Revision 1.6 2007/05/18 00:15:56 dashley
589     % Edits.
590     %
591     % Revision 1.5 2007/05/17 15:53:57 dashley
592     % Edits.
593     %
594     % Revision 1.4 2007/05/17 14:46:34 dashley
595     % Edits.
596     %
597     % Revision 1.3 2007/05/17 04:15:22 dashley
598     % Edits.
599     %
600     % Revision 1.2 2007/05/17 03:50:48 dashley
601     % Edits.
602     %
603     % Revision 1.1 2007/05/17 03:09:06 dashley
604     % Initial checkin.
605     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

dashley@gmail.com
ViewVC Help
Powered by ViewVC 1.1.25