Skip to content
SearchFR · Français
Get started

Language: English · Français

This in-depth story is available in French only.

Multiplier deux grands nombres plus vite que n log n

Non évalué Aucun tiers n’a vérifié ni le préprint d’OpenAI ni les constructions qui l’ont suivi.

Chiffres de la collecte5 du 31 oct. 2026, 6 h 57.

Le 23 septembre 2026, un préprint d’OpenAI affirme qu’on peut multiplier deux entiers de n chiffres un peu plus vite que n log n, le coût atteint en 2019 et tenu pour optimal depuis 1971. Depuis le 8 octobre, des dizaines de contributeurs agrandissent cet écart ; quatre contributions sur cinq déclarent l’aide d’une IA.

Participer à la course κ

Le dépôt integer-mult-bounds, qui tient cette course, est ouvert aux contributions, y compris celles préparées avec un agent IA. Son guide vise un résultat utile et vérifiable par un tiers en une soixantaine de minutes ; faire monter κ n'est pas exigé, et un résultat partiel ou négatif compte.

À battre : κ ≈ 0,0156371, record fusionné le 22 oct. 2026.

656 des 821 contributions relevées déclarent une IA (80 %).

Sans connaître le domaine : avec un agent IA

  1. Si vous découvrez la construction, lire la note d'entrée du dépôt (« bottleneck brief », en anglais).
  2. Choisir une tâche avec le script du dépôt : python3 scripts/choose_research_task.py
  3. Annoncer ce que vous prenez sur le forum du dépôt, pour éviter les doublons.
  4. Avec un agent IA : lui donner le fichier autoresearch.md et l'invite prévue par le dépôt, puis déclarer dans votre contribution l'IA utilisée et sa version.
  5. Relire la contribution en entier et lancer la vérification avant de l'envoyer : make verify (il faut Python 3.11, un compilateur C++17 et Boost).

Si vous connaissez le domaine

Ouvrir le dépôt integer-mult-boundsLire son guide de contribution (en anglais)

DiscoverIA ne tient pas ce dépôt et ne relit pas les contributions : leur statut reste « non évalué » tant qu'aucun tiers ne les a vérifiées. Conditions lues sur le dépôt le 22 oct. 2026.

Le coût d’une multiplication, de l’école à 2026

  1. 1Avant 1956n puissance 2Multiplication posée
  2. 21960n puissance 1,585Karatsuba
  3. 1963–1966n·e puissance c√log nToom, Cook, Schönhage
  4. 31971n log n log log nSchönhage et Strassen
  5. 2007n log n·K puissance log* nFürer
  6. 42019n log nHarvey et van der Hoeven
  7. 52026n (log n) puissance 1−κPréprint d’OpenAI, non évalué

Chaque marche est un coût plus bas pour multiplier deux nombres de n chiffres ; marches non à l’échelle.

À la loupe : la course sous n log n6

10−610−510−40,0018 oct.1624Record fusionné : 0,0156371 (22 oct.)23 sept., préprint : κ ≈ 1,6 × 10−55
10−610−510−40,0018 oct.12162024288 oct.première fusion, icekylinx12 oct.0,001 franchiRecord fusionné0,0156371, 22 oct.lm190923 sept., préprint : κ ≈ 1,6 × 10−55une cinquantaine d’ordres de grandeur plus bas
10−610−510−40,0018 oct.12162024288 oct.première fusion, icekylinx12 oct.0,001 franchiRecord fusionné0,0156371, 22 oct.lm190923 sept., préprint : κ ≈ 1,6 × 10−55
Trait noir : chaque nouveau record fusionné (57 hausses). Points gris : les 821 contributions, pleins si fusionnées, creux si seulement proposées.

La multiplication posée : n puissance 2

Pour multiplier deux nombres à la main, on multiplie chaque chiffre de l’un par chaque chiffre de l’autre. Avec deux nombres de n chiffres, cela fait n × n produits : un million pour deux nombres de mille chiffres. En 1956, le mathématicien Andreï Kolmogorov conjecture1 qu’on ne peut pas faire fondamentalement mieux que n puissance 2.

1960 : Karatsuba

À l’automne 1960, au séminaire de Kolmogorov à l’université de Moscou, Anatoli Karatsuba trouve mieux : en coupant chaque nombre en deux moitiés, trois multiplications suffisent là où il en fallait quatre. Répétée, l’astuce donne un coût en n puissance 1,585. La conjecture tombe ; l’article1, 2 paraît en 1962.

1971 : la transformée de Fourier

Toom (1963), puis Cook et Schönhage (1966) généralisent l’idée.1 En 1971, Schönhage et Strassen descendent à n log n log log n grâce à la transformée de Fourier rapide, et conjecturent que n log n est le vrai coût.3 Leur méthode, intégrée à la bibliothèque de calcul GMP, serait aujourd’hui « probablement l’algorithme de multiplication de grands entiers le plus utilisé au monde », selon Harvey et van der Hoeven.2

2019 : n log n

En 2019, après une étape intermédiaire de Fürer en 2007, Harvey et van der Hoeven atteignent n log n et confirment la conjecture de 1971 ; l’article2 paraît dans les Annals of Mathematics en 2021. Personne, en revanche, n’a démontré qu’on ne peut pas faire mieux : on ne sait même pas prouver qu’une multiplication coûte plus cher que la lecture des deux nombres.2

23 septembre 2026 : sous n log n ?

Un préprint d’OpenAI4 annonce une méthode en n (log n) puissance 1−κ, avec κ = 2 puissance −182, soit environ 1,6 × 10 puissance −55. κ mesure de combien on passe sous n log n : κ = 0, c’est n log n ; plus κ est grand, plus le gain est grand. Ici, le gain est infime, mais s’il tient, n log n n’est plus une limite. Définition et analogie au glossaire : n log n et κ.

Le préprint est daté du 23 septembre ; il est entré dans notre registre le 6 octobre, avec la publication openai/math. Aucun tiers ne l’a évalué.

Depuis le 8 octobre : la course

Le 8 octobre, un dépôt public, integer-mult-bounds, s’ouvre aux contributions : chacun peut y proposer une construction qui reprend le cadre du préprint et fait monter κ ; une contribution est dite fusionnée quand elle est intégrée au dépôt.5 La première contribution fusionnée, d’icekylinx, donne déjà κ ≈ 6 × 10 puissance −6, près de cinquante ordres de grandeur au-dessus du préprint. Le 12 octobre, Mister-Meeseeks, qui tient le dépôt, franchit 0,001. Le 17, jeremydiviney atteint 0,0017298.

En vingt-quatre jours, notre collecte compte 821 contributions : 360 fusionnées et 461 propositions, venues de 89 auteurs. 656 d’entre elles (80 %) déclarent l’aide d’une IA : Claude, Codex ou GPT. La borne a bougé 57 fois, et 128 contributions sont arrivées le seul 11 octobre.5

81810698510128117912601325141815114161017101851932013212922423142413251026927228129130131
81810698510128117912601325141815114161017101851932013212922423142413251026927228129130131
Contributions par jour, du 8 au 31 octobre (collecte du 31 oct., 6 h 57).

22 octobre : le record et ses réserves

Le record fusionné est aujourd’hui κ ≈ 0,0156371, proposé par lm1909 le 22 octobre à 21 h 28. Dans le fichier de référence du dépôt, la valeur retenue par le mainteneur est 0,0031258, depuis le 28 octobre.5

  • 0,0156371record fusionné, 22 oct.
  • 0,0031258retenu par le mainteneur, depuis le 28 oct.
  • 0,4354000meilleure proposition non fusionnée, 23 oct.
0,00150,00160,001712 oct.172227
0,00150,00160,001712 oct.151821242730Meilleure propositionnon fusionnée : 0,4354000Record fusionné0,0156371, 22 oct.Retenu par le mainteneur0,0031258, depuis le 28 oct.
Du 12 au 31 octobre, échelle linéaire. Trait plein : record fusionné ; tirets : valeur retenue par le mainteneur ; points gris : contributions, pleines si fusionnées.

Les contrôles du dépôt sont finis et exacts ; ce n’est pas une preuve complète en Lean, un langage où un ordinateur contrôle chaque étape d’une preuve.

Ce que ça change

En pratique, rien pour l’instant : ces exposants décrivent ce qui se passe quand les nombres deviennent immensément grands, pas des temps de calcul. GMP choisit déjà entre sept méthodes selon la taille des nombres, de la multiplication posée à la transformée de Fourier.7 En théorie, si le préprint tient, n log n cesse d’être la limite qu’on croyait atteinte.

Annonces liées

Sources

  1. 1A. A. Karatsuba, « La complexité des calculs » (en russe), Trudy MIAN 211 (1995), p. 189–199.
  2. 2D. Harvey et J. van der Hoeven, « Integer multiplication in time O(n log n) », Annals of Mathematics 193 (2021).
  3. 3A. Schönhage et V. Strassen, Computing 7 (1971), p. 281–292.
  4. 4OpenAI, « Integer multiplication below n log n », préprint du 23 sept. 2026 (dépôt openai/math). (github.com/openai/math)
  5. 5Dépôt integer-mult-bounds (GitHub) ; collecte DiscoverIA du 31 oct. 2026, 6 h 57. (github.com/CrocSwap/integer-mult-bounds)
  6. 7Manuel de GMP 6.3.0, « Multiplication Algorithms ».