NumberFormatException: Infinite or NaN

Question

I have a method that takes n and returns nth Fibonacci number. Inside the method implementation I use BigDecimal to get the nth Fibonacci number then I use method toBigInteger() to get the number as a BigInteger object and that's surely because I am working with huge numbers in my application.

I keep getting correct results until I pass 1475 as an argument for my method. I get NumberFormatException: Infinite or NaN in this case without any clear reason for me.

Could you please explain me why am I getting this exception?

Here's my method:

BigInteger getFib(int n){
     double phi = (1 + Math.sqrt(5))/2;
     double squareRoot = (Math.sqrt(5)) + (1/2);
     BigDecimal bd = new BigDecimal(Math.floor(Math.pow(phi, n)/(squareRoot)));
     return bd.toBigInteger();
}

Answer 1

Your Math.pow(phi, n) is too big(Infinity),double is unable to store it,use BigDecimal instead.

How about the flowing:

static BigInteger getFib(int n) {
    BigDecimal x1 = new BigDecimal((1 + Math.sqrt(5)) / 2);
    BigDecimal x2 = new BigDecimal((1 - Math.sqrt(5)) / 2);
    return x1.pow(n).subtract(x2.pow(n))
            .divide(new BigDecimal(Math.sqrt(5))).toBigInteger();
}

from the formula:

UPDATE: the above way is incorrect,because Math.sqrt(5) does not has enough precision as the comment said. I've tried to culculate sqrt(5) with more precision using Netown's method,and found out that x1.pow(n).subtract(x2.pow(n)).divide(...) is very time-consuming,it spended about 30 seconds for n = 200 in my computer.

I think the recursive way with a cache is mush faster:

    public static void main(String[] args) {
    long start = System.nanoTime();
    System.out.println(fib(2000));
    long end = System.nanoTime();
    System.out.println("elapsed:"+ (TimeUnit.NANOSECONDS.toMillis(end - start)) + " ms");
}

private static Map<Integer, BigInteger> cache = new HashMap<Integer, BigInteger>();

public static BigInteger fib(int n) {
    BigInteger bi = cache.get(n);
    if (bi != null) {
        return bi;
    }
    if (n <= 1) {
        return BigInteger.valueOf(n);
    } else {
        bi = fib(n - 1).add(fib(n - 2));
        cache.put(n, bi);
        return bi;
    }
}

It spend 7 ms in my computer for n = 2000.