Thomas Coonan wrote:
>
> >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
Everyone knows a cat has 9 lives. We have used three on this problem, so there
are probably six more solutions lurking out there.
Scott