Alternative Representation of Polynomials

A degree-d polynomial is uniquely characterized by its values at any $d + 1$ distinct points.

We can specify a degree-d polynomial $A(x) = a_0 + a_1x + \cdots + a_dx^d$ by any of the following ways:

1. Use coefficients $a_0, \dots, a_d$

2. Use points $((x_0, A(x_0)), \dots, (x_d, A(x_d))$

The second is more attractive for polynomial multiplication. Since product $C(x)$ has degree $2d$, it is fully determined by $2d+1$ points. Its value at any given point $z$ is just $A(z) \times B(z)$, so polynomial multiplication is linear in its value representation.

But usually polynomials are given with their coefficients so we have to do a bit of translation

Evaluating a polynomial of degree d ≤ n at a single point takes O(n) steps, and so the baseline for n points is $\Theta(n^2)$. We’ll now see that the fast Fourier transform (FFT) does it in just $O(n \log n)$ time, for a particularly clever choice of $x_0, \dots , x_n−1$ in which the computations required by the individual points overlap with one another and can be shared.