为什么python使用Karatsuba算法进行乘法？FFT不是更快吗？

html5 • • 问答

使用FFT（快速傅立叶变换）乘法会出现一些问题吗？我好奇。谢谢。

回答

我假设“FFT”是指像Schönhage–Strassen这样的东西。答案很可能是该算法虽然比 Karatsuba 渐进快，但更复杂，并且由于较大的常数因子，只有在非常大的数字上才能实现这一优势（维基百科引用了多个来源，仅当被乘数有数万时才切换到该算法位数）。

以上是为什么python使用Karatsuba算法进行乘法？FFT不是更快吗？的全部内容。
THE END
分享
二维码
< <上一篇
下一篇>>