DEDOUREK@unb (09/21/87)
Relative to the discussion of shifts to optimize divisions by powers
of 2, I wish to clarify the one message which warned of dire
consequences.
Consider the case of -3 / 2 and assume that the machine in question
uses two's complement representation of negative numbers. This
division has two possible "correct" answers, depending on your
definition of division.
-3 / 2 = Quotient of -1 and remainder of -1
(Most machines produce this answer)
-3 / 2 = Quotient of -2 and remainder of +1
(This answer produced by "unusual" machines, e.g.
GE/PAC 4060.)
Now one can argue that EITHER answer is CORRECT in the sense that
the divisor times the quotient plus the remainder produces the
divident, i.e.
( 2 * -1 ) + ( -1 ) = -3
( 2 * -2 ) + ( +1 ) = -3
Now consider dividing by shifting:
-3 / 2
in binary is
1111...1101 shift right by 1
which gives
111...110
which is -2, that is the second interpretation.
Now, the usual definition of "compiler optimization" is that the
result of the optimized program should be the same as the
unoptimized. Therefore, if your machine produces the first
answer for division, DO NOT OPTIMIZE DIVISION BY A POWER OF TWO
BY GENERATING A SHIFT. Note that this applies to integers.
Cardinals can always use the shift.
John DeDourek
Professor of Computer Science
School of Computer Science
University of New Brunswick
P.O. Box 4400
Fredericton, New Brunswick, CANADA E3B 5A3
(506) 453-4566
Electronic mail:
DEDOUREK@UNBMVS1.BITNET -- BITNET/NETNORTH