地点地位: 前沿科技首页 > 最新文章 > 其余前沿进展  > 正文

迄今为止最快乘法!——数学家终实现40多年前预测

>2019-05-14 10:15:34 来源: 中国科技网 作者: 夏青

据《全球科学》报导,数学期刊HAL于3月18日发表新南威尔士大学David Harvey、法国国度科学研究中央Joris van der Hoeven两位数学家文章,提出迄今大数字之间步骤最简洁的乘法运算办法。“很多计算成就的复杂性,归根结底来说便是乘法的速率成就,”论文作者Hoeven表示,这项高效的乘法运算办法研究效果可以或许提高解决从计算圆周率新数值到寻找大质数等其余成就的速率。

传统的乘法运算被称为竖式乘法,即咱咱咱们在黉舍里学到的在草稿纸上笔算乘法的办法:首先把两个数字分两排写,用下面的数字从个位开端与上面的每一名数字一一相乘,然后把结果错列对齐、再做加法运算。这种办法必要n?步能力实现乘数位数为n的乘法计算,例如,100位数字必要10000次乘法。由此可见,若利用此传统办法计算百万甚至亿位数字的乘法,即使应用现代计算机都非常耗时。

n?当然不是乘法运算所需最少的步骤。数学家咱咱们赓续简化乘法的步骤,颠末过程尝试对数字的位数停止分解偏从新组合,用少量的加减法代替大批的乘法,以节省总运算光阴,如能将步骤减为n1.58步的“Karatsuba算法”(由俄罗斯数学家Karatsuba于1960年提出)、1971年Sch?nhage和Strassen发表的“大数乘法”、2007年宾夕法尼亚州立大学数学家Martin Fürer发现的其时最快的乘法算法,等等。乘法运算办法赓续优化,直到2019年3月18日,数学家终于做到了如1971年推测那般、只必要n×log n步骤内实现运算的乘法办法。这是迄今为止的最快乘法运算办法。

不过,近20年计算机硬件发生变更,一些芯片架构履行乘法和加法时已不存在速率上的差距。因此,虽然新算法在实践先〉昧舜蚱,但在实际应用中因未能晋升多少速率而效果甚微。尽管如斯,自四千年前古巴比伦人最先创造乘法以来,各代科学家咱咱们仍竭尽全力寻找最佳算法。

(策划/夏青;审校/桂楷东)

任务编辑: 夏青
友情链接:科技媒体网  爱贝基础教育网  中国工程项目管理网  万力木业新闻网  广州洲越贸易公司  华夏娱乐新闻网  安神养生新闻网  迅诚电脑IT新闻网  旭升画报网  金融时报网