Implementación de algoritmos de teoría de números/Raíz cuadrada entera
Ir a la navegación
Ir a la búsqueda
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]
C[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);
}