Racine n-ièmede l'unité

Il existe des algorithmes déjà optimisés pour le fft y compris discret.
Donc pas la peine de tout réinventer, tu peux regarder le code source de gsl https://www.gnu.org/software/gsl/ pour te faire une idée.

Pour faire un calcul de FFT, on cree un tableau avec les puissances successives de omega ou omega est une racine primitive 2^n-ieme de l'unite. En exact, on fait le calcul modulo un nombre premier de Fourier (de la forme p=t*2^n+1), en multipliant omega^(k-1) par omega mod p (avec des optimisations pour le calcul du reste mod p). En approche, la meme methode pose des problemes de precision lorsque k est trop grand, il faut de temps en temps calculer cos(2*pi*k/2^n) et sin(2*pi*k/2^n) (mais on garde presque tout le temps le principe de la multiplication par omega=exp(i*2*pi/2^n), car c'est bien plus rapide).