Raíz cuadrada entera

En teoría de números , la raíz cuadrada entera (isqrt) de un entero no negativo n es el entero no negativo m que es el mayor entero menor o igual a la raíz cuadrada de n , $${\displaystyle \operatorname {isqrt} (n)=\lfloor {\sqrt {n}}\rfloor .}$$

Por ejemplo,${\displaystyle \operatorname {isqrt} (27)=\lfloor {\sqrt {27}}\rfloor =\lfloor 5.19615242270663...\rfloor =5.}$

Sean y números enteros no negativos. ${\estilo de visualización y}$${\estilo de visualización k}$

Los algoritmos que calculan (la representación decimal de) se ejecutan eternamente en cada entrada que no sea un cuadrado perfecto . ^{[nota 1]}${\displaystyle {\sqrt {y}}}$ ${\estilo de visualización y}$

Los algoritmos que calculan no funcionan eternamente , pero son capaces de calcular con cualquier precisión deseada . ${\displaystyle \lfloor {\sqrt {y}}\rfloor }$ ${\displaystyle {\sqrt {y}}}$${\estilo de visualización k}$

Elige cualquiera y calcula . ${\estilo de visualización k}$${\textstyle \lfloor {\sqrt {y\times 100^{k}}}\rfloor }$

Por ejemplo (configuración ): ${\displaystyle y=2}$$${\displaystyle {\begin{aligned}&k=0:\lpiso {\sqrt {2\times 100^{0}}}\rpiso =\lpiso {\sqrt {2}}\rpiso =1\\&k=1:\lpiso {\sqrt {2\times 100^{1}}}\rpiso =\lpiso {\sqrt {200}}\rpiso =14\\&k=2:\lpiso {\sqrt {2\times 100^{2}}}\rpiso =\lpiso {\sqrt {20000}}\rpiso =141\\&k=3:\lpiso {\sqrt {2\times 100^{3}}}\rpiso =\lpiso {\sqrt {2000000}}\rpiso =1414\\&\vdots \\&k=8:\lfloor {\sqrt {2\times 100^{8}}}\rfloor =\lfloor {\sqrt {20000000000000000}}\rfloor =141421356\\&\vpuntos \\\end{alineado}}}$$

Comparar los resultados con${\displaystyle {\sqrt {2}}=1,41421356237309504880168872420969807856967187537694...}$

Parece que la multiplicación de la entrada por da una precisión de k dígitos decimales. ^{[nota 2]}${\estilo de visualización 100^{k}}$

Para calcular la representación decimal (completa) de , se puede ejecutar un número infinito de veces, aumentando en un factor en cada pasada. ${\displaystyle {\sqrt {y}}}$${\displaystyle \operatorname {isqrt} (y)}$${\estilo de visualización y}$${\estilo de visualización 100}$

Supongamos que en el siguiente programa ( ) el procedimiento ya está definido y, para los fines del argumento, todas las variables pueden contener números enteros de magnitud ilimitada. ${\displaystyle \operatorname {sqrtParasiempre} }$${\displaystyle \operatorname {isqrt} (y)}$

Luego imprimirá la representación decimal completa de . ^{[nota 3]}${\displaystyle \operatorname {sqrtForever} (y)}$${\displaystyle {\sqrt {y}}}$

// Imprime sqrt(y), sin detenerse
void sqrtForever ( entero sin signo y )   
{
	unsigned int resultado = isqrt ( y );    
	printf ( "%d." , resultado ); // imprime el resultado, seguido de un punto decimal 	

	mientras ( verdadero ) // repetir para siempre ... 	
	{
		y = y * 100 ; // ejemplo teórico: se ignora el desbordamiento    	
		resultado = isqrt ( y );  
		printf ( "%d" , resultado % 10 ); // imprimir el último dígito del resultado   	
	}
}

La conclusión es que los algoritmos que calculan isqrt()son computacionalmente equivalentes a los algoritmos que calculansqrt() .

La raíz cuadrada entera de un entero no negativo se puede definir como ${\estilo de visualización y}$$${\displaystyle \lfloor {\sqrt {y}}\rfloor =x:x^{2}\leq y<(x+1)^{2},x\in \mathbb {N} }$$

Por ejemplo, porque . ${\displaystyle \operatorname {isqrt} (27)=\lfloor {\sqrt {27}}\rfloor =5}$${\displaystyle 6^{2}>27{\text{ y }}5^{2}\ngtr 27}$

Los siguientes programas en C son implementaciones sencillas.

// Raíz cuadrada entera 
// (usando búsqueda lineal, ascendente) 
unsigned int isqrt ( unsigned int y ) { // subestimación inicial, L <= isqrt(y) unsigned int L = 0 ;    

	
	    

	mientras (( L + 1 ) * ( L + 1 ) <= y ) L = L + 1 ;         
		    

	devolver L ; } 

// Raíz cuadrada entera 
// (usando búsqueda lineal, descendente) 
unsigned int isqrt ( unsigned int y ) { // sobreestimación inicial, isqrt(y) <= R unsigned int R = y ;    

	
	    

	mientras ( R * R > y ) R = R - 1 ;     
		    

	devuelve R ; } 

En el programa anterior (búsqueda lineal, ascendente) se puede reemplazar la multiplicación por la suma, utilizando la equivalencia $${\displaystyle (L+1)^{2}=L^{2}+2L+1=L^{2}+1+\sum _{i=1}^{L}2.}$$

// Raíz cuadrada entera
// (búsqueda lineal, ascendente) mediante suma
entero sin signo isqrt ( entero sin signo y )    
{
	entero sin signo L = 0 ;    
	entero sin signo a = 1 ;    
	entero sin signo d = 3 ;    

	mientras ( a <= y )   
	{
		a = a + d ; // (a + 1) ^ 2    	
		d = d + 2 ;    
		L = L + 1 ;    
	}

	devuelve L ; 
}

La búsqueda lineal comprueba secuencialmente cada valor hasta que llega al más pequeño donde . ${\estilo de visualización x}$$Estilo de visualización x^{2}>y$

Se logra una mayor velocidad utilizando la búsqueda binaria . El siguiente programa en C es una implementación.

// Raíz cuadrada entera (usando búsqueda binaria)
entero sin signo isqrt ( entero sin signo y )    
{
	entero sin signo L = 0 ;    
	int sin signo M ;  
	entero sin signo R = y + 1 ;      

    mientras ( L != R - 1 )     
    {
        M = ( I + D ) / 2 ;      

		si ( M * M <= y )     
			L = M ;  
		demás
			R = M ;  
	}

    devuelve L ; 
}

Ejemplo numérico

Por ejemplo, si se realiza un cálculo utilizando la búsqueda binaria, se obtiene la secuencia ${\displaystyle \operatorname {isqrt} (2000000)}$${\displaystyle [L,R]}$$${\displaystyle {\begin{aligned}&[0,2000001]\rightarrow [0,1000000]\rightarrow [0,500000]\rightarrow [0,250000]\rightarrow [0,125000]\rightarrow [0,62500]\rightarrow [0,31250]\rightarrow [0,15625]\\&\rightarrow [0,7812]\rightarrow [0,3906]\rightarrow [0,1953]\rightarrow [976,1953]\rightarrow [976,1464]\rightarrow [1220,1464]\rightarrow [1342,1464]\rightarrow [1403,1464]\\&\rightarrow [1403,1433]\rightarrow [1403,1418]\rightarrow [1410,1418]\rightarrow [1414,1418]\rightarrow [1414,1416]\rightarrow [1414,1415]\end{aligned}}}$$

Este cálculo requiere 21 pasos de iteración, mientras que la búsqueda lineal (ascendente, comenzando desde ) necesita${\displaystyle 0}$1414 pasos.

Una forma de calcular y es utilizar el método de Heron , que es un caso especial del método de Newton , para encontrar una solución para la ecuación , dando la fórmula iterativa ${\displaystyle {\sqrt {n}}}$${\displaystyle \operatorname {isqrt} (n)}$${\displaystyle x^{2}-n=0}$$${\displaystyle x_{k+1}={\frac {1}{2}}\!\left(x_{k}+{\frac {n}{x_{k}}}\right),\quad k\geq 0,\quad x_{0}>0.}$$

La secuencia converge cuadráticamente a como . ${\displaystyle \{x_{k}\}}$ ${\displaystyle {\sqrt {n}}}$${\displaystyle k\to \infty }$

Se puede demostrar ^{[ cita requerida ]} que es el número más grande posible para el cual se asegura el criterio de detención en el algoritmo anterior. ${\displaystyle c=1}$$${\displaystyle |x_{k+1}-x_{k}|<c}$$${\displaystyle \lfloor x_{k+1}\rfloor =\lfloor {\sqrt {n}}\rfloor }$

En implementaciones que utilizan formatos de números que no pueden representar todos los números racionales con exactitud (por ejemplo, punto flotante), se debe utilizar una constante de detención menor que 1 para protegerse contra errores de redondeo.

Aunque para muchos es irracional , la sucesión contiene sólo términos racionales cuando es racional. Por lo tanto, con este método no es necesario salir del campo de los números racionales para calcular , hecho que presenta algunas ventajas teóricas. ${\displaystyle {\sqrt {n}}}$${\displaystyle n}$${\displaystyle \{x_{k}\}}$${\displaystyle x_{0}}$${\displaystyle \operatorname {isqrt} (n)}$

Para calcular números enteros muy grandes n , se puede utilizar el cociente de la división euclidiana para ambas operaciones de división. Esto tiene la ventaja de utilizar únicamente números enteros para cada valor intermedio, lo que hace innecesario el uso de representaciones de punto flotante de números grandes. Es equivalente a utilizar la fórmula iterativa ${\displaystyle \lfloor {\sqrt {n}}\rfloor }$$${\displaystyle x_{k+1}=\left\lfloor {\frac {1}{2}}\!\left(x_{k}+\left\lfloor {\frac {n}{x_{k}}}\right\rfloor \right)\right\rfloor ,\quad k\geq 0,\quad x_{0}>0,\quad x_{0}\in \mathbb {Z} .}$$

Utilizando el hecho de que $${\displaystyle \left\lfloor {\frac {1}{2}}\!\left(x_{k}+\left\lfloor {\frac {n}{x_{k}}}\right\rfloor \right)\right\rfloor =\left\lfloor {\frac {1}{2}}\!\left(x_{k}+{\frac {n}{x_{k}}}\right)\right\rfloor ,}$$

Se puede demostrar que esto se logrará dentro de un número finito de iteraciones. ${\displaystyle \lfloor {\sqrt {n}}\rfloor }$

En la versión original, se tiene para , y para . Por lo tanto, en la versión entera, se tiene y hasta que se alcanza la solución final . Para la solución final , se tiene y , por lo que el criterio de parada es . ${\displaystyle x_{k}\geq {\sqrt {n}}}$${\displaystyle k\geq 1}$${\displaystyle x_{k}>x_{k+1}}$${\displaystyle x_{k}>{\sqrt {n}}}$${\displaystyle \lfloor x_{k}\rfloor \geq \lfloor {\sqrt {n}}\rfloor }$${\displaystyle x_{k}\geq \lfloor x_{k}\rfloor >x_{k+1}\geq \lfloor x_{k+1}\rfloor }$${\displaystyle x_{s}}$${\displaystyle x_{s}}$${\displaystyle \lfloor {\sqrt {n}}\rfloor \leq \lfloor x_{s}\rfloor \leq {\sqrt {n}}}$${\displaystyle \lfloor x_{s+1}\rfloor \geq \lfloor x_{s}\rfloor }$${\displaystyle \lfloor x_{k+1}\rfloor \geq \lfloor x_{k}\rfloor }$

Sin embargo, no es necesariamente un punto fijo de la fórmula iterativa anterior. De hecho, se puede demostrar que es un punto fijo si y solo si no es un cuadrado perfecto. Si es un cuadrado perfecto, la secuencia termina en un ciclo de período dos entre y en lugar de converger. ${\displaystyle \lfloor {\sqrt {n}}\rfloor }$${\displaystyle \lfloor {\sqrt {n}}\rfloor }$${\displaystyle n+1}$${\displaystyle n+1}$${\displaystyle \lfloor {\sqrt {n}}\rfloor }$${\displaystyle \lfloor {\sqrt {n}}\rfloor +1}$

// Raíz cuadrada de un entero
entero sin signo int_sqrt ( entero sin signo s )    
{
	// Cero da cero
    //Uno rinde uno
	si ( s <= 1 )    
		devuelve s ; 

    // Estimación inicial (debe ser demasiado alta)
	entero sin signo x0 = s / 2 ;      

	// Actualizar
	entero sin signo x1 = ( x0 + s / x0 ) / 2 ;          

	mientras ( x1 < x0 ) // Comprobación de límites   	
	{
		x0 = x1 ;  
		x1 = ( x0 + s / x0 ) / 2 ;        
	}		
	devuelve x0 ; 
}

Por ejemplo, si se calcula la raíz cuadrada entera de 2000000 utilizando el algoritmo anterior, se obtiene la secuencia En total, se necesitan 13 pasos de iteración. Aunque el método de Heron converge cuadráticamente cerca de la solución, al principio se obtiene menos de un bit de precisión por iteración. Esto significa que la elección de la estimación inicial es fundamental para el rendimiento del algoritmo. $${\displaystyle {\begin{aligned}&1000000\rightarrow 500001\rightarrow 250002\rightarrow 125004\rightarrow 62509\rightarrow 31270\rightarrow 15666\rightarrow 7896\\&\rightarrow 4074\rightarrow 2282\rightarrow 1579\rightarrow 1422\rightarrow 1414\rightarrow 1414\end{aligned}}}$$

Cuando se dispone de un cálculo rápido para la parte entera del logaritmo binario o para la longitud de bitsstd::bit_width (como por ejemplo en C++20 ), es mejor empezar por que es la menor potencia de dos mayor que . En el ejemplo de la raíz cuadrada entera de 2000000 , , , y la secuencia resultante es En este caso, solo se necesitan cuatro pasos de iteración. $${\displaystyle x_{0}=2^{\lfloor (\log _{2}n)/2\rfloor +1},}$$${\displaystyle {\sqrt {n}}}$${\displaystyle \lfloor \log _{2}n\rfloor =20}$${\displaystyle x_{0}=2^{11}=2048}$$${\displaystyle 2048\rightarrow 1512\rightarrow 1417\rightarrow 1414\rightarrow 1414.}$$

El algoritmo tradicional para calcular la raíz cuadrada con lápiz y papel se basa en trabajar desde los dígitos superiores hasta los inferiores y, a medida que se va agregando cada nuevo dígito, se elige el mayor que aún dé como resultado un cuadrado . Si se detiene después de las unidades, el resultado calculado será la raíz cuadrada entera. ${\displaystyle {\sqrt {n}}}$${\displaystyle \leq n}$

Si se trabaja en base 2 , la elección del dígito se simplifica a uno entre 0 (el "candidato pequeño") y 1 (el "candidato grande"), y las manipulaciones de dígitos se pueden expresar en términos de operaciones de desplazamiento binario. Con *multiplicación, <<desplazamiento a la izquierda y >>desplazamiento lógico a la derecha, un algoritmo recursivo para encontrar la raíz cuadrada entera de cualquier número natural es:

def  entero_sqrt ( n :  int )  ->  int :
    afirmar  n  >=  0 ,  "sqrt funciona solo para entradas no negativas"
    si  n  <  2 :
        volver  n

    # Llamada recursiva:
    small_cand  =  entero_raiz_cuadrada ( n  >>  2 )  <<  1
    lata_grande  =  lata_pequeña  +  1
    si  gran_cand  *  gran_cand  >  n :
        devuelve  small_cand
    demás :
        devolver  gran_cand


# equivalentemente:
def  entero_iter_sqrt ( n :  int )  ->  int :
    afirmar  n  >=  0 ,  "sqrt funciona solo para entradas no negativas"
    si  n  <  2 :
        volver  n

    # Encuentra el monto del cambio. Consulta también [[Buscar el primer conjunto]],
    # desplazamiento = ceil(log2(n) * 0,5) * 2 = ceil(ffs(n) * 0,5) * 2
    cambio  =  2
    mientras  ( n  >>  desplazamiento )  !=  0 :
        desplazamiento  +=  2

    # Desenrolle el bucle de ajuste de bits.
    resultado  =  0
    mientras  shift  >=  0 :
        resultado  =  resultado  <<  1
        gran_cand  =  (
            resultado  +  1
        )   # Igual que resultado ^ 1 (xor), porque el último bit siempre es 0.
        si  gran_cand  *  gran_cand  <=  n  >>  cambio :
            resultado  =  gran_cand
        cambio  -=  2

    devolver  resultado

Las presentaciones tradicionales en papel del algoritmo dígito por dígito incluyen varias optimizaciones que no están presentes en el código anterior, en particular el truco de restar previamente el cuadrado de los dígitos anteriores, lo que hace innecesario un paso de multiplicación general. Véase Métodos de cálculo de raíces cuadradas § Sistema de numeración binario (base 2) para ver un ejemplo. ^[1]

El algoritmo de raíz cuadrada de Karatsuba es un algoritmo rápido para números enteros grandes de "50 a 1.000.000 de dígitos" si se utilizan la división Karatsuba de Burnikel-Ziegler y la multiplicación Karatsuba . ^[2]

A continuación se muestra un ejemplo de algoritmo para números enteros sin signo de 64 bits. El algoritmo:

1. Normaliza la entrada dentro de u64_isqrt .
2. Llama a u64_normalized_isqrt_rem , que requiere una entrada normalizada.
3. Llama a u32_normalized_isqrt_rem con la mitad más significativa de los bits de entrada normalizados, que ya estarán normalizados ya que los bits más significativos siguen siendo los mismos.
4. Continúa recursivamente hasta que haya un algoritmo que sea más rápido cuando el número de bits sea lo suficientemente pequeño.
5. Luego, u64_normalized_isqrt_rem toma la raíz cuadrada del entero devuelto y el resto para producir los resultados correctos para el u64 normalizado dado .
6. u64_isqrt luego desnormaliza el resultado.

/// Realiza una raíz cuadrada de Karatsuba en un `u64`.
función pública u64_isqrt ( mut n : u64 ) -> u64 {     
    si n <= u32 :: MAX como u64 {      
        // Si `n` cabe en un `u32`, deje que la función `u32` lo maneje.
        devuelve u32_isqrt ( n como u32 ) como u64 ;     
    } demás {  
        // El cambio de normalización satisface la raíz cuadrada de Karatsuba
        // condición previa del algoritmo "a₃ ≥ b/4" donde a₃ es el más
        // cuarto significativo de los bits de `n` y b es el número de
        // valores que pueden representarse por ese cuarto de los bits.
        //
        // b/4 entonces serían todos 0 excepto el segundo más significativo
        // bit (010...0) en binario. Como a₃ debe ser al menos b/4, a₃
        // el bit más significativo o su vecino debe ser un 1. Dado que a₃
        // los bits más significativos son los bits más significativos de `n`, el
        // lo mismo se aplica a 'n'.
        //
        // La razón para desplazarse por un número par de bits es porque un
        // un número par de bits produce la raíz cuadrada desplazada a la
        // izquierda por la mitad del cambio de normalización:
        //
        // raíz cuadrada(n << (2 * p))
        // raíz cuadrada(2.pow(2 * p) * n)
        // raíz cuadrada(2.pow(2 * p)) * raíz cuadrada(n)
        // 2.pow(p) * raíz cuadrada(n)
        // raíz cuadrada(n) << p
        //
        // Al desplazar un número impar de bits se obtiene un feo sqrt(2)
        // multiplicado en.
        constante MÁSCARA DE BITS DE IGUALIZACIÓN : u32 = ! 1 ;   
        deje que el desplazamiento_de_normalización = n.ceros_inicial ( ) y MÁSCARA_DE_BITS_PARES ;     
        n <<= desplazamiento_normalización ;  

        sea ​​( s , _ ) = u64_normalizado_isqrt_rem ( n );    

        deje que el desplazamiento_de_desnormalización = desplazamiento_de_normalización / 2 ;     
        retorna s >> desnormalización_desplazamiento ;   
    }
}

/// Realiza una raíz cuadrada de Karatsuba en un `u64` normalizado y devuelve el cuadrado
/// raíz y resto.
función  u64_normalizada_isqrt_rem ( n : u64 )  -> ( u64 , u64 ) {  
    constante MEDIOS_BITS : u32 = u64 :: BITS >> 1 ;     
    const CUARTO_BITS : u32 = u64 :: BITS >> 2 ;     
    constante MITAD_INFERIOR_1_BITS : u64 = ( 1 << MEDIO_BITS ) - 1 ;       

    ¡debug_assert! (
        n . ceros_inicial () <= 1 ,  
        "La entrada no está normalizada: {n} tiene {} bits cero iniciales, en lugar de 0 o 1" .
        n . ceros_inicialmente ()
    );

    sea ​​hi = ( n >> MEDIOS BITS ) como u32 ;       
    sea ​​lo = n & MITAD_INFERIOR_1_BITS ;     

    sea ​​( s_prime , r_prime ) = u32_normalizado_isqrt_rem ( hi );    

    sea ​​numerador = (( r_prime como u64 ) << CUARTO_BITS ) | ( lo >> CUARTO_BITS );           
    sea ​​denominador = ( s_prime como u64 ) << 1 ;       

    sea ​​q = numerador / denominador ;     
    sea ​​u = numerador % denominador ;     

    sea ​​mut s = ( s_prime << CUARTO_BITS ) como u64 + q ;          
    sea ​​mut r = ( u << CUARTO_BITS ) | ( lo & (( 1 << CUARTO_BITS ) - 1 ));              
    sea ​​q_cuadrado = q * q ;     
    si r < q_cuadrado {    
        r + = 2 * s - 1 ;      
        es -= 1 ;  
    }
    r -= q_cuadrado ;  

    retorna ( s , r );  
}

Algunos lenguajes de programación dedican una operación explícita al cálculo de la raíz cuadrada de un número entero además del caso general o pueden extenderse mediante bibliotecas para este fin.

• Métodos para calcular raíces cuadradas