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

Burghley

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.

Sulfatize

80776376321566249506594310369598056472970340482296717528846843403451897402974064859772924316558310641200045712627734657615023748095728890842338729730058516953255187002299033438319847576705753443152494213260389820409161525095795264470887903665494432793647441708843372648309455220167976247625265489563686977653 – Sulfatize

I'm not sure this produces correct fibonacci numbers above 71, due to the limited precision of Math.sqrt(5). According to OEIS oeis.org/A000045/b000045.txt the 1475th fibonacci number is 80776376321562253452154706580907152472160058839390611448949567098441231253468434896849142844747379890769208411232896054029055178267612427002841980625179761093160192801001760246411376424603323375022055947591818021711030476170155984070706514302882384774850491778697586460466725335267737494971685815687040886025. – Dewhurst

Yes ... getting an accurate value out of this formula is going to be exceedingly difficult. 1) BigDecimal numbers have fixed precision to the right of the decimal point. 2) You can't use Math.sqrt(5) ... it is not accurate enough. – Wont

Impressive. i tried loops but its too curmbersome then i gave recursion a short and as the number increased, it slowed down now back to this and all is good. caching improves speed – Contemporaneous

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

Ornstead

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.

Wont

That's right that "phi1475" gives infinity. I could actually use BigDecimal instead and it works fine but there's still one problem. What's the equivalent to Math.floor in this case for BigDecimal? – Burghley

Try round with a rounding mode of FLOOR. But I thing that using the recurrence relation is likely to be much faster and more reliable. – Wont

Answer 4

It's not a good idea to create BigDecimal with float or double because its again limit to the range of them you must create a BigDecimal at first and do some operation with its functions like:

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

Carrnan

BigDecimal does not have a pow method accepting another BigDecimal. In fact it only support power to integer (int) values. – Thicken