Tib*_*ass 2 algorithm performance biginteger multiplication modular
来自维基百科:
"Anindya De,Chandan Saha,Piyush Kurur和Ramprasad Saptharishi [11]在2008年使用模运算实现了相似的算法,实现了相同的运行时间.但是,后者的算法仅比Schönhage-Strassen更快,因为不实际的大输入."
我会对这种不切实际的大整数的大小非常感兴趣.
也许有人确实以某种方式实现了两种算法并且可以做一些基准测试？
谢谢
富勒的算法及其模块化等价物(DSKS)是非常深入的研究课题,目前仅作为学术兴趣.实际上没有人知道交叉点有多大.并且在所有可能性中它都无关紧要,因为交叉点可能远远超出64位计算限制.
我以前实施过Schönhage-Strassen,我理解Fürer的算法是如何工作的.所以我对他们两个都很熟悉.我可以说,Schönhage-Strassen和Fürer算法之间的交叉点很可能是如此之高,以至于能够保持参数的计算机将大于可观察宇宙的大小.
当你的复杂性相差小于对数时,这就是问题所在.它需要指数级大的输入大小才能补偿Big-O常数的微小差异.
在这种情况下,已知富勒的算法具有非常非常大的Big-O常数.