数学研发论坛

 找回密码
 欢迎注册
查看: 382|回复: 3

[讨论] “发现完美的乘法”,数学研发论坛不讨论一下?

[复制链接]
发表于 2019-4-12 19:56:37 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
看不懂,只好扔块砖头。
https://arxiv.org/abs/1902.10935
https://www.quantamagazine.org/m ... -multiply-20190411/
https://www.solidot.org/story?sid=60220


我是找大数乘法找到数学研发论坛的。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-4-13 08:06:47 | 显示全部楼层
thus almost completely settling the complexity of multiplication circuits

这只是一个下界证明
具体能不能达到还是两说的
如果想知道上界,你需要参考The best known upper bound, by Fürer

话说,大数乘法,你可以考虑分治算法或者FFT
当然如果你希望算的是梅森素数之类的,对特殊数字取模意义下的大数乘法,或许你应该去梅森素数论坛看看
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-4-13 10:27:04 来自手机 | 显示全部楼层
好像是找到了复杂度为$O(n\log(n))$的乘法算法,还是很厉害的。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2019-4-13 15:33:13 | 显示全部楼层
.·.·. 发表于 2019-4-13 08:06
thus almost completely settling the complexity of multiplication circuits

这只是一个下界证明


这算法达到了O(n log(n)),然后论文作者引用了一个猜想作为定理,不完全地证明了O(n log(n))已经是乘法下界。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2019-7-17 04:16 , Processed in 0.053754 second(s), 16 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表