Strange bug with Catalan number generator

Question

I'm trying to write a iterative catalan number generator as opposed to a recursive one. It works, but only up until the number "10", and then it starts to print out numbers that don't make sense. Here's what I have so far.

  public static long dpr1(int n)
  {
  long [] Array = new long[(2*n)+1];

  Array[0]=1;

  Array[1]=1;

  int count=0;

  long c=0;

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

      Array[i]=(i)*(Array[i-1]);
      count=i;
  }

   return(((Array[count])/(((Array[n]))*(Array[n])))/(n+1));

}

I've been testing it using this as a main:

public class CatalanTest  
{
public static void main(String[] args) 
{
  long startTime, endTime, result;
  for (int n = 2; n < 18; n = n + 2) 
{ 
System.out.println(Catalan.dpr1(n));
}}}

Which returns

 2
 14
 132
 1430
 16796
 -2
 97
 0

Which are the corresponding Catalan numbers for the even numbers between 2 and 10, but after that the values don't make a ton of sense and I have no idea why. Any help sorting this out would be appreciated.

Answer 1

Based on this code A[i] is equal to Factorial(i). When n=11, you calculate Factorial up to 22, and Factorial(22) is larger than the max value of long, so your calculations overflow, and the result is wrong.

You can avoid the overflow is you realize that:

(Array[count] / (Array[n]*Array[n])) / (n+1) =
 ((2*n)!/(n!*n!))/(n+1) =
 ((n+1)*(n+2)*...*(2n)/(n!))/(n+1)=
 (n+2)*(n+3)*...*(2n)/(n!)  

So you can forget about your array and just calculate this formula, which would work without overflowing for larger values of n.

Your entire code can be reduced to :

    for (long n=2;n<18;n+=2) {
        long res = 1;
        for (long l=n+2;l<=2*n;l++)
           res *= l;
        for (long l=2;l<=n;l++)
           res=res/l;
        System.out.println(res);
    }

Which produces this output (it looks like we still get an overflow for n=16):

2
14
132
1430
16796
208012
2674440
91351

To avoid that, we can combine the multiplications and divisions, in order to keep the intermediate result small :

    for (long n=2;n<18;n+=2) {
        double res = 1;
        for (long l=n+2;l<=2*n;l++) {
           res *= l;
           res /= (l-n);
        }
        System.out.println((long)res);
    }

This produces :

2
14
132
1430
16796
208012
2674440
35357670