次のコードの目的は、多項式を係数表現から値表現に変換することです。これは、多項式を奇数乗と偶数乗に分割し、小さい多項式で再帰することによって行われます。
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）を計算するため）。それはアルゴリズムが完全に基づいているものではありませんか？小さい多項式を加算および減算して、ポイントを半分に減らしますか？*
「x」ではなく「w」の累乗が評価されるのはなぜですか？
質問はかなり数学的なものなので、これがここに属するかどうかはあまりわかりません。この質問がトピックから外れていると感じた場合は、この質問を閉じるのではなく、この質問の方が適切だと思われるサイトに移動していただければ幸いです。
*擬似コードはS.DasguptaによってAlgorithmsから取得されました。ページ71。