News for hackers. Stuff that matters.
Re:How to multiply polynomials in Θ(n log n) time by tgb on Monday September 07, 2015 @07:50PM (#10183534)
Fun article, but it was missing a little bit that took me a minute to get. So if you're already familiar with fourier transforms, this might be the missing piece to this article:

Multiplication of polynomials when expressed in the domain of "array of coefficients" is a convolution operation: really you're summing (AB)_k = sum_{i=0}^k A_i B_{k-i} to find the kth coefficient of the result. The indices for B go backwards to those of A and they add up to the fixed quantity k, so we're just looking at a discrete convolution of these two arrays.

And what does Fourier Transform do? It turns convolutions into point-wise multiplication in the 'time' domain. The convolution started as an n^2 operation but the point-wise multiplication is n, so we're left with the FFT time of n log n. So this is another instance of the "formulate problem as a convolution, FFT, perform point-wise multiplication in the time domain, inverse FFT, done" class of algorithms.

(I got stuck a while trying to figure out how polynomial multiplication is convolution. Literally it's point-wise multiplication of two functions, not a convolution, so everything seemed backwards.)

Re:How to multiply polynomials in Θ(n log n) time by rhaps0dy on Tuesday September 08, 2015 @03:56AM (#10184493)
This is mentioned in the article in the problem explanation section, but quickly and just passing by. I'll put it right at the beginning where it belongs. Thanks!

I had not understood properly on first read of your comment, but you did not mean what is on the post at all. I'll include this insight somehow :)

Don't you mean signal domain though?

Re:How to multiply polynomials in Θ(n log n) time by tgb on Tuesday September 08, 2015 @10:01AM (#10185695)
Yeah I messed that domain up. Thanks.