고속 푸리에 변환 의사 코드?

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. for 루프는 무엇을 사용하고 있습니까?

2. 의사 코드가 더 작은 다항식 만 추가하는 이유는 무엇입니까? (A (-x)를 계산하기 위해). 그게 알고리즘이 완전히 기반이 된 것이 아닌가? 반으로 포인트를 줄이기 위해 작은 다항식을 뺀 및 추가? *

3. 이유는 "w"의 능력을 평가하고있다 "X"에 반대? 문제는 매우 수학적 때문에이 여기에 속하는 경우

나는 너무 확실하지 않다. 이 질문이 주제와 다르게 느껴지면,이 질문이 더 적절할 것이라고 생각한 사이트로 이동 한 경우 감사하게 생각합니다.

* Psuedocode는 알고리즘에 의해 S. Dasgupta로부터 획득되었습니다. 페이지 71.

Answer 1

1. 루프는 재귀를위한 것입니다.
2. 음수 x를 추가 할 필요가 없습니다. FFT는 시간 공간에서 주파수 공간으로 변환합니다.