Detecting overflow

[Tim McDaniel]

In article <455 at skye.ed.ac.uk> ken at aiai.UUCP (Ken Johnson) writes:
: [about detecting overflow in integer multiplication]
:	if ( b != 0 && (a * b)/b == a) { /* No overflow */ }

In article <723 at tukki.jyu.fi> tarvaine at 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 at uicsrd.csrd.uiuc.edu
            {uunet,convex,pur-ee}!uiucuxc!uicsrd!mcdaniel
            mcdaniel%uicsrd@{uxc.cso.uiuc.edu,uiuc.csnet}