Implementación de algoritmos de teoría de números/Raíz cuadrada entera

De Wikilibros, la colección de libros de texto de contenido libre.
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.

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