Feuille de travaux pratiques numéro 8 cours d'algorithmique de licence.

Multiplication Rapide

Objectifs : comparaison de deux algorithmes de multiplication de polynômes à coefficients complexes, implantation de la transformée de Fourier.

Temps : 1 séance de 3 heures.

[ 0 ] Les complexes.

Implanter les opérations de base sur les nombres complexes à partir de la structure :
typedef struct { double re, im; } complexe
il s'agit d'écrire les fonctions
complexe add(complexe x, y) : retourne x+y.
complexe prd(complexe x, y) : retourne x*y.
complexe racine(int n) : retourne la racine nieme principale.
utiliser la formule
Z° + z¹ + ... + z^(n-1) = ( z^n - 1 ) / ( z-1 )
pour vérifier vos fonctions.

[ 1 ] Produit naif.

Il s'agit de calculer le produit de deux polynômes A(X) et B(X) de taille n dans un troisième R(X) de même taille, et donc de faire le calcul :
R(X) := A(X) * B(X) modulo ( X^n - 1 )
Faire un choix de représentation des polynômes puis implanter l'algorithme de multiplication classique
void naif( polynome r, a, b; int n ).
qui doit être de complexité quadratique.

[ 2 ] Facteurs cachés.

Compiler avec l'option -pg mais sans option d'optimisation -Ox. Utiliser le profileur gprof pour compter le nombre d'opérations effectuées sur des complexes pour calculer le produit de deux polynômes de taille n, mesurer aussi les temps de calcul. Faire un tableau récapitulatif pour
log(n) = 6, 7, 8, 9, 10, 14, 18, 22.
Estimer les facteurs cachés.

[ 3 ] Transformation de Fourier.

Implanter une procédure
void fourier ( polynome p; int n)
pour calculer réursivement la transformée de Fourier du polynôme p. Implanter l'algorithme de transformation inverse
void inverse ( polynome p; int n)
puis vérifier le bon fonctionnement de ces deux algorithmes.

     Algorithme FOURIER( P, n )
     DONNEES     P : POLYNOME;
                 n : INDICE;
     VARIABLE x, z : COMPLEXE;
              U, V : POLYNOME;
     DEBUT
        SI ( n > 1 ) ALORS
                division
                U = POLYNOME( n/2 )
                V = POLYNOME( n/2 )
                POUR i DANS [0, n/2[
                     U[i] = P[ 2*i ]
                     V[i] = P[ 2*i+1]
                FIP
                récursion
                FOURIER( U, n/2 )
                FOURIER( V, n/2 )
                fusion
                z = RACINE( n)
                x = 1;
                i = 0
                TANTQUE ( i < n/2 )
                    P[     i ] = U[ i ] + x * V[i]
                    P[ i+n/2 ] = U[ i] - x * V[i]
                    x = x * z
                    INC( i )
                FTQ
        FSI
     FIN

[ 4 ] Multiplication rapide

Utiliser les procédures récursives fourier(p)et inverse(p) pour écrire un algorithme
void rapide ( polynome r, a, b; int n)
pour effectuer la multiplication rapide des polynômes a et b. Quelle est la complexité de votre algorithme ? Reprendre les mesures de la question [2]. L'algorithme rapide est-il toujours plus rapide que l'algorithme naif ? Comment pourrait-on faire pour améliorer les performances de l'algorithme de multiplication rapide ?