Hi Everyone,

I finally got around to looking it up. The book I have uses this method:

Where x is the number to divide by 3
(In C)

result = (x >> 2) + (x >> 4) + (x >> 6) + (x >> 8)

Problem with this method is that the result is always too small. It would work
better if you converted the source number to fixed point, and the result of the
division could be rounded somehow, and converted back to an integer. Of course,
we are dealing with a PIC that only works with 8 bits at a time.


Later,

Eric

P.S. I got this method out of a game programming book, which is why it is meant
for 32-bit integers.




______________________________ Reply Separator _________________________________
Subject: Re: divide by 3
Author:  Peter van Hoof <pvh@microserve.net> at INTERNET
Date:    2/28/98 9:02 AM


SO! use the fast method BUT start with shifting left a number of times and
shift back afterwards , always the easiest way to reduce rounding errors in
integer calculations

Peter

-----Original Message-----
From: Ray Gardiner <ray@NETSPACE.NET.AU>
To: PICLIST@MITVMA.MIT.EDU <PICLIST@MITVMA.MIT.EDU>
Date: Saturday, February 28, 1998 1:55 AM
Subject: Re: divide by 3


>>> 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
>>
>>Ray:
>>
>>It doesn't work that way.  With integer division, x/2 - x/4 is NOT
>>necessarily equal to x/4.
>>
>>An example:
>>
>>    X = 15.
>>
>>    My method computes X/2 - X/4 = 15/2 - 15/4
>>                                 = 7 - 3
>>                                 = 4.
>>
>>    Your method computes X/4 = 3.
>>
>>    Note that 4 is not equal to 3.
>>
>
>I stand corrected, to use the simplified version you need to
>keep the remainders of each division so that you can round
>the result correctly. If I re-write as follows....
>
>    X/3 = (X*256/4 + X*256/16 + X*256/64 + X*256/256 +128 )/256
>
>which becomes...
>
>    X/3 = (X*64 + X*16 + X*4 + X + 128)/256
>
>
>I think the rounding errors become minimal. (not proven)
>
>The interesting point (which I missed completely!) was that
>with your method the rounding errors tend to cancel.
>
>
>Ray Gardiner (DSP Systems) ray@dsp-systems.com http://www.dsp-systems.com
>private email to:- ray@netspace.net.au
>