查找斐波那契数最后 5 位的算法

Question

我正在尝试实现一种迭代算法来计算第 N 个斐波那契数的最后 5 位数字。我可以轻松找到第 n 个斐波那契数本身并仅显示最后 5 位数字，但是，我的作业还要求找到我的程序在 1 分钟内运行的最大 n。问题是，N 变得非常大，因此斐波那契数也很大。我应该只使用 BigInteger 来存储值，最后使用 % 运算符来显示最后 5 位数字吗？有没有办法利用我只需要最后 5 位数字来加速这个过程？我觉得我错过了作业的重点。

作业是这样说的：使用 Java，实现用于计算第 n 个斐波那契数的最后 5 位的迭代算法。执行一个实验，找出您的程序在您的计算机上运行不到 1 分钟的最大 n 值。

我用于查找第 N 个斐波那契数的最后 5 位数字的代码：

public static int Fibonacci(int n){
    int a, b = 0, c = 1;
    for(int i = 1; i < n; i++){
        a = b;
        b = c;
        c = a + b;
    }
    return c % 100000;
}

我也很想知道有没有更好的迭代方案。

Answer 1

正如您已经注意到的，找到最后 5 位数字相当于计算结果模 100000。要解决溢出问题，您可以对中间结果应用 % 100000 操作，因此不需要 BigInteger。它将是：c = (a + b) % 100000.

理论上，您可以将解决方案的时间复杂度从O(N) 提高到O(log(N))。该算法基于快速矩阵求幂。但是，您的作业需要迭代方法，所以我提到它只是为了完整性。

Answer 2

Ardavel 的回答很好、清楚地解释了为什么在循环中取余数会给出正确的结果，因此您不需要使用 BigInteger。因此，为了您的作业目的，这个问题得到了回答；但是这个问题太有趣了，不能留在那里。你说：

I would also love to know if there are better iterative solutions.

所以，这里是：

矩阵乘法

Ardavel 提到您可以通过使用高效矩阵幂算法计算 matrix power 在 O(log n) 时间内计算出相同的结果。从本质上讲，第 n 个斐波那契数可以写成封闭形式：

( ... ) = ( 1 1 )n ( 1 )
( F_n )   ( 1 0 )  ( 0 )

而这个 n 次方的矩阵可以在 O(log n) 时间内计算出来，例如使用 square and multiply 算法，可以迭代实现 - 迭代版本比递归版本更有效。

"O(1) time"解决方案

事实上，您可以使用以下观察做得更好：我们将上面的矩阵方程称为 A^n v，其中 v 是初始向量。只有有限多个以 100,000 为模的二维整数向量，并且只有有限多个 2x2 整数矩阵。所以有一些有限的数字 t 这样 A^t v = v.

这意味着A^n = A^(n % t)，那么无论n有多大，你最多只需要做一个固定的，常量 矩阵乘法量。原来 t 的值是 150,000，所以我们可以通过在开始写 n %= 150000; 来改进任何算法。

但是，此解决方案的时间并不完全是 O(1)，因为对于任意大的 n，无法在常数时间内找到余数模 t。假设我们允许输入任意大（其余计算仍然可以使用 ints 完成），那么读取二进制格式的输入所花费的时间是 O(log n)。但这比 O(log n) 矩阵乘法要好得多。

中国余数定理

我们可以更进一步。如果我们应用 Chinese remainder theorem，那么找到模 2⁵ 和模 5⁵ 的答案就足够了，因为这些唯一确定答案模 10⁵。事实证明，循环长度 t 在这两种情况下都短得多：对于模数 2⁵，t 仅为 48，而对于 5⁵ 是 12,500。

这足够小，如果性能非常重要，我们可以可行地预先计算长度分别为 48 和 12,500 的数组中较小模数的结果。这些数字足够小，可以放入 2 字节 shorts，因此数组占用大约 25KB 左右的内存，而如果您要预先计算一个t = 150,000 的数组。

然后算法是"take n modulo 48 and 12,500, look up in the two arrays, and apply the Chinese remainder theorem"，这不是真正的迭代，但至少你可以争辩说数组是使用迭代算法预先计算的。

查找斐波那契数最后 5 位的算法

Algorithm for finding last 5 digits of Fibonacci number

java

iteration

algorithm

fibonacci

矩阵乘法

"O(1) time"解决方案

中国余数定理