L’écriture d’un entier A en base N ressemble à celle d’un polynôme :
A = a + bN + cN 2 +… 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 n 2 multiplications de nombres à un chiffre, puis environ n additions. On vérifie effectivement qu’en utilisant un ordinateur le temps de calcul pour des grands nombres est proportionnel à n 2.
Les ordinateurs sont devenus si puissants que ces mesures ne deviennent visibles que pour des nombres de plusieurs milliers de chiffres. Mais si vous doublez le nombre de chiffres, vous multipliez le temps de calcul par 4. Dans le cas de l’addition, vous ne faites que doubler le temps de calcul ; là est toute la différence entre complexité linéaire et complexité quadratique.
L’algorithme de Strassen
============================
