Reasonably fast Fourier transform in a single header for C and C++; grego (2023).
npm install rfft.ccomplex and vector is also provided in rfft.hpp.
sh
$ npm i rfft.c
`
And then include rfft.h or rfft.hpp as follows:
`cxx
// main.c or main.cxx
#define RFFT_IMPLEMENTATION
#include // if using C, or
#include // if using C++
int main() { / ... / }
`
Finally, compile while adding the path node_modules/rfft.c to your compiler's include paths.
`bash
$ gcc -I./node_modules/rfft.c main.c # if using C, or
$ g++ -I./node_modules/rfft.c main.cxx # if using C++
`
You may also use a simpler approach with the cpoach tool, which automatically adds the necessary include paths of all the installed dependencies for your project.
`bash
$ cpoach gcc main.c # if using C, or
$ cpoach g++ 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,