您的位置:首页 > 山西新闻

柯尔莫哥洛夫惨遭打脸,没想到乘法难题竟被澳大利亚数学家解决

时间:2019-09-30

今天,八岁的表弟从学校回家,她沮丧而沮丧。

超模俊:“小孩,你好吗?”

表兄弟:“今天的数学课,老师要求19乘17等于19。印度孩子站起来回答,他为什么如此强大,不是没有99乘法吗?”

超模俊:“毕竟,人们是19 * 19乘法的家。”

表姐尴尬地看着:“这是东西吗?”

花式乘法算法

确实有这样的事情。热爱“开放”的印度国家在乘法表中“开放”。“ 19 * 19乘法表”:

什么概念?就像堂兄在课堂上被“绞死”一样,您问他们18 * 16等于多少,他们不必思考,第二个是“ 288”,并且您必须精打细算才能得到答案。

这是可以理解的。毕竟,我们使用第九个乘法表。 18 * 16超出了我们口头计算的范围。对于超过一位的乘法,我们通常使用垂直乘法算法:

在这句话中:特别感谢城市第二中学三年级的李老师,这是您的价值,让我深刻地记住垂直乘法!

实际上,印度不仅与我们的国家相同。它们大于19 * 19,并且乘法算法不同。印度伙伴如何计算?

据说是这样的:

他们称此算法为网格乘法,虽然感觉不错,但可能有点草稿。

话虽如此,我不得不提到在英格兰,威尔士和美国部分地区常见的网格/框乘法。

网格乘法:

除此之外,还有行乘法:

如果算上这么少的数字,那么起草会如此,那么他们不能留在造纸厂解决数学问题吗?

毕竟没有必要,您可以使用计算机计算。

然后问题又来了。当涉及到使用现有的乘法算法逻辑进行数亿次计算,计算pi或找到最大素数时,甚至超级计算机也无法承受。

例如,要使用垂直乘法算法将两个十亿位数相乘,则需要十亿平方相乘。对于现代计算机,此操作大约需要30年。

历史的车轮滚滚向前,数学家们从未停止研究乘法算法。

颠覆传统,算法升级

如今,算术运算的研究历史记录在《古今数学思想》中,其中必须提到进行算术运算的20世纪最伟大的数学家之一安德烈科尔莫戈洛夫(Andrei Kolmogorov)。一个非常深入的研究。

1960年,Kolmogorov举行了关于算术开发的研讨会。他说,没有办法将两个n位数字乘以小于n个平方的平方之间的乘法。

现场数学家几乎同意Kolmogorov的观点,并同意没有比传统的垂直乘法更好的乘法算法。

但是声音刚落下来,23岁的俄罗斯数学家阿纳托利Karatsuba公开反对,现场一片茫然。

在他解雇了伟大的数学家的脸后,许多数学家认为这个孩子是疯子。

但是令人惊讶的是,仅仅一周后,他发现了一种比垂直乘法着名的Karatsuba算法更快的算法。

例如,计算25乘以63。传统算法需要4个单位数字的乘法和几个加法:

Karatsuba算法要求在单个数字之间进行3次乘法,并进行几次加法和减法:

实际上,Karatsuba算法的主要思想是分而治之算法。尽管看起来很复杂,但它的优势体现在乘以大数时,从而节省了个位数之间的乘法数:

当乘法器中的位数很大时,可以重复唐津过程,将大量的乘法器拆分成较小的部分,然后以新颖的方式重新组合这些部分,可以与少量的加法组合。减法而不是大量的乘法。

简单来说,与传统算法相比,您分裂的次数越多,乘数就越多。

例如,要计算2531乘以1467,传统算法需要在各个数字之间进行16次相乘:

Karatsuba算法只需要乘以9个数字:

可以看出,用Karatsuba算法,该操作只需要2n加法和减法运算,而传统算法需要N2次。

1971年,德国数学家schonhage和strassen提出了sch?运行时复杂度为n×logn×log(logn)的nhage-strassen算法,与karatsuba的方法相比节省了大约20亿个数字。165万亿步。

<> > >

Arnold Sch?nHage和Volker Strassen

这两位德国数学家还从信号处理领域提出了一种称为快速傅立叶变换的技术。从那时起,这项技术一直是所有快速乘法算法的基础;此外,人们推测应该有一种算法比他们发现的算法更快。复杂度为n×logn的算法(此算法可能是最快的)。

然而,在此之前,计算机大型乘法算法的发展一直陷入僵局,没有取得任何进展。

直到2007年,宾夕法尼亚州立大学数学家马丁费勒提出采用n×logn-fürer算法来打破僵局,没有任何进展。乘法算法在过去十年中得到了改进,无限接近n×logn。

0x252C

马丁费雷尔

好消息是,今年3月,澳大利亚的两位年轻数学家大卫哈维(David Harvey)和乔里斯范德霍文(Joris van der Hoeven)提出了一种新算法。通过使用多个傅立叶变换,使用大量的加法和减法代替乘法运算,证实乘法可以是×log n步完成!

这可能是最快的算法,但不幸的是,尚未证明它是最快的算法。

David Harvey和Joris van der Hoeven

看到发际线,超模知道大数乘法算法还有很长的路要走!

  • 友情链接:
  • 山西新闻网 版权所有© www.monkeyking2008.com 技术支持:山西新闻网| 网站地图