Capturing Integer Overflow in recursive function [C]

Question

UPDATE:

Thanks for the helpful comments and tips. Using what you guys said is what I came up with:

#include <limits.h> ... else { int a = binom(n - 1, k - 1); int b = binom(n - 1, k); if(a > 0) { if (b > INT_MAX - a) { // case 1: integer overflow printf("int overflow\n"); return; } } else if (b < INT_MIN - a) { // case 2: integer overflow printf("int overflow\n"); return; } int c = a + b; return c; } 

I have another question. In the above code, when I catch an integer overflow, I don't return a value - it's just return; .

One of the comments below suggested return -1; however this would not work, considering that -1 is still a real integer, right?

I am not sure what to do, since the return type is int for my function. Does return; or is there a better way to do this? It was also suggested exit(1); , but does it exit the entire program or just functions?

---

ORIGINAL:

Your function should use integer arithmetic to ensure that the results are accurate and also detect any integer overflows caused by exceeding the maximum allowed values.

I am trying to catch integer overflow while calculating binomial coefficients. Although a simple concept, what throws me away is that it is not just a one-time addition, it is a recursive algorithm that constantly executes amounts.

This is the function:

 // recursive function to calculate binomial coefficients int binom(int n, int k){ if(k == 0){ // base case return 1; } else if (n == 0){ return 0; } else{ return binom(n - 1, k - 1) + binom(n - 1, k); // recursive call } } 

Within this logic, I assume that the catch should be in a recursive call. Sort of:

if(binom(n-1, k-1) + binom(n-1,k)) causes overflow, return error, else proceed with binom(n-1, k-1) + binom(n-1,k)

Answer 1

Signed overflow is an undefined behavior that you must check for overflow before this happens.

 int a, b; int c; ... /* Compute a + b and store the result in c */ if (a > 0) { if (b > INT_MAX - a) { // a + b overflows (ie, would be > INT_MAX) } } else if (b < INT_MIN - a) { // a + b overflows (ie, would be < INT_MIN) } c = a + b; 

therefore for a recursive function:

 a = binom(n - 1, k - 1); b = binom(n - 1, k); // if no overflow c = a + b; return c; 

In your example, you also need to check n and k not == INT_MIN , otherwise operation - 1 will also overflow.

Answer 2

Do something like:

 long res=(long)binom(n - 1, k - 1) + binom(n - 1, k); if (res>INT_MAX) { printf("int overflow\n"); exit(1); } return (int)res; 

(Assuming long longer than int on your system. If not, use a wider type)

Edit: if you don't want exit on error, you must select a value (e.g. -1 ) to represent the error. also, better (and fix) you use unsigned instead of long :

 int a=binom(n - 1, k - 1),b=binom(n - 1, k); if (a<0 || b<0 || (unsigned)a+(unsigned)b>INT_MAX) return -1; return a+b; 

Answer 3

A few suggestions:

1) You use a signed integer; if you are working with strictly positive values, you should probably use unsigned int or unsigned long long. With a signed int, when an arithmetic overflow occurs, it will go to the largest possible negative number

2) The compiler will determine the preprocessor character along the INT_MAX lines; you can probably use it, for example, something like this:

 #inlcude <stdtypes.h> uint32_t binom( uint32_t n, uint32_t k ){ // (...) } else { int32_t A = binom( n-1, k-1 ) , B = binom( n-1, k ); if( (double)A + (double)B > INT_MAX ){ // error condition } else { retval = A+B; } } return retval; }