TD d’algorithmique avancée
Corrigé du 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).)
D’une part : (ax+b)×(cx+d) = acx2 +(ad+bc)x+bd. D’autre part : (a+b)(c+d) = ac+ad+bc+bd =
ac + bd + ad + bc. D’où : (ax + b) × (cx + d) = acx2 + ((a + b)(c + d) − ac − bd)x + bd, et les trois seules
multiplications nécessaires sont les calculs : ac, bd et (a + b)(c + d).
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.
Soient P [X] et Q[X] les deux polynômes d’entrée. P [X] =
n
i=0 piX i et Q[X] =
(cid:80)
n
i=0 qiX i.
(cid:80)
P [X] =
n
(cid:88)
i=0
piX i
(cid:98) n
2
(cid:99)
(cid:88)
i=0
(cid:98) n
2
(cid:99)
(cid:88)
i=0
=
=
piX i
piX i
n
+
(cid:88)
i=1+(cid:98) n
2
X 1+(cid:98) n
2
+
piX i
n−1−(cid:98) n
2
Publicité
(cid:99)
(cid:99)
(cid:99)
(cid:88)
i=0
pi+1+(cid:98) n
2
.
(cid:99)X i
(cid:99)
(cid:98) n
i=0 piX i et A[X] =
2
On pose alors B[X] =
deux polynômes de degré au plus (cid:98) n
2
polynômes C et D pour Q : Q[X] = C[X]X 1+(cid:98) n
Avec les notations précédemment définies, on a :
(cid:80)
2
(cid:99) + D[X].
(cid:80)
(cid:99) et P [X] = A[X]X 1+(cid:98) n
2
pi+1+(cid:98) n
(cid:99)X i. A[X] et B[X] sont alors
(cid:99) + B[X]. On définit de même les
2
n−1−(cid:98) n
2
i=0
(cid:99)
P [X]Q[X] = A[X]C[X]X 2+2(cid:98) n
2
(cid:99)
+((A[X] + B[X])(C[X] + D[X]) − A[X]C[X] − B[X]D[X])X 1+(cid:98) n
+C[X]D[X].
2
(cid:99)
Par conséquent, le produit de deux polynômes de degré au plus n peut se ramener au calcul de
trois produits de polynômes de degré au plus (cid:98) n
(cid:99) (A[X]C[X], B[X]D[X] et (A[X]+B[X])(C[X]+
2
D[X])), a des additions de polynômes de degré au plus n —ce qui coûte Θ(n)— et a des multipli-
cations par un monôme X j —ce qui est un simple décalage des indices et coûte également Θ(n).
L’équation de récurrence définissant la complexité de notre algorithme est alors :
T (n) = 3T (cid:16)
n
2 (cid:17) + Θ(n).
Nous appliquons alors le théorème vu en cours :
1
Théorème 1 (Résolution des récurrences « diviser pour régner »).
Soient a ≥ 1 et b > 1 deux constantes, soit f (n) une fonction et soit T (n) une fonction définie
pour les entiers positifs par la récurrence :
ou l’on interprete n/b soit comme (cid:98)n/b(cid:99), soit comme (cid:100)n/b(cid:101).
T (n) peut alors être bornée asymptotiquement comme suit :
Publicité
T (n) = aT (n/b) + f (n),
i. Si f (n) = O(n(logb a)−(cid:15)) pour une certaine constante (cid:15) > 0, alors T (n) = Θ(nlogb a).
ii. Si f (n) = Θ(nlogb a), alors T (n) = Θ(nlogb a log n).
iii. Si f (n) = Ω(n(logb a)+(cid:15)) pour une certaine constante (cid:15) > 0, et si af (n/b) ≤ cf (n) pour une
constante c < 1 et n suffisamment grand, alors T (n) = Θ(f (n)).
Ici a = 3, b = 2 et f (n) = Θ(n). Comme log2 3 > 1, nous nous trouvons dans le cas i) du théorème
et donc
(cid:0)
Pour fixer les idées, log2 3 ≈ 1, 58 et l’algorithme na¨ıf de multiplications de polynômes est en
Θ(n2).
(cid:1)
T (n) = Θ
nlog2 3
.
(b) Le second algorithme devra séparer les coefficients du polynôme d’entrée selon la parité de leur
indice.
P [X] =
=
=
=
n
(cid:88)
i=0
piX i
piX i +
(cid:88)
i pair
piX i
(cid:88)
i impair
(cid:98) n−1
2
(cid:99)
(cid:98) n
2
(cid:99)
(cid:88)
i=0
(cid:98) n
2
(cid:99)
(cid:88)
i=0
p2iX 2i +
(cid:88)
i=0
p2i+1X 2i+1
p2iX 2i + X
(cid:98) n−1
2
(cid:99)
(cid:88)
i=0
p2i+1X 2i
(cid:98) n−1
On pose alors A[X] =
2
Publicité
i=1
polynômes de degré au plus (cid:98) n
2
C et D pour Q : Q[X] = C[X 2]X + D[X 2].
Avec les notations précédemment définies on a :
(cid:80)
(cid:99)
(cid:98) n
i=0 p2iX i. A[X] et B[X] sont alors deux
p2i+1X i et B[X] =
2
(cid:99) et P [X] = A[X 2]X + B[X 2]. On définit de même les polynômes
(cid:80)
(cid:99)
P [X]Q[X] = A[X 2]C[X 2]X 2
+((A[X 2] + B[X 2])(C[X 2] + D[X 2]) − A[X 2]C[X 2] − B[X 2]D[X 2])X
+B[X 2]D[X 2]
Par conséquent, le produit de deux polynômes de degré au plus n peut se ramener au calcul de
trois produits de polynômes de degré au plus (cid:98) n
(cid:99) (A[X]C[X], B[X]D[X] et (A[X]+B[X])(C[X]+
2
D[X])), a des additions de polynômes de degré au plus n —ce qui coûte Θ(n)— a des multiplica-
tions par un monôme X j —ce qui est un simple décalage des indices et coûte également Θ(n)— et
à des transpositions du polynôme R[X] au polynôme R[X 2] —ce qui est encore un simple décalage
des indices et coûte également Θ(n). L’équation de récurrence définissant la complexité de notre
algorithme est donc comme précédemment :
et la complexité est la même :
T (n) = 3T (cid:16)
n
2 (cid:17) + Θ(n),
T (n) = Θ
nlog2 3
.
(cid:1)
(cid:0)
2
3. Montrez que deux entiers à n bits peuvent être multipliés en Θ(nlog2 3) étapes.
L’entier m =
rithmes vu à la question précédente pour obtenir le résultat escompté.
(cid:80)i=0 mi2i peut être vu comme un polynôme : il nous suffit de réappliquer un des algo-
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 »).
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)
Trigo(n, a, b)
Si n = 0 alors renvoyer (1, 0)
sinon c, d = Trigo(n − 1, a, b)
renvoyer (ac − bd, ad + bc)
3