What a Catalan number is: https://en.wikipedia.org/wiki/Catalan_number
I am doing some Java exercises and a couple of the test numbers aren't passing even though I am certain they should be.
Successfully I got 11 of the 13 results but when it comes to programming, I know I must have gotten those other 11 in some weird way if I didn't get the last two. Numbers 0 - 9 and 20 work great, but 14 and 25 are slightly off:
catalanNumber(14) -> 2674439 (expected 2674440)catalanNumber(25) -> 4861946401451 (expected 4861946401452)This is the code that I wrote:
public static long catalanNumber(int place)
{ // declare variables
double numerator = (2 * place),
denFirst = (place + 1), denSecond = place;
// C(0) = 1
if(place == 0)
return 1;
// find (2n)!
for(long i = (long)numerator - 1; i > 0; i--)
numerator *= i;
// find (n + 1)!
for(long i = (long)denFirst - 1; i > 0; i--)
denFirst *= i;
// find (n)!
for(long i = (long)denSecond - 1; i > 0; i--)
denSecond *= i;
// C(n) = (2n)! / (n + 1)!(n)!
return (long)(numerator / (denFirst * denSecond));
}
The key constraint of this problem is that I am not allowed to use recursion...if only ;p
I wasn't able to really understand what was happening here/how to convert it into my problem: Strange bug with Catalan number generator
// code from that link ^
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);
}
doubles introduce errors. silently.
Why? Well, computers. They are powerful but they aren't magic.
Think about a numbers line - between 0 and 1 there are an infinite amount of them.
And double purports to be capable of representing that entire infinity. More even; 2.0 is a double.
Turns out computers can't actually do that. Because physics, math, common sense. So instead, there are these very specific chosen few numbers. Let's call them the blessed set.
A double value can actually only represent numbers in the blessed set. There's, naturally, only a finite amount of numbers in there. double's design is, as one might expect, rather fancy math to make them the right combination of easily used by CPUs to do the calculations you want them to, and then as useful as is reasonable. As part of that process, there are way more blessed numbers in the 0-1 area then there are in, say, between 10000 and 10001 - as you get further away from 0, fewer and fewer blessed numbers.
At any rate, when the result of a calculation is not blessed, then it is rounded to the nearest blessed number instead, silently.
This introduces errors; errors for which you get no warning (you can't get a second number whose value is the exact size of the error. After all, the 'delta' is not blessed either, so that would not be possible). As you do more and more math with doubles, those errors compound. And it explains why this happens.
You have a few alternatives.
Integers (long and int for example) only do one thing 'silently', which is to 'loop' from their maximum value (Long.MAX_VALUE and Integer.MAX_VALUE - 2^31-1 and 2^63-1), to their minimum, i..e Integer.MAX_VALUE + 1 is in fact a large negative number, in fact, it's Integer.MIN_VALUE: It looped all the way around.
Other than that, they are 'perfect'. No silent rounding there. Trivial example: Don't store euros in a double. Store cents in a long.
This is a java class that guarantees perfection. However, this comes at grave cost:
double math.Given that there's no need to divide anything, you could just use that, or even better, BigInteger (as you don't appear to need decimal math in the first place - and BigInteger will go arbitrary large, as large as your system's memory will let you).