是否有比这更好的方法(性能)计算斐波那契？

Question

我制作了这个代码..而且我需要充分利用它...我真的需要计算斐波那契数字的最佳表现..请帮助...

我已经阅读了一些这类计算的代码,我想我得到了最好的...

Avaliate this for me .. 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)给定正整数作为输入的情况下,这是一种经过测试且非常有效的方法,用于以任意精度计算Fibonacci的值.该算法改编自一个解决SICP的练习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),并且声明:

这是一个聪明的算法,用于以对数步数计算斐波纳契数...这个练习是由Joe Stoy根据安德尔卡德怀伊的一个例子提出的.1990年规划:算法的推导.

当然,如果需要一次又一次地计算相同的值,则可以通过记忆已经计算的结果来实现进一步的性能增益,例如使用用于存储先前值的映射.

Answer 2

您的实现不适用于任何合适的数字，因为它会导致堆栈溢出。

我看不出有任何理由在这里使用递归。递归性很漂亮，但通常更重（它依赖于语言）。这是一个带有简单for循环的有效实现：

private static BigInteger[] fibTmp = {BigInteger.ZERO, BigInteger.ONE};
private static int maxCached = 1;
public static BigInteger fibonacci(int v) {
    if (fibTmp.length<=v) {
        fibTmp = Arrays.copyOf(fibTmp, v*5/4);
    }
    for (; maxCached<v;) {
        maxCached++;
        BigInteger v1 = fibTmp[maxCached - 1];
        BigInteger v2 = fibTmp[maxCached - 2];
        fibTmp[maxCached] = v1.add(v2);
    }
    return fibTmp[v];
}

这是一种直接实现，无需在文献中寻找高效的斐波那契算法。你最好去找他们。

另请注意，这种基于缓存的实现会占用大量内存，并且仅在多次调用该函数时才有意义。