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 :

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

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 ${\displaystyle 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 ${\displaystyle |x_{k+1}-x_{k}|<1}$ pour obtenir ${\displaystyle \lfloor x_{k+1}\rfloor =\lfloor {\sqrt {n}}\rfloor .}$

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.

On peut démontrer que c = 1 est le plus grand nombre possible pour lequel le critère d'arrêt ${\displaystyle |x_{k+1}-x_{k}|<c}$ assure que ${\displaystyle \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 : ${\displaystyle |x_{k+1}-x_{k}|<0,5.}$

• Arithmétique et théorie des nombres