Les enfants apprennent leurs tables de multiplication \u00e0 l’\u00e9cole. M\u00e9morisez-les. Bonne chance avec les nombres \u00e0 trois chiffres. C\u2019est l\u00e0 que les algorithmes entrent en jeu. Vous empilez les chiffres. Multipliez ligne par ligne. Pendant des milliers d\u2019ann\u00e9es, nous avons pens\u00e9 que c\u2019\u00e9tait le mieux que nous puissions faire. C’est lent. Brutalement lent pour le Big Data. Puis, en 1960, un jeune de 23 ans a tout chang\u00e9. Le myst\u00e8re de la vitesse de multiplication reste grand ouvert. <\/p>\n
La multiplication n’est pas seulement un devoir. Il g\u00e8re Internet. Cryptage, IA, traitement audio. Tout cela repose sur la multiplication. Multiplication lourde. Lorsque vous multipliez des nombres \u00e9normes des millions de fois par seconde, chaque \u00e9tape compte. Un l\u00e9ger gain d\u2019efficacit\u00e9 permet d\u2019\u00e9conomiser des milliards. <\/p>\n
Regardez la m\u00e9thode de l’\u00e9cole primaire. Deux chiffres signifient quatre multiplications \u00e0 un chiffre. Trois chiffres ? Neuf. Il \u00e9volue quadratiquement. Doublez la longueur, quadruplez le travail. Doublez-le encore, le travail augmente de seize fois. Les informaticiens ignorent les secondes. Le mat\u00e9riel acc\u00e9l\u00e8re de toute fa\u00e7on. Ils comptent les pas. Nous l\u2019appelons la notation Big O. L’\u00e9cole primaire est O(n^2). Quadratique. Si votre nombre augmente de 1 000, le travail explose d\u2019un million. <\/p>\n
\nLa charge de travail \u00e9volue avec le carr\u00e9 du nombre de chiffres. <\/p>\n<\/blockquote>\n
Depuis l\u2019Antiquit\u00e9, les math\u00e9maticiens pensaient que cette limite quadratique \u00e9tait une loi de la nature. Andre\u00ef Kolmogorov, une l\u00e9gende sovi\u00e9tique, y a mis\u00e9 sa r\u00e9putation lors d’une conf\u00e9rence en 1960. Il a d\u00e9clar\u00e9 aux \u00e9tudiants de l\u2019Universit\u00e9 d\u2019\u00c9tat de Moscou : \u00ab Cela prend O(n^2). \u00bb C\u2019est une conjecture formelle. Un d\u00e9fi. Attendez que quelqu’un le prouve ou le casse. <\/p>\n
Cela a pris une semaine. Anatoly Karatsuba \u00e9tait assis dans le public. Il avait 23 ans. Il est revenu avec la preuve que Kolmogorov avait tort. Le professeur \u00e9tait abasourdi. Kolmogorov a en fait \u00e9crit lui-m\u00eame l\u2019article pour une revue prestigieuse, mais il y a appos\u00e9 le nom de Karatsuba. L\u2019enfant ne le savait pas jusqu\u2019\u00e0 ce que les r\u00e9impressions arrivent par la poste. <\/p>\n
L’astuce<\/h3>\n
Karatsuba a r\u00e9alis\u00e9 quelque chose de simple mais profond. Les multiplications co\u00fbtent cher. Les ajouts sont bon march\u00e9. Pourquoi ne pas les \u00e9changer ? <\/p>\n
Prenez 12 x 34.
\nDivisez-le.
\n12 est 10 + 2.
\n34 est 30 + 4. <\/p>\nTraditionnellement, vous effectuez quatre multiplications\u00a0:
\n1×3
\n1×4
\n2×3
\n2×4 <\/p>\nKaratsuba a trouv\u00e9 un moyen de le faire \u00e0 trois.
\nCalculez la premi\u00e8re partie : 1×3 = 3.
\nCalculez la derni\u00e8re partie : 2×4 = 8. <\/p>\nMaintenant le milieu. Normalement, vous feriez (1×4) + (2×3). Deux multiplie. Additionnez plut\u00f4t les premiers nombres\u00a0: 1+2=3. Additionnez les derniers nombres : 3+4=7. Multipliez ces sommes\u00a0: 3×7=21. Soustrayez les parties que vous connaissez d\u00e9j\u00e0. 21 – 3 – 8 = 10.
\nBoum. Vous avez obtenu le moyen terme avec une multiplication suppl\u00e9mentaire. <\/p>\nEst-ce que \u00e7a vaut le coup ?
\nPas pour les petits nombres. Les frais g\u00e9n\u00e9raux li\u00e9s au fractionnement et \u00e0 l\u2019ajout vous co\u00fbtent cher.
\nMais pour 1 234 x 5 678 ? Divisez-le en deux. R\u00e9cursivit\u00e9. Divisez ces moiti\u00e9s. Faites-le \u00e0 nouveau. L\u2019\u00e9pargne compos\u00e9e.
\nL’algorithme tombe \u00e0 environ O(n^1,585).
\nLes nombres \u00e0 mille chiffres n\u00e9cessitaient autrefois un million de mults \u00e0 un chiffre. D\u00e9sormais, cela prend moins de 57 00 pas. Massif. <\/p>\nCe n\u2019est pas seulement de la th\u00e9orie. C’est en Python.
\nPython utilise les math\u00e9matiques scolaires standard pour les petites entr\u00e9es. Assez lisse.
\nUne fois que vous avez atteint environ 63 chiffres d\u00e9cimaux (selon la base de la machine), Python actionne un interrupteur. Karatsuba prend le relais. Vous ne voyez pas cela se produire. Mais c’est l\u00e0. G\u00e9rer votre cryptographie. <\/p>\nAlgorithmes Galactiques<\/h3>\n
La course s’est poursuivie pendant des d\u00e9cennies. Pouvons-nous aller plus vite ?
\n2019 a apport\u00e9 le dernier choc. David Harvey et Joris van Der Hoeven ont publi\u00e9 un algorithme qui bat Karatsuba d’un mile.
\nO (n journal n). <\/p>\nRelisez-le.
\nLes logarithmes croissent incroyablement lentement.
\nn log n est \u00e0 peine plus grand que n.
\nFondamentalement, multiplier deux nombres massifs prend d\u00e9sormais \u00e0 peu pr\u00e8s le m\u00eame temps que leur lecture. <\/p>\nC\u2019est stup\u00e9fiant. Le plafond th\u00e9orique semble avoir \u00e9t\u00e9 touch\u00e9.
\nOu peut-\u00eatre pas.
\nVoici le pi\u00e8ge.
\nCela ne fonctionne pas pour les chiffres qui nous int\u00e9ressent. <\/p>\nL’algorithme de Harvey et Van Der Hoeven ne devient plus rapide que celui de Karatsuba que lorsque les chiffres deviennent vraiment<\/em> grands. Pas grand “num\u00e9ro de carte de cr\u00e9dit”. Grand galactique.
\nEn informatique, nous avons un terme pour cela : algorithme galactique.
\nBelle th\u00e9orie. Z\u00e9ro utilisation pratique. Les chiffres requis sont plus importants que la plupart des transactions num\u00e9riques de l\u2019histoire de l\u2019humanit\u00e9 r\u00e9unies. <\/p>\nNous sommes coinc\u00e9s au milieu.
\nUtiliser des astuces des ann\u00e9es 1960 pour la plupart de nos t\u00e2ches informatiques quotidiennes.
\nPorter des costumes du 21e si\u00e8cle en plus des math\u00e9matiques du 20e si\u00e8cle. <\/p>\nUtilisons-nous r\u00e9ellement O(n log n) dans le monde r\u00e9el\u00a0?
\nPeut-\u00eatre que lorsque nous traitons des donn\u00e9es, la taille des galaxies est d\u00e9termin\u00e9e.
\nEn attendant, nous attendons.
\nPour le prochain tour.
\nOu un meilleur mat\u00e9riel pour cacher notre paresse. <\/p>\nLa r\u00e9ponse pourrait encore \u00eatre quadratique.
\nCela pourrait \u00eatre lin\u00e9aire.
\nNous ne le savons pas encore.<\/p>\n","protected":false},"excerpt":{"rendered":"Les enfants apprennent leurs tables de multiplication \u00e0 l’\u00e9cole. M\u00e9morisez-les. Bonne chance avec les nombres \u00e0 trois chiffres. C\u2019est l\u00e0 que les algorithmes entrent en jeu. Vous empilez les chiffres. Multipliez ligne par ligne. Pendant des milliers d\u2019ann\u00e9es, nous avons pens\u00e9 que c\u2019\u00e9tait le mieux que nous puissions faire. C’est lent. Brutalement lent pour le […]<\/p>\n","protected":false},"author":1,"featured_media":7909,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"tdm_status":"","tdm_grid_status":""},"categories":[1],"tags":[],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.schooler.org.ua\/fr\/wp-json\/wp\/v2\/posts\/7910"}],"collection":[{"href":"https:\/\/www.schooler.org.ua\/fr\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.schooler.org.ua\/fr\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.schooler.org.ua\/fr\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.schooler.org.ua\/fr\/wp-json\/wp\/v2\/comments?post=7910"}],"version-history":[{"count":0,"href":"https:\/\/www.schooler.org.ua\/fr\/wp-json\/wp\/v2\/posts\/7910\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.schooler.org.ua\/fr\/wp-json\/wp\/v2\/media\/7909"}],"wp:attachment":[{"href":"https:\/\/www.schooler.org.ua\/fr\/wp-json\/wp\/v2\/media?parent=7910"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.schooler.org.ua\/fr\/wp-json\/wp\/v2\/categories?post=7910"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.schooler.org.ua\/fr\/wp-json\/wp\/v2\/tags?post=7910"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}