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

/相 · 发表于 2023-10-2 16:42:33

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

我是找大数乘法找到数学研发论坛的。

ojaupobcisi · 发表于 2023-10-2 16:42:45

thus almost completely settling the complexity of multiplication circuits

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

话说，大数乘法，你可以考虑分治算法或者FFT
当然如果你希望算的是梅森素数之类的，对特殊数字取模意义下的大数乘法，或许你应该去梅森素数论坛看看

edzugxoggixo · 发表于 2023-10-2 16:43:28

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

Zpasarbola · 发表于 2023-10-2 16:44:23

这算法达到了O(n log(n))，然后论文作者引用了一个猜想作为定理，不完全地证明了O(n log(n))已经是乘法下界。

evuojad · 发表于 2023-10-2 16:44:31

这是那篇论文

ozjazit · 发表于 2023-10-2 16:45:24

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

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}$)

iciugun · 发表于 2023-10-2 16:46:17

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

		自动登录	找回密码
密码			立即注册