Path: utzoo!utgpu!attcan!uunet!husc6!rutgers!bellcore!jcricket!sjs
From: sjs@jcricket.ctt.bellcore.com (Stan Switzer)
Newsgroups: comp.lang.c
Subject: Something IBM did right (RT division of negatives).
Message-ID: <11529@bellcore.bellcore.com>
Date: 3 Nov 88 15:56:28 GMT
References: <3105@hubcap.UUCP> <34112@XAIT.XEROX.COM> <1700@dataio.Data-IO.COM> <136@twwells.uucp> <2730@hound.UUCP>
Sender: news@bellcore.bellcore.com
Reply-To: sjs@ctt.bellcore.com (Stan Switzer)
Organization: Bellcore
Lines: 76

In article <2730@hound.UUCP> rkl1@hound.UUCP (K.LAUX) writes:
> 
> 	I'm suprized that noone has questioned the validity of shifting
> instead of dividing by (powers of) 2.
> 
> 	What about the difference between Logical and Arithmetic shifts?
> If you want to divide, then divide!  A lot of compilers are smart enough
> to implement the divide as a shift, but only where appropriate.
> 
> 	I *did* notice the condition of dividend being positive, but now
> you have to *guarantee* that it will always be positive.  Also, by
> implication, the dividend is a *signed* quantity.  You can get into
> trouble if it gets changed to an *unsigned* quantity (like when 16K isn't
> enough).

Well, I really hate to open this can of worms yet again, but in my
experience whenever (for integer i) "i%4" and "i>>2" differ, what you
REALLY want is what "i>>2" does anyway (assuming 2's complement).
Which is to say that you want the MODULUS operation rather than the
REMAINDER operation.  I have seen MANY cases where this is true, and
have NEVER seen a case where it was false.

The PC/RT implements / to truncate to smaller values and i%n to always
return a value (0..n-1) for positive "n" (dunno about negative "n").
This is a CLEAR win because now the compiler can ALWAYS optimize
divisions by powers of two into right shifts without fretting over the
sign of the quotient.

The only argument for the common (mis)behavior of / and % that holds
even one drip of water is that FORTRAN requires you to do it wrong.

Please, do not argue that integer -1/2 should be -1 so that the sign
is the same as -1.0/2.0 or because "by the laws of arithmetic" (-1)/2
equals -(1/2).  These are pointless arguments that have no useful
consequences as far as correct programs are concerned.

Anyone wishing to take up the other side of the argument must find an
example of an actual situation where having -1/2 yield -1 is useful.
(The example must yield cases where the quotient can be both positive
or negative, otherwise I can just add or subtract one to the result
and get the same effect).

I offer the following examples in favor of the the "modular"
interpretation: 

1) [0..3] represents [north, east, south, and west].  With the modular
% operator, "dir = (dir-1)%4" means "turn left".  I first came across
this in a program that drew Hilbert curves.

2) Bit extraction:  To get the n'th bit from the current (char) pointer
"p" (0 bit is low) use "bit = (p[i/BITSPERCHAR]>>(i%BITSPERCHAR)) & 1"
This comes up in rasterization code often enough.  The usual solution
is to jimmy it so that you avoid negative "i" (or just use >>3 and &7
instead).

3) Window calculations in protocol handling need to know the
difference between two numbers (mod window's range). You should be
able to do "(i-j)/winrng" but must instead do "(winrng+i-j)/winrng".
I came across this case in an X.25 handler.

Actual code.  Real programs.  

Granted, to write portable code in "C" one must assume the worst.  The
point is that division must yield the same result whether optimized to
a shift or not.  Since there is no harm in it, you might as well
define integer division so that it is equivalent to the result of the
shift when that optimization can be made.

You should never have to code "i>>3" when you mean "i/8".  You should
also never have to worry that a 45 cycle divide instruction is going
to be used so that in case the quotient is negative you'll get the
answer that someone thought you wanted instead of the one you probably
really want anyway, especially when a shift would have worked just as
well.

Stan Switzer  sjs@ctt.bellcore.com