def fft(liste):
    N = len(liste)
    if N==1:
        return liste
    pair = []
    impair = []
    for k in range(0,N,2):
        pair.append(liste[k])
    for k in range(1,N,2):
        impair.append(liste[k])
    tfd_pair = fft(pair)
    tfd_impair = fft(impair)
    tfd = [0]*N
    W = numpy.exp(-1j*2*numpy.pi/N)
    N2 = int(N/2)
    for n in range(N2):
        tfd[n] = tfd_pair[n]+tfd_impair[n]*W**n
    for n in range(N2,N):
        tfd[n] = tfd_pair[n-N2]+tfd_impair[n-N2]*W**n
    return tfd
            

import numpy
from matplotlib.pyplot import *

p = 5
N = 2**p
u = numpy.zeros(N,dtype=complex)
k = numpy.arange(N)
u = numpy.sin(2*numpy.pi*k/N)+\
    0.5*numpy.sin(4*numpy.pi*k/N)+0.25*numpy.cos(10*numpy.pi*k/N)
tfd = fft(u)
         
from matplotlib.pyplot import *
spectre = numpy.absolute(tfd)*2/N
figure(figsize=(10,4))
stem(k,spectre,'r')
            

def inversion_bits(i,p): # p = nombre de bits
    c = "{0:0%db}"%p
    binaire = c.format(i)
    inv = binaire[::-1]
    return int(inv,2)
                    

import numpy
                    
def fft(u,p):
    N=len(u)
    if N!=2**p:
        print("Erreur de taille")
        return
    A = numpy.zeros(N,dtype=numpy.complex64)
    B = numpy.zeros(N,dtype=numpy.complex64)
    for k in range(N):
        j = inversion_bits(k,p)
        A[j] = u[k]
    for q in range(1,p+1): # FFT à 2**q éléments
        taille = 2**q
        taille_precedente = 2**(q-1)
        nombre_tfd = 2**(p-q) # nombre de TFD à calculer
        for m in range(nombre_tfd):
            position = m*taille
            phi = -1j*2*numpy.pi/taille
            for i in range(taille_precedente):
                W = numpy.exp(phi*i)
                B[position+i] = A[position+i] + W*A[position+taille_precedente+i]
            for i in range(taille_precedente,taille):
                W = numpy.exp(phi*i)
                B[position+i] = A[position+i-taille_precedente] + W*A[position+i]
        (A,B)=(B,A) # échange des références des tableaux
    return A

import numpy
from matplotlib.pyplot import *

p = 5
N = 2**p
u = numpy.zeros(N,dtype=complex)
k = numpy.arange(N)
u = numpy.sin(2*numpy.pi*k/N)\
    +0.5*numpy.sin(4*numpy.pi*k/N)+0.25*numpy.cos(10*numpy.pi*k/N)
tfd = fft(u,p)
         

spectre = numpy.absolute(tfd)*2/N
figure(figsize=(10,4))
stem(k,spectre,'r')