performance - 有没有比这个更好的方法(性能)计算斐波那契？

Question

我编写了这段代码..我需要充分利用它..我真的需要计算斐波那契数的最佳性能..请帮助..

我已经阅读了一些此类计算的代码，我认为我掌握了其中的精华。

请帮我评估一下.. plz..

ps: 我真的需要 BigInteger.. 我会计算大量的斐波那契数列

ps2:我已经用这个算法计算了一些大数字，我得到了很好的响应时间..但我需要知道它是否可以更好

ps3:要运行此代码，您需要使用此 VM 参数 -Xss16384k (StackSize)

public class Fibonacci {

    private static BigInteger[] fibTmp = { BigInteger.valueOf(0), BigInteger.valueOf(1) };

    public static BigInteger fibonacci(long v) {

        BigInteger fib = BigInteger.valueOf(0);

        if (v == 1) {

            fib = BigInteger.valueOf(1);

        } else if (v == 0) {

            fib = BigInteger.valueOf(0);

        } else {

            BigInteger v1 = fibonacci(v - 1);
            BigInteger v2 = fibTmp[(int) (v - 2)];

            fib = v1.add(v2);
        }

        synchronized (fibTmp) {

            if (fibTmp.length - 1 < v)
                fibTmp = Arrays.copyOf(fibTmp, (int) (v + 10));

            fibTmp[(int) v] = fib;
        }

        return fib;
    }
}

Answer 1

是的，有更好的方法。这是一种经过log(n) 测试的非常有效的方法，可以在给定正整数作为输入的情况下以任意精度计算斐波那契值。该算法改编自 SICP 的解决方案的 exercise 1.19 :

public static BigInteger fibonacci(int n) {

    int count = n;
    BigInteger tmpA, tmpP;
    BigInteger a = BigInteger.ONE;
    BigInteger b = BigInteger.ZERO;
    BigInteger p = BigInteger.ZERO;
    BigInteger q = BigInteger.ONE;
    BigInteger two = new BigInteger("2");

    while (count != 0) {

        if ((count & 1) == 0) {
            tmpP = p.multiply(p).add(q.multiply(q));
            q = two.multiply(p.multiply(q)).add(q.multiply(q));
            p = tmpP;
            count >>= 1;
        }

        else {
            tmpA = b.multiply(q).add(a.multiply(q).add(a.multiply(p)));
            b = b.multiply(p).add(a.multiply(q));
            a = tmpA;
            count--;
        }

    }

    return b;  

}

在本书的链接章节中，解释了它是如何工作的(向下滚动到练习 1.19)，并指出:

This is a clever algorithm for computing the Fibonacci numbers in a logarithmic number of steps ... This exercise was suggested by Joe Stoy, based on an example in Kaldewaij, Anne. 1990. Programming: The Derivation of Algorithms.

当然，如果需要反复计算相同的值，可以通过 memoizing 进一步提高性能。已经计算出的结果，例如使用 map 存储以前的值。