www.piclist.com/techref/method/math.htm?key=divide

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

See also: www.piclist.com/techref/method/math.htm?key=divide