TD d’algorithmique avanc´ee
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).)
Publicité
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.
(b) Le second algorithme devra s´eparer les coefficients du polynˆome d’entr´ee selon la parit´e de leur
indice.
Publicité
3. Montrez que deux entiers `a n bits peuvent ˆetre multipli´es en Θ(nlog2 3) ´etapes.
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 »).
Publicité
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)