Java迭代法求斐波那契数最后5位：优化与最大n值探索

首先，你的代码存在一个关键问题：int类型溢出。斐波那契数增长极快，第46个斐波那契数就已经超过了int的最大值（2^31-1），之后的计算会因为溢出得到错误结果，更别说处理极大的n了。

针对“仅需最后5位”的优化方案 #

你完全不需要用BigInteger——利用模运算的性质就能大幅简化计算，同时避免溢出：

(a + b) % mod = [(a % mod) + (b % mod)] % mod

也就是说，每一步计算时都对结果取100000的模，这样所有中间值都不会超过99999，用int类型就足够存储，运算速度也会极快。优化后的代码如下：

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

这个版本的迭代逻辑和你的思路一致，但每一步都做了模运算，彻底解决了溢出问题，同时保持了O(n)的时间复杂度，单步运算成本极低。

如何找到1分钟内可运行的最大n #

因为这个优化后的算法每一步都是简单的加法和模运算，你的电脑每秒可以轻松处理数百万甚至数千万次迭代。要找到1分钟内的最大n，可以写一个测试程序，记录开始时间，然后循环执行直到时间超过60秒：

public static void findMaxNInOneMinute() {
    long startTime = System.currentTimeMillis();
    long maxTime = 60 * 1000; // 1分钟毫秒数
    int n = 0;
    int a = 0, b = 1;
    while (System.currentTimeMillis() - startTime < maxTime) {
        n++;
        int c = (a + b) % 100000;
        a = b;
        b = c;
    }
    System.out.println("1分钟内可处理的最大n值：" + n);
}

注意：实际运行时n会非常大（可能达到数亿级别），因为单步迭代的耗时几乎可以忽略不计。

更优的迭代解决方案：O(log n)算法 #

如果追求极致性能，还可以用快速倍增法（迭代实现），它的时间复杂度是O(log n)，能在几十步内算出极大n对应的结果，远远快于O(n)的线性迭代。迭代版的快速倍增法代码示例：

public static int fibLastFiveDigitsFast(int n) {
    int mod = 100000;
    int a = 0;
    int b = 1;
    for (int i = 31; i >= 0; i--) {
        int c = (int)(((long)a * ((2L * b - a + mod) % mod)) % mod);
        int d = ((long)a * a % mod + (long)b * b % mod) % mod;
        a = c;
        b = d;
        if (((n >> i) & 1) != 0) {
            int temp = (a + b) % mod;
            a = b;
            b = temp;
        }
    }
    return a;
}

这个算法通过二进制分解n，把线性迭代变成了对数步数的迭代，哪怕n是10^18这样的天文数字，也能瞬间算出结果。不过如果你的作业要求必须是线性迭代，那前面的O(n)优化版就足够了。

内容的提问来源于stack exchange，提问作者Nikita Voronin