shallit@eleazar.dartmouth.edu (Jeffrey Shallit) (05/05/89)
Fans of C frequently boast that it is "very close to the machine". Since I'm a relative newcomer to the language, perhaps someone could enlighten me about the officially approved way of checking overflow when multiplying two integers. Or is doing (i) a pre-multiply test to ensure the arguments aren't too big or (ii) a post-division step to ensure the accuracy of the result the only portable way of doing this? Jeff Shallit shallit@dartmouth.edu
henry@utzoo.uucp (Henry Spencer) (05/07/89)
In article <13367@dartvax.Dartmouth.EDU> shallit@eleazar.dartmouth.edu (Jeffrey Shallit) writes: >Fans of C frequently boast that it is "very close to the machine". Since >I'm a relative newcomer to the language, perhaps someone could enlighten >me about the officially approved way of checking overflow when multiplying >two integers... C unfortunately has to be close to the hardware of a wide variety of machines. There is no consensus on whether the hardware checks for overflow or not. C generally prefers to reflect the underlying hardware rather than trying to hide it, so this lack of consensus shows to the programmer. C does not promise that overflow will be detected at all. Nor does C promise that overflow *won't* be detected; it might abort your program, or just do strange things. For reliable and portable code, you must do the check yourself, in advance (and be careful that your overflow check can't itself cause an overflow!). -- Mars in 1980s: USSR, 2 tries, | Henry Spencer at U of Toronto Zoology 2 failures; USA, 0 tries. | uunet!attcan!utzoo!henry henry@zoo.toronto.edu
tneff@bfmny0.UUCP (Tom Neff) (05/07/89)
Let me agree with and amplify on Henry Spencer's customarily excellent
remarks, namely that C can't always check things like overflow because
it has to be portable. There do exist high level languages which cater
to every hardware feature of a family of processors. On the Intel *86
family PL/M is a perfect example. Based originally on PL/I Subset (I
will mail a chocolate chip cookie to anyone who ever programmed in
THAT particular late 60s IBM brainchild!!), PL/M has hardware builtins
for virtually everything special about the 8086/88, 286, 386 and now 486.
You use them as functions or procedures in your statements, or sometimes
they are standalone statements like "DISABLE;". However PL/M is monumentally
non-portable to other architectures, as we know our minimal discomfort
at my employers'.
C on the other hand is signally portable, and incorporates the minimum
of assumptions about how its host processor is going to behave. Henry
is dead to rights: if your C program needs to worry about integer overflow
in a particular situation, let it check the values beforehand rather than
waiting for the CPU or OS to save its bacon.
--
Tom Neff UUCP: ...!uunet!bfmny0!tneff
"Truisms aren't everything." Internet: tneff@bfmny0.UU.NETgwyn@smoke.BRL.MIL (Doug Gwyn) (05/08/89)
In article <13367@dartvax.Dartmouth.EDU> shallit@eleazar.dartmouth.edu (Jeffrey Shallit) writes: >... enlighten me about the officially approved way of checking overflow when >multiplying two integers. Patient: Doctor, it hurts when I do this. Doctor: Don't do that! You're looking for tactics when what is needed is better strategy. How did you get your algorithm into the state where an overflow is even possible? Sounds to me like the algorithm needs to be better engineered.
jas@ernie.Berkeley.EDU (Jim Shankland) (05/08/89)
In article <10218@smoke.BRL.MIL> gwyn@brl.arpa (Doug Gwyn) writes: >In article <13367@dartvax.Dartmouth.EDU> shallit@eleazar.dartmouth.edu (Jeffrey Shallit) writes: >>... enlighten me about the officially approved way of checking overflow when >>multiplying two integers. >... >You're looking for tactics when what is needed is better strategy. >How did you get your algorithm into the state where an overflow is >even possible? Sounds to me like the algorithm needs to be better >engineered. I can think of lots of cases where the operands of an arithmetic operation aren't known until run-time. The only way to ensure that the operation won't overflow is to perform some check on the operands, which is exactly what he was inquiring about. I don't know how else he might "better engineer" his algorithm to avoid the problem. I understand the reasons for C's overflow semantics (or lack of them, if you will). Nonetheless, while it's not a problem most of the time, when it is a problem, it's a big one. Operations like multiplication end up becoming a subroutine -- often one written in assembler. Jim Shankland jas@ernie.berkeley.edu "Blame it on the lies that killed us, blame it on the truth that ran us down"
ka@june.cs.washington.edu (Kenneth Almquist) (05/08/89)
henry@utzoo.uucp (Henry Spencer) writes: > C unfortunately has to be close to the hardware of a wide variety of > machines. There is no consensus on whether the hardware checks for overflow > or not. C generally prefers to reflect the underlying hardware rather > than trying to hide it, so this lack of consensus shows to the programmer. If there is not a consensus, there is certainly an overwhelming majority! I know the assembly languages of half a dozen machines, and they all include overflow checks. Kenneth Almquist
cik@l.cc.purdue.edu (Herman Rubin) (05/08/89)
In article <10218@smoke.BRL.MIL>, gwyn@smoke.BRL.MIL (Doug Gwyn) writes: > In article <13367@dartvax.Dartmouth.EDU> shallit@eleazar.dartmouth.edu (Jeffrey Shallit) writes: < <... enlighten me about the officially approved way of checking overflow when < <multiplying two integers. > > Patient: Doctor, it hurts when I do this. > Doctor: Don't do that! > > You're looking for tactics when what is needed is better strategy. > How did you get your algorithm into the state where an overflow is > even possible? Sounds to me like the algorithm needs to be better > engineered. Are you that certain that the algorithm using overflow is not better engineered than the one that does not? By better engineered, I mean that it runs faster. If it is on the machine, it should be available for use. -- Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907 Phone: (317)494-6054 hrubin@l.cc.purdue.edu (Internet, bitnet, UUCP)
gwyn@smoke.BRL.MIL (Doug Gwyn) (05/08/89)
In article <1292@l.cc.purdue.edu> cik@l.cc.purdue.edu (Herman Rubin) writes: >By better engineered, I mean that it runs faster. >If it is on the machine, it should be available for use. What can I say? I disagree with both statements.
rkl@cbnewsh.ATT.COM (kevin.laux) (05/08/89)
In article <13367@dartvax.Dartmouth.EDU>, shallit@eleazar.dartmouth.edu (Jeffrey Shallit) writes: > Fans of C frequently boast that it is "very close to the machine". Since > I'm a relative newcomer to the language, perhaps someone could enlighten > me about the officially approved way of checking overflow when multiplying > two integers. Or is doing (i) a pre-multiply test to ensure the arguments > aren't too big or (ii) a post-division step to ensure the accuracy of the > result the only portable way of doing this? > Basically, it is impossible to Overflow when multiplying two integers. If you multiply two 8-bit integers, the result will not exceed 16-bits. Likewise, two 16-bit ints won't exceed a 32-bit result. Now, if you're asking if it's possible to Truncate, why of course it is. Just take two, say 16-bit ints, multiply them and assign the result to to an 8-bit char :-). The only time you might have a problem it when you're multiplying two longs with large values together. If your longs are 32-bits, then the result may need to be expressed in 64-bits. You would have to call a function designed to handle such cases and that would return two 32-bit longs, one being the Most Significant part, the other being the Least Significant part. So, except for the special case above, the CPU's multiply instruction (ie. the multiplication algorithm designed into the hardware/firmware/microcode)will never Overflow and will return the appropriate result. It is up to you to provide a variable large enough to hold the result. And even for the special case, you still cannot get an overflow; you just get back the pieces which you now must manipulate appropriately. --rkl
karl@haddock.ima.isc.com (Karl Heuer) (05/09/89)
In article <10218@smoke.BRL.MIL> gwyn@brl.arpa (Doug Gwyn) writes: >In <13367@dartvax.Dartmouth.EDU> shallit@eleazar (Jeffrey Shallit) writes: >>... enlighten me about the officially approved way of checking overflow when >>multiplying two integers. > >How did you get your algorithm into the state where an overflow is >even possible? Let's take a concrete example. How do you think one should code the implementation of the ANSI C function strtol(), which is required to detect integer overflow and return ERANGE in this case? Karl W. Z. Heuer (ima!haddock!karl or karl@haddock.isc.com), The Walking Lint
mnc@cbnewsm.ATT.COM (michael.n.condict) (05/09/89)
In article <10218@smoke.BRL.MIL>, gwyn@smoke.BRL.MIL (Doug Gwyn) writes: > In article <13367@dartvax.Dartmouth.EDU> shallit@eleazar.dartmouth.edu (Jeffrey Shallit) writes: > >... enlighten me about the officially approved way of checking overflow when > >multiplying two integers. > > Patient: Doctor, it hurts when I do this. > Doctor: Don't do that! > > You're looking for tactics when what is needed is better strategy. > How did you get your algorithm into the state where an overflow is > even possible? Sounds to me like the algorithm needs to be better > engineered. I think you're off-base here, Doug. The obvious (and morally justifiable) answer to your question is that you've read two numbers from the user's input and the user requests you to multiply them. A typical example would be an interpreter for a language that is using the local machine integers as its integer type. I too am interested in knowing how such an interpreter, written in portable C, can efficiently determine whether overflow will occur when it multiplies two arbitrary integers. The methods that come to my mind require much more time than the multiply itself. Please enlighten. Michael Condict AT&T Bell Laboratories Murray Hill, NJ {allegra|att}!m10ux!mnc
kers@otter.hpl.hp.com (Chris Dollin) (05/09/89)
Doug Gwyn said: | In article <13367@dartvax.Dartmouth.EDU> shallit@eleazar.dartmouth.edu | (Jeffrey Shallit) writes: | >... enlighten me about the officially approved way of checking overflow when | >multiplying two integers. | | Patient: Doctor, it hurts when I do this. | Doctor: Don't do that! | | You're looking for tactics when what is needed is better strategy. | How did you get your algorithm into the state where an overflow is | even possible? Sounds to me like the algorithm needs to be better | engineered. Doug, Doug! How about, for an example off the top of my head (and sitting in a directory on my workstation) writing a bytecode interpreter? Presumably, you'll let me have a multiply instruction, and not constrain the byte-code generator to only use it when it can *prove* there's no overflow? Actually, I have exactly this problem. What *is* the approved way of doing long * long and generating either the long result, or an indication of overflow? And similarly for division? Yes, I'll look at Knuth; but are there some accepted idioms around? If it matters, for other reasons I'm probably restricted to 32-bit machines with 8-bit bytes where pointers-to-long and longs have the same size. Kers. | "A foolish hobgoblin has the consistency of little minds".
gwyn@smoke.BRL.MIL (Doug Gwyn) (05/09/89)
In article <13003@haddock.ima.isc.com> karl@haddock.ima.isc.com (Karl Heuer) writes: >Let's take a concrete example. How do you think one should code the >implementation of the ANSI C function strtol(), which is required to detect >integer overflow and return ERANGE in this case? There's no requirement that strtol() be implemented in C, but assuming that you're trying to do so, in the loop that multiplies the accumulator by the base and adds in the next digit, before doing that operation test to see if it would overflow. It's not hard.
gwyn@smoke.BRL.MIL (Doug Gwyn) (05/09/89)
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.
jcbst3@cisunx.UUCP (James C. Benz) (05/09/89)
In article <436@cbnewsm.ATT.COM> mnc@cbnewsm.ATT.COM (michael.n.condict) writes: >In article <10218@smoke.BRL.MIL>, gwyn@smoke.BRL.MIL (Doug Gwyn) writes: >> In article <13367@dartvax.Dartmouth.EDU> shallit@eleazar.dartmouth.edu (Jeffrey Shallit) writes: >> >... enlighten me about the officially approved way of checking overflow when >> >multiplying two integers. And while we're on the subject (how's your old wazoo) - Is there any easy (or not so easy) way to check for overflow in arithmetic involving Floating Point values? I have a program with a large block of FP arithmetic that is quite prone to overflow (VERRRY large numbers) and my only recourse up to now has been to check the value of each computation against 1/2 * MAXFLOAT which is far from perfect. It would please me greatly and not surprise me much if there is a way built into the FP package to do this that my documentation just doesn't mention - not sure if I have the full set of docs anyway. I'm using ATT Sys V. -- Jim Benz jcbst3@unix.cis.pittsburgh.edu If a modem University of Pittsburgh answers, UCIR (412) 648-5930 hang up!
dhesi@bsu-cs.bsu.edu (Rahul Dhesi) (05/10/89)
Just a reminder to all of you: "Overflow" simply does not exist in
unsigned arithmetic. When you add two unsigned values and the result
is too big to fit, what happens is a "carry", not an overflow.
Overflow occurs only in signed arithmetic.
--
Rahul Dhesi <dhesi@bsu-cs.bsu.edu>
UUCP: ...!{iuvax,pur-ee}!bsu-cs!dhesihenry@utzoo.uucp (Henry Spencer) (05/10/89)
In article <472@cbnewsh.ATT.COM> rkl@cbnewsh.ATT.COM (kevin.laux) writes: > Basically, it is impossible to Overflow when multiplying two integers. Sorry, wrong. >If you multiply two 8-bit integers, the result will not exceed 16-bits. >Likewise, two 16-bit ints won't exceed a 32-bit result. Except that C multiplication, and the multiply instructions on some (not all) modern machines, multiply two 16-bit numbers to give a 16-bit number, or two 32-bit numbers to give a 32-bit number. > So, except for the special case above, the CPU's multiply instruction >(ie. the multiplication algorithm designed into the hardware/firmware/ >microcode)will never Overflow and will return the appropriate result. It is up to you >to provide a variable large enough to hold the result... You are assuming (a) that the CPU *has* a multiply instruction (some don't), (b) that it gives double-width results, and (c) that it does not trap an overflow. -- Mars in 1980s: USSR, 2 tries, | Henry Spencer at U of Toronto Zoology 2 failures; USA, 0 tries. | uunet!attcan!utzoo!henry henry@zoo.toronto.edu
henry@utzoo.uucp (Henry Spencer) (05/10/89)
In article <8143@june.cs.washington.edu> ka@june.cs.washington.edu (Kenneth Almquist) writes: >> ... There is no consensus on whether the hardware checks for overflow >> or not.... >If there is not a consensus, there is certainly an overwhelming majority! >I know the assembly languages of half a dozen machines, and they all >include overflow checks. But not as part of the multiply instruction. They are extra-cost tests, typically at the very least a conditional branch following the multiply. This gets expensive when you know that your multiplies never overflow, which is why C compilers typically do not generate those tests. Note that I said "on whether the *hardware* checks for overflow" (emphasis added), not "on whether the software checks for overflow". -- Mars in 1980s: USSR, 2 tries, | Henry Spencer at U of Toronto Zoology 2 failures; USA, 0 tries. | uunet!attcan!utzoo!henry henry@zoo.toronto.edu
mcdaniel@uicsrd.csrd.uiuc.edu (Tim McDaniel) (05/10/89)
You can always do pre-checks, given <limits.h> or something like it:
unsigned int a, b, c;
...
assert(b == 0 || a <= UINT_MAX / b);
c = a * b;
Similarly for other types and operations. For unsigned adds, you can
do a post-check:
c = a + b
overflowed if and only if c <= a or c <= b.
--
Tim, the Bizarre and Oddly-Dressed Enchanter
Center for ||| Internet, BITNET: mcdaniel@uicsrd.csrd.uiuc.edu
Supercomputing ||| UUCP: {uunet,convex,pur-ee}!uiucuxc!uicsrd!mcdaniel
Research and ||| ARPANET: mcdaniel%uicsrd@uxc.cso.uiuc.edu
Development, ||| CSNET: mcdaniel%uicsrd@uiuc.csnet
U of Illinois ||| DECnet: GARCON::"mcdaniel@uicsrd.csrd.uiuc.edu"diamond@diamond.csl.sony.junet (Norman Diamond) (05/10/89)
In article <939@garcon.cso.uiuc.edu> mcdaniel@uicsrd.csrd.uiuc.edu (Tim McDaniel) writes: >Summary: A week of debugging may save you ten seconds of typing and >one minute of extra run time. Hear, hear! >C requires that unsigned arithmetic be modulo 2**n for appropriate n; >operations are not permitted to overflow. Therefore, I used unsigned >arithmetic, with a separate "int sign_bit" where necessary. >Oh, the final stores (converting the unsigned work variables to ints) >are trivial: > assert(sign_bit == 1 || sign_bit == -1); > if (sign_bit > 0) { > assert(temp <= INT_MAX); /* or SHORT_MAX or ... */ > } > else { > assert(temp <= INT_MIN); > } > actual = sign_bit * temp; If you didn't find your bug in this, you either have a brain-damaged "assert" or you didn't try very hard. Since you carefully keep temp >= 0, it's kind of hard for temp to be <= INT_MIN. -- Norman Diamond, Sony Computer Science Lab (diamond%csl.sony.co.jp@relay.cs.net) The above opinions are my own. | Why are programmers criticized for If they're also your opinions, | re-inventing the wheel, when car you're infringing my copyright. | manufacturers are praised for it?
ka@june.cs.washington.edu (Kenneth Almquist) (05/10/89)
In article <1989May9.183140.1770@utzoo.uucp>, henry@utzoo.uucp (Henry Spencer) writes: > In article <8143@june.cs.washington.edu> ka@june.cs.washington.edu (Kenneth Almquist) writes: >>> ... There is no consensus on whether the hardware checks for overflow >>> or not.... >> If there is not a consensus, there is certainly an overwhelming majority! >> I know the assembly languages of half a dozen machines, and they all >> include overflow checks. > > But not as part of the multiply instruction. They are extra-cost tests, > typically at the very least a conditional branch following the multiply. > This gets expensive when you know that your multiplies never overflow, which > is why C compilers typically do not generate those tests. OK, I think I see your point. My assumption is that the cost isn't a big issue because the programmer wouldn't test for overflow unless it was necessary. You would see an *occasional* test such as: new C keyword | v if (overflow a = b * c) printf("Multiplication overflowed\n"); else printf("%d * %d = %d\n", b, c, a); Now of course if we added the gcc "statement within an expression" construct to C it would be possible to write: if (overflow {a = b * c; ... many C statements ... a += c}) printf("An overflow occurred somewhere\n"); This would generate a lot of tests, but the syntax is ugly enough to discourage its use. (I can't think of a cleaner syntax off hand.) If the hardware insists on doing a trap on overflow rather than setting a flag, there is a big jump in the cost, but only when the overflow actually occurs, which we can assume will be rare. More serious is that on such a machine, overflow checks would require run time support, and therefore might not be available in a non-hosted environment. One of the nice features of C is that virtually all the features requiring run time support are provided through library routines, so in a non-hosted environment you simply write your own implementations of these routines, or don't call them. Kenneth Almquist
bph@buengc.BU.EDU (Blair P. Houghton) (05/10/89)
In article <17981@cisunx.UUCP> jcbst3@unix.cis.pittsburgh.edu (James C. Benz) writes: >In article <436@cbnewsm.ATT.COM> mnc@cbnewsm.ATT.COM (michael.n.condict) writes: >>In article <10218@smoke.BRL.MIL>, gwyn@smoke.BRL.MIL (Doug Gwyn) writes: >>>In article <13367@dartvax.Dartmouth.EDU> shallit@eleazar.dartmouth.edu (Jeffrey Shallit) writes: >>>>... enlighten me about the officially approved way of checking >>>>overflow when multiplying two integers. [...much dancing deleted...] I know it's overhead-city, but could someone try taking logarithms, adding them, and checking them against the logarithm of the maximum-allowable number? --Blair "Yeah, but except for the last couple of bits, it's idiot-proofed."
paul@moncam.co.uk (Paul Hudson) (05/10/89)
This does it, slowly, and is really over cautious. Typedefs and constants
self-explanatory, I hope.
Feel free to criticise, but constructively, please!
Paul Hudson MAIL: Monotype ADG, Science Park, Cambridge, CB4 4FQ, UK.
PHONE: +44 (223) 420018 EMAIL: paul@moncam.co.uk,
;" FAX: +44 (223) 420911 ...!ukc!acorn!moncam!paul
`"";";" "/dev/null full: please empty the bit bucket"
Integer a,b;
unsigned long hi_a, lo_a, hi_b, lo_b;
Integer result, temp = 0;
logical minus = FALSE;
logical overflowed = FALSE;
a = one->value.integer;
b = two->value.integer;
if (a < 0)
{
if (a != MIN_INTEGER) a = (-a);
minus = TRUE;
}
if (b < 0)
{
if (b != MIN_INTEGER) b = (-b);
minus = !minus;
}
hi_a = (unsigned long)a >> 16;
lo_a = (unsigned long)a & ( (1<<16) -1);
hi_b = (unsigned long)b >> 16;
lo_b = (unsigned long)b & ( (1<<16) -1);
if (hi_a == 0)
{
temp = hi_b * lo_a;
}
else if (hi_b == 0)
{
temp = hi_a * lo_b;
}
else overflowed = TRUE;
if (temp >= (1<<15)) overflowed = TRUE;
result = lo_a * lo_b;
if (result < 0) overflowed = TRUE;
result += (temp << 16);
if (result < 0) overflowed = TRUE;
result = minus ? -result : result;
--
Paul Hudson MAIL: Monotype ADG, Science Park, Cambridge, CB4 4FQ, UK.
PHONE: +44 (223) 420018 EMAIL: paul@moncam.co.uk,
;" FAX: +44 (223) 420911 ...!ukc!acorn!moncam!paul
`"";";" "/dev/null full: please empty the bit bucket"leo@philmds.UUCP (Leo de Wit) (05/10/89)
In article <8143@june.cs.washington.edu> ka@june.cs.washington.edu (Kenneth Almquist) writes: |henry@utzoo.uucp (Henry Spencer) writes: |> C unfortunately has to be close to the hardware of a wide variety of |> machines. There is no consensus on whether the hardware checks for overflow ^^^^^^^^^^^^^^^^^^^^^^^^^^^^ |> or not. C generally prefers to reflect the underlying hardware rather |> than trying to hide it, so this lack of consensus shows to the programmer. | |If there is not a consensus, there is certainly an overwhelming majority! |I know the assembly languages of half a dozen machines, and they all ^^^^^^^^^^^^^^^^^^ |include overflow checks. ^^^^^^^^^^^^^^^ | Kenneth Almquist Unless I'm way off, Henry was talking about hardware checks, to enforced by the hardware (causing exceptions or traps or similar to occur whenever they're violated). The overflow checks in an assembly language, as Kenneth referred to, are compiler generated/programmed in, are software based checks and thus could/can be left out (I think he meant either explicitly or implicitly testing the status word). Leo.
hascall@atanasoff.cs.iastate.edu (John Hascall) (05/10/89)
In article <8172@june.cs.washington.edu> ka@june.cs.washington.edu (Kenneth Almquist) writes: >In article <1989May9.183140.1770@utzoo.uucp>, henry@utzoo.uucp (Henry Spencer) writes: >> In article <8143@june.cs.washington.edu> ka@june.cs.washington.edu (Kenneth Almquist) writes: >OK, I think I see your point. My assumption is that the cost isn't a >big issue because the programmer wouldn't test for overflow unless it >was necessary. You would see an *occasional* test such as: > new C keyword > | > v > if (overflow a = b * c) > printf("Multiplication overflowed\n"); > else > printf("%d * %d = %d\n", b, c, a); Oh, help us please!!!! What are you people trying to do? Turn C into PL/1? If this overflow business is important to you (and it certainly is for some)... Why not use SIGFPE? This works (is documented to work, I've never had occasion to try it) under BSD on the VAX, perhaps it works on your machine as well. Did ANSI have anything to say on this topic? John Hascall ISU Comp Center
bobmon@iuvax.cs.indiana.edu (RAMontante) (05/10/89)
I needed to catch overflows for a calculator program, so I just went through and wrapped all the operations in inverse operations: /* * Is a*b a safe operation? */ if (a > 1.0 && b > 1.0 && (MAX_VAL/a) < b) /* MAX < a*b? */ report_error( "multiply overflow"); else if (a < 1.0 && b < 1.0 && (MIN_VAL/a) > b) /* MIN > a*b? */ report_error( "multiply underflow"); else c = a * b; and similarly for +, -, /. Of course this roughly doubles such operations, but I couldn't see any alternative. Did I miss something? (This appears to be compiler-dependent "sometimes"; I had to do this for TurboC v1.5, but v2.0 includes support for SIG_FPE. I haven't rewritten the thing yet.)
henry@utzoo.uucp (Henry Spencer) (05/10/89)
In article <1670018@otter.hpl.hp.com> kers@otter.hpl.hp.com (Chris Dollin) writes: >Actually, I have exactly this problem. What *is* the approved way of doing > > long * long > >and generating either the long result, or an indication of overflow? And >similarly for division? Yes, I'll look at Knuth; but are there some accepted >idioms around? Apart from the obvious (but costly, in C) possibility of doing multiprecision arithmetic, you might look for a paper titled something like "Legality Assertions in Euclid", by Dave Wortman, in a very early issue of IEEE Transactions on Software Engineering (circa ten years ago). It looks at exactly this problem: how to check for overflow, precisely (i.e. no false alarms allowed), while being certain never to cause overflow in the overflow checks themselves. It's trickier than it looks. (Apologies for the imprecise reference, my copy isn't handy.) -- Mars in 1980s: USSR, 2 tries, | Henry Spencer at U of Toronto Zoology 2 failures; USA, 0 tries. | uunet!attcan!utzoo!henry henry@zoo.toronto.edu
henry@utzoo.uucp (Henry Spencer) (05/10/89)
In article <17981@cisunx.UUCP> jcbst3@unix.cis.pittsburgh.edu (James C. Benz) writes: >Is there any easy (or not so easy) way to check for overflow in arithmetic >involving Floating Point values? ... Not a portable one. -- Mars in 1980s: USSR, 2 tries, | Henry Spencer at U of Toronto Zoology 2 failures; USA, 0 tries. | uunet!attcan!utzoo!henry henry@zoo.toronto.edu
henry@utzoo.uucp (Henry Spencer) (05/12/89)
In article <1079@atanasoff.cs.iastate.edu> hascall@atanasoff.cs.iastate.edu (John Hascall) writes: > If this overflow business is important to you (and it certainly is > for some)... Why not use SIGFPE? This works (is documented to work, > I've never had occasion to try it) under BSD on the VAX, perhaps > it works on your machine as well. Did ANSI have anything to say > on this topic? SIGFPE and friends unfortunately are *very* machine-specific, because you get signals only when the hardware feels like supplying them. -- Mars in 1980s: USSR, 2 tries, | Henry Spencer at U of Toronto Zoology 2 failures; USA, 0 tries. | uunet!attcan!utzoo!henry henry@zoo.toronto.edu
gwyn@smoke.BRL.MIL (Doug Gwyn) (05/14/89)
In article <1989May12.154417.21344@utzoo.uucp> henry@utzoo.uucp (Henry Spencer) writes: >SIGFPE and friends unfortunately are *very* machine-specific, because you >get signals only when the hardware feels like supplying them. There is indeed a wide variety of arithmetic exception behavior. Some systems generate different exceptions for integer vs. floating overflow, some generate the same exception, some generate exceptions in one case but not the other, some generate exceptions only for limited classes of arithmetic "problems", etc. A few years ago, a system manager here, responding to naive "customer" pressure to generate floating exceptions on our Gould PN series machines, modified the run-time start-off module to enable exceptions. What he didn't appreciate was that the C compiler generated code that required integer overflow to be ignored, and the Gould hardware tied integer and floating exceptions to the same enable bit. Consequently non-floating applications started dying due to unexpected SIGFPEs. We were not amused.
tps@chem.ucsd.edu (Tom Stockfisch) (05/17/89)
In article <10256@smoke.BRL.MIL> gwyn@brl.arpa (Doug Gwyn) writes: _A few years ago, a system manager here, responding to naive "customer" _pressure to generate floating exceptions on our Gould PN series machines, _modified the run-time start-off module to enable exceptions. What he _didn't appreciate was that the C compiler generated code that required _integer overflow to be ignored, and the Gould hardware tied integer _and floating exceptions to the same enable bit. Consequently non-floating _applications started dying due to unexpected SIGFPEs. We were not amused. Aren't unsigned int operations guaranteed not to generate exceptions? It seems like the C compiler could/should have done things differently. So, what machines/systems does SIGFPE not work reliably on? -- || Tom Stockfisch, UCSD Chemistry tps@chem.ucsd.edu
ggs@ulysses.homer.nj.att.com (Griff Smith) (05/18/89)
In article <472@chem.ucsd.EDU>, tps@chem.ucsd.edu (Tom Stockfisch) writes: > In article <10256@smoke.BRL.MIL> gwyn@brl.arpa (Doug Gwyn) writes: > >... the Gould hardware tied integer > >and floating exceptions to the same enable bit. Consequently non-floating > >applications started dying due to unexpected SIGFPEs. We were not amused. > > Aren't unsigned int operations guaranteed not to generate exceptions? It depends on the architecture. On many machines there is no difference between unsigned integer arithmetic and signed integer arithmetic. After doing the operation, the program tests different bits in the condition code depending on the type. > It seems like the C compiler could/should have done things differently. It may have no choice. After doing an `add' that causes overflow, it's a bit late to tell the hardware that you were doing an unsigned add. Preventing the overflow is often an expensive operation. As an example of how gross it can get, consider how DEC's TOPS-10 OS separated integer and floating exceptions: if either condition was enabled, the processor generated a trap to the kernel. The kernel then tested the `enable' bits for both conditions, and quietly returned control to the user program if the trap wasn't enabled. As you might imagine, this had strange effects on execution time. > -- > || Tom Stockfisch, UCSD Chemistry tps@chem.ucsd.edu -- Griff Smith AT&T (Bell Laboratories), Murray Hill Phone: 1-201-582-7736 UUCP: {most AT&T sites}!ulysses!ggs Internet: ggs@ulysses.att.com
gwyn@smoke.BRL.MIL (Doug Gwyn) (05/18/89)
In article <472@chem.ucsd.EDU> tps@chem.ucsd.edu (Tom Stockfisch) writes: >Aren't unsigned int operations guaranteed not to generate exceptions? C guarantees that unsigned integer arithmetic is performed as modular arithmetic. >It seems like the C compiler could/should have done things differently. Bascially, to avoid relying on benign integer overflow behavior would have required slower code to be generated. Several C implementations have made this same decision.
henry@utzoo.uucp (Henry Spencer) (05/19/89)
In article <11538@ulysses.homer.nj.att.com> ggs@ulysses.homer.nj.att.com (Griff Smith) writes: >... After doing an `add' that causes overflow, it's >a bit late to tell the hardware that you were doing an unsigned add. >Preventing the overflow is often an expensive operation. Then C's unsigned arithmetic will be expensive on that machine. Unsigned arithmetic in C is *required* to be non-overflowing. -- Subversion, n: a superset | Henry Spencer at U of Toronto Zoology of a subset. --J.J. Horning | uunet!attcan!utzoo!henry henry@zoo.toronto.edu
richard@aiai.ed.ac.uk (Richard Tobin) (05/20/89)
In article <10218@smoke.BRL.MIL> gwyn@brl.arpa (Doug Gwyn) writes: >How did you get your algorithm into the state where an overflow is >even possible? Sounds to me like the algorithm needs to be better >engineered. Oh come on. There are lots of cases where this is a possibility. Perhaps he's writing an interpreter for some other language, for example. -- Richard -- Richard Tobin, JANET: R.Tobin@uk.ac.ed AI Applications Institute, ARPA: R.Tobin%uk.ac.ed@nsfnet-relay.ac.uk Edinburgh University. UUCP: ...!ukc!ed.ac.uk!R.Tobin