分治递归阶乘算法：二进制拆分与质因数分解的时空权衡

阶乘计算是数论与高性能计算中的经典问题。当 n 超过数万时，朴素算法的 O(n² log n) 复杂度会让计算时间迅速失控。本文聚焦两种主流优化策略 ——二进制拆分 (Binary Splitting) 与 质因数分解法—— 分析它们的时空权衡，并提供可直接落地的工程参数。

核心问题：乘法层级的瓶颈

计算 n! 的本质是执行 n-1 次大整数乘法。朴素算法从 1 乘到 n，第 k 步的乘数有 O(k log k) 位，单次乘法成本为 O(k log k)（假设使用 FFT 加速），总成本累积为 O(n² log n)。

问题的关键在于乘法操作数的尺寸分布。朴素算法早期乘的是小数，后期乘的是大数，导致大量中等规模乘法的累积开销。优化方向很明确：减少大整数乘法的次数，同时让每次乘法的操作数尺寸更均衡。

策略一：二进制拆分 (Binary Splitting)

二进制拆分的核心思想是分治：将区间 [a, b] 的乘积递归地拆分为 [a, mid] 与 [mid, b] 两部分，分别计算后再相乘。

p(a, b) = p(a, mid) × p(mid, b)

这种方法的精妙之处在于平衡乘法树的深度与操作数尺寸。递归深度为 O(log n)，每层需要进行 O(2^depth) 次乘法，但同层乘法的操作数尺寸相近，可以充分利用 FFT 批量处理的优势。

复杂度分析表明，使用 FFT 乘法时，总成本降至 O(log(n) · M(n log n))，其中 M(d) 表示 d 位数的乘法成本。当 M(d) = O(d log d) 时，整体复杂度为 O(n log² n)，相比朴素算法有显著改进。

工程实现要点

递归终止阈值：当区间长度 b - a 小于阈值 T 时，应切换为朴素乘法。经验值 T = 64~256（取决于底层大整数库的效率）。阈值过小会增加递归开销；阈值过大则失去分治优势。

内存管理：二进制拆分需要同时保存左右子树的中间结果，峰值内存约为 O(n log n) 位。对于 n = 10⁶ 的计算，中间结果可能占用数百 MB。建议在实现中使用迭代而非纯递归，或采用尾递归优化。

策略二：质因数分解法

质因数分解法从另一个角度切入：利用勒让德公式，先计算 n! 的质因数分解形式，再将各质数的幂相乘。

n! = ∏(p^k_p)  其中 p 为质数 ≤ n
k_p = Σ⌊n / p^i⌋  (i = 1, 2, ...)

这种方法的优势在于大幅减少乘法次数：只需进行 π(n) 次质数幂的乘法（π(n) 为质数计数函数，约 n / log n），而非 n 次连续整数乘法。

Prime Swing 算法

Peter Luschny 提出的 Prime Swing 算法是质因数分解法的工程优化版本。它将阶乘分解为奇数部分与 2 的幂的乘积，对奇数部分使用质因数分解，对 2 的幂使用位运算快速计算。

该算法在 GitHub 上有多种语言的实现（C++, Java, Python, Julia, Go），实测在计算 10⁶! 时比朴素方法快数个数量级。

时空权衡：如何选择策略

两种策略各有适用场景：

选择建议：

• 通用场景：优先使用 Prime Swing 或质因数分解法，尤其当 n > 10⁴ 时优势明显
• 内存受限环境：二进制拆分可通过调整阈值降低峰值内存
• 并行计算：二进制拆分的递归树天然适合任务并行

可落地的工程参数

基于上述分析，给出以下可直接使用的参数清单：

递归深度阈值：

# Python 示例：二进制拆分的阈值设置
BINARY_SPLIT_THRESHOLD = 64  # 区间长度小于此值时切换为朴素乘法

质数预筛规模：

# 预计算 n 以内的所有质数，使用埃氏筛或线性筛
# 空间预算：π(n) × 4 bytes ≈ n / log n × 4 bytes
# 对于 n = 10⁷，约需 2.5 MB

大整数库选择：

• C/C++: GMP 或 MPIR（MPIR 在 Windows 上更友好）
• Python: gmpy2（比原生 int 快 10-100 倍）
• Java: Apfloat 或自定义 FFT 实现

内存预算公式：

峰值内存 ≈ 2 × n × log₂(n) / 8  bytes
# 对于 n = 10⁶，约 4 MB（仅中间结果，不含最终结果）

总结

分治递归阶乘算法的优化本质是在乘法层级上做权衡：二进制拆分通过平衡乘法树的结构减少大整数乘法次数；质因数分解通过数学变换直接减少乘法操作数。实际工程中，Prime Swing 算法结合了两者的优势，是目前计算大阶乘的首选方案。

对于需要自行实现的场景，建议从二进制拆分入手（实现简单），在性能测试后逐步引入质因数分解优化。始终记住：递归阈值和内存峰值是工程落地时最关键的调参点。

参考来源

• Binary Splitting Method: http://numbers.computation.free.fr/Constants/Algorithms/splitting.html
• Peter Luschny's Fast Factorial Functions: https://github.com/PeterLuschny/Fast-Factorial-Functions

systems