TD d’algorithmique avancée
TD 3 : multiplications « diviser pour régner »
Jean-Michel Dischler et Frédéric Vivien
Multiplications « diviser pour régner »
1. Montrez comment multiplier deux polynômes linéaires ax + b et cx + d à l’aide de trois multiplications
seulement. (Indication : l’une des multiplications est (a + b)(c + d).)
Publicité
2. Donnez deux algorithmes « diviser pour régner » permettant de multiplier deux polynômes de degré
au plus n et s’exécutant en Θ(nlog2 3).
(a) Le premier algorithme devra couper les coefficients du polynôme d’entrée en deux moitiés, l’une
supérieure et l’autre inférieure.
(b) Le second algorithme devra séparer les coefficients du polynôme d’entrée selon la parité de leur
indice.
Publicité
3. Montrez que deux entiers à n bits peuvent être multipliés en Θ(nlog2 3) étapes.
Calcul de (cos(nx), sin(nx))
Écrire un algorithme prenant en entrée un entier n et une paire de valeurs réelles qui sont en fait les
valeurs du cosinus et du sinus d’un certain angle x, et renvoyant la paire (cos(nx), sin(nx)). Autrement
dit, le deuxième argument de la fonction est une paire (a,b) telle que a = cos x et b = sin x. Le schéma
de calcul doit être récursif (mais non « diviser pour régner »).
Publicité
On pourra se servir des formules de trigonométrie suivantes :
cos(nx) = cos((n-1)x) cos(x) - sin((n-1)x) sin(x)
sin(nx) = sin((n-1)x) cos(x) + cos((n-1)x) sin(x)