This is a video about the most important algorithm of all time, the Fast Fourier Transform or FFT. I mean, you use it all the time, including right now to watch this video, and it's used in radar and sonar, 5G and Wi-Fi. Basically, any time a signal is processed, there's a good chance that a fast Fourier transform is involved. But on top of all this, the FFT was discovered by scientists trying to detect covert nuclear weapons tests, and If they had discovered it sooner, it may have put a stop to the nuclear arms race.
You know, I always assumed that the nuclear arms race was inevitable, that once the US dropped atomic bombs on Hiroshima and Nagasaki, it was just unavoidable that all the other major powers would develop nukes. But maybe it wasn't. Because it was clear to everyone that nuclear weapons were game-changing.
The bomb dropped on Hiroshima released a thousand times more energy than the biggest conventional explosive. So other countries were rightfully concerned. At the end of the war, Canada and the UK requested a meeting to discuss what would be done about nuclear weapons. And contrary to what I expected, the US was actually open to these discussions. They realized that they wouldn't be the only nation with nukes for long.
So they offered to decommission all their nuclear weapons if other nations would pledge never to make them. This was known as the Baruch Plan, and it proposed that an international body would control all radioactive materials on Earth, from mining to refining to using these materials for peaceful purposes, as in nuclear power generation. But the Soviets rejected the proposal. They saw it as just another ploy to maintain American nuclear dominance. And so, the global nuclear arms race began.
To develop new nuclear weapons required extensive testing, and most of it was done in remote places like the Arctic or the South Pacific Islands. The US also created a nuclear testing site in Nevada, the radioactive products of which blew across the country, so that outside of Japan, the people most adversely affected by American nuclear weapons were Americans themselves. The US soon graduated from fission weapons to thermonuclear bombs, which combined fission and fusion to release even more energy. They were as big a leap from the first atomic bombs as those devices were from conventional explosives. a thousand times again more powerful.
Annihilation of any life on Earth has been brought within the range of technical possibilities. In 1954 at Bikini Atoll in the South Pacific, the US tested a new thermonuclear design that used lithium deuteride as a fuel. And they expected the device, codenamed Shrimp, to release the energy equivalent of 6 million tons of TNT. But they were wrong. It released two and a half times that due to unanticipated reactions with lithium-7.
And as a result, more radioactive material was created and it rained down over a much larger area than planned. Residents of neighboring atolls were only evacuated three days later suffering from radiation sickness. And further east, the 23 crew of a Japanese fishing boat were caught in a flurry of radioactive white ash.
And by that evening, they were suffering from acute radiation syndrome. One of the crew died from ensuing complications six months later. These events triggered public outcry against nuclear testing.
The modern peace sign was designed in the 1950s by combining the semaphore letters for N and D, standing for nuclear disarmament. A number of world leaders called for a comprehensive test ban. No more testing of nuclear weapons by any state.
And this call was actually taken seriously by the world's nuclear powers. They entered into negotiations at meetings with very literal names like the Conference on the Discontinuance of Nuclear Weapon Tests held in Geneva in 1958. And to show just how serious they were, they even stopped all testing during the negotiations. Which is why 1959 is the only year in a long stretch when no nuclear weapons were detonated. But there was a big problem with negotiating a comprehensive test ban, which is, how do you know that the other side will hold up their end of the bargain? The US worried that the Soviets would continue testing covertly and leapfrog them technologically, and the Soviets similarly distrusted the US.
So to address these concerns, they convened the Conference of Experts to study the possible possibility of detecting violations of a possible agreement on suspension of nuclear tests. Seriously, that was the name. I am not making this up. Now, detecting atmospheric tests was fairly straightforward.
The radioactive isotopes they produce disperse in the atmosphere and can be detected thousands of kilometers away. Underwater tests produce distinctive sounds that travel efficiently. around a kilometer below the surface of the ocean. These can be picked up by hydrophones. But underground tests are much harder to detect from afar because their radiation is mostly contained.
And the Soviets refused to allow on-site compliance visits, which they regarded as espionage. And this is ultimately why when a test ban treaty was signed in 1963, it was only a partial ban. It banned testing underwater, in the atmosphere, and in space.
places where compliance could be verified, but it didn't ban testing underground for the simple reason that it was almost impossible to verify compliance. But scientists had been trying to find a way to reliably detect underground detonations. Following the Geneva meeting, American and Soviet scientists formed a working group to discuss the issue, and their idea was to use seismometers located outside the countries where nukes were being tested to detect the faint ground vibrations caused by explosions. The problem was, how do you distinguish a nuclear test from an earthquake?
Every day around the world, there are close to 300 earthquakes with a magnitude of 3 or greater. In addition, part of the purpose of detecting your adversary's tests is to spy on them, to know how big of an explosion they can make. But the seismometer signal depends not only on the yield of the device, but also on how deep it was buried.
For a given yield, deeper explosions appear smaller. So scientists wanted a method to reliably determine whether a given signal was a bomb or an earthquake, and if it was a bomb, how big it was and how deep it was buried. They knew that all this information was contained in the seismometer signal, but it couldn't just be read off by looking at the squiggles.
They needed to know how much of different frequencies were present, which meant they needed to take a Fourier transform. A Fourier transform is a way of decomposing a signal into pure sine waves, each with its own amplitude and frequency, that add to make it up. This seems a bit like magic, since the sum of a set of sine waves can look arbitrarily complicated and nothing like its component parts.
There are some elegant ways to understand how Fourier transforms work shoutout to the awesome video by 3blue1brown, but I want to take more of a brute force approach. If you want to know how much of a particular sine wave is in a signal, just multiply the signal by the sine wave at each point, and then add up the area under the curve. As a simple example, say our signal is just a sine wave with a certain frequency, but pretend we don't know that, and we're trying to figure out which sine waves add to make it up. Well, if you multiply this signal by a sine wave of an arbitrary frequency, the two waves are uncorrelated.
You're just as likely to find places where they have the same sign, both positive or both negative, as where they have opposite signs. And therefore, when you multiply them together, the area above the x-axis is equal to the area below the x-axis, so these areas add up to zero. Which means that frequency sine wave is not a part of your signal.
And this will be true for almost all frequencies you could try, assuming you're looking over a long enough time frame. The only exception is if the frequency of the sine wave exactly matches that of the signal. Now these waves are correlated, so their product is always positive, and so is the area under the curve.
That indicates that this sine wave is part of our signal. And this trick works even if the signal is composed of a bunch of different frequencies. If the sine wave's frequency is one of the components of the signal, it will correlate with the signal producing a non-zero area.
And the size of this area tells you the relative amplitude of the signal. that frequency sine wave in the signal. Repeat this process for all frequencies of sine waves and you get the frequency spectrum, essentially which frequencies are present and in what proportions.
Now so far I've only talked about sine waves, but if the signal is a cosine wave, then even if you multiply it by a sine wave of the exact same frequency, the area under the curve will be zero. So for each frequency we actually need to multiply by a sine wave and a cosine wave and find the amplitudes for each. The ratio of these amplitudes indicates the phase of the signal, that is, how much it's shifted to the left or to the right. You can calculate these sine and cosine amplitudes separately, or you can use Euler's formula, so you only need to multiply your signal by one exponential term.
Then the real part of the sum is the cosine amplitude, and the imaginary part is the sine amplitude. In the American delegation at the Geneva meeting, there was a physicist Richard Garwin and a mathematician John Tukey. They got into a debate with the Soviet delegation over which nation's seismometers were superior.
So Garwin simulated the responses of both countries'devices on a computer at CERN. The next day, everyone agreed there wasn't much difference. The real obstacle to detecting underground explosions wasn't the accuracy of the seismometers. It was the vast amounts of computation required to Fourier transform the seismometer signals.
Here's an example seismometer signal and its Fourier transform. Thus far, I've been thinking about signals as infinite continuous waves, and when you take their Fourier transform, you get an infinite continuous frequency spectrum. But real-world signals are not like that. They are finite and made up of individual samples or data points. Even though a seismometer signal looks smooth and continuous, it doesn't record ground motion with infinite precision.
There is some fundamental ground motion, graininess to the data. So what you have is discrete finite data. So you can't use the idealized Fourier transform.
Instead you have to perform something called a discrete Fourier transform. And one of the distinguishing features of a discrete Fourier transform is that the frequency spectrum is also discrete and finite. You can think of the frequencies as falling into a finite number of bins.
And what determines the number and size of these bins is the number of samples in the signal and how closely spaced they are. For example, the more spaced out the samples are, the lower the maximum frequency you can measure, because the samples aren't close enough together to capture high frequency oscillations. The shorter the duration of the signal, the harder it is to tell similar frequencies apart, so this lowers the frequency resolution. The shorter the signal, the faster the signal is recorded.
the wider each frequency bin is. The lowest non-zero frequency you can effectively measure is one whose period is equal to the duration of the signal. And the higher frequency bins are just integer multiples of this frequency, so they fit two, three, four, and so on periods in the duration of the signal.
The total number of frequency bins is equal to the number of samples in the signal. So if the signal is made up of eight samples, then the transform has eight frequency bins going from zero up to seven times the fundamental frequency. So let's do an example.
Say we have a signal made up of eight samples. Then the discrete Fourier transform will have eight frequency bins. The first bin corresponds to a frequency of zero. Essentially, this measures if the signal is systematically shifted off the x-axis. You can think of it as measuring the DC offset.
You multiply each data point by one and add them all together. In this case, they add to zero. The second frequency bin corresponds to the frequency that fits one period in the duration of the signal. So in this case, that corresponds to one hertz. You multiply each point by a sine wave of this frequency and a cosine wave of this frequency and separately add them up.
For sine, they add to zero. For cosine, they add to... 4, and then repeat the process for 2 Hz, 3 Hz, and so on up to 7 Hz, and you have the discrete Fourier transform of this really simple signal. This process works fine in principle, and you could use it to calculate all discrete Fourier transforms, but the problem is it requires way too many calculations.
To complete one discrete Fourier transform requires multiplying n data points by N different frequency waves, so N squared complex multiplications. Now this is doable for eight samples, but if you had, say, a million samples, that would require a million squared, or one trillion calculations. At the speed of 1960s computers, that would take over three years to complete, all for a single transform.
Now, a million samples is admittedly more than you would need for a single seismic event, But to analyze tens of events per day from hundreds of seismometers, it would just be far too time consuming. And that's what gave scientists the impetus to look for a better way. The breakthrough came in 1963 at a meeting of the president's science advisory committee.
President John F. Kennedy was there, as were Garwin and Tukey, the physicist and mathematician from the Geneva meeting. Although they were discussing issues of national importance, like the Apollo program and nuclear fallout shelters, the meeting was apparently pretty boring. Garwin observed Tukey doodling throughout. But what he was actually doing was working on discrete Fourier transforms.
At the end of the meeting, Garwin asked Tukey what he had worked out, and he was shocked to learn that Tukey knew a way to compute discrete Fourier transforms with many fewer computations. It would mean that the calculation that would have taken over three years could be done in just 35 minutes. This has aptly become known as the fast Fourier transform.
So here is how it works. Consider the example from before with eight samples. Each of those data points must be multiplied by the eight different frequency waves.
Here I'm only showing cosines for simplicity. So you would expect this to require 8x8 or 64 complex multiplications. But, due to the periodic nature of sinusoids, these waves of different frequencies overlap in a predictable way. For example, at the middle data point, all of the four odd frequencies have the same value, and all of the four even frequencies have the same value as well. So instead of doing 8 multiplications, you only need to do 2. And this sort of duplication occurs at the other data points as well.
So instead of performing 64 calculations, you need only 24. Now that might seem like a small improvement, but it's the difference between a calculation that scales as n the number of samples squared, versus one that scales as n log base 2 of n, which means the bigger the data set, the greater the savings. A signal with a thousand samples would require a hundred times fewer calculations, and a million samples would require fifty thousand times fewer calculations. But how do you know which calculations are redundant? Well, take your samples and split them into even and odd index points. You still need to multiply each of these by the eight different frequency waves.
But now let's look only at the even points. and compare the first four frequencies to the second four frequencies. And what you find is that in each case at the location of the samples, the values of the two sine waves are the same.
A similar pattern can be observed for the odd index points, except the values of one sine wave are the negative of the other. More generally, they're related by a complex number. But what this means is that you don't have to do all the multiplications for the second half of the frequencies. Once you've calculated the odd and even sums for the lower half of the frequencies, you can reuse these values to find the upper half.
So you've effectively cut the number of calculations required in half. But that's only a factor of 2. How do you get down to n log base 2 of n? Well, you repeat the same trick. Split the samples again into even and odd points. and then again repeatedly until you're down to single data points.
At each split you can exploit the symmetries of sinusoidal functions to cut the number of calculations in half. And that is how the fast Fourier transform reduces n squared calculations down to n log n. And it's why today whenever anyone takes a Fourier transform it's almost always done as a fast Fourier transform.
Garwin approached an IBM researcher, James Cooley, to program a computer to run the FFT algorithm. But he didn't tell him the reason was to detect underground Soviet nuclear tests. He said it was to work out the spins in a crystal of helium-3. Cooley and Tukey published the algorithm in a seminal 1965 paper, and its use immediately took off.
But it was too late to secure a comprehensive nuclear test ban. By that time the UK, France and China had joined the Soviet Union and the US as nuclear powers. And the Partial Test Ban Treaty, far from de-escalating the nuclear arms race, just sent it underground.
The thinking was if you were only allowed to test underground, then you better be testing extensively so as not to fall behind all the other nuclear states. So from 1963, 1500 nuclear weapons were detonated. That's roughly one a week for 30 years. This testing facilitated the construction of an absurd number of nukes. At the peak in the mid-1980s, 70,000 nuclear warheads were in existence.
Total expenditure on nukes in the 20th century is estimated at around 10 trillion dollars each for the US and the Soviet Union, adjusting for inflation. If only scientists had been confident in their ability to remotely detect underground tests in the early 1960s, then a comprehensive test ban could have been reached, stopping the nuclear arms race before it really got going. To check how realistic this is, I asked Richard Garwin himself.
Well, it's a good story. It is a good story! It would have helped, and it might have turned the tide. But that would have required an earlier discovery of the fast Fourier transform.
And as luck would have it, it was discovered earlier, but then forgotten. All the way back in 1805, mathematician Carl Friedrich Gauss was studying the newly discovered asteroids of Pallas, Ceres, and Juno. To determine the orbit of Juno, Gauss devised a novel approach to harmonic analysis, and he jotted it down in his notes, but later used a different method, and he never thought to publish that first insight. Today, we can see that Gauss had figured out the discrete Fourier transform before Joseph Fourier himself published it in 1807, and he had developed the same fast Fourier transform algorithm as Cooley and Tukey a century and a half earlier.
The reason his breakthrough was because it only appeared after his death in volume 3 of his collected works, and it was written with non-standard notation in a 19th century version of Latin. What do you think would have happened if Gauss had realized the significance of his discovery and had published it in a way that others could understand? With our modern network of seismometers and computing and the fast Fourier transform, today we have the ability to detect magnitude 3 events, which correspond to a 1 kiloton or so explosion, basically anywhere on earth.
Following Cooley and Tukey's paper, the use of FFTs exploded, and they are the basis for most compression algorithms, like the ones that allow you to watch and listen to this video. Here's how the Fast Fourier Transform allows you to compress an image. You take the pixel brightness values for each row of an image and perform a Fast Fourier Transform. So essentially you're figuring out what frequencies are present in the brightness values of the rows of an image. Here, brightness represents the magnitude of each frequency component, and the color represents the phase, how shifted that frequency is to the left or the right.
And then you perform another FFT for the columns of pixels. It doesn't matter if you do the rows or columns first, what you need is a two-dimensional FFT of the original image. For almost all real-world images, you find that a lot of the values in the transform are close to zero.
I've taken the log of the transform values so you can see them, but if I don't, then it's clear most of the values, especially toward the edges, are very small. These correspond to high frequencies. And what this means is that you can throw out a lot of the information in the transformed image, say 99% of it.
But when you invert that result, you still get a fairly good representation of the original image. So on your computer, most of the images will be saved in this form as a two-dimensional fast Fourier transform. And then when you want to look at the picture again, the computer simply inverts the transform.
There are so many applications for FFTs, from solving differential equations to radar and sonar, studying crystal structures, Wi-Fi and 5G, basically all kinds of signals. signal processing use FFTs. And that's why mathematician Gilbert Strang called the FFT the most important numerical algorithm of our lifetime.
If only it had become more widely adopted after Gauss discovered it, the FFT may have even more dramatically transformed our world. Now, I don't think Gauss could ever have imagined how important the FFT would be, just as most people don't think about the cumulative impact of their life's work. You know, in an average career, you work 40 hours a week, 50 weeks a year, for 40 years. works out to 80,000 hours.
It means that your career might be your biggest opportunity to make a difference in the world. So what do you wanna do with all that time? Now, the name of this video sponsor is 80,000 hours, referencing the amount of impact you can have, the amount of hours you spend at work. And they are not selling anything. 80,000 hours is a nonprofit that helps people find fulfilling careers that make a positive impact.
The typical advice from career centers or aptitude tests really just focuses on finding a job that fits your personal preferences. But what if you care more about doing good? Well, they won't really know what to tell you besides a few well-known professions like being a doctor or a teacher. When I finished college, I knew I liked filmmaking, teaching, and science, and that I wanted to have a big positive impact, but YouTube didn't exist yet, and so I honestly had no idea what I was gonna do.
Now, I feel really fortunate to be able to do something every day that I both enjoy and which makes a positive impact on the world. So believe me, there are a lot of things out there that you can do. And 80,000 Hours offers tons of resources to help you find those things. From research-backed guides on how to pick a career that tackles pressing issues to a regular newsletter and podcast. They even have a curated job board that's kept up to date with hundreds of jobs they think will make an impact.
They have done over 10 years of research alongside academics at Oxford University on how to find a career that is both fulfilling and which makes a positive difference. So their recommendations are accurate, specific, and actionable. If you care about what the evidence says about having an impactful career, and you want real advice that goes beyond empty cliches like follow your passion, then check out 80,000 Hours. Everything they provide, from their podcast to their job board, is free forever. If you join their newsletter right now, you'll also get a free copy of their in-depth career guide sent right to your inbox.
So to get started on a career that tackles the world's most pressing problems, sign up now at 80000hours.org slash veritasium. I will put that link down in the description. So I want to thank 80000 hours for sponsoring this part of the video, and I want to thank you for watching.