“史上最快乘法算法”太快了，发明者正在想怎么让它“慢”下来

来源丨科研圈

长乘法还真是一种漫长的算法呢。图片来源：David Harvey

翻译丨杨莉昕

审校丨戚译引

两个数相乘很简单，对吧？我们在小学就会学习长乘法，就像题图这样。类似的方法可以追溯到几千年前，至少到古苏美尔人和古埃及人时代。但这真的是求两个大数的乘积的最好方法吗？

在长乘法中，我们必须用第一个数的每一位与第二个数的每一位相乘。如果两个数均有 N 位，总共就是 N2 次相乘。在上面的例子中，N 为 3， 我们必须做 32 = 9 次乘法运算。

约 1956 年，著名苏联数学家 Andrey Kolmogorov 猜测这就是两数相乘的最佳办法。 换句话说，无论你如何安排，运算的工作量至少是 N2 量级。位数翻倍意味着工作量增至四倍。

Kolmogorov 认为，如果简便方法可能存在的话，一定早就被发现了。毕竟几千年来人们一直在计算乘积。这是“诉诸无知”逻辑谬论的极好的例子。（诉诸无知：如果一个假设没有被证明是假/真的，那么这个假设是真/假的。）

更快的算法？

1960 年，23 岁的俄罗斯数学系学生 Anatoly Karatsuba 发现了一种代数技巧，能够减少需要相乘的次数。例如，运用 Karatsuba 的方法，将两个四位数相乘只用做 9 次乘法，而不是 42 = 16 次。他的方法在位数翻倍时工作量只增至三倍，与传统方法相比，在数字更大时展现了巨大的优势。对于 1000 位的数字，Karatsuba 的方法需要的乘法运算次数只有长乘法的大约 17 分之一。

但究竟为什么要把这么大的数字相乘呢？事实上，这样的乘法有大量相关应用。最明显并且最具经济效益的一个应用方向就是密码学。

现实中的大数字

每次你在网络上使用加密交流时，比如登录银行网站或进行网络搜索的时候，你的设备会执行大量乘法，其中涉及上百位甚至上千位的数字。在这个过程中，你的设备很可能就使用了 Karatsuba 的技巧。这都是软件生态系统的一部分，能让使我们的网页尽快加载出来。

在一些保密等级更高的应用中，数学家还必须应对更庞大的数字，位数达到上百万、十亿甚至万亿。对于这样的数字，甚至连 Karatsuba 的算法都太慢了。

1971 年，德国数学家 Arnold Schönhage 和 Volker Strassen 带来了一个真正的突破。他们解释了如何使用当时刚刚发表的快速傅里叶变换（fast Fourier transform，FFT）高效地将巨大数字相乘。现在，他们的方法已被数学家经常应用来处理数十亿位的数字。

FFT 是 20 世纪最重要的算法之一。它在日常生活中最常见的应用就是数字音频：每当你听 MP3、音乐流媒体或数字电台时，在台后进行音频解码的正是 FFT。

还能再快一点吗？

们的猜想的前半部分是：有可能通过最多 Nlog (N)（即 N 的自然对数的 N 倍）次量级的基本运算来将 N 位数相乘。他们自己的算法并未完全实现这个目标，它所需的运算次数是理论最小值的 log (log N)（N 对数的对数）倍。然而，直觉让他们怀疑漏掉了什么东西，Nlog (N) 应该是可行的。

自 1971 年起的几十年来，一些研究者已经对 Schönhage 和 Strassen 的算法进行了改进。尤其是 Martin Fürer，他在 2007 年设计的一种算法已经极其接近难以达到的 Nlog (N) 量级。

他们猜想的第二部分，也是更为困难的部分是：Nlog (N) 应该是基本的运算速度极限。也就是说，不可能有乘法算法能实现比这更少的运算次数。

我们达到极限了吗？

这篇文章还未经过同行评审，所以需要谨慎看待。在数学界，研究成果常常在经历同行评审之前就被传播开来。

我们的算法没有采用一维 FFT 方法（自 1971 年起关于这一问题的所有研究工作都依靠这种方法），而是使用了多维 FFT 方法。这方法本身并不新，广泛使用的 JPEG 图片格式就依靠二维 FFT 方法，三维FFT方法在物理和工程中也有很多应用。

在我们的论文中，我们使用了 1729 维的 FFT 方法。这很难想象，但在数学上并不比二维情况麻烦。

另一方面，我们希望通过进一步的改进，能让算法适用于只有数十亿或万亿位的数字。如果能实现这个目标，它将很可能成为计算数学家的工具包中必不可少的装备。

如果 Schönhage–Strassen 猜想完全正确，那么理论上，这项新算法已到了路的尽头，不可能做得更好了。

就我个人而言，如果猜想最终是错误的，那么我也会非常惊讶。但我们不应忘记发生在 Kolmogorov 身上的事情。数学有时会给人带来惊喜。

该文作者为新算法发明人之一David Harvey