Karatsuba : trois produits au lieu de quatre

Exercice · niveau 2 · informatique (MP2I/MPI), chapitre 15 — Diviser pour régner

Énoncé

Pour multiplier deux nombres de $2 m$ chiffres, on les coupe en deux moitiés : $A = a_{1} B^{m} + a_{0}$ et $C = c_{1} B^{m} + c_{0}$ . La méthode scolaire calcule quatre produits. Karatsuba en calcule trois. Écrire lesquels, et chiffrer le gain.

Corrigé

Le produit complet vaut $A C = a_{1} c_{1} B^{2 m} + (a_{1} c_{0} + a_{0} c_{1}) B^{m} + a_{0} c_{0}$ . La méthode scolaire calcule les quatre produits $a_{1} c_{1}$ , $a_{1} c_{0}$ , $a_{0} c_{1}$ , $a_{0} c_{0}$ , d'où $T (n) = 4 T (n /2) + Θ (n)$ , soit $Θ (n^{2})$ par l'exercice précédent : on retrouve la multiplication apprise à l'école.

L'astuce est que le terme central s'obtient par soustraction :

$a_{1} c_{0} + a_{0} c_{1} = (a_{1} + a_{0}) (c_{1} + c_{0}) - a_{1} c_{1} - a_{0} c_{0} .$

Les deux produits $a_{1} c_{1}$ et $a_{0} c_{0}$ étant déjà nécessaires, un troisième produit $(a_{1} + a_{0}) (c_{1} + c_{0})$ suffit. D'où $T (n) = 3 T (n /2) + Θ (n)$ , et

$T (n) = Θ (n^{l o g_{2} 3}) = Θ (n^{1, 585}) .$

Le gain, compté exactement — nombre de multiplications de chiffres, en déroulant les deux récurrences $4^{l o g_{2} n}$ et $3^{l o g_{2} n}$ :

chiffres	méthode scolaire	Karatsuba	rapport
16	256	81	$3, 2$
64	$4096$	729	$5, 6$
256	$65536$	$6561$	$10, 0$
$1024$	$1048576$	$59049$	$17, 8$
$4096$	$16777216$	$531441$	31,6

Le rapport vaut $(4/3)^{l o g_{2} n} = n^{0, 415}$ : il croît, mais lentement.

Ce que cet exemple enseigne. Le troisième temps — combiner — est ici plus lourd que chez la méthode scolaire : il y a des additions et deux soustractions en plus. Le gain ne vient pas de la combinaison, il vient d'avoir supprimé un appel récursif. Dans $T (n) = a T (n / b) + f (n)$ , quand les feuilles dominent, c'est $a$ qu'il faut attaquer, pas $f$ . Passer $a$ de $4$ à $3$ change l'exposant ; améliorer $f$ n'y changerait rien.

En pratique, Karatsuba ne devient rentable qu'à partir de quelques dizaines de chiffres — en dessous, les additions supplémentaires coûtent plus que le produit économisé. Toutes les bibliothèques de grands entiers basculent donc de l'une à l'autre à un seuil, mesuré une fois pour toutes sur la machine cible.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.