快速傅里叶变换(Fast Fourier Transform) Figure 2.7 The fast Fourier transform(polynomial formulation) function FFT(A,w) Input:Coefficient representation of a polynomial A(z) of degree <n-1,where n is a power of 2 w,an nth root of unity Output:Value representation A(w0),...,A(wn-1) if w=1:return A(1) express A(x)in the form Ae(x2)+zAo(z2) call FFT(Ae,w2)to evaluate Ae at even powers of w call FFT(Ao,w2)to evaluate Ao at even powers of w for j=0 to n-1: compute A(w)=Ae(w2i)+wjA.(w2j) return A(w),...,A(wn-1) Source:Algorithms by S.Dasgupta,C.H.Papadimitriou,and U.V.Vazirani 25 快速傅里叶变换 (Fast Fourier Transform) 25 Source: Algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani