alan@allegra.UUCP (Alan S. Driscoll) (01/08/84)
From Roger Ferrel: What we see here with the: inttype *= 0.5; vs inttype = inttype * 0.5; is a weakness of most C compilers. It seems none of them handles float operations very well when there are mixed types. Of course the above is a poor example since normally more efficent code would be generated by using: inttype >>= 1; /* how is this for getting off the subject? */ From the C Reference Manual: The value of E1>>E2 is E1 right-shifted E2 bits. The right shift is guaranteed to be logical (0-fill) if E1 is unsigned; otherwise it may be arithmetic (fill by a copy of the sign bit). If the shift is logical, then negative values of "inttype" will give you interesting results. Alan S. Driscoll AT&T Bell Laboratories
rpw3@fortune.UUCP (01/09/84)
#R:allegra:-218900:fortune:16200015:000:1388
fortune!rpw3 Jan 9 03:19:00 1984
"Those who learn nothing from history are doomed to repeat it"
-- Santayana
"The only thing we learn from history is that we learn nothing
from history" -- Hegel
"I know guys can't learn from yesterday... Hegel must be taking
the long view" -- Brunner (as spoken by a character in Stand on Zanzibar)
Not only will "negative_int >> n" give you a terribly wrong answer
(compared to "negative_int / (2**n)") if your machine uses logical shift,
but it will give you an "off by one" answer if you use arithmetic shift
(unless negative_int happens to be minus a power of 2 bigger than "n").
(-5)/4 = -1 (correct integer division)
(-5) >> 2 = -2 (arithmetic shift)
Many compilers which try to "optimize" this case also blow it (hmmm...,
you might try yours). As many have discovered in the past (the hard way,
after the compiler was in the field), the correct algorithm for optimizing
division by powers of two is (in C pseudo-code):
if(x < 0)
x += 1;
x = x "arith_right_shift" n ; /* where the divisor is 2**n */
When the PDP-10 community was trying to make the move from the old F40
compiler to FORTRAN-10, this was a really hot issue. The new, "better"
compiler was the broken one (for a while).
Rob Warnock
UUCP: {sri-unix,amd70,hpda,harpo,ihnp4,allegra}!fortune!rpw3
DDD: (415)595-8444
USPS: Fortune Systems Corp, 101 Twin Dolphins Drive, Redwood City, CA 94065shah@fortune.UUCP (01/10/84)
#R:allegra:-218900:fortune:16200017:000:302 fortune!shah Jan 9 19:37:00 1984 +------- | "Those who learn nothing from history are doomed to repeat it" | -- Santayana | | "The only thing we learn from history is that we learn nothing | from history" -- Hegel +------- Conclusion: The only thing that we learn from history is that we are doomed to repeat it. Sigh....
henry@utzoo.UUCP (Henry Spencer) (01/11/84)
Rob Warnock observes:
Not only will "negative_int >> n" give you a terribly wrong answer
(compared to "negative_int / (2**n)") if your machine uses logical shift,
but it will give you an "off by one" answer if you use arithmetic shift
(unless negative_int happens to be minus a power of 2 bigger than "n").
Actually, if the machine is using arithmetic shift the shift is arguably
right and the "true" division wrong. The problem is that there is
no unique "right" definition of integer division for the case where the
remainder is nonzero. The basic problem is to define a function n div d
(where n and d are integers) that yields an ordered pair of integers <q, r>
such that q*d + r == n && |r| < |d|. The problem is that there is more
than one such function. The four most obvious possibilities can be summed
up in terms of their effects on a non-zero remainder:
1. Remainder has same sign as dividend.
2. Remainder has same sign as divisor.
3. Remainder is always positive.
4. Magnitude of remainder is minimized, with some decision rule
for resolving ties (e.g. 5 div 2 == <2, 1> or <3, -1>).
3 is a bit odd. 4 is rounding, which is usual for floating-point
but odd for integers. The major candidates are 1 and 2. 1 is the
Fortran approach, truncating the quotient towards 0. Most languages
and most machines have followed Fortran's lead. 2 is "modulus division",
with the quotient truncated toward minus infinity. This is the division
operation implemented by arithmetic shifts on a two's-complement machine.
Modulus division is possibly superior to Fortran division, in fact, and
some recent languages and one recent machine (the 16032) recognize this.
--
Henry Spencer @ U of Toronto Zoology
{allegra,ihnp4,linus,decvax}!utzoo!henryrpw3@fortune.UUCP (01/11/84)
#R:allegra:-218900:fortune:16200018:000:1338
fortune!rpw3 Jan 11 04:59:00 1984
I regret to say, my "fix" of the divide-a-negative-variable-by-a-
constant-power-of-two-using-a-shift has a bug in it (OOPS!).
As Gary Graunke (Tektronix) rightly points out, the number that should
be added to the variable before shifting (if the variable was negative)
is the power-of-two-minus-one, not just plain 'ol one. Now you all
knew I knew all along, right? Well, I did. (Just ask our local
compiler guys.) but (BLUSH!) I didn't proofread my note very well;
I was too busy with the fancy "learn from history" quotes. (We will
see next time if I learn from history...)
Rob Warnock
UUCP: {sri-unix,amd70,hpda,harpo,ihnp4,allegra}!fortune!rpw3
DDD: (415)595-8444
USPS: Fortune Systems Corp, 101 Twin Dolphins Drive, Redwood City, CA 94065
+----------------extract from mail--- (also posted to net.lang.c // eventually)
| From allegra!tektronix!tekchips!garyg Tue Jan 10 18:47:51 1984
|
| 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 */
+---------------usenet@abnjh.UUCP (usenet) (01/12/84)
>> The four most obvious possibilities can be summed >> up in terms of their effects on a non-zero remainder: >> >> 1. Remainder has same sign as dividend. >> 2. Remainder has same sign as divisor. >> 3. Remainder is always positive. >> 4. Magnitude of remainder is minimized, with some decision rule >> for resolving ties (e.g. 5 div 2 == <2, 1> or <3, -1>). >> >> 3 is a bit odd. Not at all, 3 is what most mathematicians would say is *the* correct way to divide two integers. It is most convenient for doing modulo arithmetic. The result of doing n mod m is always less than m and greater or equal to zero. Rick Thomas