Timeline for Snowball Question FFT
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 23, 2013 at 20:48 | vote | accept | lars | ||
| Oct 20, 2013 at 20:03 | comment | added | lars | The key seems to be that the x^a and x^b have coefficients of 1; else coefficient of x^k wouldn't count the number of pairs where a_i + b_j = k. | |
| Oct 20, 2013 at 0:20 | comment | added | Yuval Filmus | Re your other comment, I agree that an argument is required, but only if you want to be very formal. Otherwise, I suggest you try a few examples and see how it works. | |
| Oct 20, 2013 at 0:20 | comment | added | Yuval Filmus | Here $x^k$ is a monomial ($x$ is known as a "formal variable"). You can also think of it as a polynomial having a single monomial. I suggest you go over the FFT algorithm again - they must have covered polynomials when they discussed the algorithm, especially given the application to multiplying univariate polynomials. | |
| Oct 19, 2013 at 23:29 | comment | added | lars | Finally, you need an argument to go from Each pair i,j satisfying $a_i+b_j=k$ contributes one term $x^k$ to the polynomial on the right. To the claim that the coefficient of $x^k$ = number of pairs that equal $k$ | |
| Oct 19, 2013 at 23:23 | comment | added | lars | Moreover, what is $x^k$? Is it a coefficient? | |
| Oct 19, 2013 at 23:21 | comment | added | lars | First you didn't even try to answer my specific questions. And now we have 3 summation signs, where there were none in the solution. So I am now more confused. | |
| Oct 19, 2013 at 23:11 | history | answered | Yuval Filmus | CC BY-SA 3.0 |