CODEWITHSUNDEEP
javamathcatalan
brack11
brack11

Reputation: 181

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.

Upvotes: 1

Views: 114

Answers (2)

Paul Janssens
Paul Janssens

Reputation: 722

Using BigDecimal is no help here, you have to perform the division AFTER you do the multiplication, in which case your algorithm works with BigInteger.

Upvotes: 1

Absent
Absent

Reputation: 914

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)

Upvotes: 2

Related Questions