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 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);
}