c++ - To find combination value of large numbers -

i want find (n choose r) large integers, , have find out mod of number.

long long int choose(int a,int b) {     if (b > a)         return (-1);     if(b==0 || a==1 || b==a)         return(1);     else     {         long long int r = ((choose(a-1,b))%10000007+(choose(a-1,b-  1))%10000007)%10000007;         return r;     } } 

i using piece of code, getting tle. if there other method please tell me.

i don't have reputation comment yet, wanted point out answer rock321987 works pretty well:

it fast , correct , including c(62, 31)

but cannot handle inputs have output fits in uint64_t. proof, try:

c(67, 33) = 14,226,520,737,620,288,370 (verify correctness , size)

unfortunately, other implementation spits out 8,829,174,638,479,413 incorrect. there other ways calculate ncr won't break this, real problem here there no attempt take advantage of modulus.

notice p = 10000007 prime, allows leverage fact integers have inverse mod p, , inverse unique. furthermore, can find inverse quite quickly. question has answer on how here, i've replicated below.

this handy since:

1. x/y mod p == x*(y inverse) mod p; and
2. xy mod p == (x mod p)(y mod p)

modifying other code bit, , generalizing problem have following:

#include <iostream> #include <assert.h>  // p must prime , less 2^63 uint64_t inversemodp(uint64_t a, uint64_t p) {     assert(p < (1ull << 63));     assert(a < p);     assert(a != 0);     uint64_t ex = p-2, result = 1;     while (ex > 0) {         if (ex % 2 == 1) {             result = (result*a) % p;         }         = (a*a) % p;         ex /= 2;     }     return result; }  // p must prime uint32_t ncrmodp(uint32_t n, uint32_t r, uint32_t p) {     assert(r <= n);     if (r > n-r) r = n-r;     if (r == 0) return 1;     if(n/p - (n-r)/p > r/p) return 0;      uint64_t result = 1; //intermediary results may overflow 32 bits      (uint32_t = n, x = 1; > r; --i, ++x) {         if( % p != 0) {             result *= % p;             result %= p;         }         if( x % p != 0) {             result *= inversemodp(x % p, p);             result %= p;         }     }     return result; }  int main() {     uint32_t smallprime = 17;     uint32_t mednum = 3001;     uint32_t halfmednum = mednum >> 1;     std::cout << ncrmodp(mednum, halfmednum, smallprime) << std::endl;      uint32_t bigprime = 4294967291ul; // 2^32-5 largest prime < 2^32     uint32_t bignum = 1ul << 24;     uint32_t halfbignum = bignum >> 1;     std::cout << ncrmodp(bignum, halfbignum, bigprime) << std::endl; } 

which should produce results set of 32-bit inputs if willing wait. prove point, i've included calculation 24-bit n, , maximum 32-bit prime. modest pc took ~13 seconds calculate this. check answer against wolfram alpha, beware may exceed 'standard computation time' there.

there still room improvement if p smaller (n-r) r <= n-r. example, precalculate inverses mod p instead of doing on demand several times over.