Path: utzoo!utgpu!jarvis.csri.toronto.edu!rutgers!iuvax!uxc!garcon!uicsrd.csrd.uiuc.edu!mcdaniel From: mcdaniel@uicsrd.csrd.uiuc.edu (Tim McDaniel) Newsgroups: comp.lang.c Subject: Re: How to multiply two ints and check overflow Summary: 10 times slower than "*", but portable Keywords: overflow Message-ID: <1034@garcon.cso.uiuc.edu> Date: 18 May 89 06:27:51 GMT References: <434@skye.ed.ac.uk> Sender: news@garcon.cso.uiuc.edu Reply-To: mcdaniel@uicsrd.csrd.uiuc.edu (Tim McDaniel) Organization: Center for Supercomputing R&D (Cedar), U. of Ill. Lines: 448 Here's safemul, my attempt at a portable overflow-checked int multiply. It has a main() driver, if you like, with various options (print a multiplication table, do a timing check, verify all the results). On a VAX 11/785 under BSD 4.3, a safemul takes about 100 microseconds (including the function call), versus about 10 microseconds for a simple int multiply. I think it's bullet-proof, even if you don't have an int divide that always rounds towards zero. Let me know if I goofed somehow. -------- cut here -------- Cut Here -------- CUT HERE -------- /* Copyright 1989 by Timothy Alan McDaniel. May be used only under * the terms of the Free Software Foundation GNU General Public * License, version one. There is NO warranty on this software. * 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} */ #define DRIVER /* use a main program to test safemul */ #define PRINT_TABLE /* wanna multiplication table? */ #define ASSUME_OVERFLOW /* if x*y ovfl, assume X*y will, if X>x>0 etc */ #undef TIMER /* 1000000 */ /* iterations for timing test */ #define USE_UINT /* use if "/" does not always round towards zero */ /**********************************************************************\ int safemul(int x, int y, int * ovfl) Return value: x*y if the result can be represented in an int without overflow 0 otherwise *ovfl is set to: 1 if x*y would overflow 0 otherwise If ovfl is (int *) NULL, and overflow would occur, a message is printed on stderr and abort() is called. The constants INT_MAX and INT_MIN are used to determine whether overflow would occur. If x, y, or x*y (evaluated in infinite precision) falls outside the inclusive range [INT_MIN .. INT_MAX], overflow is deemed to occur. These values are in the ANSI C header , or must be #defined appropriately by the user. ALGORITHM: A preliminary divide is used to determine whether a multiply would overflow, because xy > limit iff x > limit/y (when y > 0) However, divide can overflow if INT_MAX != -INT_MIN. For example, if INT_MAX is 7 and INT_MIN is -8, (-8)/(-1) would overflow. Note that this occurs for dividing by -1. If INT_MAX is within a factor of 2 of -INT_MIN (a reasonable assumption, all in all), it can only occur when dividing by -1, so I check for that specifically. Similarly, unary negation can overflow: e.g. -(-8). (If INT_MAX was between a factor of 2 and 3 of -INT_MIN, I would have to check for divide by -2 also, but divide by -3 would be OK.) 4 cases: x y then so multiply would overflow if x > 0 y > 0 xy > 0 xy>INT_MAX i.e. x>INT_MAX/y x > 0 y < 0 xy < 0 xyINT_MIN/y x < 0 y > 0 xy < 0 xy 0 xy>INT_MAX i.e. xc iff aunsigned int, and sundry. COMPILATION: You can #define DRIVER if you want to run a driver main program to verify the results of safemul from INT_MIN-1 to INT_MAX+1. It does not check for overflow on its own multiplies and such, so it only works for relatively small values of INT_MIN and INT_MAX (up to the square root of the actual magnitudes of INT_MIN and INT_MAX). The driver defines its own values for INT_MIN and INT_MAX; to change them, look just after "For testing only". If DRIVER is #defined, and the range of INT_MIN to INT_MAX is sizeable (say -2**15 to 2*15-1 on a machine with 32-bit ints), testing all possible multiplication pairs is prohibitively time-consuming. In this case, you can #define ASSUME_OVERFLOW. In this case, if it finds that x*y overflows, it will assume that X*y will overflow, for all X such that abs(X) > abs(x) and sign(X) == sign(x), and similarly for y. If DRIVER is #defined, #define PRINT_TABLE if you want a pretty multiplication table to be printed. Blank entries are those that overflowed. If DRIVER is defined, you can #define TIMER to a positive integer. Instead of verifying safemul, printing a multiplication table, and the like, it just does a crude timing test. TIMER is defined to be the number of times safemul is called; as a comparison, 10*TIMER simple multiplications are also done. Note that elapsed times are found by calling time(), which has resolution only to a full second, so the precision is low. On the original test machine (BSD 4.3, VAX 11/785), a safemul takes about 100 microseconds (sounds much better than 1/10 milliseconds) and a simple multiply takes roughly 10 microseconds, whether or not USE_UINT is defined. If you are using an ANSI C compiler, put "#" in front of all further occurrences of the word "error". If you are not using an ANSI C compiler, inspect the first #defines below for INT_MIN, INT_MAX, and EXIT_FAILURE, and make sure they are reasonable for your system. (EXIT_FAILURE is the argument to exit() if the program failed; 1 is usual, except for VMS, sometimes.) The default algorithm below depends on integer division always rounds towards zero: that (-5)/2 == 5/(-2) == -2, and (-5)/(-2) 5/2 == 2. pANS C guarantees r.t.z. only for positive operands. If you are not sure that your computer always rounds towards zero, #define USE_UINT. The algorithm will instead do its divide using unsigned ints, which pANS C guarantees will not overflow unless the divisor is 0. (USE_UINT is not the default because int is supposed to be the "most natural" integral size, which often means the fastest. Unsigned operations may take more time to get them right without overflowing.) ***NOTE*** If you define USE_UINT, it must be the case that UINT_MAX >= INT_MAX and UINT_MAX >= -INT_MIN. If this is not the case, let me know and replace your computer system, because it is TOTALLY TWISTED. \**********************************************************************/ #include #if __STDC__ > 0 #define ANSI_C 1 #include #include #ifdef USE_UINT #if UINT_MAX < INT_MAX error "UINT_MAX < INT_MAX -- sorry, no can do" #endif #if UINT_MAX < -INT_MIN error "UINT_MAX < -INT_MIN -- sorry, no can do" #endif #endif /* USE_UINT */ #else #define ANSI_C 0 #define volatile /* nothing */ /* Define these well, please. */ #define INT_MAX (0x7fffffff) #define INT_MIN (-2147483648) #define EXIT_FAILURE (1) #endif #ifdef DRIVER /* For testing only. */ #undef INT_MAX #undef INT_MIN #undef UINT_MAX /* The first choice is suitable for multiplication tables * and quick checking; the second is just to be more sure. */ #if 1 #define INT_MAX (7) #define INT_MIN (-8) #define UINT_MIN ((unsigned int) 15) #else #define INT_MAX (32767) #define INT_MIN (-32768) #define UINT_MAX ((unsigned int) 65535) #endif #endif /* Note: INT_MAX + INT_MIN > 0 iff the positive ints have a larger * range than the negative ints, except there is no chance of * overflow on unary negation in the first case. Similarly for * "== 0" and "< 0". */ /* This sanity check is a tad tighter than necessary. Also, I hope * that preprocessor arithmetic has at least as large a range * as the target-machine arithmetic -- there is no guarantee in * ANSI C. */ #if INT_MAX + INT_MIN > 0 #if INT_MAX / -INT_MIN >= 2 error "INT_MAX is at least a factor of 2 larger than -INT_MIN; sorry" #endif #else #if -INT_MIN / INT_MAX >= 2 error "-INT_MIN is at least a factor of 2 larger than INT_MAX; sorry" #endif #endif int safemul(x, y, arg_ovfl) register int x; register int y; int * arg_ovfl; { int result, t, ovfl, limit; unsigned int uint_x, uint_y, uint_limit; #ifdef DRIVER /* If DRIVER is used, INT_MAX and INT_MIN are quite a bit * smaller than their normal values. Normally, the case * checked for here should never happen, if INT_MAX and * INT_MIN are defined properly. */ if (x > INT_MAX || y > INT_MAX || x < INT_MIN || y < INT_MIN) ovfl = 1; else /* intentionally left without a ";" so it joins with the next if */ #endif if (x == 0 || y == 0) ovfl = result = 0; /* Now if we divide by x or y, we will not get zerodivide. */ #ifndef USE_UINT else { if (x == -1) { /* After swapping, this case reduces to the next case. */ t = x; x = y; y = t; } if (y == -1) { /* It is a negation: especially beware if INT_MAX != -INT_MIN. */ #if INT_MAX + INT_MIN >= 0 ovfl = (x > -INT_MIN); #else ovfl = (x < -INT_MAX); #endif if (!ovfl) result = -x; } else { /* Since we know that abs(INT_MAX) is within a factor of 2 of * abs(INT_MIN), and abs(x) and abs(y) >= 2, we cannot overflow on * divide in here. */ /* See the "truth table" above for the logic of this. */ /* If the sign of x differs from the sign of y, then ... */ if ((x > 0) ^ (y > 0)) limit = INT_MIN; else limit = INT_MAX; limit /= y; if (x > 0) ovfl = (x > limit); else ovfl = (x < limit); if (!ovfl) result = x * y; } } #else /* if USE_UINT is defined */ else { uint_x = (x >= 0) ? (unsigned int) x : -(unsigned int) x; uint_y = (y >= 0) ? (unsigned int) y : -(unsigned int) y; uint_limit = ((x > 0) ^ (y > 0)) ? -(unsigned int) INT_MIN : (unsigned int) INT_MAX; ovfl = (uint_x > uint_limit / uint_y); if (!ovfl) result = x * y; } #endif /* ifndef USE_UINT */ if (arg_ovfl) *arg_ovfl = ovfl; if (ovfl) { if (!arg_ovfl) { fprintf(stderr, "int overflow would occur in safemul.\n"); abort(); exit(EXIT_FAILURE); } result = 0; } return result; } #ifdef DRIVER static int verify_safemul(x, y) int x; int y; { int ovfl, result, my_ovfl, bad; result = safemul(x, y, &ovfl); bad = 0; if (ovfl != 0 && ovfl != 1) { fprintf(stderr, "Overflow should be 1 or 0, not %d\n", ovfl); bad = 1; } if (ovfl && result) { fprintf(stderr, "Overflow AND result! %d*%d=%d\n", x, y, result); bad = 1; } my_ovfl = (x > INT_MAX) || (x < INT_MIN) || (y > INT_MAX) || (y < INT_MIN) || (((long) x)*y > INT_MAX) || (((long) x)*y < INT_MIN); if (ovfl != my_ovfl) { fprintf(stderr, "Bad overflow! %d*%d %s, safemul says %s\n", x, y, my_ovfl ? "should overflow" : "should not overflow", ovfl ? "should overflow" : "should not overflow"); bad = 1; } if (!ovfl && result != ((long) x)*y) { fprintf(stderr, "Incorrect result! %d*%d gives %d\n", x, y, result); bad = 1; } if (bad) exit(EXIT_FAILURE); return ovfl; } main() { int x, y, ovfl, low, high, my_ovfl; long t1, t2, t3, t4; volatile int result, t; /* volatile so the timing loop does */ volatile long count; /* not get optimized away (I hope!) */ extern long time(/* long * */); #ifdef TIMER t1 = time((long *) 0); for (count = 0; count < TIMER; count++) result = safemul(17, -29, &ovfl); t2 = time((long *) 0); for (count = 0; count < TIMER; count++) result = -493; t3 = time((long *) 0); t = 17; for (count = 0; count < 10*TIMER; count++) result = t * -29; t4 = time((long *) 0); printf("safemul (averaged over %ld calls) takes about %f microseconds.\n", (long) TIMER, (t2 - t1 - (t3 - t2)) / (double) TIMER * 1e6); printf("* (averaged over %ld executions) takes about %f microseconds.\n", (long) 10*TIMER, (t4 - t3 - (t3 - t2)) / (double) TIMER * 1e5); #else /* TIMER not defined */ low = INT_MIN - 1; high = INT_MAX + 1; printf("\nAttempting to multiply values from %d to %d.\n", low, high); #ifdef ASSUME_OVERFLOW #define ACT break #else #define ACT #endif /* Get the obvious boundary cases out of the way early. */ for (x = -2; x <= 2; x++) for (y = -2; y <= 2; y++) { verify_safemul(x, y); verify_safemul(x, INT_MAX + y); verify_safemul(x, INT_MIN + y); verify_safemul(INT_MAX + x, y); verify_safemul(INT_MIN + x, y); verify_safemul(INT_MAX + x, INT_MIN + y); verify_safemul(INT_MIN + x, INT_MAX + y); } for (x = -1; x >= low; x--) { for (y = -1; y >= low; y--) if (verify_safemul(x, y)) ACT; for (y = 0; y <= high; y++) if (verify_safemul(x, y)) ACT; } for (x = 0; x <= high; x++) { for (y = 0; y <= high; y++) if (verify_safemul(x, y)) ACT; for (y = -1; y >= low; y--) if (verify_safemul(x, y)) ACT; } #ifdef PRINT_TABLE printf("x/y | "); for (y = low; y <= high; y++) printf("%4d", y); printf("\n"); printf("----|-"); for (y = low; y <= high; y++) printf("----", y); printf("\n"); for (x = low; x <= high; x++) { printf("%3d | ", x); for (y = low; y <= high; y++) { result = safemul(x, y, &ovfl); if (ovfl) printf(" "); else printf("%4d", result); } printf("\n"); } #endif /* PRINT_TABLE */ #endif /* TIMER */ exit(0); } #endif /* DRIVER */ -- "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}