Correction to divide-by-shifting algorithm
garyg at tekchips.UUCP
garyg at tekchips.UUCP
Wed Jan 11 05:30:29 AEST 1984
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
More information about the Comp.lang.c
mailing list