#!/usr/bin/python3
# Transformation de Fourier discrète, Cooley-Tukey
# Il faut que len(phi) soit une puissance de 2


def fft(phi): # fast Fourier transform
    N = len(phi)
    if N == 1:
        return phi    
    phi_p = phi[::2]   # les composantes avec indices pairs
    phi_i = phi[1::2]  # les composantes avec indices impairs
    Fphi_p = fft(phi_p)   # calcul récursif de la TFD
    Fphi_i = fft(phi_i)
    racines = np.exp(-2 * np.pi * 1j * np.arange(N//2) / N)
    c = np.empty((N), dtype=complex)
    c[:N//2] = Fphi_p + racines * Fphi_i
    c[N//2:] = Fphi_p - racines * Fphi_i
    return c