Racine carrée entière

Un article de Wikipédia, l'encyclopédie libre.

En mathématiques et en théorie des nombres, la racine carrée entière (isqrt) d'un nombre entier positif n est l'entier positif m qui est le plus grand entier inférieur ou égal à la racine carrée de n,

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

[modifier] Algorithme

Pour calculer $\sqrt{n}$ , et en particulier, isqrt(n), on peut utiliser la méthode de Newton pour l'équation $x^2-n=0\,$ , qui nous donne la formule récursive

${x}_{k+1} = \frac{1}{2}\left(x_k + \frac{ n }{x}_{k}\right), \ k \ge 0$ .

On peut choisir par exemple $x_0=n\,$ comme condition initiale.

La suite ${x k}$ converge de manière quadratique vers $\sqrt{n}$ lorsque $k \to \infty.$ Il peut être démontré (la démonstration n'est pas triviale) que l'on peut stopper dès que

$|x_{k+1}-x_k| < 1\,$

pour que $\lfloor x_{k+1} \rfloor=\lfloor \sqrt n \rfloor.$

[modifier] Domaine de calcul

Même si $\sqrt n$ est irrationnel pour la plupart des n, la suite ${x k}$ contient seulement des termes rationnels. Ainsi, avec la méthode de Newton, on n'a jamais besoin de quitter le corps des nombres rationnels pour calculer isqrt(n), un résultat qui possède certains avantages théoriques en théorie des nombres.