algorithm - 了解 Schönhage-Strassen 算法（大整数乘法）

Question

我需要在 Python 中尽可能高效地乘以几个 1000 位数的长整数。这些数字是从文件中读取的。

我正在尝试实现整数乘法的Schönhage-Strassen算法，但我坚持理解它背后的定义和数学，特别是快速傅立叶变换。

任何理解这个算法的帮助，比如一个实际的例子或一些伪代码，将不胜感激。

Answer 1

Knuth 的TAOCP的第 4.3.3 章对其进行了描述，并且在其他章节中也有一些 FFT 伪代码可用于此目的。

Answer 2

1000 位数字对于 Schönhage-Strassen 来说是“小”，真正值得使用。你可以看看Tom Cook乘法。 gmpy是提供这些功能的 gmp 的 Python 包装器。

Answer 3

不要重新发明轮子。GMP 对该算法有出色的高性能实现，任何用纯 Python 编写的算法都会慢至少 100 倍，这仅仅是因为 Python 是一种解释性语言。使用gmpy从 Python 应用程序调用 GMP。我也很好奇你正在开发的应用程序需要乘以这么大的数字 - 可能有一种更简单的方法来处理你的问题。

此外，正如其他答案所提到的，“几个 1000 位数字长”还不足以证明 Schönhage-Strassen 的合理性（您必须至少有 10000 个十进制数字，可能更多）。一些Toom-Cook 的变体，如Toom-3，通常用于此范围。再说一遍，不要自己用 Python 编写——GMP 的实现经过了非常仔细的优化。