def separation(liste,liste_finale):
    n = len(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])
    if len(pair)>2:
        separation(pair,liste_finale)
    else:
        liste_finale.append(pair[0])
    if len(impair)>2:
        separation(impair,liste_finale)
    else:
        liste_finale.append(impair[0])
            

p=4
N=2**p
liste=[]
for i in range(N):
    liste.append(i)
liste_finale = []
separation(liste,liste_finale)
            

def bits(nombre,liste_bits,p):
    liste_bits.append(nombre%2)
    if p >1:
        bits(int(nombre/2),liste_bits,p-1)
            

liste_bits=[]
bits(10,liste_bits,p)
            

def nombre(liste_bits):
    x = 0
    u=1
    for i in range(len(liste_bits)):
        x += liste_bits[i]*u
        u *= 2
    return x
            

def inversion_bits(nombre,p):
    liste_bits=[]
    bits(nombre,liste_bits,p)
    x=0
    n=len(liste_bits)
    u = 1
    for i in range(n):
        x += liste_bits[n-1-i]*u
        u *= 2
    return x
            

def ranger_ordre_bits_inverse(liste,p):
    liste_inverse = liste.copy()
    for i in range(len(liste)):
        liste_inverse[inversion_bits(i,p)] = liste[i]
    return liste_inverse
            

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')