将数组看成多项式的系数$ A(x)=a_0+a_1x+...+a_{n-1}x^{n-1} $。
点值 $y_0, y_1,...,y_{n-1} $, 其中 $y_i=A(x_i) $。
令 $w=e^{frac{2ipi}{n}}, x_i=w^i $
将A(x) 按 x的次幂 奇偶分组 A(x)=(a_0+a_2x^2+a_{n-2}^x_{n-2}) + (a_1x+a_3x^3+...+a_{n-1}x^{n-1}) = A_0(x) + xA_1(x)
k'=k<n/2 A0 + w^k A1
k'=k+n/2 A0 - w^k A1
分治递归，完成。 n扩展为2的幂。
蝴蝶。
也可三分，也有蝴蝶。 A(x)=A0+xA1+xxA2 A0+w^k'A1 + w^2k'A2
矩阵形式。A_{ij} = w^{ (i-1)(j-1) } 。 有逆矩阵 A'_{i,j}=w^{ -(i-1)(j-1) } 。故有逆变换。