We have seen how to evaluate a polynomial of degree-bound n at a single point in O(n)
Question:
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 lg2 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 3x3 + x2 - 3x + 1 when divided by x2 + x + 2 is (3x3 + x2 - 3x + 1) mod (x2 + x + 2) = 7x + 5.
Given the coefficient representation of a polynomial
and n points x0, x1, . . . ,xn-1, we wish to compute the n values A(x0), A(x1), . . . ,A(xn-1). For?0???i???j???n???1, define the polynomials
and Qij (x) = A(x) mod Pij (x). That Qij (x) has degree at most j ? i.
a. Prove that A(x) mod (x-z)=A(z) for any point z.
b. Prove that Qkk(x)=A(xk) and that Q0,n-1(x) =A(x).
c. Prove that for i≤k≤j, we have Qik(x)=Qij (x) mod Pik(x) and Qkj (x) = Qij (x) mod Pkj (x).
d.Give an O(nlg2 n)-time algorithm to evaluate A(x0), A(x1), . . . ,A(xn-1).
Step by Step Answer:
Introduction to Algorithms
ISBN: 978-0262033848
3rd edition
Authors: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest