人类用四千年碰着乘法运算天花板：史上最快乘法算法降生

图片：MENGXIN LI/QUANTA MAGAZINE

[原文来自：www.ii77.com]

[本文来自：www.ii77.com]

撰文丨KEVIN HARTNETT

翻译丨董依明

审校丨杨心舟

上个月，两位数学家揭橥的论文指出，他们发现了至今大数字之间较量速度最快的乘法运算。乘法是数学中最根基的运算体式之一，历久以来，科学家都致力于寻找最高效的乘法运算体式，该研究功效的显现标记着数学家在此方面的索求达到了一个新的高度。

“人人或者会感觉，本身在学校学到的较量方式就是最佳的那种，但事实上，科学家一向都在持续优化数学运算方式，”法国国度科学研究中心的数学家Joris van der Hoeven说道，他是论文的配合作者。从较量圆周率新数值到寻找大质数，很多较量问题的复杂性，归根结底来说就是乘法的速度问题。Hoeven在描述他们的论文功效时，认为乘法运算决意着解决其他问题的速度。

“你能够用很多雷同光速的物理常数来描述很多现象，” Hoeven说。 “若是你想知道较量机解决某些数学问题有多快，那么就需要经由整数乘法来表达这些速度。”

我们如今都在使用学校传授的统一种体式运算乘法。首先将两个数字分两排写，然后用下面数字从个位起头与上面的每一位数字一一相乘，最后分列好再做加法运算。若是你将两个两位数相乘，则会显现四次简洁的乘法运算，然后获得得数。

传统的乘法运算方式

这种方式需要大约n²步完成乘法较量，个中n是乘数的位数。 是以，三位数字需要9次乘法，而100位数字需要10000次乘法。是以该方式只适用于位数少的数字，但对于数百万或数十亿的数字就不那么轻易了。若是要将两个十亿位的数字相乘，则需要进行10¹⁸次乘法较量，即使是现代较量机一直歇地工作都大约需要30年才能完成。

几千年来，人们遍及认为已经不存在更快的乘法运算体式。1960年，23岁的俄罗斯数学家Anatoly Karatsuba列入了由20世纪伟大的数学家之一柯尔莫果洛夫向导的钻研会。会上柯尔莫果洛夫断言，n²是乘法运算所需起码的步伐，不存在更快的运算体式。但Karatsuba认是有更快地乘法运算体式的，而且经由一周的索求就发现了它。

Karatsuba的方式测验对数字的位数进行分化并从新组合，运用这种体式时，能够用少量的加法和减法取代大量的乘法。该方式节约了时间，因为完成加法较量时仅需2n步，而不是n²步（n同样代表数字的位数）。

“若是用加法替代乘法的话，你甚至能够在上学前就使用这种方式，因为它更轻易，你能够一连地完成，几乎像从右到左阅读数字一般快，”宾夕法尼亚州立大学数学家MartinFürer说道，他在2007年缔造了其时最快的乘法算法。

处理大数字时，你能够反复Karatsuba的过程，将原始数字拆分成与位数一般多的部门。每次拆分，都能够用加法和减法替代掉乘法，这会节约好多步伐。Karatsuba的方式能够将乘法运算步伐削减至n^1.58次。新南威尔士大学的数学家，新论文作者David Harvey说：“把一些乘法改变成加法后，较量机会运算得更快。”

大数相乘下两种方式的对照

1971年，ArnoldSchönhage和Volker Strassen揭橥了一种能在n×log n×log（log n）个步伐以内完成的大数乘法。若是是两个10亿位数字相乘，和这种新方式比拟，Karatsuba的方式大约需要多运算165万亿个步伐。

Schönhage和Strassen的大数乘法，对将来的研究供应了两个久远的影响。 首先，它引入了旌旗处理手艺中被称为快速傅立叶变换的方式，该手艺一向以来都作为快速乘法算法的根蒂。

其次，在其时Schönhage和Strassen推想应该还会有一个更快的算法，一种只需要n×log n单元单子数乘法的方式，而且这种算法或者会是最快的。他们推想，必然存在某种像乘法自己那样根蒂的运算，会比n×log n×log（log n）更简练。

“乘法的根蒂性与主要性无需多言，从美学的角度来说，如斯主要的运算方式终会从复杂走向简洁”Fürer说。“一样经验来看，数学运算到最后都邑变得简练。”

就如许，Schönhage和Strassen提出的 n×log n×log（log n）方式持续了36年。2007年，Fürer超越了它并打开了新的大门。而在2007年至今的十几年中，数学家也接踵地发现了更快的乘法算法，且每个算法都接近n×log n，但又没有完全达到它。终于在上个月，Harvey和van der Hoeven做到了。

他们的方式总的来说是对之前工作进行了改善。包罗拆分数字，使用快速傅立叶变换的改善版本，并综合了曩昔40年各类研究的优点。“我们更频仍地使用快速傅里叶变换，不再是只使用一次，并用加法和减法取代更多的乘法，”Hoeven说。

发现最新乘法运算方式研究者之一Hoeven。图片：ÉCOLE POLYTECHNIQUE

Harvey和Hoeven的算法证实了乘法能够在n×log n步伐内完成运算，但这并不代表没有更快的方式了。今朝最具挑战的就是要确立Hoeven的方式是最快的，2月底，奥尔胡斯大学的一个较量机科学家小组揭橥了一篇论文，认为若是另一个未经证实的猜想是准确的话，那Hoeven的乘法运算最快的方式了。

固然新算法在理论上取得了冲破，但它在实际应用中结果甚微，因为它只比之前的算法稍微快一点。 “我们所进展的是，最好的方式运算能力应该比如今的快三倍，”Hoeven说。

此外，较量机硬件的设计也发生了转变。二十年前，较量机执行加法要比乘法快。但在曩昔20年中，乘法和加法之间的速度差距已大大缩小，在一些芯片架构中，乘法运算甚至比加法还要快。对于一些硬件，“若是你想完成加法较量，你甚至能够让它们经由执行乘法来完成，如许说不定还更快。用乘法的运算速度来实现加法，这看起来有些疯狂疯。”Harvery说。

硬件会跟着时间而改变，但最佳的算法体式倒是永恒的。无论较量机会成长到什么水平，Harvey和Hoeven的算法将仍然是最有效的乘法算法。

原文链接：

https://www.wired.com/story/mathematicians-discover-the-perfect-way-to-multiply/

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

点击图片或点“阅读原文”立刻购置