Raíz cuadrada entera

La raíz cuadrada entera (isqrt) de un número natural n es un número positivo m , que es igual al entero más grande menor o igual a la raíz cuadrada de n ,

{\mbox{isqrt}}(n)=\lpiso {\sqrt {n}}\rpiso .

Por ejemplo, ya que y . ${\mbox{isqrt}}(27)=5$ ${\ estilo de visualización 5 ^ {2} = 25 <27}$ ${\ estilo de visualización 6 ^ {2} = 36> 27}$

Algoritmo

Una de las formas de calcular y es usar el método de Newton para encontrar una solución a la ecuación usando la fórmula iterativa [1] [2] ${\ sqrt {n}}$ ${\mbox{isqrt}}(n)$ ${\ estilo de visualización x^{2}-n=0}$

{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 converge cuadráticamente a en [3] . Se puede probar que si se elige como valor inicial, uno puede detenerse tan pronto como ${\ estilo de visualización \ {x_ {k} \}}$ ${\ sqrt {n}}$ $k\to\infty$ ${\ estilo de visualización x_ {0} = n}$

{\ estilo de visualización |x_{k+1}-x_{k}|<1}

para asegurar eso $\lpiso x_{k+1}\rpiso =\lpiso {\sqrt {n))\rpiso .$

Usando solo divisiones enteras

Para calcular números enteros muy grandes n , puede usar la división de cociente con un resto en ambas operaciones de división. La ventaja es el uso de solo números enteros para cada valor intermedio, lo que evita el uso de representar números como números de punto flotante . Esto es equivalente a usar la fórmula iterativa $\lpiso {\sqrt {n}}\rpiso$

{x}_{k+1}=\left\lpiso {\frac {1}{2}}\left(x_{k}+\left\lpiso {\frac {n}{x_{k} }}\right\rpiso \right)\right\rpiso ,\quad k\geq 0,\quad x_{0}>0,\quad x_{0}\in \mathbb {Z} .

Basado en el hecho de que

\left\lpiso {\frac {1}{2}}\left(x_{k}+\left\lpiso {\frac {n}{x_{k))}\right\rpiso \right)\ derecha\rpiso =\izquierda\lpiso {\frac {1}{2}}\left(x_{k}+{\frac {n}{x_{k))}\derecha)\derecha\rpiso ,

se puede demostrar que la secuencia alcanza en un número finito de iteraciones [4] . $\lpiso {\sqrt {n}}\rpiso$

Sin embargo, no será necesariamente el punto fijo de la fórmula iterativa anterior. Se puede mostrar lo que será un punto fijo si y sólo si no es un cuadrado perfecto. Si es un cuadrado perfecto, la sucesión no converge, sino que entra en un ciclo de longitud dos, cambiando alternativamente y . Para que deje de funcionar basta comprobar que o bien la sucesión converge (repitiendo el valor anterior), o bien que el siguiente valor es exactamente uno mayor que el actual, en este último caso se descarta el nuevo valor. $\lpiso {\sqrt {n}}\rpiso$ $\lpiso {\sqrt {n}}\rpiso$ $n+1$ $n+1$ $\lpiso {\sqrt {n}}\rpiso$ $\lpiso {\sqrt {n}}\rpiso +1$

Uso de operaciones bit a bit

Si *significa multiplicar, <<significa desplazar a la izquierda y significa >>desplazar lógico a la derecha, el algoritmo recursivo para encontrar la raíz cuadrada entera de cualquier número natural es el siguiente:

función enteroSqrt(n): si n < 0: error "integerSqrt solo funciona con entrada no negativa" de lo contrario si n < 2: regreso m más: candidatopequeño = integerSqrt(n >> 2) << 1 candidato grande = candidato pequeño + 1 si granCandidato*granCandidato > n: volver pequeñoCandidato más: volver gran Candidato

O iteración en lugar de recursividad:

función enteroSqrt(n): si n < 0: error "integerSqrt solo funciona con entrada no negativa" # Encuentra el cambio más grande. cambio = 2 nDesplazado = n >> desplazamiento mientras que nShifted ≠ 0 y nShifted ≠ n: cambio = cambio + 2 nDesplazado = n >> desplazamiento turno = turno - 2 # Encuentra los dígitos del resultado. resultado = 0 mientras que el desplazamiento ≥ 0: resultado = resultado << 1 resultadocandidato = resultado + 1 si resultadocandidato*resultadocandidato ≤ n >> turno: resultado = resultadocandidato turno = turno - 2 resultado devuelto

Área computacional

Aunque es un número irracional para la mayoría de los valores , la secuencia contiene solo miembros racionales si es racional. Así, usando este método, no es necesario salirse del campo de los números racionales para calcular , lo que tiene alguna ventaja teórica. ${\ sqrt {n}}$ $norte$ ${\ estilo de visualización \ {x_ {k} \}}$ $x_0$ ${\mbox{isqrt}}(n)$

Criterios de parada

Se puede mostrar cuál es el número más grande para el criterio de parada $c=1$

|x_{k+1}-x_{k}|<c\

lo que asegura que en el algoritmo anterior. $\lpiso x_{k+1}\rpiso =\lpiso {\sqrt {n))\rpiso$

En aplicaciones que utilizan formatos distintos a los racionales (por ejemplo, punto flotante), la constante de parada debe elegirse menor que uno para evitar errores de redondeo.

Véase también

Métodos para calcular raíces cuadradas

Notas

↑ El método a veces se llama "babilónico".
↑ Fred Akalin, Cálculo de la raíz cuadrada entera , 2014
↑ SG Johnson, MIT Course 18.335, Square Roots via Newton's Method , 4 de febrero de 2015
↑ Enrique Cohen. Un curso de teoría de números algebraicos computacionales. - Berlín, Heidelberg, Nueva York: Springer, 1996. - T. 138. - S. 38-49. — (Textos de posgrado en matemáticas). — ISBN 3-540-55640-0 .

Enlaces

Una vista geométrica del algoritmo de la raíz cuadrada

Algoritmos de teoría de números
Pruebas de simplicidad	Molinero Miller - Rabín Luca-Lemaire pepina Agrawala - Kayala - Sajonia Ruiseñor - Strassen
Encontrar números primos	Iterando sobre divisores Tamiz de Eratóstenes tamiz de atkin Tamiz Sundarama
Factorización	Iterando sobre divisores método Fermat p −1 Método de Pollard Algoritmo ρ de Pollard método Lehmann Método de la curva elíptica (algoritmo de Lenstra) algoritmo de dixon tamiz cuadrado
logaritmo discreto	Algoritmo de Gelfond-Shanks Algoritmo de Polig-Hellman Método ρ de Pollard Algoritmo del canguro de Pollard algoritmo de Adleman algoritmo COS
Encontrar MCD	Algoritmo de Euclides Algoritmo avanzado Algoritmo binario
Módulo aritmético	algoritmo de Montgomery Teorema del resto chino
Multiplicación y división de números.	Algoritmo Karatsuba Algoritmo de Toom-Cook Algoritmo de Schönhage-Strassen Algoritmo del Führer Algoritmo de Harvey-van der Hoeven Algoritmo de Burnickel-Ziegler
Calcular la raíz cuadrada	Algoritmo de Tonelli-Shanks Algoritmo de Berlekamp-Rabin