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

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

看不懂，只好扔块砖头。
https://arxiv.org/abs/1902.10935
https://www.quantamagazine.org/mathematicians-discover-the-perfect-way-to-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

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

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

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

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

页: [1]

数学研发论坛's Archiver

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