Racine n-ièmede l'unité — Les-mathematiques.net The most powerful custom community solution in the world

Racine n-ièmede l'unité

Bonjour à tous !
comment un ordinateur fait pour calculer les racines n-ième de l'unité ? Dans le but de faire de la FFT par exemple
Merci à vous !

Réponses

  • A priori avec la formule d'Euler on calcule l'exponentiel de tout nombre complexe, le calcul de l'exponentiel, du logarithme et des sinus,cosinus se fait par CORDIC.

    Mais il y a surement des astuces calculatoires.

    Code de gsl de la fonction puissance :113810
    pow.png 63.4K
  • 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.
  • Merci à vous !!
  • 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).
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!