The Algorithm
The Algorithm
DFFT(P:Array;k,m:Integer):Array;
begin
If k=0 Then
DFFT[0]=P[0];DFFT[1]=P[0];
Else
Evens = DFFT(EvenElemOf(P),k-1,2m);
Odds = DFFT(OddElemOf(P),k-1,2m);
For i := 0 to 2k-1-1 Do
x := Odds[j]*wmj
DFFT[j] := Evens[j] + x
DFFT[2k-1+j] := Evens[j] - x
End For
End If
end