Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!purdue!haven!adm!smoke!gwyn
From: gwyn@smoke.BRL.MIL (Doug Gwyn)
Newsgroups: comp.lang.c
Subject: Re: checking for overflow in C
Message-ID: <10243@smoke.BRL.MIL>
Date: 9 May 89 15:36:40 GMT
References: <13367@dartvax.Dartmouth.EDU> <10218@smoke.BRL.MIL> <436@cbnewsm.ATT.COM>
Reply-To: gwyn@brl.arpa (Doug Gwyn)
Organization: Ballistic Research Lab (BRL), APG, MD.
Lines: 36

In article <436@cbnewsm.ATT.COM> mnc@cbnewsm.ATT.COM (michael.n.condict) writes:
>The methods that come to my mind require
>much more time than the multiply itself.

You don't really have much choice, because if you go ahead and multiply
the numbers you will generate an exception (signal) in some implementations.
That certainly provides a way to detect overflow on those implementations,
but it's probably not what you want.  If you use floating-point arithmetic
for your interpreter, on the other hand, since you have no control over the
user input you need to be prepared to catch exceptions and deal sensibly
with them anyway.

There's too much variability in the way that integer exceptions are treated
by implementations to provide a single approach that is both portable AND
highly efficient.

A not-too-inefficient way to test for multiplication overflow before
attempting the operation is to add suitable approximations of the logs
of the absolute values of the operands and see if the sum of the logs
exceeds a "danger threshold".  You can refine the test if this preliminary
probe indicates danger of overflow, or you can just indicate overflow if
you come that close to a real one.  (Why is it necessary to allow the
edge of the envelope to be pushed by the interpreter?)

A simpler technique is to use a multiple-precision multiplication
algorithm in which case it is trivial to test for overflow after the
operation.

I admit I didn't have interpreters for uncontrolled input in mind when
I suggested finding a better algorithm, although I still think that the
suggestion applies.  The usual question one gets is "how do I trap a
division by zero", which is similar to this one; sometimes one sees
	if ( divisor != 0 )
		quotient = dividiend / divisor;
	else	/* something */
which is usually the wrong solution to the actual problem.