The following is the recursive FFT procedure of Algorithm for evaluationg a polynomial of length $N$ at $N$ Fourier points.
Algorithm (FFT - fast Fourier transform).
Input arguments.
$ \ \ $ integer $N=2^m$
$ \ \ $ polynomial $\alpha (x)=\sum_{i=0}^{N-1}\alpha_i x^i$ $ \ \ $ primitive $N$th root of unity $\omega$Ouput argument.
$ \ \ $ array $\textbf{A}=(A_0, \dots , A_{N-1})$ where $A_k=\alpha(\omega^k)$Auxiliary data.
$ \ \ $ integer $n=\frac{N}{2}$
$ \ \ $ polynomials $b(x)=\sum_{i=0}^{n-1}b_ix^i, c(x)=\sum_{i=0}^{n-1}c_ix^i$$ \ \ $ arrays $\textbf{B}=(B_0, \dots , B_{n-1}), \textbf{C}=(C_0, > \dots , C_{n-1})$
procedure FFT($N, \alpha (x), \omega , \textbf{A}$);
$ \ \ $ if N=1 $ \ \ \ \ $ then
$ \ \ \ \ \ \ \ \ $ {Basis.} $A_0 > :=\alpha_0$
$ \ \ \ \ $ else
$ \ \ \ \ $ begin
$ \ \ \ \ \ \ \ \ $ {Binary split.}
$ \ \ \ \ \ \ \ \ \ \ $ $n:=\frac{N}{2};$
$ \ \ \ \ \ \ \ \ \ \ $ $b(x):=\sum_{i=0}^{n-1}\alpha_{2i}x^i;$
$ \ \ \ \ \ \ \ \ \ \ $ $c(x):=\sum_{i=0}^{n-1} \alpha_{2i+1}x^i;$
$ \ \ \ \ \ \ \ \ $ {Recursive calls.}
$ \ \ \ \ \ \ \ \ \ \ $ FFT($n, b(x),\omega^2, \textbf{B}$);
$ \ \ \ \ \ \ \ \ \ \ $ FFT($n,c(x), \omega^2 , \textbf{C}$);
$ \ \ \ \ \ \ \ \ $ {Combine.}
$ \ \ \ \ \ \ \ \ \ \ $ for $k:=0$ until $n-1$ do
$ \ \ \ \ \ \ \ \ \ \ $ begin
$ \ \ \ \ \ \ \ \ \ \ \ \ $ $A_k:=B_k+\omega^k \times C_k;$
$ \ \ \ \ \ \ \ \ \ \ \ \ $ $A_{k+n}:=B_b-\omega^k \times C_k$
$ \ \ \ \ \ \ \ \ \ \ $end
end
I tried to implement the FFT algorithm at an example but I got stuck...
We have the polynmial $\alpha (x)=x^3+2x^2+5x+3$. ($N=2^2$)
FFT($4, \alpha (x), \omega \textbf{A}$)
$ \ \ \ \ $ $n=2$
$ \ \ \ \ $ $b(x)=3+2x$
$ \ \ \ \ $ $c(x)=5+x$
$ \ \ \ \ $ FFT($2, b(x),\omega^2, \textbf{B}$)
$ \ \ \ \ \ \ \ \ $ $n=1$
$ \ \ \ \ \ \ \ \ $ $b(x)=3$
$ \ \ \ \ \ \ \ \ $ $c(x)=2$
$ \ \ \ \ \ \ \ \ $ FFT($1,b(x), \omega^2, \textbf{B}$)
$ \ \ \ \ \ \ \ \ \ \ \ \ $ $B_0=3$
$ \ \ \ \ \ \ \ \ $ FFT($1, c(x), \omega^2, \textbf{C}$)
$ \ \ \ \ \ \ \ \ \ \ \ \ $ $C_0=2$
$ \ \ \ \ \ \ \ \ $ $k=0$
$ \ \ \ \ \ \ \ \ \ \ \ \ $ $B_0=B_0+\omega^0 \cdot C_0=5$
$ \ \ \ \ \ \ \ \ \ \ \ \ $ $B_2=B_0-\omega^0 \cdot C_0=1$
$ \ \ \ \ \ \ \ \ $ $k=1$
$ \ \ \ \ \ \ \ \ \ \ \ \ $ $B_1=B_1+\omega^1 \cdot C_1$
Is it correct so far?