javamathcatalan

Error while calculating Catalan number sequence

Whatever I tried this following code throws ArithmeticException with message "Non-terminating decimal expansion; no exact representable decimal result." on bigger numbers (like 43, 50, 56 etc).

Here is the code:

private BigDecimal catalan(int n) {
    if (n <= 1) {
        return BigInteger.ONE;
    }
    return BigDecimal.valueOf(4)
            .multiply(BigDecimal.valueOf(n))
            .subtract(BigDecimal.valueOf(2))
            .divide(BigDecimal.valueOf(n).add(BigDecimal.ONE))
            .multiply(new BigDecimal(catalan(n - 1)));
}

This method works flawlessly on small n numbers but when it comes to higher values it crashes.

Solution

  • The Exception occurs because of the line

    .divide(BigDecimal.valueOf(n).add(BigDecimal.ONE))

    Here you did not give a precision scale, which means that it is possible to get an infinitely long decimal expansion, e.g when dividing 1 by 3.

    To solve the error you need to put in a rounding scale and a rounding mode.

    E.g:

    .divide(BigDecimal.valueOf(n).add(BigDecimal.ONE), 10, RoundingMode.HALF_UP)