Correction to divide-by-shifting algorithm

[garyg at tekchips.UUCP]

An algorithm recently submitted for substituting an arithmetic right shift 
for division of negative by powers of two is incorrect for two's complement 
arithmetic. It may also be noted that uncorrected numeric shifting to the 
right works fine for machines with signed magnitude or one's complement 
arithmetic (e.g., IBM 7094, Univac 1100 series).

The incorrect algorithm is...

		int x;
		unsigned int n;
		/* replace x/(2^n), n>=0 by ... */
		if(x < 0)
		    x += 1;
		x = x "arith_right_shift" n ;	/* where the divisor is 2^n */


The correct algorithm is...

		int x;
		unsigned int n;
		/* replace x/(2^n), n>=0, 2^n-1 <= maxint by ... */
		if(x < 0)
		    x += 2^n-1;
		x = x "arith_right_shift" n ;	/* where the divisor is 2^n */

In particular, try -31/8 or -32/8. The incorrect algorithm is provides correct
results only for -(2^n)-1, for n>0. Further simplification is necessary in
case of large values of n. Obviously, the final value of x is zero in 
those cases.

The theory behind this is that unless all the bits which will be lost are zero
(in which case the dividend is a negative power of two, which needs no 
correction and is unaffected by our addition), the quotient will be rounded
towards -infinity rather than towards zero, as desired. The addition of
'all one bits' in the fractional part will round it towards +infinity. Since
the number is negative, this is also equivalent to rounding towards zero.

This is another example of the problem of variables standing for storage
locations (a sequence of computational values through a sequence of machine
states) rather than a single computed value. The faulty algorithm may be
derived by wishing to correct the final value of x by 1. By confusing the 
initial value of x with the final value of x, one obtains this incorrect
algorithm. 

Gary Graunke

UUCP: decvax!tektronix!tekmdp!garygr
Voice: (503)-629-3081
USPS: Tektronix M.S. 92-525, P.O. Box 4600, Beaverton, OR 97077 USA