最高效的乘法：两个非常大的数字相乘迄今最快算法

发表于 5年以前 | 总阅读数：754 次

新浪科技讯北京时间5月5日消息，据国外媒体报道，四千年前，巴比伦人发明了乘法，而最近数学家们又对乘法进行了完善，两位研究人员描述了迄今为止发现的将两个非常大的数字相乘的最快方法。这篇论文具有重要的意义，标志着长期以来寻找最高效乘法步骤的努力达到了新的高度。

“基本上，每个人都认为你在学校学习的（相乘）方法是最好的，但实际上这是一个活跃的研究领域，”法国国家科学研究中心的数学家、论文合著者约里斯·范德霍芬说道。该论文发表在法国的国家开放存取文献数据库Archive ouverte HAL（https：//hal.archives-ouvertes.fr/hal-02070778/document）上。

从计算圆周率的新位数到寻找大质数，许多计算问题的复杂性都可以归结为乘法运算的速度。按照范德霍芬的描述，他们的研究结果其实是为许多其他类型的问题的求解速度设定了一种数学极限。

“在物理学中，有一些重要的常数，比如光速，可以用来描述各种现象，”范德霍芬说，“如果你想知道计算机解决某些数学问题的速度能有多快，那么就可以将整数乘法视为某种基础，你可以用它来表示这些速度。”

大多数人都用同样的方法学习乘法。我们把两个数分两排写，用下面数字的每一位乘以上面数字的每一位，最后排列好再做加法。如果是两个两位数的数相乘，那你一共要做四个较简单的乘法来得到最终的乘积。

这种小学中所教的方法或称“进位”法需要n^2个步骤，其中n是每个相乘数字的位数。所以3位数需要9次乘法，而100位数需要10000次乘法。

这种进位法适用于只有几个位数的数字，但是当我们将具有数百万或数十亿位数的数字相乘（比如计算机精确计算圆周率，或者寻找大型质数）时，这种方法就会陷入停滞。两个10亿位数的数字相乘需要运行10^18次（10亿的平方）的乘法——这将花费现代计算机大约30年的时间。

几千年来，人们普遍认为没有更快的相乘方法。1960年，23岁的俄罗斯数学家安纳托利·卡拉苏巴参加了由20世纪最伟大数学家之一的安德烈·科尔莫戈罗夫主持的研讨会。柯尔莫戈罗夫在会上断言，没有少于n^2个步骤的通用乘法过程。卡拉苏巴认为并非如此。经过一周的努力，他找到了更快进行乘法运算的新方法。

卡拉苏巴的方法涉及将数字按数位分解，并以一种新颖的方式重新组合它们，允许使用少量的加法和减法替换大量的乘法。该方法可以节省时间，因为加法只需2n步，而不是n^2步。

“如果用加法的话，你可以在学校里提早一年就使用这一方法，因为它容易得多。你可以连续地相乘，几乎就像从右到左阅读数字一样快，”宾夕法尼亚州立大学的数学家马丁·富勒说道。他在2007年建立了当时最快的乘法算法。

当处理大数时，你可以重复卡拉苏巴的过程，将原始数字分解为几乎与数位同样多的部分。每进行一次拆分，就可以用加法和减法来代替乘法，从而减少很多步骤。澳大利亚新南威尔士大学的数学家、这篇新论文的合著者大卫·哈维说：“你可以把一些乘法转化为加法，重点在于，对电脑来说，做加法的速度会更快。”

卡拉苏巴的方法使得仅使用n^1.58个一位数乘法就可以进行大数的相乘。然后在1971年，德国数学家阿诺德·肖恩哈格和沃克尔·斯特拉森发表了一种方法，可以在n×log n×log（log n）个步骤内完成的大数乘法，其中log n是n的对数。对于两个10亿位数的数字，卡拉苏巴的方法需要大约额外运算165万亿个步骤。

肖恩哈格和斯特拉森的方法主要是关于计算机如何运算大数乘法，对未来的研究产生了两个重要的长期影响。首先，该方法引入了一种来自信号处理领域的技术，即快速傅里叶变换。该技术一直是所有快速乘法算法的基础。

其次，在同一篇论文中，肖恩哈格和斯特拉森推测应该有一种更快的算法，一种只需要n×log n个单位数运算的方法，而且这种算法可能是最快的。他们的推测基于一种直觉，即像乘法这样的基本运算必须有一个比n×log n×log（log n）更优雅的极限。

“人们普遍认为，乘法运算是一项非常重要的基本运算，以至于从美学的角度来看，这么重要的运算需要一个很好的复杂度边界，”富勒说，“从一般经验来说，基本事物的数学最终总是优雅的。”

肖恩哈格和斯特拉森提出的n×log n×log（log n）方法直到36年后才被取代。2007年，富勒提出了新的方法，闸门打开了。在过去的十年里，数学家们相继发现了更快的乘法算法，每一种算法都在一点点逼近n×log n，但都没有完全达到。最终在上个月，哈维和范德霍芬做到了。

他们的方法主要是对前人工作进行了改进，包括拆分数字，使用改进版的快速傅里叶变换，并利用了过去40年取得的其他进展。范德霍芬说：“我们以更加频繁的方式使用（快速傅里叶变换），而不是只使用一次，并且用加法和减法取代更多的乘法。”

哈维和范德霍芬的算法证明了乘法可以在n×log n步内完成，但这并不能证明没有更快的方法。要确定这是可能的最佳方法要困难得多。今年二月底，丹麦奥尔胡斯大学的一个计算机科学家小组发表了一篇论文，认为如果另一个未经证实的猜想也是正确的话，那么哈维和范德霍芬确实提出了最快的乘法运算方法。

虽然新算法在理论上具有重要意义，但在实践中还不会带来太大的变化，因为它只比已有的算法好一点点。“我们所期望的是，这种方法的运算速度能比现在快三倍，”范德霍芬说，“不会太过惊人。”

此外，计算机硬件的设计也发生了变化。20年前，计算机的加法运算比乘法运算快得多。经过过去20年的发展，乘法和加法之间的速度差距已经大大缩小，在一些芯片架构中，乘法甚至可以比加法更快。哈维表示，利用一些硬件，“你实际上可以通过让计算机做乘法来加快做加法的速度，这简直太疯狂了。”

硬件会随着时代而改变，但一流的算法是永恒的。不管未来的计算机是什么样子，哈维和范德霍芬的算法仍然是最高效的乘法算法。