Worth checking out. Quoting the FFTW Home Page:

FFTW is a C subroutine library for computing the discrete Fourier transform (DFT) in one or more dimensions, of arbitrary input size, and of both real and complex data (as well as of even/odd data, i.e. the discrete cosine/sine transforms or DCT/DST). We believe that FFTW, which is free software, should become the FFT library of choice for most applications.

Now, can it work when you have less than 16KB available RAM?

### Like this:

Like Loading...

*Related*

A couple of thoughts:

1. I took a look at their comparisons to older methods, as I recall it only starts to be faster with very large N, in the range of 1 million or larger.

2. I’d guess from (1) that it’s not particularly amenable to 16 KB of RAM, though not sure about that.

3. It’s not “free” if you want to use it commercially, and other methods are less encumbered by licensing. With FFTW, you have to negotiate with MIT to get a license.

Thanks for sharing your thoughts. Do you know any other FFT libraries that can be easily embedded on a low memory device like an Arduino?

Try Numerical Recipes in C (or C++, I can’t remember). They have several versions, including one for single-dimensional signals like audio, and that as I recall is fairly small. Their license allows free use, as long as you don’t expose the routine’s access externally to a user, for general use. Their book is well worth it for the documentation, and they’ve been around for a long time so their routines are well-debugged. A web search will turn up other approaches.

Ray

Thanks for sharing. Numerical Recipes in C is very interesting and chapter 12 is fully dedicated to FFT.