Looks like Andy beat me to it, but the roundoff error in the
second method is definitely quite attrocious. Here is an excerpt from a
table showing the difference.

                Alg1    Alg2
=========       ======  ======
255 / 3 =       85 (0)  81 (-4)
254 / 3 =       85 (1)  81 (-3)
253 / 3 =       84 (0)  81 (-3)
252 / 3 =       84 (0)  81 (-3)
251 / 3 =       84 (1)  80 (-3)
250 / 3 =       84 (1)  80 (-3)
249 / 3 =       83 (0)  80 (-3)
248 / 3 =       83 (1)  80 (-2)
247 / 3 =       82 (0)  79 (-3)
246 / 3 =       82 (0)  79 (-3)
245 / 3 =       81 (0)  79 (-2)
244 / 3 =       81 (0)  79 (-2)
243 / 3 =       81 (0)  78 (-3)
242 / 3 =       81 (1)  78 (-2)
241 / 3 =       80 (0)  78 (-2)
240 / 3 =       80 (0)  78 (-2)
239 / 3 =       80 (1)  76 (-3)

        The Alg1 column is using add and sub, while the Alg2 column uses
only add. ( The source for this program is attached).

        Matt

On Fri, 27 Feb 1998, Andrew Warren wrote:

> Ray Gardiner <PICLIST@MITVMA.MIT.EDU> wrote:
>
> > 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.
>
> -Andy
>
> === Andrew Warren - fastfwd@ix.netcom.com
> === Fast Forward Engineering - Vista, California
> === http://www.geocities.com/SiliconValley/2499
>

/*****************************************/
/* Matt Calder, Dept. of Statistics, CSU */
/* http://www.stat.colostate.edu/~calder */
/*****************************************/

Content-Type: TEXT/PLAIN; charset=US-ASCII; name="div3.c"
Content-ID: <Pine.SUN.3.96.980227095513.27526B@tlaloc.stat.colostate.edu>
Content-Description: Source to generate full table


#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main()
{
	int p, d1, d2, c;

	for (p=0; p < 100; p++) {
		
		d1 = (p >> 1) - (p >> 2) + 
		     (p >> 3) - (p >> 4) + 
                     (p >> 5) - (p >> 6) + 
                     (p >> 7) - (p >> 8);

		d2 = (p >> 2) + (p >> 4) + 
                     (p >> 6) + (p >> 8);

		c = floor(((double) p)/3.0 + 0.5);	

		printf("%d / 3 \t= %d\t%d \t(%d) \t%d \t(%d)\n", 
			p, c, d1, d1-c, d2, d2-c);
	}
}