用于查找斐波纳契数的最后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

Ardavel的答案很好地解释了为什么将循环中的余数取为正确的值，从而使您不需要使用BigInteger。因此，出于您分配任务的目的，将回答此问题；但是问题太有趣了，无法解决。你说：

我也很想知道是否有更好的迭代解决方案。

所以，去了：

矩阵乘法

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

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

[此矩阵与n的幂可以在O（log n）时间中进行计算，例如使用square and multiply算法，该算法can可以迭代实现-迭代版本比递归版本更有效。

“ O（1）时间”解决方案

实际上，使用以下观察结果，您甚至可以做得更好：让我们在A^n v上方调用矩阵方程，其中v是初始向量。模数为100,000的有限2D整数向量有限，并且矩阵2x2的整数矩阵也有限。因此，存在一些有限数t使得A^t v = v。

这意味着A^n = A^(n % t)，然后得出无论多少n是，您最多只需要做fixed，constant数量的矩阵乘法。事实证明t的值为150,000，因此我们可以通过在开始时编写n %= 150000;来改进任何算法。

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

中国余数定理

我们可以走得更远。如果我们应用Chinese remainder theorem，那么找到答案模2 ⁵和答案模5 ⁵就足够了，因为它们唯一地确定答案模10 ⁵。事实证明，两种情况下的循环长度t都短得多：对于模数2 ⁵，t仅为48，而对于模数5 [5]则为12,500。^{这足够小，如果性能非常重要，我们可以适当地预先计算长度分别为48和12,500的数组中较小模数的结果。这些数字足够小，可以容纳2个字节的short，因此，如果要为[C0 ] = 150,000。}

该算法为

“取n模48和12,500，在两个数组中查找，并应用中国余数定理”

，这并不是真正的迭代，但是至少您可以说这些数组是预先计算的使用迭代算法。

Answer 2

正如您已经注意到的，找到最后5位数字等同于对结果取模100000。要解决溢出问题，可以对中间结果应用int操作，因此不需要BigInteger。它将是：t。