Calculation of the Catalan number
I am using this code to calculate Catalan number. This gives me the correct value up to n = 6, then it gives me the wrong values. I checked by hand using a calculator. For Ex: when n = 5 the Catalan number is 42, which is true, but when n = 7 it gives me 6, which is completely wrong, since the answer should be 429. I just can't figure out what happened. Can anyone help me?
static void Main(string[] args)
{
int i, n, fact, fact1, fact2, CatalanN;
Console.WriteLine("Enter a Number (n>=0)");
n = Convert.ToInt32(Console.ReadLine());
fact = n;
for (i = n - 1; i > 0; i--)
{
fact = fact * i;
}
Console.WriteLine("" + fact);
Console.ReadLine();
fact1 = 2*n;
for (i = 2*n - 1; i > 0; i--)
{
fact1 = fact1 * i;
}
Console.WriteLine("" + fact1);
Console.ReadLine();
fact2 = n+1;
for (i = (n+1)-1; i > 0; i--)
{
fact2 = fact2 * i;
}
Console.WriteLine("" + fact2);
Console.ReadLine();
CatalanN = fact1 / (fact2 * fact);
Console.WriteLine("Catalan Number of the given number is : " + CatalanN);
Console.ReadLine();
}
source to share
If you change your second loop to:
for (i = 2*n - 1; i > 0; i--)
{
int old = fact1;
fact1 = fact1 * i;
Console.WriteLine("" + old + " " + fact1);
}
then you will see that you are suffering from overflow (slightly reformatted to align values):
14 182
182 2184
2184 24024
24024 240240
240240 2162160
2162160 17297280
17297280 121080960
121080960 726485760
726485760 -662538496 <- overflow occurs here.
-662538496 1644813312
1644813312 639472640
639472640 1278945280
1278945280 1278945280
This is due to the terms of the factor type in the calculations. Changing the type to long
will give you some more breathing room (allowing you to do C ten). Also, decimal
might go a little further, but you may need to use an arbitrary precision math library (for example System.Numerics.BigInteger
) for higher numbers.
You can use a slightly less burdensome calculation that minimizes intermediate conditions a little:
n = Convert.ToInt32(Console.ReadLine()); CatalanN = 1; Term = 0; while (n-- > 1) { Term++; CatalanN = CatalanN * (4 * Term + 2) / (Term + 2); }
This will give you even more breathing room, no matter what type of data you're using. Even our low int
can get up to C sixteenwith this calculation, a long
can get at least C 25that as far as I could be concerned to check.
source to share