Hello everybody,
Sometime ago I learnt FFT and its application in multiplying numbers. I never understood completely how it works but I sort of understood the way it multiplied numbers.
Now lately I've heard friends of mine talking about FFT and using it in places I couldn't possibly imagine how would FFT help. I'm having trouble understanding what does FFT compute at all. Wikipedia talks about complex sinusoids and I've tried understanding it but I just jump from a huge article to another and get lost in countless definitions and equations.
A classic example of what I mean is the following problem. The editorial talks about FFT but I can't even comprehend what it is saying.
Now I know that FFT involves quite serious mathematical theory that I most likely don't know, since I'm only 10th grade, but as I'm competing quite actively in many competitions I thought that understanding it is quite important.
I would be extremely grateful if someone could help me out in understanding what exactly is this algorithm doing by explaining or pointing me to a place I can learn it from. While Wikipedia often has tons of information, it often lacks simplicity and learning from it directly can be really tough.
I am looking for an explanation that would help me understand the concept and idea of the algorithm, and not code or implemenations.
Thanks in advance :)
The version with the most application in competitive programming is discrete FFT. To put it simply, you're given arrays A0..n - 1, B0..n - 1 and want to compute their convolution, another array c0..n - 1 given as
where you can take the indices modulo $n$ (circular convolution) or define out-of-range elements to be 0 (linear convolution).
This is what it is. Wiki isn't a good source in this case, since it has most use in (pretty much continuous) signal analysis. It also isn't a good idea to try to learn the theory behind it from scratch, since it usually takes a few semesters of calculus.
I remember having googled some lecture notes that described it well, but I don't know where it was...
Could you briefly explain how do you modify the arrays to get linear convolution vs circular convolution?
P.S. Thanks, actually simplifying it in that way really helped me get the idea. Now i'm only wondering how do you make a circular convolution?
FFT convolution is circular by definition. On the reverse, if one needs non-circular, an effort must be taken (usually with padding zeroes)
One thing you should know is that FFT helps you to multiply polinomials, and does it much faster than naive algorithm. And then you actually don't even need to understand why and how it works in order to solve problems. It is not even necessary to understand how we make NlogN from N^2 with divide-and-conquer, and why this divide-and-conquer works at all:)
There are few common "tricks" giving us some ways to use FFT for problem solving. One of them you already mentioned — writing decimal number as a polinomial; this gives you a way to multiply numbers fast. You multiply polinomials, then just calculate value of a product for x=BASE, right?
Other common trick is used in a problem from CF Round#270. If you have 2 polinomials, and you change degrees in one of them by rule deg1[i]=N-deg1[i] (so it looks like reversing of this polinomial), then for every pair (x1^y1, x2^y2) with constant difference of degrees from original polinomials you will now have pair with constant sum of degrees. If you had y1[i]=y2[i], now you have y1[i]=N-y2[i], so y1[i]+y2[i]=N. Multiplying sums up degrees, therefore every such pair will give +x^N to the product (and to count such pairs you just have to look at x^N and it's coefficient). You can further expand this method to solve well-known problem like this:
You are given array A of size N. A[i] is either 1 or 0 for every i. Count number of pairs of indices i,j such that i-j==X and A[i]*A[j]==1 for X=0..N
Using trick with reversing you move from "constant difference" to "constant sum", and then just output some coefficients of product of polinomials.
Look for editorials of some FFT-related problems, and you'll find out some other tips&tricks. Understanding concept of FFT is great, but i don't think that it helps you to discover constant_difference->constant_sum trick by yourself, if you never seen it before.
Thanks a lot, now I get the idea from the analysis :)