我有一个方法,取n并返回第n个斐波纳契数.在方法实现中我使用BigDecimal来获取第n个Fibonacci数,然后我使用方法toBigInteger()来获取数字作为BigInteger对象,这肯定是因为我在我的应用程序中处理大量数字.

我一直得到正确的结果,直到我通过1475作为我的方法的参数.我得到NumberFormatException：在这种情况下无限或NaN没有任何明确的理由.

你能解释一下我为什么会得到这个例外吗？

这是我的方法：

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

解决方法:

你的Math.pow(phi,n)太大(Infinity),double无法存储它,而是使用BigDecimal.

流动怎么样：

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

从公式：

更新：
上面的方法是不正确的,因为Math.sqrt(5)没有足够的精度,如评论所说.我试图使用Netown的方法更精确地计算sqrt(5),并发现x1.pow(n).subtract(x2.pow(n)).divide(…)非常耗时,我的电脑在n = 200时大约30秒.

我认为缓存的递归方式更快：

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

它在我的计算机上花费7毫秒,n = 2000.