Public domain single header fast Fourier transform for arbitrary array sizes, in about 100 lines of C code, which should be straightforward to understand.
A C++ implementation using the stdlib complex and vector is also provided in rfft.hpp.
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.
Inspired by Project Nayuki, but written in a simpler and arguably more straightforward way.
Public domain.
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4