Frame from The Fast Fourier Transform (FFT): Most Ingenious Algorithm Ever? Plays with YouTube's privacy-enhanced embed

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

Reducible Explainers intermediate
Open on YouTube First HN thread

7 HN users recommended this explainer in 8 different months between 2021 and 2026.

2007–2026
5 strong recommendations 3 recommendations 1 citation HackerTube score 10.5

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

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.

Pull quote: “It derives the FFT algorithm from polynomial multiplication and it’s fantastic . I rewatch it every 6 months or so.” (HN, 2024)

Also tagged: fast fourier transform, fft, polynomial multiplication, algorithms, convolution, signal processing

What Hacker News said

9 labeled comments from the HN archive; up to 20 are kept per video, favoring different commenters. Each one links back to the original thread.

Strongly recommends squaredot December 2022 under Understanding Convolutions in Probability: A Mad-Science Perspective
FFT applied to polynomial multiplication
Read the full comment
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 [this video] .
View on Hacker News
Strongly recommends tverbeure October 2025 under Discrete Fourier Transform
Fantastic FFT explanation
I almost always prefer text over video, but this video on the same subject is fantastic: [this 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.
View on Hacker News
Recommends jstx1 October 2021 under A gentle introduction to the FFT (2002)
FFT explainer in 3blue1brown style, focused on the algorithm
And an FFT explanation by Reducible - [this 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.
View on Hacker News
Recommends foooobaba February 2023 under Polynomial Interpolation
Covers FFT for polynomial interpolation and multiplication
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: [this video] Also, chapter 30 of CLRS: [link]
View on Hacker News
Recommends medbar April 2026 under Understanding the FFT Algorithm (2013)
Intuition for how FFT works in 30 minutes
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]: [this video]
View on Hacker News

Citations, criticism and jokes

Keyboard shortcuts

/
Search
j k
Next / previous video in a list
Enter
Open the focused video
l
Like (on a video page)
w
Watch later (on a video page)
?
This help
Esc
Close