Abonnez-vous

Multiplions en temps quasi linéaire !


Hervé Lehning

L'information est tombée fin mars : les mathématiciens David Harvey et Joris van der Hoeven ont montré que la multiplication de grands entiers est « quasi linéaire », une conjecture qui tenait depuis 1971 et l'intuition de Volker Strassen. Revisitons l'une des opérations de base de l'arithmétique !


L’écriture d’un entier A en base N ressemble à celle d’un polynôme :

A = a + bN + cN2 +… où a, b, c… sont des nombres entiers compris entre 0 et N – 1. Pour additionner deux nombres à n chiffres, en utilisant l’algorithme classique, enseigné à l’école élémentaire, on effectue n additions de nombres à un chiffre, avec, éventuellement, n additions correspondant aux retenues. On vérifie effectivement qu’en utilisant un ordinateur le temps de calcul pour de très grands nombres est proportionnel à n. Plus précisément, il est majoré par une constante multipliée par n, ce que l’on note O(n) (« grand o de n »). On dit que sa complexité – ce qui est un modèle mathématique du temps de calcul – est linéaire.

En utilisant l’algorithme classique, enseigné dans les écoles, la multiplication n’est pas linéaire mais quadratique, c’est-à-dire que sa complexité est un O(n2) car on effectue alors n2 multiplications de nombres à un chiffre, puis environ n additions. On vérifie effectivement qu’en utilisant un ordinateur le temps ... Lire la suite gratuitement


références

 Integer multiplication in time O(n log n). David Harvey et Joris Van Der Hoeven, 2019, disponible en ligne.
 Les algorithmes.
Bibliothèque Tangente 37, 2013.