FFT Example: Unraveling the Recursion

We break down how the FFT evaluates a particular polynomial at the roots of unity by unraveling the recursive process completely.

0:00 Introduction
1:13 FFT Example Breakdown

Music:
All music by Aakash Gandhi

[kiranraaj]

Why doesnt this channel have the recommendation it deserves. Its by far the best CS edutainment channel I have discovered yet.

[eamonnsiocain]

I remember studying the FFT in college (some 50 years ago) and I used it throughout my career. I’m now retired, but I still love to watch videos on Maths. Yours are particularly clear; in fact, they are works of art. Excellent!

[NTNscrub]

This series alone earned you my subscription. It ain't much, but it's something. Thank you for the explanations.

[mubashirsoomro]

What a lovely set of videos! it helped me refresh my memories from Signal Processing classes. Would have loved to see some butterfly diagrams though, they are very beautiful to look at and quite useful to visually understand the process.

[berkealgul]

Man... learning computer science with 3b1b style. Insta sub

[jaishriharivishnu]

you always make me cry, be its tower of hanoi, recursion in number of colour, now fast fourier. Thanks a lot for being so supportive

[jackblack]

I love your channel! I run my high school computer club and your videos are an invaluable resource for both learning and teaching!

[Zmunk]

thanks for this example, I wouldn't have understood the FFT without it

[GrahamHay-td]

Finally I have found an explanation that makes sense. Many thanks!

[GhenGhost]

I have been mulling over the FFT for WEEKS. Finally I have understood it, just by seeing that for 4 elements, the number of multiplications we did was 2*2+4 = 8 = 4 log2(4), compared to 4^2 = 16 for the DFT. For 8, it would be 4*2+2*4+8 = 24 = 8log2(8), compared to 8^2 = 16. I have an exam on this this Monday, so thanks to you if i ace the FFT question!

[nicknichols]

Why does this channel only have 20k subscribers?? Great content.

[vihnupradeep]

Thankyou so much for this very intuitive breakdown of fft ! Commenting so that, this series will get the views it deserves.

[fhz]

I'd like to add a very interesting point. While working with discrete signals, it common to use Z- transform. It leads a vector to a polynom in the variable z. The interesting point is that a polynomial multiplication is the convolution of its coefficients. The discrete convolution can be performed with a "smart" internal product. "Smart" because of size of results, where the product starts and finishes for each and a back to front flip.

I'd be glad with a Z transform video. :)

[Flash-qroh]

Please continue making these videos they are so helpful

[teka]

Amazing explanation and illustration!!!

There seems to be a small typo at around 2:09: P_e (x^2) —> P_e(x) and similarly for P_o.

Keep up the awesome work!

[larcomj]

Interesting to see the FFT from a algorithm/comp sci perspective.

[Zeero]

Are you going to go over the butterfly diagram in the thumbnail from the last video?

[amirPenton]

Could you do an example inverse FFT? Using the algorithm from the other video I can't get it to work. I think the 1/n which was a factor of the alternative omega is supposed to just be multiplied by the entire final product, but I'm sure I'm just missing something here because every source I check leaves the formula the same way.
Really love the content, reminiscient of 3blue1brown how you can make advanced topics so easy to understand.

Edit: Checked another source and I'm right, checked on the other video and it's fixed in the description. Should have checked there first I guess!

[ilonachan]

Really nice! Although when I read the title I thought this would be about turning the recursive algorithm into an iterative version. Which is something I've just spent the afternoon doing, it was interesting. (Maybe I should just look up the "advanced" algorithm for any n)

[vinoudu]

So satisfying!
But that would be nice to see how fft works when n is not a power of 2 !