数学家发现完美的乘法方法(2019年)

3月18日，两名研究人员描述了迄今发现的最快的将两个非常大的数字相乘的方法。这篇论文标志着一项长期探索的高潮，目的是寻找执行数学中最基本的运算之一的最有效的程序。

“每个人基本上都认为你在学校里学到的方法是最好的，但实际上这是一个活跃的研究领域，”法国国家科学研究中心数学家、该研究的合著者之一约里斯·范德胡芬(Joris Van Der Hoven)说。

许多计算问题的复杂性，从计算圆周率的新数字到寻找大素数，归根结底是乘法的速度。范德胡芬将他们的结果描述为为解决许多其他类型的问题设定了一种数学速度限制。

范德胡芬说：“在物理学中，有一些重要的常数，比如光速，可以用来描述各种现象。”如果你想知道计算机解决某些数学问题的速度有多快，那么整数乘法就会作为一种基本的积木出现，你可以用它来表示那些类型的速度。

几乎每个人都以同样的方式学习乘法。我们将两个数字堆叠起来，将底部数字的每一位与顶部数字的每一位相乘，最后做加法运算。如果要将两个两位数相乘，最终需要执行四次较小的乘法才能得到最终的乘积。

小学或“进位”方法需要大约n 2个步骤，其中n是要相乘的每个数字的位数。因此，三位数需要9次乘法，而100位数需要10,000次乘法。

进位方法对于只有几位数的数字很有效，但当我们将数百万位或数十亿位的数字相乘时(这是计算机用来精确计算圆周率或作为全球搜索大素数的一部分)，它就陷入了困境。将两个10亿位的数字相乘需要10亿的平方，即10 18次乘法，这将需要一台现代计算机大约30年的时间。

几千年来，人们普遍认为没有更快的繁殖方式。1960年，23岁的俄罗斯数学家Anatoly Karatsuba参加了由20世纪伟大数学家之一Andrey Kolmogorov主持的研讨会。科尔莫戈罗夫断言，没有一般的乘法过程需要少于n2步。Karatsuba认为有--经过一周的寻找，他找到了它。

Karatsuba的方法包括分解一个数字的数字，并以一种新颖的方式将它们重新组合，这样你就可以用少量的加法和减法来代替大量的乘法。该方法节省了时间，因为相加只需要2n个步骤，而不是n2个步骤。

宾夕法尼亚州立大学(Pennsylvania State University)数学家马丁·富勒(Martin Fürer)说，“此外，你在学校提前一年做乘法，因为它要容易得多，你可以在线性时间内做，几乎和从右到左读数字一样快。”他在2007年创造了当时最快的乘法算法。

在处理大数字时，您可以重复Karatsuba过程，将原始数字拆分成几乎与其数字一样多的部分。对于每次拆分，您可以用需要少得多的加法和减法来取代需要很多步骤才能计算的乘法。

这篇新论文的合著者、新南威尔士大学(University Of New South Wales)数学家大卫·哈维(David Harvey)说，“你可以把一些乘法运算转化为加法运算，这个想法是，对于计算机来说，加法运算会更快。”

Karatsuba的方法使得仅使用n个1.58个一位数的乘法就可以进行数字乘法。1971年，Arnold Schönhage和Volker Strassen发表了一种方法，能够在n×logn×log(Logn)乘法步骤中乘以大数，其中logn是n的对数。对于两个10亿位的数字，Karatsuba的方法需要大约165万亿次额外的步骤。

Schönhage和Strassen的方法，也就是计算机如何将巨大的数字相乘，产生了另外两个重要的长期后果。首先，它介绍了信号处理领域中一种称为快速傅立叶变换的技术的使用。自那以后，这项技术一直是每一种快速乘法算法的基础。

其次，在同一篇论文中，Schönhage和Strassen推测，应该有一种比他们发现的算法更快的算法-一种只需要n×logn个位数运算的方法-这样的算法将是最快的。他们的猜想是基于一种直觉，即像乘法这样基本的运算一定有一个比n×logn×log(Logn)更精细的极限。

富勒说：“人们普遍认为，乘法是如此重要的基本运算，仅从美学的角度来看，如此重要的运算需要一个很好的复杂性界限。”“从一般的经验来看，最基本的东西最后的数学总是很优雅的。”

Schönhage和Strassen的笨拙的n×logn×log(Logn)方法坚持了36年。2007年，富勒击败了它，闸门打开了。在过去的十年里，数学家们相继发现了更快的乘法算法，每一种算法都逐渐接近n×logn，但都没有完全达到它。上个月，哈维和范德胡芬到了那里。

他们的方法是对摆在他们面前的主要工作的提炼。它拆分数字，使用改进的快速傅立叶变换，并利用了过去40年来取得的其他进步。范德胡芬说：“我们使用(快速傅立叶变换)的方式要猛烈得多，使用几次而不是一次，用加法和减法取代更多的乘法。”

Harvey和van der Hoven的算法证明了乘法可以在n×logn步内完成。然而，这并不能证明没有更快的方法可以做到这一点。要确定这是可能的最佳方法要困难得多。2月底，奥胡斯大学(Aarhus University)的一组计算机科学家发表了一篇论文，认为如果另一个未经证实的猜测也是正确的，这确实是最快的乘法。

虽然新算法在理论上很重要，但在实践中不会有太大变化，因为它只比已经使用的算法略好一些。范德胡芬说：“我们所能希望的最好结果是我们的速度是现在的三倍。”“这不会很壮观。”

此外，计算机硬件的设计也发生了变化。二十年前，计算机的加法运算速度远远快于乘法运算。在过去的20年里，乘法和加法之间的速度差距已经大大缩小，以至于在某些芯片体系结构中，乘法甚至可以比加法更快。哈维说，有了一些硬件，“通过告诉计算机做乘法问题，你实际上可以更快地做加法，这简直是疯了。”

硬件与时俱进，但一流的算法是永恒的。不管未来的计算机是什么样子，哈维和范德胡芬的算法仍将是最有效的乘法。