Raíz cuadrada entera

Mayor entero menor o igual a la raíz cuadrada

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.}$

Observación introductoria

Sean y números enteros no negativos. ${\displaystyle y}$ ${\displaystyle 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}}}$ ${\displaystyle 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}}}$ ${\displaystyle k}$

Elige cualquiera y calcula . ${\displaystyle k}$ ${\textstyle \lfloor {\sqrt {y\times 100^{k}}}\rfloor }$

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

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]} ${\displaystyle 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)}$ ${\displaystyle y}$ ${\displaystyle 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 {sqrtForever} }$ ${\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 detenersevoid 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() .

Algoritmos básicos

La raíz cuadrada entera de un entero no negativo se puede definir como ${\displaystyle 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{ and }}5^{2}\ngtr 27}$

Algoritmo que utiliza búsqueda lineal

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

Búsqueda lineal mediante adición

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

Algoritmo que utiliza búsqueda binaria

La búsqueda lineal comprueba secuencialmente cada valor hasta que llega al más pequeño donde . ${\displaystyle x}$ ${\displaystyle 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ásR = 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.

Algoritmo que utiliza el método de Newton

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 }$

Criterio de parada

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.

Dominio de computación

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

Usando solo división de números enteros

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}$

Ejemplo de implementación en C

// Raíz cuadrada de un enteroentero sin signo int_sqrt ( entero sin signo s )    {// Cero da cero //Uno rinde unosi ( s <= 1 )    devuelve s ;  // Estimación inicial (debe ser demasiado alta)entero sin signo x0 = s / 2 ;      // Actualizarentero sin signo x1 = ( x0 + s / x0 ) / 2 ;          mientras ( x1 < x0 ) // Comprobación de límites   {x0 = x1 ;  x1 = ( x0 + s / x0 ) / 2 ;        }devuelve x0 ; }

Ejemplo numérico

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.}$$

Algoritmo dígito por dígito

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}$

Uso de operaciones bit a bit

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]

Algoritmo de raíz cuadrada de Karatsuba

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

En lenguajes de programación

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.

Véase también

• Métodos para calcular raíces cuadradas

Notas

1. Las raíces cuadradas de los cuadrados perfectos (por ejemplo, 0, 1, 4, 9, 16) son números enteros. En todos los demás casos, las raíces cuadradas de los números enteros positivos son números irracionales.
2. No es de sorprender que la multiplicación repetida por 100 sea una característica en Jarvis (2006)
3. La parte fraccionaria de las raíces cuadradas de los cuadrados perfectos se representa como 000... .

Referencias

1. Woo, C (junio de 1985). "Algoritmo de raíz cuadrada mediante ábaco (archivado)". Archivado desde el original el 6 de marzo de 2012.
2. Zimmermann, Paul (1999). "Raíz cuadrada de Karatsuba" (PDF) . Informe de investigación n.° 3805. Inria (publicado el 24 de mayo de 2006). Archivado desde el original (PDF) el 11 de mayo de 2023.
3. "BigInteger - Documentación de la Capilla 2.1". Documentación de la Capilla - Documentación de la Capilla 2.1 .
4. "CLHS: Función SQRT, ISQRT". Common Lisp HyperSpec (TM) .
5. "Matemáticas - Crystal 1.13.2". Documentación de la API del lenguaje de programación Crystal .
6. "Matemáticas - El lenguaje Julia". Documentación de Julia - El lenguaje Julia .
7. "iroot- Ayuda de Maple". Ayuda - Maplesoft .
8. "Funciones matemáticas". Documentación de la biblioteca estándar de Python .
9. "4.3.2 Numéricos genéricos". Documentación de Racket .
10. "clase Integer - Documentación de RDoc". Documentación de RDoc .
11. "Elementos del anillo ℤ de números enteros - Anillos conmutativos estándar". Documentación de SageMath .
12. "Informe revisado7 sobre el esquema de lenguaje algorítmico". Estándares de esquema .
13. "página del manual de mathfunc - Funciones matemáticas de Tcl". Manual de Tcl/Tk 8.6 .

Enlaces externos

• Jarvis, Ashley Frazer (2006). "Raíces cuadradas por sustracción" (PDF) . Mathematical Spectrum . 37 : 119–122.
• Minsky, Marvin (1967). "9. Los números reales computables". Computación: máquinas finitas e infinitas . Prentice-Hall. ISBN 0-13-165563-9.OCLC 0131655639  .
• "Una visión geométrica del algoritmo de la raíz cuadrada".