TD d’algorithmique avanc´ee
Corrig´e du TD 3 : multiplications « diviser pour r´egner »
Jean-Michel Dischler et Fr´ed´eric Vivien
Multiplications « diviser pour r´egner »
1. Montrez comment multiplier deux polynˆomes lin´eaires ax + b et cx + d `a 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`u : (ax + b) × (cx + d) = acx2 + ((a + b)(c + d) − ac − bd)x + bd, et les trois seules
multiplications n´ecessaires sont les calculs : ac, bd et (a + b)(c + d).
2. Donnez deux algorithmes « diviser pour r´egner » permettant de multiplier deux polynˆomes de degr´e
au plus n et s’ex´ecutant en Θ(nlog2 3).
(a) Le premier algorithme devra couper les coefficients du polynˆome d’entr´ee en deux moiti´es, l’une
sup´erieure et l’autre inf´erieure.
Soient P [X] et Q[X] les deux polynˆomes d’entr´ee. 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
+
Publicité
(cid:88)
i=1+(cid:98) n
2
X 1+(cid:98) n
2
+
piX i
n−1−(cid:98) n
2
(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ˆomes de degr´e au plus (cid:98) n
2
polynˆomes C et D pour Q : Q[X] = C[X]X 1+(cid:98) n
Avec les notations pr´ec´edemment d´efinies, 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´efinit de mˆeme les
2
n−1−(cid:98) n
2
i=0
(cid:99)
Publicité
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´equent, le produit de deux polynˆomes de degr´e au plus n peut se ramener au calcul de
trois produits de polynˆomes de degr´e 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ˆomes de degr´e au plus n —ce qui coˆute Θ(n)— et a des multipli-
cations par un monˆome X j —ce qui est un simple d´ecalage des indices et coˆute ´egalement Θ(n).
L’´equation de r´ecurrence d´efinissant la complexit´e de notre algorithme est alors :
T (n) = 3T (cid:16)
n
2 (cid:17) + Θ(n).
Nous appliquons alors le th´eor`eme vu en cours :
1
Th´eor`eme 1 (R´esolution des r´ecurrences « diviser pour r´egner »).
Soient a ≥ 1 et b > 1 deux constantes, soit f (n) une fonction et soit T (n) une fonction d´efinie
pour les entiers positifs par la r´ecurrence :
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 ˆetre born´ee asymptotiquement comme suit :
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´eor`eme
et donc
(cid:0)
Pour fixer les id´ees, log2 3 ≈ 1, 58 et l’algorithme na¨ıf de multiplications de polynˆomes est en
Θ(n2).
(cid:1)
T (n) = Θ
nlog2 3
.
(b) Le second algorithme devra s´eparer les coefficients du polynˆome d’entr´ee selon la parit´e de leur
indice.
P [X] =
=
=
=
n
Publicité
(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
i=1
polynˆomes de degr´e au plus (cid:98) n
2
C et D pour Q : Q[X] = C[X 2]X + D[X 2].
Avec les notations pr´ec´edemment d´efinies on a :
(cid:80)
(cid:99)
(cid:98) n
i=0 p2iX i. A[X] et B[X] sont alors deux
Publicité
p2i+1X i et B[X] =
2
(cid:99) et P [X] = A[X 2]X + B[X 2]. On d´efinit de mˆeme les polynˆomes
(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´equent, le produit de deux polynˆomes de degr´e au plus n peut se ramener au calcul de
trois produits de polynˆomes de degr´e 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ˆomes de degr´e au plus n —ce qui coˆute Θ(n)— a des multiplica-
tions par un monˆome X j —ce qui est un simple d´ecalage des indices et coˆute ´egalement Θ(n)— et
`a des transpositions du polynˆome R[X] au polynˆome R[X 2] —ce qui est encore un simple d´ecalage
des indices et coˆute ´egalement Θ(n). L’´equation de r´ecurrence d´efinissant la complexit´e de notre
algorithme est donc comme pr´ec´edemment :
et la complexit´e est la mˆeme :
T (n) = 3T (cid:16)
n
2 (cid:17) + Θ(n),
T (n) = Θ
nlog2 3
.
(cid:1)
(cid:0)
2
3. Montrez que deux entiers `a n bits peuvent ˆetre multipli´es en Θ(nlog2 3) ´etapes.
L’entier m =
rithmes vu `a la question pr´ec´edente pour obtenir le r´esultat escompt´e.
(cid:80)i=0 mi2i peut ˆetre vu comme un polynˆome : il nous suffit de r´eappliquer un des algo-
Calcul de (cos(nx), sin(nx))
´Ecrire un algorithme prenant en entr´ee un entier n et une paire de valeurs r´eelles 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`eme argument de la fonction est une paire (a,b) telle que a = cos x et b = sin x. Le sch´ema
de calcul doit ˆetre r´ecursif (mais non « diviser pour r´egner »).
On pourra se servir des formules de trigonom´etrie 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