The Fast Fourier Transform (FFT): Most Ingenious Algorithm Ever?
Reducible7 HN recommenders · 2021–2026
2.3M views · explainer · evergreen · Uploaded 2020-11-14
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.
HN repeatedly calls it a fantastic explanation that made FFT click, with some rewatching it periodically.
19:42But what is the Fourier Transform? A visual introduction.
3Blue1Brown
23:53D/A and A/D | Digital Show and Tell (Monty Montgomery @ xiph.org)
FL Studio
59:34CppCon 2017: Matt Kulukundis “Designing a Fast, Efficient, Cache-friendly Hash Table, Step by Step”
CppCon
1:07:41Modern Dictionaries by Raymond Hettinger
SF Python
1:13:41CppCon 2014: Chandler Carruth "Efficiency with Algorithms, Performance with Data Structures"
CppCon
1:06:00CppCon 2017: Juan Pedro Bolivar Puente “Postmodern immutable data structures”
CppCon
1:29:55Sorting Algorithms: Speed Is Found In The Minds of People - Andrei Alexandrescu - CppCon 2019
CppCon
3:39(1/4) Intro/History: Introducing a 100-year-old mechanical computer
engineerguy
9 comments from Hacker News
Were you watching this video by any chance? [VIDEO] ("The Fast Fourier Transform (FFT): Most Ingenious Algorithm Ever?" by Reducible)
And an FFT explanation by Reducible - [VIDEO] It's in a similar style to 3blue1brown (uses the same visualisation library) but the video focuses specifically on the FFT algorithm, not on Fourier transforms in general. I'm pretty sure Grant himself recommended the Reducible video at some point.
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.
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 coefficients of the polynomial ... in the respective context. If we look at the discrete case, since the operation of convolution is computationally expensive (O(n^3)), people often rely on the Fast Fourier Transform Algorithm (FFT), that runs in O(n log(n)). An excellent and very enjoyable video on the FFT applied to the polynomial multiplication is [VIDEO] .
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]
Related: Fast Fourier Transform (FFT) can be used for polynomial interpolation in O(nlogn) time (if you get to choose the points, and use “complex roots of unity”), where n is the degree of the polynomial, and is used as a step in multiplication of polynomials in O(nlogn) as well. This video covers it well: [VIDEO] Also, chapter 30 of CLRS: [LINK]
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.
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.
For anyone interested and with 30 minutes to spare, I would recommend the youtube video [1] by Reducible for an intuition on how FFT works. [1]: [VIDEO]