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,

$\text{isqrt}(n)=\lfloor \sqrt{n}\rfloor .$

Por ejemplo, $\text{isqrt}(27)=5$ porque $5\cdot 5=25\le 27$ y $6\cdot 6=36>27$.

Algoritmo usando el método de Newton

Una forma de calcular $\sqrt{n}$ y $\text{isqrt}(n)$ es usar el método de Newton para encontrar la solución de la ecuación $x^2-n=0$, dada por la fórmula iterativa

$x_{k+1}=\frac{1}{2}(x_k+\frac{n}{x_k}),k\ge 0,x_0>0.$

La sucesión $\{x_k\}$ converge cuadráticamente a $\sqrt{n}$ cuando $k\to \mathrm{\infty }$. Se puede demostrar que si se toma $x_0=n$ como valor inicial, se puede parar tan pronto como $|x_{k+1}-x_k|<1$ para asegurar que $\lfloor x_{k+1}\rfloor =\lfloor \sqrt{n}\rfloor .$

Pseudocódigo

función $\mathrm{i}\mathrm{s}\mathrm{q}\mathrm{r}\mathrm{t}(n)$
    $x_k\leftarrow 0$
    $x_{k+1}\leftarrow n$
    mientras $|x_{k+1}-x_k|\ge 1$ hacer
        $x_k\leftarrow x_{k+1}$
        $x_{k+1}\leftarrow \frac{1}{2}(x_k+\frac{n}{x_k})$
    devolver $\lfloor x_{k+1}\rfloor$

$x\leftarrow y$ significa "sustituya el valor de $x$ por del de $y$", y devolver expresa el resultado del algoritmo y su terminación.

Implementación en distintos lenguajes de programación

C

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