Exercice
Nous cherchons ici à effectuer le produit de deux entiers $x$ et $y$ écrits en binaire sur $k$ bits, avec $k$ une puissance de $2$. On peut noter $x = x_1 x_2 \ldots x_k$ et $y = y_1 y_2 \ldots y_k$. Les bits $x_1$ et $y_1$ sont les bits de poids forts.
$1.$ Donner la complexité de l’addition de deux nombres écrits en binaire écrits sur $n$ bits.
$2.$ Donner la complexité pour multiplier un nombre écrit en binaire sur $n$ bits par une puissance de $2$ inférieure à $2^{k}$.
$3.$ Quel est la complexité du produit naïf de deux nombres en binaire sur $n$ bits dont le résultat est écrit sur $2n$ bits ?
On pose $x_G = x_1 \ldots x_{k/2}$ et $x_D = x_{k/2+1} \ldots x_k$. De même, on pose $y_G$ et $y_D$.
$4.$ Exprimer naïvement $xy$ en fonction de $x_G$, $x_D$, $y_G$, $y_D$ et des puissances de $2$.
$5.$ Quelle est la complexité de l’algorithme de diviser pour régner associé ?
$6.$ Exprimer $xy$ en fonction de $x_G$, $x_D$, $y_G$, $y_D$ et des puissances de $2$ en utilisant moins de multiplication.
$7.$ Quelle est la complexité de l’algorithme de diviser pour régner associé ?
$8.$ Comment adapter l’algorithme pour multiplier des entiers sur $k$ bits avec $k$ quelconque ?
Cet algorithme de calcul a été développé par Anatolii Karatsuba en 1960 et publié en 1962.
Correction
$1.$ Pour additionner deux entiers, il est nécessaire de regarder chaque bits. De ce fait, le problème de l’addition de deux entiers est en $\Omega(n)$. De plus l’algorithme de la retenue tourne en $O(n)$. Il en résulte que la complexité de l’addition de deux entiers de $n$ bits est $\displaystyle \boxed{\Theta\left(n\right)}$.
$2.$ Pour multiplier un entier écris sur $n$ bits par une puissance de $2$, il nous suffit de décaler les bits de notre entier. Ainsi, il nous faut encore $\boxed{\Theta\left(n\right)}$ opérations.
$3.$ L’algorithme naïf de multiplication consiste à multiplier $x$ par chaque bit de $y$ avant de sommer. Cela nécessite donc $\displaystyle \boxed{\Theta\left(n^{2}\right)}$ opérations.
$4.$ On a la formule suivante :
\[xy = x_Gy_G\cdot2^{k} + (x_Gy_D + x_Dy_G)\cdot2^{k/2} + x_Dy_D\]
$5.$ Si on calcule récursivement cette formule, on remarque qu’on effectue 4 appels sur des instances de tailles $k/2$. De plus la fusion des différents résultats nécessite deux multiplications par des puissances de $2$ et trois additions, soit un coût en $O(k)$. Ainsi, un algorithme calculant cette formule a une complexité $C(n)$ qui vérifie la récurrence :
\[C(n) = 4C\left(\frac{n}{2}\right) + O(n)\]
Le master theorem nous permet donc de conclure que notre algorithme tourne en $\boxed{\Theta\left(k^{2}\right)}$ opérations. On ne remarque donc pas d’améliorations par rapport à la méthode naïf.
$6.$ Posons $g = x_Gy_G$, $d = x_Dy_D$ et $u = (x_G+x_D)(y_G+y_D)$. On note qu’on obtient ces valeurs en trois multiplications.
De plus, on note que $u – d – g = x_Gy_D + x_Dy_G$. On a donc :
\[xy = g\cdot2^{k} + (u-g-d)\cdot2^{k/2} + d\]
$7.$ L’algorithme de diviser pour régner associé à cette formule a une complexité définie par la formule :
\[T(k) = 3T\left(\frac{k}{2}\right) + O(k)\]
Le master theorem nous donne donc $\displaystyle T(k)=O\left(n^{\log_2(3)}\right)=O\left(n^{1.6}\right)$.
$8.$ Pour des entiers de tailles $n$ quelconque, on considère $m$ tel que $2^{m} \geq n \gt 2^{m-1}$. On complète à gauche nos entiers par des zéros pour obtenir des entiers de taille $2^m$. Ensuite, on procède avec notre algorithme qui aura une complexité en $O\left(2^{ \log_2(3) \cdot m}\right)$. Or on a $2^{m} \leq 2n$, donc notre algorithme fonctionne en $O\left(2^{ \log_2(3) } \cdot n^{ \log_2(3) }\right)$, soit en $O\left(n^{ \log_2(3) }\right)$.