Geek Answers Handbook

Fast Fourier Transform

I need to multiply two polynomials, each of which has small integral coefficients. I need a fast FFT procedure in C / C ++ that can fold with them. I saw several libraries, but they seem to be too common across multiple files. The important thing is that I need code that is not too long and can be very easily used and compiled in a single .c/.cpp file.

  • FFT should be optimized for real inputs, at least if not small integers.
  • The Radix 4 implementation, if available, will also be great.
  • Compilation does not require special compilation flags, since compilation of the program must be performed in an external environment that I cannot control.

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

+8
c ++ c fft signal-processing dft
source share
2 answers

For a simple and easy to use FFT implementation, try KissFFT . If you need absolute maximum performance, although not against a little complexity, then it should be FFTW .

+12
source share

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

+2
source share

More articles:


All Articles