CODEWITHSUNDEEP
javacatalan
Kemper Lee
Kemper Lee

Reputation: 276

Java "Catalan number" generator is almost working right

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:

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);
}

Upvotes: 0

Views: 104

Answers (2)

Kemper Lee
Kemper Lee

Reputation: 276

I was able to translate the link's code into my problem, however, I was still unable to figure out the syntax/use case for the BigInteger Object.

public static long catalanNumber(int number) 
{   // negative catalan DNE
    if(!(number < 0))
    {   // assign starting catalan number
        double value = 1;
        // C(0) & C(1) = 1
        if(number > 1)
        {
            for(long place = number + 2; 
                 place <= 2 * number; place++) 
            {
                value *= place;
                value /= (place - number);
            }
        }
        // remove decimals
        return (long)value;
    }
    // invalid catalan number (n < 0)
    return -1;
}

^ This ^ does work great but having that double in my loop makes me a little nervous. I would love to see how to do it using the BigInteger Object as well/instead though because I know this will only work to X number of bits till it overflows.

Where to learn more about BigInteger Objects:

Also, thank you @rzwitserloot for explaining how the floating points handle large numbers. I would highly recommend reading his answer if you are new to Java -- or even programming in general.

Upvotes: 0

rzwitserloot
rzwitserloot

Reputation: 103273

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.

Use only integral math

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.

Use BigDecimal

This is a java class that guarantees perfection. However, this comes at grave cost:

  1. It's slow as molasses, many orders of magnitude slower than double math.
  2. It will crash if you divide, unless the division so happens to work out 'nicely', or you explicitly ask for... loss of precision. What's 1 divided by 3, written in decimal, and without any losses? You'll find that this question cannot be answered. It's 0.3333333333... and that just keeps going forever, so you cannot losslessly represent the very simple 1/3 in decimal notation. I'm not sure if BigDecimal uses decimal or more likely binary, but the point is, no matter what base you choose, various divisors will not 'fit'. (In decimal, 1/4 is fine: That's 0.25, with perfect precision, so that one can be done).

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).

Upvotes: 3

Related Questions