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

数学家们找到了一种更快的方法来计算乘法，但是它适用的数字极其庞大，需要经过改进才能得到实际应用，用于计算“仅有”数十亿位的数字。

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

来源 the Conversation

作者 David Harvey，新南威尔士大学数学副教授

翻译 杨莉昕

审校 戚译引

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

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

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

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

更快的方法

没过几年，Kolmogorov 的猜想就被证明是大错特错。

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

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

现实生活中的大数字

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

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

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

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

还能再快一点吗？

在 1971 年的论文中， Schnhage 和 Strassen 也提出了一个引人注目的猜想。为了解释它，我得先讲一点学术知识。

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

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

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

我们达到极限了吗？

几周前，Joris van der Hoeven 和我发表了一篇研究论文（论文链接），描述了一种新的乘法算法，终于触及了 N log (N) 这个“圣杯”，解决了 Schnhage–Strassen 猜想中“简单”的部分。

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

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

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

极其庞大的数字

这项新算法目前还很难得到实际运用，因为我们文章中的证明只适用于大得出奇的数字。即使把每一位数字都写在一个氢原子上，可观测的宇宙中也几乎没有足够的空间写下它们。

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

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

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

扩展阅读：

关于新算法的原理，请阅读《人类用四千年碰到乘法运算天花板：史上最快乘法诞生》

本文来自微信公众号“科研圈”。如需转载，请在“科研圈”后台回复“转载”，或通过公众号菜单与我们取得联系。

论文信息

【标题】Integer multiplication in time O(n log n)

【作者】David Harvey, Joris Van Der Hoeven

【时间】18 Mar 2019

【链接】https://hal.archives-ouvertes.fr/hal-02070778/document

【摘要】Let M(n) denote the time required to multiply two n-bit integers. We work in the multitape Turing model, in which the time complexity of an algorithm refers to the number of steps performed by a deterministic Turing machine with a fixed, finite number of linear tapes [34]. The main results of this paper also hold in the Boolean circuit model [40, Sec. 9.3], with essentially the same proofs. We write f(n) = O(g(n)) (respectively f(n) = (g(n))) to indicate that there exist constants C > 0 and n0 such that f(n) 6 Cg(n) (respectively f(n) > Cg(n)) for all n > n0, and f(n) = Θ(g(n)) to mean that both f(n) = O(g(n)) and f(n) = (g(n)) hold. Sch¨onhage and Strassen conjectured in 1971 that the true complexity of integer multiplication lies in Θ(n log n) [39], and in the same paper established their famous upper bound M(n) = O(n log n log log n). In 2007 their result was sharpened by F¨urer to M(n) = O(n log n Klog n) [12, 13] for some unspecified constant K > 1, where log n denotes the iterated logarithm, i.e., log x := min{k > 0 : logkx 6 1}. Prior to the present work, the record stood at M(n) = O(n log n 4log n) [22]. The main result of this paper is a verification of the upper bound in Sch¨onhage and Strassen’s conjecture, thus completely closing the remaining 4log n gap:

阅读论文解读及推荐

点击关注领研网论文频道。

▽ 精彩回顾 ▽