sjs@jcricket.ctt.bellcore.com (Stan Switzer) (11/03/88)
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
djones@megatest.UUCP (Dave Jones) (11/05/88)
From article <11529@bellcore.bellcore.com>, by sjs@jcricket.ctt.bellcore.com (Stan Switzer): > 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). > While I don't want to concede that the way you have restricted debate on this is justified, but I'll bite anyway. I'll use the second example you gave immediately after the challenge. > I offer the following examples in favor of the the "modular" > interpretation: > ... > > 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). > In the scheme of things you propose, bit[-1] has the same location as bit[7]. Is that what you want? Change the meaning of (-1)/BITSPERCHR to be -1, and every bit gets its own happy home. Good enough? Best regards, Dave J.
stuart@bms-at.UUCP (Stuart Gathman) (11/09/88)
In article <11529@bellcore.bellcore.com>, sjs@jcricket.ctt.bellcore.com (Stan Switzer) writes: > 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. How about rounding by adding 1/2 and truncating (toward the smallest number, not zero)? Trunctating (-1)/2 to -1 is exactly the approach that does *not* require checking the sign when using arithmetic shifts. If you want logical shifts, use unsigned operands. -- Stuart D. Gathman <stuart@bms-at.uucp> <..!{vrdxhq|daitc}!bms-at!stuart>
sjs@jcricket.ctt.bellcore.com (Stan Switzer) (11/09/88)
In article <973@goofy.megatest.UUCP> djones@megatest.UUCP (Dave Jones) writes: > From article <11529@bellcore.bellcore.com>, by sjs@jcricket.ctt.bellcore.com (Stan Switzer): > > 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). > While I don't want to concede that the way you have restricted debate > on this is justified, but I'll bite anyway. I'll use the second > example you gave immediately after the challenge. Actually, the terms are fair enough. I only ask for demonstration that the behavior is useful. Unfortunately I botched my original posting. I typed -1 when I meant 0 and 0 when I meant -1. Just goes to show that this business can be tricky. I'm sure you'll find the terms of debate reasonable now that we agree :-). > > 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" > In the scheme of things you propose, bit[-1] has the same location > as bit[7]. Is that what you want? Change the meaning of (-1)/BITSPERCHR > to be -1, and every bit gets its own happy home. > Good enough? Better than good enough. It's my point exatly. Too bad the errors in my first article confused the issue. Regarding another followup that there are at least three "reasonable" definitionions of "/" and "%" and that Common Lisp has all three (and various kitchen appliances :-), whether the other interpretations are reasonable or not is debatable. I still have NEVER seen a case where the other definitions are USEFUL. Again, too bad the errors in my original article tend to confuse the issue. Back to "C". Given that C does not (fully) define the behavior of neg/pos or neg%pos, the implementor is free to choose a definition which allows the shift optimization (the interpretation where -1 / 2 == -1 and -1 % 2 == 1 -- I got it right this time, right?). Unfortunately, if there is a hardware div/rem instruction the implementor's best choice is probably to just use the instruction and let the result be whatever the instruction gives, and since div/rem instruction is designed with FORTRAN in mind -- FORTRAN requires (last time I checked) -1/2 to be 0 and mod(-1,2) to be -1 -- the shift optimization is precluded. But, as the RT plainly shows, having -1/2 == -1 breaks no code and, God only knows, probably fixes some code that was broken all along This is because unless you specifically exploit the discontinuity at zero in the FORTRAN definition, the behavior is entirely useless. I find it difficult that anyone would do that on purpose. Conclusions: If you have to do div in software, you might as well design it so that you can use shifts to handle divides by powers of two. If you design hardware, you really ought to consider designing your div instruction that way as well. If you have to worry about FORTRAN you might consider whether it is worthwhile having two flavors of div/rem instructions. To be sure, you might look at it and decide not to bother, but you probably ought to see if it is worthwhile. It IS a strange idea though, designing an instruction so that it can sometimes NOT be used -- you have to take into account how much faster things go when you get to use shift instead. Stan Switzer sjs@ctt.bellcore.com
stt@inmet (11/11/88)
The flip-side of this div = shift is to take the route that Intel did with the 80960, and provide an additional right shift instruction which does the same thing as "normal" divide on negative numbers. It is a lot faster than divide, and always truncates toward 0. Essentially it is a divide-by-power-of-2 instruction. S. Tucker Taft Intermetrics, Inc. Cambridge, MA 02138