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

Pour calculer √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² – 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 √n. On peut démontrer que si l'on choisit x₀ = 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

Bien que √n soit irrationnel pour « presque tout » n, la suite (x_k) contient seulement des termes rationnels si l'on choisit x₀ 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

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

(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).