Calcul de la racine carrée

Godefroy — Sat, 11 Mar 2006 00:44:30 +0100

Je me posais depuis un certain temps la question toute bête mais interessante : comment calculer efficacement la racine carrée d'un nombre ?
Je parts de x² = a
Il y a quelques mois j'avais fait un petit programme un peu brutal et très lent sur ma TI-89 qui essayait plein de possibilités pour trouver x en vérifiant à chaque fois en comparant x² et a, jusqu'à obtenir un écart maximal prédéfini. Mais c'était pas du tout satisfaisant...
J'ai alors cherché un peu sur internet, et j'ai trouvé plusieurs méthodes, mais la plupart étaient faites pour être utilisées à l'écrit, et elles étaient donc inexploitable dans un programme. Et j'ai trouvé la méthode d'Héron d'Alexandrie (1^er siècle après J-C) qui consiste en fait à créer une fonction dont le minimum sur R⁺ est en x = √a et y = √a. On cherche donc à atteindre le minimum de cette fonction pour avoir la valeur la plus approchée possible de √a
A partir de l'équation x² = a, on obtient :
2x² = x² + a
2x = x + a/x
x = (x + a/x)/2

Ce qui donne une fonction f(x) = (x + a/x)/2
A gauche, on voit la fonction f(x) = (x + 9/x)/2 pour trouver la racine carré de 9
On voit bien que le minimum de f(x) sur R⁺ est en 3, qui est bien ce que l'on cherche ^^
Mais comment trouver ce minimum ? En calculant la dérivée f '(x) de f(x) et en cherchant la solution de f '(x) = 0 (la dérivée étant égale au coefficient directeur de la tangente en un point, elle est égale à 0 lorsque la tangente est horizontale, et donc lorsque f(x) atteint son minimum)
Mais non ! car si on fait ça, le résultat est.... √a ! On ne va tout de même pas tourner en rond ^^
Non en fait cette fonction permet à partir de n'importe quel nombre de départ d'obtenir un nombre plus proche de √a que ce nombre de départ. Donc en répétant le calcul 3 ou 4 fois on obtient déjà une très bonne approximation.

Prenons par exemple a = 671, et la racine carré de la puissance de 10 de ce nombre comme nombre de départ (facile à mettre en oeuvre dans un programme).
On a dans ce cas comme nombre de départ : x = √100 = 10
f(10) = (10 + 671 / 10) / 2 = 39,05
f(39,05) = (39,05 + 671 / 39,05) / 2 = 28,1025641025
f(28,1025641025) = (28,1025641025 + 671 / 28,1025641025) / 2 = 25,9896944600
f(25,9896944600) = (25,9896944600 + 671 / 25,9896944600) / 2 = 25,9038100697
f(25,9038100697) = (25,9038100697 + 671 / 25,9038100697) / 2 = 25,9036676943
f(25,9036676943) = (25,9036676943 + 671 / 25,9036676943) / 2 = 25,9036676940

La valeur réelle de la racine carré de 671 donnée par un ordinateur est 25,9036676940
Au bout de 3 calculs, on obtient déjà un résultat convenable : 25,98
Et au bout de 6 calculs, on trouve la racine carré de 671 avec une précision de 10 chiffres après la virgule !
Evidemment, plus le nombre de départ est proche de la racine carré, et le nombre dont on veut trouver la racine carré est petit, moins il y a de calculs à faire ^^

Article original rédigé par Godefroy et publié sur Godefroy
Reproduction interdite sans autorisation