乘法的完美算法是什么？数学家可能才刚刚找到答案
乘法的完美算法是什么？数学家可能才刚刚找到答案From 佐佑
原理
Yesterday
自乘法发明以来，数千年已经过去了，但是直到最近，数学家可能才让这一“技艺”接近完美。你或许会好奇，难道我们至今还没有完美的乘法计算方法吗？我们自小从课堂里学的方法难道不够好吗？事实上，乘法算法是数学里的一个活跃的研究领域。
现有的方法虽然简单且看似高效，但它却不适用于极度大的数字，例如那些超过十亿位的数字。无论是计算圆周率还是寻找大的质数，其中所涉及的计算问题的复杂性归根结底都源自于乘法的速度。3月18日，数学家David Harvey和Joris van der Hoeven（分别来自新南威尔士大学和巴黎综合理工大学）在HAL（法国国家科学研究中心机构库）提交了一篇论文，论文描述了一个将两个非常大的数字相乘的新方法，这是迄今为止发现的最快、最高效的乘法算法。
当我们想知道计算机能多快的解决一些数学问题时，整数间的乘法就是其中最基本的关键所在。当要计算的数字非常大时，衡量速度的最重要标准就是随着数字的位数增加，所需的运算量会增长得多快。
几乎我们所有人从课堂里学到乘法方法都一样：我们将两个要相乘的数上下写在一起，然后用底下数字的每一位去乘以上面数字的每一位，最后再将结果加起来。也就是说当我们要做一个两位数乘以两位数的乘法时，需要总共做四次小的乘法来得到最终的乘积。https://mmbiz.qpic.cn/mmbiz_jpg/tqOuxs8dsHMCHkTm8Xiaib5NdVzIpROvjVYOJLtwwmPFg9l0xfrMbiaXDnqdRZvjnvv7aoPlrZtcxbUicPuPnJDesQ/640?wx_fmt=jpeg○ 传统算法2位数相乘，需要做4次单位数字相乘，再求和才能得到结果。
用这种“进位”方法来做n位数乘以n位数的乘法时，一般需要n²步，所以3位数相乘需要做9次乘法，而100位数相乘则需要做10000次乘法。也就是说这种方法只适用于只有几位数的数字相乘，但在面对将数百万位或数十亿位的数字时，便会陷入困境。https://mmbiz.qpic.cn/mmbiz_jpg/tqOuxs8dsHMCHkTm8Xiaib5NdVzIpROvjVUCsticI34UIPmWArUBkfAsiaswk7WvapSibjVJfPWTHobmia5ovgvJBCKA/640?wx_fmt=jpeg○ 传统算法的4位数相乘，需要做16次单位数字的乘法，再求和。
可是在精确计算圆周率或者搜寻大型质数中，我们必须进行这样的运算。如果用这种方法做两个10亿位数的数字相乘，大约将需要花费30年的时间。
1960年，被誉为20世纪最伟大的数学家之一的柯尔莫果洛夫（Andrey Kolmogorov）曾断言，不存在通用的能让数字相乘在少于n²步之内完成的运算方法。而当时年仅23岁的数学家Anatoly Karatsuba却认为——有！经过一周的搜索之后——他找到了。1962年，他正式发表了他的Karatsuba算法。
Karatsuba的算法需要将数字分解，并以一种新颖的方式重新组合它们，然后用少量的加法和减法来替换大量的乘法运算。这一方法能节省时间，因为相比于乘法的n²步，加法只需2n步。
https://mmbiz.qpic.cn/mmbiz_jpg/tqOuxs8dsHMCHkTm8Xiaib5NdVzIpROvjVPHe1jkQq8W5Aibib6TabHicBP0u1N1czvTv8bfpngzLG5ly4d2nibbwYSw/640?wx_fmt=jpeg○ Karatsuba算法的2位数相乘，只需要3次乘法运算（B、C、E），再加上加减法运算。
当处理较大的数字时，可以重复使用Karatsuba算法，将原始数字进行拆分。每进行一次拆分，就可以用加法和减法来代替需要很多步骤才能计算的乘法。而对于计算机来说，加法运算比乘法运算要更快。Karatsuba的算法能将n位数的数字相乘的运算量缩减到n^1.58。
https://mmbiz.qpic.cn/mmbiz_jpg/tqOuxs8dsHMCHkTm8Xiaib5NdVzIpROvjVIITf38bgcLl3aociadWwUJKL9flQScmnicV6QNgjPIqKKD3z23pqtbQg/640?wx_fmt=jpeg○ Karatsuba算法的4位数相乘，只需要3次Karatsuba乘法运算，每次Karatsuba运算包括三次单位数乘法运算，因此总共只需要进行9次乘法运算。
到了1971年，德国数学家Arnold Schonhage和Volker Strassen发表了一种方法，对于n位数的数字相乘（n较大），可以在n×log(n)×log(log(n))步内完成乘法运算。当两个n等于10亿的数字相乘时，Schonhage和Strassen的算法比Karatsuba的方法节省了大约165万亿步。
Schonhage和Strassen的算法不仅成为了计算机用来计算大型数据相乘的方法，并且将信号处理领域中的快速傅里叶变换作为了可用于快速乘法算法的技术。除此之外，他们还推测出应该存在一种比他们的方法更快的算法：对于n位数的数字相乘，更快的算法应该只需要n×log(n)个运算步骤便可以完成；并认为这种算法可能是乘法运算的极限速度。
Schönhage和Strassen的方法一直坚挺了36年，直到2007年才被数学家Martin Fürer击败。Fürer发现了当时的最快乘法运算方法，但他放弃了精进他的算法。他曾在一个采访中表示，这是一个难度极大的挑战，他对此毫无信心。正因如此，他对新研究的成功才表示出无比的惊讶与兴奋。
不过自Fürer之后，数学家们在过去的十年间相继发现了更快的乘法算法，每一种都在一点点地逼近n×log(n)，但都没能完全达到。直到上个月，Harvey和van der Hoeven抵达了这个极限。
新的方法是基于对前人的工作进行改进而得出的成果。他们用了改进过的快速傅里叶变换步，而且在他们的方法中会多次用到快速傅里叶变换，用加法和减法取代更多的乘法。
Harvey和van der Hoeven的算法证明了乘法的确可以在n×log(n)步内完成，这在理论上能算得上一大突破。但在实践中，它并不能表现出明显的优势，它的高效主要体现在大得惊人的数字相乘上。van der Hoeven说，我们最多可以期待它比已有的算法快3倍。
在这项研究中，他们只考虑了多于10214857091104455251940635045059417341952位以上的二进制数字，这些数字用0和1进行编码。不过他们并没有真实地进行任何大规模的乘法运算，因为这个数字比宇宙中的原子数量还多得多。这意味着计算机根本无法进行这样的计算，因为没有足够的原子来表示如此巨大的数字，更不用说将它们相乘了。他们所做的是提出了一种技术，使得能从理论上证明这种技术将比其他方法更快，或者说至少对于这么大的数字会是这样。
而另一个对这个算法不那么有利的因素是，现如今的计算机硬件已与20年前的大为不同。在一些新的芯片构架中，乘法运算与加减法运算的速度差距在不断缩小，甚至有的还能比加减法运算更快。因此在一些情况下，研究人员可能还需要设法用乘法运算来代替加法运算以提高运算速度。
尽管如此，但这一算法仍有可能在寻找新的质数或精确圆周率方面发挥作用。在乘法运算这样一个基本问题上能取得这样的成就无疑是非常了不起的。而且即便硬件会随时代变化，但一流的算法是永恒的。不管未来的计算机是什么样子，都不会改变Harvey和van der Hoeven找到了迄今为止最有效的乘法算法的事实。
编译：佐佑参考链接： https://hal.archives-ouvertes.fr/hal-02070778/document
https://www.quantamagazine.org/mathematicians-discover-the-perfect-way-to-multiply-20190411/ https://www.sciencenews.org/article/mathematicians-may-have-found-fastest-way-multiply-huge-numbers?tgt=nr
页:
[1]