5

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

我一直得到正确的结果，直到我通过1475作为我的方法的参数。我NumberFormatException: Infinite or 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();
}
4

4 回答 4

5

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

对于 n = 2000，它在我的计算机上花费了 7 毫秒。

于 2013-08-03T02:11:59.603 回答
1

你的问题在这里：

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

结果Math.floor(Math.pow(phi, n)/(squareRoot))是给你无限或NaN。

根据BigDecimal javadoc ，如果您使用具有无限值或 NaN 的双精度数，则构造函数 ( BigDecimal(double)) 可能会抛出NumberFormatException

于 2013-08-03T01:51:58.367 回答
1

这不是 INF / NaN 的原因，但它绝对是错误的。这 ...

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

……相当于这个……

double squareRoot = Math.sqrt(5));

... 因为(1/2)是整数除法，返回一个整数值；即零。

事实上，我认为 INF / NaN 最可能的解释是“phi 1475 ”太大而无法表示为double. 所以该pow方法正在返回INF......这是“太大”在Java中表示为浮点数的方式。

如果您想以这种方式计算斐波那契数，您需要使用能够表示所涉及的非常大的数字的表示......并以足够的准确度表示它们。Javadouble类型无法做到这一点。确实，很难使用BigDecimal... 进行计算，正如对已接受答案的评论所表明的那样！

我建议使用递归关系。它会变得更简单......而且可能也会更有效。

于 2013-08-03T01:52:28.053 回答
0

使用 float 或 double创建不是一个好主意，BigDecimal因为它再次限制了它们的范围，您必须首先创建一个 BigDecimal 并对其功能进行一些操作，例如：

BigDecimal a;
BigDecimal b;
x1.pow(b);
于 2013-08-03T02:14:27.663 回答