Быстрое преобразование Фурье Псевдокод?

Question

Целью следующего кода является преобразование полинома из представления коэффициента в представление значения путем деления его на его нечетные и четные степени и последующего рекурсии на меньших многочленах.

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)) 

1. Что для цикла используется для?

2. Почему псевдокод только добавляет меньшие многочлены, не нужно ли их вычитать? (для вычисления A (-x)). Разве это не то, на чем основан алгоритм? Добавление и вычитание меньших многочленов для уменьшения точек в полу? *

3. Почему оцениваются полномочия «w» в отличие от «x»?

Я не слишком уверен, если это принадлежит здесь, так как этот вопрос является довольно математической. Если вы чувствуете, что этот вопрос не соответствует теме, я был бы признателен, если бы вы перенесли его на сайт, где вы считали, что этот вопрос будет более уместным, а просто закрыв его.

* Псевдокод получен от Алгоритмы S. Dasgupta. Page 71.

Answer 1

1. Цикл предназначен для рекурсии.
2. Не нужно добавить для отрицательных x; БПФ преобразуется из пространства времени в частоту.