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


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


翻译丨杨莉昕

审校丨戚译引

来源丨科研圈(ID:keyanquan)


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


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


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


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



更快的算法?

没过几年,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。


还能再快一点吗?

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

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


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


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



我们达到极限了吗?

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

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


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


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

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

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


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


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


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


扩展阅读:

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

本文转载自公众号“科研圈”(ID:keyanquan)

《环球科学》2019年4月刊现已上市

点击图片或点“阅读原文”立即购买

评论已关闭