Andy Shaw wrote:
>
> Hi Folks,
> Does anyone out there have any code for a reasonably
> fast divide by 10 routine. I'm just looking for a rounded
> up 8 bit signed value as the result I don't need the
> remainder.
A little over a year ago we had this same discussion. I'll
post some of the pertinent (or at least interesting) results:
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 = (3/16 + 3/256 + 3/4096 + ... + 3/(2^(4*m)) ) / 2
where m is an integer corresponding to how many terms you wish to keep.
Or more compactly:
i->infinity
___
3 \
1/10 = --- * /__ 2^(-4*i)
2 i=1
This can be checked by using the formula for the sum of a geometric
series:
i=k-1
___ 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 = 3* [1/(1 - 1/16) - 1]/2 = 3 ( 16/15 - 1)/2 = 1/10
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 re-arrange this slightly,
X / 10 ~ 3 * ((X<<12 + X<<8 + X<<4 + X) >> 17)
Then after that,
Thomas Coonan wrote:
{Quote hidden}>
> >Here's a 16-bit divide-by-10 algorithm (y = x/10):
> >
> > y = x/4
> >
> > for i = 1 to 7
> > y = x - y
> > y = y/4
> > next i
> >
> > y = y/2
> I understand why powers of two are good... And I sort of see how you
> divide down close to the target before you do too much shifting...
>
> So, what's your general problem-solving technique for this class of
> problem? Are you applying some basic number theory tricks about rational
> numbers, or is this trial-n-error?
and
Andrew Warren wrote:
{Quote hidden}>
> In this case, my divide-by-10 code is just a divide-by-5 with an
> extra divide-by-2 tacked on at the end. I came up with the original
> divide-by-5 routine by noticing the following:
>
> x 4x x 5x
> --- = ----, and --- = ----.
> 5 20 4 20
>
> Therefore,
>
> x x x
> --- = --- - ----
> 5 4 20
>
> x x/4
> = --- - -------
> 4 5
>
> x (x/4) (x/4)/4
> = --- - ( ------- - --------- )
> 4 4 5
>
> etc...
>
Another way to skin Andy's cat is to return to the binary fraction of
x/5 and do some manipulation:
x
--- = 0.001100110011001100110011...
5
3 3 3 3
= x *( -- + --- + ---- + ... + ------ )
16 256 4096 2^(4*m)
= x * 3 * ( 1>>4 + 1>>8 + 1>>12 + ... + 1>>(4*m) ) (1)
Now, x * 3 can be rewritten as x<<2 - x (i.e. x*3 = x*4 - x)
x
--- = (x<<2 - x) * ( 1>>4 + 1>>8 + 1>>12 + ... + 1>>(4*m) )
5
= x * ( 1>>2 + 1>>6 + 1>>10 + ... + 1>>(4*m-2) ) -
x * ( 1>>4 + 1>>8 + 1>>12 + ... + 1>>(4*m) )
= x * ( 1>>2 - 1>>4 + 1>>6 - 1>>8 + 1>>10 -+ ... -+ 1>>(2*m) )
Now, assuming x is a 16 bit integer we only need to keep terms up to m=7
x
--- ~= x * ( 1>>2 - 1>>4 + 1>>6 - 1>>8 + 1>>10 - 1>>12 + 1>>14 )
5
= x * (1 - (1 - (1 - (1 - (1 - (1 - 1>>2)>>2)>>2)>>2)>>2)>>2)>>2
= (x - (x - (x - (x - (x - (x - x>>2)>>2)>>2)>>2)>>2)>>2)>>2
This is Andy's algorithm unrolled.
Just for grins, Pete Brink's cat can be skinned similarly:
First note that x * 3 can be rewritten as x<<1 + x. Substitute this
into equation (1) from above and you get:
x
--- = (x<<1 + x) * ( 1>>4 + 1>>8 + 1>>12 + ... + 1>>(4*m) )
5
= x * (1>>3 + 1>>4 + 1>>7 + 1>>8 + ... )
= (x>>3 + x>>4 + x>>7 + x>>8 + ...)
= (x + x>>1 + x>>4 + x>>5 + ...) >> 3
or,
x
--- = (x + x>>1 + x>>4 + x>>5 + ...) >> 4
10
------------------------------------------------------------
And finally, for grins I wrote a simply minded loop-and-divide-by-10
routine which is short in code space but takes a "long time" (which
is just as vague as "reasonable fast") to run:
;----------------------------------
;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
In another message, I alluded to the possibility of a 16bit-divide-by-
10 routine that would execute in 50 cycles. Maybe Dmitry will want
to take a whack at it?
I hope this is enough to keep you busy for a while.
Scott