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

Closed. This question does not meet Stack Overflow guidelines. It is not currently accepting answers.

---

Questions asking us to recommend or find a book, tool, software library, tutorial or other off-site resource are off-topic for Stack Overflow as they tend to attract opinionated answers and spam. Instead, describe the problem and what has been done so far to solve it.

Closed 8 years ago.

Improve this question

I'm trying to find the fundamental freq开发者_如何学Cuency of a recorded sound using FFT in C. Would anyone know a open source implementation in C that I can modify and use?

Thanks!

---

FFTW is probably what you are looking for.

---

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

---

Another worth considering is D.J. Bernstein's. It's somewhat on the complex side (as is FFTW) but faster than most (including FFTW) in most tests.

---

You will find here a C/C++ implementation, with a description of the source code (tutorial): http://drdobbs.com/cpp/199500857

---

An implementation using optimized bit-shifts can be found at XFT library of algorithms. It is worth a look for more than just Fourier transforms.