0

I m trying to calculate ncr(combinations) in c using dp. But it is failing with n=70. Can anyone help?

unsigned long long ncr( int n , int r)
{
unsigned long long c[1001];
int i=1; 
c[0]=1;
for(i=1; i<=r; i++)
    c[i]= ((unsigned long long) (c[i-1]) * (unsigned long long)( n-i+1))%(unsigned long long) (1000000007)/ (unsigned long long)(i);
return c[r];
}

basic idea is ncr = ((n-r+1)/r)* nc(r-1)

Jarod42
  • 203,559
  • 14
  • 181
  • 302
bhavneet
  • 51
  • 2
  • 11

2 Answers2

2

The intermediate product (unsigned long long) (c[i-1]) * (unsigned long long)( n-i+1) is a very big number, and is overflowing the 64 bits word.

You may want to use bignums. I strongly recommend against developing your own bignum functions (e.g. multiplication and division of bignums), because it is a delicate algorithmic subject (you could still get a PhD about that).

I suggest using some existing bignum library like GMP.

Some languages or implementations (in particular SBCL for Common Lisp) offers native bignum operations. But standard C or C++ don't.

Basile Starynkevitch
  • 223,805
  • 18
  • 296
  • 547
  • sorry i used the following in actual code (took mod of ans) :c[i]= ((unsigned long long) (c[i-1]) * (unsigned long long)( n-i+1))%(unsigned long long) (1000000007)/ (unsigned long long)(i); – bhavneet Feb 09 '13 at 12:01
  • But you still need to compute C(n,p) in bignums, and then take the modulus of `1000000007` which is a large prime number (so all digits or bits of C(n,p) are needed to get the modulus). You really cannot avoid bignums in your case.... – Basile Starynkevitch Feb 09 '13 at 12:02
  • 2
    @bhavneet To compute `nCr % p`, you mustn't divide by `i`, you have to multiply with its modular inverse. Also [check here](http://stackoverflow.com/a/10862881/1011995). – Daniel Fischer Feb 09 '13 at 14:07
-1

Make the division before the multiplication. a*b/c = (a/c) *b where the second better for overflow which seems your problem.

blackmath
  • 242
  • 1
  • 10
  • if u mean c[i]= (((unsigned long long) (c[i-1])/ (unsigned long long)(i) )* (unsigned long long)( n-i+1))%(unsigned long long) (1000000007); its still not working – bhavneet Feb 09 '13 at 12:19
  • I did not debug it, still u need to make it with rec, much better and readable in my opinion. does it pass for values n>=71? – blackmath Feb 10 '13 at 12:40
  • The final result is an integer, that doesn't mean each intermediate factor in your particular order of building it up is an integer. – vonbrand Feb 11 '13 at 21:23
  • With `long`, `(a*b)/c` may be different than `(a/c)*b`: `(3*2)/2 == 3 ` which is different than `(3/2)*2 == 2`. – Jarod42 Oct 31 '14 at 20:01