采用快速倍增法的大下标斐波那契区间和整除判断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整除。 - 移除代码中所有完全冗余的无用逻辑
- 删掉静态块中从未被实际调用的
previousValuesHolderHashMap,该结构存的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
相关产品推荐
相关产品推荐

