Java: avoiding factorial overflow

Question

I'm supposed to optimize the following code so that it calculates the central binomial coefficient up to the max value of integer (up to n = 16).

public static int factorial(int n)
{
    int result= 1;

    for(int i = 2; i <= n; i++) result *= i;

    return result;
}

public static int centralbinom(int n)
{
    return factorial(2*n) / (factorial(n) * factorial(n));
}

Naturally I get an overflow for every n > 6. How do I 'break down' the factorial function so that doesn't has to deal with big numbers such as 2n = 2*16 = 32 ?

Or is there a better way to calculate the central binomial coefficient?

Answer 1

Here are several optimizations that you can do in addition to using BigIntegers that may reduce your calculations, in most of you cases overflow that you may be having in your program.

1. Since you need factorial(n) at least two time. Calculate it once and store it in a variable.

2. Factorial(2*n) has factorial(n) in it. Since you have already calculated factorial(n) before all you need to do is calculate till factorial(2n....n) and then multiply factorial(n) to it. Here's one way how that can be done.

   //Pseudocode
   
   //find factorial of n given I know already till k
   
   int findFactorial(n, k) {
     int result = 1
     for i n to 1
   
       if(i==k) 
          break;
   
       result = result * n;
     return result
   }
   
   //factorial(2*n) = facorial(n, k) * factorial(k)
   

This will reduce your calculations a lot and in case if you expect your program not to have an overflow, you can go away with BigIntegers.

Answer 2

If you need a factorial of big number, you have to use BigInteger class to calculate result:

public static BigInteger factorial(int n) {
    BigInteger result = BigInteger.ONE;

    for (int i = 2; i <= n; ++i) {
        result = result.multiply(BigInteger.valueOf(i));
    }

    return result;
}

Answer 3

If the central binomial coefficient of 17 is greater than the integer max, and you only need to compute it for 17 numbers, then the obvious solution is a lookup table. Create a 17-element array containing the central binomial coefficient for n = 0 to 16. I think you'll find this solution is extremely efficient.

You can find a list of them here. http://oeis.org/A000984

Answer 4

Just compress your factorial by gamma. set gamma to 10 is good enough

public static double factorial(int n, double gamma)
{
    double result= 1;
    double gammaInv = 1.0/gamma;
    for(int i = 2; i <= n; i++) result *= pow(i,gammaInv);

    return result;
}

public static int centralbinom(int n, double gamma)
{
    return pow(factorial(2*n,gamma) / 
        (factorial(n,gamma) * factorial(n),gamma),
        gamma);
}