performance - “Fast Integer Multiplication Using Modular Arithmetic”（2008）算法何时比 Schönhage-Strassen 算法更快？

Question

来自维基百科：

“Anindya De、Chandan Saha、Piyush Kurur 和 Ramprasad Saptharishi [11] 在 2008 年使用模运算给出了类似的算法，实现了相同的运行时间。但是，对于不切实际的大输入，后一种算法仅比 Schönhage-Strassen 快。”

我会对这种不切实际的大整数的大小非常感兴趣。

也许有人确实以某种方式实现了这两种算法并且可以做一些基准测试？

谢谢

Answer 1

Fürer 的算法及其等效模块 (DSKS) 是非常深入的研究课题，目前仅作为学术兴趣。没有人真正知道交叉点有多大。而且很可能这无关紧要，因为该交叉点可能远远超出 64 位计算限制。

我之前实现过 Schönhage-Strassen，并且了解 Fürer 算法的工作原理。所以我对他们两个都很熟悉。我可以说 Schönhage-Strassen 和 Fürer 算法之间的交叉点非常高，以至于能够保存参数的计算机将大于可观测宇宙的大小。

当您的复杂性相差小于对数时，这就是问题所在。即使是 Big-O 常数的微小差异，也需要指数级的大输入大小来补偿。

在这种情况下，已知 Fürer 算法具有非常非常大的 Big-O 常数。