De Wikilibros, la colección de libros de texto de contenido libre.
La raíz cuadrada entera (isqrt) de un entero positivo n es un entero positivo m que es el entero menor o igual que la raíz cuadrada de n,

Por ejemplo,
porque
y
.
Algoritmo usando el método de Newton[editar]
Una forma de calcular
y
es usar el método de Newton para encontrar la solución de la ecuación
, dada por la fórmula iterativa

La sucesión
converge cuadráticamente a
cuando
. Se puede demostrar que si se toma
como valor inicial, se puede parar tan pronto como
para asegurar que
Pseudocódigo[editar]
función
mientras
hacer
devolver
significa "sustituya el valor de
por del de
", y devolver expresa el resultado del algoritmo y su terminación.
Implementación en distintos lenguajes de programación[editar]
#include <math.h>
unsigned int isqrt(unsigned int n){
float x0 = 0.0f;
float x1 = (float)n;
while (fabsf(x1 - x0) >= 1.0f){
x0 = x1;
x1 = 0.5f*(x0 + n / x0);
}
return (unsigned int)floorf(x1);
}