使斐波那契更快

我被要求编写斐波那契算法的简单实现，然后使其更快。

这是我的初始实现

public class Fibonacci {

    public static long getFibonacciOf(long n) {
        if (n== 0) {
            return 0;
        } else if (n == 1) {
            return 1;
        } else {
            return getFibonacciOf(n-2) + getFibonacciOf(n-1);
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner (System.in);
        while (true) {
            System.out.println("Enter n :");
            long n = scanner.nextLong();
            if (n >= 0) {
                long beginTime = System.currentTimeMillis();
                long fibo = getFibonacciOf(n);
                long endTime = System.currentTimeMillis();

                long delta = endTime - beginTime;

                System.out.println("F(" + n + ") = " + fibo + " ... computed     in " + delta + " milliseconds");
            } else {
                break;

            }
        }

    }

}

正如你所看到的，我正在使用System.currentTimeMillis（）来简单测量计算斐波那契时经过的时间。

这种实现速度很快呈指数级增长，如下图所示

所以我有一个简单的优化想法。将以前的值放在 HashMap 中，而不是每次都重新计算它们，只需将它们从 HashMap 中取回（如果它们存在）。如果它们不存在，我们就把它们放在HashMap中。

这是新版本的代码

public class FasterFibonacci {

    private static Map<Long, Long> previousValuesHolder;
    static {
        previousValuesHolder = new HashMap<Long, Long>();
        previousValuesHolder.put(Long.valueOf(0), Long.valueOf(0));
        previousValuesHolder.put(Long.valueOf(1), Long.valueOf(1));
    }
    public static long getFibonacciOf(long n) {
        if (n== 0) {

            return 0;
        } else if (n == 1) {
            return 1;
        } else {
            if (previousValuesHolder.containsKey(Long.valueOf(n))) {
                return previousValuesHolder.get(n);
            } {

                long newValue = getFibonacciOf(n-2) + getFibonacciOf(n-1);
                previousValuesHolder.put(Long.valueOf(n),     Long.valueOf(newValue));
                return newValue;
            }

        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner (System.in);
        while (true) {
            System.out.println("Enter n :");
            long n = scanner.nextLong();
            if (n >= 0) {
                long beginTime = System.currentTimeMillis();
                long fibo = getFibonacciOf(n);
                long endTime = System.currentTimeMillis();

                long delta = endTime - beginTime;

                System.out.println("F(" + n + ") = " + fibo + " ... computed     in " + delta + " milliseconds");
            } else {
                break;

            }
        }

    }

这种变化使计算速度非常快。我立即计算了从2到103的所有值，并且在F（104）处得到了一个很长的溢出（给我F（104） = -7076989329685730859，这是错误的）。我发现它是如此之快，以至于**我想知道我的代码中是否有任何错误（感谢您的检查，请让我知道）**。请看第二张图片：

我更快的斐波那契算法的实现是否正确（在我看来，因为它得到的值与第一个版本相同，但由于第一个版本太慢，我无法用它计算更大的值，如F（75）））？我还可以使用哪些其他方法来加快速度？还是有更好的方法来使它更快？另外，我如何计算更大值（如150，200）的斐波那契而不得到**长溢出**？虽然它看起来很快，但我想把它推向极限。我记得Abrash先生说过“最好的优化器在你的两只耳朵之间”，所以我相信它仍然可以改进。感谢您的帮助

[版本说明：]虽然这个问题解决了我问题中的一个要点，但你可以从上面看到我有额外的问题。