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

  Рет қаралды 1,955,980

Reducible

Reducible

Күн бұрын

Пікірлер: 1 500
@Reducible
@Reducible 4 жыл бұрын
For those of you who want to see me break down further how the FFT Implementation works: checkout out this video: kzbin.info/www/bejne/iqqTe5aIa6mpn9U 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() 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."
@ashtonsmith1730
@ashtonsmith1730 4 жыл бұрын
:) first to reply to u
@Reducible
@Reducible 4 жыл бұрын
@@electronicmusicwave7459 Great question and the answer is that multiplication of polynomials is an indirect way to get to the DFT. The key idea is that one of the fastest ways to do polynomial multiplication is take coefficient representations of each polynomial, evaluate them at the appropriate number of roots of unity, multiply the y-coordinates in this new representation, and convert back to coefficient form. The DFT shows up in the evaluation step because evaluation of polynomials is just a matrix vector product where the matrix is the DFT. Remember, at its core, the FFT algorithm is just a fast way to multiply a vector by the DFT matrix -- polynomial multiplication just happens to be one case where the DFT shows up, so we can use the FFT. The DFT also shows up in all sorts of other applications such as taking a time domain signal and converting it to a frequency domain representation, image compression algorithms, acoustics, etc. So there's nothing special about polynomial multiplication other than the fact that the fastest way to do it involved polynomial evaluation which has the DFT.
@jameshogge
@jameshogge 4 жыл бұрын
Was just about to comment the error but saw you already had it! Great video and really clear too!
@LeviATallaksen
@LeviATallaksen 4 жыл бұрын
@@Reducible Divide by 2, rather than by n, I think? Otherwise, in the recursions, we would divide by n/2, while calling on recursions that divide by n/4 themselves, and so on... Really like the video, by the way!
@wormius51
@wormius51 4 жыл бұрын
Great video. Now I got it to work. Maybe you could add a correction in the video though?
@mikemarsh5433
@mikemarsh5433 2 жыл бұрын
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.
@TrapAddict
@TrapAddict 2 жыл бұрын
That sounds so cool!
@imjyun
@imjyun 2 жыл бұрын
yes, further optimization by using photonics !
@7654321220
@7654321220 2 жыл бұрын
sounds like a nice experiment for undergrad students
@headyshotta5777
@headyshotta5777 2 жыл бұрын
I had to read the last sentence just to make sure this wasn't one of those overly complex "andddd I have no idea what I'm talking about. I just made all that up." Memes 🤣 don't mind me, smooth brain over here 😭
@metroboominauditorybellow563
@metroboominauditorybellow563 2 жыл бұрын
As a physics undergrad with some knowledge about FORTRAN and Assembly, and made in '72.... WOAH
@geeshta
@geeshta 3 жыл бұрын
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 KZbin 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.
@markuscwatson
@markuscwatson 2 жыл бұрын
You need to learn the FFT from an engineer's point of view. This is more math/algorithm than you likely need.
@imlxh7126
@imlxh7126 2 жыл бұрын
@@markuscwatson Even better, learn it from a music producer's point of view. Once you get a grip for what filters and EQ do to audio, thinking about signals in the frequency domain makes a LOT more sense.
@nickwallette6201
@nickwallette6201 2 жыл бұрын
As an idiot, I feel like a blind man at a demonstration of optical illusions watching this video. I can tell there are really cool things happening, I just can't see them. OTOH, the 3Blue1Brown videos on FFT were inspirational. I really need to take some math classes. I love everything about audio. I like building speaker enclosures (physics!), I like coding (math!), I like building electronics, and I would love to do some DSP development. But when I start trying to grok the math behind all of that stuff, it feels like somebody took the numbers and four-function buttons off my calculator and now it's all Greek to me.
@ricardoraymond9037
@ricardoraymond9037 2 жыл бұрын
This guy has got to be joking if he seriously thinks we got any mileage in knowledge from this video. He was just talking to himself
@charlesmrader
@charlesmrader 2 жыл бұрын
@@imlxh7126 The reason music relates so closely to frequency is that our ears are sensitive to frequency, but not to phase. A sine wave of a given frequency sounds almost exactly the same if it is delayed by a few milliseconds. Two sinewaves of different frequency sound the same if one is shifted relative to the other. Computers that recognize speech begin with frequency analysis.
@timotejbernat462
@timotejbernat462 4 жыл бұрын
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
@edtsch
@edtsch 4 жыл бұрын
I was thinking as I saw that: "he shouldn't have used the exclamation point there."
@moegreen3870
@moegreen3870 4 жыл бұрын
LOL... i wonder, i think in the spanish fonts they have an exclamation that is flipped upside down :p
@Cyberplayer5
@Cyberplayer5 4 жыл бұрын
Exclamation ! math is hard....XD
@DarthZackTheFirstI
@DarthZackTheFirstI 4 жыл бұрын
spent a crazy amount at 17:30 because w^(n-1) (that would mean 15 points - 1 = 14/2=7; but that lacks one point to reach the opposite site) doesnt really work out when the first is 1 ... . suppose its 16 points divided by 2. then it works just fine :-p . or did i overlook some math context from before? has he uploaded a correct python code by now?
@wuxi8773
@wuxi8773 3 жыл бұрын
Exclamation ! well deserved
@CodeParade
@CodeParade 4 жыл бұрын
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.
@Reducible
@Reducible 4 жыл бұрын
Hey, didn't expect this! I absolutely LOVE the work you do CodeParade! Thanks for leaving this comment! I also love the union find algorithm. The ideas that lead up to the ultimate optimization of path compression and the Ackermann function is also quite beautiful and definitely something I'll keep in mind!
@jaikumar848
@jaikumar848 4 жыл бұрын
@@Zcon18 which post ?
@Zcon18
@Zcon18 4 жыл бұрын
@@jaikumar848 the community post from a couple of days ago
@jamesbalajan3850
@jamesbalajan3850 3 жыл бұрын
I'd love to see a video on union-find. One of the most underrated data structures. Its so incredibly useful for graph problems.
@RudraSingh-pb5ls
@RudraSingh-pb5ls 3 жыл бұрын
@@jamesbalajan3850 absolutely
@alexarnold8461
@alexarnold8461 4 жыл бұрын
Holy crap! How has it already been 30 mins!?! You know it's a good video when you completely loose track of time!
@Reducible
@Reducible 4 жыл бұрын
Thank you so much for this comment! I love hearing comments like this one.
@ccgarciab
@ccgarciab 4 жыл бұрын
I didn't realize, that's amazing!
@nickikallman390
@nickikallman390 3 жыл бұрын
My reaction was instead "Holy crap! How has it already been 3 hours!?!" because I like to pause and think things through and just marvel at the beauty of it
@abc-by1kb
@abc-by1kb 4 жыл бұрын
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.
@blitzkringe
@blitzkringe 3 жыл бұрын
I think the most impressive thing about this Fourier Transform related video is that it never mentions words "sine" or "frequency".
@owenpenning1597
@owenpenning1597 Жыл бұрын
Fourier transform and fast Fourier transform are different
@JeanBaptisteEmanuelZorg
@JeanBaptisteEmanuelZorg Жыл бұрын
or integrals hell
@ibraheemsony9947
@ibraheemsony9947 Жыл бұрын
​​@@owenpenning1597 but they gave similar results
@peterhemmings2929
@peterhemmings2929 Жыл бұрын
Often seems like e^jt is the more fundanmental concept, cos and sin are just the real and imaginary parts of that
@chzpan
@chzpan Жыл бұрын
I am curious why a sin hater would even care about Fourier.
@MrKyltpzyxm
@MrKyltpzyxm 4 жыл бұрын
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.
@Reducible
@Reducible 4 жыл бұрын
Thank you so much for taking the time to write out such a nice comment! I try to make the videos as accessible as possible, but it can be tough especially when we are talking about something as advanced as algorithms to calculate fourier transforms. But I'm glad you were able to get something out of it!
@benjaminv3748
@benjaminv3748 4 жыл бұрын
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 KZbin by quite a bit (imo). Keep it up! See you when you've totally blown up :)
@intrinsicload
@intrinsicload 4 жыл бұрын
WOW. I'm literally blown away. This video is EXCELLENT. PLEASE keep doing what you're doing! Instant share.
@Reducible
@Reducible 4 жыл бұрын
Thank you! Don't plan on stopping any time soon :)
@MadScientist267
@MadScientist267 3 жыл бұрын
Literally?
@Relative0
@Relative0 Жыл бұрын
An amazing breakdown of the FFT!
@1wsm1
@1wsm1 4 жыл бұрын
Who came here from 3blue1brown and fell in love with this channel?
@Reducible
@Reducible 4 жыл бұрын
That shoutout was awesome!
@shadowthehedgehog2727
@shadowthehedgehog2727 4 жыл бұрын
I didn’t know they are from 3blue1brown, but now that you mention it they remind me of one another
@Celastrous
@Celastrous 4 жыл бұрын
Me! This video wasn't quite as easy to follow as Grant's videos, it was a bit too fast paced, but this guy seems to just be starting out, and he's doing a great job so far!
@JSBACH-yv9sx
@JSBACH-yv9sx 4 жыл бұрын
Me too!
@WaluigiisthekingASmith
@WaluigiisthekingASmith 4 жыл бұрын
@@shadowthehedgehog2727 they are different but using the same tools
@petergilliam4005
@petergilliam4005 3 жыл бұрын
Honestly among my favorite youtube videos ever created. I've never felt such an urge to like a video. Every time I'd come back, I'd be disappointed that I've already liked the video and can't do it again.
@1fareast14
@1fareast14 4 жыл бұрын
I smell Grant's python library at work (oh, its credited in description, never mind)
@bimbumbamdolievori
@bimbumbamdolievori 3 жыл бұрын
I thought soo!!!
@xXKILLBOT27Xx
@xXKILLBOT27Xx 2 жыл бұрын
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.
@Maltanx
@Maltanx 4 жыл бұрын
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!
@Reducible
@Reducible 4 жыл бұрын
Haha that's awesome! Always a great time to learn about the FFT!
@l.f.3835
@l.f.3835 3 жыл бұрын
I never knew Applejack's brother was into algorithm theory!! Awesome :^)
@avi7278
@avi7278 3 жыл бұрын
I think that has something to do with polynomial multiplication or something, ehhhemmm...
@arno.claude
@arno.claude 2 жыл бұрын
This explanation is insane!
@NEMountainG
@NEMountainG 4 жыл бұрын
One of the first videos on KZbin I’ve seen that intuitively implements a complex mathematical idea in code. I appreciate how must respect you have for your viewers by showing them the steps to solve this problem without “baby talk”. Absolutely fantastic work! Also, I am aware of 3B1B, Primer, etc. Those channels are also fantastic but I enjoyed how this video actually showed the code implemented from scratch.
@Reducible
@Reducible 4 жыл бұрын
Thank you so much for this awesome comment!
@NEMountainG
@NEMountainG 4 жыл бұрын
You deserve all the compliments you’re reading. I’m fairly familiar with this topic and you did a great job explaining it, easily better than how it was first explained to me.
@vylbird8014
@vylbird8014 4 жыл бұрын
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.
@Reducible
@Reducible 4 жыл бұрын
You've just discovered a future video I'm planning on error correcting codes (Shh don't tell anyone :P).
@AJMansfield1
@AJMansfield1 4 жыл бұрын
@@Reducible Convolutional error correcting codes too, pls?
@Reducible
@Reducible 4 жыл бұрын
​@@AJMansfield1 the ones that I was thinking about going through initially are Reed-Solomon codes and the Berlekamp Welsh algorithm. Both of those techniques rely on similar ideas with polynomials but over a finite field. Pretty cool stuff. Convolutional error correction codes are also pretty interesting so may think about addressing that as well. I have an insanely long list of video ideas that I'm just adding to one by one based on request and my interest so I can't make any promises :)
@gabelluc9573
@gabelluc9573 4 жыл бұрын
This is absolutely brilliant !
@david203
@david203 3 жыл бұрын
@id523a Can someone please explain this? I've implemented Diffie-Hellman, but I'm not familiar with Shamir's algorithm.
@hannesk2119
@hannesk2119 4 жыл бұрын
I am glad 3b1b gave you a shoutout so that I got to see this! very nice video, I especially liked seeing the actual code implementation and of course the smooth animations :)
@JoJoModding
@JoJoModding 4 жыл бұрын
Did 3b1b? Seems like I missed that. Where did he give that shoutout?
@sainathsingineedi2922
@sainathsingineedi2922 4 жыл бұрын
@@JoJoModding community post
@tsunghan_yu
@tsunghan_yu 3 жыл бұрын
@@sainathsingineedi2922 Patreon?
@tsunghan_yu
@tsunghan_yu 3 жыл бұрын
@@JoJoModding kzbin.info/www/bejne/nWm1nHSondl2mZY
@_philosopher_00
@_philosopher_00 3 жыл бұрын
wow man, "A genius is one who makes complex ideas to simple not simple ideas to complex" this surely applies to you. keep doing this good work.
@Jellylamps
@Jellylamps 4 жыл бұрын
I’m just getting into programming and i love learning why things work the way they do. I feel like this channel is going to be very helpful to me
@skoky76
@skoky76 2 жыл бұрын
It won’t - watching this as an common programmer is like if as a worker you would watch how shovel is made in a forge. Nice to watch and know how it is done, but won’t do the shoveling 😀
@joshgorton3843
@joshgorton3843 3 жыл бұрын
I'm a software developer with a background in sound engineering... so I'm use to peering into "black boxes" only to find the math is way over my head... I just trust the magic, LOL. THIS video was about to be more of the same were it not for the final wrap up at the end - WOW! Well done, sir. Well done!
@dombowombo3076
@dombowombo3076 4 жыл бұрын
I think 3Blue1Brown is very happy to see that his library is put to a good use. You even addopted his style of presentation. :) Nice work.
@dragonfyre1589
@dragonfyre1589 3 жыл бұрын
This is a fantastic video! Feels very much like the style of 3b1b- not just bc of the animation, but also bc you have a similar way of carefully yet thoroughly explaining complex ideas. Well done!
@desmonddulaney7131
@desmonddulaney7131 Жыл бұрын
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.
@jingyuanxu7272
@jingyuanxu7272 10 ай бұрын
For anyone has the same confusion - It's actually correct. You start with a function P(x), which in the example, is something to the x^5. You x is input, the function P(x) is something of x^5. To decompose, you split this x^5 into two parts, in the video example, it's x^2, x^4 and odd part is x^3 and x^5, except x^3 and x^5 can be expressed as x*x^2 and x*x^4. The two decomposed function, P_e and P_o, is a function of x, or you can think it as function of y, where y=x^2. So essentially, 2x^4+7x^2+1 is P_e(y) = 2y^2 + 7y + 1. So it's not a mistake, x^2 just mean P_e(y) will take input where the input is x^2 from the original function. FYI - All the video content basically came from the book called "Algorithms". I think combining the book with the video makes a lot more sense...coming from somebody reading the book, don't understand a thing, had to watch the video, then video makes a high level sense but omits a lot of details so had to go back to book again.
@AnatoliiKuznietsov
@AnatoliiKuznietsov 2 ай бұрын
​@@jingyuanxu7272who is the author of this book? where can I find it?
@lbognini
@lbognini Ай бұрын
​@@jingyuanxu7272 Thanks for confusing us even more.
@arez-dev
@arez-dev Ай бұрын
@@lbognini Hey, I just got confused by that as well. So maybe let me try to explain it the way I think I understood it: So P_e(x^2) = 2x^2 + 7x + 1. Looks weird, but let's try to calculate a value of a position. Let's call that position "a". If you now substitute your position a into the formula of P_e, you will notice, that it basically stands where x^2 was standing before: P_e(a) = P_e(x^2) So a = x^2. Now you can just calculate P_e(a) like normal: P_e(a) = 2a^2 + 7a + 1 but since a = x^2 we can write P_e(a) = 2(x^2)^2 + 7(x^2) + 1 = 2x^4+7x^2+1 Hope that helps! 😁
@histravelstories8458
@histravelstories8458 9 ай бұрын
This might be one of the first videos other than travel vlogs where I fell in love with it and subscribed. FFT had been a nightmare, everytime I started learning it mind would just wander off. this video is soooooo good. Thank you for making this. And being beautiful ... you have added beauty to the FFT algorithm.
@tienthanh8490
@tienthanh8490 3 жыл бұрын
I’ve been curious about FFT for a while and has some rough ideas about its applications, but how it works is still a black box to me. Thanks a lot for making such useful educational content - this is the best explanation on FFT I’ve seen so far, oh and great video editing as well. I’m sure this will stick with me, and even if I need some recap I’ll go back to this video. Keep up the good work!
@Renain-hr8bq
@Renain-hr8bq Ай бұрын
This was incredible! 2.5 hours of the lecture in my university explained flawlessly in 28 minutes!!
@mohammedbelgoumri
@mohammedbelgoumri 4 жыл бұрын
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.
@Reducible
@Reducible 4 жыл бұрын
Apologies, I made a rookie mistake and forgot to do that before uploading this video -- just pushed the code for this video.
@mohammedbelgoumri
@mohammedbelgoumri 4 жыл бұрын
Thank you kindly. Keep up the amazing work!
@jajssblue
@jajssblue 4 жыл бұрын
Agreed. Felt like a masterclass. I wish I had this video back in college when I covered the material.
@shantanurahman5084
@shantanurahman5084 4 жыл бұрын
You can find the code (with explanation too) over here cp-algorithms.com/algebra/fft.html
@mohammedbelgoumri
@mohammedbelgoumri 4 жыл бұрын
@@shantanurahman5084 Thanks a lot. I meant the code for the animation, not that of the FFT.
@muskyoxes
@muskyoxes 4 жыл бұрын
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
@RotBaron
@RotBaron 3 жыл бұрын
the creator of these animations has a super loaded patreon page and other stuff. he is doing great!
@davidgustavsson4000
@davidgustavsson4000 3 жыл бұрын
No reason to shit on other creators though. A lot of experience and planning can go into a makeup tutorial too.
@MarekKnapek
@MarekKnapek 4 жыл бұрын
26:44 "So, if your mind isn't blown, you haven't been paying attention." Not gonna lie, you had me in the first half.
@farrukhzamir
@farrukhzamir 11 ай бұрын
Beautifully described and explained. This is the Best video on FFT on youtube which describes the underlying concepts of FFT.
@arno.claude
@arno.claude 2 жыл бұрын
I really wanted to understand FFT, so I took the time to thoroughly watch 3Blue1Brown's, Veritasium's, and your video on the topic, and your approach helped me the most! Maybe because I watched it last, but still, you did a phenomenal job. Well done!
@justarandomcatwithmoustache
@justarandomcatwithmoustache 2 жыл бұрын
same man.
@viharivemuri7202
@viharivemuri7202 Жыл бұрын
I just read about the FFT from CLRS, where the authors directly went into choice of evaluation points as complex roots of unity. But your intuition and the way you deduced that is brilliant! Thanks man!
@BM-jy6cb
@BM-jy6cb 4 жыл бұрын
I was hopeless at maths at uni and even I could follow this. Fantastic explanation!
@Tondadrd
@Tondadrd 4 жыл бұрын
I couldn't fully follow this :( I had Linear algebra at uni tho...
@MRooodddvvv
@MRooodddvvv 4 жыл бұрын
I still cant :(
@duykhanh7746
@duykhanh7746 3 жыл бұрын
i had to stop after 20 minutes because my mind was overloaded...
@hellNo116
@hellNo116 4 жыл бұрын
ok i remember being blown away the first time i learned about fft and i only saw it only the context of signal processing. this is truly amazing. i would watch the big O notation if i didn't just have a month doing so already this semester. your video was amazing and i am really glad i came across it. really inspiring keep up the good work!!!
@sdsa007
@sdsa007 2 жыл бұрын
This is such an amazingly lucid visual explanation of Fourier! I think Laplace, himself would almost be proud, if not infuriated. So much to visualize, but so little time! I mean frequency…
2 жыл бұрын
infourierted
@aloshe1000
@aloshe1000 3 жыл бұрын
This is the most elegant way to explain FFT I have ever encountered. Brilliant!
@TrapAddict
@TrapAddict 2 жыл бұрын
The best way to understand the FFT algorithm is to do it several times for different signal types by hand, starting off with simple signals. Get the equations, draw the diagrams, and then get the outputs and even write a script to do it if you're inclined. Sometimes you just have to follow the rules and steps, and trust that it will all make sense over time!
@CrypticPulsar
@CrypticPulsar 8 ай бұрын
ive parked on this topic for the past 9 weeks, and only now thanks to this incredible video the pieces are finally coming to fall into place! Thank you so much!
@fdmeneses
@fdmeneses 4 жыл бұрын
It's awesome to see 3b1b inspiring great new channels like Reducible. Fantastic material thus far and I'm truly excited for what's to come. Well done!
@renatobritto4096
@renatobritto4096 2 жыл бұрын
Wow just wow, this has gotta be the best video of the year for me. Absolutely astounding work!
@miklov
@miklov 4 жыл бұрын
My mind wasn't blown even once but I didn't arm it first. I'll rewatch this when I have read up on roots of unity and DFT matrices. I did enjoy the content even though it was currently way over my head ^^
@mukhamediyar
@mukhamediyar 2 жыл бұрын
This is single-handedly the best explanation on the topic I have ever seen. Perfect for college students!!
@shishka4022
@shishka4022 4 жыл бұрын
Man, this is one of the best videos I’ve ever seen! You are very clear and keep it very interesting. Serious props to you, great job!
@blacklistnr1
@blacklistnr1 2 жыл бұрын
I was about to comment about the voice's EQ and compression, then I saw the video date and checked your newest video. Congrats on the progress, much more understandable!
@Reducible
@Reducible 2 жыл бұрын
Thanks so much for this comment! Audio was definitely one of those parts of the channel that was admittedly quite weak in the early stages. Got a new microphone, learned a lot more about doing voice overs properly, and it's nice to see that someone notices :) Usually, the gauge for whether it's good is that no one complains :P
@blacklistnr1
@blacklistnr1 2 жыл бұрын
@@Reducible The classic work of behind-the-scenes engineers: when everything is built meticulously no one notices, get one thing wrong and it's top headline. I'm glad you liked my small token of appreciation! :)
@林均頤
@林均頤 4 жыл бұрын
Mind-blowing... Never do I think of FFT when speaking about polynomial multiplication, nor do I ever see so clear the core of the algorithm. My first encounter with FFT is horrible, with the overwhelming notations making me dizzy. This channel absolutely deserves more views.
@Anik70053
@Anik70053 2 жыл бұрын
Better than boring lectures of Advanced Algorithms in college. I really appreciate your explanations. Keep going on. A thumbs up from me.
@PowerhouseCell
@PowerhouseCell 4 жыл бұрын
Really neat video! Speaking from experience, this must have taken forever to make haha. Brilliantly explained and produced :)
@Reducible
@Reducible 4 жыл бұрын
I just watched some of your videos! Man, you are going to explode -- very well done. I can definitely learn a few things from you :) Keep at it!
@sathviknallapuri4667
@sathviknallapuri4667 2 жыл бұрын
Surely, one of the best explanations of FFT I have ever listened to.
@elael2
@elael2 4 жыл бұрын
Great video!! I learned FFT in the classical context, but this is amazing! (Thanks 3b1b for suggesting 😄) Just one detail, I feel we cannot apply the 1/n directly to omega (if the inverse is right). Because 1/n is applied to the 1 values on the matrix as well as the omega is raised to some power that would affect the 1/n too. =)
@Reducible
@Reducible 4 жыл бұрын
Yeah another astute commenter like yourself noticed this, I updated my pinned comment with this note to address this. Sorry about that!
@peplegal8253
@peplegal8253 3 жыл бұрын
Interesting ! Since the coeficient representation can be seen as being in the "frequency domain" (or modal domain whatever) ...and the value representation as being in the "time domain"...oh yeah !!! It makes sense Fourier can be used to exchange between those domains. Really beautiful !!! Thanks ! (you've got another subscriber my friend).
@AndrewAkaHrun
@AndrewAkaHrun 3 жыл бұрын
Amazing! I somehow missed this part of signal processing course so was using FFT as a black wonderbox almost everyday. Now I have a clear view on how it's acually working. Thanks a lot, man! Your work is highly appreciated. Special thanks for using Python for code representation.
@slavisha1989
@slavisha1989 3 жыл бұрын
This is possibly the best explanation of the FFT and IFFT on KZbin.
@anywallsocket
@anywallsocket 4 жыл бұрын
This is insanely good work. I wish I had a better sense of how Euler’s identity, complex numbers, polynomials, and the cycle of differentiation and integration all relate, because everything seems to boil down to these ideas at the heart of mathematics.
@peterfireflylund
@peterfireflylund 2 жыл бұрын
Add linear algebra to the list! (And Generating Functions - I think there is a 3blue1brown video about them.)
@SPalC-qu6hh
@SPalC-qu6hh 2 ай бұрын
"If your mind isn't blown, you haven't been paying attention." --- The beauty of Mathematics!!! Brilliant video man!
@STD282
@STD282 4 жыл бұрын
Absolutely beautiful, I always wanted to understand as to why FFT works! The FFT has always been presented to me as a thing that can map vector convolution to vector multiplication element-wise, and now it looks astonishingly clear why. The trick is, the convolution (or as I sometimes call it, long multiplication without carrying) is *exactly* what you should do in order to multiply the polynomials in coefficient representation, therefore, you can apply it anywhere where convolution takes place. Thank you for this video!
@DarianLee-j8x
@DarianLee-j8x Жыл бұрын
I don't usually comment on youtube, but this video desevered it! Thank you so much! You explained everything so well
@JohnWick-xd5zu
@JohnWick-xd5zu 4 жыл бұрын
This guy was my TA at Cal ❤️❤️
@Reducible
@Reducible 4 жыл бұрын
Go bears! :)
@electronicsandroboticsclub750
@electronicsandroboticsclub750 4 жыл бұрын
John Wick is at caltech now?
@MrNerdHair
@MrNerdHair 10 ай бұрын
Excellent. I was looking for info on the NTT and iNTT over finite fields, and this is a perfect explanation that doesn't incorporate any of the "motivating" nonsense about waves or rotations that aren't relevant for my particular situation!
@jakobv8
@jakobv8 4 жыл бұрын
I don't even have a layman's understanding of complex mathematics, but I was very pleased to be along for the ride, just out of curiosity. Beautiful presentation and I hope to be able to revise and understand more one day.
@BostonGongsil
@BostonGongsil 3 жыл бұрын
This video totally blows my mind and makes me regret not going to science school for the first time. Thank you so much for the great video.
@DJTimeLock
@DJTimeLock 3 жыл бұрын
"We'll take a look at something you're all familiar with. Polynomial multiplication." 1:53 minutes in and you already lost me lmao
@communistpropagandist4608
@communistpropagandist4608 3 жыл бұрын
bruh
@leptok3736
@leptok3736 3 жыл бұрын
We've gone too deep 😂
@lorenpearson1230
@lorenpearson1230 3 жыл бұрын
I used to teach this, and I always found a concrete example was helpful to students. While FFT applies anywhere, we were working with time based signals and extracting the frequencies. While you showed that at the start, I feel you should finish with that. The classic teaching approach of telling the class where you will be taking them, taking them there, and summing up by revisiting where they've been.
@MasamuneX
@MasamuneX 4 жыл бұрын
this is way over my head but I appreciate things being talked about in terms of computability not just in the abstract
@andresquesnel1350
@andresquesnel1350 Жыл бұрын
This is one of the best explanations I have ever seen. Thank you
@CarlosToscanoOchoa
@CarlosToscanoOchoa 4 жыл бұрын
Minute 6:30: how do you multiply points? I'm trying to figure out the rule and I'm not getting it. By the way: subscribed before finishing the video. Seems AMAZING!
@Reducible
@Reducible 4 жыл бұрын
By multiplying points, all that's really happening is multiplying the y-values and keeping the x-value the same. Sorry if that was confusing!
@kavya_manohar
@kavya_manohar 4 жыл бұрын
Thanks for asking this. And thanks for the answer too.I was also confused there. Excellent video.
@CarlosToscanoOchoa
@CarlosToscanoOchoa 4 жыл бұрын
🤦🏻‍♂️🤦🏻‍♂️🤦🏻‍♂️ MANY THANKS! Now that you said it, it is obvious. I think it was the sentence "multiplying points" that got me confused. Thanks again!
@DEtchells
@DEtchells 3 жыл бұрын
Ah! Glad this was asked and answered, that was a showstopper for me, so I went hunting in the comments :-)
@trudyandgeorge
@trudyandgeorge 2 жыл бұрын
Thanks for asking. I came here to ask the same thing.
@ramyakatkam5730
@ramyakatkam5730 2 жыл бұрын
MInd is definitely Blown like a nuclear explanation especially at the part when you mentioned the use of complex numbers, thank you for giving an incredible explanation to a concept in short time that I could not even comprehend during my entire semester of Digital Signal Processing Course! Kudos!
@icicle8334
@icicle8334 3 жыл бұрын
You can never tell how KZbin search algorithm leads you to the right place
@benmaghsoodi2067
@benmaghsoodi2067 3 жыл бұрын
It uses FFT
@JoeNguyen9x
@JoeNguyen9x 3 жыл бұрын
This is the english explanation that I have been looking for. God bless you
@Renslay
@Renslay 3 жыл бұрын
I never went into understanding FFT, because it always seemed so scary to me - even after I understood the Fourier transformation itself. But holy math, this explanation is brilliant! The animations are so smooth (3B1B did a really amazing job with his module!), and everything is clean and understandable. The length of the final code is completely mind blowing! I got so hyped I wrote my own Python implementation, which contains the entire polynomial multiplication, using the FFT implementation you provided (with a few minor modifications). So here it is! Notes: - in FFTCore(), sign decides whenever we use FFT (sign=1), or IFFT(sign=-1) - using list comprehensions instead of for cycles - expanding the polynomials so we always operate on length of powers of 2 - pretty printing the result (the limitations of float values bring near-zero but non-zero imaginary components after IFFT) import math, cmath def FFTCore(P, sign): n = len(P) if n == 1: return P ye, yo = FFTCore(P[::2], sign), FFTCore(P[1::2], sign) w = [cmath.exp(sign*2*cmath.pi*1j*i/n) for i in range(n//2)] y1 = [ye[j] + w[j]*yo[j] for j in range(n//2)] y2 = [ye[j] - w[j]*yo[j] for j in range(n//2)] return y1 + y2 # concatenation def FFT(P, inverse=False): n = len(P) assert((n & (n-1) == 0) and n != 0), "Length of P must be a power of 2" if inverse: return list(map(lambda x: x/n, FFTCore(P, -1))) return FFTCore(P, 1) def polyMul(A, B): lenA, lenB = len(A), len(B) lenC = pow(2, math.ceil(math.log2(lenA+lenB))) A, B = A + [0]*(lenC-lenA), B + [0]*(lenC-lenB) Af, Bf = FFT(A), FFT(B) Cf = [Af[i] * Bf[i] for i in range(lenC)] return FFT(Cf, inverse=True) def prettyPrint(C, lenC): res = [f"{x.real:0.2f}" if cmath.isclose(x.imag, 0.0, abs_tol=0.0001) else f"{x.real:0.2f}{['+',''][x.imag < 0]}{x.imag:0.2f}j" for x in C] print(', '.join(res[:lenC-1])) A = [2, 3, 1] B = [1, 0, 2] C = polyMul(A, B) prettyPrint(C, len(A)+len(B))
@natefidalgo7625
@natefidalgo7625 3 жыл бұрын
Most videos or how people would approach introducing FFT would be by means of Fourier transforms and complex numbers. Including myself and i liked this way of explaining it since it was independent of knowing Fourier transforms or complex analysis to any significant amount. Very very neat way to expose people to FFT thru the problem of fast polynomial multiplication. Just so happened i came across your video and realized it was so close to what i was trying to do with Schönhage-Strassen algorithm and Fürer's_algorithm to get a Harvey and van der Hoeven algorithm O(nlogn). Still got some work to do but was a delight to see somebody creating a video so well on a similar problem. Keep it up great channel!
@xcoder1122
@xcoder1122 2 жыл бұрын
The video is really great and I understood it very well but what I don't understood is how this all relates to time domain vs frequency domain. The FFT transforms a signal from time domain to frequency domain but here it transforms a polygon from coefficient domain to value domain? Aren't these two entirely different things? How is coefficient domain the same as time domain and value domain the same as frequency domain?
@Fat_Fit-ls3hx
@Fat_Fit-ls3hx 4 ай бұрын
I have the same question in my mind
@DannyWrigley
@DannyWrigley 2 ай бұрын
The initial coefficients represent an equation that maps across the time domain (X is understood as time), and the resulting coefficients represent an equation which maps across the value domain (X is understood as value/frequency).
@mohitjoshi9446
@mohitjoshi9446 4 ай бұрын
So brillant description of FFT algorithm. Great job man.
@diegoG21
@diegoG21 4 жыл бұрын
I was blown by the hability to make me lose track of the topic faster than any teacher, engineer and mathematician combined.
@nedisawegoyogya
@nedisawegoyogya 3 жыл бұрын
sarcasm?
@savinolupo2379
@savinolupo2379 2 жыл бұрын
Thank you so much for the beautiful arguments you used to show the magnificence of the FFT algorithm!
@GeofreySanders
@GeofreySanders 4 жыл бұрын
This... this is a perfect example of FM technology.
@ZuvielDrama
@ZuvielDrama 4 жыл бұрын
holy shit - i have tears in my eyes, because this explanation was so beautyful easy to follow. I have to watch it again tomorow. What a great video. Thank you so much!!!!!!!
@batner
@batner 4 жыл бұрын
13:30 Thats it i'm lost. Good video man! Will have to review from top.
@Leon-be4lx
@Leon-be4lx 4 жыл бұрын
batner Same Here
@zihengtong4816
@zihengtong4816 3 жыл бұрын
Sir, you've explained this topic really clearly! And luckily I've seen your video 3days before my exam. Thank you sooo much!!
@_spartan11796
@_spartan11796 4 жыл бұрын
Could someone clarify how the multiplication was carried out at 6:32?
@dominikkuczkowski9537
@dominikkuczkowski9537 4 жыл бұрын
For a given x you multiply values of A and B functions and that gives you the value of C function at that x
@_spartan11796
@_spartan11796 4 жыл бұрын
@@dominikkuczkowski9537 I understand now, thank you!
@chandankumarmishra336
@chandankumarmishra336 3 жыл бұрын
@@dominikkuczkowski9537 thanks...I had to read it multiple times to understand though...
@lbognini
@lbognini 3 жыл бұрын
@@dominikkuczkowski9537 Thanks! It was confusing because he said: "we take five points from each of the two polynomials" as if it was 2 x 5 random points. It would've been clearer if he said: we take five random numbers ( -2, -1, 0, 1, 2). And for each number x, we calculate A(x) and B(x) then multiply them to come up with C(x): A(-2)*B(-2) = C(-2) A(-1)*B(-1) = C(-1) and so on. I would've chosen a different color for the values of x.
@aze4308
@aze4308 2 жыл бұрын
So great that 3b1b just gave this video a shoutout, it's super underrated!
@HomieSeal
@HomieSeal 2 жыл бұрын
Hell yeah
@Alexagrigorieff
@Alexagrigorieff 4 жыл бұрын
Polynomial multiplication is just a discrete convolution, and Fourier Transform is a known way to perform convolution.
@smolboi9659
@smolboi9659 3 жыл бұрын
Yea for signals convolution in the original time domain is the same as multiplication in the frequency domain. This is exactly analogous to convolution of the coefficient representation (using the distributive law) being the same as pointwise multiplication of the value representation. This is the convolution theorem.
@life1lover
@life1lover Жыл бұрын
The best video on mathematics I have ever seen so far, congratulations
@tubanbodyslammer9125
@tubanbodyslammer9125 4 жыл бұрын
I'm here from 3b1b: they just kinda dropped fft on us in intro to EE.
@igornoga5362
@igornoga5362 4 жыл бұрын
Common assumption in engineering courses is that fft is a magic box that's very usefull but the students don't need to know what's inside
@General12th
@General12th 3 жыл бұрын
@@igornoga5362 Common, but probably very unfortunate. Too many students will spend too much time trying to figure out how the magic box works that they lose focus on the rest of the lesson. It's hard for engineering students (and humans in general) to totally compartmentalize "oh, just pretend it works for now".
@lockedloop9413
@lockedloop9413 2 жыл бұрын
Probably I am not the first one who posts this: I wish videos like these were around when I started by EE BSc. Beautifully explained.
@benspiecker484
@benspiecker484 4 жыл бұрын
I would be interested to learn why the FFT circuit resembles a benes network.
@Reducible
@Reducible 4 жыл бұрын
That was a connection I did not realize, doesn't seem like there's much literature about such a connection, but definitely is interesting. Thanks for teaching me something!
@PhillipNordwall
@PhillipNordwall 4 жыл бұрын
Ben at a high conceptual level all the coefficients of the two polynomials being multiplied will need some connectivity to each other. This is just like needing to have a circuit path between all pairs that need to communicate in say a telephone network.
@hoaxuan7074
@hoaxuan7074 4 жыл бұрын
@@PhillipNordwall The fast Walsh Hadamard transform is better for connectivity.
@pafloxyq
@pafloxyq 4 жыл бұрын
Your way of explaining is really Awesome....pls keep making such videos...!!!
@xbronn
@xbronn 4 жыл бұрын
I’m going to watch this until i understand it
@MurakDurak
@MurakDurak 4 жыл бұрын
i had this exact algorithm in a numerical programming class in university and my professor did a fairly poor job at explaining what FFT and IFFT really are - he just showed us the algorithm and how its recursive call works. this video makes me truly appreciate how ingenious this algorithm actually is, and knowing where the algorithm comes from makes understanding it a lot easier. thank you for this amazing explanation!
@amicloud_yt
@amicloud_yt 3 жыл бұрын
holy crap wow this video really made things click for me i've never gotten goosebumps from understanding something before but i just did
@rabinunofficial7362
@rabinunofficial7362 3 жыл бұрын
An absolute beauty... Visualization at its best.. Hats off from the bottom of my 💓
@Liberty4Ever
@Liberty4Ever 4 жыл бұрын
It's soul crushing for mathematicians, but to truly appreciate the glorious beauty of the FFT, you really need to be an electrical engineer. 😁
@keris3920
@keris3920 3 жыл бұрын
I've found a lot of applications for the FFT over the years. Stochastics, statistics, machine learning, music, audio engineering, and so much more. As much as its elegance and ubiquity is stated in the video, it still somehow doesn't seem to do the algorithm justice. It is baked into everything.
@Liberty4Ever
@Liberty4Ever 3 жыл бұрын
@@keris3920 - Great examples. A software defined radio (SDR) can replace a heap of components used to process the radio frequency signal with the FFT, and then replace a lot more components used to process the resulting audio. I get the impression that a more computationally capable human brain could listen to the radio by simply thinking of the FFT, without needing any electronic components.
@keris3920
@keris3920 3 жыл бұрын
@@Liberty4Ever in audio engineering, it's almost paramount to do a lot of frequency-domain work in software using FFTs and wavelets. If you record something that's modified by the hardware, there is no going back and fixing it later. Music in general has a place for both HW and SW implementations of the FFT and frequency-domain modifications in general, so it is a great example (even if the average Joe doesn't have to consider the FFT when listening to music, someone has used an FFT to assist in almost every recorded work of art to date).
@amaarquadri
@amaarquadri 4 жыл бұрын
Great video! You definitely deserve more subscribers!
@floyo
@floyo 4 жыл бұрын
Why Fourier, though? I don't see a connection to fourier transform yet.
@blaze0812
@blaze0812 4 жыл бұрын
Yet.
@damondanieli
@damondanieli 4 жыл бұрын
The Fourier Transform is an integration from -∞ to +∞ of a continuous function. Note the integrand (kernel) of the Fourier transform. The Discrete Time Fourier Transform (DTFT) is still continuous with the summation from -∞ to +∞ (continue to note the kernel). The Discrete Fourier Transform (DFT) samples the DTFT into N samples. The Fast Fourier Transform (FFT) is an optimization of the DFT that uses N (power of 2) samples as shown in the video above. This article has links to all of the above: en.m.wikipedia.org/wiki/Discrete-time_Fourier_transform. Hope that helps.
@AhsanAli-fr4ok
@AhsanAli-fr4ok 4 жыл бұрын
In my opinion, Fourier Transform actually allows to go from coefficient value representation to point wise representation. So in that context, doing calculations in that point representation form are possible through Discrete Fourier Transform(DFT); and an efficient way to perform DFT by utilizing the symmetry and periodicity is the Fast Fourier Transform(FFT). Feel free to correct me if I am wrong
@B-System
@B-System 3 жыл бұрын
@@AhsanAli-fr4ok The pointwise representation would be what is meant by Discrete in this case, so I believe you are correct here.
@shobhitverma4221
@shobhitverma4221 3 жыл бұрын
Never had an recommended video with this much of a knowledge gain
@brendanmitchell4581
@brendanmitchell4581 2 жыл бұрын
Really awesome video. Right on my level, understandable but challenging enough to make me think. My mind was kinda blown a couple times! Really well done! For me, the one extra thing I'd love to see is an explanation of the connection between this algorithm and the arithmetic or discrete Fourier Transform. I think of a Fourier transform as a method for viewing data or functions from the time domain in the frequency domain. This video outlined a method for evaluating polynomials at the roots of unity, but it isn't obvious to me that that is equivalent to a transformation to frequency space. At first glance, they seem like completely different problems. After some work I was able to convince myself that they were equivalent (and experimentation confirms it) but I would love to see a follow up video to solidify that connection in my mind! Again, awesome work and thanks for a great video!
@eric3813
@eric3813 2 жыл бұрын
Damn, i just found that Video and got SOO MUCH MORE insight in the magic behind FFT! Thank you so much!!
The Discrete Fourier Transform: Most Important Algorithm Ever?
29:24
Mom Hack for Cooking Solo with a Little One! 🍳👶
00:15
5-Minute Crafts HOUSE
Рет қаралды 23 МЛН
How to treat Acne💉
00:31
ISSEI / いっせい
Рет қаралды 108 МЛН
99.9% IMPOSSIBLE
00:24
STORROR
Рет қаралды 31 МЛН
Une nouvelle voiture pour Noël 🥹
00:28
Nicocapone
Рет қаралды 9 МЛН
But what is the Fourier Transform?  A visual introduction.
20:57
3Blue1Brown
Рет қаралды 10 МЛН
Coding Adventure: Sound (and the Fourier Transform)
43:31
Sebastian Lague
Рет қаралды 457 М.
What is Jacobian? | The right way of thinking derivatives and integrals
27:14
How PNG Works: Compromising Speed for Quality
32:00
Reducible
Рет қаралды 643 М.
But what is a convolution?
23:01
3Blue1Brown
Рет қаралды 2,8 МЛН
Fast Inverse Square Root - A Quake III Algorithm
20:08
Nemean
Рет қаралды 5 МЛН
3. Divide & Conquer: FFT
1:20:52
MIT OpenCourseWare
Рет қаралды 322 М.
The more general uncertainty principle, regarding Fourier transforms
19:21
How Computers Draw Weird Shapes (Marching Squares)
28:00
Reducible
Рет қаралды 412 М.
Mom Hack for Cooking Solo with a Little One! 🍳👶
00:15
5-Minute Crafts HOUSE
Рет қаралды 23 МЛН