1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

For testing, you can use SageMath very easily;

you had erros on

$$A(x_0) = 0, A(x_1) = 16, A(x_2) = 85, A(x_3)=208, \\B(x_0) = -1, \color{red}{B(x_1) = -2}, \color{red}{B(x_2) = -5},\color{red}{B(x_3) = 8}$$

    R = PolynomialRing(QQ, 'x')
    A = 3 *x^2-4*x+1
    B = x -2
    a0 = A(1)
    a1 = A(3)
    a2 = A(6)
    a3 = A(9)
    b0 = B(1)
    b1 = B(3)
    b2 = B(6)
    b3 = B(9)
    c0 = a0*b0
    c1 = a1*b1
    c2 = a2*b2
    c3 = a3*b3
    
    print( a0,a1,a2,a3)
    print( b0,b1,b2,b3)
    print( c0,c1,c2,c3)
    
    f = R.lagrange_polynomial([(1,c0),(3,c1),(6,c2),(9,c3)])
    f

Outputs

0 16 85 208
-1 1 4 7
0 16 340 1456
3*x^3 - 10*x^2 + 9*x - 2
$\endgroup$
2
  • $\begingroup$ Thank you Kelalaka! So it was just some wrong numbers. $\endgroup$ – user777 Mar 17 at 21:28
  • $\begingroup$ Yes, if you need to do only hand, double-check everything. $\endgroup$ – kelalaka Mar 17 at 21:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.