Hello friends, this is my first ever blog on Code forces. Few days back, in my Design of Algorithms lecture, Fast Fourier transform was taught and I was having some difficulty grasping it. I have learnt it now from various sources like CLRS and Emaxx and thought to make it easy for others as well. :) Here I present to you a very fundamental approach to understanding what fast Fourier transform does.
Let us try to multiply 2 polynomials of degree n, what is its time complexity if we multiply the polynomials as we did in high school? We would have to multiply every coefficient corresponding to every power of x. This Naive Approach, as we can see takes O(n^2) time. Now we ask ourselves the question that underlies the Design And Analysis of Algorithms, Can We do better?
As it turns out, we can. Using the Fast Fourier transform, we can do this task and bring back the complexity to O(n*log(n)) complexity. But, that is far now as we shall now see the Discrete Fourier Transform, the basis for FFT. Well, FFT is just an optimization of DFT in which we store previously calculated values and use them to compute the current values. Going too far, am i not? I must restrict the discussion of FFT her and concentrate on DFT for the time being.
What is DFT? - Before answering this, just think, can we retrieve a polynomial y = P(x)of degree n if we know values of y for (n+1) values of x ? Yes certainly we can, because we get n+1 distinct linear equations and that many number of unknown, we can retrieve the value. - So, suppose I need C(x) = A(x)*B(x), I need the values of A(x) and B(x) at 2*n+1 points to calculate all the coefficients of C, which is the result. Now, How much time does this take? If we do it optimally using HONOR's rule, it takes us (2*n+1) computations for computing values for each of C,A,B. And each computation takes O(n) time if we compute it optimally by applying HONOR's rule, which goes like this: Suppose, I have to calculate the value of 10+6*x+6*(x^2)+3*(x^3), I will compute 3*x then add 6 to it. which makes it (3*x+6) and then multiplying it with x, we get 3*x^2+6*x. I think you guys have guessed where this is going? See how small changes in this make life so much easier!!! :) - As I have already mentioned, there are 2*n+1 maximum computations with each computation taking n computations in itself. This takes our complexity to O(N^2), which is as worse as our naive algorithm, but what DFT has done here is that it has provided us with an idea of how to get to that O(N*log(N)) solution, How you ask, keep reading, and we will see. :)
Now Let us move to Fast Fourier Transform Here I think all have prerequisite knowledge of complex numbers and how they are represented as vectors on the plane. If not, please revise it here. Here, I am going to provide one very important property of the nth roots of unity. which is :
