La calculatrice utilise des suites, issues de raffinements de la méthode de Newton (voir Les Algorithmes, Bibliothèque Tangente 37, 2013, ou Itération et Récurrence, Bibliothèque Tangente 76, 2021).
La fonction f utilisée est définie par f (x) = x2 ‒ a.
On cherche la solution de f (x) = 0 car la solution est bien la quantité qui nous intéresse. Implémentons l’algorithme.
La dérivée de f vaut f ' (x) = 2 x, et on a
On en déduit bien la suite de Héron :
Illustrons maintenant la méthode avec a = 163. Pour initialiser les calculs, on peut partir de a, ou bien, 163 étant compris entre 144 = 122 et 169 = 132, de 12.
En trois itérations seulement de l’algorithme, le résultat est épatant puisque
De fait, le nombre de décimales exactes double (au minimum) à chaque boucle (phénomène de convergence quadratique).
À chaque itération, on a une addition et une division ainsi qu’une division par 2, facile à programmer en binaire, soit seulement trois opérations à réaliser.
L’astuce de Schönhage
L’inconvénient majeur de l’utilisation de la suite de Héron (voir ci-dessus) est la présence d’une division : c’est une opération « pénible » et « lente », même pour un circuit électronique. Mais il est possible de remplacer la division « a / un » par une suite : on utilise, encore une fois, la méthode de Newton pour calculer l’inverse 1/b d’un nombre réel b > 0. On utilise cette fois la fonction g définie par ce qui conduit à la suite v définie par vn+1 = vn(2 ‒ bvn).
En effet :
et
d’où
soit
On peut encore faire mieux ! Le mathématicien allemand Arnold Schönhage (né en 1934) a eu l’idée de coupler les deux suites de la méthode de Newton, ce couplage s’avérant plus performant que l’utilisation des deux méthodes séparément. Pour calculer une valeur approchée de la racine carrée de a > 0, on repart de la suite u, définie par
Pour calculer on utilise la méthode de Newton sur les inverses.
On utilise dans ce contexte deux suites, u et v :
avec