Implementación de algoritmos de teoría de números/Raíz cuadrada entera
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 NewtonEditar
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ódigoEditar
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ónEditar
CEditar
#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);
}