piclist 1996\05\28\181109a >
Thread: 16bit divide by 10
www.piclist.com/techref/method/math.htm?key=divide
BY : Scott Dattalo email (remove spam text)

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=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 = 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 re-arrange 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
<31AB799F.3FC@unix.sri.com> 7bit