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 :
Algorithme
Pour calculer Modèle:Sqrt et Modèle:Math, on peut utiliser la méthode de Héron — c'est-à-dire la méthode de Newton appliquée à l'équation Modèle:Math — qui nous donne la formule de récurrence Modèle:Retrait
La suite Modèle:Math converge de manière quadratique vers Modèle:Sqrt. On peut démontrer que si l'on choisit Modèle:Math comme condition initiale, il suffit de s'arrêter dès que Modèle:Retrait pour obtenir Modèle:Retrait
Domaine de calcul
Bien que Modèle:Sqrt soit irrationnel pour « presque tout » Modèle:Math, la suite Modèle:Math contient seulement des termes rationnels si l'on choisit Modèle:Math rationnel. Ainsi, avec la méthode de Newton, on n'a jamais besoin de sortir du corps des nombres rationnels pour calculer Modèle:Math, 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 Modèle:Math = 1 est le plus grand nombre possible pour lequel le critère d'arrêt Modèle:Retrait assure que Modèle:Retrait dans l'algorithme ci-dessus.
Puisque les calculs informatiques actuels impliquent des erreurs d'arrondi, on a besoin d'utiliser Modèle:Math < 1 dans le critère d'arrêt, par exemple : Modèle:Retrait