The Fast Fourier Transform (FFT): Most Ingenious Algorithm Ever?

Channel:Reducible · Length:28:23 · Published:2020-11-14 · Views:2296182

Watch on YouTube

Summary

Reducible's visual walkthrough of the Fast Fourier Transform, motivated by polynomial multiplication. It shows how the FFT's key ideas can be discovered by asking the right questions.

Why HN recommends it

HN repeatedly calls it a fantastic explanation that made FFT click, with some rewatching it periodically.

It derives the FFT algorithm from polynomial multiplication and it’s fantastic . I rewatch it every 6 months or so. — HN, 2024

Algorithms & data structures · Information theory & signal processing

Subtitles (excerpt)

the world of algorithms is vast but we can often split them into two distinct classes the first class is those that are inherently useful think of your standard graph algorithms like dfs or bfs these algorithms show up all over the place they are efficient and as a result we like to understand them the second class of algorithms we study are ones that are just purely beautiful think of the first time you saw the incredibly simple recursive implementation of towers of annoy if you have a soul you feel a sense of wonder a sense of awe at the elegance of such an algorithm it happens to not actually be that useful or efficient as a matter of fact but we still study it just as we like to read a work of fiction it inspires us and motivates out-of-the-box thinking today i want to talk about an algorithm that rightfully belongs in both classes and my personal favorite algorithm the fast fourier transform the fast fourier transform or fft is without exaggeration one of the most important algorithms created in the last century so much of the modern technology that we have today such as wireless communication gps and in fact anything related to the vast field of signal processing relies on the insights of the fft but it's

On Hacker News

I almost always prefer text over video, but this video on the same subject is fantastic: [VIDEO] . I watch it at least once every year. Also, the title of the blog post (and by extension this HN post) is IMO not really correct: it's not about the DFT but specifically about the FFT. — tverbeure, 2025-10
If you haven’t seen it yet, you should watch this video: [VIDEO] It derives the FFT algorithm from polynomial multiplication and it’s fantastic . I rewatch it every 6 months or so. — tverbeure, 2024-07
That video did the same for me. I also like the reducible video for Fast Fourier Transforms as well as the Veratasium piece that shares some fun history. Reducible - FFTs the most ingenious algorithm ever [VIDEO] Veritasium - The Most Important Algorithm of All Time [LINK] — kippinitreal, 2023-01
As the author mentions, convolutions for signal processing and convolutions for probability are essentially equivalent things in two different contexts. It is interesting that the same concept is behind the multiplication of polynomials. In the discrete case we have the parallel of the vectors representing ... the (discretized) probability density <-> the (discrete) signal intensity <-> the coeff… — squaredot, 2022-12
Not a book, but I truly enjoy this guy’s videos: [VIDEO] . I usually watch them while eating lunch. He does a truly fantastic job. — withinboredom, 2021-11

Related videos