4000年前，巴比伦人发明了乘法。现在，数学家们已经完善了它。
2019年3月18日，两名研究人员描述了迄今为止发现的两个非常大的数字相乘的最快方法。这篇论文标志着一项长期研究的高潮，该研究旨在找到执行数学中最基本运算之一的最有效程序。
“基本上，每个人都认为你在学校学到的方法是较好的，但实际上这是一个活跃的研究领域，”法国国家科学研究中心数学家、合着者之一乔里斯·范德霍芬说。
许多计算问题的复杂性，从计算π的新数字到寻找大素数，归结为乘法的速度。Van der Hoeven将他们的结果描述为设定了一种数学上的速度限制，来限制其他问题的解决速度。
范德霍芬说：“在物理学中，有一些重要的常数，比如光速，可以用来描述各种现象。”。“如果你想知道计算机解决某些数学问题的速度有多快，那么整数乘法就会作为一种基本的积木出现，你可以用它来表示这些速度。”
大多数人都以同样的方式学习乘法。我们把两个数字叠加在一起，将底部数字中的每一位乘以顶部数字中的每一位，最后进行加法。如果你将两个两位数相乘，你最终会进行四次较小的乘法，得到最终的乘积。
小学或“携带”方法需要大约n2个步骤，其中n是要乘以的每个数字的位数。所以三位数需要九次乘法，而100位数需要10000次乘法。
进位法适用于只有几位数的数字，但当我们将数字乘以数百万或数十亿位数时，进位法就会陷入困境（这是计算机用来精确计算π或作为全球搜索大素数的一部分所做的）。用10亿位数乘以两个数字需要10亿次的平方或1018次乘法，这将花费现代计算机大约30年的时间。
几千年来，人们普遍认为没有更快的繁殖方式。1960年，23岁的俄罗斯数学家安纳托利·卡拉祖巴参加了由20世纪伟大数学家之一安德烈·科尔莫戈洛夫主持的研讨会。科尔莫戈罗夫断言，没有需要少于2步的乘法通用程序。 (乘法_百度百科 (baidu.com)) 认为有——经过一周的搜索，他找到了。
的方法包括分解数字的数字，并以一种新颖的方式重新组合它们，允许你用少量的加法和减法代替大量的乘法。该方法节省了时间，因为添加只需要2n步，而不是n2步。
宾夕法尼亚州立大学数学家马丁·弗勒（ Fürer）在2007年创造了当时最快的乘法算法。他说：“加起来，你在学校提前一年做，因为这更容易，你可以在线性时间里做，几乎和从右到左读取数字一样快。”。
当处理大数字时，你可以重复 程序，将原始数字分成几乎和数字一样多的部分。每一次拆分，你都会用需要更少计算步骤的加法和减法来代替需要很多计算步骤的乘法。
“你可以把一些乘法转换成加法，而且加法运算的速度会更快，”新南威尔士大学的数学家大卫·哈维和这篇新论文的合着者说。
Karatsuba 的方法使得只用n1就可以进行乘法。58个一位数的乘法。然后在1971年，阿诺德·舍恩哈奇和沃尔克·斯特拉森发表了一种方法，能够以n×logn×logn（logn）的乘法步骤将大数相乘，其中logn是n的对数。对于两个10亿位数的数字，卡拉祖巴的方法需要大约165万亿个额外的步骤。
Schönhage(SSA（一种高效的二进制乘法算法）_百度百科 (baidu.com)) 和 Strassen(施特拉森算法_百度百科 (baidu.com)) 的方法，即计算机如何将巨大的数字相乘，还有另外两个重要的长期后果。首先，它介绍了一种来自信号处理领域的技术，称为快速傅里叶变换。自那以后，这种技术一直是每一种快速乘法算法的基础。
其次，在同一篇论文中， Schönhage 和 Strassen 推测，应该有一种比他们发现的算法更快的算法——一种只需要n×logn个位数运算的方法——而且这种算法可能是最快的。他们的猜想基于一种预感，即像乘法这样基本的运算必须有一个比n×logn×log（logn）更优雅的极限。
弗勒说：“人们普遍认为乘法是一种非常重要的基本运算，从美学的角度来看，如此重要的运算需要一个很好的复杂性边界。”。“从一般的经验来看，最后基本事物的数学结果总是优雅的。”
Schönhage 和 Strassen 笨拙的n×logn×logn（logn）方法持续了36年。2007年，弗勒打败了它，闸门打开了。在过去的十年里，数学家们相继发现了速度更快的乘法算法，每一种算法都逐渐接近n×logn，但都没有达到。上个月，哈维和范德霍文到达了那里。
他们的方法是对摆在他们面前的主要工作的改进。它分解数字，使用快速傅里叶变换的改进版本，并利用过去四十年取得的其他进步。范德霍芬说：“我们以一种更猛烈的方式使用（快速傅里叶变换），多次使用它，而不是一次，并用加法和减法取代更多的乘法。”。
Harvey和van der Hoeven的算法证明乘法可以在n×logn步中完成。然而，这并不能证明没有更快的方法。要确定这是较好的方法要困难得多。2月底，奥胡斯大学（Aarhus University）的一组计算机科学家发表了一篇论文，认为如果另一个未经证实的猜想也是真的，那么这确实是实现乘法的最快方法。
虽然新算法在理论上很重要，但在实践中不会有太大变化，因为它只比已经使用的算法稍微好一点。范德霍芬说：“我们最大的希望是我们的速度快了三倍。”。“不会太壮观。”
此外，计算机硬件的设计也发生了变化。20年前，计算机执行加法的速度比乘法快得多。在过去的20年里，乘法和加法之间的速度差距已经大大缩小，在某些芯片架构中，乘法甚至可以比加法更快。哈维说，有了一些硬件，“你实际上可以通过告诉计算机做乘法题来更快地做加法，这简直是疯了。”。
硬件随着时代的变化而变化，但一流的算法是永恒的。不管未来的计算机是什么样子，哈维和范德霍文的算法仍然是最有效的乘法方法。
欢迎点赞、评论、转发。
