I'm trying to apply the following algorithm from DPV's textbook to an example to see how it works. First, the algorithm is as following:
Algorithm [DPV, p. 60]
Input: Coefficients of two polynomials. A(x) and B(x), of degree d.
Output: Their product $C = A . B$
- Selection: Pick some points $x_0, x_1, x_2, ..., x_{n-1}$ where $n\geq 2d+1$
- Evaluation: Compute $A(x_0), A(x_1), ...., A(x_{n-1})$ and $B(x_0), B(x_1), ...., B(x_{n-1})$
- Multiplication: Compute $C(x_k)=A(x_k) \times B(x_k)$ for all $k=0, 1, ..., n-1$
- Interpolation: Recover $C(x) = c_0 + c_1 x + c_2 x^2 + .... + c_{2d} x^{2d}$
Now, I took an example $A(x) = 3x^2 -4x + 1$ and $B(x) = x-2$. The output should be $C(x) = 3x^3 - 10 x^2 + 9 x -2$. Now, the algorithm first choose an arbitrary points, so I will choose the following: $x_0 = 1, x_1 = 3, x_2=6,$ and $x_3 = 9$. Now, we evaluate the A(x_i) and B(x_i) for $i=0, 1, 2$ and $3$. Thus, $A(x_0) = 0, A(x_1) = 16, A(x_2) = 85, A(x_3)=208, B(x_0) = -1, B(x_1) = -2, B(x_2) = -5,$ and $B(x_3)=-8$. Thus, we compute $C(x_i)$ for $i=0, 1, 2,$ and $3$. So, we get $C(x_0) = 0, C(x_1) = -32, C(x_2)=-425,$ and $C(x_3) = -1664$.
Now, I have $x_0=1, x_1=3, x_2=6,$ and $x_3=9$ and the corresponding $C(x_0) = 0, C(x_1) = -32, C(x_2) = -425,$ and $C(x_3)=-1664$. This I will apply the polynomial interpolation to get the output. I used this page to compute the coefficients of C(x). So, I got the output as following: $-3x^3 + 7x^2 - 5x + 1$ but it should be this one: $C(x) = 3x^3 - 10 x^2 + 9 x -2$. So, where is the problem? Is it because finding interpolation cannot be in exact so the coefficient is an approximation to the exact one.