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