Racine carrée entière

En mathématiques et en théorie des nombres, la racine carrée entière (isqrt) d'un entier naturel est la partie entière de sa racine carrée :

{\mbox{isqrt}}(n)=\lfloor {\sqrt {n}}\rfloor .

Algorithme[modifier | modifier le code]

Pour calculer $\sqrt n$ et $isqrt(n)$ , on peut utiliser la méthode de Héron — c'est-à-dire la méthode de Newton appliquée à l'équation $x 2 - n = 0$ — qui nous donne la formule de récurrence $x_{k+1}={\frac {1}{2}}\left(x_{k}+{\frac {n}{x_{k}}}\right),~k\geq 0.$

La suite $(x k)$ converge de manière quadratique vers $\sqrt n$ . On peut démontrer que si l'on choisit $x 0 = n$ comme condition initiale, il suffit de s'arrêter dès que $|x_{k+1}-x_{k}|<1$ pour obtenir $\lfloor x_{k+1}\rfloor =\lfloor {\sqrt {n}}\rfloor .$

Domaine de calcul[modifier | modifier le code]

Bien que $\sqrt n$ soit irrationnel pour « presque tout » $n$ , la suite $(x k)$ contient seulement des termes rationnels si l'on choisit $x 0$ rationnel. Ainsi, avec la méthode de Newton, on n'a jamais besoin de sortir du corps des nombres rationnels pour calculer $isqrt(n)$ , un résultat qui possède certains avantages théoriques en théorie des nombres.

Le critère d'arrêt[modifier | modifier le code]

On peut démontrer que $c$ = 1 est le plus grand nombre possible pour lequel le critère d'arrêt $|x_{k+1}-x_{k}|<c$ assure que $\lfloor x_{k+1}\rfloor =\lfloor {\sqrt {n}}\rfloor$ dans l'algorithme ci-dessus.

Puisque les calculs informatiques actuels impliquent des erreurs d'arrondi, on a besoin d'utiliser $c$ < 1 dans le critère d'arrêt, par exemple : $|x_{k+1}-x_{k}|<0,5.$

Références[modifier | modifier le code]

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Integer square root » (voir la liste des auteurs).

Arithmétique et théorie des nombres