以下代码的目的是将多项式从系数表示转换为值表示，方法是将其划分为奇数和偶数幂，然后在较小的多项式上递归。
function FFT(A, w)
Input: Coefficient representation of a polynomials A(x) of degree ≤ n-1, where n
is a power of 2w, an nth root of unity.
Output: Value representation A(w^0),...,A(w^(n-1))
if w = 1; return A(1)
express A(x) in the form A_e(x^2) and xA_o(x^2) /*where A_e are the even powers and A_o
the odd.*/
call FFT(A_e,w^2) to evaluate A_e at even of powers of w
call FFT(A_o,w^2) to evaluate A_o at even powers of w
for j = 0 to n-1;
compute A(w^j) = A_e(w^(2j))+w^j(A_o(w^(2j)))
return A(w^0),...,A(w^(n-1))
for 循环的用途是什么？
为什么伪代码只添加较小的多项式，不需要也减去它们？（计算 A(-x)）。这不是算法完全基于的吗？添加和减去较小的多项式以将点减少一半？*
为什么要评估“w”的幂而不是“x”？
我不太确定这是否属于这里，因为这个问题非常数学。如果您觉得这个问题是题外话，如果您将它移到一个您认为这个问题更合适的网站，而不是仅仅关闭它，我将不胜感激。
*Psuedocode由 S. Dasgupta从Algorithms获得。第 71 页。