Kind: captions
Language: en
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 anytime 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 U.S 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 U.S 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
foreign
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 a 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 U.S also created a nuclear testing
site in Nevada their 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 U.S 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
Earth is being bored within the range of
technical possibilities
[Music]
thank you
in 1954 at Bikini Atoll in the South
Pacific the U.S 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 is 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 U.S 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
possibility of detecting violations of a
possible agreement on suspension of
nuclear tests seriously that was the
name I am not making this up
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 three 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 shout out to the awesome
video by three blue one brown 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 waves 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 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 nations
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 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
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 2 3 4 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 well
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 1 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 four and then repeat the process
for two Hertz 3 Hertz and so on up to 7
Hertz and you have the Discrete Fourier
transform of this really simple signal
now this process works fine in principle
and you could use it to calculate all
Discrete Fourier transforms but the
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
and 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
Tuki doodling throughout but what he was
actually doing was working on Discrete
Fourier transforms at the end of the
meeting Garwin asked Tuki what he had
worked out and he was shocked to learn
that Tuki 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 8 times 8
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 eight
multiplications you only need to do two
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 50 000 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 indexed 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
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 two 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 U.S as
nuclear powers
and the partial Test Ban Treaty bar 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 U.S 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
than 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 the board 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 Palace
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 Tuki a
century and a half earlier
the reason his breakthrough was not
widely adopted 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
one kiloton or so explosion basically
anywhere on Earth
following Cooley and tuki'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 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 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 and that 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
want to 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 non-profit
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 finish
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 going to
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
eighty thousand hours everything they
provide from their podcast to their job
board is free forever if you join the
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 eighty thousand hours dot org
slash veritasium I will put that link
down in the description so I want to
thank 80 000 hours for sponsoring this
part of the video and I want to thank
you for watching