How to calculate binomial coefficients for large numbers

Question

I need to calculate n!/(nr)!r! in c #. It is easy to calculate using the factor function for small numbers, but when the number gets larger, like 100, it doesn't work. Is there any other way with which we can calculate combinations for large numbers?

Answer 1

First, I note that you are trying to calculate a binomial coefficient, so call it that.

Here are a few calculation methods. If you use BigInteger, you do not need to worry about overflow:

First method: use factorial:

 static BigInteger Factorial(BigInteger n) { BigInteger f = 1; for (BigInteger i = 2; i <= n; ++i) f = f * i; return f; } static BigInteger BinomialCoefficient(BigInteger n, BigInteger k) { return Factorial(n) / (Factorial(nk) * Factorial(k)); } 

Method two: use recursion:

 static BigInteger BinomialCoefficient(BigInteger n, BigInteger k) { if (n == 0) return 1; if (k == 0) return 0; return BinomialCoefficient(n-1, k-1) + BinomialCoefficient(n-1, k) } 

This method, however, is not fast unless you memoize the result.

The third method: be smarter in minimizing the number of multiplications and divide earlier. This reduces the number of numbers:

 static BigInteger BinomialCoefficient(BigInteger n, BigInteger k) { // (n C k) and (n C (nk)) are the same, so pick the smaller as k: if (k > n - k) k = n - k; BigInteger result = 1; for (BigInteger i = 1; i <= k; ++i) { result *= n - k + i; result /= i; } return result; } 

So, for example, if you calculated (6 C 3) instead of calculating (6 x 5 x 4 x 3 x 2 x 1) / ((3 x 2 x 1) x (3 x 2 x 1)), you calculate (( (4/1) * 5) / 2) * 6) / 3, which allows, if possible, small numbers.

Answer 2

Following what Eric said, dividing the early ones helps a lot, you can improve this by dividing from high to low. That way you can calculate any result if endresult is suitable for Long. Here's the code I'm using (sorry for Java, but the conversion should be easy):

 public static long binomialCoefficient(int n, int k) { // take the lowest possible k to reduce computing using: n over k = n over (nk) k = java.lang.Math.min( k, n - k ); // holds the high number: fi. (1000 over 990) holds 991..1000 long highnumber[] = new long[k]; for (int i = 0; i < k; i++) highnumber[i] = n - i; // the high number first order is important // holds the dividers: fi. (1000 over 990) holds 2..10 int dividers[] = new int[k - 1]; for (int i = 0; i < k - 1; i++) dividers[i] = k - i; // for every divider there always exists a highnumber that can be divided by // this, the number of highnumbers being a sequence that equals the number of // dividers. Thus, the only trick needed is to divide in reverse order, so // divide the highest divider first trying it on the highest highnumber first. // That way you do not need to do any tricks with primes. for (int divider: dividers) for (int i = 0; i < k; i++) if (highnumber[i] % divider == 0) { highnumber[i] /= divider; break; } // multiply remainder of highnumbers long result = 1; for (long high : highnumber) result *= high; return result; } 

Answer 3

For .net 4.0 and a larger class using BigInteger instead of int / long

For other .net use your own class of large numbers, for example, from IntX: http://www.codeplex.com/IntX/

Answer 4

I think it will be effective. This is O (k)

notice n! / p! r! just overrides the last rn value so 7 3

 7 x 6 x 5 x 4 x 3 x 2 x 1 over 4 x 3 x 2 x 1 public static uint BinomialCoeffient(uint n, uint k) { if (k > n) return 0; uint c = n; for (uint i = 1; i < k; i++) { c *= n - i; c /= i + 1; } return c; }