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.

Calycle

What's your question? I need a million dollars. Also, I like cheese. A LOT. – Ortegal

@muntoo - Real polynomial convolution is an important problem in itself and hence I think its natural to ask this question. I don't need full power of FFT but just a specific small subset and the fact that there IS an OS implementation almost suiting my needs, means that it is not unrealistic either. – Calycle

How large are the polynomials? FFT has better complexity than direct convolution, but also a significantly higher constant, for small problems direct convolution would be faster. – Chandrachandragupta

Pretty large. Degree is around 10^6. I am sure an O(N^2) algorithm won't run in any reasonable time. – Calycle

Answer 1

For a straightforward and easy to use FFT implementation try KissFFT. If you need absolute maximum performance though, and don't mind a little complexity, then it has to be FFTW.

Alcazar

Answer 2

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:

• 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.

Welby

Answer 3

I've adapted the smbFft function from this example on DspDimension to my needs in the past.

Whitmore