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,

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

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

Algoritmo usando el método de Newton

Una forma de calcular ${\sqrt {n}}$ y ${\mbox{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}}\left(x_{k}+{\frac {n}{x_{k}}}\right),\quad k\geq 0,\quad x_{0}>0.$

La sucesión $\{x_{k}\}$ converge cuadráticamente a ${\sqrt {n}}$ cuando $k\to \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 {isqrt} (n)\,$
    $x_{k}\leftarrow 0$
    $x_{k+1}\leftarrow n$
    mientras $|x_{k+1}-x_{k}|\geq 1$ hacer
        $x_{k}\leftarrow x_{k+1}$
        $x_{k+1}\leftarrow {\frac {1}{2}}\left(x_{k}+{\frac {n}{x_{k}}}\right)$
    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);
}