ArithmétiqueNotion · Glossaire
multiplication de grands nombres
La multiplication de grands nombres consiste à calculer exactement le produit de deux entiers dont l’écriture comporte beaucoup de chiffres. Pour deux entiers de n chiffres, la méthode scolaire demande un nombre de multiplications élémentaires de l’ordre de n², ce qui la rend trop lente à grande échelle. Des algorithmes rapides réduisent ce coût en découpant les entiers en blocs puis en recombinant leurs produits sans changer le résultat.
Sommaire
Ce que vous allez apprendre
- Relier le coût quadratique de la méthode scolaire au nombre de chiffres.
- Refaire une multiplication exacte par découpage de Karatsuba.
- Situer Toom-Cook, Schönhage-Strassen, Fürer et le résultat théorique de 2019.
- Reconnaître les seuils et hypothèses qui empêchent de déclarer un algorithme toujours meilleur.
En clair
Poser 1 234 × 5 678 chiffre par chiffre demande seize petits produits avant de gérer les décalages et les retenues. Avec des nombres de millions ou de milliards de chiffres, cette accumulation devient l'essentiel du temps de calcul.
Les algorithmes de multiplication de grands nombres découpent alors chaque entier en blocs. Ils recombinent quelques produits de blocs afin d'éviter une partie des opérations. Karatsuba illustre ce gain : trois produits de deux blocs remplacent les quatre produits qu'exigerait un développement direct.
Définition
La multiplication de grands nombres regroupe les algorithmes qui calculent exactement le produit de deux entiers dont l'écriture comporte beaucoup de chiffres. Pour deux entiers de n chiffres, la méthode scolaire effectue un nombre de multiplications élémentaires de l'ordre de n². L'enjeu est de réduire cette croissance, pas de changer le résultat.
Dans le découpage de Karatsuba, la base de découpage est notée B. Les deux entiers sont écrits x = aB + b et y = cB + d, où a et c sont les blocs de tête, tandis que b et d sont les blocs de fin. Trois produits suffisent : ac, bd et (a + b)(c + d). Leur recombinaison est exacte :
En appliquant récursivement ce découpage à deux entiers de quatre chiffres, Karatsuba ramène de seize à neuf le nombre de multiplications chiffre par chiffre.
Toom-Cook généralise le découpage en davantage de blocs. Pour des tailles bien plus grandes, Schönhage-Strassen exploite une transformée de Fourier rapide. La chronologie donnée par la source va de Karatsuba en 1962 à Toom-Cook en 1963 et 1966, puis à Schönhage-Strassen en 1971, à Fürer en 2007 et aux travaux encore théoriques de David Harvey et Joris van der Hoeven en 2019.
Un exemple, pas à pas
Calculons 1 234 × 5 678 par un découpage de type Karatsuba. Les données sont les blocs 12 et 34 pour le premier entier, les blocs 56 et 78 pour le second, et la base B = 100. La figure annonce visuellement ces quatre blocs et les trois produits à effectuer.
1. Calculez le produit des blocs de tête : 12 × 56 = 672.
2. Calculez le produit des blocs de fin : 34 × 78 = 2 652.
3. Additionnez les blocs de chaque entier, puis multipliez : (12 + 34) × (56 + 78) = 46 × 134 = 6 164.
4. Retirez les deux premiers produits au troisième : 6 164 − 672 − 2 652 = 2 840.
2. Calculez le produit des blocs de fin : 34 × 78 = 2 652.
3. Additionnez les blocs de chaque entier, puis multipliez : (12 + 34) × (56 + 78) = 46 × 134 = 6 164.
4. Retirez les deux premiers produits au troisième : 6 164 − 672 − 2 652 = 2 840.
Les trois résultats sont replacés selon les puissances de la base :
Le produit exact est donc 7 006 652. Un contrôle indépendant donne les trois derniers chiffres : 234 × 678 = 158 652, qui se termine bien par 652 comme le résultat obtenu.
En pratique
Pour quelques chiffres, la multiplication scolaire reste directe et son coût est modeste. Changer d'algorithme ajouterait un découpage et une recombinaison sans bénéfice visible.
Quand la taille des entiers augmente, un programme peut préférer Karatsuba, puis des méthodes plus élaborées. Le critère observable est le temps total : le gain sur le nombre de petits produits doit dépasser le coût des additions et des découpages.
À l'échelle d'un milliard de chiffres, l'écart devient décisif. Avec l'hypothèse d'une nanoseconde par multiplication élémentaire, la source estime environ 32 ans pour la méthode naïve, contre une trentaine de secondes pour Schönhage-Strassen ; l'algorithme théorique de 2019 réduit encore la complexité asymptotique.
À ne pas confondre
La multiplication de grands nombres ne désigne pas la multiplication de nombres ayant seulement une grande valeur. Le critère décisif est la longueur de leur écriture : 10100 est immense mais s'écrit très brièvement sous cette forme, tandis qu'un entier donné par un milliard de chiffres constitue une entrée gigantesque.
Il ne faut pas non plus confondre un algorithme exact avec une approximation numérique. Karatsuba, Toom-Cook et les méthodes citées visent le produit entier exact ; si le dernier chiffre du résultat peut varier avec un arrondi, il s'agit d'un autre cadre de calcul.
Enfin, la transformée de Fourier est un outil, pas le produit recherché. Dans Schönhage-Strassen, elle accélère l'organisation des calculs ; le résultat final reste la multiplication des deux entiers de départ.
Limites et pièges
Le seuil où un algorithme avancé devient avantageux n'est pas universel. Si le découpage, les additions et la mémoire coûtent plus que les produits économisés, le programme doit conserver une méthode plus simple ; il faut comparer les temps sur la machine et les tailles considérées.
Le gain « neuf au lieu de seize » concerne précisément deux entiers de quatre chiffres lorsque le découpage de Karatsuba est poursuivi jusqu'aux multiplications chiffre par chiffre. Il ne signifie pas que toute multiplication, quelle que soit sa taille, exige exactement neuf opérations.
Les durées de 32 ans et d'une trentaine de secondes reposent sur l'hypothèse annoncée d'une nanoseconde par multiplication élémentaire. Elles illustrent un ordre de grandeur ; sans cette hypothèse, il faut comparer les complexités et mesurer l'implémentation plutôt que reprendre ces temps tels quels.
Le résultat de 2019 est présenté dans la source comme encore théorique. Une meilleure complexité asymptotique ne garantit donc pas le meilleur temps pour une entrée concrète : les constantes cachées et les coûts auxiliaires doivent aussi être pris en compte.
Pour aller plus loin
La fiche Transformée de Fourier éclaire l'outil qui organise rapidement les calculs dans la méthode de Schönhage-Strassen.
L'article De la transformation de Fourier à la transformée en cosinus discrète prolonge l'étude des transformations rapides et de leurs représentations.
La notice Karatsuba Anatolii Alexevich permet de situer le mathématicien associé au premier algorithme ayant franchi la barrière quadratique.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres