You need to enable JavaScript to run this app. 采用快速倍增法的大下标斐波那契区间和整除判断Java代码优化咨询
优惠活动
大模型
产品
解决方案
定价
更多

采用快速倍增法的大下标斐波那契区间和整除判断Java代码优化咨询

针对该斐波那契整除判断的代码优化方案

核心性能瓶颈定位

当前代码耗时过高的核心原因是完全没必要的超大数高精度计算:最终目标只是判断区间和能否被整数D整除,不需要计算F(2000万)对应的几百万位完整大整数,仅需计算该数值模D的结果即可,全程可把参与运算的数值控制在远小于BigInteger计算规模的范围内,直接把耗时从秒级压到毫秒级。

具体可落地的优化点

  • 把全链路运算替换为模D下的运算,彻底移除无用的BigInteger高精度计算
    利用模运算的基本性质:对于任意整数k,(x - y) mod D = [(x mod D) - (y mod D)] mod D,区间和(F_{b+2} - F_{a+1})的整除判断完全可以在每次快速倍增计算的中间步骤直接对D取模,所有参与运算的数值最大不超过D^2(百万级D下乘积仅为万亿级,long类型即可承载),完全不需要存储百万位长度的BigInteger。
    注意计算减法取模时要加D再取模,避免出现负余数导致判断错误,即最终判断条件为:modResult = ((fibMod(b+2, d) - fibMod(a+1, d)) % d + d) % d,当且仅当modResult为0时区间和可被D整除。
  • 移除代码中所有完全冗余的无用逻辑
    • 删掉静态块中从未被实际调用的previousValuesHolder HashMap,该结构存的BigDecimal值没有在任何斐波那契计算流程中被读取,属于纯冗余内存占用
    • 删掉快速倍增循环中全程未被返回值依赖的m变量,原代码中m的每次乘2、自增运算没有任何实际作用,属于无效计算
    • 删掉无意义的封装层multiply方法,直接在快速倍增流程中调用原生乘法即可,多余的方法包装只会增加调用开销
    • 删掉静态全局变量totalSum,把计算结果改为方法内的局部变量,避免静态状态带来的额外内存管理开销
  • 快速倍增逻辑适配小数值运算优化
    把原有的基于BigInteger的倍增计算,替换为基于long类型的模运算版本:每次循环计算斐波那契对(F_{2k}, F_{2k+1})时,直接把乘法结果对D取模,避免数值膨胀。
    适配后的核心计算片段参考:
    private static long fibMod(int n, long mod) {
        if (n == 0) return 0;
        long a = 0, b = 1; // 对应F(0), F(1)
        for (int bit = Integer.highestOneBit(n); bit != 0; bit >>>= 1) {
            // 倍增公式: F(2k) = F(k) * [2*F(k+1) - F(k)]
            long c = (a * ((2 * b - a + mod) % mod)) % mod;
            // 倍增公式: F(2k+1) = F(k)^2 + F(k+1)^2
            long d = (a * a % mod + b * b % mod) % mod;
            a = c;
            b = d;
            if ((n & bit) != 0) {
                long next = (a + b) % mod;
                a = b;
                b = next;
            }
        }
        return a;
    }
    
  • 小细节调整减少无意义的类型转换
    原checkSum方法中对余数的longValue()判断可以直接基于long类型的模运算结果完成,不需要把余数转成BigInteger再转回long,进一步减少对象创建开销。

优化后性能预期

原测试场景A=1e7、B=2e7、D=987654下,改造后的计算流程全程仅涉及long类型的整数乘法和取模,没有任何大对象的创建和高精度乘法运算,整体耗时可从原来的3.3秒降至10毫秒以内。


内容的提问来源于stack exchange,提问作者Denis E

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.10.27 14:45:03