De n² à n ln n : multiplier plus vite de grands entiers

Intervenant 10:00

Bienvenue dans le podcast du magazine Tangente. Chaque fois que vous achetez quelque chose en ligne, que vous tapez le numéro de votre carte bancaire sur un site, votre ordinateur fait un calcul. Plus précisément, il multiplie deux nombres entre eux pour chiffrer vos données. Et pas des petits nombres. On parle de monstres avec des centaines, voire des milliers de chiffres.

Intervenant 20:20

Oui, tout à fait.

Intervenant 10:21

Et si nos ordinateurs utilisaient la méthode de multiplication qu'on a tous appris à l'école primaire, ce simple achat sur Internet ne prendrait pas une fraction de seconde, il prendrait des heures.

Intervenant 20:31

Et à l'échelle mondiale, ça signifierait tout simplement la paralysie de notre société numérique en fait ?

Intervenant 10:37

Ouais, carrément.

Intervenant 20:38

Gagner du temps de calcul en informatique, c'est épargner des ressources énergétiques immenses et des infrastructures colossales. Donc le but de notre plongée au cœur de nos sources aujourd'hui, c'est de comprendre par quel miracle mathématique on arrive à contourner cette lenteur absolue.

Intervenant 10:55

Exactement.

Intervenant 20:56

Et ce qui est fascinant, c'est que la solution passe par un domaine qui semble, à première vue en tout cas, totalement déconnecté de la réalité matérielle.

Intervenant 11:04

Ouais, c'est ça qui est dingue. Pour comprendre comment on construit ce gratte-ciel infiniment plus vite, il faut d'abord qu'on regarde le problème en face. Multiplier des nombres gigantesques, c'est vraiment le goulot d'étranglement de l'informatique moderne. Alors, pour cette exploration, on va décortiquer comment des concepts mathématiques, qu'on qualifie souvent d'abstraits, en l'occurrence les nombres complexes, sont en fait le moteur caché qui propulse nos calculs à une vitesse vertigineuse.

Intervenant 21:31

C'est ça. Mais avant de parler de la solution, posons le problème. Au fond, c'est quoi écrire un grand nombre pour un ordinateur ?

Intervenant 11:39

Gardons en tête notre système habituel, la base 10, même si la logique s'applique à n'importe quelle base n utilisée par une machine.

Intervenant 21:47

D'accord.

Intervenant 11:47

Quand vous avez un nombre, vous le décomposez selon la position de ces chiffres. Unités, dizaines, centaines.

Intervenant 21:54

Ouais, classique.

Intervenant 11:55

Mathématiquement, c'est une somme de puissances. Le dernier chiffre multiplié par 1, l'avant-dernier par n, celui d'avant par n², etc. Donc, si je me souviens bien de mes cours d'algèbre, ce qu'on fait là, c'est qu'on transforme un simple nombre en un polynôme. Nos fameux x, x², x³. Sauf qu'ici, notre x, c'est la base de notre système de numération.

Intervenant 22:19

Exactement, voilà. Vous avez votre nombre A qui devient un polynôme et vous avez un autre nombre géant, B, qui est un autre polynôme.

Intervenant 12:28

Ok.

Intervenant 22:28

Vous voulez les multiplier ? L'approche instinctive, c'est la méthode qu'on pose sur le papier. Vous prenez chaque chiffre du nombre du bas et vous le multipliez par chaque chiffre du nombre du haut.

Intervenant 12:38

Et c'est là qu'on se heurte à un mur redoutable, le fameux mur de la complexité.

Intervenant 22:42

Oui, parce que si vous deux nombres ont n chiffres chacun, pour chaque chiffre du premier, vous faites n opérations avec le second. Au total, vous allez faire n multiplié par n opérations, c'est-à-dire n² multiplications, sans même compter les additions pour tout regrouper à la fin.

Intervenant 12:59

D'accord. Alors, posons-nous une seconde là-dessus. Parce que dire n², ça sonne un peu technique, mais l'impact physique est brutal. Laissez-moi utiliser une analogie.

Intervenant 23:09

Allez-y.

Intervenant 13:10

Imaginez que ce calcul, c'est l'équivalent d'une grande soirée de networking où tout le monde doit serrer la main. Si vous avez 100 personnes dans la salle, faire en sorte que chaque personne sert la main de toutes les autres, ça demande environ 10 000 poignées de main.

Intervenant 23:22

C'est une excellente image.

Intervenant 13:23

Mais si vous louez une salle plus grande et que vous doublez le nombre d'invités pour passer à 200 personnes, le nombre de poignées de main ne fait pas que doubler. Il ne passe pas à 20 000, il passe à 40 000. Vous avez multiplié le temps de la soirée par 4. Si vous avez 12 fois plus d'invités, la soirée dure 100 fois plus longtemps. C'est ça la punition du n². Pour des nombres de plusieurs milliers de chiffres, l'ordinateur suffoque sous les poignées de main.

Intervenant 23:50

Complètement. Et face à cela, l'algorithme classique est tout simplement une impasse. On ne peut pas accélérer le matériel indessinément. Ben

Intervenant 13:59

non, à un moment ça change quoi.

Intervenant 24:01

Voilà. Il a fallu que les mathématiciens trouvent un raccourci. Et pour briser cette limite du n², nos sources montrent qu'il faut faire une véritable pirouette conceptuelle.

Intervenant 14:12

D'accord.

Intervenant 24:12

On va faire appel au nombre complexe via un outil qu'on appelle la transformation de Fourier discrète.

Intervenant 14:18

Alors, et c'est précisément là que l'auditeur attentif lève un sourcil. Pourquoi utiliser les nombres complexes ? C'est ce qu'on appelle les nombres imaginaires, non ? C'est ça, oui. Ils utilisent cette fameuse unité I, dont le carré vaut moins 1. Ça flotte dans un espace à deux dimensions. Pourquoi diable utiliser un outil géométrique aussi abstrait pour faire une simple multiplication de nombres entiers bien réels ? J'ai un peu l'impression qu'on essaie de couper du beurre avec un laser de science-fiction, là.

Intervenant 24:44

C'est un scepticisme tout à fait légitime. Ce détour par l'abstraction semble ajouter de la difficulté. Mais c'est là qu'est le génie de la méthode.