Métodos para calcular raíces cuadradas

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 13 de enero de 2022; las comprobaciones requieren 4 ediciones .

Los métodos de raíz cuadrada son algoritmos computacionales para calcular los valores aproximados de las raíces cuadradas principales (o no negativas) (generalmente indicadas como , o ) de un número real. Aritméticamente, esto significa que si se da un número , el procedimiento encuentra un número que, cuando se multiplica por sí mismo, da . Algebraicamente, esto significa el procedimiento para encontrar una raíz no negativa de una ecuación . Geométricamente, esto significa construir un lado de un cuadrado con un área dada. ${\ estilo de visualización {\ sqrt {S))}$ ${\sqrt[{2}]{S))$ ${\ estilo de visualización S^{1/2}}$ $S$ $S$ ${\ estilo de visualización x^{2}-S=0}$

Cualquier número real tiene dos raíces [1] . El valor principal de la raíz cuadrada de la mayoría de los números es un número irracional con una secuencia infinita de dígitos decimales. Como resultado, la representación decimal de cualquier raíz cuadrada solo puede calcularse aproximadamente con una precisión finita (lugares decimales). Sin embargo, incluso si tomamos la raíz cuadrada de un número entero, para que el resultado tenga una representación finita, algunos de los procedimientos utilizados para calcular la raíz solo pueden devolver una serie de aproximaciones con precisión creciente.

La representación de fracción continua de un número real se puede utilizar en lugar de la expansión decimal o binaria y esta representación tiene la propiedad de que la raíz cuadrada de cualquier número racional (que no es un cuadrado perfecto) tiene un período, es decir, una expansión periódica similar a cómo los números racionales tienen expansión repetitiva del sistema numérico decimal.

Los métodos analíticos más comúnmente aceptados son iterativos y constan de dos pasos: encontrar un valor inicial adecuado y luego refinar iterativamente hasta alcanzar un cierto criterio de parada. El valor inicial puede ser cualquier número, pero si está más cerca del valor final, se requerirán menos iteraciones. El método de este tipo más famoso, e incluso más conveniente para la programación, es el método de Newton, que se basa en el cálculo de la derivada. Varios métodos, como la división manual de Horner o la expansión en serie, no requieren un valor inicial. En algunas aplicaciones, se requiere encontrar la raíz cuadrada entera , que es la raíz cuadrada redondeada al entero más cercano (en este caso, se puede usar un procedimiento modificado).

El método utilizado depende de cómo se utilizará el resultado (es decir, qué tan preciso debe ser el resultado) y qué herramientas están disponibles. Los métodos se pueden dividir aproximadamente en aquellos que se pueden hacer mentalmente, que requieren lápiz y papel, o aquellos que se implementan como un programa y se ejecutan en computadoras u otros dispositivos informáticos. Se puede tener en cuenta la velocidad de convergencia (cuántas iteraciones se requerirán para lograr una precisión determinada), la complejidad computacional de las operaciones individuales (como la división) o iteraciones y la distribución de errores (la precisión del resultado).

Los procedimientos para encontrar raíces cuadradas (en particular, la raíz de 2) se conocen desde al menos la época de la antigua Babilonia (siglo XVII a. C.). El método de Heron del siglo I en Egipto fue el primer algoritmo verificable para calcular la raíz cuadrada. Los métodos analíticos modernos comenzaron a desarrollarse después de la adopción de los números arábigos en Europa occidental a principios del Renacimiento . En estos días, casi todos los dispositivos informáticos tienen una función de raíz cuadrada rápida y precisa como una construcción de lenguaje de programación integrada, una función de biblioteca o una declaración de hardware que se basa en los procedimientos que se describen a continuación.

Puntuación inicial

Muchos algoritmos iterativos de raíz cuadrada requieren un valor aleatorio inicial. Este valor debe ser un número positivo distinto de cero. Debe estar entre 1 y , el número cuya raíz cuadrada buscamos, ya que la raíz cuadrada debe estar dentro de estos límites. Si el valor inicial está muy lejos de la raíz, el algoritmo necesitará más iteraciones. Si comienza con (o con ), funcionará con iteraciones adicionales solo para obtener el orden de la raíz. Por lo tanto, es útil tener una estimación aproximada de la raíz, que puede tener poca precisión, pero es fácil de calcular. En general, cuanto más precisa sea la estimación, más rápida será la convergencia. Para el método de Newton (también llamado método de Babilonia o de Heron), un valor inicial ligeramente mayor que la raíz proporciona una convergencia más rápida que un valor inicial menor que la raíz. $S$ ${\ estilo de visualización x_ {0} = 1}$ $S$ ${\tfrac {1}{2}}\vert \log _{2}S\vert$

En términos generales, la estimación se considera en un intervalo arbitrario en el que se sabe que contiene una raíz (como ). Obtener una mejor estimación implica obtener límites más estrechos en el intervalo o una mejor aproximación funcional a. Esta última generalmente significa usar polinomios de orden superior para la aproximación, aunque no todas las aproximaciones usan polinomios. Los métodos de estimación comunes son escalares, lineales, hiperbólicos y logarítmicos. El sistema decimal generalmente se usa para estimar mentalmente o en papel. El sistema numérico binario es más adecuado para evaluaciones por computadora. Al evaluar, el exponente y la mantisa generalmente se tratan por separado. ${\ estilo de visualización [x_{0},S/x_{0}]}$ ${\ estilo de visualización f (x).}$

Puntuación decimal

Por lo general, el número se expresa en forma exponencial como , donde , y n es un número entero, entonces una estimación de la posible raíz cuadrada puede ser , donde . $S$ ${\ estilo de visualización \ veces 10 ^ {2n})$ $1\leqslant a<100$ ${\sqrt {a}}\times 10^{n}$ $1\leqslant {\sqrt {a}}<10$

Estimaciones escalares

Los métodos escalares dividen todo el rango en contenedores y la puntuación en cada contenedor se representa con un solo número. Si el rango se trata como un solo intervalo, entonces la media aritmética (5.5) o la media geométrica () son estimaciones aceptables. Las estimaciones absolutas y relativas para estas estimaciones diferirán. En general, un solo número será muy inexacto. Más estimaciones precisas dividen el rango en dos o más intervalos, pero la estimación escalar sigue siendo muy aproximada. ${\sqrt {10}}\aproximadamente 3{,}16)\veces 10^{n}$

Para dos intervalos divididos geométricamente, la raíz cuadrada se puede estimar como [2] . ${\sqrt {S}}={\sqrt {a}}\times 10^{n}$

{\sqrt {S}}\approx {\begin{cases}2\cdot 10^{n}&{\text{if }}a<10,\\6\cdot 10^{n}&{ \text{if}}a\geqslant 10.\end{casos}}

Esta estimación tiene un error absoluto máximo en el punto = 100 y un error relativo máximo del 100 % en el punto = 1. ${\displaystyle 4\cdot 10^{n))$

Por ejemplo, con una descomposición , la puntuación será . , con un error absoluto de 246 y un error relativo de casi el 70%. ${\ estilo de visualización S = 125348}$ ${\displaystyle 12{,}5348\times 10^{4))$ ${\sqrt {S}}\aprox. 6\cdot 10^{2}=600$ ${\sqrt {125348}}=354{,}0$

Estimación lineal

La mejor estimación y el método estándar es la aproximación lineal de la función en un arco pequeño. Si, como se indicó anteriormente, el exponente se extrae del número y el intervalo se reduce a , puede usar una secante o una tangente en algún lugar del arco para aproximar, pero la regresión directa por mínimos cuadrados será más precisa. $y = x^2$ $S$ ${\ estilo de visualización [1100]}$

La línea recta, obtenida por el método de los mínimos cuadrados, minimiza la distancia media entre la estimación y el valor de la función. Su ecuación es . Después de transformar y redondear los coeficientes para simplificar los cálculos, obtenemos ${\ estilo de visualización y = 8{,} 7x-10}$ $x=0{,}115y+1{,}15$

{\sqrt {S}}\approx (a/10+1{,}2)\cdot 10^{n}

Esta es la mejor estimación promedio que se puede obtener con un intento de aproximación lineal de la función en el intervalo . La estimación tiene un error absoluto máximo de 1,2 en el punto a=100 y un error relativo máximo del 30 % en los puntos S=1 y 10 [3] . $y=x^2$ ${\ estilo de visualización [1100]}$

Para dividir por 10, resta uno del exponente o, en sentido figurado, mueve el punto decimal una posición hacia la izquierda. Para esta fórmula, cualquier constante sumada igual a 1 más un pequeño incremento da una estimación satisfactoria, por lo que no es necesario memorizar el número exacto. La aproximación (redondeada o no redondeada) utilizando una línea recta que resta la región en términos de precisión no da más de un signo correcto. El error relativo es más de 1/2 2 , por lo que da menos de 2 bits de información. La precisión está muy limitada, ya que la región abarca dos órdenes de magnitud, que es bastante grande para este tipo de estimación. $a$ ${\ estilo de visualización [1100]}$

Se puede obtener una estimación significativamente mejor usando una aproximación lineal por partes, es decir, usando varios segmentos que se aproximan al subarco del arco original. Cuantos más segmentos se utilicen, mejor será la aproximación. El uso más común de las tangentes. El punto crítico es cómo dividir el arco y dónde colocar los puntos de contacto. Un método efectivo para dividir el arco de y=1 a y=100 es el geométrico: para dos intervalos, el límite del intervalo es la raíz cuadrada del intervalo original, 1 * 100, es decir, y . Para tres intervalos habrá raíces cúbicas - , y , y así sucesivamente. Para dos intervalos, este es un número muy conveniente. Es fácil obtener rectas tangentes en los puntos de contacto y . Sus ecuaciones son: y . Invirtiendo las ecuaciones, obtenemos que las raíces cuadradas son iguales a y . Entonces para : ${\ estilo de visualización [1, {\ sqrt [{2}] {100}}]}$ ${\ estilo de visualización [{\ sqrt [{2}] {100)), 100]}$ $[1,{\sqrt[{3}]{100}}],[{\sqrt[{3}]{100}},({\sqrt[{3}]{100}})^{ 2}]$ ${\ estilo de visualización [({\ sqrt [{3}] {100))) ^ {2}, 100]}$ ${\sqrt[{2}]{100}}=10$ $x={\sqrt {1*{\sqrt {10}}}}$ $x={\sqrt {10*{\sqrt {10))))$ $y=3{,}56x-3{,}16$ $y=11{,}2x-31{,}6$ $x=0{,}28y+0{,}89$ ${\ estilo de visualización x = 0{,}089y+2{,}8}$ ${\displaystyle S=a\cdot 10^{2n))$

{\sqrt {S}}\approx {\begin{cases}(0{,}28a+0{,}89)\cdot 10^{n}&{\text{if }}a<10, \\(0{,}089a+2{,}8)\cdot 10^{n}&{\text{si}}a\geqslant 10.\end{casos}}

Los valores absolutos máximos están en los límites derechos de los intervalos, en los puntos a=10 y 100, y son iguales a 0,54 y 1,7, respectivamente. Los errores relativos máximos aparecen en los extremos de los intervalos, en los puntos a=1, 10 y 100, y son iguales al 17%. 17% o 0,17. Son mayores que 1/10, por lo que el método da una precisión de menos de un dígito significativo.

Estimación hiperbólica

En algunos casos, la estimación hiperbólica puede ser válida, ya que la hipérbola también es una curva convexa y puede ubicarse a lo largo del arco Y = x 2 mejor que una línea recta. El estimador hiperbólico es computacionalmente más difícil porque requiere la división por un número de punto flotante. Una aproximación hiperbólica casi óptima a x 2 en el intervalo es . Después de la transformación obtenemos . Entonces para : ${\ estilo de visualización [1100]}$ ${\ estilo de visualización y = 190/(10-x)-20}$ ${\ estilo de visualización x = -190/(y+20)+10}$ ${\displaystyle S=a\cdot 10^{2n))$

{\sqrt {S}}\approx \left({\frac {-190}{a+20}}+10\right)\cdot 10^{n}

La división de punto flotante debe tener una precisión de un decimal, ya que toda evaluación da esa precisión, y tal división se puede hacer mentalmente. La estimación hiperbólica es, en promedio, mejor que la estimación escalar o lineal. Su error absoluto máximo es 1,58 en el punto 100 y su error relativo máximo es 16,0% en el punto 10. Para el peor de los casos a=10, la puntuación es 3,67. Si comenzamos en 10 y aplicamos las iteraciones de Newton-Rapson directamente, se necesitan dos iteraciones, que arrojan 3,66, antes de alcanzar la precisión de la estimación hiperbólica. Para un caso más típico como 75, la estimación hiperbólica es 8,00 y se necesitan 5 iteraciones de Newton-Rapson a partir de 75 para obtener un resultado más preciso.

Evaluación aritmética

Un método similar a la aproximación lineal por partes, pero que usa solo operaciones aritméticas en lugar de ecuaciones algebraicas, usa la tabla de multiplicar a la inversa: la raíz cuadrada de los números entre 1 y 100 está entre 1 y 10, así que como sabemos que 25 es un cuadrado exacto (5 × 5) y 36 es un cuadrado exacto (6 × 6), entonces la raíz cuadrada de un número que es mayor que 25 pero menor que 36 comienza con el número 5. Lo mismo ocurre con los números entre otros cuadrados. Este método da el primer dígito correcto, pero su precisión es solo de un dígito: el primer dígito de la raíz cuadrada de 35, por ejemplo, es 5, pero la raíz de 35 en sí misma es casi igual a 6.

Es mejor dividir el intervalo entre dos cuadrados por la mitad. Entonces, la raíz de cualquier número entre 25 y la mitad de 36 (que es 30,5) se evalúa como 5, otros números mayores que 30,5 hasta 36 se evalúan como 6 [4] . El procedimiento requiere muy poca aritmética para encontrar el medio de dos productos de la tabla. Aquí hay una tabla de tales números:

a	plaza más cercana	$k={\sqrt {a))$ est.
1 a 2.5	1 (= 1 2 )	una
2,5 a 6,5	4 (= 2 2 )	2
6,5 a 12,5	9 (= 3 2 )	3
12,5 a 20,5	16 (= 4 2 )	cuatro
20,5 a 30,5	25 (= 5 2 )	5
30,5 a 42,5	36 (= 6 2 )	6
42,5 a 56,5	49 (= 72 )	7
56,5 a 72,5	64 (= 82 )	ocho
72,5 a 90,5	81 (= 9 2 )	9
90,5 a 100	100 (= 102 )	diez

La operación final será la multiplicación de la puntuación k por la potencia de las decenas dividida por la mitad, de modo que para , ${\displaystyle S=a\cdot 10^{2n))$

{\sqrt {S}}\aprox. k\cdot 10^{n}

El método proporciona una precisión de un dígito significativo porque redondea al mejor primer dígito.

El método se puede extender a 3 cifras significativas en la mayoría de los casos interpolando entre los cuadrados más cercanos. Si , entonces es aproximadamente igual a k más una fracción igual a la diferencia entre a y , dividida por la diferencia entre los dos cuadrados: ${\displaystyle k^{2}\leqslant a<(k+1)^{2))$ ${\ sqrt {a}}$ $k^{2}$

{\sqrt {a}}\aprox. k+R

dónde

{\displaystyle R={\frac {(ak^{2})}{(k+1)^{2}-k^{2))))

La operación final, como la anterior, es la multiplicación del resultado por la potencia de diez dividida por la mitad

{\sqrt {S}}={\sqrt {a}}\cdot 10^{n}\aprox. (k+R)\cdot 10^{n}

El número k es el dígito decimal y R es la fracción a convertir a decimal. Una fracción generalmente tiene un dígito en el numerador y uno o dos dígitos en el denominador, por lo que la conversión a decimal se puede hacer mentalmente.

Ejemplo: encuentre la raíz cuadrada de 75. , entonces a es 75 y n es 0. Según la tabla de multiplicar, la raíz cuadrada de la mantisa debe ser 8 con una fracción porque , a , es demasiado grande. Entonces k es 8 siendo la fracción la representación decimal de R . La fracción R tiene un numerador y un denominador. 11/17 es un poco más pequeño que 12/18, que es 2/3 o 0,67, por lo que 0,66 es una buena suposición (está bien adivinar aquí ya que el error es pequeño). Entonces el valor de la raíz es . √ 75 a tres cifras significativas sería 8,66, por lo que una puntuación de tres cifras significativas es buena. No todas las estimaciones que utilizan este método son tan precisas, pero están bastante cerca. $75=75\times 10^{2\cdot 0}$ ${\ estilo de visualización 8 \ veces 8 = 64}$ ${\ estilo de visualización 9 \ veces 9 = 81}$ $75-k^{2}=11$ ${\ estilo de visualización 81-k ^ {2} = 17}$ $8+0{,}66=8{,}66$

Evaluación binaria

Cuando el trabajo se lleva a cabo en el sistema binario (digamos, en un procesador de computadora), se expresa como , donde , la raíz cuadrada se puede estimar como $S$ ${\ estilo de visualización \ veces 2 ^ {2n})$ ${\displaystyle 0{,}1_{2}\leqslant a<10_{2))$ ${\sqrt {S}}={\sqrt {a}}\times 2^{n}$

{\sqrt {S}}\approx (0{,}485+0{,}485\cdot a)\cdot 2^{n}

que es una regresión de mínimos cuadrados sobre los 3 bits más significativos. tiene un error absoluto máximo de 0.0408 en el punto =2 y un error relativo máximo de 3.0% en el punto =1. Para los cálculos, es conveniente una estimación redondeada (porque los coeficientes son potencias de 2) ${\ sqrt {a}}$ $a$ $a$

{\sqrt {S}}\approx (0{,}5+0{,}5\cdot a)\cdot 2^{n}

[5]

que tiene un error absoluto máximo de 0.086 en el punto 2 y un error relativo máximo de 6.1% en los puntos y . ${\ estilo de visualización a = 0{,} 5}$ $a=2{,}0$

Para la aproximación binaria da Desde , la estimación da un error absoluto de 19 y un error relativo de 5,3%. El error relativo es ligeramente inferior a 1/2 4 , por lo que la aproximación tiene una precisión de más de 4 bits. $S=125348=1\;1110\;1001\;1010\;0100_{2}=1{,}1110\;1001\;1010\;0100_{2}\veces 2^{16}\,$ ${\sqrt {S}}\approx (0{,}5+0{,}5\cdot a)\cdot 2^{8}=1{,}0111\;0100\;1101\;0010_ {2}\cdot 1\;0000\;0000_{2}=1{,}456\cdot 256=372{,}8.$ ${\sqrt {125348}}=354{,}0$

Se puede obtener una estimación de hasta 8 bits buscando en la tabla los 8 bits más significativos , dado que el bit más significativo está implícito en la mayoría de las representaciones de punto flotante, y los bits menos significativos después de los 8 bits deben redondearse. La tabla contiene 256 bytes de raíces cuadradas de 8 bits precalculadas. Por ejemplo, para el índice 11101101 2 , que es 1,8515625 10 en decimal , el valor de la tabla es 10101110 2 , que es 1,359375 10 en decimal , la raíz cuadrada de 1,8515625 10 a 8 bits (2+ signo decimal). $a$ $a$

método babilónico

Quizás el primer algoritmo utilizado para la aproximación sea el método conocido como método babilónico , aunque no hay evidencia directa, aparte de la inferencia hipotética, de que los matemáticos babilónicos usaran este método [6] . El método también se conoce como el método de Heron , en honor al matemático griego del siglo I Heron , quien dio la primera descripción explícita del método en su trabajo de 60 años Metrica [7] La técnica básica es que si x es mayor que el cuadrado raíz de un número real no negativo S , entonces será menos raíz y viceversa. Por lo tanto, es razonable esperar que el promedio de estos dos números esté más cerca de la raíz (la prueba formal de este hecho se basa en la desigualdad sobre la media aritmética, geométrica y armónica , que muestra que este promedio es siempre mayor que el cuadrado raíz, lo que asegura la convergencia). El método es equivalente a usar el método de Newton para resolver la ecuación . ${\ estilo de visualización {\ sqrt {S))}$ ${\tfrac{S}{x}}$ ${\ estilo de visualización x^{2}-S=0}$

Más precisamente, si x es una suposición inicial para , y el error en nuestra estimación es tal que , podemos expandir los paréntesis y obtener ${\ estilo de visualización {\ sqrt {S))}$ $\varepsilon$ $S=(x+\varepsilon)^{2}$

\varepsilon ={\frac {Sx^{2}}{2x+\varepsilon}}\approx {\frac {Sx^{2}}{2x}},

porque _

{\ estilo de visualización \ varepsilon \ ll x}

Por lo tanto, podemos compensar el error y actualizar nuestra estimación anterior

x+\varepsilon \approx x+{\frac {Sx^{2}}{2x}}={\frac {S+x^{2}}{2x}}={\frac {{\frac {S }{x}}+x}{2}}\equiv x_{\text{actualizado}}

Dado que el error calculado no fue exacto, se convertirá en nuestra próxima aproximación. El proceso de actualización continúa hasta que alcanzamos la precisión deseada. Es un algoritmo con convergencia cuadrática , lo que significa que el número de dígitos correctos de la aproximación (en términos generales) se duplica con cada iteración. Funciona así:

Empezamos con cualquier valor inicial positivo (cuanto más cerca de la verdadera raíz cuadrada de S , mejor). $x_{0}$
Igualamos el promedio entre y (usamos la media aritmética para aproximar la media geométrica ). $x_{{n+1}}$ $x_{n}$ ${\ Displaystyle {\ tfrac {S} {x_ {n}}}}$
Repita el paso 2 hasta que alcancemos la precisión deseada.

El algoritmo se puede representar de la siguiente manera:

x_{0}\approx {\sqrt {S)),

x_{n+1}={\frac {1}{2}}\left(x_{n}+{\frac {S}{x_{n}}}\right),

{\sqrt {S}}=\lim _{n\to \infty }x_{n}.

El algoritmo también funciona bien para números p -ádicos , pero no se puede usar para identificar raíces cuadradas reales con raíces cuadradas p -ádicas. Se puede, por ejemplo, construir una sucesión de números racionales obtenida por este método que converge a +3 en el caso de los números reales, pero a -3 en los números biádicos.

Ejemplo

Para calcular √ S , donde S = 125348, con seis dígitos significativos, utilice el método de estimación aproximada descrito anteriormente

{\begin{alineado}{\begin{matriz}{rlll}x_{0}&=6\cdot 10^{2}&=600{,}000\\[0,3em]x_{1} &={\frac {1}{2}}\izquierda(x_{0}+{\frac {S}{x_{0}}}\derecha)&={\frac {1}{2}}\izquierda (600{,}000+{\frac {125348}{600{,}000}}\right)&=404{,}457\\[0.3em]x_{2}&={\frac {1}{ 2}}\left(x_{1}+{\frac {S}{x_{1}}}\right)&={\frac {1}{2}}\left(404{,}457+{\ fracción {125348}{404{,}457}}\right)&=357{,}187\\[0.3em]x_{3}&={\frac {1}{2}}\left(x_{2 }+{\frac {S}{x_{2}}}\right)&={\frac {1}{2}}\left(357{,}187+{\frac {125348}{357{,} 187}}\right)&=354{,}059\\[0.3em]x_{4}&={\frac {1}{2}}\left(x_{3}+{\frac {S}{ x_{3}}}\derecha)&={\frac {1}{2}}\left(354{,}059+{\frac {125348}{354{,}059}}\derecha)&=354 {,}045\\[0.3em]x_{5}&={\frac {1}{2}}\left(x_{4}+{\frac {S}{x_{4}}}\right) &={\frac {1}{2}}\left(354{,}045+{\frac {125348}{354{,}045}}\right)&=354{,}045\end{matriz} }\end{alineado}}

Por lo tanto ${\sqrt {125348}}\aproximadamente 354{,}045$

Convergencia

Suponga que x 0 > 0 y S > 0. Entonces, para cualquier n x n > 0. El error relativo x n se define como

\varepsilon _{n}={\frac {x_{n}}{\sqrt {S}}}-1>-1

y entonces

x_{n}={\sqrt {S}}\cdot (1+\varepsilon _{n}).

Ahora se puede demostrar que

\varepsilon _{n+1}={\frac {\varepsilon _{n}^{2}}{2(1+\varepsilon _{n}})))\geqslant 0.

y consecuentemente

\varepsilon _{n+2}\leqslant \min \left\({\frac {\varepsilon _{n+1}^{2)){2)),{\frac {\varepsilon _{n +1}}{2}}\derecho\}

y esto implica convergencia garantizada, y esta convergencia es cuadrática .

Convergencia en el peor de los casos

Si usamos un método de estimación aproximada con el método babilónico, los peores casos de precisión en orden descendente son:

{\begin{alineado}S&=1;&x_{0}&=2;&x_{1}&=1{,}250;&\varepsilon _{1}&=0{,}250.\\ S&=10;&x_{0}&=2;&x_{1}&=3{,}500;&\varepsilon _{1}&<0{,}107.\\S&=10;&x_{0}& =6;&x_{1}&=3{,}833;&\varepsilon _{1}&<0{,}213.\\S&=100;&x_{0}&=6;&x_{1}&= 11{,}333;&\varepsilon_{1}&<0{,}134.\end{alineado}}

y luego de todos modos

\varepsilon _{1}\leqslant 2^{-2}.\,

\varepsilon _{2}<2^{-5}<10^{-1}.\,

\varepsilon _{3}<2^{-11}<10^{-3}.\,

\varepsilon _{4}<2^{-23}<10^{-6}.\,

\varepsilon _{5}<2^{-47}<10^{-14}.\,

\varepsilon _{6}<2^{-95}<10^{-28}.\,

\varepsilon _{7}<2^{-191}<10^{-57}.\,

\varepsilon _{8}<2^{-383}<10^{-115}.\,

Los errores de redondeo debilitan la convergencia. Se recomienda almacenar al menos un dígito adicional por encima de la precisión x n deseada para minimizar los errores de redondeo.

Método Bakhshali

Este método para encontrar la aproximación de la raíz cuadrada fue escrito en un antiguo manuscrito indio llamado el manuscrito Bakhshali . El método es equivalente a dos iteraciones del método babilónico con valor inicial x 0 . Por lo tanto, el algoritmo es cuadráticamente convergente, lo que significa que el número de signos válidos de la aproximación aumenta unas cuatro veces con cada iteración [8] . La representación del algoritmo en notación moderna es la siguiente: Calcular , sea x 0 2 la aproximación inicial a la raíz S . Las iteraciones se realizan secuencialmente. ${\ estilo de visualización {\ sqrt {S))}$

{\begin{alineado}a_{n}&={\frac {S-x_{n}^{2}}{2x_{n}}},\\b_{n}&=x_{n} +a_{n},\\x_{n+1}&=b_{n}-{\frac {a_{n}^{2}}{2b_{n}}}=(x_{n}+a_{ n})-{\frac {a_{n}^{2}}{2(x_{n}+a_{n})}}.\end{alineado}}

Esto se puede usar para construir una aproximación racional a la raíz cuadrada, comenzando con un número entero. Si es un entero elegido cercano a S y es la diferencia cuyo valor absoluto se minimiza, entonces la primera iteración se puede escribir de la siguiente manera: ${\ estilo de visualización x_ {0} = N}$ $N^2$ $d=NS^{2}$

{\sqrt {S}}\aprox. N+{\frac {d}{2N}}-{\frac {d^{2}}{8N^{3}+4Nd}}={\frac {8N ^{4}+8N^{2}d+d^{2}}{8N^{3}+4Nd}}={\frac {N^{4}+6N^{2}S+S^{2 }}{4N^{3}+4NS}}={\frac{N^{2}(N^{2}+6S)+S^{2}}{4N(N^{2}+S)} }.

El método de Bakhshali se puede generalizar para calcular una raíz arbitraria, incluidas las raíces fraccionarias [9] .

Ejemplo

Usemos el mismo ejemplo que se dio para el método babilónico. Sea Entonces la primera iteración da ${\ estilo de visualización S = 125348.}$

{\begin{alineado}x_{0}&=600\\a_{1}&={\frac {125348-600^{2}}{2\times 600}}&&=&-195{, }543\\b_{1}&=600+(-195{,}543)&&=&404{,}456\\x_{1}&=404{,}456-{\frac {(-195{, }543)^{2}}{2\times 404{,}456}}&&=&357{,}186\end{alineado}}

De manera similar, la segunda iteración da

{\begin{alineado}a_{2}&={\frac {125348-357{,}186^{2}}{2\times 357{,}186}}&&=&-3{,} 126\\b_{2}&=357{,}186+(-3{,}126)&&=&354{,}060\\x_{2}&=354{,}06-{\frac {(- 3{,}1269)^{2}}{2\times 354{,}06}}&&=&354{,}046\end{alineado}}

Número por número

Este es un método para encontrar secuencialmente cada dígito de la raíz cuadrada. El método es más lento que el babilónico, pero tiene algunas ventajas.

Es más fácil de calcular manualmente.
Se sabe que cada signo encontrado de la raíz es correcto, es decir, no se cambiará en las próximas iteraciones.
Si la representación de la raíz cuadrada tiene un número finito de dígitos, el algoritmo termina después del último dígito encontrado. Por lo tanto, se puede usar para probar que un número dado es un cuadrado perfecto .
El algoritmo funciona en cualquier sistema numérico y, por supuesto, el funcionamiento del algoritmo depende del sistema numérico elegido.

Los palos de Napier incluyen funciones adicionales para realizar este algoritmo. El algoritmo para calcular la raíz enésima dígito a dígito es una generalización de este método.

Principio básico

Considere primero el caso de encontrar la raíz cuadrada de un número Z , que es el cuadrado de un número de dos dígitos XY , donde X es el dígito de las decenas e Y es el dígito de las unidades. Tenemos:

Z=(10X+Y)^{2}=100X^{2}+20XY+Y^{2}

Primero, definamos el valor de X . X es el dígito más grande tal que X 2 no excede a Z , del cual se eliminan los dos últimos dígitos.

En la siguiente iteración, conectamos un par de dígitos multiplicando X por 2 y colocando el resultado en la posición de las decenas, y luego tratando de averiguar a qué es igual Y.

Dado que en nuestro caso la respuesta es la raíz cuadrada exacta, el algoritmo se detiene.

La misma idea se puede extender para calcular una raíz cuadrada arbitraria. Imagina que podemos encontrar la raíz cuadrada de N como la suma de n números positivos tales que

N=(a_{1}+a_{2}+a_{3}+\dotsb +a_{n})^{2}.

Al reutilizar la identidad

{\ estilo de visualización (x+y)^{2}=x^{2}+2xy+y^{2},}

el lado derecho se puede representar como

{\begin{alineado}&(a_{1}+a_{2}+a_{3}+\dotsb +a_{n})^{2}\\=&\,a_{1}^{ 2}+2a_{1}a_{2}+a_{2}^{2}+2(a_{1}+a_{2})a_{3}+a_{3}^{2}+\puntosb + a_{n-1}^{2}+2\izquierda(\sum_{i=1}^{n-1}a_{i}\derecha)a_{n}+a_{n}^{2}\ \=&\,a_{1}^{2}+[2a_{1}+a_{2}]a_{2}+[2(a_{1}+a_{2})+a_{3}]a_ {3}+\dotsb +\left[2\left(\sum _{i=1}^{n-1}a_{i}\right)+a_{n}\right]a_{n}.\end {alineado}}

Esta expresión nos permite encontrar la raíz cuadrada por selección sucesiva de valores . Suponga que los números ya han sido seleccionados, entonces el término m-ésimo está dado por , donde es la aproximación encontrada a la raíz cuadrada. Ahora cada nueva selección debe satisfacer la recursividad $ai}$ $a_{1},\ldots,a_{m-1}$ $Y_{m}=[2P_{m-1}+a_{m}]a_{m},$ ${\displaystyle P_{m-1}=\sum_{i=1}^{m-1}a_{i))$ $soy$

X_{m}=X_{m-1}-Y_{m},

entonces para todos en el valor inicial Si se encuentra la raíz cuadrada exacta. Si no, entonces la suma da una aproximación adecuada a la raíz cuadrada y será un error de aproximación. $X_{m}\geqslant0$ $1\leqslant m\leqslant n,$ $X_{0}=N.$ ${\ estilo de visualización X_ {n} = 0,}$ $ai}$ $X_n$

Por ejemplo, en decimal tenemos

N=(a_{1}\cdot 10^{n-1}+a_{2}\cdot 10^{n-2}+\cdots +a_{n-1}\cdot 10+a_{n })^{2},

donde son indicadores de la posición de los dígitos, y los coeficientes . En cada m-ésimo paso del cálculo de la raíz cuadrada, se encuentra una raíz cuadrada aproximada. La magnitud y los términos sumables están dados por las fórmulas ${\ estilo de visualización 10 ^ {ni}}$ $a_{i}\in \{0,1,2,\ldots,9\}$ $P_{m-1}$ $Y_{m}$

P_{m-1}=\sum_{i=1}^{m-1}a_{i}\cdot 10^{ni}=10^{n-m+1}\sum_{i =1}^{m-1}a_{i}\cdot 10^{mi-1},

Y_{m}=[2P_{m-1}+a_{m}\cdot 10^{nm}]a_{m}\cdot 10^{nm}=\left[20\sum_{i= 1}^{m-1}a_{i}\cdot 10^{mi-1}+a_{m}\right]a_{m}\cdot 10^{2(nm)}.

Dado que los indicadores de posición tienen una potencia par de 10, solo necesitamos trabajar con el par de dígitos más altos en el término restante en cualquier paso m-ésimo. La siguiente sección organiza este procedimiento. $Y_{m}$ $X_{m-1}$

Obviamente, se puede usar un método similar para calcular la raíz cuadrada en cualquier sistema numérico, no necesariamente en decimal. Por ejemplo, encontrar la raíz cuadrada dígito por dígito en binario es bastante eficiente porque el valor se busca en el pequeño conjunto de dígitos {0,1}. Esto hace que el cálculo sea más rápido, ya que en cada paso el valor es igual o igual a . El hecho de que solo haya dos posibilidades para también facilita la elección de un valor en el m-ésimo paso del cálculo. Esto se debe a que solo necesitamos verificar que para Si esta condición se cumple, tomamos ; y si no, entonces tomamos También el hecho de que la multiplicación por 2 se lleva a cabo desplazando hacia la izquierda ayuda en los cálculos. $ai}$ $Y_{m}$ $Y_{m}=0$ ${\ estilo de visualización a_ {m} = 0}$ $Y_{m}=2P_{m-1}+1$ ${\ estilo de visualización a_ {m} = 1}$ $soy$ $soy$ ${\displaystyle Y_{m}\leqslant X_{m-1))$ $a_{m}=1.$ ${\ estilo de visualización a_ {m} = 1}$ $a_{m}=0.$

Sistema numérico decimal

Escribamos el número original en forma decimal. Los números se escriben de forma similar a la división mediante un algoritmo de división larga y , como en la división larga, la raíz cuadrada se escribirá en la línea superior. Ahora dividamos los números en pares, comenzando con una coma, en ambos lados. El punto decimal de la raíz cuadrada estará en el punto decimal del cuadrado. Un dígito de raíz cuadrada se escribe sobre un par de dígitos de raíz cuadrada.

Comenzando desde la posición más a la izquierda, realizamos el siguiente procedimiento para cada par de dígitos:

Bajamos el par más alto de dígitos no usados (si se usan todos los dígitos, escribimos "00") y los escribimos a la derecha del resto del paso anterior (no hay resto en el primer paso). En otras palabras, multiplica el resto por 100 y suma dos dígitos. Este será el valor actual de c .
Encuentre p , y y x así:
- Que sea parte de la raíz ya encontrada , ignorando el punto decimal. (Para el primer paso, p = 0.) ${\símbolo en negrita {p}}$
- Determine el mayor número tal que . Usaremos una nueva variable . ${\símbolo en negrita {x}}$ ${\ estilo de visualización x (20p + x) \ leqslant c}$ ${\ estilo de visualización {\ símbolo de negrita {y}} = x (20p + x)}$
  - Tenga en cuenta que simplemente se duplica p con el dígito x adjunto a la derecha . ${\ estilo de visualización 20p+x}$
  - Tenga en cuenta que x se puede encontrar adivinando al azar cuál debería ser c /(20• p ), con un cálculo de prueba de y , luego x se toma más alto o más bajo dependiendo del resultado.
- Colocamos el dígito como el siguiente dígito de la raíz, es decir, encima del par de dígitos cuadrados que se acaban de bajar. Ahora el próximo valor de p se obtiene del valor anterior usando la fórmula . $X$ ${\ estilo de visualización p \ veces 10 + x}$
Resta y de c para formar un nuevo residuo.
Si el resto es cero y no hay más dígitos para bajar, el algoritmo se detiene. De lo contrario, volvemos al paso 1 y realizamos la siguiente iteración.

Ejemplos

Encuentra la raíz cuadrada de 152.2756.

1 2. 3 4 / \/ 01 52.27 56 01 1*1 <= 1 < 2*2 x = 1 01 y = x*x = 1*1 = 1 00 52 22*2 <= 52 < 23*3 x = 2 00 44 y = (20+x)*x = 22*2 = 44 08 27 243*3 <= 827 < 244*4 x = 3 07 29 y = (240+x)*x = 243*3 = 729 98 56 2464*4 <= 9856 < 2465*5 x = 4 98 56 y = (2460+x)*x = 2464*4 = 9856 00 00 El algoritmo se detiene: Respuesta 12.34

Sistema numérico binario

Esta sección utiliza el formalismo de la sección Cálculo dígito por dígito , con modificaciones menores, que y cada uno es igual a o . Ahora repasamos todo desde abajo hasta y construimos una solución aproximada como la suma de todos para los que encontramos un valor. Para determinar si o es igual a , tomamos . Si (es decir, el cuadrado de nuestra aproximación incluida no excede el cuadrado original), entonces establecemos , de lo contrario establecemos y . Para evitar elevar al cuadrado cada paso, almacenamos la diferencia y la actualizamos en cada iteración configurando c . Inicialmente configuramos para el más grande con . $N^{2}=(a_{n}+\dotsb +a_{0})^{2}$ $soy$ $2^{m}$ ${\ estilo de visualización 0}$
$2^{m}$ $2^{n}$ $2^0$ ${\displaystyle P_{m}=a_{n}+a_{n-1}+\ldots +a_{m))$ $ai}$
$soy$ $2^{m}$ ${\ estilo de visualización 0}$ ${\displaystyle P_{m}=P_{m+1}+2^{m))$ ${\displaystyle P_{m}^{2}\leqslant N^{2))$ $2^{m}$ ${\displaystyle a_{m}=2^{m))$ ${\ estilo de visualización a_ {m} = 0}$ $P_{m}=P_{m+1}$
${\ Displaystyle P_ {m}}$ $X_{m}=N^{2}-P_{m}^{2}$ ${\displaystyle X_{m}=X_{m+1}-Y_{m))$ ${\displaystyle Y_{m}=P_{m}-P_{m+1}=2P_{m+1}a_{m}+a_{m}^{2))$
$a_{n}=P_{n}=2^{n}$ $norte$ ${\displaystyle (2^{n})^{2}=4^{n}\leqslant N^{2))$

Como optimización adicional, almacenamos y , dos términos en el caso de que no sea cero, en variables separadas , : $P_{m+1}2^{m+1}$ ${\ estilo de visualización (2 ^ {m}) ^ {2}}$ $Y_{m}$ $soy$ ${\ Displaystyle c_ {m}}$ ${\ Displaystyle d_ {m}}$

c_{m}=P_{m+1}2^{m+1}

d_{m}=(2^{m})^{2}

Y_{m}={\begin{casos}c_{m}+d_{m}&{\text{si}}a_{m}=2^{m}\\0&{\text{si} }a_{m}=0\end{casos}}

${\ Displaystyle c_ {m}}$ y se puede actualizar de manera eficiente en cada paso: ${\ Displaystyle d_ {m}}$

c_{m-1}=P_{m}2^{m}=(P_{m+1}+a_{m})2^{m}=P_{m+1}2^{m} +a_{m}2^{m}={\begin{casos}c_{m}/2+d_{m}&{\text{si}}a_{m}=2^{m}\\c_{ m}/2&{\text{si}}a_{m}=0\end{casos}}

d_{m-1}={\frac {d_{m}}{4}}

Darse cuenta de

c_{-1}=P_{0}2^{0}=P_{0}=N

, que es el resultado final devuelto por la siguiente función.

Implementación del algoritmo en lenguaje C [10] :

int32_t isqrt(int32_tn) {afirme(("el valor de entrada debe ser no negativo", n > 0)); int32_t x = n; // int32_t c = 0; // // comienza con la mayor potencia de cuatro <= n

X_{{n+1}}

c_n

d_{n}

int32_t d = 1 << 30; // Establece el segundo bit más significativo en 1. // Igual que ((sin firmar)INT32_MAX + 1) / 2. mientras que (d > n) d >>= 2; while (d != 0) // para { si (x >= c + d) // si , entonces { x -= c + d; // c = (c >> 1) + d; //

{\displaystyle d_{n}\puntos d_{0))

{\displaystyle X_{m+1}\geqslant Y_{m))

{\displaystyle a_{m}=2^{m))

{\displaystyle X_{m}=X_{m+1}-Y_{m))

c{m-1}=c_{m}/2+d_{m}(a_{=}2^{m})

} más c >>= 1; // re >>= 2; //

c_{m-1}=c_{m}/2(a_{m}=0)

d_{m-1}=d_{m}/4

} volver c; //

c_{{-1}}

}

Es posible implementar un algoritmo más rápido tanto en notación binaria como decimal si se utilizan tablas para la selección, es decir, la implementación del principio de usar más memoria reduce el tiempo de ejecución [11] .

Identidad exponencial

Las calculadoras de bolsillo suelen implementar buenos programas de logaritmo exponencial y natural . Luego, el cálculo de la raíz cuadrada S se realiza utilizando las propiedades de los logaritmos ( ) y exponenciales ( ): ${\ estilo de visualización \ln x^{n}=n\ln x}$ ${\ estilo de visualización e ^ {\ ln x} = x}$

{\sqrt {S}}=e^{{\frac {1}{2}}\ln S}.

El denominador de la fracción corresponde a la raíz enésima . En nuestro caso, el denominador es 2. La misma identidad se usa para calcular la raíz cuadrada usando tablas de logaritmos o reglas de cálculo .

Un método iterativo con dos variables

Este método es aplicable para encontrar la raíz cuadrada de y converge mejor para . Esto, sin embargo, no es una limitación significativa para la computación en computadoras, ya que en las representaciones de números binarios en punto flotante y punto fijo es trivial multiplicar por una potencia entera de 4 y luego corregir a la potencia deseada de 2 cambiando el exponente o desplazamiento, respectivamente. Por lo tanto, se puede desplazar dentro de . Además, el siguiente método no usa divisiones generales, sino solo sumas, restas, multiplicaciones y divisiones por una potencia de dos. La última de estas acciones se implementa trivialmente. La desventaja del método es la acumulación de errores, a diferencia de los métodos iterativos con una variable como el babilónico. ${\ estilo de visualización 0<S<3\,\!}$ ${\ estilo de visualización S \ aproximadamente 1}$ ${\ estilo de visualización S \, \!}$ ${\ estilo de visualización {\ sqrt {S))}$ ${\ estilo de visualización S \, \!}$ ${\frac{1}{2}}\leqslant S<2$

Paso inicial del método

a_{0}=S\,\!

c_{0}=S-1\,\!

pasos iterativos

a_{n+1}=a_{n}-a_{n}c_{n}/2\,\!

c_{n+1}=c_{n}^{2}(c_{n}-3)/4\,\!

Entonces (para ). $a_{n}\rightarrow {\sqrt {S))$ $c_{n}\flecha derecha 0$

Tenga en cuenta que la convergencia , y por lo tanto , es cuadrática. $c_{n}\,\!$ $a_{n}\,\!$

La demostración del método es bastante sencilla. Primero reescribimos la definición iterativa como $c_{n}\,\!$

1+c_{n+1}=(1+c_{n})(1-c_{n}/2)^{2}\,\!

Ahora, de frente, se prueba que

{\displaystyle S(1+c_{n})=a_{n}^{2))

y por tanto la convergencia al resultado deseado está asegurada por la convergencia a 0, que, a su vez, se sigue de . $a_{n}\,\!$ ${\ estilo de visualización {\ sqrt {S))}$ $c_{n}\,\!$ $-1<c_{0}<2\,\!$

Este método fue desarrollado alrededor de 1950 por M. W. Wilks , D. J. Wheeler y S. Gill [12] para su uso en el EDSAC , una de las primeras computadoras electrónicas [13] . Posteriormente, el método se generalizó a raíces no cuadradas [14] .

Métodos iterativos para calcular el recíproco de la raíz cuadrada de un número

Los siguientes son métodos iterativos para calcular el recíproco de la raíz cuadrada de S , es decir, . Si se encuentra tal valor, lo encontramos simplemente multiplicando: . Estas iteraciones solo usan multiplicaciones y no usan divisiones. Porque los métodos son más rápidos que el método babilónico . Sin embargo, los métodos son inestables, si el valor inicial no está cerca del recíproco del valor raíz, las iteraciones divergen. Por lo tanto, puede ser ventajoso iterar primero con el método babilónico para obtener una estimación aproximada de la raíz antes de comenzar a utilizar estos métodos. ${\ estilo de visualización 1/{\ sqrt {S))}$ ${\ estilo de visualización {\ sqrt {S))}$ ${\sqrt {S}}=S\cdot (1/{\sqrt {S}})$

La aplicación del método de Newton a la ecuación produce un método que converge cuadráticamente y usa tres multiplicaciones en cada paso: ${\ estilo de visualización (1/x^{2})-S=0}$ $x_{n+1}={\frac {x_{n}}{2}}\cdot (3-S\cdot x_{n}^{2})=x_{n}\cdot \left( {\frac {3}{2}}-{\frac {S}{2}}\cdot x_{n}^{2}\right).$
Otra iteración se obtiene del método Halley , que es el método del Jefe de Hogar de segundo orden. El método converge cúbicamente , pero usa cinco multiplicaciones por iteración: ${\displaystyle y_{n}=S\cdot x_{n}^{2))$ $x_{n+1}={\frac {x_{n}}{8}}\cdot (15-y_{n}\cdot (10-3\cdot y_{n}))=x_{n }\cdot \left({\frac {15}{8}}-y_{n}\cdot \left({\frac {10}{8}}-{\frac {3}{8}}\cdot y_ {n}\derecho)\derecho)$ .
Cuando se trabaja con números de punto fijo , la multiplicación por 3 y la división por 8 se pueden implementar por turnos y sumas. Cuando se trabaja con coma flotante, el método de Halley se puede reducir a cuatro multiplicaciones por iteración precalculando y ajustando todas las demás constantes para compensar: ${\sqrt {\frac{3}{8}}}S$ $y_{n}={\sqrt {\frac {3}{8}}}S\cdot x_{n}^{2}$ , $x_{n+1}=x_{n}\cdot \left({\frac {15}{8}}-y_{n}\cdot \left({\sqrt {\frac {25}{6 }}}-y_{n}\derecho)\derecho)$ .

Algoritmo de Goldschmidt

Algunas computadoras usan el algoritmo de Goldschmidt para calcular y simultáneamente . El algoritmo de Goldschmidt encuentra más rápido que la iteración de Newton-Rapson en computadoras con operaciones de suma y multiplicación compartidas y un procesador de punto flotante canalizado o dos procesadores de punto flotante independientes [15] . ${\ estilo de visualización {\ sqrt {S))}$ ${\ estilo de visualización 1/{\ sqrt {S))}$ ${\ estilo de visualización {\ sqrt {S))}$

La primera forma de escribir el algoritmo de Goldschmidt comienza con

{\ estilo de visualización b_ {0} = S}

Y_{0}\aprox. 1/{\sqrt {S))

(generalmente se usa la búsqueda de tabla)

y_{0}=Y_{0}

x_{0}=Sy_{0}

y se realizan iteraciones

b_{n+1}=b_{n}Y_{n}^{2}

Y_{n+1}=(3-b_{n+1})/2

{\ estilo de visualización x_{n+1}=x_{n}Y_{n+1}}

y_{n+1}=y_{n}Y_{n+1}

hasta que esté lo suficientemente cerca de 1 o se haya realizado un número fijo de iteraciones. Las iteraciones convergen a $bi}$

\lim _{n\to \infty}x_{n}={\sqrt {S))

\lim _{n\to \infty }y_{n}=1/{\sqrt {S))

Tenga en cuenta que puede omitir el cálculo de o , y si desea ambos, puede usarlo al final en lugar de evaluar en cada iteración. $x_{n}$ $y_{n}$ $x_{n}=Sy_{n}$

El segundo método, que usa las operaciones combinadas de multiplicación y suma , comienza con

y_{0}\aprox. 1/{\sqrt {S))

(generalmente se usa la búsqueda de tabla)

x_{0}=Sy_{0}

h_{0}=y_{0}/2

y se realizan iteraciones

r_{n}=0{,}5-x_{n}h_{n}

{\displaystyle x_{n+1}=x_{n}+x_{n}r_{n))

{\displaystyle h_{n+1}=h_{n}+h_{n}r_{n))

hasta que se acerque lo suficiente a 0, o se realice un número fijo de iteraciones. Los valores convergen a $Rhode Island}$

\lim _{n\to \infty}x_{n}={\sqrt {S))

\lim _{n\to \infty}2h_{n}=1/{\sqrt {S))

Serie de Taylor

Si N es una aproximación a , la mejor aproximación se puede encontrar utilizando la serie de Taylor de la función de raíz cuadrada : ${\ estilo de visualización {\ sqrt {S))}$

{\sqrt {N^{2}+d}}=N\sum _{n=0}^{\infty }{\frac {(-1)^{n}(2n)!}{( 1-2n)n!^{2}4^{n))}{\frac {d^{n}}{N^{2n}}}=N\left(1+{\frac {d}{2N ^{2))}-{\frac {d^{2}}{8N^{4}}}+{\frac {d^{3}}{16N^{6}}}-{\frac {5d ^{4}}{128N^{8}}}+\cdots\right)

El orden de convergencia es igual al número de términos utilizados en la serie. Cuando se usan dos términos, el método es equivalente al método babilónico . Cuando se usan tres términos, cada iteración usa casi tantas operaciones como las que usa la aproximación de Bakhshali , pero la convergencia es más débil. Por lo tanto, este método no es un método de cálculo particularmente eficiente. Para maximizar la tasa de convergencia, se debe elegir N para que sea lo más pequeño posible. ${\frac{|d|}{N^{2))}\,$

Expansión en fracciones continuas

Las irracionalidades cuadráticas (números de la forma , donde a , b y c son números enteros), y en particular las raíces cuadradas de números enteros, tienen fracciones continuas periódicas . A veces, el objetivo no es encontrar el valor numérico de la raíz cuadrada, sino expandirlo a una fracción continua y, por lo tanto, a su aproximación racional. Sea S un número positivo cuya raíz se encuentra. Ahora sea a la aproximación inicial y r el resto, entonces podemos escribir Como tenemos , podemos expresar la raíz cuadrada de S como ${\frac{a+{\sqrt {b}}}{c}}$ $S=a^{2}+r.$ $Sa^{2}=({\sqrt {S}}+a)({\sqrt {S}}-a)=r$

{\sqrt {S}}=a+{\frac {r}{a+{\sqrt {S}}}}.

Aplicando esta expresión para al denominador de la fracción, obtenemos ${\ estilo de visualización {\ sqrt {S))}$

{\sqrt {S}}=a+{\frac {r}{a+(a+{\frac {r}{a+{\sqrt {S)))))))=a+{\frac {r} {2a+{\frac {r}{a+{\sqrt {S)))))).

notación compacta

El numerador/denominador de la expansión de fracción continua (ver a la izquierda) es difícil de escribir y también difícil de encajar en el sistema de formato de documentos existente. Por esta razón, se ha desarrollado una notación especial para representar de forma compacta las partes enteras y periódicas de las fracciones continuas. Una de esas convenciones usa la "línea discontinua" léxica para representar la barra entre el numerador y el denominador, lo que permite que la fracción se escriba horizontalmente en lugar de verticalmente:

{\sqrt {S}}=a+{\frac {r|}{|2a}}+{\frac {r|}{|2a}}+{\frac {r|}{|2a}} +\cpuntos

Aquí, cada trazo horizontal (en fracción) está representado por tres trazos, dos verticales y uno horizontal, que se separan de . $r$ $2a$

Una notación aún más compacta tiene una forma especial

{\ estilo de visualización [a; 2a, 2a, 2a,...]}

Para las fracciones continuas periódicas (que son todas raíces cuadradas), la parte repetida se enumera solo una vez, con una barra sobre la parte repetida:

[a;{\overline{2a}}]

Para √ 2 el valor es 1, por lo que la representación será $a$

{\ estilo de visualización [1; {\ overline {2}}]}

Siguiendo este camino, obtenemos la fracción continua generalizada para la raíz cuadrada ${\sqrt {S}}=a+{\cfrac {r}{2a+{\cfrac {r}{2a+{\cfrac {r}{2a+\ddots ))))))$

El primer paso para calcular dicha fracción para obtener una raíz cuadrada es sustituir la raíz y elegir el número de denominadores. Por ejemplo, en forma canónica es 1 y para √ 2 , es 1, entonces la fracción continua numérica para 3 denominadores es $r$ $a$

{\sqrt {2}}\aprox. 1+{\cfrac {1}{2+{\cfrac {1}{2+{\cfrac {1}{2}}}}}}

Paso 2. La fracción continua se enrolla, un denominador a la vez, para obtener una fracción racional cuyo numerador y denominador son números enteros. El proceso de plegado se ve así (tomando los primeros tres denominadores):

1+{\cfrac {1}{2+{\cfrac {1}{2+{\cfrac {1}{2})))))=1+{\cfrac {1}{2+{ \cfrac {1}{\frac {5}{2}}}}}

{\displaystyle =1+{\cfrac {1}{2+{\cfrac {2}{5))))=1+{\cfrac {1}{\frac {12}{5))))

=1+{\cfrac {5}{12}}={\frac {17}{12}}

Finalmente (paso 3), dividimos el numerador por el denominador de la fracción racional para obtener una aproximación de la raíz:

{\ estilo de visualización 17 \ div 12 = 1 {,} 42}

redondeado a tres decimales.

El valor real de la raíz √ 2 es 1,41 con tres dígitos significativos. El error relativo es 0,17%, por lo que una fracción racional es buena hasta casi tres decimales. Si tomamos más denominadores, obtenemos una mejora constante en la aproximación: cuatro denominadores dan una fracción , lo que da casi 4 dígitos de precisión, etc. ${\frac{41}{29}}=1{,}4137$

Las fracciones continuas están disponibles en tablas para al menos números pequeños y constantes bien conocidas. Para números arbitrarios en notación decimal, los valores precalculados son probablemente inútiles. La siguiente tabla de fracciones racionales pequeñas, llamadas convergentes , se deriva de fracciones continuas canónicas para varias constantes:

√ S	tiro continuo	~ decimal	Fracciones adecuadas
√2 _	${\ estilo de visualización [1; {\ overline {2}}]}$	1.41421	${\frac {3}{2)),{\frac {7}{5)),{\frac {17}{12)),{\frac {41}{29)),{\frac {99}{70}}$
√ 3	${\ estilo de visualización [1; {\ overline {1,2}}]}$	1.73205	${\frac {2}{1)),{\frac {5}{3)),{\frac {7}{4)),{\frac {19}{11)),{\frac {26}{15)),{\frac{71}{41)),{\frac{97}{56}}$
√5 _	${\ estilo de visualización [2; {\ overline {4}}]}$	2.23607	${\frac {9}{4)),{\frac {38}{17)),{\frac {161}{72))$
√ 6	$[2;{\overline {2,4}}]$	2.44949	${\frac {5}{2)),{\frac {22}{9)),{\frac {49}{20)),{\frac {218}{89))$
√ 10	${\ estilo de visualización [3; {\ overline {6}}]}$	3.16228	${\frac{19}{6)),{\frac{117}{37}}$
${\ estilo de visualización {\ sqrt {\ pi))}$	${\ estilo de visualización [1; 1, 3, 2, 1, 1, 6...]}$	1.77245	${\frac {2}{1)),{\frac {7}{4)),{\frac {16}{9)),{\frac {23}{13)),{\frac {39}{22}}$
${\ estilo de visualización {\ sqrt {e))}$	${\ estilo de visualización [1; 1,1,1,5,1,1...]}$	1.64872	${\frac {2}{1)),{\frac {3}{2)),{\frac {5}{3)),{\frac {28}{17)),{\frac {33}{20)),{\frac{61}{37}}$
${\ estilo de visualización {\ sqrt {\ phi}}}$	${\ estilo de visualización [1; 3, 1, 2, 11, 3, 7...]}$	1.27202	${\frac {4}{3)),{\frac {5}{4)),{\frac {14}{11))$

Nota: Todas las fracciones aplicables se enumeran hasta el denominador 99.

En general, cuanto mayor sea el denominador de una fracción racional, mejor será la aproximación. También se puede demostrar que cortar una fracción continua da como resultado una fracción racional, con una mejor aproximación a la raíz de cualquier fracción con un denominador menor o igual que el denominador de esa fracción. Por ejemplo, ninguna fracción con un denominador inferior a 70 es tan buena como 99/70 que se aproxima a √2 .

Método de secuencia de Luke

La sucesión de Lucas del primer tipo está definida por la relación recursiva ${\ Displaystyle U_ {n} (P, Q)}$

$U_{n}(P,Q)={\begin{casos}0&{\text{if }}n=0\\1&{\text{if }}n=1\\P\cdot U_{ n-1}(P,Q)-Q\cdot U_{n-2}(P,Q)&{\text{de lo contrario}}\end{casos}}$

y su polinomio característico es

$x^{2}-P\cdot x+Q=0$

, tiene un discriminante y raíces $D=P^{2}-4Q$

${\begin{matriz}x_{1}={\dfrac {P+{\sqrt {D))}{2)),&x_{2}={\dfrac {P-{\sqrt {D)) {2}}\end{matriz}}}$

Todo esto da el siguiente valor positivo

$\lim _{n\to \infty }{\dfrac {U_{n+1}}{U_{n}}}=x_{1}$

. Entonces, si queremos obtener , podemos elegir y , y luego calcular usando y para valores grandes . La forma más eficiente de calcular y − ${\ sqrt {a}}$ ${\ estilo de visualización P = 2}$ ${\ Displaystyle Q = 1-a}$ $x_{1}=1+{\sqrt {a))$ $U_{n+1}$ $Naciones Unidas}$ $norte$ $U_{n+1}$ $Naciones Unidas}$

${\begin{bmatrix}U_{n}\\U_{n+1}\end{bmatrix}}={\begin{bmatrix}0&1\\-Q&P\end{bmatrix}}\cdot {\begin {bmatrix}U_{n-1}\\U_{n}\end{bmatrix}}={\begin{bmatrix}0&1\\-Q&P\end{bmatrix}}^{n}\cdot {\begin{bmatrix }} }U_{0}\\U_{1}\end{bmatriz}}$

Salir:

${\begin{bmatrix}0&1\\a-1&2\end{bmatrix}}^{n}\cdot {\begin{bmatrix}0\\1\end{bmatrix}}={\begin{bmatrix} U_{n}\\U_{n+1}\end{bmatriz}},$

y luego en : $n\to\infty$

${\sqrt {a}}={\frac{U_{n+1}}{U_{n}}}-1$

Aproximaciones dependientes de la representación de punto flotante

El número se representa como un número de punto flotante como . Este formato de notación también se llama notación exponencial . La raíz cuadrada de este número es igual y se pueden presentar fórmulas similares para raíces cúbicas y logaritmos. Esto no simplifica la tarea, pero si solo se requiere una aproximación, entonces es una buena estimación del orden de la mantisa. Además, entendemos que algunas potencias de p pueden resultar impares, entonces en vez de trabajar con potencias fraccionarias de la base, multiplicamos por ella y le restamos uno al grado, haciéndola par. La representación refinada se convierte en , por lo que la raíz cuadrada será . ${\ estilo de visualización m \ veces b ^ {p}}$ ${\sqrt {m}}\veces b^{\tfrac {p}{2}}$ $b^{\tfrac {p}{2))$ ${\displaystyle 3141{,}59=3{,}14159{\times}10^{3))$ ${\displaystyle 31{,}4159{\times}10^{2))$ ${\sqrt {31,4159}}{\veces}10^{1}$

Si solo se toma la parte entera de la mantisa, esta puede tomar valores del 1 al 99 y esto puede usarse como índice en una tabla de 99 raíces precalculadas para completar la estimación. Una computadora que usa la base hexadecimal puede requerir una tabla más grande, pero usando la base 2, la tabla solo constará de tres valores: los posibles bits de la parte entera de la representación refinada de la mantisa pueden ser 01 (si el exponente es par, por lo tanto, no hay cambio, y tenga en cuenta que el punto flotante del número normalizado siempre tiene un dígito alto distinto de cero), o si el exponente era impar, 10 u 11, estos son los dos primeros bits de la mantisa original. Luego, 6,25 (= 110,01 en binario) se normaliza a una potencia par, por lo que el par de bits de la mantisa es 01, mientras que 0,625 (= 0,101 en binario) se normaliza a una potencia impar, por lo que se requiere una conversión numérica a , y luego el par de bits será 10. Nótese que el bit menos significativo de la orden se refleja en el bit más significativo de la mantisa agrupada en pares. Un exponente par tiene el bit menos significativo de cero y la mantisa cuádruple comenzará en cero, mientras que un exponente impar tendrá un 1 en el bit menos significativo y la mantisa cuádruple comenzará en 1. Entonces, cuando el exponente se reduce a la mitad, es equivalente a desplazar el bit menos significativo del exponente al primer bit de la mantisa agrupada por pares. $1{,}1001\veces 2^{2}$ ${\ estilo de visualización 1{,} 01 \ veces 2 ^ {-1}}$ $10{,}1\veces 2^{-2}$

Una tabla con tres elementos se puede ampliar para incluir bits de mantisa adicionales. Sin embargo, en el caso de las computadoras, en lugar de calcular la interpolación en una tabla, muchas veces es mejor buscar una forma de cálculo más simple que dé los mismos resultados. Ahora todo depende de los detalles exactos del formato de representación del número y de las operaciones disponibles para obtener partes del número y trabajar con ellas. Por ejemplo, Fortran contiene una función EXPONENT(x)para obtener un título. El esfuerzo invertido en obtener una buena aproximación inicial vale la pena al eliminar las iteraciones adicionales del proceso de refinamiento que serían necesarias en el caso de una mala aproximación.

Muchas computadoras siguen el estándar de punto flotante IEEE (o una representación bastante cercana) y se puede obtener una aproximación de raíz cuadrada muy rápida como punto de partida para el método de Newton. La técnica para esta aproximación surge del hecho de que el formato de número flotante (base dos) se aproxima al logaritmo en base 2. Es decir, $\log _{2}(m\times 2^{p})=p+\log _{2}(m)$

Entonces, para un número de punto flotante IEEE de 32 bits (en el que el exponente tiene un desplazamiento de 127 [16] ), puede obtener un logaritmo aproximado interpretando el número como un número entero de 32 bits, multiplicándolo por y restando el desplazamiento 127, es decir ${\ estilo de visualización 2^{-23}}$

x_{\text{int}}\cdot 2^{-23}-127\approx \log _{2}(x).

Por ejemplo, el número 1.0 en hexadecimal es 0x3F800000, que puede representarse como un número entero. Usando la fórmula anterior, obtendrá lo esperado de . Del mismo modo, obtendrá 0,5 de 1,5 (=0x3FC00000). $1065353216=127\cdot 2^{23}$ $1065353216\cdot 2^{-23}-127=0$ ${\ estilo de visualización \ registro _ {2} (1 {,} 0)}$

Para obtener la raíz cuadrada, divide el logaritmo por 2 y vuelve a convertir el resultado. El siguiente programa demuestra la idea. Tenga en cuenta que el bit menos significativo del exponente se traduce deliberadamente a la mantisa. Una forma de justificar los pasos de este programa, asumiendo que es el desplazamiento del grado y es el número de bits almacenados en la mantisa, es probar $b$ $norte$

(((x_{\text{int}}/2^{n}-b)/2)+b)\cdot 2^{n}=(x_{\text{int}}-2^{ n})/2+((b+1)/2)\cdot 2^{n}.

/* Supongamos que el número flotante está en formato IEEE 754 */ #incluir <stdint.h> flotar sqrt_approx ( flotar z ) { unión { flotador f ; uint32_ti ; _ } valor = { z }; /* Convierte el tipo sin cambiar la representación de bits */ /* * Demostrar que * ((((val.i / 2^m) - b) / 2) + b) * 2^m = ((val.i - 2^m) / 2) + ((b + 1) / 2) * 2^m) * donde * b = compensación de potencia * m = número de bits en la mantisa */ valor _ yo -= 1 << 23 ; /* Resta 2^m. */ valor _ yo >>= 1 ; /* Dividir por 2. */ valor _ yo += 1 << 29 ; /* Sumar ((b + 1) / 2) * 2^m. */ valor de retorno f ; /* Interpretar como float de nuevo */ }

Las tres operaciones aritméticas que forman el núcleo de la función se pueden representar en una línea. Se puede agregar un refinamiento adicional para reducir el error relativo máximo. Por lo tanto, las tres operaciones, sin incluir la reducción a real, se pueden reescribir como

valor _ i = ( 1 << 29 ) + ( val . i >> 1 ) - ( 1 << 22 ) + a ;

donde a es un desplazamiento para reducir los errores de aproximación. Por ejemplo, con a = 0 los resultados son exactos para potencias pares de 2 (por ejemplo, 1,0), pero para otros números el resultado será algo grande (por ejemplo, 1,5 para 2,0 en lugar de 1,414... con un error del 6%). Para a = −0x4B0D2, el error relativo máximo se reduce a ±3,5%.

Si la aproximación se va a utilizar como valor inicial para el método de Newton en la ecuación , entonces es preferible la forma inversa que se muestra en la siguiente sección. ${\ estilo de visualización (1/x^{2})-S=0}$

El recíproco de la raíz cuadrada

Una variante del procedimiento anterior se presenta a continuación y se puede utilizar para calcular el inverso de la raíz cuadrada, es decir, . Esta variante fue escrita por Greg Walsh. La aproximación de desplazamiento da un error relativo de menos del 4 % y el error se reduce al 0,15 % después de una iteración del método de Newton [17] . En gráficos por computadora, esta es una forma muy eficiente de normalizar un vector. $x^{-{1 \over 2}}$

flotar invSqrt ( flotar x ) { float xhalf = 0.5f * x ; unión { flotar x ; ent i ; } tu ; tu _ x = x ; tu _ yo = 0x5f375a86 - ( u . yo >> 1 ); /* La siguiente línea se puede repetir un número arbitrario de veces para aumentar la precisión */ tu _ x = tu _ x * ( 1.5f - xmitad * u . x * u . x ); te devuelvo _ x ; }

Algunos VLSI implementan la búsqueda del recíproco de la raíz cuadrada utilizando una estimación polinomial seguida de una iteración de Goldschmidt [18] .

La raíz de un número negativo o complejo

Si , entonces su raíz principal es igual a $S<0$

{\sqrt {S}}={\sqrt {\vert S\vert }}\,\,i\,.

Si , donde a y b son números reales y , entonces su raíz principal es igual a ${\ estilo de visualización S = a + bi}$ $b\neq 0$

{\sqrt {S}}={\sqrt {\frac {\vert S\vert +a}{2}}}\,+\,\operatorname {sgn}(b){\sqrt {\frac {\vert S\vert -a}{2))}\,\,i\,.

Esto se puede verificar elevando al cuadrado [19] [20] . Aquí

{\displaystyle \vert S\vert ={\sqrt {a^{2}+b^{2))))

es el módulo del número S . La raíz principal de un número complejo se define como una raíz con parte real no negativa.

Véase también

Algoritmo alpha max plus beta min
raíz cuadrada entera

Notas

↑ Además de la raíz principal, existe una raíz cuadrada negativa igual en valor absoluto a la raíz principal, pero de signo contrario, excepto en el caso del cero, cuando hay dos raíces cero idénticas.
↑ Los factores dos y seis se usan porque aproximan la media geométrica de los posibles valores inferior y superior con un número dado de dígitos: y . ${\sqrt {{\sqrt {1}}\cdot {\sqrt {10}}}}={\sqrt[{4}]{10}}\aprox. 1{,}78\,$ ${\sqrt {{\sqrt {10}}\cdot {\sqrt {100}}}}={\sqrt[{4}]{1000}}\aproximadamente 5{,}62\,$
↑ La estimación no redondeada tiene un error absoluto máximo de 2,65 en el punto 100 y un error relativo máximo de 26,5 % en los puntos y=1, 10 y 100
↑ Si el número está exactamente a la mitad de dos cuadrados, como 30,5, toma el número mayor, que en nuestro caso es 6
↑ Esta es la ecuación de la recta tangente a y=x 2 en el punto y=1.
↑ Fowler y Robson 1998 , pág. 376.
↑ Heath, 1921 , pág. 323–324.
↑ Bailey, Borwein, 2012 , pág. 646–657.
↑ Regresando al manuscrito Bakhshali . Blog Simply Curious (5 de junio de 2018). Consultado el 21 de diciembre de 2020. Archivado desde el original el 26 de octubre de 2020. (indefinido)
↑ Raíz cuadrada entera rápida por Mr. Algoritmo del ábaco de Woo (archivado)
↑ Función de raíz cuadrada entera . Consultado el 30 de diciembre de 2021. Archivado desde el original el 30 de septiembre de 2007. (indefinido)
↑ Wilkes, Wheeler, Gill, 1951 .
↑ Campbell-Kelly, 2009 .
↑ Gower, 1958 , pág. 142-143, 1958.
↑ Markstein, Peter (noviembre de 2004). División de software y raíz cuadrada usando algoritmos de Goldschmidt (PDF) . VI Jornadas de Números Reales y Computadores . Dagstuhl , Alemania. CiteSeerX 10.1.1.85.9648 . Archivado (PDF) desde el original el 28 de abril de 2022 . Consultado el 30 de diciembre de 2021 . Parámetro obsoleto utilizado |deadlink=( ayuda )
↑ Se suma 127 al exponente del número, lo que permite interpretar el exponente como un número sin signo.
↑ Raíz cuadrada inversa rápida . Archivado el 6 de febrero de 2009 en Wayback Machine por Chris Lomont.
↑ "Cálculo de Alta Velocidad y Doble Precisión de Recíproco, División, Raíz Cuadrada y Raíz Cuadrada Inversa" por José-Alejandro Piñeiro y Javier Díaz Bruguera 2002 (resumen)
↑ Abramowitz, Stegun, 1964 , pág. 17
↑ Cooke, 2008 , pág. 59.

Literatura

David Fowler, Eleanor Robson. Aproximaciones a la raíz cuadrada en las matemáticas de la antigua Babilonia: YBC 7289 en contexto // Historia Mathematica. - 1998. - T. 25 , núm. 4 . -doi : 10.1006/ hmat.1998.2209 .
Tomás Little Heath . Una historia de las matemáticas griegas. - Oxford: Clarendon Press, 1921. - V. 2. - S. 323-324.
David Bailey, Jonathan Borwein. Raíces cuadradas indias antiguas: un ejercicio de paleomatemática forense // American Mathematical Monthly. - 2012. - T. 119 , núm. 8 _
Miltonn Abramowitz, Irene A. Stegun. Sección 3.7.26 // Manual de funciones matemáticas con fórmulas, gráficos y tablas matemáticas . - Publicaciones Courier Dover, 1964. - Pág. 17. - ISBN 978-0-486-61272-0 .
JC Gower. Una nota sobre un método iterativo para la extracción de raíces // The Computer Journal. - 1958. - T. 1 1 , núm. 3 .
M. Campbell-Kelly. Origen de la Computación // Scientific American. - 2009. - Septiembre.
Roger Cooke. Álgebra clásica: su naturaleza, orígenes y usos . - John Wiley and Sons, 2008. - ISBN 978-0-470-25952-8 .
MV Wilkes, DJ Wheeler, S. Gill. La preparación de programas para una computadora digital electrónica. — Addison-Wesley, 1951.

Métodos para calcular raíces cuadradas

Puntuación inicial

Puntuación decimal

Evaluación binaria

método babilónico

Ejemplo

Convergencia

Método Bakhshali

Ejemplo

Número por número

Principio básico

Sistema numérico decimal

Sistema numérico binario

Identidad exponencial

Un método iterativo con dos variables

Métodos iterativos para calcular el recíproco de la raíz cuadrada de un número

Algoritmo de Goldschmidt

Serie de Taylor

Expansión en fracciones continuas

Método de secuencia de Luke

Aproximaciones dependientes de la representación de punto flotante

El recíproco de la raíz cuadrada

La raíz de un número negativo o complejo

Véase también

Notas

Literatura

Referencias Weisstein, Eric W. Algoritmos de raíz cuadrada (inglés) en el sitio Wolfram MathWorld .