ken@aiai.ed.ac.uk (Ken Johnson) (05/18/89)
Since I posted a C program which detects overflow in int multiplication
at immense cost in time terms, I received the following solution
by e-mail:
if ( a != 0 && (a * b)/b == a) { /* No overflow */ }
My first thought is the first test should really be applied to b,
not a, to prevent overflow, giving
if ( b != 0 && (a * b)/b == a) { /* No overflow */ }
However, this is not always going to work. Consider the case of
a = 512 (0x200), b = 64 (0x40). Then in 16-bit arithmetic,
a != 0 is true
b != 0 is true
(a * b) = 0x8000 (overflowing) but 0x8000/0x40 = 0x200
...so I don't think this is guaranteed to work either.
A further example would be 521 * 63 (0x209 * 0x3f).
--
Ken Johnson, AI Applications Institute, 80 South Bridge, Edinburgh EH1 1HN
E-mail ken@aiai.ed.ac.uk, phone 031-225 4464 extension 212
Half of what I have said in this article is rubbish. I don't know which half.mcdaniel@uicsrd.csrd.uiuc.edu (Tim McDaniel) (05/20/89)
[My earlier article with the same title, <1067@garcon.cso.uiuc.edu>, was incomplete. I intend to cancel it. Sorry if you see both of these.] In article <455@skye.ed.ac.uk> ken@aiai.UUCP (Ken Johnson) writes: >Since I posted a C program which detects overflow in int multiplication >at immense cost in time terms, I received the following solution >by e-mail: > > if ( b != 0 && (a * b)/b == a) { /* No overflow */ } As I noted eariler, it doesn't work if overflow on multiply causes a fatal trap. (However, if it silently truncates, it's almost correct. I should have made this a special case in MY immense-cost code.) By the way, Ken's code wasn't so bad. It did have a loop, but it avoided division, which can be slooooow. >However, this is not always going to work. Consider the case of >a = 512 (0x200), b = 64 (0x40). Then in 16-bit arithmetic, ... presumably, 2s-complement, and "*" silently left-truncates on overflow ... > (a * b) = 0x8000 (overflowing) Yes. 0x8000 == -32768 (where "overflow" means "the result is an integer, but cannot be represented exactly in the storage provided") > but 0x8000/0x40 = 0x200 No. The ANSI C standard requires that -32768/64 == -512. The division here (0x8000/0x40 == 0x200) is correct for unsigned, but if it was unsigned arithmetic, there was no overflow; in unsigned, 0x8000 represents 32768, which is the correct result. So the test worked in this case. >A further example would be 521 * 63 (0x209 * 0x3f). Same type of result. >...so I don't think this is guaranteed to work either. A problem case is actually a = 0x8000 = -32768, b = -1. a * b = 0x8000 = -32768 This has overflowed, since the correct answer, 32768, can't be stored in 16 bits 2s-complement. Then -32768 / b = -32768 / -1 = -32768 for the same basic reason. Here's another, less probable case: suppose that an overflow on "*" generates INT_MAX (or INT_MIN, depending on the proper sign). Then -1311 * 25 = -32775 This would be reduced to INT_MIN = -32768 (say). -32768 / 25 = -1310.72000 = uhhh .... An ANSI C implementation is permitted to generate either -1310 (truncate) or -1311 (round to -infinity). If it chooses the latter, the test fails. -- "6:20 O Timothy, keep that which is committed to thy trust, avoiding profane and vain babblings, and oppositions of science falsely so called: 6:21 Which some professing have erred concerning the faith." Tim, the Bizarre and Oddly-Dressed Enchanter | mcdaniel@uicsrd.csrd.uiuc.edu {uunet,convex,pur-ee}!uiucuxc!uicsrd!mcdaniel mcdaniel%uicsrd@{uxc.cso.uiuc.edu,uiuc.csnet}
tarvaine@tukki.jyu.fi (Tapani Tarvainen) (05/20/89)
In article <455@skye.ed.ac.uk> ken@aiai.UUCP (Ken Johnson) writes: [about detecting overflow in integer multiplication] > if ( b != 0 && (a * b)/b == a) { /* No overflow */ } > >However, this is not always going to work. Consider the case of >a = 512 (0x200), b = 64 (0x40). Then in 16-bit arithmetic, > > a != 0 is true > b != 0 is true > (a * b) = 0x8000 (overflowing) but 0x8000/0x40 = 0x200 > >...so I don't think this is guaranteed to work either. If you're doing unsigned multiplication the above isn't overflow, if signed then division is presumably signed also and 0x08000/0x040 = -32768/-64 = -512 = 0x0FE00 != 0x0200. Actually I'm not at all sure signed multiplication gives the above result in all processors, or indeed that any particular result can be relied on. Nonetheless, the test works even if we assume that a random number is generated whenever overflow occurs: If c/b == a && c%b == 0 then c == a*b, without overflow, as long as division can be relied on. Moreover, if a*b overflows, then c/b == a && c%b != 0 isn't possible. Division can overflow in 2's complement arithmetic in one case only, namely when the most negative number is divided by -1 (e.g., -32768/-1 with 16 bits) (in one's complement arithmetic it NEVER overflows) so if -32768*-1 gives -32768 and -32768/-1 also gives -32768 then the test will fail. The truly paranoid can can test for this possibility separately, e.g., a<0 && -a<0 doesn't take much time. Of course there's still the possibility that a too smart compiler will optimize (a*b)/b as a ... but if you write it as c = a * b; if (c / b != a) { /* overflow */ ... you should be safe; if ((c = a * b) / b != a) { ... is probably OK as well (anybody know what pANS says about expression optimization in cases like this?). Finally: All this assumes multiplication can only result in normal numbers - if there is an architecture with integer NaNs or something which can result from multiplication overflow but isn't guaranteed to work reasonably in division, then all bets are off. (E.g., if integers are stored as 64 bits but behave as 48-bit ones, except when overflow occurs ... I vaguely remember having heard of such a system.) -- Tapani Tarvainen BitNet: tarvainen@finjyu Internet: tarvainen@jylk.jyu.fi -- OR -- tarvaine@tukki.jyu.fi
mcdaniel@uicsrd.csrd.uiuc.edu (Tim McDaniel) (05/21/89)
In article <455@skye.ed.ac.uk> ken@aiai.UUCP (Ken Johnson) writes: : [about detecting overflow in integer multiplication] : if ( b != 0 && (a * b)/b == a) { /* No overflow */ } In article <723@tukki.jyu.fi> tarvaine@tukki.jyu.fi (Tapani Tarvainen) writes: >Nonetheless, the test works even if we assume that a random number is >generated whenever overflow occurs ... as long as division can be >relied on. I answered this in another posting. Basically, "division can't be relied on" for negative divisors. >Division can overflow in 2's complement arithmetic in one case only, >namely when the most negative number is divided by -1 (e.g., >-32768/-1 with 16 bits) ... The truly paranoid can can test >for this possibility separately, e.g., a<0 && -a<0 >doesn't take much time. In such a case, -a == -INT_MIN overflows, which could trap. In my code, I checked for all cases in which -1 is an operand. The check is much easier to do and generating the result is much faster. >Of course there's still the possibility that a too smart compiler >will optimize (a*b)/b as a ... One of the most heatedly-debated issues in the ANSI C standardization effort was whether it should be legal to optimize past parenthesis boundaries. Existing practice was that it was legal, and it was proposed that the unary "+" operator would disable optimization. In this case, the expression above would have had to write "+(a*b)/b" to assure the desired behavior. After much debate, it was decided to follow the FORTRANish rule to make it illegal. Thus, a pANS C-compliant compiler can't be "too smart" here. Under pANS C, "(a*b)/b" cannot be optimized to "a". However, if it's not pANS C-compliant, all bets are off. (That's the reason for having a standard in the first place, so that at least SOME bets can be made. :-) >integers are stored as 64 bits but behave as 48-bit ones, except when >overflow occurs ... I vaguely remember having heard of such a >system.) Working from memory here: I think one such system was the CDC Cyber 174 and 175. Floating-point numbers were 64 bits long, with a 15 bit exponent field. The "mantissa" field was not a fraction, as on most systems today, but an integer. These were ones-complement machines. Therefore, the f.p. value was just mant_sign * (mantissa * 2 ** (exp_sign * exponent)) So integers were simply floating-point numbers with an exponent of 0. I'm not sure whether there were any special integer instructions, or whether floating-point instructions were used instead. In the latter case, overflow would have ... interesting ... effects. Any loop counter being incremented by 1 that overflowed (overflew? :-) would hit INT_MAX+1 and stick there. -- "6:20 O Timothy, keep that which is committed to thy trust, avoiding profane and vain babblings, and oppositions of science falsely so called: 6:21 Which some professing have erred concerning the faith." Tim, the Bizarre and Oddly-Dressed Enchanter | mcdaniel@uicsrd.csrd.uiuc.edu {uunet,convex,pur-ee}!uiucuxc!uicsrd!mcdaniel mcdaniel%uicsrd@{uxc.cso.uiuc.edu,uiuc.csnet}
scjones@sdrc.UUCP (Larry Jones) (05/21/89)
In article <1076@garcon.cso.uiuc.edu>, mcdaniel@uicsrd.csrd.uiuc.edu (Tim McDaniel) writes: > Under pANS C, "(a*b)/b" cannot be optimized to "a". However, if it's not > pANS C-compliant, all bets are off. (That's the reason for having a > standard in the first place, so that at least SOME bets can be made. > :-) [where a and b are both integers] Sorry, but you're wrong -- pANS DOES allow the expression to be optimized provided the optimized expression gives the same result as the original expression in all cases where the result is well defined. If a and b are both integers, then the expression "a" does give the same result as "(a*b)/b" except when "(a*b)/b" overflows. If it overflows, the results are undefined and getting the "correct" answer without generating an overflow is certainly an allowable response to undefined behavior. ---- Larry Jones UUCP: uunet!sdrc!scjones SDRC scjones@SDRC.UU.NET 2000 Eastman Dr. BIX: ltl Milford, OH 45150-2789 AT&T: (513) 576-2070 "You can't get a body like mine in a bottle -- unless you push REAL HARD." - Judy Tenuta / Dr. Pepper
jfc@athena.mit.edu (John F Carr) (05/23/89)
In article <731@sdrc.UUCP> scjones@sdrc.UUCP (Larry Jones) writes: >If a and b are both integers, then the expression "a" >does give the same result as "(a*b)/b" except when "(a*b)/b" >overflows. If it overflows, the results are undefined and >getting the "correct" answer without generating an overflow is >certainly an allowable response to undefined behavior. If they are unsigned integers, this optimization is not possible, since overflow is ignored (i.e. given n bit words, (2 * (2^n - 1)) / 2 == 2^(n-1) - 1 is required with unsigned math [becuase the intermediate value, 2*(2^n - 1) must be truncated to 2^n - 2], while the true answer is (2 * (2^n - 1)) / 2 == 2^n - 1 ). --John Carr (jfc@athena.mit.edu) John Carr "When they turn the pages of history, jfc@Athena.mit.edu When these days have passed long ago, bloom-beacon! Will they read of us with sadness athena.mit.edu!jfc For the seeds that we let grow?" --Neil Peart