To get somewhat decent O(nlogn) performance we can use a divide & conquer algorithm leaning on the formula's periodicity. As my primary source, https://lcamtuf.substack.com/p/not-so-fast-mr-fourier, quips: It literally goes around in circles!
We divide the sampled input by even & odd indices, recursing into both halves until we get a single sample to return directly.
We merge the results by pairing up even & odd results, calculating even ± odd*e^iτk/N for N samples at kth index.
3/4!
You can conceive as the Fourier Transform as winding the signal around a circle, & seeing how off-balance it gets for different numbers of windings. 3Blue1Brown has a good visualization: https://www.youtube.com/watch?v=spUNpyF58BY
Unfortunately (as Sebastian Lague saw, https://www.youtube.com/watch?v=iA6wRgwl7k0 ) simply iterating over all samples & frequencies is slow on even a modern PC, let alone something we want to run realtime below 5V2A. Taking O(n^2) time.
So how do we make the Fourier Transform fast?
2/4?
To get somewhat decent O(nlogn) performance we can use a divide & conquer algorithm leaning on the formula's periodicity. As my primary source, https://lcamtuf.substack.com/p/not-so-fast-mr-fourier, quips: It literally goes around in circles!
We divide the sampled input by even & odd indices, recursing into both halves until we get a single sample to return directly.
We merge the results by pairing up even & odd results, calculating even ± odd*e^iτk/N for N samples at kth index.
3/4!
A catch here is that the recursive algorithm retrieves the array's entries in random order, whereas I've already suggested that I want our DSP to read its data in sequence. Besides it'd be easier to write firmware without recursion!
So to turn this into an iterative algorithm we can rephrase the divide step into reversing the bits of the indices (I've stated that out-of-order is fine). Then for each power-of-2 we can iterate over the unmerged chunks of that array, merging them as normal.
4/4.5
A drawback of this Cooley-Tukey FFT algorithm I described is that it requires the quantity of input to be a power-of-2. Since I reckon most callers can contrive this to be the case, I won't dig into the complexity of handling non power-of-2 quantities.
4.5/4.5 Fin for today! Tomorrow: Complex numbers!
