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. ...
Lire la suite gratuitement