Hello i try to implement FFT (Fast Fourier Transform) with python. But it wrong?. It’s simple Cooley and Tukey algorithm.
My problem: result vector of my implementation and np.fft.ftt
does not match
My FFT implementation:
def fft(x):
N = len(x)
if N <= 1:
return x
else:
even = ctsfft(x[0::2])
odd = ctsfft(x[1::2])
T = [0] * N
for k in range(N // 2):
twiddle = np.exp(-2j * np.pi * k / N)
T[k] = even[k] + twiddle * odd[k]
T[k + N // 2] = even[k] - twiddle * odd[k]
return np.array(T)
To reproduce the problem (Repl It)
P.S.
If you can see first (0 index) element is same both but others no. Why? I don’t know.
Also i tried normalization and it also not same
I try to rewrite algorithm from wiki I works but result don’t same to numpy
I try to search answer where i have bug in llama
I searched answer in source code of numpy and also doesn’t find
Proger is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.