We have seen how to evaluate a polynomial of degree-bound n at a single point in O(n) time using Horner's rule. We have also discovered how to evaluate such a polynomial at all n complex roots of unity in O(n lg n) time using the FFT. We shall now show how to evaluate a polynomial of degree-bound n at n arbitrary points in O(n lg² n) time.

To do so, we shall assume that we can compute the polynomial remainder when one such polynomial is divided by another in O(nlgn) time, a result that we state without proof. For example, the remainder of 3x³ + x² - 3x + 1 when divided by x² + x + 2 is (3x³ + x² - 3x + 1) mod (x² + x + 2) = 7x + 5.

Given the coefficient representation of a polynomial

and n points x₀, x₁, . . . ,x_n-1, we wish to compute the n values A(x₀), A(x₁), . . . ,A(x_n-1). For?0???i???j???n???1, define the polynomials

and Q_ij (x) = A(x) mod P_ij (x). That Q_ij (x) has degree at most j ? i.

a. Prove that A(x) mod (x-z)=A(z) for any point z.

b. Prove that Q_kk(x)=A(x_k) and that Q_0,n-1(x) =A(x).

c. Prove that for i≤k≤j, we have Q_ik(x)=Q_ij (x) mod P_ik(x) and Q_kj (x) = Q_ij (x) mod P_kj (x).

d.Give an O(nlg² n)-time algorithm to evaluate A(x₀), A(x₁), . . . ,A(x_n-1).

Transcribed Image Text:

Pij (x) = Ik-;(x – xx) %<%3Di Xk)