garyg@tekchips.UUCP (01/10/84)
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