Fibonacci nth term formula with BigInteger in java

Question

I'm trying to solve the nth term of fibonacci series based on this formula.

Here is my code :

public BigInteger getFibonacciNumber(int index) {
        final Instant start = Instant.now();

        if (index == 0) return BigInteger.ZERO;
        if (index == 1) return BigInteger.ONE;

        BigDecimal phi1 = new BigDecimal("5");
        phi1 = phi1.sqrt(MathContext.DECIMAL128);
        BigDecimal phi2 = phi1.subtract(BigDecimal.ONE);
        phi1 = phi1.add(BigDecimal.ONE);
        phi1 = phi1.divide(new BigDecimal("2"), 8, RoundingMode.HALF_EVEN);
        phi2 = phi2.divide(new BigDecimal("2"), 8, RoundingMode.HALF_EVEN);


        BigDecimal p1 = phi1.pow(index);
        BigDecimal p2 = phi2.pow(index);
        p1 = p1.subtract(p2);
        BigDecimal sqrt5 = BigDecimal.valueOf(Math.sqrt(5));
        p1 = p1.divide(sqrt5, 8, RoundingMode.HALF_EVEN);
        Log.infov(
                "Fibonacci number for index {0} computed in {1}",
                index, Duration.between(start, Instant.now()));
        return p1.toBigInteger();
    }

But I have problems, for example, with the 100th term, I expect 354224848179261915075 when I get 354224875546939407559. I think that there's a problem with the scale or the rounding method of the BigDecimal but I don't know how to resolve it. Do you have any idea?

Answer 1

I found two problems regarding the precision of your calculations. First, the divide needs a higher scale value. Second, in the end you cast the result to a BigInteger, which simply cuts off the decimal places. You need to round the value to an integer value first. I also restructured your method a little:

public static BigInteger getFibonacciNumber(int index) {
    if (index == 0) return BigInteger.ZERO;
    if (index == 1) return BigInteger.ONE;

    BigDecimal sqrt5 = new BigDecimal(5).sqrt(MathContext.DECIMAL128);

    BigDecimal PHI = BigDecimal.ONE.add(sqrt5).divide(new BigDecimal(2), RoundingMode.HALF_UP);
    BigDecimal phi = BigDecimal.ONE.subtract(sqrt5).divide(new BigDecimal(2), RoundingMode.HALF_UP);

    BigDecimal p1 = PHI.pow(index, MathContext.DECIMAL128);
    BigDecimal p2 = phi.pow(index, MathContext.DECIMAL128);
    p1 = p1.subtract(p2);

    p1 = p1.divide(sqrt5, 50, RoundingMode.HALF_UP);

    return p1.setScale(0, RoundingMode.HALF_UP).toBigInteger();
}

If you input 100 the result is as expected:

354224848179261915075

Edit: Had to make the precision even higher as the result was still a little bit off