c++ - 快速傅里叶变换

Question

我需要将两个多项式相乘，每个多项式的积分系数都很小。我需要一个 C/C++ 中的快速 FFT 例程，它可以对它们进行卷积。我见过几个库，但它们似乎太大了，分布在多个文件中。重要的是我需要的代码不是太长并且可以很容易地在单个 .c/.cpp 文件中使用和编译。

1. 如果不是小整数，至少应针对实际输入优化 FFT。
2. Radix 4 实现(如果可用)也很好。
3. 编译它应该不需要特殊的编译标志，因为程序的编译必须在我无法控制的外部环境中完成。

非常符合我需求的是 here .但我需要速度加倍的东西。

Answer 1

要获得简单易用的 FFT 实现，请尝试 KissFFT .如果您需要绝对的最大性能，并且不介意有点复杂，那么它必须是 FFTW .