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