piclist 1996\05\30\141006a >
Thread: 16bit divide by 10
face BY : myke predko email (remove spam text)

>I can save 600bytes in a lookup table if I can figure out a good way to
>divide a 16 bit number by 10.
>I have the app notes with the general 16 math, but I need a smaller and
>faster routine.

As everybody was probably expecting, I have to put in my two cents worth and
drop in some code...

Here is a 16 bit unsigned division algorithm that I have used in the past.
Initially, it shifts the Divisor until bit 14 is set and then begins
shifting down.  If the divisor can be taken from the dividend, it is.  Next,
the divisor is shifted down until you get the initial divisor.  The results
(quotient and remainder) are all 16 bits long and an additional 8 bit
register is used in the example code below.

Here is the psuedo-code:

Count = 0                       - Count keeps track of where the Divisor is
Quotient = 0                    - Quotient is actually a 16 bit sum

while ( Divisor & 0x04000 ) != 0  - Find where to shift the Divisor up to
 Count = Count + 1             - Record How Many Bits Shifted
 Divisor = Divisor << 1        - Shift up the Divisor

while Count != 0                - Now, do the Shifting Subtraction (Division)
 if Dividend >= Divisor        - Can Subtract from the Result
   Quotient = Quotient + ( 2 ^ Count )
   Divident = Divident - Divisor
 Count = Count - 1
 Divisor = Divisor >> 1

That's it.  Divident contains the remainder and Quotient contains the
quotient of the value.  Note that this algorithm will go into an endless
loop if the divisor is equal to zero.  I stop the shifting up with bit 14 of
the Divisor so that signed values can be supported (even though this
algorithm won't work with negative values).

The PIC code for doing this is below.  Note, that I have changed the code in
two places.  The first is with regards to Count.  Rather than using a
counter, I shift a "1" up and down (ending the division when the "1" ends up
in the Carry Flag).  This means that I can add Count to the Quotient
directly.  The second area that I have changed is in regard to the
comparison of the Dividend to the Divisor, note that I save the contents of
the subtraction (compare) and use it later, rather than subtracting twice.

 clrf  Quotient                ;  Initialize the Variables
 clrf  Quotient + 1

 movlw 1                       ;  Instead of a Counter, Count is a shifted
 movwf Count                   ;  Value for adding to the Quotient
 clrf  Count + 1

StartLoop                       ;  Find the Top Value for the Divisor
 btfsc Dividend, 6             ;  If Bit 14 Set, then we have the value
  goto DivLoop

 bcf   STATUS, C               ;  Shift over the Carry and the Divisor
 rlf   Count
 rlf   Count + 1
 rlf   Divisor                 ;  Note, Carry will be Zero from Count
 rlf   Divisor + 1

 goto  StartLoop               ;  Now, see if we can shift again

DivLoop                         ;  Do the Shifted Subtraction
 movf  Divisor + 1, w          ;  Compare Values, High First
 subwf Dividend + 1, w
 movwf Temp                    ;  Save Result for later (just in case)
 movf  Divisor, w
 subwf Dividend
 btfss STATUS, C               ;  Make Sure Carry is accounted for
  decf Temp

 btfsc Temp, 7                 ;  Do we have a Negative Number from Subtract?
  goto DivSkip                 ;  Yes, Don't Subtract this value

 movwf Dividend                ;  Else, save the result for the Next
 movf  Temp, w                 ;   Subtract
 movwf Dividend

 movf  Count + 1, w            ;  Add the Bit Offset to the Quotient
 addwf Quotient + 1
 movf  Count, w
 addwf Quotient                ;  Don't have to worry about Carry

DivSkip                         ;  Now, Shift the Values Down

 bcf   STATUS, C               ;  Shift down the Divisor
 rrf   Divisor + 1
 rrf   Divisor

 rrf   Count + 1               ;  Now see if the Count is finished
 rrf   Count

 btfss STATUS, C               ;  Finished if Carry is Set
  goto DivLoop

Note that with this code, "Dividend" now contains the Remainder and
"Divisor" is the original "Divisor" >> 1.

In terms of space and execution speed, I think you'll find this to be a
pretty good improvement from the code in the ECBK (although not as good as
some of the algorithms other people have put in for a direct divide by 10).


"We're Starfleet officers, weird is part of the job."

Capt. Catherine Janeway

See also: www.piclist.com/techref/method/math.htm?key=divide
Reply You must be a member of the piclist mailing list (not only a www.piclist.com member) to post to the piclist. This form requires JavaScript and a browser/email client that can handle form mailto: posts.
Subject (change) 16bit divide by 10

month overview.

new search...