Combinatory issue due to Factorial overflow

Question

I need a function which can calculate the mathematical combination of (n, k) for a card game.

My current attempt is to use a function based on usual Factorial method :

    static long Factorial(long n)
    {
        return n < 2 ? 1 : n * Factorial(n - 1); 
    }

    static long Combinatory(long n , long k )
    {
        return Factorial(n) / (Factorial(k) * Factorial(n - k)); 
    }

It's working very well but the matter is when I use some range of number (n value max is 52 and k value max is 4), it keeps me returning a wrong value. E.g :

   long comb = Combinatory(52, 2) ; // return 1 which should be actually 1326

I know that it's because I overflow the long when I make Factorial(52) but the range result I need is not as big as it seems.

Is there any way to get over this issue ?

You're looking to calculate binomials. http://stackoverflow.com/questions/1495856/how-can-i-calculate-a-factorial-in-c-sharp-using-a-library-call — Sten Petrov, Jul 25 '14 at 15:03
@p.s.w.g : because both codes compile in Java and C#, and long are both 64bits. — user3877200, Jul 25 '14 at 15:04
I'm curious about why you need to calculate such large numbers. Would an approximation suffice? — Teepeemm, Jul 25 '14 at 18:12

Perfect28 · Accepted Answer · 2015-04-17T15:25:00.633

10

Instead of using the default combinatory formula n! / (k! x (n - k)!), use the recursive property of the combinatory function.

    (n, k) = (n - 1, k) + (n - 1, k - 1)

Knowing that : (n, 0) = 1 and (n, n) = 1.

-> It will make you avoid using factorial and overflowing your long.

Here is sample of implementation you can do :

 static long Combinatory(long n, long k)
    {
        if (k == 0 || n == k )
            return 1;

        return Combinatory(n - 1, k) + Combinatory(n - 1, k - 1); 
    }

EDIT : With a faster iterative algorithm

    static long Combinatory(long n, long k)
    {
        if (n - k < k)
            k = n - k;

        long res = 1;

        for (int i = 1; i <= k; ++i)
        {
            res = (res * (n - i + 1)) / i;
        }

        return res;
    }

edited Apr 17 '15 at 15:25

answered Jul 25 '14 at 15:00

Perfect28

11,089
3
25
45

1

This is *super* inefficient, and with the numbers hes talking about, he likely still won't be able to actually compute the values that he'll need to. This is like the textbook example of how not to use recursion. – Servy Jul 25 '14 at 15:08
1

@Servy, also a textbook example of when to use memoization. Also could exploit the identity (n, k) = (n, n-k) – Solomon Slow Jul 25 '14 at 15:15
Yes because 4! still isn't that big of a number, but as soon as you get to about 8 you get to the point where it takes a very long time, and only a few past that if you can wait for quite some time. That's the problem with having an O(N!) algorithm. – Servy Jul 25 '14 at 15:17
@jameslarge yes, that is one possible way of making this not perform terribly. – Servy Jul 25 '14 at 15:18
1

@Servy : I made an edit on the answer. I hope it will satisfy you – Perfect28 Jul 25 '14 at 15:29
Than you for your answer – user3877200 Jul 25 '14 at 15:52

score 2 · Answer 2 · answered Jul 25 '14 at 15:11

2

In C# you can use BigInteger (I think there's a Java equivalent).

e.g.:

static long Combinatory(long n, long k)
{
    return (long)(Factorial(new BigInteger(n)) / (Factorial(new BigInteger(k)) * Factorial(new BigInteger(n - k))));
}

static BigInteger Factorial(BigInteger n)
{
    return n < 2 ? 1 : n * Factorial(n - 1);
}

You need to add a reference to System.Numerics to use BigInteger.

answered Jul 25 '14 at 15:11

Matthew Watson

104,400
10
158
276

Than you for your answer – user3877200 Jul 25 '14 at 15:52
Java has a BigInteger class, but it doesn't have operator overloading, so you'd need to adjust `/`, `<`, `*`, and `-`. – Teepeemm Sep 03 '14 at 17:25

score 2 · Answer 3 · answered Jul 25 '14 at 15:38

If this is not for a homework assignment, there is an efficient implementation in Apache's commons-math package

http://commons.apache.org/proper/commons-math/apidocs/org/apache/commons/math3/util/ArithmeticUtils.html#binomialCoefficientDouble%28int,%20int%29

If it is for a homework assignment, start avoiding factorial in your implementation.

Use the property that (n, k) = (n, n-k) to rewrite your choose using the highest value for k.

Then note that you can reduce n!/k!(n-k)! to n * n-1 * n-2 .... * k / (n-k) * (n-k-1) ... * 1 means that you are multiplying every number from [k, n] inclusive, then dividing by every number [1,n-k] inclusive.

// From memory, please verify correctness independently before trusting its use.
//
public long choose(n, k) {
  long kPrime = Math.max(k, n-k);
  long returnValue = 1;
  for(i = kPrime; i <= n; i++) {
    returnValue *= i;
  }
  for(i = 2; i <= n - kPrime; i++) {
    returnValue /= i;
  }
  return returnValue;
}

Please double check the maths, but this is a basic idea you could go down to get a reasonably efficient implementation that will work for numbers up to a poker deck.

score 0 · Answer 4 · answered Jul 25 '14 at 17:03

The recursive formula is also known as Pascal's triangle, and IMO it's the easiest way to calculate combinatorials. If you're only going to need C(52,k) (for 0<=k<=52) I think it would be best to fill a table with them at program start. The following C code fills a table using this method:

static  int64_t*    pascals_triangle( int N)
{
int n,k;
int64_t*    C = calloc( N+1, sizeof *C);
    for( n=0; n<=N; ++n)
    {   C[n] = 1;
        for( k=n-1; k>0; --k)
        {   C[k] += C[k-1];
        }
    }
    return C;
}

After calling this with N=52, for example returns, C[k] will hold C(52,k) for k=0..52

Combinatory issue due to Factorial overflow

4 Answers4