fft παίρνει ως όρισμα μια λίστα (ή μια ακολουθία)
[a0,..aN-1] όπου N είναι μια δύναμη του 2. fft επιστρέφει τη λίστα [b0,..bN-1] τέτοια ώστε,
για k=0..N-1
fft([a0,..aN-1])[k]=bk=
N-1
∑
j=0
xjωN-k·
j
όπου ωN είναι μια αρχική N-στη ρίζα της μονάδος.
Είσοδος :