Page Wikipedia

Dans les années 1950, Andreï Kolmogorov – grand mathématicien russe – émet l'hypothèse que pour multiplier deux nombres de $n$ chiffres, on ne peut faire mieux que $n^2$ multiplications élémentaires à un chiffre, et des additions. Il en parla en 1960 dans un séminaire auquel assistait Anatoli Karatsuba. Celui-ci, une semaine plus tard, proposait son algorithme.

Soit un nombre $x$ que l'on peut écrire $\overline{ab}$. $x = \overline{ab} = a \cdot 10^k + b$.

Par exemple, si $x = 4\,639$, on dira que $a = 46$ et $b = 39$. On a donc $x = \overline{ab} = a \cdot 10^2 + b$.

Pour bien faire, le mieux est de séparer, autant que possible, $x$ en deux parties égales.

De la même façon, posons $y = \overline{cd} = c \cdot 10^k + d$.

$$x \times y = \overline{ab} \times \overline{cd} = a\cdot c \cdot 10^{2k} + (a\cdot d + b \cdot c)\cdot 10^k + b\cdot d$$

On peut penser que le calcul nécessite alors 4 multiplications de plus petite taille : $a\cdot b$, $a\cdot c$, $b\cdot c$ et $b\cdot d$, c'est à dire la même chose que pour une multiplication posée en colonnes façon école primaire.

Mais Karatsuba remarque que nous n'avons pas besoin de $a\cdot d$ et $b \cdot c$ individuellement mais seulement de $$a\cdot d + b \cdot c = (a - b)\cdot(d - c) + a\cdot c + b\cdot d$$

Autrement dit le calcul nécessite le calcul des multiplications : $a\cdot c$, $b\cdot d$ et $(a-b)\cdot(d-c)$, tout le reste s'obtient avec des additions.

Calculer $\overline{ab} \cdot \overline{cd}$ nécessite de calculer par exemple $a \cdot b$. Eh bien on peut reproduire le même raisonnement en découpant $a$ et $b$ en morceaux plus petits.

Voyons un exemple, on veut calculer $4\,639 \cdot 875$.

• $x = 4\,639$ donc $a = 46$, $b = 39$ avec $k=2$
• $y = 875$. On complète $y$ pour qu'il ait la taille de $x$ plus grand (du point de vue de l'écriture) donc $y = 0\,875$ et donc $c = 08$ et $d = 75$.
• D'abord calculons $a\cdot c$, c'est à dire $46 \cdot 08$.
  On ne fait pas ce calcul directement, on applique encore la méthode de Karatsuba :
  • $a = \overline{a'b'}$ avec $a' = 4$, $b' = 6$, $k = 1$
  • $c = \overline{c'd'}$ avec $c' = 0$, $d' = 8$
  • Calculs des produits faits directement puisqu'ils n'ont plus qu'un chiffre :
    • $a'\cdot c' = 4 \cdot 0 = 0$
    • $b'\cdot d' = 6 \cdot 8 = 48$
    • $(a'-b')\cdot(d'-c') = -2\cdot 8 = -16$
  • On déduit $a\cdot c = 0\cdot 10^2 + (-16 + 0 + 48)\cdot 10^1 + 48 = 368$
• Ensuite calculons $b\cdot d$ :
  • $b = \overline{a'b'}$ avec $a' = 3$, $b' = 9$, $k = 1$
  • $d = \overline{c'd'}$ avec $c' = 7$, $d' = 5$
  • Calculs des produits faits directement puisqu'ils n'ont plus qu'un chiffre :
    • $a'\cdot c' = 3 \cdot 7 = 21$
    • $b'\cdot d' = 9 \cdot 5 = 45$
    • $(a'-b')\cdot(d'-c') = -6\cdot -2 = 12$
  • On déduit $b\cdot d = 21\cdot 10^2 + (12 + 21 + 45)\cdot 10^1 + 45 = 2925$
• Enfin calculons $(a-b)\cdot(d-c)$
  • $a-b = 46 - 39 = 07 = \overline{a'b'}$ avec $a' = 0$, $b' = 7$, $k = 1$
  • $d-c = 75 - 08 = 67 = \overline{c'd'}$ avec $c' = 6$, $d' = 7$
  • Calculs des produits faits directement puisqu'ils n'ont plus qu'un chiffre :
    • $a'\cdot c' = 0 \cdot 6 = 0$
    • $b'\cdot d' = 7 \cdot 7 = 49$
    • $(a'-b')\cdot(d'-c') = -7\cdot 1 = -7$
  • On déduit $b\cdot d = 0\cdot 10^2 + (-7 + 0 + 49)\cdot 10^1 + 49 = 469$
• On en déduit $x\cdot y = 368\cdot 10^4 + (469 + 368 + 2925) \cdot 10^2 + 2925 = 4\,059\,125$ ce qui est bien la bonne réponse.

Au final, au lieu des $4^2 = 16$ multiplications nécessaires si on avait posé la multiplication en colonne, on n'en a fait que $9$.

Remarque : Vous pourriez vous dire que $x$ et $y$ ne faisaient que 4 et 3 chiffres ce qui donne 12 multiplications ce qui reviendrait à ne pas compter le temps d'une multiplication par $0$. Dans ce cas, on peut ne compter, dans l'algorithme de Karatsuba que les multiplications sans $0$ et on voit qu'il n'y en a que 7 ce qui reste encore nettement inférieur.

Vous allez Réaliser l'implémentation de cet algorithme en Python.

Bien sûr notre but est de faire la multiplication de nombre très grands, par exemple de 1000 ou 10000 chiffres. Python est capable de manipuler de tels chiffres mais vous ne savez pas comment il s'y prend et comme l'algorithme de Karatsuba a quelque chose de fondamental, il est important de maîtriser tout le processus.

Vous ne devrez donc pas représenter les nombres à multiplier comme de simples int. Vous pourrez les représenter sous divers autres formes, à votre convenance. Voici quelques idées.

x = "4639". Cette forme permet un découpage facile. Par exemple la première moitié est x[:2] et le seconde est x[2:]. De plus, on n'a aucune peine à compléter x à gauche par des 0 si nécessaire.

En revanche, quand on arrivera au multiplication élémentaires à un chiffre et aux additions, ce système peut devenir gênant car il faudra sans doute convertir chaque digit d'un caractère à un entier, ce qui occasionnera de nombreux transtypages str → int et int → str.

Cela peut aussi créer des difficultés si on veut gérer l'éventualité d'un nombre négatif (ce qui arrive dans le déroulement de l'algorithme même si les nombres initiaux sont positifs)

x = (4, 6, 3, 9). Cette solution me semble meilleure puisqu'elle a les mêmes avantages et pas le défaut des transtypages. La difficulté sur les éventuels nombres négatifs demeure.

Créer une classe modélisant un nombre. C'est la meilleur méthode :

• on pourra stocker les digits dans un objets sous forme d'un tuple comme dans le cas précédent,
• on pourra utiliser un attribut signe pour tenir compte du signe,
• on pourra doter la classe de méthodes comme __add__, __sub__, __le__, __lt__,… et bien sûr __str__ ce qui rendra le code beaucoup plus lisible.
  À la limite, dans ce cas, on peut intégrer l'algorithme de Karatsuba dans une méthode __mul__ de la classe.

Il sera intéressant de prévoir une comparaison de temps d'exécution.