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 To: 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 >