>Ray Gardiner <PICLIST@MITVMA.MIT.EDU> wrote:
>
>> Andy Warren provided the following....
>> > -----------------------------------------------------------------
>> >
>> >Here's a BASIC program to do a more-or-less correct division; it
>> >uses the fact that x/3 = x/2 - x/4 + x/8 - x/16 + x/32 - x/64....:
>> >
>> > basic program snipped
>> >
>>
>> You can do this twice as fast (8 bit precision) Using...
>>
>>     1/3 = 1/4 + 1/16 + 1/64 + 1/256...
>
>
>Ray:
>
>If you try that method, I think you'll find that the rounding errors
>are too large to give acceptable results.
>
>-Andy
>

Actually, the rounding errors are the same in both cases. I derived
the algorithm by simplifying yours, as follows.

        x/2   - x/4     = x/4
        x/8   - x/16    = x/16
        x/32  - x/64    = x/64
        x/128 - x/256   = x/256


So both algorithms are computationally equivalent. Except the
simplified version is twice as fast.

The algorithm can also be derived from Brian Schousek's solution X*85/256
by observing that 85 is 64+16+4+1, I should have explained further.

        If the first step is to multiply by 85 then divide by 256
        then..

        X*85 = X*64 + X*16 + X*4 + X*1

        Now divide by 256

        X*64/256 + X*16/256 + X*4/256 + X*1/256

        Which of course gives..

        X/4 + X/16 + X/64 + X/256

        The rounding error will be X ( 1/3 - 85/256) or
        X*0.0013 which is about 0.3 of a bit in the worst
        case.





Ray Gardiner (DSP Systems) ray@dsp-systems.com http://www.dsp-systems.com
private email to:- ray@netspace.net.au