The Fast Fourier Transform (FFT): Most Ingenious Algorithm Ever?
Channel:Reducible · Length:28:23 · Published:2020-11-14 · Views:2296182
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
- The Marvel Symphonic Universe · Every Frame a Painting · 13:35
- Can YOU Fix Climate Change? · Kurzgesagt – In a Nutshell · 15:49
- But what is the Riemann zeta function? Visualizing analytic continuation · 3Blue1Brown · 20:28
- But how does bitcoin actually work? · 3Blue1Brown · 25:15
- Darts in Higher Dimensions (with 3blue1brown) - Numberphile · Numberphile · 32:11
- Saving Voyager 1! - Bruce Waggoner at !!Con 2024 · !!Con · 35:25
- HC2023-K2: Hardware for Deep Learning · hotchipsvideos · 1:05:27
- The Most Underrated Algorithm · Veritasium · 26:33
- Unix and Google · FOAM · 7:15
- But what is the Fourier Transform? A visual introduction. · 3Blue1Brown · 19:41
- D/A and A/D | Digital Show and Tell (Monty Montgomery @ xiph.org) · FL Studio · 23:52
- CppCon 2017: Matt Kulukundis “Designing a Fast, Efficient, Cache-friendly Hash Table, Step by Step” · CppCon · 59:33
- Modern Dictionaries by Raymond Hettinger · SF Python · 1:07:41
- CppCon 2014: Chandler Carruth "Efficiency with Algorithms, Performance with Data Structures" · CppCon · 1:13:41
- CppCon 2017: Juan Pedro Bolivar Puente “Postmodern immutable data structures” · CppCon · 1:05:59
- Sorting Algorithms: Speed Is Found In The Minds of People - Andrei Alexandrescu - CppCon 2019 · CppCon · 1:29:55