The Fastest Fourier Transform In The West

An interesting aspect of time-varying waveforms is that by using a trick called a Fourier Transform (FT), they can be represented as the sum of their underlying frequencies. This mathematical insight is extremely helpful when processing signals digitally, and allows a simpler way to implement frequency-dependent filtration in a digital system. [klafyvel] needed this capability for a project, so started researching the best method that would fit into an Arduino Uno. In an effort to understand exactly what was going on they have significantly improved on the code size, execution time and accuracy of the previous crown-wearer.

A complete real-time Fourier Transform is a resource-heavy operation that needs more than an Arduino Uno can offer, so faster approximations have been developed over the years that exchange absolute precision for speed and size. These are known as Fast Fourier Transforms (FFTs). [klafyvel] set upon diving deep into the mathematics involved, as well as some low-level programming techniques to figure out if the trade-offs offered in the existing solutions had been optimized. The results are impressive.

Fastest FFT code benchmarking results in ms
Benchmarking results showing speed of implementation versus the competition (ApproxFFT)

Not content with producing one new award-winning algorithm, what is documented on the blog is a masterclass in really understanding a problem and there are no less than four algorithms to choose from depending on how you rank the importance of execution speed, accuracy, code size or array size.

Along the way, we are treated to some great diversions into how to approximate floats by their exponents (French text), how to control, program and gather data from an Arduino using Julia, how to massively improve the speed of the code by using trigonometric identities and how to deal with overflows when the variables get too large. There is a lot to digest in here, but the explanations are very clear and peppered with code snippets to make it easier and if you have the time to read through, you’re sure to learn a lot!  The code is on GitHub here.

If you’re interested in FFTs, we’ve seen them before around these parts. Fill your boots with this link of tagged projects.

22 thoughts on “The Fastest Fourier Transform In The West

  1. I’m not sure I understand how Fast Fourier Transform (as in Cooley-Tuckey algorithm) is an approximation or a “real” Fourier transform of a discrete signal… The algorithm gives an exact solution of a discrete Fourier transform, the “fast” comes from the fact that it use O(n log n) operations instead of O(n²) using a clever divide-and-conquer idea.

    Granted, you can indeed speed up the implementation (lowering the prefactor) by using tricks at the cost of precision on top of this (floating point values are never exact to begin with anyway), but the “fast” doesn’t come from there.

  2. The Fast Fourier Transform (FFT) is a specific algorithm for efficiently computing the discrete Fourier transform. FFT is not about the tradeoffs of small microcontrollers and it’s not imprecise, it’s about the asymptotic complexity of the task. The article seems to suggest otherwise.

    1. yes. in fact when i was learning the algorithm i wrote a program that proved the only difference from ft and fft was the removal of redundant math operations that were exactly identical.

  3. All very well, but ArduinoFFT has been around for ages, and according to the graphs in the corner, is getting on for twice as fast again as the fastest of these (6.32ms for a 256-bin transform, and another 1.49ms to window the input, and reorder & reformat the output into linear 8-bit results). It’s here:

    There’s also the Fast Hartley transform, which makes use of a different kernel function – one which allows it to function as its own inverse – and is about twice as fast again. Unsurprisingly its URL is

    1. That’s a really nice like – thanks ‘just passing’ – the links from that site are also gold. I have never implemented an FFT on an MCU and the linked Czech site had the most comprehensive and practical overview I’ve read to date. But also thanks Klafyvel for your contributions.

    1. This actually got me wondering: What’s the cheapest microcontroller with an FPU? Is it one of the squillions of Cortex-M4F chips out there, or one of the ESP32s – or something I’ve not heard of?

  4. The article doesn’t seem to entirely cover it, how well would this perform for doing a real-time FFT on an incoming analogue signal? I’ve seen arduino code putting the AVR’s ADC in free running mode which does a homodyne detection to see if a given frequency of input wave is present, could this be used in a similar way to realtime (averaged over last few ms perhaps) detect which frequencies are present. What would be the fastest frequency it could actually see?

  5. In the comments below the simple POV device article posted earlier this month I mentioned using RF induced noise on the A2D pin as a periodicity detector for syncing the POV scan rate, well this fast FFT code may be very useful for that. N.B. it doesn’t have to be that fast as we can assume that the fan blade the POV device is mounted on is mostly constant, except when switched between speed levels so the interval between timing checks can be fairly long, it just helps if these interruptions are as short as possible.

  6. Just for giggles, let’s say I had an audio signal that I arbitrarily wanted to purge the third most significant harmonic from. Would any of these FFT implementations allow me to sense the top x harmonics, and select a filter that would feedback a portion of the signal that had been filtered to the frequency of that harmonic, so that it disappeared from the output waveform? Maybe I wanted to Add a filtered out copy of the 4th harmonic, or something like that. The analog filter could be an single Op-amp band pass filter where analog switches were used to switch in/out capacitors of an RC pair in the feedback path of the op-amp circuit.

Leave a Reply

Please be kind and respectful to help make the comments section excellent. (Comment Policy)

This site uses Akismet to reduce spam. Learn how your comment data is processed.