rfft.h

Public domain single header fast Fourier transform for arbitrary array sizes, in about 100 lines of C code, which should be straightforward to understand. By Grego.

A C++ implementation using the stdlib complex and vector is also provided in rfft.hpp.

Installation

Run:

$ npm i rfft.c

And then include rfft.h or rfft.hpp as follows:

// main.c or main.cxx
#define RFFT_IMPLEMENTATION
#include "node_modules/rfft.c/rfft.h"   // if using C, or
#include "node_modules/rfft.c/rfft.hpp" // if using C++

int main() { /* ... */ }

And then compile with gcc or g++ as usual.

$ gcc main.c    # if using C, or
$ g++ main.cxx  # if using C++

You may also use a simpler approach:

// main.c or main.cxx
#define RFFT_IMPLEMENTATION
#include <rfft.h>   // if using C, or
#include <rfft.hpp> // if using C++

int main() { /* ... */ }

If you add the path node_modules/rfft.c to your compiler's include paths.

$ gcc -I./node_modules/rfft.c main.c    # if using C, or
$ g++ -I./node_modules/rfft.c main.cxx  # if using C++

Algorithms

The classic Cooley-Turkey algorithm is used in place (without additional allocations) for arrays of size 2^k.

For more more general ones, Bluestein algorithm is used. It utilizes the binomial identity 2nk = n^2 + k^2 - (k - n)^2 to express the Fourier transform as a convolution of two sequences, which can be computed using the algorith for the power of 2 sizes. It needs to allocate two auxillary array of size at most 4n + 3.

The runnig time is always O(n log(n)). However, if the speed is crucial, more optimized libraries like FFTW are recommended.

Inspiration

Inspired by Project Nayuki, but written in a simpler and arguably more straightforward way.

License

Public domain.