Iterative Algorithm
Iterative Algorithm
For i := 0 To n-2 By 2 Do
T[i] = p[f(i)] + p[f(t+1)];
T[i+1] := p[f(i)] - p[f(t+1)];
End For
m := n/2; n := 2;
For k := lg n - 2 To 0 By -1 Do
m := m/2; n := 2*n;
For i := 0 To (2k-1)*n By n Do
For j := 0 To (n/2)-1 Do
x := wmj * T[i+n/2+j];
T[i+n/2+j] := T[i+j] - x;
T[i+j] := T[i+j] + x;
End For
End For
End For