The Fast Fourier Transform (FFT): Most Ingenious Algorithm Ever?

In this video, we take a look at one of the most beautiful algorithms ever created: the Fast Fourier Transform (FFT). This is a tricky algorithm to understand so we take a look at it in a context that we are all familiar with: polynomial multiplication. You will see how the core ideas of the FFT can be "discovered" through asking the right questions. The key insights that are presented in this video is that polynomial multiplication can be improved significantly by multiplying polynomials in a special value representation. The challenge that presents itself is the problem of converting a polynomial from a standard coefficient representation to value representation.

We see that the FFT is an incredibly efficient recursive algorithm that performs this task, and we also discover that a slightly tweaked FFT (Inverse FFT) can also solve the reverse problem of interpolation. If this video doesn't blow your mind, I don't know what will.

0:00 Introduction
2:19 Polynomial Multiplication
3:36 Polynomial Representation
6:06 Value Representation Advantages
7:07 Polynomial Multiplication Flowchart
8:04 Polynomial Evaluation
13:49 Which Evaluation Points?
16:30 Why Nth Roots of Unity?
18:28 FFT Implementation
22:47 Interpolation and Inverse FFT
26:49 Recap

Also a subtle mistake that a commenter made me aware of -- at 26:40 instead of replacing w with (1/n * e^{-2 * pi i/ n}), the actual right way to do this is by taking the final output of the IFFT at the end of the recursion and dividing by n.

So the full change is w = e^{-2 pi i / n}
And then somewhere outside the scope of the IFFT function ifft_result = 1/n * IFFT(values)

The treatment of the FFT in this video is inspired by several well known references, mainly Introduction to Algorithms (Cormen et al.) and Algorithms (Papadimitriou et al.).

Music:

All other music by Aakash Gandhi

SVG Attributions:

[Reducible]

Also a subtle mistake that a commenter made me aware of -- at 26:40 instead of replacing w with (1/n * e^{-2 * pi i/ n}), the actual right way to do this is by taking the final output of the IFFT at the end of the recursion and dividing by n. Sorry about that error, and in general all bugs like this one will be updated in the description of the video.

So the full change is w = e^{-2 pi i / n}
And then somewhere outside the scope of the IFFT function ifft_result = 1/n * IFFT(<values>)

As one additional side note, there seems to be a little confusion about the point by point multiplication at 6:31. Remember, all that's happening here is we are sampling points from polynomials A(x) and B(x) and using these points to find a set of points for C(x) = A(x)B(x). Every corresponding y coordinate for C(x) will be the y coordinate of A(x) multiplied by the y coordinate of B(x). Therefore, point by point multiplication really means "let's just keep the x-coordinates and multiply the y-coordinates."

[mikemarsh]

Back in 1972 when I was a young physics grad working in an optics lab, I built an FFT optical spectrometer using a Michaelson interferometer using a laser reference beam as a ruler to trigger my computer program as to when to take samples of the sample beam, using an appropriate set of A/D converters. I scanned the interferometer by advancing one leg with a fine screw and we took 16, 384 samples, which made for a nice resolution. Written in Fortran for a Data General Nova with a 5 pass compiler, then hand optimized the assembly code to make it efficient enough to run in real time, displayed on a long retention phosphor oscilloscope as it scanned. I even made a hardware assisted program instruction to do the bit reversal and shift to speed it up.

[timotejbernat]

6:58 not going to lie, I spent an inordinate amount of time trying to figure out how it could possibly be O(n)! before realizing the exclamation was only punctuation, not a factorial

[geeshta]

Years ago when I got to sound design, I was so excited that you can represent sound as both a waveform and a set of frequencies. I heard about this mysterious "Fourrier transform" that was responsible for that and the famous "FFT" algorithm that made it possible for computers to do things such as equalization quickly. I saw some videos on YouTube that explained it but lacking the proper mathematical background, I couldn't wrap my head around it.

Now this video got to my recommended, with your excellent step-by-step explanation with actual examples. I still can't wrap my head around it.

[blitzkringe]

I think the most impressive thing about this Fourier Transform related video is that it never mentions words "sine" or "frequency".

[CodeParade]

Just got recommended your channel, really like it! If you need any topic suggestions, I'd love to see a video about the disjoint set and union-find algorithm. That's one of my favorites, but it's not as well known. It even uses the inverse Ackermann function for the big-O analysis too which is super weird and interesting.

[fareast]

I smell Grant's python library at work (oh, its credited in description, never mind)

[fuckYTIDontWantToUseMyRealName]

"If your mind isn't blown, you weren't paying attention."

I promise, I tried.

[benjaminv]

This is a great video. I love the close interconnection of serious mathematics and efficient programming. This didn't just help me better understand tricks for efficient algorithms (the log n trick is awesome), but also understand why the fourier transform is defined as it is. I mean, I understood the mathematics since before, but this gave so much intuition.

Some background knowledge defenitly helps here, I think, but I love the level. Please keep it up! Simpler concepts are covered pretty well elsewhere too, but this might be the best video on FFT on all of YouTube by quite a bit (imo). Keep it up! See you when you've totally blown up :)

[alexarnold]

Holy crap! How has it already been 30 mins!?! You know it's a good video when you completely loose track of time!

[abc-bykb]

13:00 for those of you who are wondering why he is plugging in the square of x_i. It's because when we use the coefficient form, if we just plug in x_i, it would be interpreted as powers 0, 1, 2, ...., so if we plug in x^2 it would be interpreted as (x^2)^0. (x^2)^1, (x^2)^2, (x^2)^3, which are powers 0, 2, 4, 6...which are even terms.

[wsm]

Who came here from 3blue1brown and fell in love with this channel?

[vylbird]

An aside: When you mention that any polynomial of degree N can be uniquely determined by N+1 points? That's how many forms of forward error correction work, suitably modified for modular arithmetic. If you want to send your message you break it up into N parts, each of which becomes a point on a polynomial of degree N-1. Then generate as many extra points on the polynomial as you need to generate a list of K points where K>N, and transmit those K points through your unreliable communications channel. As long as at least N of the K make it through to the other end, you can recover the original message.... and thus your phone call can keep on going even with a little radio interference taking place. You can tune K to be optimal for the reliability of your communications channel and the acceptable level of overhead.

[Maltanx]

Dude, you uploaded this video like two minutes before I searched for a video on how FFT works. Not even subbed but this was one of the first videos to pop up. That was a ridiculously perfect timing!

Also, I'm getting strong 3blue1brown vibes from your channel, subscribed right away!

[MrKyltpzyxm]

This popped up in my recommendations. I have a bad habit of watching long, intricately detailed descriptions of concepts that I do not have the foundational education to understand. This is probably why every time I see a video like this that assumes I have some prior knowledge, I wonder how I ended up here.
The video itself, however, is spectacular. Very easy to follow, even with my lack of understanding. (I don't think I am describing this very well, but you'll have to trust me.) I work as a cable technician and have a very VERY basic understanding of RF signal processing theory. It's always interesting to peer into the depths of what keeps it all tied together.
I keep telling myself that one day I'll work up the nerve to pursue a more structured, formal education in these topics, but in the mean time I am glad that such accessible presentations exist out here in the wild.

[intrinsicload]

WOW. I'm literally blown away. This video is EXCELLENT. PLEASE keep doing what you're doing! Instant share.

[desmonddulaney]

Very helpful video. However, I'd like to point out that @10:50, the decomposed functions should be P_e(x) and P_o(x) not P_e(x^2) and P_o(x^2) because once we do substitute in x^2, it should get us back to the original function. No one has pointed out this mistake so I figured I would because I was confused for a little bit.

[mohammedbelgoumri]

One of the absolute best math videos I ever watched. Only problem is I couldn't find the code for this particular video in the repo.

[muskyoxes]

this is a ridiculously awesome amount of work, possibly hundreds of times as long as the video. it hurts to think this will make less money than someone doing a makeup tutorial

[xXKILLBOTXx]

I like the fact you actually laid out the pseudocode for the algorithm at the end of each section, most channels that cover topics like these usually leave it at the block diagram. Shows you really know your stuff.