fft

Fast Fourier Transform

Fast algorithm for the fourier transform in \(O(n\log n)\).

def fft(x):
    n = len(x)
    if n == 1:
        return x
    x_e = fft(x[::2])
    x_o = fft(x[1::2])
    roots_of_unity = np.exp(-1j * 2 * np.pi * np.arange(n) / n)
    return np.concatenate([x_e + roots_of_unity[:n//2] * x_o,
                           x_e + roots_of_unity[n//2:] * x_o])

Above works for \(n\) being a power of 2.