java - 在 Java 中找到百万分之一的斐波那契数列

Question

在斐波那契数列中，每一项都是前两项的总和。

fibonacci(1) == 1, fibonacci(0) == 0; 
fibonacci(2) = fibonacci(1) + fibonacci(0);
...

在网上搜索后，我发现这个算法可以解决:

这是我的代码:

import java.math.BigInteger;

public class Fibonacci {
    public static BigInteger fib(BigInteger n) {
        double p = (1 + Math.sqrt(5)) / 2;
        double q = (1 - Math.sqrt(5) / 2;
        BigInteger result = BigInteger.ZERO;
        result = ( Math.pow(p, n) - Math.pow(q, n) ) / Math.sqrt(5); //error
        return result;
    }
}

那个错误怎么解决，我要参数是BigInteger，不是Integer，返回数也是BigInteger。

Answer 1

您需要使用 BigDecimal#pow() 而不是 Math.pow() .

因为 Math.pow() 返回 double，但是如果 p 和 n 太大那么它将引发原始溢出错误。

BigDecimal bp = new BigDecimal(p);
BigDecimal bq = new BigDecimal(q);

BigDecimal result = bp.pow(n); // n must be in the range 0 through 999999999, inclusive. ZERO. 

现在 result 得到 p^n 作为 BigDecimal。希望您了解 BigDecimal 计算。