Pour extraire une racine carrée ( & q par exemple) avec une calculette on utilise la méthode de Newton
On cherche x tq x² - q = f(x) = 0
1) Soit e critère d´arrêt
2) Soit N nb d´itérations max
3) Soit x(0) valeur initiale
4) Tant que n+1 < N, x(n+1) = x(n) - f(x(n))/f´(x(n))
5) Si |x(n+1) - x(n)|/|x(n+1)| < e la convergence est atteinte et x = x(n+1) ( -> arrêt) sinon on incrémente n et on va en 4)
6) Si N atteint la convergence n´est pas atteinte ( -> arrêt)
Pour la racine carré la difficulté est de choisir une valeur initiale x(0) assez proche de & q pour que la convergence soit rapide
L´intervalle de recherche étant R+, on va le réduire
Tour réel q peut s´écrire q = m*2^N ( écriture binaire) avec m = mantisse normalisée ( ( 1/2<=m<=1) et N = exposant
1) Si N pair & q = & m 2^(N/2)
2) Si N impair & q = & m/& 2 2^((N+1)/2))
On se ramène à chercher & m avec 1/2<=m<=1 ( & 2 est calculé une fois pour toutes et mis en mémoire)
On utilise Newton pour résoudre f(x) = x²-m = 0
L´algorithme devient :
x(n+1) = x(n) - f(x(n))/f´(x(n)) = x(n) - ( (x(n)² - m)/(2 x(n)) = ( 1/2) ( x(n) + m/x(n))
Pour trouver la valeur initiale x(0)on utilise le résultat suivant ( Cheney et Kincaid) :
La courbe y = 1,27235367 + 0,242693281 x - ( 1,02966039)/(1+x) est une bonne approximation de & x dans [1/2,1]
On utilise cette approximation pour déterminer x(0)