“The Fast Fourier Transform (FFT) is an efficient algorithm to compute the discrete Fourier transform of a signal. If you search for algorithm implementations, you will find this great Instructable. However, while it provides an effective way to implement the FFT, it is possible to be even more efficient while keeping a high precision. In the present Instructable, I propose to re-use the implementation I made in Julia here (English version available here on my blog) to beat ApproxFFT. Let’s dig in!
What Is the Main Difference With ApproxFFT ?
ApproxFFT uses a central trick to calculate the FFT: it approximates the sines and cosines needed for calculation using a lookup table. On the contrary, the code provided in this instructable will calculate an FFT with close to zero approximation using a trigonometric identity.
Another issue with ApproxFFT is that it does not perform the calculation in place! Indeed, take a look at lines 66 and 67 in the original file. You’ll notice two array allocations that triple the program’s memory footprint and prevent using arrays bigger than 256 cells on my Arduino Uno!
In this Instructable, I will provide two new implementations of the FFT on Arduino. One will use the float type, thanks to some floating point arithmetic tricks (described in this blog post - in french, sorry). The second and third will use fixed point arithmetic, and the type used for storage will be int, just as in the original Instructable. However, the calculations will be made faster thanks to the trigonometry identity, a handcrafted saturating addition routine and a fixed point multiplication based on the fmuls instruction provided by the AVR assembler.”