Any Open Source Fast Fourier Transform C implementation? [closed]

Question

I'm trying to find the fundamental frequency of a recorded sound using FFT in C. Would anyone know a open source implementation in C that I can modify and use?

Thanks!

Answer 1

I've found Ooura's C fft packages to be superior to FFTW's for practical purposes. Using FFTW optimally takes time and patience to get FFTW's wisdom system working correctly, especially when cross-compiling. Additionally, FFTW has that viral GPL license attached to it, so you can't use it in closed-source projects without paying them a bunch of money.

Unlike FFTW, Ooura's code has a very permissive license; additionally, Ooura's work doesn't depend on a complex build environment. Other than FFTW, Ooura's code is either the fastest, or nearly the fastest, cross-platform FFT library. It runs about twice as fast as the KISS FFT library, which remains popular for some inexplicable reason. Ooura's code takes two-level CPU caches into account, which works well with most modern processors.

If you truly feel the need for speed, then you should skip FFTW and Ooura and go direct to your CPU manufacturer for their custom FFT libraries. Vendor-supplied, CPU specific libraries tend to be the fastest in a footrace. Some examples include Intel MKL and clFFT.

Also, if you're trying to find fundamental frequencies, don't forget about good old fashioned autocorrelation. If it works well enough for you it may be significantly faster than running an FFT. Check out the classic Rabiner paper for an overview.

Someone said they needed an FFT library that works with single-precision as well as double-precision floats. Armadillo can do this. If you decide to use single-precision floats to calculate FFTs, BE COMPLETELY SURE that you have measured and quantified the amount of error in the results. FFTs are a huge pile of multiplies, and roundoff errors can aggregate VERY quickly indeed with a single-precision FFT. You can get results that look good but are wrong. Consider yourself warned...

Answer 2

FFTW is probably what you are looking for.