“发现完美的乘法”，数学研发论坛不讨论一下？

zeroieme · 发表于 2019-4-12 19:56:37

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

您需要登录才可以下载或查看，没有账号？欢迎注册

×

看不懂，只好扔块砖头。
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
当然如果你希望算的是梅森素数之类的，对特殊数字取模意义下的大数乘法，或许你应该去梅森素数论坛看看

mathe · 发表于 2019-4-13 10:27:04

好像是找到了复杂度为$O(n\log(n))$的乘法算法，还是很厉害的。

zeroieme · 发表于 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

这是那篇论文

无心人 · 发表于 2019-9-27 11:45:53

这是乘法的各种算法的时间复杂度

Date	Authors	Time complexity
<3000 BC	Unknown	O($n^2$)
1962	Karatsuba	O($ n^{\log 3/ \log 2} $)
1963	Toom	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} $)
1969	Knuth	O($n 2^{\sqrt{2\log n/\log 2 }}(\log n) $)
1971	SchönhageStrassen	O( $n \log n \log\log n$)
2007	Fürer	O( $ \log n 2^{O(\log^* n)} $)
2014	Harvey, van der Hoeven	O( $n \log n 8^{\log^* n}$)

wayne · 发表于 2019-10-8 09:48:26

复杂度应该是达到了完美的O(n log(n)) , 不过这种算法现在才发现, 应该比例常数不小吧.

账号		自动登录	找回密码
密码			欢迎注册

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

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

评分