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

zeroieme

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


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

.·.·.

thus almost completely settling the complexity of multiplication circuits

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

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

mathe

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

zeroieme

.·.·. 发表于 2019-4-13 08:06
thus almost completely settling the complexity of multiplication circuits

这只是一个下界证明

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

无心人

这是那篇论文

无心人

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

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&#246;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&#246;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

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