The Fast Fourier Transform (FFT): Most Ingenious Algorithm Ever?
Vložit
- čas přidán 1. 05. 2024
- 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.).
Support: / reducible
This video wouldn't be possible without the open source manim library created by 3blue1brown: github.com/3b1b/manim
Here is link to the repository that contains the code used to generate the animations in this video: github.com/nipunramk/Reducible
Elegant proof that the matrix used in the proof that (d + 1) points uniquely define a degree d polynomial is invertible: math.stackexchange.com/questi...
Music:
Lift Motif by Kevin MacLeod is licensed under a Creative Commons Attribution license (creativecommons.org/licenses/...)
Source: incompetech.com/music/royalty-...
Artist: incompetech.com/
All other music by Aakash Gandhi
SVG Attributions:
Earth: Designed by Flat Icons from www.flaticon.com, CC BY 4.0 creativecommons.org/licenses/..., via Wikimedia Commons
GPS: Icons made by www.flaticon.com/authors/pause08 from www.flaticon.com/
Wireless Comms: Design inspired by svgsilh.com/image/297434.html
For those of you who want to see me break down further how the FFT Implementation works: checkout out this video: czcams.com/video/Ty0JcR6Dvis/video.html
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."
:) first to reply to u
@@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.
Was just about to comment the error but saw you already had it! Great video and really clear too!
@@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!
Great video. Now I got it to work. Maybe you could add a correction in the video though?
"If your mind isn't blown, you weren't paying attention."
I promise, I tried.
it's too much for my 3 am brain lol
Tried to blow your mind, or tried to pay attention? I tried both, still working on it.
Me too! I knew I was in trouble when he started with the part "everybody" understands -- polynomial math. All the sudden I got the feeling like I had boarded a plane, and it was starting to taxi to the runway, and the flight attendant just announced that we're headed to ... wait.. where?!? Uh oh!
@@nickwallette6201 Same, I barely remembered what polynomials were, I last studied them was like 7 years ago when I was in Middle school.
Oh I paid attention that’s when my mind started trying to blow not because it understood the concept but because it tried so hard to understand.
I think I just wrote a complicated sentence🤔
Who came here from 3blue1brown and fell in love with this channel?
That shoutout was awesome!
I didn’t know they are from 3blue1brown, but now that you mention it they remind me of one another
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!
Me too!
@@shadowthehedgehog2727 they are different but using the same tools
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.
That sounds so cool!
yes, further optimization by using photonics !
sounds like a nice experiment for undergrad students
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 😭
As a physics undergrad with some knowledge about FORTRAN and Assembly, and made in '72.... WOAH
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
I was thinking as I saw that: "he shouldn't have used the exclamation point there."
LOL... i wonder, i think in the spanish fonts they have an exclamation that is flipped upside down :p
Exclamation ! math is hard....XD
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?
Exclamation ! well deserved
I think the most impressive thing about this Fourier Transform related video is that it never mentions words "sine" or "frequency".
i mean they do mention frequency at the start but i see what you mean
Fourier transform and fast Fourier transform are different
or integrals hell
@@owenpenning1597 but they gave similar results
Often seems like e^jt is the more fundanmental concept, cos and sin are just the real and imaginary parts of that
Holy crap! How has it already been 30 mins!?! You know it's a good video when you completely loose track of time!
Thank you so much for this comment! I love hearing comments like this one.
I didn't realize, that's amazing!
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
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 CZcams 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.
You need to learn the FFT from an engineer's point of view. This is more math/algorithm than you likely need.
@@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.
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.
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
@@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.
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 CZcams by quite a bit (imo). Keep it up! See you when you've totally blown up :)
I smell Grant's python library at work (oh, its credited in description, never mind)
I thought soo!!!
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.
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!
@@Zcon18 which post ?
@@jaikumar848 the community post from a couple of days ago
I'd love to see a video on union-find. One of the most underrated data structures. Its so incredibly useful for graph problems.
@@jamesbalajan3850 absolutely
Astonishing how the quality side by side with the level of complexity of your videos keeps improving further and further. Thx.
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!
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.
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!
Beyond excellent! Now I must spend my day binging your entire content. Can't wait for more already!
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.
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
the creator of these animations has a super loaded patreon page and other stuff. he is doing great!
No reason to shit on other creators though. A lot of experience and planning can go into a makeup tutorial too.
I absolutely love this. Complex math being presented in an intuitive way makes it so much more accessible. Keep up the good work!
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!
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!!!
WOW. I'm literally blown away. This video is EXCELLENT. PLEASE keep doing what you're doing! Instant share.
Thank you! Don't plan on stopping any time soon :)
Literally?
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!
Wow just wow, this has gotta be the best video of the year for me. Absolutely astounding work!
This is the most elegant way to explain FFT I have ever encountered. Brilliant!
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.
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!
Haha that's awesome! Always a great time to learn about the FFT!
I never knew Applejack's brother was into algorithm theory!! Awesome :^)
I think that has something to do with polynomial multiplication or something, ehhhemmm...
Thanks for taking the time to make this video
What an awesome presentation .. also love the fact that you share your code for people to gain the knowledge you have. So hats off 👍
2 minutes in and i love it already
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
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 😀
This was not only interesting, it was really well explained AND pleasantly animated. You did more in 30 mins than my teacher did in a year, subbed xp
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.
dude, this channel is really well made! im definitely subbing for more
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.
You've just discovered a future video I'm planning on error correcting codes (Shh don't tell anyone :P).
@@Reducible Convolutional error correcting codes too, pls?
@@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 :)
Shamir's secret sharing algorithm is based on that same property.
This is absolutely brilliant !
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!
Thank you so much for the beautiful arguments you used to show the magnificence of the FFT algorithm!
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!
This guy was my TA at Cal ❤️❤️
Go bears! :)
John Wick is at caltech now?
Im so glad that I found this channel, keep making the good stuff!.
Insanely brilliant idea separated into simple concepts! Great video.
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.
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.
I'm glad I found this channel, it's really beautiful. Good luck!!
Surely, one of the best explanations of FFT I have ever listened to.
I was blown by the hability to make me lose track of the topic faster than any teacher, engineer and mathematician combined.
sarcasm?
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 :)
Did 3b1b? Seems like I missed that. Where did he give that shoutout?
@@JoJoModding community post
@@sainathsingineedi2922 Patreon?
@@JoJoModding czcams.com/video/g8RkArhtCc4/video.html
Incredible the way you explain such a complex topic. I could follow all of the details.
Great job!
This channel is going to blow up and I'm excited!
One of the first videos on CZcams 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.
Thank you so much for this awesome comment!
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.
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.
Never had an recommended video with this much of a knowledge gain
Beautifully constructed tutorial, well done. I learned a lot!
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.
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!
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 ^^
This is possibly the best explanation of the FFT and IFFT on CZcams.
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!
I was hopeless at maths at uni and even I could follow this. Fantastic explanation!
I couldn't fully follow this :(
I had Linear algebra at uni tho...
I still cant :(
i had to stop after 20 minutes because my mind was overloaded...
So great that 3b1b just gave this video a shoutout, it's super underrated!
Hell yeah
This is one of the best explanations I have ever seen. Thank you
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!
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.
Apologies, I made a rookie mistake and forgot to do that before uploading this video -- just pushed the code for this video.
Thank you kindly. Keep up the amazing work!
Agreed. Felt like a masterclass. I wish I had this video back in college when I covered the material.
You can find the code (with explanation too) over here
cp-algorithms.com/algebra/fft.html
@@shantanurahman5084
Thanks a lot. I meant the code for the animation, not that of the FFT.
This is beautiful. Thank you for this astounding work :D
Thank you so much for an excellent presentation on a beautiful and complex topic. I was going to ask what inspired the dissection using polynomials, but you already left references in the description! Absolutely fantastic!
This video is both useful and beautiful.
this is way over my head but I appreciate things being talked about in terms of computability not just in the abstract
So clearly explained and well demonstrated! Thank you so much for your work.
You managed to make me fall in love with the FFT ahahaha! I already knew it’s use cases, theoretical bases and all, but the explanation you provided is simply perfect!
Really neat video! Speaking from experience, this must have taken forever to make haha. Brilliantly explained and produced :)
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!
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…
infourierted
Damn, i just found that Video and got SOO MUCH MORE insight in the magic behind FFT! Thank you so much!!
This is single-handedly the best explanation on the topic I have ever seen. Perfect for college students!!
You can never tell how CZcams search algorithm leads you to the right place
It uses FFT
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.
Brings back memories. Thank you! Nice tribute and explanation..
Love it! Thank you for this amazing presentation, really enjoyed it!
"We'll take a look at something you're all familiar with. Polynomial multiplication."
1:53 minutes in and you already lost me lmao
bruh
We've gone too deep 😂
This is awesome ❤️
This video is worthy of thoroughly watching multiple times !!
Wow, I am very pleased to see such substantial inspiring video showing up here, thank you.
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!
same man.
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!
I really enjoyed the explanation and how elegant it is.
Great video :)
Beautifully described and explained. This is the Best video on FFT on youtube which describes the underlying concepts of FFT.
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. =)
Yeah another astute commenter like yourself noticed this, I updated my pinned comment with this note to address this. Sorry about that!
You are going to make it big. Keep up the good work.
spent 6 hours figuring this out, and it blows my mind! What a great algorithm! This Fourier transform has a lot of applications, mostly prominent in signal processing. An ingenious algorithm to the core.
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.
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.
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.
Amazing how smart and mindblowing the idea behind the algorithm is despite not using any advanced maths - all the prerequisites are covered in 1st grade course, yet it's all so cool and unobvious. Also, this video is a really cool presentation of it - i'm definitely subscribing for more content like this.
Pretty much the best explanation out there for this topic... Thank you!
This... this is a perfect example of FM technology.
13:30 Thats it i'm lost. Good video man! Will have to review from top.
batner Same Here
This is an incredible video! Congratulations
Great video. Nicolet launched the 440 FFT dual channel analyser in the mid 70’s whilst I was half way through my eng degree. It was lust at first sire from me, and lead me to a wonderfull career in signal analysis and machine condition monitoring.
holy crap wow
this video really made things click for me
i've never gotten goosebumps from understanding something before
but i just did
I’m going to watch this until i understand it
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!
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
@@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! :)
It's amazing how well explained is this. I have the immediate need to subscribe
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!