烧仙草,清水河,管理-大蓝社区,共创新环境,争做时代绿化先锋

admin 4个月前 ( 06-23 03:15 ) 0条评论
摘要: 长乘法还真是一种漫长的算法呢.图片来源:David Harvey翻译丨杨莉昕审校丨戚译引来源丨科研圈(ID:keyanquan)两个数相乘很简......


长乘法还真是一种绵长的算法呢。图片来历:David Harvey


翻译丨杨莉昕

审校丨戚译引

来历丨科研圈(ID:keyanquan)


两个数相乘很简略,对吧?咱们在小学就会学习长乘法,就像题图这样草莓数码。相似的办法可以追溯到几千年前,至少到古苏美尔人和古埃及人年代。但这真的是求两个大数的乘积的最好办法吗?


在长乘法中,咱们有必要用榜首个数的每一位与第二个数的每一位相乘。假如两个数均有 N 位,一共就古龙之陨是 N相乘。在上面的比方中,N 为 3, 咱们有必要做 32 = 9 次乘法运算。


约 1956 年,闻名苏联数学家 Andrey Kolmogorov 猜测这便是两数相乘的烧仙草,清水河,办理-大蓝社区,共立异环境,争做年代美化前锋最佳办法。 换句话说,不管你怎么组织,运算的工作量至少是 N量级。位数翻倍意味着工作量增至四倍。


Kolmogorov 以为,如tv9815果简洁办法或许存在的话,必定早就被发现了。究竟几千年来人们一直在核算乘积。这是“诉诸无知”逻辑谬论的极好的比方京欣二号。(诉诸无知:假如一个假定没有被证明是假/真的,那么这个假定是真/袁东操影视论坛假的。)



更快的算法?

没过几年,Kolmogorqwqshowov 的猜测就被证明tvs4在线直播是大错特错。

1960 年,23 岁的俄罗斯数学系学生 Anatoly Karatsuba 发现了一种代数技巧,可以削减需求相乘的次数。例如,运用 Karatsuba 的办法,将两个四位数相乘只用做 9 次乘法,而不是 42 = 16 次。他的办法在位数翻倍时工作量只增至三倍,与传统办法比较,在数字更大时展示了巨大的优势。关于 1000 位的数字,Karatsuba 的办法需求的乘法运算次数只要长乘法的大约 17 烧仙草,清水河,办理-大蓝社区,共立异环境,争做年代美化前锋分之一。


但究竟为河州平弦什么要把这么大的数字相乘呢?事实上,这样的乘法有许多相谌天舒关运用。最显着而且最具经济效益的一个运用方向便是密码学。



实践中的大数字


每次你在网络上运用加密沟通时,比方登录银行网站或进行网络查找的时分,你的设备会履行许多乘法,其间触及上百位乃至上千位的数字。在这个过程中,你的设备很或许就运用了 Karatsuba烧仙草,清水河,办理-大蓝社区,共立异环境,争做年代美化前锋 的技巧。这都是软件生态系统的一部分,能让使咱们的网页赶快加载出来。


在一些保密等级更高的运用中,数学家还有必要应对更巨大的数字,位数到达上百万、十亿乃至万亿。关于这样的数字,乃至连 Karatsuba 的算法都太慢了。


1971 年,德国数学家 Arn吴亚飞少将old Schnhage 和 mide020Volker Strassen 带来了一个真实的打破。他们解说了怎么运用其时邃古雷帝诀刚刚宣布的快速傅里叶变换(fast Fourier transform,FFT)高效地将巨大数字相乘。现在,他们的办法已被数学家常常运用来处理数十亿位的数字。


FFT 是 20 世纪最重要的算法之一烧仙草,清水河,办理-大蓝社区,共立异环境,争做年代美化前锋。它在日常日子中最常见的运用便是数字音频:每逢你听 MP3、音乐流媒体或数字电台时,在台后进行音频解码的正是 FFT。


还能再快一点吗?

在 1971 年的论文中,纤诗婷内衣 Schnhage 和 Strassen 也提出了一个有目共睹的我超勇的猜测。为了解说它,我得先讲一点学术常识。

们的猜测的前半部分是:有或许经过最多 Nlog (N)(即 N 的自然对数的 N烧仙草,清水河,办理-大蓝社区,共立异环境,争做年代美化前锋 倍)次量级的根本运算来将 N 位数相乘。他们自己的算法并未彻底完成这个方针,它所需的运算次数是理论最小值的 log (log N)(N 对数的对数)倍。但是,直觉让他们置疑漏掉了什么东西,Nlog (N) 应该是可行的。


自 1971 年起的几十年来,一些研讨者现已对 Schnhage 和 Strassen 的算法进行了改善。尤其是 Martin Frer,他在 2007 年规划的一种算法现已极端挨近难以到达的 Nlog (N) 量级。


他们猜测的第二部分,也是更为困难的部分是:Nlog (N) 应该是根本的运算速度极限。也便是说,不或许有乘法算法能完成比这更少的运算次数。



咱们谭启贤到达极限了吗?

几周前,Joris van der Hoeven 和我宣布了一篇研讨论文(论文链接),描绘了一种新的乘法算法,总算触及了 N log (N) 这个“圣杯”,处理了 Schnhage–Strassen 猜测中“简略”的部分。

这篇文章还未经过同行评定,所以需求慎重看待。在数学界,研讨成果常常在阅历同行评定之前就被传达开来。


咱们烧仙草,清水河,办理-大蓝社区,共立异环境,争做年代美化前锋的算法没有选用一维 FFT 办法(自 1971 年起关于这一问题的一切研讨工作都依托这种办法),而是运用了多维 FFT 办法。这办法自身并不新,广泛运用的 JPEG 图片格式就依托二维 FFT 办法,三维FFT办法在物理和工程中也有许多运用。


在咱们的论文中,咱们运用了 1729 维的 FFT 办法。这很难幻想,但在数烧仙草,清水河,办理-大蓝社区,共立异环境,争做年代美化前锋学上并不比二维状况费事。

这项新算法现在还很难得到实践运用,由于咱们文章中的证明只适用于大得出奇的数字。即便把每一位数字都写在一个氢原子上,可观测的世界中也几乎没有满足的空间写下它们。

另一方面,hallite密封件咱们期望经过进一步的改善,能让算法适用于只要数十亿或万亿位的数字。假如导游陈严能完成这个方针,它将很或许成为核算数学家的工具包中必不行少的配备。


假如土灰蛇 Schnhage–Strassen赵春城苏媚 猜测彻底正确,那么理论上,这项新算法已到了路的止境,不或许做得更好了。


就我个人而言,假如猜测最终是过错的,那么我也会十分惊奇。但咱们不该忘掉发生在 Kolmogorov 身上的工作。数学有时会给人带来惊喜。


该文作者为新算法发明人之一David Harvey


扩展阅览:

关于新算法的原理,请阅览人类用四千年碰到乘法运算天花板:史上最快乘法诞生

本文转载自大众号“科研圈”(ID:keyanquan)

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

点击图片或点“阅览原文”当即购买

文章版权及转载声明:

作者:admin本文地址:http://grand-blue.com/articles/1910.html发布于 4个月前 ( 06-23 03:15 )
文章转载或复制请以超链接形式并注明出处大蓝社区,共创新环境,争做时代绿化先锋