finding combinatorial of large numbers

Question

What is an efficient way of finding the number of ways k gifts can be chosen from N gifts where N can be very large (N ~ 10^18). That is we have to calculate N(C)K or N chose K. K can also be of the order of N.

Answer 1

I guess there are no fast ways to compute such large numbers. You can approximate it using Stirling's formula

Answer 2

Stirling's formula would be useful only if you had further asymptotic information such as k ~ n / 3 or k ~ log n. With no further information on your specific problem, you will not draw any information of Stirling's formula.

For your problem as stated, the most direct way to compute C(n, k) when k and n are large (and even when they are not large) is to use

log C(n, k) = log (n!) - (log (k!) + log ((n - k)!))

and

n! = gamma(n + 1).

The fact is that it is quite easy to come with an implementation of log gamma, and you then have

C(n, k) = exp (f(n + 1) - f(k + 1) - f(n - k + 1))

where f = log gamma .

You can find numerical algorithms for computing log gamma in Numerical Recipes, an old version is available there and you will find a sample implementation in Chapter 6.

Answer 3

Since variety is the spice of life, another approach is the following. The value (N Choose K)/2^N approaches a normal distribution with mean N/2 and Standard Deviation Sqrt[N]/2 and it does so quite quickly. We can therefore approximate (N Choose K) as 2^N * Normdist(x,0,1)/std where x =( k - N/2)/std and std is Sqrt[N]/2.
Normdist(x,0,1) = Exp(-x^2/2)*1/(Sqrt(2*Pi))

In terms of error this should get much better the larger the number, and a quick check using N as 113(?) shows an maximum error as a percent of the largest coefficient of less than 0.3%.

Not claiming its better than using Stirling formula, but think that it might avoid some of the n^n calculations and working out the log of these coefficients is a pretty simple calculation.

Answer 4

The value of C(n, k) can be close to 2^n. (well, order of magnitude smaller, but that's not important here).

What important is that to store number 2^(10^18), you need 10^18 bits or ~ 10^17 bytes.
You might want to adjust problem definition, because there're no computers like that.

Others have already pointed out approximate formula, where you could store result as a floating point number, thus not spending more memory than necessary.