如何在Clojure中高效计算超大BigInteger的平方？

核心问题根源 #

直接计算超大BigInteger的平方会导致数字大小呈指数级增长，10000轮迭代后，数字的位数会达到天文级别。BigInteger的乘法/平方操作时间复杂度为O(n²)（n为数字位数），因此性能会急剧恶化，甚至无法在合理时间内完成。

最优解决方案：利用模运算性质优化 #

Advent of Code 2022 Day11 Part2的核心需求是判断数值能否被特定除数整除，不需要保留完整的超大数值。根据模运算的性质：

• 若L是所有猴子除数的最小公倍数（LCM），则对于任意数值x，x mod L的结果与x本身对每个除数取模的结果完全一致。
• 因此，每次计算新数值后，只需保留x mod L即可，这样数值始终维持在L的范围内，不会无限膨胀。

由于题目中的除数均为质数，LCM就是所有除数的乘积，直接用BigInteger存储即可。

Clojure中的具体实现 #

1. 计算所有除数的LCM：

   (defn compute-lcm [divisors]
     (reduce #(.multiply %1 (bigint %2)) (bigint 1) divisors))
   

   这里假设divisors是所有猴子的除数组成的集合。

2. 修改数值更新函数：
   将原来的平方计算改为平方后取模LCM，例如：

   ;; 替代原来的(fn [old] (.pow old 2))
   (fn [old lcm] (mod (* old old) lcm))
   

   或者用.pow版本：

   (fn [old lcm] (mod (.pow old 2) lcm))
   

   两种方式性能差异不大，但取模后数值被限制在LCM范围内，后续迭代的计算速度会极大提升。

3. 迭代过程中应用优化：
   在每一轮猴子的数值更新步骤中，计算完新的数值后立即对LCM取模，确保后续操作都是基于较小的BigInteger进行。

效果验证 #

通过这种优化，10000轮迭代的计算时间会从“数天”缩短到几秒甚至更短，完全符合题目的时间要求。

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