c++ - Fast Fourier Transform

Question

I need to multiply two polynomials each having small integral coefficients. I need a fast FFT routine in C/C++ which can convolve them. I have seen several libraries but they seem to be too large spread over multiple files. What is important is I need code which is not too long and can be very easily used and compiled in a single .c/.cpp file.

1. FFT should be optimized for real inputs at least if not small integers.
2. Radix 4 implementation if available would be fine too.
3. Compiling it should take no special compilation flags as compilation of program has to be done in external environment which I can't control.

One that very well matches my needs is here. But I need something twice as fast.

Answer 1

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

Answer 2

我已经根据我过去的需求调整了DspDimensionsmbFft上这个示例中的函数。

Answer 3

我收集了一些适合或大部分适合该问题的热门搜索结果（C/C++ FFT），并且我通常将它们从简单到复杂进行组织：

• https://www.sanfoundry.com/cpp-program-compute-dft-coefficients-directly/
• https://www.sanfoundry.com/cpp-program-compute-discrete-fourier-transform-using-fast-fourier-transform-approach/
• https://www.safaribooksonline.com/library/view/c-cookbook/0596007612/ch11s18.html
• https://tfetimes.com/c-fast-fourier-transform/
• http://fftwpp.sourceforge.net/
• http://www.fftw.org/
• https://sourceforge.net/projects/kissfft/
• http://www.drdobbs.com/cpp/a-simple-and-efficient-fft-implementatio/199500857
• https://www.programming-techniques.com/2013/05/calculation-of-discrete-fourier.html
• https://rosettacode.org/wiki/Fast_Fourier_transform#C.2B.2B
• https://github.com/scipr-lab/libfqfft
• http://librow.com/articles/article-10
• http://www.kurims.kyoto-u.ac.jp/~ooura/fft.html

随意添加或更新列表。