The Fast Fourier Transform: History, Impact, and Applications

1. Introduction: The Most Important Algorithm

The Fast Fourier Transform (FFT) is ubiquitously used in modern technology including video streaming, 5G, WiFi, radar, and sonar. The video introduces the FFT's historical discovery during Cold War nuclear weapons detection efforts.

2. The Nuclear Arms Race and Test Ban Negotiations

After WWII, the U.S. proposed the Baruch Plan to limit nuclear weapons, but the Soviet Union rejected it, triggering a global arms race. Public outcry against nuclear testing in the 1950s led to international negotiations for a comprehensive test ban, but verification of underground tests proved impossible without advanced detection methods.

3. The Challenge of Detecting Underground Nuclear Tests

Scientists needed a way to distinguish nuclear explosions from earthquakes using seismic data and determine bomb yield and burial depth. The problem required computing Fourier transforms on seismic signals, which required prohibitive amounts of computation—over 3 years for a single analysis of a million-sample signal.

4. Understanding Fourier Transforms

A Fourier transform decomposes signals into their component sine and cosine waves with different frequencies and amplitudes. The discrete Fourier transform applies to finite, sampled real-world signals with frequency components organized into discrete bins determined by signal duration and sampling rate.

5. The Computational Breakthrough

In 1963, John Tukey discovered a method to dramatically reduce FFT computational complexity from N² to N log N by exploiting periodic symmetries in sinusoidal functions. A million-sample transform that would take 3 years could now be computed in 35 minutes.

6. How the Fast Fourier Transform Works

The FFT algorithm recursively splits data into even and odd-indexed samples, exploiting symmetries of sine and cosine waves to reuse calculations. At each level of splitting, the number of required calculations is halved, achieving exponential improvements in speed.

7. History Lost and Rediscovered: Gauss's Forgotten Algorithm

Carl Friedrich Gauss independently derived the FFT algorithm in 1805 while analyzing asteroid orbits but never published it. His notes remained undiscovered until after his death, written in Latin with non-standard notation, representing a 160-year delay in one of mathematics' most important discoveries.

8. Consequences for the Nuclear Arms Race

The partial test ban treaty of 1963 only banned atmospheric and underwater testing because underground tests couldn't be reliably detected. This sent the arms race underground, leading to 1,500 nuclear detonations between 1963 and 1993, peaking at 70,000 nuclear warheads in the mid-1980s.

9. Modern Applications: Image Compression and Signal Processing

FFTs enable image compression by identifying high-frequency components (which contribute little to visual perception) and discarding them without noticeably degrading image quality. FFTs are fundamental to compression algorithms, WiFi, 5G, radar, sonar, medical imaging, and all forms of signal processing.

10. Conclusion: Impact of Career Choices

The video concludes by reflecting on how Gauss's forgotten work and Cooley-Tukey's rediscovery illustrate the cumulative impact of intellectual work. The 80,000 Hours nonprofit helps people find careers that make positive global impact.