Grands entiers : la conjecture du calcul quasi linéaire démontrée

Intervenant 10:00

Bienvenue dans le podcast du magazine Tangente. Je suis vraiment ravie de vous accueillir pour notre exploration du jour.

Intervenant 20:07

Merci, je suis très content

Intervenant 10:09

d'être là. Et on va aborder un sujet qui a l'air simple comme ça, mais qui est en fait un truc assez fou. Alors, imaginez juste une seconde que vous arrivez dans un immense stade.

Intervenant 20:21

Ouais, un stade de foot, par exemple.

Intervenant 10:24

Voilà, un stade de foot de disons 100 000 places pour assister à un événement. Mais à l'entrée, on vous donne une consigne. Une consigne stricte. Avant de pouvoir vous asseoir, vous devez obligatoirement serrer la main de absolument chaque personne présente dans les gradins.

Intervenant 20:40

Ah oui, c'est un véritable cauchemar logistique.

Intervenant 10:44

C'est totalement intenable. Et le pire, c'est que si le stade s'agrandit et qu'il passe à, mettons, 200 000 places, l'effort global ne fait pas que doubler.

Intervenant 20:53

Non, il quadruple.

Intervenant 10:54

Exactement, il quadruple. Parce que chaque nouvelle personne qui entre doit elle aussi serrer la main de toutes les autres.

Intervenant 21:00

C'est

Intervenant 11:00

ça. Eh bien, cette espèce de corvée exponentielle, c'est très exactement ce que subit votre ordinateur chaque fois qu'il effectue une simple multiplication avec de très grands noms.

Intervenant 21:10

Oui. Mais aujourd'hui, dans notre décryptage, on va plonger dans une découverte qui vient de changer les règles de ce jeu. On va décortiquer l'exploit récent de deux mathématiciens, donc David Harvey et Joris van der Hoeven. Oui, une publication qui

Intervenant 11:24

est tombée fin mars,

Intervenant 21:26

d'ailleurs. C'est ça. Et ils ont prouvé que la multiplication de très grands entiers peut se faire en un temps dit quasi linéaire. Et ça, ça résout au passage une conjecture mythique qui avait été posée par Volker Strassen en 1971. C'est un aboutissement exceptionnel, parce qu'on parle ici de réinventer carrément l'ingénierie interne d'une opération que l'humanité pratique depuis des millénaires.

Intervenant 11:52

Oui, et c'est justement ce qui m'amène à mon premier gros blocage.

Intervenant 21:57

D'accord.

Intervenant 11:58

Quand on regarde nos sources pour préparer cette émission, le point de départ de tout ce travail de haute volée, c'est la multiplication.

Intervenant 22:04

Oui.

Intervenant 12:04

Mais pourquoi chercher à réinventer une opération que n'importe quel enfant de 8 ans s'est posée sur un cahier de brouillon ?

Intervenant 22:11

Oui, c'est vrai qu'on peut se poser la question.

Intervenant 12:13

Si la méthode de l'école primaire fonctionne depuis l'Antiquité, en quoi est-elle soudainement devenue un problème pour des ordinateurs qui sont capables de faire des milliards de calculs par seconde ?

Intervenant 22:25

En fait, c'est une question d'échelle tout simplement. Pour bien comprendre l'impasse, il faut comparer la multiplication à sa cousine qui est, disons, beaucoup plus sage.

Intervenant 12:33

L'addition ?

Intervenant 22:34

Voilà, l'addition. Prenons l'algorithme classique de l'addition, celui qu'on a tous appris. Si vous voulez additionner deux nombres qui comportent chacun une certaine quantité de chiffres, disons, je ne sais pas, 100 chiffres.

Intervenant 12:45

Ouais, des grands nombres quoi.

Intervenant 22:46

L'ordinateur va effectuer 100 petites opérations basiques. Il va commencer par la droite, il ajoute les unités.

Intervenant 12:52

Il gère la petite retenue.

Intervenant 22:54

Exactement, il gère une éventuelle retenue, il passe aux dizaines et il avance comme ça jusqu'au

Intervenant 12:58

bout. D'accord, donc le temps que prend la machine, il est strictement proportionnel à la longueur du nombre.

Intervenant 23:03

Si

Intervenant 13:04

j'assimile ça à une tâche quotidienne, l'addition c'est un peu comme lire un livre. Si on me donne un manuscrit de 400 pages au lieu d'un manuscrit de 200 pages, ça me prendra exactement deux fois plus de temps à lire. C'est hyper prévisible et c'est stable, non ?

Intervenant 23:19

C'est exactement ça. En informatique et en mathématiques, on appelle ça un temps de calcul de complexité linéaire. On le note mathématiquement avec un grand O.

Intervenant 13:29

Le fameux grand

Intervenant 23:30

O. Voilà, ce qui donne O2n, où le n représente la taille du nombre. L'addition, elle est linéaire. La machine glisse sur les chiffres de manière complètement

Intervenant 13:40

fluide.

Intervenant 23:41

Mais la multiplication classique, celle qu'on pose sur le papier, vous savez, en décalant d'un cran à chaque ligne,

Intervenant 13:47

Oui, avec les petits zéros, les petits points qu'on rajoute.

Intervenant 23:50

C'est ça. Eh bien, elle obéit à une toute autre physique. Pour multiplier un nombre par un autre, chaque chiffre du premier nombre doit rencontrer chaque chiffre du second nombre.

Intervenant 14:02

Et donc, c'est là qu'on retrouve mon analogie de tout à l'heure, celle du stade et des fameuses poignées de main.

Intervenant 24:08

Tout le monde doit interagir avec tout le monde.

Intervenant 14:10

C'est la métaphore parfaite. Si vous avez un nombre de taille n multiplié par un autre nombre de taille n, vous forcez l'ordinateur à faire n multiplié par n petites opérations.

Intervenant 24:23

Donc

Intervenant 14:23

n². C'est ce qu'on nomme une complexité quadratique notée O . Et ça, à grands déchèges, c'est un mur de briques en fait.

Intervenant 24:31

Mais oui, parce qu'aujourd'hui, que ce soit en cryptographie pour sécuriser vos transactions bancaires ou bien en astronomie, les ordinateurs manipulent des nombres qui ne font pas juste 100 chiffres, ils font des centaines de milliers, voire des millions de chiffres.

Intervenant 14:45

Donc, si mon nombre géant est seulement 10 fois plus grand, mon ordinateur ne met pas 10 fois plus de temps à le traiter, il met 100 fois plus de temps.

Intervenant 24:54

Exactement. Et s'il est, disons, 1000 fois plus grand, on passe à 1 million de fois plus de temps de calcul.