数学研发论坛

 找回密码
 欢迎注册
查看: 862|回复: 6

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

[复制链接]
发表于 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))已经是乘法下界。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-9-27 11:39:49 | 显示全部楼层
这是那篇论文

even fast integer multiplication.pdf

479.64 KB, 下载次数: 5, 下载积分: 金币 -1 枚, 经验 1 点, 下载 1 次

评分

参与人数 1威望 +4 金币 +4 贡献 +4 经验 +4 鲜花 +4 收起 理由
zeroieme + 4 + 4 + 4 + 4 + 4 赞一个!

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-9-27 11:45:53 | 显示全部楼层
这是乘法的各种算法的时间复杂度
DateAuthors Time complexity
<3000 BCUnknown O(\(n^2\))
1962KaratsubaO(\( n^{\log 3/ \log 2} \))
1963Toom O(\( n 2^{5\sqrt{\log n/\log 2}} \)  )
1966 Schönhage O( \(n 2^{\sqrt{2\log n/log 2 }}(\log n)^{3/2} \))
1969Knuth O(\(n 2^{\sqrt{2\log n/\log 2 }}(\log n) \))
1971 SchönhageStrassen O( \(n \log n \log\log n\))
2007Fürer O( \( \log n 2^{O(\log^* n)} \))
2014Harvey, van der Hoeven   O( \(n \log n 8^{\log^* n}\))

  
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-10-8 09:48:26 | 显示全部楼层
复杂度应该是达到了完美的O(n log(n)) , 不过这种算法现在才发现,  应该 比例常数不小吧.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2019-10-22 23:54 , Processed in 0.058320 second(s), 20 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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