(多项式在多个点的求值) 我们已经看到， 运用霍纳法则，如何在O(n)时间内求出次数界为n的多项式在单个点的值。同时，我们也发现，远用FFT能在O(n lgn)时间内求出这样的一个多项式在所有n个单位复数根处的值。现在我们就来说明如何在O(nlg2n)时间内，求出一个次数界为n的多项式在任意n个点的值。
为了做到这一点，我们将假设下面未经证明的结论:当一个这样的多项式除以另一个多项式时，我们可以在O(n lgn)时间内计算出该多项式的余式。例如，多项式3x3 +x2一3x+1除以x2+x+2,余式为
给定一个多项式
的系数表达和n个点x0,x1,...,xn-1，我们希望计算出nk=0个值A(x0), A(x1), ...，A(xn-1)。对0≤i≤j≤n-1，定义多项式
和多项式
。注意到，Qij(x)次数至多是j- i。
的系数表达和n个点x0,x1,...,xn-1，我们希望计算出nk=0个值A(x0), A(x1), ...，A(xn-1)。对0≤i≤j≤n-1，定义多项式和多项式。注意到，Qij(x)次数至多是j- i。 a.证明:对任意点z, A(x) mod (x-z)=A(z)。
b.证明: Qk(x)=A(xk), 以及Q0,n-1(x)=A(x)。
c.证明:对i≤k≤j,我们有Qik(x)=Qij(x) modPik(x),以及Qkj(x)=Qij(x)mod Pkj(x)。
c.证明:对i≤k≤j,我们有Qik(x)=Qij(x) modPik(x),以及Qkj(x)=Qij(x)mod Pkj(x)。
d.给出一个运行时间为O(n lg2n)的算法，以求出A(x0), A(x1), ...，A(xn-1)。
