Peut-on multiplier deux grands nombres plus vite qu'avec la méthode apprise à l'école ?

Pourquoi cette question : un modèle d'introduction

Le jury attend que vous expliquiez pourquoi vous avez choisi la question. Inspirez-vous de ce modèle, mais racontez votre propre parcours.

J'ai longtemps pensé que la multiplication posée était la seule façon de multiplier. Le mathématicien Kolmogorov le pensait aussi, jusqu'à ce qu'un étudiant de 23 ans, Karatsuba, trouve mieux en 1960. J'ai voulu comprendre son astuce, qui tient en une identité remarquable, et mesurer ce qu'elle fait gagner.

L'enjeu et les notions du programme

Utiliser le calcul littéral pour économiser une multiplication, puis résoudre une récurrence par les puissances et le logarithme.

Le plan de l'exposé en 9,5 min

1. 1. Introduction

   1 min

   Multiplier deux nombres de $n$n chiffres à la main demande de multiplier chaque chiffre de l'un par chaque chiffre de l'autre : $n^2$n² produits. En cryptographie, on multiplie des nombres de milliers de chiffres. Problématique : peut-on faire moins de $n^2$n² produits ?

2. 2. Mathématiques : l'astuce de Karatsuba

   4 min

   On coupe chaque nombre en deux moitiés : $x=a\times 10^k+b$x=a×10^(k)+b, $y=c\times 10^k+d$y=c×10^(k)+d. Alors $xy=ac\times 10^{2k}+(ad+bc)\times 10^k+bd$xy=ac×10^(2k)+(ad+bc)×10^(k)+bd : quatre multiplications de moitiés.

   L'astuce : $(a+b)(c+d)=ac+ad+bc+bd$(a+b)(c+d)=ac+ad+bc+bd, donc $ad+bc=(a+b)(c+d)-ac-bd$ad+bc=(a+b)(c+d)-ac-bd. Avec les trois produits $ac$ac, $bd$bd et $(a+b)(c+d)$(a+b)(c+d), on obtient tout : 3 multiplications au lieu de 4, plus quelques additions, peu coûteuses.

   Exemple : $x=12$x=12, $y=34$y=34 : $ac=1\times 3=3$ac=1×3=3, $bd=2\times 4=8$bd=2×4=8, $(1+2)(3+4)=21$(1+2)(3+4)=21, d'où $ad+bc=21-3-8=10$ad+bc=21-3-8=10 et $xy=300+100+8=408$xy=300+100+8=408.

   Coût : $M(n)=3M\left(\frac{n}{2}\right)$M(n)=3M (n/2), avec $M(1)=1$M(1)=1. Pour $n=2^k$n=2^(k), $M(n)=3^k=3^{{\log }_{2}n}=n^{{\log }_{2}3}\approx n^{1,585}$M(n)=3^(k)=3^(log₂n)=n^(log₂3)≈ n^(1,585). Pour 1 024 chiffres : $3^{10}=59049$3¹⁰=59 049 produits de chiffres contre $1024^2=1048576$1024²=1 048 576, près de 18 fois moins.

3. 3. NSI : en pratique

   3 min

   La version récursive s'arrête sur de petits nombres, que l'on multiplie directement, car les additions supplémentaires ne valent la peine qu'au-delà d'une certaine taille (quelques dizaines de chiffres). Python utilise d'ailleurs Karatsuba pour ses grands entiers.

   On a trouvé depuis des méthodes encore plus rapides, fondées sur la transformée de Fourier, jusqu'à un algorithme en $n\log n$nlog n publié en 2019. L'histoire montre qu'une méthode millénaire peut être battue par une idée de calcul littéral.

4. 4. Conclusion

   1,5 min

   On peut multiplier plus vite qu'à l'école : en économisant une multiplication sur quatre grâce à une identité, Karatsuba passe de $n^2$n² à $n^{{\log }_{2}3}$n^(log₂3). Le gain grandit avec la taille des nombres. J'ouvre sur l'exponentiation rapide, qui combine ces multiplications pour calculer de grandes puissances.

Ce que j'écris au tableau

Pas de calculatrice ni de support numérique : un calcul clé écrit au tableau rend l'exposé concret et montre la solidité des connaissances.

Conclusion : la réponse à la question

Les questions probables du jury

Pendant les 10 minutesd'échange, le jury vous fait préciser et approfondir, sur tout le programme de vos spécialités en lien avec la question.

Les pièges qui coûtent des points

• Oublier de soustraire ac et bd.
• Croire que Karatsuba est plus rapide pour de petits nombres.
• Confondre n^(log₂ 3) et 3n.

Revoir les notions

• Calcul littéral et équations (Seconde) →
• Fonction logarithme népérien (Terminale spé maths) →

Autres questions : algorithmes et complexité

• Pourquoi trier un million de nombres peut-il prendre dix minutes ou un centième de seconde selon l'algorithme ?
• Pourquoi couper un problème en deux permet-il de le résoudre beaucoup plus vite ?
• Peut-on inventer un algorithme de tri encore plus rapide, ou existe-t-il une limite infranchissable ?
• Un ordinateur mille fois plus rapide permet-il de résoudre des problèmes mille fois plus grands ?

Toutes les questions maths-nsi →