One Trick Made Computers 50,000x Faster | Fast Fourier Transform

In 1963, John Tukey scribbled an idea on a notepad at a meeting of President Kennedy's Science Advisory Committee. The committee was trying to figure out how to detect Soviet underground nuclear tests after the Limited Test Ban Treaty. The math required to fingerprint a deep explosion from a seismometer was clear; the computation was impossible. Tukey's idea cut the cost of that computation by a factor of fifty thousand.

Two years later, James Cooley at IBM published the algorithm. It's now called the Fast Fourier Transform. It runs every Wi-Fi packet, every MRI scan, every JPEG, every MP3, every gravitational-wave detection at LIGO. It is, with reasonable confidence, the most-executed nontrivial algorithm in the history of computing.

But Cooley and Tukey didn't invent it. The same algorithm was first written down in 1805, in Latin, by Carl Friedrich Gauss — to chase the orbit of an asteroid. He filed the manuscript away and never published. The world had to wait 160 years to learn what he had quietly discovered.

This video is about how the FFT works, why it matters, and why the most important algorithm of the 20th century was sitting in a drawer in Brunswick for over a century before anyone could use it.

Chapters:
0:00 A signal you can't see
1:20 The cost of listening
2:50 1965
4:42 The trick
6:30 Where it hides
8:21 The notebook
10:00 Why it took 160 years

Music:
"Origami" — Scott Buckley (https://www.scottbuckley.com.au)
"Incredulity" — Scott Buckley (https://www.scottbuckley.com.au)
Used under Creative Commons BY 4.0 license.

Sources:
Heideman, Johnson & Burrus, "Gauss and the History of the FFT," Archive for History of Exact Sciences (1985).
Cooley & Tukey, "An Algorithm for the Machine Calculation of Complex Fourier Series," Mathematics of Computation 19, no. 90 (1965): 297–301.
Strang, "Wavelets," SIAM Review 36, no. 1 (1994).

#mathematics #algorithm #fft #fourier #manim #problemsvisualized

Видео One Trick Made Computers 50,000x Faster | Fast Fourier Transform канала Euclidia