Fast Fourier Transform

c++ c signal-processing fft dft
Nikhil Garg picture Nikhil Garg · Mar 10, 2011 · Viewed 30.5k times · Source

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

Paul R picture Paul R · Mar 10, 2011

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.

Related questions

Data Compression Algorithms

I was wondering if anyone has a list of data compression algorithms. I know basically nothing about data compression and I was hoping to learn more about different algorithms and see which ones are the newest and have yet to …

Read More
C/C++ library for reading MIDI signals from a USB MIDI device

I want to write C/C++ programs that take input from a MIDI device. The MIDI device connects to my PC using a USB connector. I'm looking for a (C/C++ implemented) library that I can use to read the …

Read More
Looking for a good C/C++ wavelet library for signal processing

Does anyone know of a good C/C++ wavelet library for signal processing? The signal is float or double valued, not int valued.

Read More