到O(n log n)的算法演进与并行实践)
初看“大整数加法 VS 大整数乘法”这个题目很多人第一反应是不就是竖式运算吗加法逐位相加乘法交叉相乘再加进位能有什么好对比的。可一旦数字从“课堂上写得下的32位数”变成“几十万甚至上千万位”这两者立刻从亲兄弟变成仇人——加法几乎沿着一条直线跑完乘法却在指数级的陡坡上越爬越慢。我早期做一次密钥生成工具时对这个差距的感受特别深模幂运算的核心就是几百次大整数模乘。当时图省事自己实现了朴素乘法测了一次密钥生成时间差点以为程序死循环了换成现成的GMP之后同一个操作快了好几个数量级。也正是从那时起我才认真弄明白“大整数加法 VS 大整数乘法”这个题目背后的完整技术栈从 O(n) 的进位链优化到 O(n^1.585) 的 Karatsuba再到 O(n log n) 的 FFT 乘法以及最近被高频讨论的并行化方案。这篇文章我想以一个做过大数运算、也在生产项目里调过性能的人的身份把这套东西讲透加法为什么能做到线性乘法为什么没那么简单主流库内部到底怎么切算法以及“大整数加法 并行”这个方向为什么值得关注又难在哪里。适合想自己实现大数运算、备战算法竞赛、或者单纯好奇加密库背后乘法是怎么跑起来的读者。1. 局部依赖与全局组合加法与乘法的复杂度分水岭在进入具体算法之前必须先理解一个底层差异为什么同样是“逐位处理”加法和乘法的复杂度会差出一个量级这个问题的答案决定了后续所有优化的方向。1.1 进位链加法性能的真正挂载点先看加法。假设有 n 位的十进制大整数 A 和 B从低位往高位逐位计算规则是s_i (a_i b_i c_i) mod 10c_{i1} (a_i b_i c_i) / 10关键就在这个 c_i 上第 i 位的结果要用到第 i-1 位的进位而第 i-1 位的进位又依赖第 i-2 位……这是一种典型的“局部依赖”——每个位置只依赖紧邻的低位不依赖更远的位。正因为这种依赖是局部的逐位处理的总工作量才是 O(n)每一位最多做三次操作两数相加、加上进位、判断新进位。无论数字多大都不需要回头重新计算之前的位置。但注意这条进位链最坏会穿透全部 n 位。最典型的例子是 999...999 1结果是 1000...000进位从最低位一路传到最高位。教科书上通常不讨论这个细节因为从渐进复杂度看仍然是 O(n)但工程上这一条链意味着循环里每一步都依赖前一步的进位值处理器没法提前把后面的指令并行起来。这也是大整数加法并行化最头疼的地方后面第 4 章我会专门展开。1.2 交叉项的全局扩散朴素乘法为什么躲不开 O(n²)再看乘法。同样是 n 位竖式乘法怎么做把 A 的每一位和 B 的每一位都交叉相乘然后按位权累加。结果第 k 位上的数字很可能要由所有满足 ijk 组合的 a_i * b_j 共同决定。这就是“全局组合”。加法的第 k 位只依赖第 k 位和第 k-1 位的进位而乘法的第 k 位需要把所有交叉项都汇总进来。于是主体工作量是 n 次乘 n 次也就是 n² 次标量运算。这就是朴素乘法 O(n²) 的来源跟加法的 O(n) 完全不在一个量级。想理解这两个差异有个生活类比特别好用加法像排队过闸口每个人只跟着前面那个人走队伍再长也是一次遍历乘法像全班人互相握手每新来一个人都要跟已经到的每个人握一次手人数翻倍握手次数立刻翻四倍。你组织 100 个朋友聚会互相握手和只安排大家排队进门需要的运维成本完全不同。到这里先记住第一个结论加法被“局部依赖”保护天然就是线性的乘法被“全局组合”拖累教科书式的竖式算法要付出 n² 次操作。接下来所有优化都是在跟“全局组合”做斗争或者想办法让进位依赖被分摊掉。2. 加法O(n) 已定死能优化的只有常数因子既然加法复杂度已经被“局部依赖”锁定为 O(n)那还有什么可优化答案是常数因子。实际性能差异可以在同一个 O(n) 框架下差出好几倍所以值得细抠。2.1 逐位相加的教科书实现与进位传播在算法课本里我们通常看到的实现长这样def big_add(a_digits, b_digits): carry 0 result [] n max(len(a_digits), len(b_digits)) for i in range(n): da a_digits[i] if i len(a_digits) else 0 db b_digits[i] if i len(b_digits) else 0 s da db carry result.append(s % 10) carry s // 10 if carry: result.append(carry) return result这里用的是十进制数字位数组逻辑直观。但注意一个关键点每一次迭代都读取 carry同时写入 carry这是整段代码唯一真正无法绕开的依赖边。处理器虽然可以乱序执行但它无法重排后续迭代中必须读取 carry 的那条指令所以这实际上是一条相当窄的循环依赖链。如果要写一个性能还不错的库通常不会停留在十进制位上。生产级实现会直接用 64 位无符号整数数组把“数字位”从十进制的一位扩大到二进制的一个机器字。同样的数据循环次数缩减到原来的约 1/19因为一个 64 位二进制字大约能表示 19 位十进制数字。单单这一步常数因子就小了一个数量级。2.2 无符号回绕检测64 位粒度下的经典加法写法在 C 语言里经典的大整数加法内核长这样// x 和 y 是 uint64_t 数组长度均为 len结果写入 z长度 len1 uint64_t carry 0; for (size_t i 0; i len; i) { uint64_t t x[i] y[i]; uint64_t sum t carry; carry (t x[i]) | (sum t); // 两段溢出任一发生则向高位进位 z[i] sum; }几个要点值得展开无符号整数溢出按 2^64 取模是 C 标准明确定义的所以 t x[i] y[i] 溢出后t x[i] 恒成立可以可靠地检测进位不依赖 CPU 标志位。把 carry 也加入时要分成两步看先算 x[i]y[i] 是否溢出再算这个局部和加上 carry 后是否又溢出。两个溢出任有一个发生传给下一位的进位就是 1。这是最容易写错的地方很多人偷懒直接把三个数一次性相加结果进位逻辑全乱掉。现代编译器还能做更多__builtin_add_overflow这类内置函数可以同时拿到结果和溢出标志代码更易读性能也不差。在 x86 上最终会生成 adc 指令链效率很高。我在写自己的库时习惯用这个两步判断版本因为它在 ARM 和 x86 上都不会引起分支预测失败也不依赖特定编译器对表达式的识别程度。2.3 实测里最容易拖慢加法性能的三个因素加法已经做到 O(n)实际跑起来还有什么坑我总结三个最常见的内存带宽。大整数加法本质上是顺序读两个数组、写一个数组。当 n 大到超过 L2/L3 缓存时瓶颈就从 CPU 指令变成了内存带宽。这时候不管怎么优化算法吞吐上限都无限接近内存带宽。想继续提升只有靠 SIMD 一次处理多组数据。进位链破坏并行度。依赖链导致后续迭代无法提前开始。虽然现代 CPU 可以用条件执行和分支预测削弱影响但代码里显式的分支越少越好。这也是我倾向于用算术逻辑而不是 if 来更新 carry 的原因。符号处理。大整数库经常用补码表示负数。如果直接用逐位加法算法符号位会像毒药一样在进位链里传播。工程上更稳妥的做法是“符号-大小”表示符号单独存一个标志数值部分永远按无符号处理做减法时先比较大小再由大数减小数。所以你看加法这边真正花功夫的不是“算法复杂度”——它已经最优了而是“常数因子”用更宽的字、少分支、少内存拷贝。这也是为什么很多老人会说加法不是 CPU 的问题是内存的问题。3. 乘法Karatsuba 到 FFT 的接力赛如果说加法是“把带宽吃满就算赢”乘法就是一场真正的算法接力赛。每一种算法都有它的适用范围后续算法永远在更低复杂度与更高常数之间做权衡。3.1 朴素竖式乘法先跑通再谈优化先写一个最朴素的版本def big_mul(a_digits, b_digits): n, m len(a_digits), len(b_digits) result [0] * (n m) for i in range(n): carry 0 for j in range(m): cur result[i j] a_digits[i] * b_digits[j] carry result[i j] cur % 10 carry cur // 10 pos i m while carry: s result[pos] carry result[pos] s % 10 carry s // 10 pos 1 return result复杂度一目了然两个循环n*m 次内层操作近似 O(n²)。别看它慢它最大的价值是“正确性锚点”。后面所有更复杂的算法都可以拿朴素乘法来交叉验证结果。我强烈建议任何自己写大数库的人都保留这个版本做对拍。朴素乘法在工程上的优化点是按 limb机器字而不是十进制位来做。但内循环要不断累加写到 result[ij] 上内存访问是斜着走的cache 不友好这也是性能开销的主要来源之一。3.2 Karatsuba三次乘法换一次额外减法递归榨出 n^1.5851960 年23 岁的 Karatsuba 发现乘法不一定非得做 n² 次。他的思路非常朴素把大整数从中间切成两半A A_1 * B^k A_0B B_1 * B^k B_0其中 B^k 是“半个数位长度”的基数。那么乘积展开是A * B A_1 B_1 * B^{2k} (A_1 B_0 A_0 B_1) * B^k A_0 B_0直接算需要 4 次子乘法A1B1、A1B0、A0B1、A0B0。Karatsuba 的关键发现是中间项可以拼出来A_1 B_0 A_0 B_1 (A_1 A_0)(B_1 B_0) - A_1 B_1 - A_0 B_0所以只需要算三次乘法(A1A0)(B1B0)、A1B1、A0B0再配合几次 O(n) 级别的加减法。递推复杂度为T(n) 3T(n/2) O(n)解得 T(n) O(n^{log₂3}) ≈ O(n^{1.585})。当 n1 万位时朴素的 1 亿次操作变成约 220 万次相差 45 倍当 n100 万位时朴素的 10¹² 次直接不可能跑Karatsuba 大约 3 亿次已经有实际可行性。Python 的参考实现骨架def karatsuba(a, b): if len(a) 32 or len(b) 32: return big_mul(a, b) n max(len(a), len(b)) half n // 2 a0, a1 a[:half], a[half:] b0, b1 b[:half], b[half:] z0 karatsuba(a0, b0) z1 karatsuba(a1, b1) z2 karatsuba(big_add(a0, a1), big_add(b0, b1)) # 结果 z1 * B^(2*half) (z2 - z0 - z1) * B^half z0 return combine(z0, z1, z2, half)真正的工程实现里有几个人第一次写必然踩的坑递归终止不要太小。Karatsuba 虽然渐进更好但常数比朴素乘法大一般在几十个 limb约几百到上千个十进制位以下直接用朴素乘法更划算。A0A1 和 B0B1 可能产生额外进位。这个进位进入子乘法时子乘法的规模会变成 half1必须单独处理否则会在拼接处错位。减法必须支持负数结果。z2 - z0 - z1 可能是负数需要单独实现大整数比较和减法。3.3 Toom-Cook 与 FFT进一步压复杂度的两条路线Karatsuba 是“切成两段3 次乘法”。推广一下切成 k 段可以做到更低的指数。经典的 Toom-3 切成 3 段用 5 次乘法复杂度 O(n^{log₃5}) ≈ O(n^{1.465})Toom-4 用 7 次乘法指数约 1.404。这类算法统称 Toom-Cook原理是把多项式求值-插值套路用在大整数上先在几个固定点求值做少量乘法再插值回去。实现起来加减法和系数运算非常多调试也痛苦所以除了 GMP 这类库很少有人从零撸 Toom-3。当 n 再往上涨比如几十万个 limb 以上连 Toom-Cook 也开始吃力了。这时得换视角乘法本质上在做卷积。两个数相乘结果第 k 位的系数是c_k Σ_{ijk} a_i · b_j这正是离散卷积。而快速卷积可以用 FFT把 A 和 B 各做一次离散傅里叶变换频域逐点相乘再做逆变换。总复杂度 O(n log n)配合数论变换 NTT 可以完全避开浮点舍入误差。这也是 GMP、OpenSSL 在超大数乘法时最终会切到的算法。这里必须提醒一句FFT 乘法在 n 较小时常数非常大不是“从 100 位开始就变快”的魔法。它跟 Karatsuba 一样有明确的阈值起点。具体阈值因库而异通常要在几千个 limb约几万到几十万二进制位以上FFT 才会真正胜出。3.4 GMP 们是怎么选的阈值触发与混合算法真正的大数库不会只用一种算法。GMP 的内部逻辑大致是操作数规模使用算法复杂度极小几个 limb直接竖式乘法O(n²)几十个 limbKaratsubaO(n^1.585)再往上Toom-3 / Toom-4O(n^1.465 ~ 1.404)超大成千上万个 limbFFT / NTTO(n log n)OpenSSL 的 BN 库也类似虽然它的策略没有 GMP 那么激进但同样根据操作数长度选择入口。Java 的 BigInteger 也采用了差不多同一套技术路线。你用一个库觉得“几千位乘法也挺快”背后其实是这一整套混合策略在接力工作。写到这里分享一个自维护大数库的实践先按朴素乘法跑通再实现 Karatsuba最后接上 FFT。每加一层就做“新旧实现交叉校验”随机生成两个大整数用新旧两种方式计算结果必须完全一致。因为大整数乘法的符号处理、进位拼接很容易错位光靠几个单元测试根本不够。4. 并行化的两条路线加法卖力过闸乘法天然好拆最近“大整数加法 并行”这个热词被反复搜索背后其实是一个很值得讨论的技术分叉点语义上明明更简单的加法并行起来反而比乘法更别扭。4.1 为什么“大整数加法 并行”会成为关注热点三个背景叠加在一起全同态加密、零知识证明、部分密码学原语要处理超长整数位宽动辄几万甚至几十万多核 CPU 已经普及AVX2/AVX-512 让你一次能算四组甚至更多 64 位加法大整数加法看似太简单很多人默认“没啥可并行的”但实际上并行加法可以做而且值得做。4.2 加法并行难的真正原因进位链和内存带宽我前面反复提到了进位链。严格按竖式从低位往高位扫第 i 位必然依赖第 i-1 位的进位所以“第一轮逐位算”确实没法直接摊到多个线程——你让线程 2 先算第 1000 位它不知道第 999 位会不会传一个进位上来自然算不准。另一个限制是内存带宽。加法本身几乎不怎么占 CPU 算力多数场景卡在读两个数组、写一个数组。多线程如果只是把数组分成几段每段独立做加法最终整合时反而可能因为缓存一致性、同步开销把收益吃掉。4.3 加法并行的一种可行方案分块局部和链路进位归并实践中我见过比较稳妥的“两阶段加法”把 n 位的数组切成 k 块每块大小约 n/k每块独立计算局部和并把溢出进位记下来这一步各线程完全独立可以并行最后按块顺序跑一遍“进位归并”把第 0 块的进位加到第 1 块第 1 块的进位加到第 2 块……通常只需 O(k) 次处理k 远小于 n。为什么可行因为“局部和”是每块内部的事线程在算自己那块时不需要知道前一块的进位结果它唯一需要额外保存的是“无进位时的结果”和“有进位时的结果”——最多两个版本。归并阶段再按真实进位选择。本质上就是拿额外空间换并行度。如果追求更细粒度可以在 SIMD 层面做类似的事一次计算 4 组 64 位加法同时记录四组进位最后向量化归并。我个人的经验是在支持 AVX-512 的机器上纯加法的吞吐还能再提高二到三倍。这也解释了为什么真正吃性能的加法场景更偏向 SIMD 而不是多线程。4.4 乘法并行交叉乘积分发到多线程归约比加法好做乘法这边的画风完全不一样。朴素乘法的本质是所有 a_i · b_j 的累加每个交叉乘法的结果都落在 result[ij] 附近互不冲突或者最多做无锁归约加法交换律保证顺序无关。这意味着你可以按行分解——比如把 a 的某一段分给每个线程各线程独立算完整的一段乘积最后再累加。这种“任务天然独立”的结构让乘法在多线程下的加速比通常能接近线性瓶颈主要出现在尾部归约。Karatsuba 和 FFT 也都能并行Karatsuba 的三个子任务之间没有依赖关系可以直接分给三个线程FFT 更不用说本身就是“逐点变换再逐点相乘”SIMD 和多线程都很好用。所以在工程上如果你有大整数乘法的性能需求并行化往往从乘法下手更划算。我自己在一台 16 线程的机器上做过一次非严格的趋势对比两个两万位的十进制数相乘单线程跑了几十毫秒拆到 8 线程后只剩不到三分之一而同样规模的加法单线程两毫秒8 线程只快了百分之二三十。趋势非常明显——加法并行是在省“几毫秒的零头”乘法并行是在省“几十上百毫秒的大头”。4.5 热词背后的小结所以当你搜“大整数加法 并行”看到大量讨论一点也不奇怪因为加法正好处在“看似简单、实际难并行”的边界线程并行收益有限SIMD 并行收益明显乘法则是“看似复杂、其实好拆”分到多核收益大和 SIMD、FFT 都能无缝衔接。理解这一点做技术选型时心里就有底了。5. 工程选型什么时候自己写什么时候直接用库前面讲了这么多原理最后落到实际项目里核心问题只有一个这套东西到底要不要自己写5.1 位数与算法选型对照先给一个粗颗粒度的对照表十进制位数二进制位数约推荐方案≤ 19 位≤ 64 bit直接 uint64/int64别用大数库≤ 38 位≤ 128 bit__int128 或语言内置的 BigInt几百位几千 bitJava/Python 内置、OpenSSL BN、GMP 都可以几千位几万 bitKaratsuba 起步库内部会自动切 Toom几万位以上十几万 bit 以上FFT/NTT 不可少优先 GMP 等专业库不建议为生产环境从零写大整数乘法库。不是因为有现成的解决方案而是这类代码牵涉符号、内存、进位、阈值切换而且一旦性能不达标很难通过后期零散优化救回来。真要自研定位应该是学习、算法演示或特定约束下的定制。5.2 自己实现时容易踩的三个坑中间结果长度。两数相乘的结果长度是 len(a)len(b)不是 max(len(a), len(b)) 再大一位。分配少了会越界分配多了影响性能。我见过几次 bug都是因为把等长数相乘当成 len*2-1 来分配忘掉了最高位的进位。负数的处理。很多初学者把大整数存成“首位标记符号”然后照抄加法算法进位逻辑立刻全乱。成熟的方案是先做绝对值运算最后再把符号因子加回去或者统一用补码表示但补码下加法、比较要切到另一套思路。基准测试的公平性。测试大整数乘法别在 Python 里手写循环去对比 C 库。这看似可笑但网上确实有许多“Python 大数比 C 慢 1000 倍”的结论就是这么来的。跨语言对比时要让两边使用相同算法和类似的数据布局。5.3 我的实践建议与替代方案如果你只是做算法题、写博客演示Karatsuba 加上朴素乘法就完全够了代码控制在几十行能讲清楚复杂度跃迁即可。如果你在做证书、TLS、区块链这类依赖大整数的项目选 OpenSSL BN 或 GMP 是常识。注意两个库的 API 风格差异很大OpenSSL 的 BN 以“操作者需要手动管理临时变量”出名性能上会给部分灵活性让步GMP 更底层性能优先接口也更机械。Rust 生态可以先用num-bigint或crypto-bigint性能足够覆盖大多数日常需求。如果你真的需要“超长整数 并行”我给的优先顺序是先用合适的基础库跑出单线程可靠性再考虑 SIMD 优化加法常数因子最后才考虑多线程分组算乘法。麻烦程度也是这个顺序递增别反着来。最后说点个人体会。当年做那个密钥工具时我抱着“所有数学库都在做同样的事我自己写可能更快”的心态硬是从朴素乘法开始撸了一版大数运算最后被真实数据教做人朴素乘法和 GMP 之间差了将近两个数量级。那一刻我才真正敬畏“算法复杂度”这四个字。所以后来我但凡遇到“大整数 XX”的需求都会先问自己三件事长度有多大是不是常数时间敏感安全场景有没有并行机会前两个问题决定要不要引入专门库最后一个问题决定要不要在库的基础上再包一层。至于大整数加法和大整数乘法哪个更值得优化我的答案很明确加法优化常数乘法优化算法两者没有高低只是复杂度分布完全不同——希望这篇内容能帮你把这条分水岭彻底看清。
大整数加法与乘法：从O(n)到O(n log n)的算法演进与并行实践
初看“大整数加法 VS 大整数乘法”这个题目很多人第一反应是不就是竖式运算吗加法逐位相加乘法交叉相乘再加进位能有什么好对比的。可一旦数字从“课堂上写得下的32位数”变成“几十万甚至上千万位”这两者立刻从亲兄弟变成仇人——加法几乎沿着一条直线跑完乘法却在指数级的陡坡上越爬越慢。我早期做一次密钥生成工具时对这个差距的感受特别深模幂运算的核心就是几百次大整数模乘。当时图省事自己实现了朴素乘法测了一次密钥生成时间差点以为程序死循环了换成现成的GMP之后同一个操作快了好几个数量级。也正是从那时起我才认真弄明白“大整数加法 VS 大整数乘法”这个题目背后的完整技术栈从 O(n) 的进位链优化到 O(n^1.585) 的 Karatsuba再到 O(n log n) 的 FFT 乘法以及最近被高频讨论的并行化方案。这篇文章我想以一个做过大数运算、也在生产项目里调过性能的人的身份把这套东西讲透加法为什么能做到线性乘法为什么没那么简单主流库内部到底怎么切算法以及“大整数加法 并行”这个方向为什么值得关注又难在哪里。适合想自己实现大数运算、备战算法竞赛、或者单纯好奇加密库背后乘法是怎么跑起来的读者。1. 局部依赖与全局组合加法与乘法的复杂度分水岭在进入具体算法之前必须先理解一个底层差异为什么同样是“逐位处理”加法和乘法的复杂度会差出一个量级这个问题的答案决定了后续所有优化的方向。1.1 进位链加法性能的真正挂载点先看加法。假设有 n 位的十进制大整数 A 和 B从低位往高位逐位计算规则是s_i (a_i b_i c_i) mod 10c_{i1} (a_i b_i c_i) / 10关键就在这个 c_i 上第 i 位的结果要用到第 i-1 位的进位而第 i-1 位的进位又依赖第 i-2 位……这是一种典型的“局部依赖”——每个位置只依赖紧邻的低位不依赖更远的位。正因为这种依赖是局部的逐位处理的总工作量才是 O(n)每一位最多做三次操作两数相加、加上进位、判断新进位。无论数字多大都不需要回头重新计算之前的位置。但注意这条进位链最坏会穿透全部 n 位。最典型的例子是 999...999 1结果是 1000...000进位从最低位一路传到最高位。教科书上通常不讨论这个细节因为从渐进复杂度看仍然是 O(n)但工程上这一条链意味着循环里每一步都依赖前一步的进位值处理器没法提前把后面的指令并行起来。这也是大整数加法并行化最头疼的地方后面第 4 章我会专门展开。1.2 交叉项的全局扩散朴素乘法为什么躲不开 O(n²)再看乘法。同样是 n 位竖式乘法怎么做把 A 的每一位和 B 的每一位都交叉相乘然后按位权累加。结果第 k 位上的数字很可能要由所有满足 ijk 组合的 a_i * b_j 共同决定。这就是“全局组合”。加法的第 k 位只依赖第 k 位和第 k-1 位的进位而乘法的第 k 位需要把所有交叉项都汇总进来。于是主体工作量是 n 次乘 n 次也就是 n² 次标量运算。这就是朴素乘法 O(n²) 的来源跟加法的 O(n) 完全不在一个量级。想理解这两个差异有个生活类比特别好用加法像排队过闸口每个人只跟着前面那个人走队伍再长也是一次遍历乘法像全班人互相握手每新来一个人都要跟已经到的每个人握一次手人数翻倍握手次数立刻翻四倍。你组织 100 个朋友聚会互相握手和只安排大家排队进门需要的运维成本完全不同。到这里先记住第一个结论加法被“局部依赖”保护天然就是线性的乘法被“全局组合”拖累教科书式的竖式算法要付出 n² 次操作。接下来所有优化都是在跟“全局组合”做斗争或者想办法让进位依赖被分摊掉。2. 加法O(n) 已定死能优化的只有常数因子既然加法复杂度已经被“局部依赖”锁定为 O(n)那还有什么可优化答案是常数因子。实际性能差异可以在同一个 O(n) 框架下差出好几倍所以值得细抠。2.1 逐位相加的教科书实现与进位传播在算法课本里我们通常看到的实现长这样def big_add(a_digits, b_digits): carry 0 result [] n max(len(a_digits), len(b_digits)) for i in range(n): da a_digits[i] if i len(a_digits) else 0 db b_digits[i] if i len(b_digits) else 0 s da db carry result.append(s % 10) carry s // 10 if carry: result.append(carry) return result这里用的是十进制数字位数组逻辑直观。但注意一个关键点每一次迭代都读取 carry同时写入 carry这是整段代码唯一真正无法绕开的依赖边。处理器虽然可以乱序执行但它无法重排后续迭代中必须读取 carry 的那条指令所以这实际上是一条相当窄的循环依赖链。如果要写一个性能还不错的库通常不会停留在十进制位上。生产级实现会直接用 64 位无符号整数数组把“数字位”从十进制的一位扩大到二进制的一个机器字。同样的数据循环次数缩减到原来的约 1/19因为一个 64 位二进制字大约能表示 19 位十进制数字。单单这一步常数因子就小了一个数量级。2.2 无符号回绕检测64 位粒度下的经典加法写法在 C 语言里经典的大整数加法内核长这样// x 和 y 是 uint64_t 数组长度均为 len结果写入 z长度 len1 uint64_t carry 0; for (size_t i 0; i len; i) { uint64_t t x[i] y[i]; uint64_t sum t carry; carry (t x[i]) | (sum t); // 两段溢出任一发生则向高位进位 z[i] sum; }几个要点值得展开无符号整数溢出按 2^64 取模是 C 标准明确定义的所以 t x[i] y[i] 溢出后t x[i] 恒成立可以可靠地检测进位不依赖 CPU 标志位。把 carry 也加入时要分成两步看先算 x[i]y[i] 是否溢出再算这个局部和加上 carry 后是否又溢出。两个溢出任有一个发生传给下一位的进位就是 1。这是最容易写错的地方很多人偷懒直接把三个数一次性相加结果进位逻辑全乱掉。现代编译器还能做更多__builtin_add_overflow这类内置函数可以同时拿到结果和溢出标志代码更易读性能也不差。在 x86 上最终会生成 adc 指令链效率很高。我在写自己的库时习惯用这个两步判断版本因为它在 ARM 和 x86 上都不会引起分支预测失败也不依赖特定编译器对表达式的识别程度。2.3 实测里最容易拖慢加法性能的三个因素加法已经做到 O(n)实际跑起来还有什么坑我总结三个最常见的内存带宽。大整数加法本质上是顺序读两个数组、写一个数组。当 n 大到超过 L2/L3 缓存时瓶颈就从 CPU 指令变成了内存带宽。这时候不管怎么优化算法吞吐上限都无限接近内存带宽。想继续提升只有靠 SIMD 一次处理多组数据。进位链破坏并行度。依赖链导致后续迭代无法提前开始。虽然现代 CPU 可以用条件执行和分支预测削弱影响但代码里显式的分支越少越好。这也是我倾向于用算术逻辑而不是 if 来更新 carry 的原因。符号处理。大整数库经常用补码表示负数。如果直接用逐位加法算法符号位会像毒药一样在进位链里传播。工程上更稳妥的做法是“符号-大小”表示符号单独存一个标志数值部分永远按无符号处理做减法时先比较大小再由大数减小数。所以你看加法这边真正花功夫的不是“算法复杂度”——它已经最优了而是“常数因子”用更宽的字、少分支、少内存拷贝。这也是为什么很多老人会说加法不是 CPU 的问题是内存的问题。3. 乘法Karatsuba 到 FFT 的接力赛如果说加法是“把带宽吃满就算赢”乘法就是一场真正的算法接力赛。每一种算法都有它的适用范围后续算法永远在更低复杂度与更高常数之间做权衡。3.1 朴素竖式乘法先跑通再谈优化先写一个最朴素的版本def big_mul(a_digits, b_digits): n, m len(a_digits), len(b_digits) result [0] * (n m) for i in range(n): carry 0 for j in range(m): cur result[i j] a_digits[i] * b_digits[j] carry result[i j] cur % 10 carry cur // 10 pos i m while carry: s result[pos] carry result[pos] s % 10 carry s // 10 pos 1 return result复杂度一目了然两个循环n*m 次内层操作近似 O(n²)。别看它慢它最大的价值是“正确性锚点”。后面所有更复杂的算法都可以拿朴素乘法来交叉验证结果。我强烈建议任何自己写大数库的人都保留这个版本做对拍。朴素乘法在工程上的优化点是按 limb机器字而不是十进制位来做。但内循环要不断累加写到 result[ij] 上内存访问是斜着走的cache 不友好这也是性能开销的主要来源之一。3.2 Karatsuba三次乘法换一次额外减法递归榨出 n^1.5851960 年23 岁的 Karatsuba 发现乘法不一定非得做 n² 次。他的思路非常朴素把大整数从中间切成两半A A_1 * B^k A_0B B_1 * B^k B_0其中 B^k 是“半个数位长度”的基数。那么乘积展开是A * B A_1 B_1 * B^{2k} (A_1 B_0 A_0 B_1) * B^k A_0 B_0直接算需要 4 次子乘法A1B1、A1B0、A0B1、A0B0。Karatsuba 的关键发现是中间项可以拼出来A_1 B_0 A_0 B_1 (A_1 A_0)(B_1 B_0) - A_1 B_1 - A_0 B_0所以只需要算三次乘法(A1A0)(B1B0)、A1B1、A0B0再配合几次 O(n) 级别的加减法。递推复杂度为T(n) 3T(n/2) O(n)解得 T(n) O(n^{log₂3}) ≈ O(n^{1.585})。当 n1 万位时朴素的 1 亿次操作变成约 220 万次相差 45 倍当 n100 万位时朴素的 10¹² 次直接不可能跑Karatsuba 大约 3 亿次已经有实际可行性。Python 的参考实现骨架def karatsuba(a, b): if len(a) 32 or len(b) 32: return big_mul(a, b) n max(len(a), len(b)) half n // 2 a0, a1 a[:half], a[half:] b0, b1 b[:half], b[half:] z0 karatsuba(a0, b0) z1 karatsuba(a1, b1) z2 karatsuba(big_add(a0, a1), big_add(b0, b1)) # 结果 z1 * B^(2*half) (z2 - z0 - z1) * B^half z0 return combine(z0, z1, z2, half)真正的工程实现里有几个人第一次写必然踩的坑递归终止不要太小。Karatsuba 虽然渐进更好但常数比朴素乘法大一般在几十个 limb约几百到上千个十进制位以下直接用朴素乘法更划算。A0A1 和 B0B1 可能产生额外进位。这个进位进入子乘法时子乘法的规模会变成 half1必须单独处理否则会在拼接处错位。减法必须支持负数结果。z2 - z0 - z1 可能是负数需要单独实现大整数比较和减法。3.3 Toom-Cook 与 FFT进一步压复杂度的两条路线Karatsuba 是“切成两段3 次乘法”。推广一下切成 k 段可以做到更低的指数。经典的 Toom-3 切成 3 段用 5 次乘法复杂度 O(n^{log₃5}) ≈ O(n^{1.465})Toom-4 用 7 次乘法指数约 1.404。这类算法统称 Toom-Cook原理是把多项式求值-插值套路用在大整数上先在几个固定点求值做少量乘法再插值回去。实现起来加减法和系数运算非常多调试也痛苦所以除了 GMP 这类库很少有人从零撸 Toom-3。当 n 再往上涨比如几十万个 limb 以上连 Toom-Cook 也开始吃力了。这时得换视角乘法本质上在做卷积。两个数相乘结果第 k 位的系数是c_k Σ_{ijk} a_i · b_j这正是离散卷积。而快速卷积可以用 FFT把 A 和 B 各做一次离散傅里叶变换频域逐点相乘再做逆变换。总复杂度 O(n log n)配合数论变换 NTT 可以完全避开浮点舍入误差。这也是 GMP、OpenSSL 在超大数乘法时最终会切到的算法。这里必须提醒一句FFT 乘法在 n 较小时常数非常大不是“从 100 位开始就变快”的魔法。它跟 Karatsuba 一样有明确的阈值起点。具体阈值因库而异通常要在几千个 limb约几万到几十万二进制位以上FFT 才会真正胜出。3.4 GMP 们是怎么选的阈值触发与混合算法真正的大数库不会只用一种算法。GMP 的内部逻辑大致是操作数规模使用算法复杂度极小几个 limb直接竖式乘法O(n²)几十个 limbKaratsubaO(n^1.585)再往上Toom-3 / Toom-4O(n^1.465 ~ 1.404)超大成千上万个 limbFFT / NTTO(n log n)OpenSSL 的 BN 库也类似虽然它的策略没有 GMP 那么激进但同样根据操作数长度选择入口。Java 的 BigInteger 也采用了差不多同一套技术路线。你用一个库觉得“几千位乘法也挺快”背后其实是这一整套混合策略在接力工作。写到这里分享一个自维护大数库的实践先按朴素乘法跑通再实现 Karatsuba最后接上 FFT。每加一层就做“新旧实现交叉校验”随机生成两个大整数用新旧两种方式计算结果必须完全一致。因为大整数乘法的符号处理、进位拼接很容易错位光靠几个单元测试根本不够。4. 并行化的两条路线加法卖力过闸乘法天然好拆最近“大整数加法 并行”这个热词被反复搜索背后其实是一个很值得讨论的技术分叉点语义上明明更简单的加法并行起来反而比乘法更别扭。4.1 为什么“大整数加法 并行”会成为关注热点三个背景叠加在一起全同态加密、零知识证明、部分密码学原语要处理超长整数位宽动辄几万甚至几十万多核 CPU 已经普及AVX2/AVX-512 让你一次能算四组甚至更多 64 位加法大整数加法看似太简单很多人默认“没啥可并行的”但实际上并行加法可以做而且值得做。4.2 加法并行难的真正原因进位链和内存带宽我前面反复提到了进位链。严格按竖式从低位往高位扫第 i 位必然依赖第 i-1 位的进位所以“第一轮逐位算”确实没法直接摊到多个线程——你让线程 2 先算第 1000 位它不知道第 999 位会不会传一个进位上来自然算不准。另一个限制是内存带宽。加法本身几乎不怎么占 CPU 算力多数场景卡在读两个数组、写一个数组。多线程如果只是把数组分成几段每段独立做加法最终整合时反而可能因为缓存一致性、同步开销把收益吃掉。4.3 加法并行的一种可行方案分块局部和链路进位归并实践中我见过比较稳妥的“两阶段加法”把 n 位的数组切成 k 块每块大小约 n/k每块独立计算局部和并把溢出进位记下来这一步各线程完全独立可以并行最后按块顺序跑一遍“进位归并”把第 0 块的进位加到第 1 块第 1 块的进位加到第 2 块……通常只需 O(k) 次处理k 远小于 n。为什么可行因为“局部和”是每块内部的事线程在算自己那块时不需要知道前一块的进位结果它唯一需要额外保存的是“无进位时的结果”和“有进位时的结果”——最多两个版本。归并阶段再按真实进位选择。本质上就是拿额外空间换并行度。如果追求更细粒度可以在 SIMD 层面做类似的事一次计算 4 组 64 位加法同时记录四组进位最后向量化归并。我个人的经验是在支持 AVX-512 的机器上纯加法的吞吐还能再提高二到三倍。这也解释了为什么真正吃性能的加法场景更偏向 SIMD 而不是多线程。4.4 乘法并行交叉乘积分发到多线程归约比加法好做乘法这边的画风完全不一样。朴素乘法的本质是所有 a_i · b_j 的累加每个交叉乘法的结果都落在 result[ij] 附近互不冲突或者最多做无锁归约加法交换律保证顺序无关。这意味着你可以按行分解——比如把 a 的某一段分给每个线程各线程独立算完整的一段乘积最后再累加。这种“任务天然独立”的结构让乘法在多线程下的加速比通常能接近线性瓶颈主要出现在尾部归约。Karatsuba 和 FFT 也都能并行Karatsuba 的三个子任务之间没有依赖关系可以直接分给三个线程FFT 更不用说本身就是“逐点变换再逐点相乘”SIMD 和多线程都很好用。所以在工程上如果你有大整数乘法的性能需求并行化往往从乘法下手更划算。我自己在一台 16 线程的机器上做过一次非严格的趋势对比两个两万位的十进制数相乘单线程跑了几十毫秒拆到 8 线程后只剩不到三分之一而同样规模的加法单线程两毫秒8 线程只快了百分之二三十。趋势非常明显——加法并行是在省“几毫秒的零头”乘法并行是在省“几十上百毫秒的大头”。4.5 热词背后的小结所以当你搜“大整数加法 并行”看到大量讨论一点也不奇怪因为加法正好处在“看似简单、实际难并行”的边界线程并行收益有限SIMD 并行收益明显乘法则是“看似复杂、其实好拆”分到多核收益大和 SIMD、FFT 都能无缝衔接。理解这一点做技术选型时心里就有底了。5. 工程选型什么时候自己写什么时候直接用库前面讲了这么多原理最后落到实际项目里核心问题只有一个这套东西到底要不要自己写5.1 位数与算法选型对照先给一个粗颗粒度的对照表十进制位数二进制位数约推荐方案≤ 19 位≤ 64 bit直接 uint64/int64别用大数库≤ 38 位≤ 128 bit__int128 或语言内置的 BigInt几百位几千 bitJava/Python 内置、OpenSSL BN、GMP 都可以几千位几万 bitKaratsuba 起步库内部会自动切 Toom几万位以上十几万 bit 以上FFT/NTT 不可少优先 GMP 等专业库不建议为生产环境从零写大整数乘法库。不是因为有现成的解决方案而是这类代码牵涉符号、内存、进位、阈值切换而且一旦性能不达标很难通过后期零散优化救回来。真要自研定位应该是学习、算法演示或特定约束下的定制。5.2 自己实现时容易踩的三个坑中间结果长度。两数相乘的结果长度是 len(a)len(b)不是 max(len(a), len(b)) 再大一位。分配少了会越界分配多了影响性能。我见过几次 bug都是因为把等长数相乘当成 len*2-1 来分配忘掉了最高位的进位。负数的处理。很多初学者把大整数存成“首位标记符号”然后照抄加法算法进位逻辑立刻全乱。成熟的方案是先做绝对值运算最后再把符号因子加回去或者统一用补码表示但补码下加法、比较要切到另一套思路。基准测试的公平性。测试大整数乘法别在 Python 里手写循环去对比 C 库。这看似可笑但网上确实有许多“Python 大数比 C 慢 1000 倍”的结论就是这么来的。跨语言对比时要让两边使用相同算法和类似的数据布局。5.3 我的实践建议与替代方案如果你只是做算法题、写博客演示Karatsuba 加上朴素乘法就完全够了代码控制在几十行能讲清楚复杂度跃迁即可。如果你在做证书、TLS、区块链这类依赖大整数的项目选 OpenSSL BN 或 GMP 是常识。注意两个库的 API 风格差异很大OpenSSL 的 BN 以“操作者需要手动管理临时变量”出名性能上会给部分灵活性让步GMP 更底层性能优先接口也更机械。Rust 生态可以先用num-bigint或crypto-bigint性能足够覆盖大多数日常需求。如果你真的需要“超长整数 并行”我给的优先顺序是先用合适的基础库跑出单线程可靠性再考虑 SIMD 优化加法常数因子最后才考虑多线程分组算乘法。麻烦程度也是这个顺序递增别反着来。最后说点个人体会。当年做那个密钥工具时我抱着“所有数学库都在做同样的事我自己写可能更快”的心态硬是从朴素乘法开始撸了一版大数运算最后被真实数据教做人朴素乘法和 GMP 之间差了将近两个数量级。那一刻我才真正敬畏“算法复杂度”这四个字。所以后来我但凡遇到“大整数 XX”的需求都会先问自己三件事长度有多大是不是常数时间敏感安全场景有没有并行机会前两个问题决定要不要引入专门库最后一个问题决定要不要在库的基础上再包一层。至于大整数加法和大整数乘法哪个更值得优化我的答案很明确加法优化常数乘法优化算法两者没有高低只是复杂度分布完全不同——希望这篇内容能帮你把这条分水岭彻底看清。
