Detecting Overflow In nCr Function

Question

I have two functions here that together compute the nCr:

int factorial(int n) {
int c;
int result = 1;

 for (c = 1; c <= n; c++)
 {
  result = result*c;

 }

return result;
}




int nCr(int n, int r) {
int result;

 result = factorial(n)/(factorial(r)*factorial(n-r));

 return result;
}

I am having trouble with an error check I need to implement. As n gets larger, I won't have the ability to computer n! and this error check has to exist in both nCr and factorial. They both must detect this overflow.

Currently, when I enter a number that is too large for computation, I get a floating type error returned from the command line.

I am having trouble accounting for this overflow check. Any help would be much appreciated, thanks.

Possible duplicate http://stackoverflow.com/questions/11809502/which-is-better-way-to-calculate-ncr — mazhar islam, Jul 25 '15 at 12:33
Why don't you just skip computing the factorials, and just compute the binomial coefficient directly? — EOF, Jul 25 '15 at 12:35
i suggest doing the way we compute manually.. first multiply `temp1 *= n` decrementing `n` till `(n-r)` then divide by computing `r` factorial.. — Haris, Jul 25 '15 at 12:37
I need to keep my function as returning an int, instead of a long long unsigned int, because I am working off of a template and cannot change what the function returns. I also need the two functions, for this is part of a longer stretch of code where these 2 functions are needed later on and are also specified in the template I'm working from. — Bret, Jul 25 '15 at 12:39
So you're asking how to store values in an `int` larger than it can represent? One important task in software development is to choose the correct data type for a given problem (and not the reverse) — too honest for this site, Jul 25 '15 at 12:44
I am only asking how to detect this overflow. I did not design the template myself, but I have to follow its design. I am just having trouble detecting the overflow in both nCr and factorial based on this design. — Bret, Jul 25 '15 at 13:02
1. Indent your code properly. 2. Your algorithm is very bad, as it'll calculate the low factorials again and again. For example to calculate 12C5 it'll calculate `1*2*3*4*5` 3 times and `5!*6*7` twice — phuclv, Jul 25 '15 at 13:17
If you just want to check the overflow, there are already numerous duplicates here [How to detect integer overflow in C/C++?](http://stackoverflow.com/q/199333/995714), [Detecting signed overflow in C/C++](http://stackoverflow.com/q/3944505/995714), [Avoiding interger overflow with permutation (nPr, nCr) functions in C](http://stackoverflow.com/q/11016069/995714)... — phuclv, Jul 25 '15 at 13:19

score 0 · Answer 1 · edited Jul 25 '15 at 14:22

In your code, the maximum value is always factorial(n),
so you only need to check that n! isn't bigger than 2.147.483.647 (max int value).

Please note that the stored max value can be different based on the size of the int type in memory (different machines can specify different sizes).

However, the last bit in int type variables is reserved for storing the sign (+ or -), thus the max value can be half of 65.535 and 4.294.967.295 i.e. 32.767 and 2.147.483.647 for int types.

SIZE_OF_INT(bits)    MAX VALUE(UNSIGNED)     MAX_VALUE(SIGNED)
---------------------------------------------------------------
16                   65.535                  32.767
32                   4.294.967.295           2.147.483.647

The value of 13! can go beyond the max value of the int type (in 32 bit).

12! = 479.001.600 and
13! = 6.227.020.800

So, you need to check in nCr(int n, int r) that the max value of n is always less than 13 (i.e. n<=12) and r<=n. And in factorial(int n): n<=12.

`int` is not guaranteed to have 32 bits. It's a bad idea to tell a beginner to rely on _implementation defined_ behaviour. Even more as it is completely unnecessary: do not use magic numbers; the standard defines `MAX_INT` for a reason. — too honest for this site, Jul 25 '15 at 12:47
`factorial(n)` is large but `factorial(r)*factorial(n-r)` may even be larger — phuclv, Jul 25 '15 at 13:18

score 0 · Answer 2 · answered Jul 25 '15 at 13:39

A better way of calculating binomial coefficients

typedef unsigned long long ull;

ull nCr(int n, int r) {
    ull res = 1;
    if (r > n - r) r = n - r;
    for (int i = 0; i < r; ++i) {
        res *= (n - i);
        res /= (i + 1);
    }
    return res;
}

Detecting Overflow In nCr Function

2 Answers2