让斐波那契更快

Question

我需要编写斐波那契算法的简单实现，然后让它更快。

这是我的初步实现

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) 处得到 long 溢出（ 给我 F(104) = -7076989329685730859 ，这是错误的)。我发现它太快了**我想知道我的代码中是否有任何错误（感谢您的检查并让我知道）**。请看第二张图：

我更快的斐波那契算法的实现是否正确（对我来说似乎是正确的，因为它获得与第一个版本相同的值，但由于第一个版本太慢，我无法用它计算更大的值，例如 F( 75））？还有什么其他方法可以使它更快？或者有没有更好的方法让它更快？此外，如何计算更大值（例如 150、200）的斐波那契数列而不会出现 **long 溢出**？虽然它看起来很快，但我想将它推向极限。我记得 Abrash 先生说过'最好的优化器就在你的两只耳朵之间'，所以我相信它仍然可以改进。感谢您的帮助

[版注：] 虽然 this 问题解决了我问题的主要问题之一，但从上面可以看出我还有其他问题。

Answer 1

动态规划

Idea:Instead of recomputing the same value multiple times you just store the value calculated and use them as you go along.

f(n)=f(n-1)+f(n-2) 且 f(0)=0,f(1)=1。因此，当您计算出 f(n-1) 时，如果您存储 f(n) 和 f(n-1) 的值，则可以轻松计算出 f(n)。

我们先来看一个 Bignums 数组。 A[1..200]。将它们初始化为-1。

伪代码

fact(n)
{
if(A[n]!=-1) return A[n];
A[0]=0;
A[1]=1;
for i=2 to n
  A[i]= addition of A[i],A[i-1];
return A[n]
}

这会在 O(n) 时间内运行。自己检查一下。

这种技术也称为记忆。

想法

动态规划（通常称为 DP）是解决特定 class 问题的一种非常强大的技术。它需要非常优雅的方法表述和简单的思维，并且编码部分非常容易。思路很简单，如果你已经用给定的输入解决了一个问题，那么保存结果以供将来参考，以避免再次解决同样的问题.. 很快'Remember your Past'。

如果给定的问题可以分解成更小的子问题，这些更小的子问题又被分解成更小的子问题，在这个过程中，如果你观察到一些over-lappping subproblems，那么这对 DP 来说是一个很大的暗示。此外，子问题的最优解有助于给定问题的最优解（称为 Optimal Substructure Property ）。

有两种方法可以做到这一点。

1.) Top-Down : Start solving the given problem by breaking it down. If you see that the problem has been solved already, then just return the saved answer. If it has not been solved, solve it and save the answer. This is usually easy to think of and very intuitive. This is referred to as Memoization. (I have used this idea).

2.) Bottom-Up : Analyze the problem and see the order in which the sub-problems are solved and start solving from the trivial subproblem, up towards the given problem. In this process, it is guaranteed that the subproblems are solved before solving the problem. This is referred to as Dynamic Programming. (MinecraftShamrock used this idea)

还有更多！

（其他方法）

看看我们寻求更好解决方案的追求并没有就此结束。你会看到不一样的做法-

If you know how to solve recurrence relation then you will find a solution to this relation

f(n)=f(n-1)+f(n-2) given f(0)=0,f(1)=1

解完你就得出公式了-

f(n)= (1/sqrt(5))((1+sqrt(5))/2)^n - (1/sqrt(5))((1-sqrt(5))/2)^n

可以写成更紧凑的形式

f(n)=floor((((1+sqrt(5))/2)^n) /sqrt(5) + 1/2)

复杂性

你可以在O(logn)次操作中得到一个数字的幂。你必须学习 Exponentiation by squaring.

编辑：值得指出的是，这并不一定意味着可以在 O(logn) 中找到斐波那契数。实际上我们需要计算的位数是线性增长的。可能是因为我所说的位置似乎声称可以在 O(logn) 时间内计算数字的阶乘是错误的想法。 [Bakurui,MinecraftShamrock 对此发表评论]

Answer 2

如果您需要非常频繁地计算 n 个斐波那契数，我建议使用 amalsom 的答案。

但是如果您想计算一个非常大的斐波那契数，您将运行内存不足，因为您正在存储所有个较小的斐波那契数。以下伪代码仅将最后两个斐波那契数保留在内存中，即它需要更少的内存：

fibonacci(n) {
    if n = 0: return 0;
    if n = 1: return 1;
    a = 0;
    b = 1;
    for i from 2 to n: {
        sum = a + b;
        a = b;
        b = sum;
    }
    return b;
}

分析
这可以计算非常高的斐波那契数而内存消耗非常低：我们有 O(n) 次 循环重复 n-1 次。 space 的复杂度也很有趣：第 n 个斐波那契数的长度为 O(n)，可以很容易地显示：
F_n <= 2 * F_n-1
这意味着第 n 个斐波那契数最多是其前身的两倍。将二进制数加倍相当于一次左移，这会将必要的位数增加一位。所以表示第 n 个斐波那契数最多需要 O(n) space。我们在内存中最多有三个连续的斐波那契数，这使得 O(n) + O(n-1) + O(n-2) = O(n) 总 space 消耗.与此相反，记忆算法总是在内存中保留前 n 个斐波那契数，这使得 O(n) + O(n-1) + O(n-2) + ... + O(1) = O(n^2) space 消耗.

那么应该使用哪种方式呢？
将所有较低的斐波那契数保留在内存中的唯一原因是如果您非常频繁地需要斐波那契数。这是一个平衡时间和内存消耗的问题。

Answer 3

预计算大量 fib(n) 结果，并将它们存储为算法中的查找 table。砰，免费 "speed"

现在，如果您需要计算 fib(101) 并且您已经存储了 0 到 100 的 fib，这就像尝试计算 fib(1)。

很可能这不是本作业要查找的内容，但它是一个完全合法的策略，基本上是从运行算法中进一步提取缓存的想法。如果您知道您可能会经常计算前 100 个 fibs，并且您需要非常非常快地完成计算，那么没有比 O(1) 更快的了。因此，完全带外计算这些值并存储它们以便以后查找。

当然，在计算值时也会缓存它们:) 重复计算是浪费。

Answer 4

这是一段代码，它采用迭代方法而不是递归方法。

输出示例:

Enter n: 5
F(5) = 5 ... computed in 1 milliseconds
Enter n: 50
F(50) = 12586269025 ... computed in 0 milliseconds
Enter n: 500
F(500) = ...4125 ... computed in 2 milliseconds
Enter n: 500
F(500) = ...4125 ... computed in 0 milliseconds
Enter n: 500000
F(500000) = 2955561408 ... computed in 4,476 ms
Enter n: 500000
F(500000) = 2955561408 ... computed in 0 ms
Enter n: 1000000
F(1000000) = 1953282128 ... computed in 15,853 ms
Enter n: 1000000
F(1000000) = 1953282128 ... computed in 0 ms

为便于查看，...省略了部分结果。

代码片段:

public class CachedFibonacci {
    private static Map<BigDecimal, BigDecimal> previousValuesHolder;
    static {
        previousValuesHolder = new HashMap<>();
        previousValuesHolder.put(BigDecimal.ZERO, BigDecimal.ZERO);
        previousValuesHolder.put(BigDecimal.ONE, BigDecimal.ONE);
    }

    public static BigDecimal getFibonacciOf(long number) {
        if (0 == number) {
            return BigDecimal.ZERO;
        } else if (1 == number) {
            return BigDecimal.ONE;
        } else {
            if (previousValuesHolder.containsKey(BigDecimal.valueOf(number))) {
                return previousValuesHolder.get(BigDecimal.valueOf(number));
            } else {
                BigDecimal olderValue = BigDecimal.ONE,
                        oldValue = BigDecimal.ONE,
                        newValue = BigDecimal.ONE;

                for (int i = 3; i <= number; i++) {
                    newValue = oldValue.add(olderValue);
                    olderValue = oldValue;
                    oldValue = newValue;
                }
                previousValuesHolder.put(BigDecimal.valueOf(number), newValue);
                return newValue;
            }
        }
    }

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

                System.out.printf("F(%d) = %.0f ... computed in %,d milliseconds\n", inputNumber, fibo, delta);
            } else {
                System.err.println("You must enter number > 0");
                System.out.println("try, enter number again, please:");
                break;
            }
        }
    }
}

这种方法比递归版本运行得快得多。

在这种情况下，迭代解决方案往往会更快一些，因为每个递归方法调用需要一定的处理器时间。原则上是聪明的编译器可以避免递归方法调用，如果它们遵循简单的话模式，但大多数编译器不这样做。从这个角度来看，迭代解决方案是可取的。

更新：

在 Java 8 版本和 Stream API 可用之后，又一种计算斐波那契的方法可用。

已与 JDK 17.0.2 核实。

代码：

public static BigInteger streamFibonacci(long n) {
    return Stream.iterate(new BigInteger[]{BigInteger.ONE, BigInteger.ONE},
                    p -> new BigInteger[]{p[1], p[0].add(p[1])})
            .limit(n)
            .reduce((a, b) -> b)
            .get()[0];
}

测试输出：

Enter n (q for quit): 5
F(5) = 5 ... computed in 2 ms
Enter n (q for quit): 50
F(50) = 1258626902 ... computed in 0 ms
Enter n (q for quit): 500
F(500) = 1394232245 ... computed in 3 ms
Enter n (q for quit): 500000
F(500000) = 2955561408 ... computed in 4,343 ms
Enter n (q for quit): 1000000
F(1000000) = 1953282128 ... computed in 19,280 ms

效果还不错
请记住，... 只是削减实数的所有后续数字。

Answer 5

斐波那契 (0) = 0
斐波那契 (1) = 1
Fibonacci(n) = Fibonacci(n - 1) + Fibonacci(n - 2)，当 n >= 2

通常有两种计算斐波那契数列的方法：

递归:
```
public long getFibonacci(long n) {
  if(n <= 1) {
    return n;
  } else {
    return getFibonacci(n - 1) + getFibonacci(n - 2);
  }
}
```
这种方式直观易懂，同时由于不复用计算出的斐波那契数，时间复杂度约为O(2^n)，但不存储计算结果，因此节省了space 很多，实际上 space 的复杂度是 O(1).
动态规划:
```
public long getFibonacci(long n) {
  long[] f = new long[(int)(n + 1)];
  f[0] = 0;
  f[1] = 1;
  for(int i=2;i<=n;i++) {
    f[i] = f[i - 1] + f[i - 2];
  }
  return f[(int)n];
}
```
这种 Memoization 方法计算斐波那契数并在计算下一个时重复使用它们。时间复杂度还不错，是O(n)，而space复杂度是O(n)。让我们研究一下是否可以优化 space 的复杂度...因为 f(i) 只需要 f(i - 1) 和 f(i - 2)，所以没有必要存储所有计算出的斐波那契数。

更高效的实现是:
```
public long getFibonacci(long n) {
  if(n <= 1) {
    return n;
  }
  long x = 0, y = 1;
  long ans;
  for(int i=2;i<=n;i++) {
    ans = x + y;
    x = y;
    y = ans;
  }
  return ans;
}
```
时间复杂度O(n)，space复杂度O(1)。

补充： 由于斐波那契数增长惊人的快，long 只能处理少于 100 个斐波那契数。在Java中，我们可以使用BigInteger来存储更多的斐波那契数。

Answer 6

远离斐波那契递归并使用恒等式

(F(2n), F(2n-1)) = (F(n)^2 + 2 F(n) F(n-1), F(n)^2+F(n-1)^2)
(F(2n+1), F(2n)) = (F(n+1)^2+F(n)^2, 2 F(n+1) F(n) - F(n)^2)

这允许您根据 (F(k+1), F(k)) 计算 (F(m+1), F(m))，k 的大小是 m 的一半。迭代地编写除以 2 的一些位移位，这应该为您提供理论上的 O(log n) 平方求幂速度，同时完全保持在整数算术范围内。（好吧，O(log n) 算术运算。由于您将使用大约 n 位的数字，因此一旦您被迫切换到大型整数库，它就不会是 O(log n) 时间。在 F(50 ), 你会溢出整数数据类型，最多只能达到 2^(31).)

（很抱歉没有记住 Java 足以在 Java 中实现它；任何想要的人都可以自由编辑它。）

Answer 7

这是一种在 O(log n) 中可证明的方法（因为循环运行 log n 次） :

/* 
 * Fast doubling method
 * F(2n) = F(n) * (2*F(n+1) - F(n)).
 * F(2n+1) = F(n+1)^2 + F(n)^2.
 * Adapted from:
 *    https://www.nayuki.io/page/fast-fibonacci-algorithms
 */
private static long getFibonacci(int n) {
    long a = 0;
    long b = 1;
    for (int i = 31 - Integer.numberOfLeadingZeros(n); i >= 0; i--) {
        long d = a * ((b<<1) - a);
        long e = (a*a) + (b*b);
        a = d;
        b = e;
        if (((n >>> i) & 1) != 0) {
            long c = a+b;
            a = b;
            b = c;
        }
    }
    return a;
}

我在这里（按照惯例）假设一个乘法/加法/任何操作都是常数时间，与位数无关，即，将使用固定长度的数据类型。

This page 解释了几种最快的方法。为了便于阅读，我只是将它从使用 BigInteger 翻译出来。这是 BigInteger 版本：

/* 
 * Fast doubling method.
 * F(2n) = F(n) * (2*F(n+1) - F(n)).
 * F(2n+1) = F(n+1)^2 + F(n)^2.
 * Adapted from:
 *    http://www.nayuki.io/page/fast-fibonacci-algorithms
 */
private static BigInteger getFibonacci(int n) {
    BigInteger a = BigInteger.ZERO;
    BigInteger b = BigInteger.ONE;
    for (int i = 31 - Integer.numberOfLeadingZeros(n); i >= 0; i--) {
        BigInteger d = a.multiply(b.shiftLeft(1).subtract(a));
        BigInteger e = a.multiply(a).add(b.multiply(b));
        a = d;
        b = e;
        if (((n >>> i) & 1) != 0) {
            BigInteger c = a.add(b);
            a = b;
            b = c;
        }
    }
    return a;
}

Answer 8

前段时间采用了类似的方法，我刚刚意识到您可以进行另一种优化。

如果你知道两个大的连续答案，你可以以此为起点。例如，如果您知道 F(100) 和 F(101) ，然后计算 F(104) 与计算 [=31= 大致一样困难 (*) ]F(4) 基于 F(0) 和 F(1).

向上迭代计算与使用缓存递归计算一样高效，但使用的内存更少。

做了一些总结后，我也意识到，对于任何给定的 z < n:

F(n)=F(z) * F(n-z) + F(z-1) * F(n-z-1)

如果 n 是奇数，你选择 z=(n+1)/2，那么这将减少到

F(n)=F(z)^2+F(z-1)^2

在我看来，您应该能够通过我尚未找到的方法使用它，您应该能够使用上述信息在等于以下操作的次数中找到 F(n)：

n 加倍中的位数（如上）+ n 次加法中的 1 位数；在 104 的情况下，这将是（7 位，3 个“1”位）= 14 次乘法（平方），10 次加法。

(*)假设两个数字相加花费相同的时间，与两个数字的大小无关。

让斐波那契更快

Making Fibonacci faster

java

algorithm

fibonacci

动态规划

伪代码

想法

还有更多！

复杂性