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 modulo un entier donné. Implantation de l'algorithme de Karazuba.

Temps : 1 séance de 3 heures.

[ 0 ] Les scalaires et les polynomes.

Implanter les opérations de base modulo un entier donné.
Il s'agit d'écrire les fonctions
#define base 13
int add(complexe x, y) : retourne x+y modulo base.
int prd(complexe x, y) : retourne x*y modulo base.
Les polynomes seront représentés par une structure à deux champs : un pointeur vers les coefficients, et la taille du polynomes.

typedef struct { int taille;
int * coef;
} POLYNOME;
et les fonctions
POLYNOME allocation( int n );
void Liberer( POLYNOME p );

[ 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 taille double, et donc de faire le calcul exact:
R(X) := A(X) * B(X)
Ecrire la procédure correspondqnte, les allocations de mémoire devraient etre externes à la procédure...
void naif( POLYNOME r, a, b).
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 ] Algorithme de Karazuba.

Implanter l'algorithme de Karazuba.

     Algorithme KARAZUBA(A, B, R)
     DONNEES     A,B,R : POLYNOME;
     VARIABLE    AH, AL, BH, BL : POLYNOME;
                 PS, PA, PB, SA, SB : POLYNOME;
     DEBUT
        SI ( TAILLE(A) > 1 ) ALORS
              division
               DIVISION( A, AH, AL)
               DIVISION( B, BH, BL)
               preparation
                ADDITION( AH, AL, SA);
               ADDITION( BH, BL, SB);
              récursion
               KARAZUBA( AH, BH, PH );
               KARAZUBA( AL, BL, PL );
               KARAZUBA( SA, SB, PS );
              fusion
               SOUSTRACT( PS , PH );
               SOUSTRACT( PS , PL );
               FUSION( PL, PS, PL, R );
         SINON
              R[0] := prd( A[O], B[0] );
        FSI
     FIN

[ 4 ] 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.

[ 5 ] commenter les temps de calcul obtenus en [2] et [4];