Any implementation of fast open source Fourier transform?

I am trying to find the main frequency of the recorded sound using FFT in C. Does anyone know an open source implementation in C that I can change and use?

Thanks!

+4
source share
5 answers

FFTW is probably what you are looking for.

+5
source

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

+1
source

Another noteworthy question is DJ Bernstein. This is a bit of a tricky part (like FFTW), but faster than most (including FFTW) in most tests.

+1
source

I found Ooura C fft packages for practical purposes above FFTW. Using FFTW optimally requires time and patience for the FFTW wisdom system to work properly, especially with cross-compilation. In addition, FFTW has a GPL viral license for it, so you cannot use it in closed source projects without paying them a ton of money.

Unlike FFTW, Ooura code has a very permissive license; In addition, Ooura does not depend on a complex build environment. Besides FFTW, Ooura Code is either the fastest or almost the fastest FFT cross-platform library. It runs about twice as fast as the KISS FFT Library, which remains popular for some inexplicable reason. Ooura code takes into account two-level CPU caching, which works well with most modern processors.

If you really feel the need for speed, then you should skip FFTW and Ooura and go straight to your processor for your custom FFT libraries. Processor-specific vendors tend to be the fastest in the lag. Some examples include Intel MKL and clFFT .

Also, if you are trying to find the main frequencies, don't forget about the good old-fashioned autocorrelation. If it works well enough for you, it can be significantly faster than starting an FFT. Check out the classic Rabiner paper for a review.

Someone said that they need a FFT library that works with both single precision and double precision floating point. He will not win a single affection, but armadillo can do it. If you decide to use floats with the same precision for calculating FFT, BE FULLY SURE that you measured and quantified the number of errors in the results. FFT is a huge bunch of multiplications, and rounding errors can quickly aggregate VERY fast using FFT with one precision. You may get results that look good but are wrong. Consider yourself warned ...

+1
source

An implementation using optimized bit shifts can be found in the XFT algorithm library . This deserves more than just the Fourier transform.

0
source

All Articles