# The Most Important Algorithm Of All Time

The Fast Fourier Transform is used everywhere but it has a fascinating origin story that could have ended the nuclear arms race. This video is sponsored by 80,000 Hours. Head to http://80000hours.org/veritasium to sign up for their newsletter and get sent a free copy of their in-depth career guide.

A huge thank you to Dr. Richard Garwin for taking the time to speak with us.

Thanks to Dr. Steve Brunton of the University of Washington for his help with understanding the Fast Fourier Transform.

Thanks to Dr. Cliff Thurber of the University of Wisconsin-Madison, Dr. Paul Richards of Columbia University, and Dr. Steven Gibbons of the Norwegian Geotechnical Institute for their expertise.

Thanks to Grant Sanderson of 3Blue1Brown for his helpful feedback on the script. His great video on the Fourier Transform is here – https://youtu.be/spUNpyF58BY

▀▀▀

References:

Kristensen, H.M., Korda, M. (2022). Status of World Nuclear Forces. Federation of American Scientists (FAS). https://ve42.co/Stockpile2022

Barth, K. H. (1998). Science and politics in early nuclear test ban negotiations. Physics Today, 51(3), 34-39. – https://ve42.co/Barth1998

Schmalberger, T. (1991). In pursuit of a nuclear test ban treaty – https://ve42.co/Schmalberger1991

Bowers, D., & Selby, N. D. (2009). Forensic seismology and the comprehensive nuclear-test-ban treaty. Annual Review of Earth and Planetary Sciences, 37, 209-236 – https://ve42.co/Bowers2009

Incorporated Research Institutions for Seismology (IRIS). (2022). How Often Do Earthquakes Occur? https://ve42.co/IRIS2022

Kimball, D. (2022). The Nuclear Testing Tally. Arms Control Association. https://ve42.co/TestTally2022

Kværna, T., & Ringdal, F. (2013). Detection capability of the seismic network of the International Monitoring System for the Comprehensive Nuclear Test Ban Treaty. Bulletin of the Seismological Society of America, 103(2A), 759-772 – https://ve42.co/Kvrna2013

Sykes, L. R., & Evernden, J. F. (1982). The verification of a comprehensive nuclear test ban. Scientific American, 247(4), 47-55 – https://ve42.co/Sykes1982

Peterson, J., & Hutt, C. R. (2014). World-wide standardized seismograph network: a data users guide (p. 82). US Department of the Interior, US Geological Survey. – https://ve42.co/Peterson2014

Richards, P. G., & Kim, W. Y. (2009). Monitoring for nuclear explosions. Scientific American, 300(3), 70-77 – https://ve42.co/Richards2009

Jacobsen, L. L., Fedorova, I., & Lajus, J. (2021). The seismograph as a diplomatic object: The Soviet–American exchange of instruments, 1958–1964. Centaurus, 63(2), 277-295 – https://ve42.co/Jacobsen2021

Schwartz S. I. (1998). The Hidden Costs Of Our Nuclear Arsenal: Overview Of Project Findings. The Brookings Institution – https://ve42.co/Schwartz1998

Ricón, J.L. (2016). The Soviet Union: Military Spending. Nintil – https://ve42.co/Nintil2016

Heideman, M. T., Johnson, D. H., & Burrus, C. S. (1985). Gauss and the history of the fast Fourier transform. Archive for history of exact sciences, 265-277 – https://ve42.co/Heideman1985

Ford, D. (2004). Richard Garwin – Session IV. American Institute of Physics (AIP). – https://ve42.co/Ford2004

Aaserud, F. (1986). Richard Garwin – Session I. American Institute of Physics (AIP). – https://ve42.co/Aaserud1986

Goldstein, A. (1997). James W. Cooley, an oral history. IEEE History Center, Piscataway, NJ, USA – https://ve42.co/Goldstein1997

Cooley, J., Garwin, R., Rader, C., Bogert, B., & Stockham, T. (1969). The 1968 Arden House workshop on fast Fourier transform processing. IEEE Transactions on Audio and Electroacoustics, 17(2), 66-76 – https://ve42.co/Cooley1969

▀▀▀

Special thanks to Patreon supporters:

Louis Lebbos, Elliot MIller, RayJ Johnson, Brian Busbee, Jerome Barakos M.D., Amadeo Bee, TTST, Balkrishna Heroor, Chris LaClair, John H. Austin, Jr., OnlineBookClub.org, Matthew Gonzalez, Eric Sexton, John Kiehl, Diffbot, Gnare, Dave Kircher, Burt Humburg, Blake Byers, Dumky, Evgeny Skvortsov, Meekay, Bill Linder, Paul Peijzel, Josh Hibschman, Mac Malkawi, Mike Schneider, John Bauer, jim buckmaster, Juan Benet, Sunil Nagaraj, Richard Sundvall, Lee Redden, Stephen Wilcox, Marinus Kuivenhoven, Michael Krugman, Cy ‘kkm’ K’Nelson, Sam Lutfi, Ron Neal

▀▀▀

Written by Derek Muller & Felicity Nelson

Filmed by Derek Muller & Raquel Nuno

Animation by Ivy Tello, Jakub Misiek, Alex Drakoulis, and Fabio Albertelli

Edited by Albert Leung & Derek Muller

Research Assistant: Katie Barnshaw

Additional video/photos supplied by Pond5 and Getty Images

Music from Epidemic Sound

Produced by Derek Muller, Petr Lebedev, and Emily Zhang

If you’re thinking about how to make a positive impact with your work, get a free in-depth career guide from 80,000 Hours: 80000hours.org/veritasium

No

FFT is important and all, but I have a question:

Do you know what the following audio and video formats have in common: MP3, WMA, AAC, Dolby Digital AC3, Ogg Vorbis, Opus, JPEG, MPEG video?

Answer: none of them use FFT. At all. Video formats use the 2D Discrete Cosine Transform, or DCT for short as their basis. Audio formats use Modified Discrete Cosine Transform (MDCT) which gives excellent frame windowing with zero cost, which is really difficult to explain but works almost like magic. With DCT you don’t have to deal with complex numbers which further helps make it better suited for lossy compression.

FFT has many uses in signal analysis. But unlike this video would make you believe, compression isn’t one of FFT:s strongholds.

This is the first time i didn’t fully understand your video atleast I learned something new anyway.. ofcourse this topic is something i never even knew about before this so you’ve done great on explanation

Hey Veritasium, I have invented a 100% clean energy electricity generator, potentially perpetual.. how can I contact you??

I really can’t overstate how appreciative I am of these science history videos. It’s easy in the STEM fields to forget the history soaked into the ideas we take for granted every day. I would like if Math classes gave a little glimpse into this – especially in primary schools. Maybe more kids would appreciate the importance of math and “when we would ever need this in real life”.

Personally, I hated learning the history of things in school, because I’m not _using_ the history. I’m fine with watching videos on it on my own time because I’m doing it of my own volition and not being tested on it.

The worst parts of math and science classes were when they became history classes.

YES!!! I hated math before I started researching it on my own.

YT helped me comprehend concepts I had long gave up on trying to grasp.

It’s a great feeling to have thay eureka moment after so long I the dark.

Good schools should take advantage of technology, and leave most lectures to video makers with a particular talent for it. Teacher time is more valuably spent answering question and helping with hands on exercises.

@Sepehr I agree but unfortunately, no regular teacher has the budget and time (and definitely not the skill) to produce Bill Nye the Science Guy level interesting type shows. That’s why we love to show Bill Nye you tube videos to science classes. There are so many interesting and informative YouTube videos on math and science. (Big thanks to YouTube!!)

In truth though, kids get bored and disinterested in seeing video after video of the topics presented in such an interesting way. (Bill’s “enthusiasm” can get a bit repetitive and off putting even for the most interested.)

Still, I very much appreciate the math & science lessons (the whole k-12 curriculum, essentially) available online, for free, on YouTube. (Again, BIG thanks YouTube!)

99% of people don’t need to know this information. I’d rather kids be well rounded

As a Electrical Engineering student who has taken digital signal processing, this is a beautiful high level understanding of fft. Love your videos man!

Ah signals and systems, memories.

Good time memories staying up until 2AM doing FFT and Laplace.

Damn it. That was word for word the same comment I was about to write

@Kevin as another electrical engineer, I am akin to Nikola Tesla so if you have any questions just ask me

As another electrical engineering student, I couldn’t agree more. It’s beautiful in ways I can’t describe

FFT is the reason we are able to diagnose the problems with industrial machinery (pumps, compressors, turbines). As a mechanical engineer, I absolutely loved this explanation, but have to watch it again to understand it fully. Thanks, Derek for this work! 🙏