Cooley-Tukey Fast Fourier Transform can be complex to implement, if you want to optimize it. A basic version is surprisingly simple, I implemented it for fun in Python a couple of years ago:

    def fft(x):
        N = len(x)
        if N == 1:
            return x
        assert N % 2 == 0
        E = fft(x[::2])
        O = fft(x[1::2])
        X = [None] * N
        for k in range(N // 2):
            tf = np.exp(-2j * np.pi * k / N)
            X[k] = E[k] + tf * O[k]
            X[k + N//2] = E[k] - tf * O[k]
        return X

The Wikipedia article describing it is surprisingly decent: https://en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT_algor...