数学家仍未找到乘法最快解法
Mathematicians still don't know the fastest way to multiply numbers
小学生背乘法口诀表，但面对大数乘法，传统竖式算法效率极低，复杂度高达O(n^2)。1960年，23岁的Anatoly Karatsuba用天才的代数技巧打破了这一认知，将乘法转化为更廉价的加法，大幅提升了计算速度。如今，Python等编程语言在数字达到630位时会自动切换至Karatsuba算法。2019年，David Harvey和Joris van der Hoeven更是提出了O(n log n)的算法，理论上接近乘法速度的极限。然而，这些突破性的算法往往属于“银河系算法”，仅在数字大到不可思议时才显现优势，日常应用中我们仍依赖更实用的方法。乘法效率的每一次提升，都深刻影响着加密、人工智能和硅芯片的性能。
在计算机科学中，银河系算法是一个正式术语，指那些在足够大的数字上效率惊人，但因数字过于庞大而在实践中永远无用的方法。
HN 评论区
144- JoelJacobson
2024 年，我尝试用 Karatsuba 算法优化 PostgreSQL 的 NUMERIC 数据类型（基于 10000 进制）。问题在于，找到切换到 Karatsuba 的最佳阈值非常困难，因为这取决于两个因子的大小总和。折腾了几百个小时后，我放弃了，开始思考是否有更简单的方案。我想起了之前有过但后来放弃的一个想法：将数字基数从 10k 现代化为 100M（64 位），但这因磁盘上现有的数据而充满挑战。在急于寻找解决方案时，我 wondered 是否可以在运行时快速地在 10k 进制和 100M 进制之间进行转换，随后意识到，是的，当然可以，对于相当小的 N 值（测试显示在 3 到 6 个基数位之间）就已经足够快了。这个技巧基本上将 O(N^2) 中的 N 减半，即变为 O((N/2)^2)，同时增加了 O(2*N) 的转换开销。
我和 NUMERIC 数据类型的维护者一起在这个想法上折腾得很开心，两个月后补丁终于准备好了并被合并：
https://git.postgresql.org/gitweb/?p=postgresql.git;a=commit...
- ErroneousBosh
我不知道“小学”具体指哪个年龄段，但我记得 7 或 8 岁时学过这种方法，不过直到读了艾萨克·阿西莫夫（Isaac Asimov）的短篇小说《权力的感觉》（The Feeling of Power）后，我才真正理解透彻。
让我感到惊讶的是，这里似乎漏掉了一点（除非我没注意到页面糟糕的排版），那就是计算机如何相乘两个整数。我大约 11 岁时在一本书里看到过一种技术，被称为“俄罗斯农夫法”（Russian Farmer Method，或者类似的名字，那是英文书，我可能记错了）。
在这种方法中，你将乘数右移，被乘数左移，一个减半，另一个翻倍。如果乘数是奇数，就把被乘数加到总和中。
这实际上和你在小学学过的“长乘法”做同样的事，只是用二进制表示。当你为高位数字在右边加一个 0 时，你是翻倍，而不是乘以十。如果你写代码来实现它，你会先移位乘数，然后通过检查进位标志（Carry flag），或者如果你像我读的那本书的作者一样在 PDP8 上演示，就检查“链接位”（Link bit），来决定是否相加。
但让我们看一个具体的例子，随机选两个数 205 * 707，用较小的那个作为乘数：
205, 707 奇数，加 707 到总和
102, 1414 偶数，忽略
51, 2828 奇数，加 2828 到总和
25, 5656 奇数，加 5656 到总和
12, 11312 偶数，忽略
6, 22624 偶数，忽略
3, 45248 奇数，加 45248 到总和
1, […]
- jmalicki
我在使用带有额外结构的 Strassen 矩阵乘法内核配合自定义 CUDA 内核方面取得了巨大的成功（例如，协方差矩阵是对称正定的，或者可以用 Cholesky 分解表示，这在大量有用的计算中都会出现）。虽然那是几年前的事了，但据我所记，我发现它在 n>2500 左右时开始优于标准内核（此外，我还利用了矩阵的显式结构约束，所以这并不完全是公平的比较）。
- nobrains
为什么我们要让计算机去相乘个位数，而不是像人类一样查表获取结果呢？为了回答我自己的问题，我假设是因为相乘仍然比查表更快？有什么想法吗？
- bombela
这篇文章难道只是为了我描述问题就结束了吗？我意犹未尽，想要更多。
- projectileboy
对深入挖掘感兴趣的朋友，可以看看 Karatsuba 算法（https://en.wikipedia.org/wiki/Karatsuba_algorithm）、Strassen 矩阵乘法（https://en.wikipedia.org/wiki/Strassen_algorithm）以及 Toom-Cook 乘法（https://en.wikipedia.org/wiki/Toom–Cook_multiplication）。
当然，还有实现上的考量。例如，你可以通过递归地将矩阵分解为子矩阵并行化来加速 Strassen，但只能做到一定程度——一旦子矩阵足够小，直接进行 Strassen 计算反而更快。这也取决于你的硬件。对于这样一个看似简单的问题，你真的可以深入到一个兔子洞里去！
- qingcharles
我很惊讶自己以前没听说过这个。如果能看到他们证明已经发现了 O(n × log n) 的最快解法，或者是否还有更多突破，会很有趣。
- morpheos137
据我理解，Karatsuba 算法只有在相对于人类尺度非常大的数字上才变得有利。数学上它很有趣，但在工程角度，开销通常不值得用于实际应用。因子大小和乘积精度之间存在根本性的权衡。如果你能接受较低的精度，那么对于人类尺度上的大数，浮点数就很好用。