java - Java 中的超大型斐波那契数列

Question

我正在尝试快速计算大斐波那契数。这是我的代码。对于100万以上的数据来说速度太慢了，如何改进？

public static BigInteger fib(BigInteger n) {

        int k = n.intValue();
        BigInteger ans = null;

        if(k == 0) { 
            ans = new BigInteger("0");
        } else if(Math.abs(k) <= 2) {
            ans = new BigInteger("1");
        } else {
            BigInteger km1 = new BigInteger("1");
            BigInteger km2 = new BigInteger("1");

            for(int i = 3; i <= Math.abs(k); ++i) {
                ans = km1.add(km2);
                km2 = km1;
                km1 = ans;
            }
        }

       if(k<0 && k%2==0) { ans = ans.negate(); }
       return ans;
    } 

比奈效果很好。多谢你们!

Answer 1

一种方法是计算 2x2 矩阵的 (N-1)th 次方:

A = ((1, 1), (1, 0))

然后我们有

Fib(n) = A^(n-1)[0][0], for n >= 1

并且可以使用Exponentiation by squaring有效地计算矩阵A的幂