Pourquoi j'adore les maths

Les calculs (efficaces)

Calculer, c'est toute une affaire.

Prenons un exemple tout sympathique : comment multiplier deux nombres ?

Gudule : allumer la calculatrice, hop, c'est fait.

Alors, comment la calculatrice multiplie-t-elle deux nombres ?

Gudule : je suis trop jeune pour me poser cette question.

Pour faire plus simple je vais prendre des polynômes. Juste des expressions avec des puissances d'un « inconnu » X. Il n'a pas de valeur particulière, c'est X. C'est plus simple parce qu'il n'y a pas de retenue. Mais la morale restera sensiblement la même avec des entiers.

Après tout, 11 ce n'est que 1 + X avec X = 10, vous voyez le tableau.

Gudule fut enfermé pendant plusieurs semaines après cette illustration perturbatrice. Le compte-rendu du tribunal rapporte que le prévenu aurait déclaré « LOL XPTDR » pour sa seule défense. Heureusement, Gudule fut rendu à son propriétaire après son internement et put reprendre PJAM avec un peu de retard.

Prenons donc deux polynômes :

a + bX et c + dX, où les a, b, c, d sont des entiers.

Multiplions-les : ac + (ad + bc)X + bdX²

Combien est-ce que ça « coûte » au processeur de ma calculatrice ? Eh bien, quatre multiplications. Or une multiplication, c'est plus difficile à faire qu'une addition. Vous êtes d'accord : c'est pour ça qu'on apprend des tables horribles et interminables.

Gudule : c'était une justification bâclée, mais continuez, maître, continuez.

Et puis, imaginez qu'au lieu de a, b, c, d, on mette de plus petits polynômes et qu'on descende comme ça jusqu'à rencontrer les entiers eux-mêmes. Ça nous fait toujours (le nombre de coefficients du premier polynôme) fois (le nombre de coefficients du deuxième) multiplications à effectuer, additionner le résultat, bref, c'est pas la joie.

Peut-on faire mieux ?

Si vous aviez demandé aux mathématiciens au début du siècle dernier, ils auraient peut-être dit que non, mais nous sommes en 2016 et on utilise des ordinateurs depuis pas mal de temps. On a besoin de faire de gros calculs. On veut des algorithmes fameux. Et des branches des maths existent pour ça, la théorie computationnelle des nombres, l'algèbre computationnelle, qui s'occupent bel et bien de « calculer » les objets.

Donc, oui, on peut faire mieux, grâce à l'idée de Karatsuba pour commencer : il est possible de faire trois, au lieu de quatre, multiplications.

Car ac + (ad + bc)X + bdX² = ac + ( (a + c)(b + d) – ac – bd)X + bdX². Et toc.

Gudule : c'est l'arnaque.

Dit comme ça, ça manque de panache, mais maintenant imaginez que les a, b, c, d sont des polynômes plus petits : vous « coupez en deux » jusqu'à descendre aux entiers eux-mêmes. Cette stratégie formidable (diviser pour régner) vous conduit à améliorer considérablement :

– au départ pour deux polynômes à n coefficients, de l'ordre de n² opérations

– avec l'algorithme de Karatsuba, n à la puissance 1, 585 environ.

Ne râlez pas, c'est vraiment mieux. Pas encore de quoi se rouler par terre, cependant. C'est juste une preuve que des algorithmes malins existent.

L'un des meilleurs algorithmes du 20e siècle, justement, parle de multiplications, c'est l'algorithme FFT (Fast Fourier Transform). L'idée est remarquable : vous voulez toujours multiplier deux polynômes. Vous allez :

– effectuer une transformée de Fourier discrète (par analogie avec la bien connue transformée de Fourier continue), qui va en quelque sorte transporter ces deux polynômes dans un monde différent et merveilleux

– multiplier dans ce monde, où c'est plutôt facile

– revenir sur vos pas dans le monde réel grâce à la transformée inverse.

C'est un type de schéma d'interpolation / évaluation qui va consister à considérer non pas les polynômes par leurs coefficients, mais par les valeurs qu'ils prennent en certains points, pour certains X bien choisis.

La transformée de Fourier continue, normalement, consiste à représenter une fonction non pas comme donnée par sa courbe habituelle (les valeurs qu'elle prend), mais comme une somme de composantes oscillantes. C'est très apprécié des physiciens, en électricité et en mécanique, tout se ramène peu ou prou à des choses qui oscillent.

La transformée de Gudule, elle, consiste à changer mon esclave personnel en brocoli parce que c'est marrant.

Dans leur compte-rendu, les policiers qui assistèrent à l'attaque du supermarché par un brocoli sauteur insistèrent sur le caractère inhabituel de ce qu'ils avaient vécu. Le brocoli est toujours en fuite, il aurait volé un scooter avec l'aide d'une betterave.

Le ministère de la Santé se félicita de cette publicité et rappela qu'il est important de manger au moins cinq fruits et légumes par jour, et de varier ceux-ci.

Le coût théorique de l'algorithme FFT de l'ordre de (n log(n)) opérations, c'est-à-dire n fois un petit facteur, en fait (si vous lisez PJAM depuis longtemps, vous savez que log(n) est plutôt petit, il n'est là que pour troller).

Attention, on rappelle qu'ici n est le nombre de coefficients du polynôme, donc si vous pensez aux entiers, c'est de l'ordre du nombre de chiffres de n.

Donc, la théorie vous dit que multiplier des nombres prend à peu près (ça peut être 5, 10 fois plus, mais en tout cas c'est du même ordre) autant de temps que d'écrire le résultat. Elle est pas belle la vie ?

Ainsi naquirent les calculatrices modernes (celles qui ensuite vous dérivent des fonctions, les tracent à votre place, inversent des séries formelles, des matrices, résolvent des systèmes d'équations, interprètent de petits langages de programmation Turing-complets qui permettent de programmer un Pong). Et ainsi les petits collégiens purent-ils multiplier des entiers plus vite qu'avec leur tête et sans faire d'erreur. On n'arrête pas le progrès.

-------------------

Comment ? 3K vues ? 500 votes ?

Tout ça, c'est vraiment de la folie.

(Gudule passe sur un monocycle en chantant "Ce matin, un endomorphisme a tué un matheux. C'était un morphisme qui avait un fusil.")

Merci, chers lecteurs :D