Truncated match.
PICList
Thread
'16bit divide by 10'
1996\05\28@154852
by
David E. Queen
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.
1996\05\28@173722
by
fastfwd
David E. Queen <spam_OUTPICLISTTakeThisOuTMITVMA.MIT.EDU> wrote:
> 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.
David:
Didn't I just post a divideby5 routine here? Oh, well... Must have
been that other PIC list.
Here's a 16bit divideby10 algorithm (y = x/10):
y = x/4
for i = 1 to 7
y = x  y
y = y/4
next i
y = y/2
This works for both signed and unsigned x; if you can deal with a
very slight rounding error, you can speed the routine up by iterating
only 5 times, rather than 7.
Andy
Andrew Warren  .....fastfwdKILLspam@spam@ix.netcom.com
Fast Forward Engineering, Vista, California
http://www.geocities.com/SiliconValley/2499
1996\05\28@181109
by
Scott Dattalo

David E. Queen wrote:
>
> 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.
David,
I don't have a routine, but I do have an algorithm. In general, when you
find that you need to divide by a constant, it is often easier to multiply
by the reciprocal of that constant. For example, to divide by some X, we
can find the closest Y that satisfies the equation:
1/X = Y/ (2^n)
Then division by X is transformed to multiplication by Y followed by a shift
of n bits. Note that this is actually converting the fraction 1/X into a binary
fraction.
When X is an integer, then either Y will be an integer or will be a repeating
pattern (somewhat analogous to how 1/3 = .333333). If it is a repeating pattern,
then pray to the god of numbers that it is a simple one. Fortunately, 1/10 is a
very simple pattern:
1/10 = 0.00011001100110011001100110011001100 ..... (base 2)
This can be rewritten to emphasize the optimization:
1/10 = 2 * (3/16 + 3/256 + 3/4096 + ... + 3/(2^(4*m)) )
where m is an integer corresponding to how many terms you wish to keep. Or more
compactly:
i>infinity
___
\
1/10 = 6*/__ 2^(4*i)
i=1
This can be checked by using the formula for the sum of a geometric series:
i=k1
___ 1  r^k
\ 
/__ r^i = 1  r
i=0
In our case, r = 1/16. Taking into account the fact that our summation begins at
1
and not zero and also that k is infinity, we get
1/10 = 6* [1/ (1 1/16)  1] = 6 ( 16/15  1) = 1/10 (The check is good!)
We can also express the multiplications and divisions by shifting
X / 10 = 3 * (X>>4 + X>>8 + X>>12 + X>>16 + ...) << 2
Since you are only interested in 16 bit integers divided by 10 then all you need
are the first four terms. To reduce roundoff, you will want to rearrange this
slightly,
X / 10 ~ 3 * ((X<<12 + X<<8 + X<<4 + X) >> 17)
The following (untested) psuedo code implements the formula
int divby10(int X)
{
long Y;
int i;
Y = 0;
for(i=0; i<4; i++)
{
Y = Y + X;
X = X << 4;
}
Y = (Y + Y<<1) >> 17; /* i.e. Y*3/(2^17) */
return(Y);
}
Scott
1996\05\28@190959
by
James Musselman
Scott Dattalo wrote:
> 1/10 = 0.00011001100110011001100110011001100 ..... (base 2)
>
> This can be rewritten to emphasize the optimization:
> 1/10 = 2 * (3/16 + 3/256 + 3/4096 + ... + 3/(2^(4*m)) )
Isn't the above line wrong? Isn't 2 * 3/16 greater than 1/10? Or am I missing
something?
James
1996\05\28@193733
by
fastfwd
James Musselman <PICLISTKILLspamMITVMA.MIT.EDU> wrote:
> Scott Dattalo wrote:
>
> > 1/10 = 0.00011001100110011001100110011001100 ..... (base 2)
> >
> > This can be rewritten to emphasize the optimization:
> > 1/10 = 2 * (3/16 + 3/256 + 3/4096 + ... + 3/(2^(4*m)) )
>
> Isn't the above line wrong? Isn't 2 * 3/16 greater than 1/10? Or
> am I missing something?
You're not missing anything, James. Scott's explanation (and
ASCIIart equations) were all excellent, but he screwed up slightly
in that last line; it should be:
1/10 = 3 + 3/16 + 3/256 + 3/4096 + ... + 3/(2^(4*m))

32
Andy
Andrew Warren  .....fastfwdKILLspam.....ix.netcom.com
Fast Forward Engineering, Vista, California
http://www.geocities.com/SiliconValley/2499
1996\05\28@194155
by
Steve Hardy
> From: James Musselman <EraseMEjamesspam_OUTTakeThisOuTRADIXGROUP.COM>
>
> Scott Dattalo wrote:
>
> > 1/10 = 0.00011001100110011001100110011001100 ..... (base 2)
> >
> > This can be rewritten to emphasize the optimization:
> > 1/10 = 2 * (3/16 + 3/256 + 3/4096 + ... + 3/(2^(4*m)) )
>
> Isn't the above line wrong? Isn't 2 * 3/16 greater than 1/10? Or am I
missing
> something?
> James
>
Scott meant the initial coefficient to be 1/2 not 2. Scott
must have had an April 1 calculator since he also claimed that
> > 1/10 = 6* [1/ (1 1/16)  1] = 6 ( 16/15  1) = 1/10 (The check is good!)
SJH
1996\05\28@210412
by
Scott Dattalo

Steve Hardy wrote:
{Quote hidden}>
> > From: James Musselman <
jamesspam_OUTRADIXGROUP.COM>
> >
> > Scott Dattalo wrote:
> >
> > > 1/10 = 0.00011001100110011001100110011001100 ..... (base 2)
> > >
> > > This can be rewritten to emphasize the optimization:
> > > 1/10 = 2 * (3/16 + 3/256 + 3/4096 + ... + 3/(2^(4*m)) )
> >
> > Isn't the above line wrong? Isn't 2 * 3/16 greater than 1/10? Or am I
> missing
> > something?
> > James
> >
>
> Scott meant the initial coefficient to be 1/2 not 2. Scott
> must have had an April 1 calculator since he also claimed that
>
> > > 1/10 = 6* [1/ (1 1/16)  1] = 6 ( 16/15  1) = 1/10 (The check is good!)
The Derivative of r cubed divided by three.
With egg dripping off his face he confesses, "I inadvertantly propogated an
error." 8^(
If you're really interested, here are the corrections for Rev 1.0001:
This line is correct:
1/10 = 0.00011001100110011001100110011001100 ..... (base 2)
This line was incorrect:
> 1/10 = 2 * (3/16 + 3/256 + 3/4096 + ... + 3/(2^(4*m)) )
and should have been
1/10 = (3/16 + 3/256 + 3/4096 + ... + 3/(2^(4*m)) ) / 2
The summation is incorrect:
> i>infinity
> ___
> \
> 1/10 = 6*/__ 2^(4*i)
> i=1
And should have been
i>infinity
___
3 \
1/10 =  * /__ 2^(4*i)
2 i=1
The **check** was incorrect:
> 1/10 = 6* [1/ (1 1/16)  1] = 6 ( 16/15  1) = 1/10 (The check is good!)
and should have been
1/10 = 3* [1/ (1 1/16)  1]/2 = 3 ( 16/15  1)/2 = 1/10 (The check is good!)
((I think))
Sorry folks... I guess people do read this stuff.
So, as Steve points out, I inadvertantly was multiplying by two when I should
have been
dividing by two (thanks Steve). However the theory is sound.
BTW
Thomas Coonan wrote: (in Response to Andy's posting)
>
> So, what's your general problemsolving technique for this class of
> problem? Are you applying some basic number theory tricks about rational
> numbers, or is this trialnerror?
Yes.
Scott
PS
The answer is: r * dr * r. Get it? Hardyharhar. Sorry Steve, it's something I
stole
from the Simpsons.
1996\05\29@080115
by
John B C Walker
David,
Just a suggestion, use successive subtraction. I do when I divide a
11bit number by 7 for one of my projects. Works well.
J.W.
On Tue, 28 May 1996, David E. Queen wrote:
> 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.
>

Johnnie Walker
MSc Digital Systems Engineering
HeriotWatt University
email: @spam@ceejbcwKILLspamcee.hw.ac.uk
KILLspamceejbwKILLspampp.hw.ac.uk
www: http://www.cee.hw.ac.uk/~ceejbcw
tel: (0131) 343 2864
fax: (0131) 556 5501
_________________________________________________________________
1996\05\29@080945
by
John B C Walker
Sorry, just realised, successive subtraction only works for integer
answers, of course.
J.W.
> David E. Queen wrote:
> >
> > 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.
>

Johnnie Walker
MSc Digital Systems Engineering
HeriotWatt University
email: RemoveMEceejbcwTakeThisOuTcee.hw.ac.uk
spamBeGoneceejbwspamBeGonepp.hw.ac.uk
www: http://www.cee.hw.ac.uk/~ceejbcw
tel: (0131) 343 2864
fax: (0131) 556 5501
_________________________________________________________________
1996\05\30@141006
by
myke predko

>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 psuedocode:
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).
Myke
Myke
"We're Starfleet officers, weird is part of the job."
Capt. Catherine Janeway
'16bit divide by 10'
1996\06\05@210643
by
Tom Van Baak
>Scott Dattalo wrote:
>> Everyone knows a cat has 9 lives. We have used three
>> on this problem, so there are probably six more solutions
>> lurking out there.
>
If you're willing to call a 16x16 bit multiply subroutine you
can replace constant division with reciprocal multiplication.
Using C for this example:
typedef unsigned short UINT16;
typedef unsigned long UINT32;
//
// 16bit divide by 10 without division.
//
UINT16
DivideBy10 (
UINT16 Dividend
)
{
UINT16 Quotient;
UINT32 Temp;
Temp = (UINT32) Dividend;
Temp = (Temp * 52429) >> 19;
Quotient = (UINT16) Temp;
return Quotient;
>}
This technique is used by highperformance compilers since
a multiplication and a shift is almost always faster than
a division.
Tom
1996\06\11@160057
by
Scott Dattalo

David E. Queen wrote: (a few weeks ago)
>
> I can save 600bytes in a lookup table if I can figure out a good way to
> divide a 16 bit number by 10.
>
David,
Did you ever code a 16 bit divide by 10 routine? If so what did you end
up with?
Out of curiosity, I wrote a few versions. Here are some approximate cycle
and word counts:
Version 1: 50 cycles 50 words
Version 2: 90 cycles 40 words
Version 3: 136 cycles 14 words
Version 1 is an implementation of the solution I had originally posted.
Version 2 is an implementation of a variation of Andy Warren's solution.
Version 3 is an oldfashioned shift and subtract routine.
The first two versions exist only on paper. The third has been tested over
several, but not all 2^16 possible dividends.
N_hi equ 0x20
N_lo equ 0x21
count equ 0x22
R_hi equ 0x23
R_lo equ 0x24
;
;divby10
; Divides the unsigned integer N_hi:N_lo by the constant 10.
;
;Input
; N_lo  Low byte of the 16 bit dividend
; N_hi  High " "
;Output
; R_lo  Low byte of the result
; R_hi  High " "
;
; 14 words
; 149 cycles
divby10_ver3
CLRF R_lo ;Only need to clear R_lo. R_hi is cleared by
shifting(below)
MOVLW 13
MOVWF count ;
v3_1 MOVLW 0xa0 ;If the high byte is greater than or equal to
0xa0,
SUBWF N_hi,W ;then this subtraction causes no borrow (i.e.
C=1)
SKPNC
MOVWF N_hi ;Replace N_hi with N_hi  0xa0 if
RLF R_lo,F ;Shift result left one bit and
RLF R_hi,F ; pick up the carry bit in the process.
RLF N_lo,F ;Adjust N for the next iteration.
RLF N_hi,F
DECFSZ count,F
goto v3_1
RETURN
1996\06\11@204818
by
Scott Dattalo

Tom Van Baak wrote: (note: Tom did not send this to the PIC list)
>
> Is it me or does your divby10_ver3 fail on 16?
> >
No, it's me! I didn't take (==have) the time to test the routine thoroughly
enough during lunch. The problem was that under certain conditions, a borrow
was not occuring during the subtraction (when I was expecting one to occur).
To fix the problem, I shifted the input right one bit and divided by 0x50
instead
of 0xa0. I tested this version over more but still not all of the possible
values.
(16 was the first value I tested).
N_hi equ 0x20
N_lo equ 0x21
count equ 0x22
R_hi equ 0x23
R_lo equ 0x24
;
;divby10
; Divides the unsigned integer N_hi:N_lo by the constant 10.
;
;Input
; N_lo  Low byte of the 16 bit dividend
; N_hi  High " "
;Output
; R_lo  Low byte of the result
; R_hi  High " "
;
; 17 words
; 152 cycles
divby10_ver3
CLRC
RRF N_hi,F
RRF N_lo,F
CLRF R_lo ;Only need to clear R_lo. R_hi is cleared by
shifting(below)
MOVLW 13
MOVWF count ;
v3_1 MOVLW 0x50 ;If the high byte is greater than or equal to
0xa0,
SUBWF N_hi,W ;then this subtraction causes no borrow (i.e.
C=1)
SKPNC
MOVWF N_hi ;Replace N_hi with N_hi  0xa0 if
RLF R_lo,F ;Shift result left one bit and
RLF R_hi,F ; pick up the carry bit in the process.
RLF N_lo,F ;Adjust N for the next iteration.
RLF N_hi,F
DECFSZ count,F
goto v3_1
RETURN
Thanks Tom for catching this one.
Scott
PS. Next time, I'll make my butthead project manager insist I go to lunch.
Oops, sorry E. S., I meant that other butthead project manager.
More... (looser matching)
 Last day of these posts
 In 1996
, 1997 only
 Today
 New search...