Detecting overflow

[Tapani Tarvainen]

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 */ }
>
>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 at finjyu
Internet:  tarvainen at jylk.jyu.fi  -- OR --  tarvaine at tukki.jyu.fi