Métodos para calcular raíces cuadradas

Algoritmos para calcular raíces cuadradas.

Los métodos para calcular raíces cuadradas son algoritmos para aproximar la raíz cuadrada no negativa de un número real positivo . Dado que todas las raíces cuadradas de números naturales , excepto las de cuadrados perfectos , son irracionales , ^[1] las raíces cuadradas normalmente sólo pueden calcularse con cierta precisión finita: estos métodos suelen construir una serie de aproximaciones cada vez más precisas . ${\displaystyle {\sqrt {S}}}$ ${\displaystyle S}$

La mayoría de los métodos de cálculo de raíz cuadrada son iterativos: después de elegir una estimación inicial adecuada de , se realiza un refinamiento iterativo hasta que se cumple algún criterio de terminación. Un esquema de refinamiento es el método de Heron, un caso especial del método de Newton . Si la división es mucho más costosa que la multiplicación, puede ser preferible calcular la raíz cuadrada inversa. ${\displaystyle {\sqrt {S}}}$

Hay otros métodos disponibles para calcular la raíz cuadrada dígito a dígito o utilizando series de Taylor. Las aproximaciones racionales de raíces cuadradas se pueden calcular utilizando expansiones de fracciones continuas.

El método empleado depende de la precisión necesaria y de las herramientas y la potencia computacional disponibles. Los métodos pueden clasificarse a grandes rasgos como aquellos adecuados para el cálculo mental, aquellos que normalmente requieren al menos papel y lápiz, y aquellos que se implementan como programas para ejecutarse en una computadora electrónica digital u otro dispositivo informático. Los algoritmos pueden tener en cuenta la convergencia (cuántas iteraciones se requieren para lograr una precisión específica), la complejidad computacional de operaciones individuales (es decir, división) o iteraciones y la propagación de errores (la precisión del resultado final).

Algunos métodos, como la división sintética con lápiz y papel y la expansión de series, no requieren un valor inicial. En algunas aplicaciones, se requiere una raíz cuadrada entera , que es la raíz cuadrada redondeada o truncada al entero más cercano (en este caso se puede emplear un procedimiento modificado).

Historia

Los procedimientos para encontrar raíces cuadradas (particularmente la raíz cuadrada de 2 ) se conocen al menos desde el período de la antigua Babilonia en el siglo XVII a.C. Los matemáticos babilónicos calcularon la raíz cuadrada de 2 a tres "dígitos" sexagesimales después del 1, pero no se sabe exactamente cómo. Sabían cómo aproximar una hipotenusa usando

$${\displaystyle {\sqrt {a^{2}+b^{2}}}\approx a+{\frac {1}{2}}b^{2}a^{-1}}$$

^[2] ${\displaystyle {\frac {41}{60}}+{\frac {15}{3600}}}$ ${\displaystyle {\frac {40}{60}}}$ ${\displaystyle {\frac {10}{60}}}$ ${\displaystyle {\sqrt {2}}.}$

El método de Heron del Egipto del siglo I fue el primer algoritmo determinable para calcular la raíz cuadrada. ^[3]

Los métodos analíticos modernos comenzaron a desarrollarse después de la introducción del sistema de numeración arábiga en Europa occidental a principios del Renacimiento. ^{[ cita necesaria ]}

Hoy en día, casi todos los dispositivos informáticos tienen una función de raíz cuadrada rápida y precisa, ya sea como una construcción de lenguaje de programación, una función intrínseca del compilador o de biblioteca, o como un operador de hardware, basado en uno de los procedimientos descritos.

Estimación inicial

Muchos algoritmos iterativos de raíz cuadrada requieren un valor inicial . La semilla debe ser un número positivo distinto de cero; debe estar entre 1 y , el número cuya raíz cuadrada se desea, porque la raíz cuadrada debe estar en ese rango. Si la semilla está lejos de la raíz, el algoritmo requerirá más iteraciones. Si uno se inicializa con (o ), entonces se desperdiciarán aproximadamente iteraciones solo para obtener el orden de magnitud de la raíz. Por lo tanto, es útil contar con una estimación aproximada, que puede tener una precisión limitada pero que es fácil de calcular. En general, cuanto mejor sea la estimación inicial, más rápida será la convergencia. Para el método de Newton (también llamado método babilónico o de Heron), una semilla algo más grande que la raíz convergerá ligeramente más rápido que una semilla algo más pequeña que la raíz. ${\displaystyle S}$ ${\displaystyle x_{0}=1}$ ${\displaystyle S}$ ${\displaystyle {\tfrac {1}{2}}\vert \log _{2}S\vert }$

En general, una estimación se realiza de acuerdo con un intervalo arbitrario que se sabe que contiene la raíz (como ). La estimación es un valor específico de una aproximación funcional a lo largo del intervalo. Obtener una mejor estimación implica obtener límites más estrictos en el intervalo o encontrar una mejor aproximación funcional a . Esto último suele significar el uso de un polinomio de orden superior en la aproximación, aunque no todas las aproximaciones son polinomiales. Los métodos comunes de estimación incluyen escalar, lineal, hiperbólico y logarítmico. Generalmente se utiliza una base decimal para realizar estimaciones mentales o con lápiz y papel. Una base binaria es más adecuada para estimaciones por computadora. Al estimar, el exponente y la mantisa generalmente se tratan por separado, ya que el número se expresaría en notación científica. ${\displaystyle [x_{0},S/x_{0}]}$ ${\displaystyle f(x)={\sqrt {x}}}$ ${\displaystyle f(x)}$

Estimaciones decimales

Normalmente, el número se expresa en notación científica como donde y n es un número entero, y el rango de posibles raíces cuadradas es donde . ${\displaystyle S}$ ${\displaystyle a\times 10^{2n}}$ ${\displaystyle 1\leq a<100}$ ${\displaystyle {\sqrt {a}}\times 10^{n}}$ ${\displaystyle 1\leq {\sqrt {a}}<10}$

Estimaciones escalares

Los métodos escalares dividen el rango en intervalos y la estimación en cada intervalo se representa mediante un único número escalar. Si el rango se considera como un intervalo único, los tiempos de la media aritmética (5.5) o la media geométrica ( ) son estimaciones plausibles. El error absoluto y relativo para estos será diferente. En general, un solo escalar será muy inexacto. Las mejores estimaciones dividen el rango en dos o más intervalos, pero las estimaciones escalares tienen una precisión inherentemente baja. ${\displaystyle {\sqrt {10}}\approx 3.16}$ ${\displaystyle 10^{n}}$

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

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

Esta estimación tiene un error absoluto máximo de a = 100 y un error relativo máximo de 100% en a = 1. ${\displaystyle 4\cdot 10^{n}}$

Por ejemplo, para factorizado como , la estimación es . , un error absoluto de 246 y un error relativo de casi el 70%. ${\displaystyle S=125348}$ ${\displaystyle 12.5348\times 10^{4}}$ ${\displaystyle {\sqrt {S}}\approx 6\cdot 10^{2}=600}$ ${\displaystyle {\sqrt {125348}}=354.0}$

Estimaciones lineales

Una mejor estimación, y el método estándar utilizado, es una aproximación lineal a la función sobre un arco pequeño. Si, como se indicó anteriormente, las potencias de la base se factorizan a partir del número y el intervalo se reduce a , se puede usar como aproximación una línea secante que abarque el arco o una línea tangente en algún lugar a lo largo del arco, pero una línea de regresión de mínimos cuadrados cruzar el arco será más preciso. ${\displaystyle y=x^{2}}$ ${\displaystyle S}$ ${\displaystyle [1,100]}$

Una línea de regresión de mínimos cuadrados minimiza la diferencia promedio entre la estimación y el valor de la función. Su ecuación es . Reordenamiento, . Redondeando los coeficientes para facilitar el cálculo, ${\displaystyle y=8.7x-10}$ ${\displaystyle x=0.115y+1.15}$

$${\displaystyle {\sqrt {S}}\approx (a/10+1.2)\cdot 10^{n}}$$

Esa es la mejor estimación en promedio que se puede lograr con una aproximación lineal de una sola pieza de la función y=x ² en el intervalo . Tiene un error absoluto máximo de 1,2 en a=100 y un error relativo máximo del 30% en S=1 y 10. ^{[Nota 2]} ${\displaystyle [1,100]}$

Para dividir por 10, resta uno del exponente de o, en sentido figurado, mueve la coma decimal un dígito hacia la izquierda. Para esta formulación, cualquier constante aditiva 1 más un pequeño incremento generará una estimación satisfactoria, por lo que recordar el número exacto no es una carga. La aproximación (redondeada o no) utilizando una sola línea que abarca el rango tiene menos de un dígito significativo de precisión; el error relativo es mayor que 1/2 ² , por lo que se proporcionan menos de 2 bits de información. La precisión es muy limitada porque el rango es de dos órdenes de magnitud, bastante grande para este tipo de estimación. ${\displaystyle a}$ ${\displaystyle [1,100]}$

Se puede obtener una estimación mucho mejor mediante una aproximación lineal por partes: múltiples segmentos de línea, cada uno de los cuales se aproxima a algún subarco del original. Cuantos más segmentos de línea se utilicen, mejor será la aproximación. La forma más común es utilizar líneas tangentes; las decisiones críticas son cómo dividir el arco y dónde colocar los puntos tangentes. Una forma eficaz de dividir el arco de y  = 1 a y  = 100 es geométricamente: para dos intervalos, los límites de los intervalos son la raíz cuadrada de los límites del intervalo original, 1×100, es decir, [1, ² √ 100 ] y [ ² √ 100 ,100]. Para tres intervalos, los límites son las raíces cúbicas de 100: [1, ³ √ 100 ], [ ³ √ 100 ,( ³ √ 100 ) ² ] y [( ³ √ 100 ) ² ,100], etc. intervalos, ² √ 100 = 10, un número muy conveniente. Las rectas tangentes son fáciles de derivar y están ubicadas en x = √ 1* √ 10 y x = √ 10* √ 10 . Sus ecuaciones son: y . Invirtiendo, las raíces cuadradas son: y . Así para : ${\displaystyle y=3.56x-3.16}$ ${\displaystyle y=11.2x-31.6}$ ${\displaystyle x=0.28y+0.89}$ ${\displaystyle x=.089y+2.8}$ ${\displaystyle S=a\cdot 10^{2n}}$

$${\displaystyle {\sqrt {S}}\approx {\begin{cases}(0.28a+0.89)\cdot 10^{n}&{\text{if }}a<10,\\(.089a+2.8)\cdot 10^{n}&{\text{if }}a\geq 10.\end{cases}}}$$

Los errores absolutos máximos ocurren en los puntos altos de los intervalos, en a = 10 y 100, y son 0,54 y 1,7 respectivamente. Los errores relativos máximos se encuentran en los puntos finales de los intervalos, en a =1, 10 y 100, y son del 17% en ambos casos. 17% o 0,17 es mayor que 1/10, por lo que el método produce menos de un dígito decimal de precisión.

Estimaciones hiperbólicas

En algunos casos, las estimaciones hiperbólicas pueden ser eficaces, porque una hipérbola también es una curva convexa y puede estar a lo largo de un arco de Y = x ² mejor que una línea. Las estimaciones hiperbólicas son más complejas desde el punto de vista computacional porque necesariamente requieren una división flotante. Una aproximación hiperbólica casi óptima a x ² en el intervalo es y=190/(10-x)-20. Transponiendo, la raíz cuadrada es x = -190/(y+20)+10. Así para : ${\displaystyle [1,100]}$ ${\displaystyle S=a\cdot 10^{2n}}$

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

La división flotante debe tener una precisión de solo un dígito decimal, porque la estimación general es solo esa precisión y se puede hacer mentalmente. Una estimación hiperbólica es mejor en promedio que una estimación escalar o lineal. Tiene un error absoluto máximo de 1,58 en 100 y un error relativo máximo de 16,0% en 10. Para el peor caso en a=10, la estimación es 3,67. Si se comienza con 10 y se aplican las iteraciones de Newton-Raphson de inmediato, se necesitarán dos iteraciones, lo que arrojará 3,66, antes de que se supere 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 necesitarían 5 iteraciones de Newton-Raphson comenzando en 75 para obtener un resultado más preciso.

Estimaciones aritméticas

Un método análogo a la aproximación lineal por partes pero que utiliza sólo ecuaciones aritméticas en lugar de algebraicas, utiliza las tablas de multiplicar a la inversa: la raíz cuadrada de un número entre 1 y 100 está entre 1 y 10, por lo que si sabemos que 25 es un cuadrado perfecto (5 × 5), y 36 es un cuadrado perfecto (6 × 6), entonces la raíz cuadrada de un número mayor o igual a 25 pero menor que 36, comienza con un 5. Lo mismo ocurre con los números entre otros cuadrados. Este método producirá un primer dígito correcto, pero no es exacto a un dígito: el primer dígito de la raíz cuadrada de 35, por ejemplo, es 5, pero la raíz cuadrada de 35 es casi 6.

Una mejor manera es dividir el rango en intervalos a mitad de camino entre los cuadrados. Entonces, cualquier número entre 25 y la mitad de 36, que es 30,5, estima 5; cualquier número mayor que 30,5 hasta 36, ​​estima 6. ^{[Nota 3]} El procedimiento sólo requiere un poco de aritmética para encontrar un número límite en medio de dos productos de la tabla de multiplicar. Aquí hay una tabla de referencia de esos límites:

La operación final es multiplicar la estimación k por la potencia de diez dividido por 2, por lo que , ${\displaystyle S=a\cdot 10^{2n}}$

$${\displaystyle {\sqrt {S}}\approx k\cdot 10^{n}}$$

El método produce implícitamente un dígito significativo de precisión, ya que redondea al mejor primer dígito.

El método se puede ampliar a 3 dígitos significativos en la mayoría de los casos, interpolando entre los cuadrados más cercanos que delimitan el operando. Si , entonces es aproximadamente k más una fracción, la diferencia entre a y k ² dividida por la diferencia entre los dos cuadrados: ${\displaystyle k^{2}\leq a<(k+1)^{2}}$ ${\displaystyle {\sqrt {a}}}$

$${\displaystyle {\sqrt {a}}\approx k+R}$$

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

La operación final, como arriba, es multiplicar el resultado por la potencia de diez dividido por 2;

$${\displaystyle {\sqrt {S}}={\sqrt {a}}\cdot 10^{n}\approx (k+R)\cdot 10^{n}}$$

k es un dígito decimal y R es una fracción que debe convertirse a decimal. Por lo general, tiene un solo dígito en el numerador y uno o dos dígitos en el denominador, por lo que la conversión a decimal se puede realizar mentalmente.

Ejemplo: encuentre la raíz cuadrada de 75. 75 = 75 × 10 ^{2  · 0} , entonces a es 75 y n es 0. De las tablas de multiplicar, la raíz cuadrada de la mantisa debe ser 8 puntos porque 8 × 8 es 64, pero 9 × 9 es 81, demasiado grande, entonces k es 8; algo es la representación decimal de R . La fracción R es 75 - k ² = 11, el numerador, y 81 - k ² = 17, el denominador. 17/11 es un poco menos que 18/12, que es 2/3 o 0,67, así que suponga 0,66 (aquí está bien adivinar, el error es muy pequeño). Entonces la estimación es 8 + 0,66 = 8,66 . √ 75 con tres dígitos significativos es 8,66, por lo que la estimación es buena con 3 dígitos significativos. No todas las estimaciones que utilicen este método serán tan precisas, pero sí cercanas.

Estimaciones binarias

Cuando se trabaja en el sistema numérico binario (como lo hacen internamente las computadoras), al expresar como dónde , la raíz cuadrada se puede estimar como ${\displaystyle S}$ ${\displaystyle a\times 2^{2n}}$ ${\displaystyle 0.1_{2}\leq a<10_{2}}$ ${\displaystyle {\sqrt {S}}={\sqrt {a}}\times 2^{n}}$

$${\displaystyle {\sqrt {S}}\approx (0.485+0.485\cdot a)\cdot 2^{n}}$$

que es la línea de regresión de mínimos cuadrados con coeficientes de 3 dígitos significativos. tiene un error absoluto máximo de 0,0408 en =2 y un error relativo máximo de 3,0% en =1. Una estimación redondeada computacionalmente conveniente (porque los coeficientes son potencias de 2) es: ${\displaystyle {\sqrt {a}}}$ ${\displaystyle a}$ ${\displaystyle a}$

${\displaystyle {\sqrt {S}}\approx (0.5+0.5\cdot a)\cdot 2^{n}}$^{[Nota 4]}

que tiene un error absoluto máximo de 0,086 en 2 y un error relativo máximo de 6,1% en a = 0,5 y a = 2,0 .

Para , la aproximación binaria da . , por lo que la estimación tiene un error absoluto de 19 y un error relativo del 5,3%. El error relativo es un poco menor que 1/2 ⁴ , por lo que la estimación es buena para 4+ bits. ${\displaystyle S=125348=1\;1110\;1001\;1010\;0100_{2}=1.1110\;1001\;1010\;0100_{2}\times 2^{16}\,}$ ${\displaystyle {\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}$ ${\displaystyle {\sqrt {125348}}=354.0}$

Se puede obtener una estimación de hasta 8 bits mediante una búsqueda en la tabla de los 8 bits superiores de , recordando que el bit superior está implícito en la mayoría de las representaciones de punto flotante, y el bit inferior de los 8 debe redondearse. La tabla tiene 256 bytes de valores de raíz cuadrada de 8 bits precalculados. Por ejemplo, para el índice 11101101 ₂ que representa 1.8515625 ₁₀ , la entrada es 10101110 ₂ que representa 1.359375 ₁₀ , la raíz cuadrada de 1.8515625 con una precisión de ₁₀ a 8 bits (más de 2 dígitos decimales). ${\displaystyle a}$ ${\displaystyle a}$

método de garza

El primer algoritmo explícito para la aproximación se conoce como método de Herón , en honor al matemático griego del siglo I, Héroe de Alejandría , que describió el método en su obra Métrica del año 60 d.C. ^[3] Este método también se llama método babilónico (no debe confundirse con el método babilónico para aproximar hipotenusas), aunque no hay evidencia de que los babilonios conocieran el método. ${\displaystyle {\sqrt {S}}}$

Dado un número real positivo , sea x ₀ > 0 cualquier estimación inicial positiva. El método de Heron consiste en calcular iterativamente ${\displaystyle S}$

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

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

Esto equivale a utilizar el método de Newton para resolver . Este algoritmo es cuadráticamente convergente : el número de dígitos correctos de aproximadamente se duplica con cada iteración. ${\displaystyle x^{2}-S=0}$ ${\displaystyle x_{n}}$

Derivación

La idea básica es que si x es una sobreestimación de la raíz cuadrada de un número real no negativo S, entoncesS/Xserá una subestimación, y viceversa, por lo que se puede esperar razonablemente que el promedio de estos dos números proporcione una mejor aproximación (aunque la prueba formal de esa afirmación depende de la desigualdad de las medias aritméticas y geométricas que muestra que este promedio es siempre una sobreestimación). de la raíz cuadrada, como se señala en el artículo sobre raíces cuadradas , asegurando así la convergencia).

Más precisamente, si x es nuestra estimación inicial y ε es el error en nuestra estimación tal que S = ( x + ε ) ² , entonces podemos expandir el binomio ${\displaystyle {\sqrt {S}}}$

$${\displaystyle (x+\varepsilon )^{2}=x^{2}+2x\varepsilon +\varepsilon ^{2}}$$

${\displaystyle \varepsilon ={\frac {S-x^{2}}{2x+\varepsilon }}\approx {\frac {S-x^{2}}{2x}},}$desde . ${\displaystyle \varepsilon \ll x}$

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

$${\displaystyle x+\varepsilon \approx x+{\frac {S-x^{2}}{2x}}={\frac {S+x^{2}}{2x}}={\frac {{\frac {S}{x}}+x}{2}}\equiv x_{\text{revised}}}$$

Este algoritmo funciona igualmente bien en los números p -ádicos , pero no se puede utilizar para identificar raíces cuadradas reales con raíces cuadradas p -ádicas; uno puede, por ejemplo, construir una secuencia de números racionales mediante este método que converja a +3 en los reales, pero a −3 en los 2-ádicos.

Ejemplo

Para calcular √ S , donde S = 125348, con seis cifras significativas, utilice el método de estimación aproximado anterior para obtener

$${\displaystyle {\begin{aligned}{\begin{array}{rlll}x_{0}&=6\cdot 10^{2}&&=600.000\\[0.3em]x_{1}&={\frac {1}{2}}\left(x_{0}+{\frac {S}{x_{0}}}\right)&={\frac {1}{2}}\left(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+{\frac {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}}}\right)&={\frac {1}{2}}\left(354.059+{\frac {125348}{354.059}}\right)&=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{array}}\end{aligned}}}$$

Por lo tanto, √ 125348 ≈ 354,045 .

Convergencia

Gráficos semilogarítmicos que comparan la velocidad de convergencia del método de Heron para encontrar la raíz cuadrada de 100 para diferentes conjeturas iniciales. Las conjeturas negativas convergen a la raíz negativa y las positivas a la raíz positiva. Tenga en cuenta que los valores más cercanos a la raíz convergen más rápido y todas las aproximaciones son sobreestimaciones. En el archivo SVG, coloque el cursor sobre un gráfico para mostrar sus puntos.

Supongamos que x ₀ > 0 y S > 0. Entonces, para cualquier número natural n , x _n > 0. Sea el error relativo en x _n definido por

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

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

Entonces se puede demostrar que

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

Y así eso

$${\displaystyle \varepsilon _{n+2}\leq \min \left\{{\frac {\varepsilon _{n+1}^{2}}{2}},{\frac {\varepsilon _{n+1}}{2}}\right\}}$$

cuadrática

El peor caso para la convergencia

Si se utiliza la estimación aproximada anterior con el método babilónico, los casos menos precisos en orden ascendente son los siguientes:

$${\displaystyle {\begin{aligned}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{aligned}}}$$

Así, en cualquier caso,

$${\displaystyle {\begin{aligned}\varepsilon _{1}&\leq 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}.\end{aligned}}}$$

Los errores de redondeo ralentizarán la convergencia. Se recomienda mantener al menos un dígito adicional más allá de la precisión deseada del x _n que se calcula para minimizar el error de redondeo.

método bakhshali

Este método para encontrar una aproximación a una raíz cuadrada se describió en un antiguo manuscrito indio , llamado manuscrito Bakhshali . Es equivalente a dos iteraciones del método babilónico que comienzan con x ₀ . Por lo tanto, el algoritmo es cuárticamente convergente, lo que significa que el número de dígitos correctos de la aproximación aproximadamente se cuadriplica con cada iteración. ^[4] La presentación original, usando notación moderna, es la siguiente: Para calcular , sea la aproximación inicial a . Luego, itere sucesivamente como: ${\displaystyle {\sqrt {S}}}$ ${\displaystyle x_{0}^{2}}$ ${\displaystyle S}$

$${\displaystyle {\begin{aligned}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{aligned}}}$$

Esto se puede utilizar para construir una aproximación racional a la raíz cuadrada comenzando con un número entero. Si se elige un número entero cercano a y es la diferencia cuyo valor absoluto se minimiza, entonces la primera iteración se puede escribir como: ${\displaystyle x_{0}=N}$ ${\displaystyle N^{2}}$ ${\displaystyle S}$ ${\displaystyle d=S-N^{2}}$

$${\displaystyle {\sqrt {S}}\approx 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 Bakhshali se puede generalizar al cálculo de una raíz arbitraria, incluidas las raíces fraccionarias. ^[5]

Ejemplo

Usando el mismo ejemplo dado con el método babilónico, entonces, la primera iteración da ${\displaystyle S=125348.}$

$${\displaystyle {\begin{aligned}x_{0}&=600\\[1ex]a_{1}&={\frac {125348-600^{2}}{2\times 600}}&&=&-195.543\\[1ex]b_{1}&=600+(-195.543)&&=&404.456\\[1ex]x_{1}&=404.456-{\frac {(-195.543)^{2}}{2\times 404.456}}&&=&357.186\end{aligned}}}$$

Asimismo, la segunda iteración da

$${\displaystyle {\begin{aligned}a_{2}&={\frac {125348-357.186^{2}}{2\times 357.186}}&&=&-3.126\\[1ex]b_{2}&=357.186+(-3.126)&&=&354.060\\[1ex]x_{2}&=354.06-{\frac {(-3.1269)^{2}}{2\times 354.06}}&&=&354.046\end{aligned}}}$$

Cálculo dígito por dígito

Este es un método para encontrar cada dígito de la raíz cuadrada en una secuencia. Este método se basa en el teorema del binomio y básicamente en un algoritmo de resolución inverso . Es más lento que el método babilónico, pero tiene varias ventajas: ${\displaystyle (x+y)^{2}=x^{2}+2xy+y^{2}}$

• Puede ser más fácil para los cálculos manuales.
• Se sabe que cada dígito de la raíz encontrado es correcto, es decir, no es necesario cambiarlo más adelante.
• Si la raíz cuadrada tiene una expansión que termina, el algoritmo termina después de encontrar el último dígito. Por tanto, se puede utilizar para comprobar si un número entero dado es un número cuadrado .
• El algoritmo funciona para cualquier base y, naturalmente, la forma en que procede depende de la base elegida.

Las desventajas son:

• Se vuelve inmanejable para las raíces superiores.
• No tolera conjeturas o subcálculos inexactos; tales errores provocan que todos los dígitos siguientes del resultado sean incorrectos, a diferencia del método de Newton , que autocorrige cualquier error de aproximación.
• Si bien el cálculo dígito por dígito es bastante eficiente en papel, es demasiado costoso para las implementaciones de software. Cada iteración involucra números más grandes, lo que requiere más memoria, pero solo avanza la respuesta un dígito correcto. Por tanto, el algoritmo tarda más tiempo por cada dígito adicional.

Los huesos de Napier incluyen una ayuda para la ejecución de este algoritmo. El algoritmo de desplazamiento de raíz n- ésima es una generalización de este método.

Principio básico

Primero, considere el caso de encontrar la raíz cuadrada de un número Z , es decir, 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. Específicamente:

$${\displaystyle Z=\left(10X+Y\right)^{2}=100X^{2}+20XY+Y^{2}}$$

Ahora , usando el algoritmo dígito por dígito, primero determinamos el valor de X. X es el dígito más grande tal que X ² es menor o igual que Z del cual eliminamos los dos dígitos más a la derecha.

En la siguiente iteración, emparejamos los dígitos, multiplicamos X por 2 y lo colocamos en el lugar de las décimas mientras intentamos calcular cuál es el valor de Y.

Dado que este es un caso simple donde la respuesta es una raíz cuadrada perfecta XY , el algoritmo se detiene aquí.

La misma idea se puede extender a cualquier cálculo arbitrario de raíz cuadrada a continuación. Supongamos que podemos encontrar la raíz cuadrada de N expresándola como una suma de n números positivos tales que

$${\displaystyle N=\left(a_{1}+a_{2}+a_{3}+\dots +a_{n}\right)^{2}.}$$

Aplicando repetidamente la identidad básica

$${\displaystyle (x+y)^{2}=x^{2}+2xy+y^{2},}$$

$${\displaystyle {\begin{aligned}&(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}+\dots +a_{n-1}^{2}+2\left(\sum _{i=1}^{n-1}a_{i}\right)a_{n}+a_{n}^{2}\\=&\,a_{1}^{2}+[2a_{1}+a_{2}]a_{2}+[2(a_{1}+a_{2})+a_{3}]a_{3}+\dots +\left[2\left(\sum _{i=1}^{n-1}a_{i}\right)+a_{n}\right]a_{n}.\end{aligned}}}$$

Esta expresión nos permite encontrar la raíz cuadrada adivinando secuencialmente los valores de s. Supongamos que los números ya han sido adivinados, entonces el m -ésimo término del lado derecho de la suma anterior viene dado por dónde está la raíz cuadrada aproximada encontrada hasta ahora. Ahora cada nueva suposición debería satisfacer la recursividad. ${\displaystyle a_{i}}$ ${\displaystyle a_{1},\ldots ,a_{m-1}}$ ${\displaystyle Y_{m}=\left[2P_{m-1}+a_{m}\right]a_{m},}$ ${\textstyle P_{m-1}=\sum _{i=1}^{m-1}a_{i}}$ ${\displaystyle a_{m}}$

$${\displaystyle X_{m}=X_{m-1}-Y_{m},}$$

${\displaystyle X_{m}\geq 0}$ ${\displaystyle 1\leq m\leq n,}$ ${\displaystyle X_{0}=N.}$ ${\displaystyle X_{n}=0,}$ ${\displaystyle a_{i}}$ ${\displaystyle X_{n}}$

Por ejemplo, en el sistema numérico decimal tenemos

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

${\displaystyle 10^{n-i}}$ ${\displaystyle a_{i}\in \{0,1,2,\ldots ,9\}}$ ${\displaystyle P_{m-1}}$ ${\displaystyle Y_{m}}$

$${\displaystyle P_{m-1}=\sum _{i=1}^{m-1}a_{i}\cdot 10^{n-i}=10^{n-m+1}\sum _{i=1}^{m-1}a_{i}\cdot 10^{m-i-1},}$$

$${\displaystyle Y_{m}=\left[2P_{m-1}+a_{m}\cdot 10^{n-m}\right]a_{m}\cdot 10^{n-m}=\left[20\sum _{i=1}^{m-1}a_{i}\cdot 10^{m-i-1}+a_{m}\right]a_{m}\cdot 10^{2(n-m)}.}$$

Aquí, dado que el valor posicional de es una potencia par de 10, solo necesitamos trabajar con el par de dígitos más significativos del término restante en cualquier etapa m-ésima. La siguiente sección codifica este procedimiento. ${\displaystyle Y_{m}}$ ${\displaystyle X_{m-1}}$

Es obvio que se puede utilizar un método similar para calcular la raíz cuadrada en sistemas numéricos distintos del sistema numérico decimal. Por ejemplo, encontrar la raíz cuadrada dígito por dígito en el sistema numérico binario es bastante eficiente ya que el valor de se busca a partir de un conjunto más pequeño de dígitos binarios {0,1}. Esto hace que el cálculo sea más rápido ya que en cada etapa el valor de es for o for . El hecho de que solo tengamos dos opciones posibles para también facilita el proceso de decidir el valor de en la m -ésima etapa del cálculo. Esto se debe a que solo necesitamos verificar si se cumple esta condición, entonces tomamos ; si no, entonces Además, el hecho de que la multiplicación por 2 se realice mediante desplazamientos de bits a la izquierda ayuda en el cálculo. ${\displaystyle a_{i}}$ ${\displaystyle Y_{m}}$ ${\displaystyle Y_{m}=0}$ ${\displaystyle a_{m}=0}$ ${\displaystyle Y_{m}=2P_{m-1}+1}$ ${\displaystyle a_{m}=1}$ ${\displaystyle a_{m}}$ ${\displaystyle a_{m}}$ ${\displaystyle Y_{m}\leq X_{m-1}}$ ${\displaystyle a_{m}=1.}$ ${\displaystyle a_{m}=1}$ ${\displaystyle a_{m}=0.}$

decimales (base 10)

Escribe el número original en forma decimal. Los números se escriben de manera similar al algoritmo de división larga y, como en la división larga, la raíz se escribirá en la línea de arriba. Ahora separe los dígitos en pares, comenzando desde el punto decimal y yendo hacia la izquierda y hacia la derecha. El punto decimal de la raíz estará encima del punto decimal del cuadrado. Un dígito de la raíz aparecerá encima de cada par de dígitos del cuadrado.

Comenzando con el par de dígitos más a la izquierda, realice el siguiente procedimiento para cada par:

1. Comenzando por la izquierda, baje el par de dígitos más significativo (el más a la izquierda) que aún no se haya usado (si se han usado todos los dígitos, escriba "00") y escríbalos a la derecha del resto del paso anterior (en el primer paso, no quedará ningún resto). En otras palabras, multiplica el resto por 100 y suma los dos dígitos. Este será el valor actual c .
2. Encuentre p , y y x , de la siguiente manera:
   • Sea p la parte de la raíz encontrada hasta ahora , ignorando cualquier punto decimal. (Para el primer paso, p = 0.)
   • Determine el dígito mayor x tal que . Usaremos una nueva variable y = x (20 p + x ). ${\displaystyle x(20p+x)\leq c}$
     • Nota: 20 p + x es simplemente el doble de p , con el dígito x añadido a la derecha.
     • Nota: x se puede encontrar adivinando qué es c /(20· p ) y haciendo un cálculo de prueba de y , luego ajustando x hacia arriba o hacia abajo según sea necesario.
   • Coloque el dígito como el siguiente dígito de la raíz, es decir, encima de los dos dígitos del cuadrado que acaba de bajar. Por lo tanto, la siguiente p será la antigua p multiplicada por 10 más x . ${\displaystyle x}$
3. Resta y de c para formar un nuevo resto.
4. Si el resto es cero y no hay más dígitos que bajar, entonces el algoritmo ha terminado. De lo contrario, vuelva al paso 1 para realizar otra iteración.

Ejemplos

Encuentra la raíz cuadrada de 152,2756.

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

Sistema de numeración binario (base 2)

Esta sección utiliza el formalismo de la sección anterior de cálculo dígito por dígito, con la ligera variación que permitimos , con cada o . Repetimos todo , desde abajo hasta , y construimos una solución aproximada , la suma de todo para la cual hemos determinado el valor. Para determinar si es igual a o , dejamos . Si (es decir, el cuadrado de nuestra solución aproximada incluida no excede el cuadrado objetivo), entonces , en caso contrario y . Para evitar elevar al cuadrado en cada paso, almacenamos la diferencia y la actualizamos incrementalmente configurándola con . Inicialmente, nos fijamos en el más grande con . ${\displaystyle N^{2}=(a_{n}+\dotsb +a_{0})^{2}}$ ${\displaystyle a_{m}=2^{m}}$ ${\displaystyle a_{m}=0}$
${\displaystyle 2^{m}}$ ${\displaystyle 2^{n}}$ ${\displaystyle 2^{0}}$ ${\displaystyle P_{m}=a_{n}+a_{n-1}+\ldots +a_{m}}$ ${\displaystyle a_{i}}$
${\displaystyle a_{m}}$ ${\displaystyle 2^{m}}$ ${\displaystyle 0}$ ${\displaystyle P_{m}=P_{m+1}+2^{m}}$ ${\displaystyle P_{m}^{2}\leq N^{2}}$ ${\displaystyle 2^{m}}$ ${\displaystyle a_{m}=2^{m}}$ ${\displaystyle a_{m}=0}$ ${\displaystyle P_{m}=P_{m+1}}$
${\displaystyle P_{m}}$ ${\displaystyle X_{m}=N^{2}-P_{m}^{2}}$ ${\displaystyle X_{m}=X_{m+1}-Y_{m}}$ ${\displaystyle Y_{m}=P_{m}^{2}-P_{m+1}^{2}=2P_{m+1}a_{m}+a_{m}^{2}}$
${\displaystyle a_{n}=P_{n}=2^{n}}$ ${\displaystyle n}$ ${\displaystyle (2^{n})^{2}=4^{n}\leq N^{2}}$

Como optimización adicional, almacenamos y , los dos términos de en caso de que sea distinto de cero, en variables separadas ,: ${\displaystyle P_{m+1}2^{m+1}}$ ${\displaystyle (2^{m})^{2}}$ ${\displaystyle Y_{m}}$ ${\displaystyle a_{m}}$ ${\displaystyle c_{m}}$ ${\displaystyle d_{m}}$

$${\displaystyle c_{m}=P_{m+1}2^{m+1}}$$

$${\displaystyle d_{m}=(2^{m})^{2}}$$

$${\displaystyle Y_{m}={\begin{cases}c_{m}+d_{m}&{\text{if }}a_{m}=2^{m}\\0&{\text{if }}a_{m}=0\end{cases}}}$$

${\displaystyle c_{m}}$y se puede actualizar eficientemente en cada paso: ${\displaystyle d_{m}}$

$${\displaystyle c_{m-1}=P_{m}2^{m}=(P_{m+1}+a_{m})2^{m}=P_{m+1}2^{m}+a_{m}2^{m}={\begin{cases}c_{m}/2+d_{m}&{\text{if }}a_{m}=2^{m}\\c_{m}/2&{\text{if }}a_{m}=0\end{cases}}}$$

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

Tenga en cuenta que:

$${\displaystyle c_{-1}=P_{0}2^{0}=P_{0}=N,}$$

Una implementación de este algoritmo en C: ^[6]

int32_t isqrt ( int32_t n ) {    afirmar (( "la entrada sqrt debe ser no negativa" , n > 0 ));    // X_(n+1) int32_tx = n ; _    // c_n int32_tc = 0 ; _    // d_n que comienza en la potencia más alta de cuatro <= n int32_t d = 1 << 30 ; // El segundo bit superior está establecido.       // Igual que ((sin firmar) INT32_MAX + 1) / 2. mientras ( re > norte ) {     re >>= 2 ;   } // para dₙ … d₀ mientras ( d ! = 0 ) {     if ( x >= c + d ) { // si X_(m+1) ≥ Y_m entonces a_m = 2^m        x -= c + d ; // X_m = X_(m+1) - Y_m      c = ( c >> 1 ) + re ; // c_(m-1) = c_m/2 + d_m (a_m es 2^m)        } demás {  c >>= 1 ; // c_(m-1) = c_m/2 (aₘ es 0)    } re >>= 2 ; // d_(m-1) = d_m/4    } devolver c ; //c_(-1)  }

Se pueden implementar algoritmos más rápidos, en binario y decimal o cualquier otra base, mediante el uso de tablas de búsqueda, lo que de hecho intercambia más espacio de almacenamiento por un tiempo de ejecución reducido . ^[7]

Identidad exponencial

Las calculadoras de bolsillo generalmente implementan buenas rutinas para calcular la función exponencial y el logaritmo natural , y luego calculan la raíz cuadrada de S usando la identidad encontrada usando las propiedades de los logaritmos ( ) y exponenciales ( ): ^{[ cita necesaria ]} ${\displaystyle \ln x^{n}=n\ln x}$ ${\displaystyle e^{\ln x}=x}$

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

enésimatablas de logaritmosreglas de cálculo

Un método iterativo de dos variables.

Este método es aplicable para encontrar la raíz cuadrada de y converge mejor para . Sin embargo, esto no es una limitación real para un cálculo basado en computadora, ya que en las representaciones de punto flotante y punto fijo de base 2, es trivial multiplicar por una potencia entera de 4 y, por lo tanto , por la correspondiente potencia de 2, por cambiando el exponente o desplazando, respectivamente. Por lo tanto, se puede mover al rango . Además, el siguiente método no emplea divisiones generales, sino sólo sumas, restas, multiplicaciones y divisiones por potencias de dos, que también son triviales de implementar. Una desventaja del método es que se acumulan errores numéricos, a diferencia de los métodos iterativos de una sola variable como el babilónico. ${\displaystyle 0<S<3\,\!}$ ${\displaystyle S\approx 1}$ ${\displaystyle S\,\!}$ ${\displaystyle {\sqrt {S}}}$ ${\displaystyle S\,\!}$ ${\textstyle {\tfrac {1}{2}}\leq S<2}$

El paso de inicialización de este método es

$${\displaystyle {\begin{aligned}a_{0}&=S\\c_{0}&=S-1\end{aligned}}}$$

$${\displaystyle {\begin{aligned}a_{n+1}&=a_{n}-a_{n}c_{n}/2\\c_{n+1}=c_{n}^{2}(c_{n}-3)/4\end{aligned}}}$$

${\displaystyle a_{n}\to {\sqrt {S}}}$ ${\displaystyle c_{n}\to 0}$

La convergencia de , y por tanto también de , es cuadrática. ${\displaystyle c_{n}\,\!}$ ${\displaystyle a_{n}\,\!}$

La prueba del método es bastante sencilla. Primero, reescribe la definición iterativa de como ${\displaystyle c_{n}}$

$${\displaystyle 1+c_{n+1}=(1+c_{n})(1-{\tfrac {1}{2}}c_{n})^{2}.}$$

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

${\displaystyle a_{n}\,\!}$ ${\displaystyle {\sqrt {S}}}$ ${\displaystyle c_{n}\,\!}$ ${\displaystyle -1<c_{0}<2\,\!}$

Este método fue desarrollado alrededor de 1950 por MV Wilkes , DJ Wheeler y S. Gill ^[8] para su uso en EDSAC , una de las primeras computadoras electrónicas. ^[9] El método se generalizó posteriormente, permitiendo el cálculo de raíces no cuadradas. ^[10]

Métodos iterativos para raíces cuadradas recíprocas.

Los siguientes son métodos iterativos para encontrar la raíz cuadrada recíproca de S , que es . Una vez encontrado, encuentre por simple multiplicación: . Estas iteraciones implican sólo multiplicación y no división. Por tanto, son más rápidos que el método babilónico. Sin embargo, no son estables. Si el valor inicial no está cerca de la raíz cuadrada recíproca, las iteraciones se alejarán de él en lugar de converger hacia él. Por lo tanto, puede resultar ventajoso realizar una iteración del método babilónico con una estimación aproximada antes de comenzar a aplicar estos métodos. ${\displaystyle 1/{\sqrt {S}}}$ ${\displaystyle {\sqrt {S}}}$ ${\displaystyle {\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 usando tres multiplicaciones por paso: ${\displaystyle (1/x^{2})-S=0}$
  $${\displaystyle 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 mediante el método de Halley , que es el método del Amo de Casa de orden dos. Esto converge cúbicamente , pero implica cinco multiplicaciones por iteración: ^{[ cita necesaria ]}
  $${\displaystyle y_{n}=S\cdot x_{n}^{2},}$$
  y
  $${\displaystyle 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}\right)\right).}$$
• Si se hace aritmética de punto fijo , la multiplicación por 3 y la división por 8 se pueden implementar mediante desplazamientos y sumas. Si se utiliza punto 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: ${\textstyle {\sqrt {3/8}}S}$
  $${\displaystyle y_{n}={\sqrt {\frac {3}{8}}}S\cdot x_{n}^{2},}$$
  y
  $${\displaystyle x_{n+1}=x_{n}\cdot \left({\frac {15}{8}}-y_{n}\cdot \left({\sqrt {\frac {25}{6}}}-y_{n}\right)\right).}$$

algoritmo de Goldschmidt

Algunas computadoras utilizan el algoritmo de Goldschmidt para calcular y simultáneamente . El algoritmo de Goldschmidt encuentra más rápido que la iteración de Newton-Raphson en una computadora con una instrucción de multiplicar-suma fusionada y una unidad de punto flotante canalizada o dos unidades de punto flotante independientes. ^[11] ${\displaystyle {\sqrt {S}}}$ ${\displaystyle 1/{\sqrt {S}}}$ ${\displaystyle {\sqrt {S}}}$

Comienza la primera forma de escribir el algoritmo de Goldschmidt

${\displaystyle b_{0}=S}$

${\displaystyle Y_{0}\approx 1/{\sqrt {S}}}$(normalmente utilizando una búsqueda de tabla)

${\displaystyle y_{0}=Y_{0}}$

${\displaystyle x_{0}=Sy_{0}}$

e itera

$${\displaystyle {\begin{aligned}b_{n+1}&=b_{n}Y_{n}^{2}\\Y_{n+1}&={\tfrac {1}{2}}(3-b_{n+1})\\x_{n+1}&=x_{n}Y_{n+1}\\y_{n+1}&=y_{n}Y_{n+1}\end{aligned}}}$$

${\displaystyle b_{i}}$

$${\displaystyle \lim _{n\to \infty }x_{n}={\sqrt {S}},}$$

$${\displaystyle \lim _{n\to \infty }y_{n}=1/{\sqrt {S}}.}$$

${\displaystyle x_{n}}$ ${\displaystyle y_{n}}$ ${\displaystyle x_{n}=Sy_{n}}$

Comienza una segunda forma, que utiliza operaciones fusionadas de suma múltiple .

${\displaystyle y_{0}\approx 1/{\sqrt {S}}}$(normalmente utilizando una búsqueda de tabla)

${\displaystyle x_{0}=Sy_{0}}$

${\displaystyle h_{0}={\tfrac {1}{2}}y_{0}}$

e itera

$${\displaystyle {\begin{aligned}r_{n}&=0.5-x_{n}h_{n}\\x_{n+1}&=x_{n}+x_{n}r_{n}\\h_{n+1}&=h_{n}+h_{n}r_{n}\end{aligned}}}$$

${\displaystyle r_{i}}$

$${\displaystyle \lim _{n\to \infty }x_{n}={\sqrt {S}},}$$

$${\displaystyle \lim _{n\to \infty }2h_{n}=1/{\sqrt {S}}.}$$

serie de taylor

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

$${\displaystyle {\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)}$$

Como método iterativo, el orden de convergencia es igual al número de términos utilizados. Con dos términos, es idéntico al método babilónico. Con tres términos, cada iteración requiere casi tantas operaciones como la aproximación de Bakhshali, pero converge más lentamente. ^{[ cita necesaria ]} Por lo tanto, esta no es una forma de cálculo particularmente eficiente. Para maximizar la tasa de convergencia, elija N para que sea lo más pequeño posible. ${\displaystyle {\frac {|d|}{N^{2}}}\,}$

Expansión de fracción continua

La representación de fracción continua de un número real se puede utilizar en lugar de su expansión decimal o binaria y esta representación tiene la propiedad de que la raíz cuadrada de cualquier número racional (que aún no sea un cuadrado perfecto) tiene una expansión periódica y repetida, similar a cómo los números racionales tienen expansiones repetidas en el sistema de notación decimal.

Los irracionales cuadráticos (números de la forma , donde a , byc son números enteros) y, en particular, las raíces cuadradas de números enteros, tienen fracciones continuas periódicas . A veces lo que se desea es encontrar no el valor numérico de una raíz cuadrada, sino su expansión fraccionaria continua y, por tanto, su aproximación racional. Sea S el número positivo para el cual debemos encontrar la raíz cuadrada. Luego, suponiendo que a es un número que sirve como estimación inicial y r es el término restante, podemos escribir Como tenemos , podemos expresar la raíz cuadrada de S como ${\displaystyle {\frac {a+{\sqrt {b}}}{c}}}$ ${\displaystyle S=a^{2}+r.}$ ${\displaystyle S-a^{2}=({\sqrt {S}}+a)({\sqrt {S}}-a)=r}$

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

Aplicando esta expresión al término denominador de la fracción, tenemos ${\displaystyle {\sqrt {S}}}$

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

Notación compacta

La expansión del numerador/denominador para fracciones continuas (ver a la izquierda) es complicada de escribir e incrustar en sistemas de formato de texto. Por eso los matemáticos han ideado varias notaciones alternativas, como ^[12]

$${\displaystyle {\sqrt {S}}=a+{\frac {r}{2a+}}\,{\frac {r}{2a+}}\,{\frac {r}{2a+}}\cdots }$$

En todo momento, una notación aún más compacta es: ^[13] ${\displaystyle r=1}$

$${\displaystyle [a;2a,2a,2a,\cdots ]}$$

Para fracciones continuas repetidas (lo que hacen todas las raíces cuadradas de cuadrados no perfectos), la repetición se representa solo una vez, con una línea superpuesta para indicar una repetición no terminante de la parte superpuesta: ^[14]

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

Para √ 2 , el valor de es 1, por lo que su representación es: ${\displaystyle a}$

$${\displaystyle [1;{\overline {2}}]}$$

Procediendo de esta manera, obtenemos una fracción continua generalizada para la raíz cuadrada como

$${\displaystyle {\sqrt {S}}=a+{\cfrac {r}{2a+{\cfrac {r}{2a+{\cfrac {r}{2a+\ddots }}}}}}}$$

El primer paso para evaluar dicha fracción ^[15] y obtener una raíz es hacer sustituciones numéricas de la raíz del número deseado y el número de denominadores seleccionados. Por ejemplo, en forma canónica, es 1 y para √ 2 , es 1, por lo que la fracción continua numérica para 3 denominadores es: ${\displaystyle r}$ ${\displaystyle a}$

$${\displaystyle {\sqrt {2}}\approx 1+{\cfrac {1}{2+{\cfrac {1}{2+{\cfrac {1}{2}}}}}}}$$

El paso 2 consiste en reducir la fracción continua de abajo hacia arriba, un denominador a la vez, para obtener una fracción racional cuyo numerador y denominador sean números enteros. La reducción procede así (tomando los tres primeros denominadores):

$${\displaystyle {\begin{aligned}1+{\cfrac {1}{2+{\cfrac {1}{2+{\cfrac {1}{2}}}}}}&=1+{\cfrac {1}{2+{\cfrac {1}{\frac {5}{2}}}}}\\&=1+{\cfrac {1}{2+{\cfrac {2}{5}}}}=1+{\cfrac {1}{\frac {12}{5}}}\\&=1+{\cfrac {5}{12}}={\frac {17}{12}}\end{aligned}}}$$

Finalmente (paso 3), divide el numerador por el denominador de la fracción racional para obtener el valor aproximado de la raíz:

$${\displaystyle 17\div 12=1.42}$$

El valor real de √ 2 es 1,41 con tres dígitos significativos. El error relativo es del 0,17%, por lo que la fracción racional tiene una precisión de casi tres dígitos. Tomar más denominadores da sucesivamente mejores aproximaciones: cuatro denominadores dan como resultado la fracción , con una precisión de casi 4 dígitos, etc. ${\displaystyle {\frac {41}{29}}=1.4137}$

Los siguientes son ejemplos de raíces cuadradas, sus fracciones simples continuas y sus primeros términos, llamados convergentes , hasta el denominador 99 inclusive:

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

Aproximaciones que dependen de la representación en coma flotante

Un número se representa en un formato de punto flotante , lo que también se denomina notación científica . Su raíz cuadrada es y se aplicarían fórmulas similares para raíces cúbicas y logaritmos. A primera vista, esto no supone ninguna mejora en cuanto a simplicidad, pero supongamos que sólo se requiere una aproximación: entonces sólo es bueno en un orden de magnitud. A continuación, reconozca que algunas potencias, p , serán impares, por lo tanto, para 3141,59 = 3,14159 × 10 ${\displaystyle m\times b^{p}}$ ${\displaystyle {\sqrt {m}}\times b^{p/2}}$ ${\displaystyle b^{p/2}}$³ en lugar de tratar con potencias fraccionarias de la base, multiplica la mantisa por la base y resta uno a la potencia para igualarla. La representación ajustada pasará a ser el equivalente a 31,4159 × 10² para que la raíz cuadrada sea √ 31.4159 × 10¹ .

Si se toma la parte entera de la mantisa ajustada, solo pueden existir los valores del 1 al 99, y eso podría usarse como índice en una tabla de 99 raíces cuadradas precalculadas para completar la estimación. Una computadora que use base dieciséis requeriría una tabla más grande, pero una que use base dos requeriría sólo tres entradas: los bits posibles de la parte entera de la mantisa ajustada son 01 (siendo la potencia aun así no hubo desplazamiento, recordando que una computadora normalizada número de coma flotante siempre tiene un dígito de orden superior distinto de cero) o si la potencia era impar, 10 u 11, siendo estos los dos primeros bits de la mantisa original. Por lo tanto, 6,25 = 110,01 en binario, normalizado a 1,1001 × 2 ² una potencia par, por lo que los bits emparejados de la mantisa son 01, mientras que 0,625 = 0,101 en binario se normaliza a 1,01 × 2 ⁻¹ una potencia impar, por lo que el ajuste es 10,1 × 2 ⁻² y los bits emparejados son 10. Observe que el bit de orden inferior de la potencia se repite en el bit de orden superior de la mantisa por pares. Una potencia par tiene su bit de orden inferior cero y la mantisa ajustada comenzará con 0, mientras que para una potencia impar ese bit es uno y la mantisa ajustada comenzará con 1. Así, cuando la potencia se reduce a la mitad, es como si El bit de orden inferior se desplaza para convertirse en el primer bit de la mantisa por pares.

Una tabla con sólo tres entradas podría ampliarse incorporando bits adicionales de la mantisa. Sin embargo, con las computadoras, en lugar de calcular una interpolación en una tabla, a menudo es mejor encontrar algún cálculo más simple que proporcione resultados equivalentes. Ahora todo depende de los detalles exactos del formato de la representación, además de qué operaciones están disponibles para acceder y manipular las partes del número. Por ejemplo, Fortran ofrece una EXPONENT(x)función para obtener el poder. El esfuerzo invertido en diseñar una buena aproximación inicial debe recuperarse evitando así las iteraciones adicionales del proceso de refinamiento que habrían sido necesarias para una mala aproximación. Dado que son pocos (una iteración requiere dividir, sumar y reducir a la mitad), la restricción es severa.

Muchas computadoras siguen la representación IEEE (o suficientemente similar), y se puede obtener una aproximación muy rápida a la raíz cuadrada al iniciar el método de Newton. La técnica que sigue se basa en el hecho de que el formato de punto flotante (en base dos) se aproxima al logaritmo de base 2. Eso es ${\displaystyle \log _{2}(m\times 2^{p})=p+\log _{2}(m)}$

Entonces, para un número de punto flotante de precisión simple de 32 bits en formato IEEE (donde, en particular, la potencia tiene un sesgo de 127 agregado para la forma representada), puede obtener el logaritmo aproximado interpretando su representación binaria como un entero de 32 bits, escalando. por y eliminando un sesgo de 127, es decir ${\displaystyle 2^{-23}}$

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

Por ejemplo, 1.0 está representado por un número hexadecimal 0x3F800000, que representaría si se tomara como un número entero. Usando la fórmula anterior obtienes , como se esperaba de . De manera similar, obtienes 0,5 de 1,5 (0x3FC00000). ${\displaystyle 1065353216=127\cdot 2^{23}}$ ${\displaystyle 1065353216\cdot 2^{-23}-127=0}$ ${\displaystyle \log _{2}(1.0)}$

Para obtener la raíz cuadrada, divide el logaritmo entre 2 y vuelve a convertir el valor. El siguiente programa demuestra la idea. Se permite intencionalmente que el bit más bajo del exponente se propague hacia la mantisa. Una forma de justificar los pasos de este programa es asumir que el sesgo del exponente es el número de bits almacenados explícitamente en la mantisa y luego demostrar que ${\displaystyle b}$ ${\displaystyle n}$

$${\displaystyle \left(\left({\tfrac {1}{2}}\left(x_{\text{int}}/2^{n}-b\right)\right)+b\right)\cdot 2^{n}={\tfrac {1}{2}}\left(x_{\text{int}}-2^{n}\right)+\left({\tfrac {1}{2}}\left(b+1\right)\right)\cdot 2^{n}.}$$

/* Se supone que float está en el formato de punto flotante de precisión simple IEEE 754 */ #include <stdint.h> float sqrt_approx ( float z ) { union { float f ; uint32_ti ; _ } valor = { z }; /* Convertir tipo, preservando el patrón de bits */ /*  * Para justificar el siguiente código, demuestre que  *  * ((((val.i / 2^m) - b) / 2) + b) * 2^m = ( (val.i - 2^m) / 2) + ((b + 1) / 2) * 2^m)  *  * donde  *  * b = sesgo del exponente  * m = número de bits de mantisa  */ val . yo -= 1 << 23 ; /* Resta 2^m. */ val . yo >>= 1 ; /* Dividir por 2. */ val . yo += 1 << 29 ; /* Sumar ((b + 1) / 2) * 2^m. */                      valor de retorno . f ; /* Interpretar nuevamente como flotante */ } 

Las tres operaciones matemáticas que forman el núcleo de la función anterior se pueden expresar en una sola línea. Se puede agregar un ajuste adicional para reducir el error relativo máximo. Entonces, las tres operaciones, sin incluir el elenco, se pueden reescribir como

vale . yo = ( 1 << 29 ) + ( valor . yo >> 1 ) - ( 1 << 22 ) + a ;              

donde a es un sesgo para ajustar los errores de aproximación. Por ejemplo, con a = 0 los resultados son precisos para potencias pares de 2 (por ejemplo, 1,0), pero para otros números los resultados serán ligeramente demasiado grandes (por ejemplo, 1,5 para 2,0 en lugar de 1,414... con un error del 6%). Con a = −0x4B0D2, el error relativo máximo se minimiza a ±3,5%.

Si se va a utilizar la aproximación para una estimación inicial del método de Newton para la ecuación , entonces se prefiere la forma recíproca que se muestra en la siguiente sección. ${\displaystyle (1/x^{2})-S=0}$

Recíproco de la raíz cuadrada

A continuación se incluye una variante de la rutina anterior, que se puede utilizar para calcular el recíproco de la raíz cuadrada; es decir, fue escrita por Greg Walsh. La aproximación de desplazamiento de enteros produjo un error relativo de menos del 4%, y el error cayó aún más al 0,15% con una iteración del método de Newton en la línea siguiente. ^[16] En gráficos por computadora es una forma muy eficiente de normalizar un vector. ${\displaystyle x^{-1/2}}$

flotar invSqrt ( flotar x ) { flotar xhalf = 0.5f * x ; unión { flotador x ; int yo ; } tu ; tu . x = x ; tu . yo = 0x5f375a86 - ( tu . yo >> 1 ); /* La siguiente línea se puede repetir cualquier número de veces para aumentar la precisión */ u . x = tu . x * ( 1.5f - xhalf * u . x * u . x ); devolverte . _ X ; }                                         

Algunos hardware VLSI implementan la raíz cuadrada inversa utilizando una estimación polinómica de segundo grado seguida de una iteración de Goldschmidt . ^[17]

Cuadrado negativo o complejo

Si S  < 0, entonces su raíz cuadrada principal es

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

Si S  =  a + bi donde a y b son reales y b  ≠ 0, entonces su raíz cuadrada principal es

$${\displaystyle {\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 la raíz al cuadrado. ^{[18] [19]} Aquí

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

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

Ver también

• Algoritmo alfa máximo más beta mínimo
• algoritmo de raíz enésima

Notas

1. Los factores dos y seis se utilizan porque aproximan las medias geométricas de los valores más bajos y más altos posibles con el número de dígitos dado: y . ${\displaystyle {\sqrt {{\sqrt {1}}\cdot {\sqrt {10}}}}={\sqrt[{4}]{10}}\approx 1.78\,}$ ${\displaystyle {\sqrt {{\sqrt {10}}\cdot {\sqrt {100}}}}={\sqrt[{4}]{1000}}\approx 5.62\,}$
2. La estimación no redondeada tiene un error absoluto máximo de 2,65 en 100 y un error relativo máximo del 26,5% en y=1, 10 y 100.
3. Si el número está exactamente a medio camino entre dos cuadrados, como 30,5, adivina el número mayor, que en este caso es 6
4. Esta es, dicho sea de paso, la ecuación de la recta tangente a y  =  x ² en y  = 1.

Referencias

1. Jackson 2011.
2. Fowler y Robson 1998.
3. Heath 1921.
4. Bailey y Borwein 2012.
5. Simplemente curioso 2018.
6. Chico y UKC 1985.
7. Steinarson, Corbit y Hendry 2003.
8. Wilkes, Wheeler y Gill 1951.
9. Campbell-Kelly 2009.
10. Gower 1958.
11. Markstein 2004.
12. ver: fracción continua generalizada#Notación
13. ver: Fracción continua#Notaciones
14. ver: fracción continua periódica
15. Sardina 2007, 2.3j en la p.10.
16. Lomont 2003.
17. Piñeiro y Díaz Bruguera 2002.
18. Abramowitz y Stegun 1964, sección 3.7.26.
19. Cooke 2008.

Bibliografía

• Abramowitz, Miltonn; Stegun, Irene A. (1964). Manual de funciones matemáticas con fórmulas, gráficas y tablas matemáticas . Publicaciones de Courier Dover. pag. 17.ISBN _ 978-0-486-61272-0.
• Bailey, David; Borwein, Jonathan (2012). "Raíces cuadradas indias antiguas: un ejercicio de paleomatemáticas forenses" (PDF) . Mensual Matemático Estadounidense . vol. 119, núm. 8. págs. 646–657 . Consultado el 14 de septiembre de 2017 .
• Campbell-Kelly, Martin (septiembre de 2009). "Origen de la Computación". Científico americano . 301 (3): 62–69. Código Bib : 2009SciAm.301c..62C. doi : 10.1038/scientificamerican0909-62. JSTOR  26001527. PMID  19708529.
• Cooke, Roger (2008). Álgebra clásica: su naturaleza, orígenes y usos . John Wiley e hijos. pag. 59.ISBN _ 978-0-470-25952-8.
• Cazador de aves, David; Robson, Eleanor (1998). "Aproximaciones de raíz cuadrada en las matemáticas de la antigua Babilonia: YBC 7289 en contexto" (PDF) . Historia Matemática . 25 (4): 376. doi : 10.1006/hmat.1998.2209 .
• Gower, John C. (1958). "Una nota sobre un método iterativo para la extracción de raíces". La revista informática . 1 (3): 142-143. doi : 10.1093/comjnl/1.3.142 .
• Jackson, Terence (1 de julio de 2011). "95.42 Raíces cuadradas irracionales de números naturales: un enfoque geométrico". La Gaceta Matemática . 95 (533): 327–330. doi :10.1017/S0025557200003193. ISSN  0025-5572. S2CID  123995083.
• Chico, Martín; Reino Unido (1985). "Raíz cuadrada entera rápida según el algoritmo del ábaco del Sr. Woo (archivado)". Archivado desde el original el 6 de marzo de 2012.
• Brezo, Thomas (1921). Una historia de las matemáticas griegas, vol. 2. Oxford: Prensa de Clarendon. págs. 323–324.
• Lomont, Chris (2003). "Raíz cuadrada inversa rápida" (PDF) .
• Markstein, Peter (noviembre de 2004). División de software y raíz cuadrada mediante algoritmos de Goldschmidt (PDF) . VI Congreso sobre Números Reales y Computadores. Dagstuhl , Alemania. CiteSeerX  10.1.1.85.9648 .
• Piñeiro, José-Alejandro; Díaz Bruguera, Javier (diciembre de 2002). "Cálculo de alta velocidad y doble precisión de recíproco, división, raíz cuadrada y raíz cuadrada inversa". Transacciones IEEE en computadoras . 51 (12): 1377–1388. doi :10.1109/TC.2002.1146704.
• Sardina, Manny (2007). "Método general para extraer raíces utilizando fracciones continuas (plegadas)". Surrey (Reino Unido).
• Simplemente curioso (5 de junio de 2018). "Apoyándonos en el manuscrito de Bakhshali". Blog simplemente curioso . Consultado el 21 de diciembre de 2020 .
• Steinarson, Arne; Corbit, Dann; Hendry, Mateo (2003). "Función de raíz cuadrada entera".
• Wilkes, MV ; Wheeler, DJ ; Gill, S. (1951). La preparación de programas para una computadora digital electrónica. Oxford: Addison-Wesley. págs. 323–324. OCLC  475783493.

enlaces externos

• Weisstein, Eric W. "Algoritmos de raíz cuadrada". MundoMatemático .
• Raíces cuadradas por resta
• Algoritmo de raíz cuadrada entera de Andrija Radović
• Algoritmos de calculadora personal I: raíces cuadradas (William E. Egbert), Hewlett-Packard Journal (mayo de 1977): página 22
• Calculadora para aprender la raíz cuadrada.