优德88手机投注_w8811优德安全网_忧德w88top

频道:科技创新 日期: 浏览:311

乘法创造以来,数千年现已曩昔了,但是直到最近,数学家或许才让这一“技艺”挨近完美。你或许会猎奇,莫非咱们至今还没有完美的乘法核算办法吗?咱们自小从讲堂里学的办法莫非不行好吗?现实上,乘法算法是数学里的一个活泼的研讨范畴。


现有的办法尽管简略且看似高效,但它却不适用于极度大的数字,例如那些超越十亿位的数字。无论是核算圆周率仍是寻觅大的质数,其间所触及的核算问题的复杂性归根到底都源自于乘法的速度。3月18日,数学家David HarveyJoris van der Hoeven(别离来自新南威尔士大学和巴黎归纳理工大学)在HAL(法国国家科学研讨中心组织库)提交了一篇论文,论文描绘了一个将两个十分大的数字相乘的新办法,这是迄今为止发现的最快、最高效的乘法算法。


当咱们想知道核算机能多快的处理一些数学问题时,整数间的乘法便是其间最基本的关键所在。当要核算的数字十分大时,衡量速度的最重要规范便是跟着数字的位数添加,所需的运算量会增加得多快。


简直咱们所有人从讲堂里学到乘法办法都相同:咱们将两个要相乘的数上下写在一同,然后用底下数字的每一位去乘以上面数字的每一位,终究再将效果加起来。也便是说当咱们要做一个两位数乘以两位数的乘法时,需求一共做四次小的乘法来得到终究的乘积。

○ 传统算法2位数相乘,需求做4次单位数字相乘,再求和才干得到效果。


用这种“进位”办法来做n位数乘以n位数的乘法时,一般需求n²步,所以3位数相乘需求做9次乘法,而100位数相乘则需求做10000次乘法。也便是说这种办法只适用于只要几位数的数字相乘,但在面临将数百万位或数十亿位的数字时,便会陷入困境。

○ 传统算法的4位数相乘,需求做16次单位数字的乘法,再求和。


但是在准确核算圆周率或许查找大型质数中,咱们有必要进行这样的运算。假如用这种办法做两个10亿位数的数字相乘,大约将需求花费30年的时刻。


1960年,被誉为20世纪最巨大的数学家之一的柯尔莫果洛夫(Andrey Kolmogorov)曾断语,不存在通用的能让数字相乘在少于n²步之内完结的运算办法。而其时年仅23岁的数学家Anatoly Karatsuba却以为——有!通过一周的查找之后——他找到了。1962年,他正式宣布了他的Karatsuba算法


Karatsuba的算法需求将数字分化,并以一种新颖的办法重新组合它们,然后用少数的加法和减法来替换许多的乘法运算。这一办法能节省时刻,由于比较于乘法的步,加法只需2n步。


○ Karatsuba算法的2位数相乘,只需求3次乘法运算(B、C、E),再加上加减法运算。


当处理较大的数字时,能够重复使用Karatsuba算法,将原始数字进行拆分。每进行一次拆分,就能够用加法和减法来替代需求许多过程才干核算的乘法。而关于核算机来说,加法运算比乘法运算要更快。Karatsuba的算法能将n位数的数字相乘的运算量缩减到n^1.58。


○ Karatsuba算法的4位数相乘,只需求3次Karatsuba乘法运算,每次Karatsuba运算包含三次单位数乘法运算,因而一共只需求进行9次乘法运算。


到了1971年,德国数学家Arnold SchonhageVolker 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找到了迄今为止最有用的乘法算法的现实。


编译:佐佑

参阅链接:

[1] https://hal.archives-ouvertes.fr/hal-02070778/document

[2] https://www.quantamagazine.org/mathematicians-discover-the-perfect-way-to-multiply-20190411/

[3] https://www.sciencenews.org/article/mathematicians-may-have-found-fastest-way-multiply-huge-numbers?tgt=nr


热门
最新
推荐
标签