C++ function to calculate factorial returns negative value

Question

I've written a C++ function to calculate factorial and used it to calculate ²²C₁₁ (Combination). I have declared a variable ans and set it to 0. I tried to calculate

22C11 = fact(2*n)/(fact(n)*fact(n))

where i sent n as 11. For some reason, i'm getting a negative value stored in answer. How can i fix this?

long int fact(long int n) {
    if(n==1||n==0)
        return 1;
    long int x=1;
    if(n>1)
    x=n*fact(n-1);
    return x;
}

The following lines are included in the main function:

long int ans=0;
    ans=ans+(fact(2*n)/(fact(n)*fact(n)));
cout<<ans;

The answer i'm getting is -784 The correct answer should be 705432

NOTE: This function is working perfectly fine for n<=10. I have tried long long int instead of long int but it still isn't working.

Not according to the answer to this - http://stackoverflow.com/questions/1819189/what-range-of-values-can-integer-types-store-in-c — RaviTej310, Jan 28 '16 at 05:05
As i said, i have already tried `long long int` and `long int` but they weren't working. — RaviTej310, Jan 28 '16 at 05:08
Well, that's the answer, and to get help with code that isnt working you would need to post that code — M.M, Jan 28 '16 at 05:09
`long long int` is typically 64 bits. `22!` is `1124000727777607680000`, which requires at least 70 bits. — Keith Thompson, Jan 28 '16 at 05:13

score 3 · Accepted Answer · answered Jan 28 '16 at 05:27

It is unwise to actually calculate factorials - they grow extremely fast. Generally, with combinatorial formulae it's a good idea to look for a way to re-order operations to keep intermediate results somewhat constrained.

For example, let's look at (2*n)!/(n!*n!). It can be rewritten as ((n+1)*(n+2)*...*(2*n)) / (1*2*...*n) == (n+1)/1 * (n+2)/2 * (n+3)/3 ... * (2*n)/n. By interleaving multiplication and division, the rate of growth of intermediate result is reduced.

So, something like this:

int f(int n) {
  int ret = 1;
  for (int i = 1; i <= n; ++i) {
    ret *= (n + i);
    ret /= i;
  }
  return ret;
}

Demo

score 2 · Answer 2 · answered Jan 28 '16 at 05:13

2

22! = 1,124,000,727,777,607,680,000

2⁶⁴ = 18,446,744,073,709,551,615

So unless you have 128-bit integers for unsigned long long you have integer overflow.

answered Jan 28 '16 at 05:13

Mark Tolonen

166,664
26
169
251

score 0 · Answer 3 · edited May 23 '17 at 11:59

0

You are triggering integer overflow, which causes undefined behaviour. You could in fact use long long int, or unsigned long long int to get a little bit more precision, e.g:

unsigned long long fact(int n)
{
    if(n < 2)
        return 1;

    return fact(n-1) * n;
}

You say you tried this and it didn't work but I'm guessing you forgot to also update the type of x or something. (In my version I removed x as it is redundant). And/or your calculation still was so big that it overflowed unsigned long long int.

You may be interested in this thread which shows an algorithm for working out nCr that doesn't require so much intermediate storage.

edited May 23 '17 at 11:59

Community

1
1

answered Jan 28 '16 at 05:08

M.M

138,810
21
208
365

Although recursion with very large numbers generally doesn't lead anywhere good. With factorial, you're going to keep the number small anyways, but every time you call a function from itself, it sets up a new stack frame. You can run out of stack space pretty quickly. For example: unsigned long long foo(int n){ if (n == 1<<63) return n; else return foo(n+1); – Goodies Jan 28 '16 at 05:16
@Goodies a good point although I would expect compilers to implement *tail recursion optimization* in this case. In fact you can [see that happening here](http://goo.gl/yB6Tj1) – M.M Jan 28 '16 at 05:18

score 0 · Answer 4 · answered Jan 28 '16 at 05:31

You increasing your chances of success by avoiding the brute force method.

COMB(N1, N2) = FACT(N1)/(FACT(N1-N2)*FACT(N2))

You can take advantage of the fact that both the nominator and the denominator have a lot of common terms.

COMB(N1, N2) = (N1-N2+1)*(N1-N2+2)*...*N1/FACT(N1)

Here's an implementation that makes use of that knowledge and computes COMB(22,11) with much less risk of integer overflow.

unsigned long long comb(int n1, int n2)
{
   unsigned long long res = 1;
   for (int i = (n1-n2)+1; i<= n1; ++i )
   {
      res *= i;
   }

   for (int i = 2; i<= n2; ++i )
   {
      res /= i;
   }

   return res;
}

C++ function to calculate factorial returns negative value

4 Answers4

Linked