微啦网 首页 > 教育

人类用四千年碰到乘法运算天花板:史上最快乘法算法诞生

2019-04-15 20:47 环球科学

图片:MENGXIN LI/QUANTA MAGAZINE

四千年前,古巴比伦人最先发明了乘法。而历史上,数学家也在不断简化乘法的步骤,直到上个月,两位数学家发表了迄今步骤最简洁的乘法运算方法。

撰文丨KEVIN HARTNETT

翻译丨董依明

审校丨杨心舟

上个月,两位数学家发表的论文指出,他们发现了至今大数字之间计算速度最快的乘法运算。乘法是数学中最基本的运算方式之一,长期以来,科学家都致力于寻找最高效的乘法运算方式,该研究成果的出现标志着数学家在此方面的探索到达了一个新的高度。

“大家可能会觉得,自己在学校学到的计算方法就是最佳的那种,但事实上,科学家一直都在继续优化数学运算方法,”法国国家科学研究中心的数学家Joris van der Hoeven说道,他是论文的共同作者。从计算圆周率新数值到寻找大质数,许多计算问题的复杂性,归根结底来说就是乘法的速率问题。Hoeven在描述他们的论文成果时,认为乘法运算决定着解决其他问题的速度。

“你可以用许多类似光速的物理常数来描述许多现象,” Hoeven说。 “如果你想知道计算机解决某些数学问题有多快,那么就需要通过整数乘法来表达这些速度。”

传统的乘法运算

我们现在都在使用学校教授的同一种方式运算乘法。首先将两个数字分两排写,然后用下面数字从个位开始与上面的每一位数字一一相乘,最后排列好再做加法运算。如果你将两个两位数相乘,则会出现四次简单的乘法运算,然后得到得数。

传统的乘法运算方法

这种方法需要大约n2步完成乘法计算,其中n是乘数的位数。 因此,三位数字需要9次乘法,而100位数字需要10000次乘法。因此该方法只适用于位数少的数字,但对于数百万或数十亿的数字就不那么方便了。如果要将两个十亿位的数字相乘,则需要进行1018次乘法计算,即使是现代计算机不停歇地工作都大约需要30年才能完成。

几千年来,人们普遍认为已经不存在更快的乘法运算方式。1960年,23岁的俄罗斯数学家Anatoly Karatsuba参加了由20世纪伟大的数学家之一柯尔莫果洛夫领导的研讨会。会上柯尔莫果洛夫断言,n2是乘法运算所需最少的步骤,不存在更快的运算方式。但Karatsuba认是有更快地乘法运算方式的,并且经过一周的探索就发现了它。

Karatsuba算法

Karatsuba的方法尝试对数字的位数进行分解并重新组合,运用这种方式时,可以用少量的加法和减法代替大量的乘法。该方法节省了时间,因为完成加法计算时仅需2n步,而不是n2步(n同样代表数字的位数)。

“如果用加法替代乘法的话,你甚至可以在上学前就使用这种方法,因为它更容易,你可以连续地完成,几乎像从右到左阅读数字一样快,”宾夕法尼亚州立大学数学家MartinFürer说道,他在2007年创造了当时最快的乘法算法。

处理大数字时,你可以重复Karatsuba的过程,将原始数字拆分成与位数一样多的部分。每次拆分,都可以用加法和减法替换掉乘法,这会节省很多步骤。Karatsuba的方法可以将乘法运算步骤减少至n1.58次。新南威尔士大学的数学家,新论文作者David Harvey说:“把一些乘法转变成加法后,计算机会运算得更快。”

大数相乘下两种方法的比较

乘法步骤不断更新

1971年,ArnoldSchönhage和Volker Strassen发表了一种能在n×log n×log(log n)个步骤以内完成的大数乘法。如果是两个10亿位数字相乘,和这种新方法相比,Karatsuba的方法大约需要多运算165万亿个步骤。