Write an n2 program to do lagrangian interpolation can x55

Question

Problem

1. Write an N₂ program to do lagrangian interpolation.

2. Can x55 be computed with fewer than nine multiplications? If so, say which ones: if not, say why not.

3. List all the polynomial multiplications performed when the divide-and-conquer • polynomial multiplication method described in the text is used to square 1 + x + x² + x³ + x⁴ + x⁵ + x⁶ + x⁷ + x⁸.