快速傅里叶变换
int * multiplication(int a[], int b[], int size_a, int size_b)
{
int i, j;
for (i = 0; i < size_a + size_b; ++ i) c[i] = 0;
for (i = 0; i < size_a; ++ i)
for (j = 0; j < size_b; ++ j)
c[i+j] += a[i]*b[j]
return c;
}
It will take n^2 operations.
♥ To reduce that, we can transform the coefficient representation to
sample representation. Then do the multiplication, then transform back.
Sample representation: given {(x_0, y_0), ..., (x_n, y_n)}, there is exactly
one polynomial p of degree n s.t. p(x_i) = y_i for all i. Thus, {(x_0, y_0)
, ..., (x_n, y_n)} can represent a n-degree polynomial.
To multiply two polynomials, just multiply their sample values. If we are
multiply two polynomials of degree n, we need to start with 2n+1 sample
values for each polynomials, since that is how many we need to uniquely
represent the product polynomial. This obvious takes O(n).
If we can choose the sample points carefully (e.g., FFT), we can do the
transformation in O(n \log n). Thus, the whole multiplication takes O(n \log
n).
