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.

Answer 2

Your problem is here:

BigDecimal bd = new BigDecimal(Math.floor(Math.pow(phi, n)/(squareRoot)));

the result of Math.floor(Math.pow(phi, n)/(squareRoot)) is giving you either infinite or NaN.

According to the BigDecimal javadoc that constructor (BigDecimal(double)) could throw a NumberFormatException if you use a double with value infinite or NaN

Answer 3

This is not cause of the INF's / NaN's but it is definitely wrong. This ...

double squareRoot = (Math.sqrt(5)) + (1/2);

... is equivalent to this ...

double squareRoot = Math.sqrt(5));

... because (1/2) is an integer division, returning an integer value; i.e. zero.

---

In fact, I think the most likely explanation for the INF / NaN is that "phi¹⁴⁷⁵" is too large to be represented as a double. So the pow method is returning INF ... which is the way that "too large" is represented as a floating number in Java.

---

If you want to compute Fibonacci numbers this way, you need to use a representation that is capable of representing the really large numbers involved ... and represent them with sufficient accuracy. The Java double type cannot do this. And indeed, it is hard to do the computation using BigDecimal ... as the comments on the accepted answer demonstrate!

I'd recommend using the recurrence relation. It is going to be much simpler ... and probably more efficient as well.