Racine carrée entière

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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 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 x2n = 0 — qui nous donne la formule de récurrence x_{k+1}=\frac12\left(x_k+\frac n{x_k}\right),~k\ge0.

La suite (xk) converge de manière quadratique vers n. On peut démontrer que si l'on choisit x0 = 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 n soit irrationnel pour presque tout n, la suite (xk) contient seulement des termes rationnels si l'on choisit x0 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.


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