Find The Millionth Fibonacci in Java

Question

In Fibonacci sequence each item is the sum of the previous two.

fibonacci(1) == 1, fibonacci(0) == 0; 
fibonacci(2) = fibonacci(1) + fibonacci(0);
...

After searching the web I find this algorithm to solve:

And here is my code:

import java.math.BigInteger;

public class Fibonacci {
    public static BigInteger fib(BigInteger n) {
        double p = (1 + Math.sqrt(5)) / 2;
        double q = (1 - Math.sqrt(5) / 2;
        BigInteger result = BigInteger.ZERO;
        result = ( Math.pow(p, n) - Math.pow(q, n) ) / Math.sqrt(5); //error
        return result;
    }
}

How to solve that error, I want the parameter is BigInteger, not Integer, and the return number is BigInteger, too.

Answer 1

Instead of Math.pow() you need to use BigDecimal#pow().

Because Math.pow() returns double, but if p and n are too large than it will easily produce primitive overflow and error will occur.

BigDecimal bp = new BigDecimal(p);
BigDecimal bq = new BigDecimal(q);

BigDecimal result = bp.pow(n); // n must be in the range 0 through 999999999, inclusive. ZERO. 

Now result got p^n as BigDecimal. Hope you understand the BigDecimal calculation.

Answer 2

The standard mathematical operators in Java is not overridden for Big numbers. These are just objects. So you have to work with them as objects.

public static BigInteger fib(int n) {
    BigDecimal phi = new BigDecimal((1 + Math.sqrt(5)) / 2).pow(n);
    BigDecimal phi_ = new BigDecimal((1 - Math.sqrt(5)) / 2).pow(n);
    BigDecimal divider = new BigDecimal(Math.sqrt(5));
    BigDecimal result = phi.subtract(phi_).divide(divider);
    return result.toBigInteger();
}

Updated:

As @Gassa said, the above method accumulates error because

BigDecimal is initialized by a double which in turn has precision of only 15 decimal digits

but we need much more.

So we can use sqrt method for BigDecimal from here:

public static BigInteger fib(int n) {
    BigDecimal one = new BigDecimal(1);
    BigDecimal sqrtFive = bigSqrt(new BigDecimal(5));
    BigDecimal two = new BigDecimal(2);

    BigDecimal phi = one.add(sqrtFive).divide(two, RoundingMode.HALF_DOWN).pow(n);
    BigDecimal phi_ = one.subtract(sqrtFive).divide(two, RoundingMode.HALF_DOWN).pow(n);

    BigDecimal result = phi.subtract(phi_).divide(sqrtFive, RoundingMode.HALF_DOWN);

    return result.toBigInteger();
}

private static final BigDecimal SQRT_DIG = new BigDecimal(150);
private static final BigDecimal SQRT_PRE = new BigDecimal(10).pow(SQRT_DIG.intValue());

/**
 * Private utility method used to compute the square root of a BigDecimal.
 *
 * @author Luciano Culacciatti
 * @url http://www.codeproject.com/Tips/257031/Implementing-SqrtRoot-in-BigDecimal
 */
private static BigDecimal sqrtNewtonRaphson  (BigDecimal c, BigDecimal xn, BigDecimal precision){
    BigDecimal fx = xn.pow(2).add(c.negate());
    BigDecimal fpx = xn.multiply(new BigDecimal(2));
    BigDecimal xn1 = fx.divide(fpx,2*SQRT_DIG.intValue(), RoundingMode.HALF_DOWN);
    xn1 = xn.add(xn1.negate());
    BigDecimal currentSquare = xn1.pow(2);
    BigDecimal currentPrecision = currentSquare.subtract(c);
    currentPrecision = currentPrecision.abs();
    if (currentPrecision.compareTo(precision) <= -1){
        return xn1;
    }
    return sqrtNewtonRaphson(c, xn1, precision);
}

/**
 * Uses Newton Raphson to compute the square root of a BigDecimal.
 *
 * @author Luciano Culacciatti
 * @url http://www.codeproject.com/Tips/257031/Implementing-SqrtRoot-in-BigDecimal
 */
public static BigDecimal bigSqrt(BigDecimal c){
    return sqrtNewtonRaphson(c,new BigDecimal(1),new BigDecimal(1).divide(SQRT_PRE));
}