C++ 快速傅立叶变换
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/5255474/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Fast Fourier Transform
提问by Nikhil Garg
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/.cppfile.
我需要将两个多项式相乘，每个多项式的积分系数都很小。我需要一个可以对它们进行卷积的 C/C++ 中的快速 FFT 例程。我见过几个库，但它们似乎太大，分布在多个文件中。重要的是我需要的代码不会太长，并且可以很容易地在单个.c/.cpp文件中使用和编译。
- FFT should be optimized for real inputs at least if not small integers.
- Radix 4 implementation if available would be fine too.
- Compiling it should take no special compilation flags as compilation of program has to be done in external environment which I can't control.
- FFT 至少应该针对实际输入进行优化，如果不是小整数的话。
- 如果可用，Radix 4 实现也可以。
- 编译它应该不需要特殊的编译标志，因为程序的编译必须在我无法控制的外部环境中完成。
One that very well matches my needs is here. But I need something twice as fast.
非常符合我的需求的一款就在这里。但我需要两倍的速度。
回答by Paul R
回答by LnxPrgr3
I've adapted the smbFftfunction from this example on DspDimensionto my needs in the past.
过去，我已经根据我的需要调整了DspDimension上smbFft此示例中的函数。
回答by Andrew
I've collected some of my top search results that fit or mostly fit the question (C/C++ FFT), and I've generally organized them from simple to complex:
我收集了一些适合或大部分适合问题（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
- 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
Feel free to add to or update the list.
随意添加或更新列表。
