NumberFormatException: Infinite or NaN

Question

I have a method that takes n and returns the nth Fibonacci number. Inside the method implementation, I use BigDecimal to get the nth Fibonacci number, then I use the toBigInteger() method to get the number as a BigInteger object, and this, of course, because I work with huge numbers in my application.

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

Could you explain to me why I get this exception?

Here is 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) too big (infinity), double cannot save it, use BigDecimal instead.

How about flow:

 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(); } 

according to the formula:

UPDATE: the above path is incorrect because Math.sqrt (5) is not accurate enough as the comment said. I tried to more accurately derive sqrt (5) using the Netown method and found out that x1.pow(n).subtract(x2.pow(n)).divide(...) takes a very long time, it takes 30 seconds for n = 200 on my computer.

I think the recursive path with the cache is slower:

  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; } } 

He spent 7 ms on 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)) gives you infinity or NaN.

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

Answer 3

This is not the cause of INF / NaN, but it is definitely wrong. It...

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

... 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 INF / NaN is that "phi ¹⁴⁷⁵ " is too large to be represented as double . So the pow method returns INF ... this is the way that "too big" is represented as a floating-point number in Java.

---

If you want to calculate Fibonacci numbers this way, you need to use a representation that can display really large numbers ... and represent them with sufficient accuracy. The Java double type cannot do this. Indeed, it is difficult to perform calculations using BigDecimal ... as the comments on the accepted answer show!

I would recommend using a recursive relation. It will be much easier ... and probably more efficient.

Answer 4

It is not recommended to create a BigDecimal using float or double, because it again limits their range, you must first create a BigDecimal and perform some operation with its functions, such as:

 BigDecimal a; BigDecimal b; x1.pow(b);