FFT Example: Unraveling the Recursion

I guess most of you will watch this video after watching the main video. This video is meant to go a little deeper into how the actual FFT implementation works to give a super quick summary of the main ideas from the first video. motivated the idea of ​​fft via polynomial multiplication, the key idea is that polynomial multiplication is much faster when we use a point-valued representation of polynomials, but the question we had to address right away is how do we convert polynomials from a representation of coefficients to a representation of the value of this conversion was the fast Fourier transform where, if we choose our set of evaluation points as roots of unity, we formulate a beautiful recursive algorithm to evaluate polynomials in single or log-n At the time, this was the implementation of that algorithm, so I'm going to be honest when I first learned FFT in an algorithms class in college and saw this implementation.

This is basically, in a nutshell, what happened, no matter how hard you try to understand everything up to this point. I feel like most people will say: with me and get lost in the details whenever you are lost. One of the most useful things you can do is to fully break down a specific

example

. Let's do just that, suppose I provide the following input to the function fft representing a polynomial of degree 3 that we defined first. n is equal to 4, this does not meet the base case criteria, so we proceed to define omega as e to the power of 2 pi i over 4, which is equivalent to the complex number i, what this means for us is that this will ensure that the roots of unity at which we evaluate the polynomial are the fourth roots of unity that correspond to the following points on the unit circle, then we define p e as the even degree terms of five and two, which makes p e let the linear function five plus two x p or be similarly defined with terms of odd degree three and one, making it another linear function three plus inputs, let's see what happens in the recursive call in terms of even degree here we define n as 2 and then we define omega as e to the power of 2 pi i over 2, which is equal to negative 1, which means that the polynomial will be evaluated at the second roots of unity or at the next points on the unit circle we then proceed with another division of the polynomial in terms of even and odd degrees, which are now just constants.

We pass the zero degree polynomials to two more recursive calls. Both recursive calls end up reaching the base case and returning whatever input was passed. in the outputs of these recursive calls they are then assigned to the variables y and and and or now we can proceed to define our output and for this call, which is initially a two-element list of zeros, we proceed to our for loop whose first line assigns the the index zero of y is the zero index of y e plus omega to the power of zero multiplied by the zero index of y or this is essentially the evaluation step required for the root of unit number one, which is omega to the power of 0.

This expression ends up being 7, which updates the list and consequently, going to the second line of the for loop, we assign the first index of the list and as the zero index of y e minus omega raised to the power of zero multiplied by the zero index of y or this corresponds to the evaluation step for the root of unity number two which is omega to the power of one and the negative pair of our first root of unity the value of this expression is 3 which is then updated in the list now we return this value after finishing the recursive call in terms of even degree we proceed to do the same process in the recursive call in terms of odd degree the logic is exactly the same but with a different input, so I will let you follow the animations on your own Now let's move on to the step key after getting the return values ​​from the recursive calls on the polynomials of even and odd degree terms.

This is then assigned to the variables y and y and o in our current call. Now, when we define our list y, it has four values. all of which are initially zero, then we proceed to the for loop in the first iteration, the first line maps the zero index of y to the zero index of y e plus omega raised to zero multiplied by the zero index of y o, this is essentially evaluating the polynomial original in the first root of the unit omega raised to 0 and the expression gives us the value 11. Moving now to the second line of the for loop in our first iteration, we now want to assign the second index of y to zero. index of y e minus omega raised to zero multiplied by the zero index of y or this is now evaluating the third root of unity omega squared which is the negative pair of the first root of unity the value of this expression is 3 which is now the second index of our list and output now we go to the second iteration of the for loop which begins by assigning the first index of y as the first index of y e plus omega raised to 1 multiplied by the index 1 of y o, this corresponds to valuing the second root of unity in our unit circle, which is simply omega to the power of 1. the value of this expression is the complex number 3 plus 2i, which is now index 1 of our output list in the second line of the for loop that now assign the third index of y to be the first index of y e minus omega raised to one times the index one of y o which evaluates the final root of the unit when evaluated, this ends up being the complex number three minus two i, which is the final element in our output list and now we have the final output of f t in our original degree 3 polynomial as a final sanity check, it is good to try evaluating the polynomial at the fourth roots of unity and verify that the values ​​we get coincide with those calculated by fft, if you do this exercise, you will see that they actually coincide.

That's all for this video and thanks for watching. If you enjoyed the content, please press the Like button to have this content recommended to more people if you wish. For more content like this, be sure to hit the subscribe button and if you'd like to more directly support the work of this channel, check out the Patreon page linked in the description below. See you in the next video.