Métodos para calcular raíces cuadradas

Algorithms for calculating square roots

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 los números naturales , excepto las de los cuadrados perfectos , son irracionales , ^[1] las raíces cuadradas normalmente solo se pueden calcular con una 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 la 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 en su lugar. ${\displaystyle {\sqrt {S}}}$

Existen otros métodos para calcular la raíz cuadrada dígito por dígito o mediante series de Taylor. Se pueden calcular aproximaciones racionales de raíces cuadradas mediante desarrollos de fracciones continuas.

El método empleado depende de la precisión necesaria, de las herramientas disponibles y de la capacidad computacional. Los métodos pueden clasificarse a grandes rasgos como los adecuados para el cálculo mental, los que normalmente requieren al menos papel y lápiz, y los que se implementan como programas que se ejecutan 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 hallar raíces cuadradas (en particular 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 utilizando (dando por ejemplo para la diagonal de una puerta cuya altura es de varillas y cuyo ancho es de varillas) y es posible que hayan utilizado un enfoque similar para hallar la aproximación de ^[2] $${\displaystyle {\sqrt {a^{2}+b^{2}}}\approx a+{\frac {1}{2}}b^{2}a^{-1}}$$ ${\displaystyle {\frac {41}{60}}+{\frac {15}{3600}}}$ ${\displaystyle {\frac {40}{60}}}$ ${\displaystyle {\frac {10}{60}}}$ ${\displaystyle {\sqrt {2}}.}$

El método de Herón , del siglo I en Egipto, fue el primer algoritmo comprobable 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ábigo en Europa occidental a principios del Renacimiento. ^{[ cita requerida ]}

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 del lenguaje de programación, una función intrínseca del compilador o de la 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 de semilla . 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á muy alejada de la raíz, el algoritmo requerirá más iteraciones. Si uno inicializa con (o ), entonces aproximadamente se desperdiciarán iteraciones solo para obtener el orden de magnitud de la raíz. Por lo tanto, es útil tener una estimación aproximada, que puede tener una precisión limitada pero 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 utilizar un polinomio de orden superior en la aproximación, aunque no todas las aproximaciones son polinómicas. Los métodos comunes de estimación incluyen escalar, lineal, hiperbólico y logarítmico. Por lo general, se utiliza una base decimal para la estimación mental o con papel y lápiz. Una base binaria es más adecuada para las estimaciones por computadora. Al estimar, el exponente y la mantisa suelen tratarse 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 único intervalo, las medias aritméticas (5,5) o geométricas ( ) son estimaciones plausibles. El error absoluto y relativo para estas serán diferentes. En general, un único escalar será muy inexacto. Las estimaciones mejores 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 del 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 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, se eliminan del número las potencias de la base y se reduce el intervalo a , se puede utilizar como aproximación una línea secante que abarque el arco o una línea tangente en algún punto a lo largo del arco, pero una línea de regresión de mínimos cuadrados que intersecta el arco será más precisa. ${\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 . Reordenando, . 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}}$$

Esta 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, reste uno del exponente de , o, en sentido figurado, mueva el punto decimal un dígito a la izquierda. Para esta formulación, cualquier constante aditiva 1 más un pequeño incremento dará como resultado 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 es menor que 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 está severamente 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 opciones 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. Para dos 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 . Por lo tanto, 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 se producen 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 17% en ambos casos. 17% o 0,17 es mayor que 1/10, por lo que el método arroja una precisión de menos de un dígito decimal.

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 situada a lo largo de un arco de Y = x ² mejor que una línea. Las estimaciones hiperbólicas son más complejas computacionalmente, 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. Por lo tanto, 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 ser precisa solo hasta un dígito decimal, porque la estimación general solo es así de precisa y se puede hacer mentalmente. Una estimación hiperbólica es mejor en promedio que las estimaciones escalares o lineales. 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 uno comienza con 10 y aplica iteraciones de Newton-Raphson directamente, se requerirán dos iteraciones, lo que dará como resultado 3,66, antes de que se exceda 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 requerirí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 solo ecuaciones aritméticas en lugar de algebraicas, utiliza las tablas de multiplicar al revés: 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 dará un primer dígito correcto, pero no es preciso hasta 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 que estén a la mitad de los cuadrados. Por lo tanto, cualquier número entre 25 y la mitad de 36, que es 30,5, se estima en 5; cualquier número mayor que 30,5 hasta 36, ​​se estima en 6. ^{[Nota 3]} El procedimiento solo requiere un poco de aritmética para encontrar un número límite en el 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 para , ${\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: donde ${\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 la anterior, 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. Generalmente 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 hacer mentalmente.

Ejemplo: halla la raíz cuadrada de 75. 75 = 75 × 10 ^{2  · 0} , por lo que a es 75 y n es 0. De las tablas de multiplicar, la raíz cuadrada de la mantisa debe ser 8 coma algo porque 8 × 8 es 64, pero 9 × 9 es 81, demasiado grande, por lo que 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. 11/17 es un poco menor que 12/18, que es 2/3s o .67, así que adivina .66 (está bien adivinar aquí, el error es muy pequeño). Entonces la estimación es 8 + .66 = 8.66 . √ 75 elevado a tres cifras significativas es 8,66, por lo que la estimación es válida hasta tres cifras significativas. No todas las estimaciones realizadas con este método serán tan precisas, pero se aproximarán.

Estimaciones binarias

Cuando se trabaja en el sistema numérico binario (como lo hacen internamente las computadoras), al expresar como donde , 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 para 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 de 5,3%. El error relativo es un poco menor que 1/2 ⁴ , por lo que la estimación es válida 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 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 que el bit inferior del 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 precisión de 8 bits (2+ dígitos decimales). ${\displaystyle a}$ ${\displaystyle a}$

El método de Heron

El primer algoritmo explícito para aproximar se conoce como método de Herón , en honor al matemático griego del siglo I Herón de Alejandría, quien describió el método en su obra Métrica del año 60 d . C. ^[3] Este método también se denomina método babilónico (que 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 realizar cálculos iterativos hasta lograr la precisión deseada. La secuencia definida por esta ecuación converge a ${\displaystyle S}$ $${\displaystyle x_{n+1}={\frac {1}{2}}\left(x_{n}+{\frac {S}{x_{n}}}\right),}$$ ${\displaystyle \ {\bigl (}\ x_{0},\ x_{1},\ x_{2},\ x_{3},\ \ldots \ {\bigr )}\ }$ ${\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 : la cantidad de dígitos correctos de se duplica aproximadamente con cada iteración. ${\displaystyle x^{2}-S=0}$ ${\displaystyle x_{n}}$

Derivación

La idea básica es que si es una sobreestimación de la raíz cuadrada de un número real no negativo, entonces será 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). ${\displaystyle \ x\ }$ ${\displaystyle \ S\ }$ ${\displaystyle \ {\tfrac {\ S\ }{x}}\ }$

Más precisamente, si es nuestra estimación inicial de y es el error en nuestra estimación tal que entonces podemos expandir el binomio como: y resolver para el término de error ${\displaystyle \ x\ }$ ${\displaystyle \ {\sqrt {S~}}\ }$ ${\displaystyle \ \varepsilon \ }$ ${\displaystyle \ S=\left(x+\varepsilon \right)^{2}\ ,}$ $${\displaystyle \ {\bigl (}\ x+\varepsilon \ {\bigr )}^{2}=x^{2}+2x\varepsilon +\varepsilon ^{2}}$$

${\displaystyle \varepsilon ={\frac {\ S-x^{2}\ }{\ 2x+\varepsilon \ }}\approx {\frac {\ S-x^{2}\ }{2x}}\ ,}$Si suponemos que ${\displaystyle \ \varepsilon \ll x~}$

Por lo tanto, podemos compensar el error y actualizar nuestra estimación anterior como Dado que el error calculado no fue exacto, esta no es la respuesta real, sino que se convierte en nuestra nueva estimación para utilizar en la siguiente ronda de corrección. El proceso de actualización se repite hasta que se obtiene la precisión deseada. $${\displaystyle \ x+\varepsilon \ \approx \ x+{\frac {\ S-x^{2}\ }{2x}}\ =\ {\frac {\ S+x^{2}\ }{2x}}\ =\ {\frac {\ {\frac {S}{\ x\ }}+x\ }{2}}\ \equiv \ x_{\mathsf {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 hasta seis cifras significativas, utilice el método de estimación aproximada anterior para obtener ${\displaystyle \ {\sqrt {S~}}\ }$ ${\displaystyle \ S=125348\ ,}$ $${\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, hasta tres decimales. ${\displaystyle \ {\sqrt {125348~}}\approx 354.045\ }$

Convergencia

Gráficos semilogarítmicos que comparan la velocidad de convergencia del método de Heron para hallar la raíz cuadrada de 100 para diferentes suposiciones iniciales. Las suposiciones negativas convergen a la raíz negativa, las suposiciones 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, pase el cursor sobre un gráfico para mostrar sus puntos.

Supongamos que Entonces, para cualquier número natural, el error relativo en se define por y por lo tanto ${\displaystyle \ x_{0}>0~~{\mathsf {and}}~~S>0~.}$ ${\displaystyle \ n:x_{n}>0~.}$ ${\displaystyle \ x_{n}\ }$ $${\displaystyle \ \varepsilon _{n}={\frac {~x_{n}\ }{\ {\sqrt {S~}}\ }}-1>-1\ }$$ $${\displaystyle \ x_{n}={\sqrt {S~}}\cdot \left(1+\varepsilon _{n}\right)~.}$$

Entonces se puede demostrar que $${\displaystyle \ \varepsilon _{n+1}={\frac {\varepsilon _{n}^{2}}{2(1+\varepsilon _{n})}}\geq 0~.}$$

Y por lo tanto y en consecuencia esa convergencia está asegurada, y cuadrática . $${\displaystyle \ \varepsilon _{n+2}\leq \min \left\{\ {\frac {\ \varepsilon _{n+1}^{2}\ }{2}},{\frac {\ \varepsilon _{n+1}\ }{2}}\ \right\}\ }$$

El peor escenario para la convergencia

Si utilizamos 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í que, 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 cálculo, para evitar un error de redondeo significativo. ${\displaystyle \ x_{n}\ }$

Método Bakhshali

Este método para hallar una aproximación a una raíz cuadrada se describió en un antiguo manuscrito indio , llamado el manuscrito Bakhshali . Es equivalente a dos iteraciones del método babilónico comenzando con x _0. Por lo tanto, el algoritmo es cuárticamente convergente, lo que significa que el número de dígitos correctos de la aproximación se cuadruplica aproximadamente con cada iteración. ^[4] La presentación original, utilizando 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 entero. Si es un entero elegido de modo que esté cerca de , 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, sea 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 inverso que resuelve . Es más lento que el método babilónico, pero tiene varias ventajas: ${\displaystyle (x+y)^{2}=x^{2}+2xy+y^{2}}$

• Puede resultar más sencillo realizar cálculos manuales.
• Se sabe que cada dígito de la raíz encontrado es correcto, es decir, no es necesario modificarlo posteriormente.
• Si la raíz cuadrada tiene una expansión que termina, el algoritmo termina después de encontrar el último dígito. Por lo tanto, se puede utilizar para verificar 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 llevan a que cada dígito siguiente del resultado sea incorrecto, 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 teoría, es demasiado costoso para las implementaciones de software. Cada iteración implica números más grandes, lo que requiere más memoria, pero solo avanza la respuesta en un dígito correcto. Por lo tanto, el algoritmo requiere más tiempo para cada dígito adicional.

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

Principio básico

En primer lugar, consideremos el caso de hallar 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. En concreto: $${\displaystyle Z=\left(10X+Y\right)^{2}=100X^{2}+20XY+Y^{2}}$$

Ahora, utilizando 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 a 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 la décima mientras intentamos averiguar 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 de raíz cuadrada arbitrario. 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, el término del lado derecho se puede expandir como $${\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 término m -ésimo del lado derecho de la suma anterior está dado por donde es la raíz cuadrada aproximada encontrada hasta ahora. Ahora cada nueva suposición debe satisfacer la recursión tal que para todos con inicialización Cuando se ha encontrado la raíz cuadrada exacta; si no, entonces la suma de s da una aproximación adecuada de la raíz cuadrada, siendo el error de aproximación. ${\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 de numeración decimal tenemos donde son marcadores de posición y los coeficientes . En cualquier etapa m-ésima del cálculo de la raíz cuadrada, la raíz aproximada encontrada hasta el momento y el término de suma se dan por $${\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)}.}$$

En este caso, 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 sección siguiente 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 en 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 para o para . El hecho de que solo tengamos dos opciones posibles para también hace que el proceso de decidir el valor de en la etapa m -ésima del cálculo sea más fácil. Esto se debe a que solo necesitamos verificar si para 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.}$

Decimal (base 10)

Escribe el número original en forma decimal. Los números se escriben de forma similar al algoritmo de la división larga y, como en la división larga, la raíz se escribirá en la línea de arriba. Ahora separa los dígitos en pares, comenzando desde el punto decimal y yendo tanto hacia la izquierda como hacia la derecha. El punto decimal de la raíz estará sobre el punto decimal del cuadrado. Un dígito de la raíz aparecerá sobre 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. Empezando 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 habrá resto). En otras palabras, multiplique el resto por 100 y sume los dos dígitos. Este será el valor actual c .
2. Encuentra 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).
   • Determinar el dígito mayor x tal que . Utilizaremos 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 cuál 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.
   • Coloca el dígito como el siguiente dígito de la raíz, es decir, encima de los dos dígitos del cuadrado que acabas de bajar. De esta manera, el siguiente p será el antiguo p por 10 más x . ${\displaystyle x}$
3. Restar y de c para formar un nuevo resto.
4. Si el resto es cero y no hay más dígitos que eliminar, 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*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 termina: Respuesta=12.34

Sistema de numeración binario (base 2)

Esta sección utiliza el formalismo de la sección de cálculo dígito por dígito anterior, con la ligera variación de que dejamos , con cada o . Iteramos todos los , desde abajo hasta , y construimos una solución aproximada , la suma de todos para los que hemos determinado el valor. Para determinar si es igual a o , dejamos . Si (es decir, el cuadrado de nuestra solución aproximada incluyendo no excede el cuadrado objetivo) entonces , de lo contrario y . Para evitar elevar al cuadrado en cada paso, almacenamos la diferencia y la actualizamos de forma incremental estableciendo con . Inicialmente, establecemos para 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 de manera eficiente 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: cuál es el resultado final devuelto en la función siguiente. $${\displaystyle c_{-1}=P_{0}2^{0}=P_{0}=N,}$$

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

int32_t es raíz cuadrada ( int32_t n ) {    assert (( "la entrada sqrt no debe ser negativa" , n > 0 ));    // X_(n+1) int32_t x = n ;    //c_n int32_t c = 0 ;    // d_n que comienza en la potencia más alta de cuatro <= n int32_t d = 1 << 30 ; // Se establece el segundo bit desde arriba.       // Igual que ((unsigned) INT32_MAX + 1) / 2. mientras ( d > n ) {     d >>= 2 ;   } // para dₙ … d₀ mientras ( d != 0 ) {     si ( 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 ) + d ; // 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)    } d >>= 2 ; // d_(m-1) = d_m/4    } devolver c ; // c_(-1)  }

Se pueden lograr algoritmos más rápidos, en binario, decimal o cualquier otra base, utilizando tablas de búsqueda, lo que en realidad implica intercambiar más espacio de almacenamiento por un tiempo de ejecución reducido . ^[7]

Identidad exponencial

Las calculadoras de bolsillo suelen implementar buenas rutinas para calcular la función exponencial y el logaritmo natural , y luego calculan la raíz cuadrada de S utilizando la identidad encontrada usando las propiedades de los logaritmos ( ) y exponenciales ( ): ^{[ cita requerida ]} El denominador en la fracción corresponde a la raíz n ésima. En el caso anterior, el denominador es 2, por lo tanto, la ecuación especifica que se debe encontrar la raíz cuadrada. La misma identidad se utiliza cuando se calculan raíces cuadradas con tablas de logaritmos o reglas de cálculo . ${\displaystyle \ln x^{n}=n\ln x}$ ${\displaystyle e^{\ln x}=x}$ $${\displaystyle {\sqrt {S}}=e^{{\frac {1}{2}}\ln S}.}$$

Un método iterativo de dos variables

Este método es aplicable para hallar 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 potencia correspondiente de 2, cambiando el exponente o desplazándolo, respectivamente. Por lo tanto, se puede mover al rango . Además, el siguiente método no emplea divisiones generales, sino solo sumas, restas, multiplicaciones y divisiones por potencias de dos, que nuevamente son triviales de implementar. Una desventaja del método es que los errores numéricos se acumulan, 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 mientras los pasos iterativos leen Entonces, (while ). $${\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 lo tanto también de , es cuadrática. ${\displaystyle c_{n}\,\!}$ ${\displaystyle a_{n}\,\!}$

La prueba del método es bastante sencilla. Primero, reescribimos la definición iterativa de como Luego es sencillo demostrar por inducción que y, por lo tanto, la convergencia de al resultado deseado está asegurada por la convergencia de a 0, que a su vez se sigue de . ${\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 que se ha encontrado, se encuentra mediante una simple multiplicación: . Estas iteraciones implican solo multiplicación y no división. Por lo tanto, son más rápidas 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 ella en lugar de converger hacia ella. Por lo tanto, puede ser ventajoso realizar una iteración del método babilónico en 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 utilizando 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 Householder de orden dos. Este converge cúbicamente , pero implica cinco multiplicaciones por iteración: ^{[ cita requerida ]} y $${\displaystyle y_{n}=S\cdot x_{n}^{2},}$$ $${\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 usa punto flotante, el método de Halley se puede reducir a cuatro multiplicaciones por iteración mediante el cálculo previo y el ajuste de todas las demás constantes para compensar: y ${\textstyle {\sqrt {3/8}}S}$ $${\displaystyle y_{n}={\sqrt {\frac {3}{8}}}S\cdot x_{n}^{2},}$$ $${\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

El algoritmo de Goldschmidt es una extensión de la división de Goldschmidt , llamada así por Robert Elliot Goldschmidt, ^{[11] [12]} que se puede utilizar para calcular raíces cuadradas. Algunas computadoras utilizan el algoritmo de Goldschmidt para calcular simultáneamente y . El algoritmo de Goldschmidt encuentra más rápido que la iteración de Newton-Raphson en una computadora con una instrucción de multiplicación-suma fusionada y una unidad de punto flotante segmentada o dos unidades de punto flotante independientes. ^[13] ${\displaystyle {\sqrt {S}}}$ ${\displaystyle 1/{\sqrt {S}}}$ ${\displaystyle {\sqrt {S}}}$

La primera forma de escribir el algoritmo de Goldschmidt comienza

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

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

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

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

y se repite hasta que esté lo suficientemente cerca de 1, o un número fijo de iteraciones. Las iteraciones convergen a y Nótese que es posible omitir tanto y como del cálculo, y si se desean ambos, se pueden utilizar al final en lugar de calcularlos en cada iteración. $${\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}}$

Una segunda forma, que utiliza operaciones de multiplicación-suma fusionadas , comienza

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

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

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

y se repite hasta que esté lo suficientemente cerca de 0, o un número fijo de iteraciones. Esto converge a y $${\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 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 requerida ]} Por lo tanto, esta no es una forma particularmente eficiente de cálculo. Para maximizar la tasa de convergencia, elija N de modo que sea lo más pequeño posible. ${\displaystyle {\frac {|d|}{N^{2}}}\,}$

Expansión de fracciones continuas

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 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 , b y c son enteros), y en particular, las raíces cuadradas de los 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 más bien su expansión en fracción continua y, por lo tanto, su aproximación racional. Sea S el número positivo para el que se requiere encontrar la raíz cuadrada. Luego, suponiendo que a es un número que sirve como una estimación inicial y que 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 numerador/denominador para fracciones continuas (ver a la izquierda) es complicada de escribir y de incorporar en sistemas de formato de texto. Por ello, los matemáticos han ideado varias notaciones alternativas, como ^[14] $${\displaystyle {\sqrt {S}}=a+{\frac {r}{2a+}}\,{\frac {r}{2a+}}\,{\frac {r}{2a+}}\cdots }$$

En general, una notación aún más compacta es: ^[15] Para las fracciones continuas repetidas (como lo hacen todas las raíces cuadradas de cuadrados no perfectos), la repetición se representa solo una vez, con una línea superior para indicar una repetición no terminal de la parte sobrerrayada: ^[16] ${\displaystyle r=1}$ $${\displaystyle [a;2a,2a,2a,\cdots ]}$$ $${\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 ^[17] y obtener una raíz es hacer sustituciones numéricas para 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 se realiza de la siguiente manera (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: redondeado a tres dígitos de precisión. $${\displaystyle 17\div 12=1.42}$$

El valor real de √ 2 es 1,41 con tres dígitos significativos. El error relativo es 0,17%, por lo que la fracción racional es buena con una precisión de casi tres dígitos. Si se toman más denominadores, se obtienen aproximaciones cada vez mejores: 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 continuas simples 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 al truncar una fracción continua se obtiene una fracción racional que es la 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 menor o igual a 70 es una aproximación tan buena a √ 2 como 99/70.

Aproximaciones que dependen de la representación en punto flotante

Un número se representa en un formato de punto flotante como , 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 una mejora en la simplicidad, pero supongamos que solo se requiere una aproximación: entonces, solo es bueno hasta un orden de magnitud. A continuación, reconozca que algunas potencias, p , serán impares, por lo que 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 trabajar con potencias fraccionarias de la base, multiplica la mantisa por la base y resta uno a la potencia para que quede par. La representación ajustada será el equivalente a 31,4159 × 10² por lo que la raíz cuadrada será √ 31,4159 × 10¹ .

Si se toma la parte entera de la mantisa ajustada, sólo pueden existir los valores de 1 a 99, y podrían utilizarse como índice en una tabla de 99 raíces cuadradas precalculadas para completar la estimación. Una computadora que utilice base dieciséis requeriría una tabla más grande, pero una que utilice base dos requeriría sólo tres entradas: los bits posibles de la parte entera de la mantisa ajustada son 01 (la potencia es par, por lo que no hubo desplazamiento, recordando que un número de punto flotante normalizado 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 apareados de la mantisa son 01, mientras que .625 = 0,101 en binario se normaliza a 1,01 × 2 ⁻¹ una potencia impar por lo que el ajuste es a 10,1 × 2 ⁻² y los bits apareados son 10. Observe que el bit de orden bajo de la potencia se refleja en el bit de orden alto de la mantisa por pares. Una potencia par tiene su bit de orden bajo 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. Por lo tanto, cuando la potencia se reduce a la mitad, es como si su bit de orden bajo se desplazara 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 dé resultados equivalentes. Ahora todo depende de los detalles exactos del formato de la representación, además de las operaciones disponibles para acceder y manipular las partes del número. Por ejemplo, Fortran ofrece una EXPONENT(x)función para obtener la potencia. El esfuerzo invertido en idear una buena aproximación inicial se recupera al evitar las iteraciones adicionales del proceso de refinamiento que se habrían necesitado para una aproximación deficiente. Dado que son pocas (una iteración requiere una división, una suma y una reducción a la mitad), la restricción es severa.

Muchos ordenadores siguen la representación IEEE (o una suficientemente similar) y se puede obtener una aproximación muy rápida a la raíz cuadrada para 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 en base 2. Es decir ${\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, notablemente, 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, escalándolo 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 se representa con un número hexadecimal 0x3F800000, que representaría si se tomara como un entero. Si se utiliza la fórmula anterior, se obtiene , como se esperaba de . De manera similar, se obtiene 0.5 a partir 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, divida el logaritmo por 2 y convierta el valor nuevamente. 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 suponer que es el sesgo del exponente y es la cantidad 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}.}$$

/* 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_t i ; } val = { z }; /* Convertir tipo, conservando 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 . i -= 1 << 23 ; /* Restar 2^m. */ val . i >>= 1 ; /* Dividir por 2. */ val . i += 1 << 29 ; /* Suma ((b + 1) / 2) * 2^m. */                      retorna val . f ; /* Interpretar nuevamente como float */ } 

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. Por lo tanto, las tres operaciones, sin incluir la conversión, se pueden reescribir como

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

where a is a bias for adjusting the approximation errors. For example, with a = 0 the results are accurate for even powers of 2 (e.g. 1.0), but for other numbers the results will be slightly too big (e.g. 1.5 for 2.0 instead of 1.414... with 6% error). With a = −0x4B0D2, the maximum relative error is minimized to ±3.5%.

If the approximation is to be used for an initial guess for Newton's method to the equation ${\displaystyle (1/x^{2})-S=0}$, then the reciprocal form shown in the following section is preferred.

Reciprocal of the square root

A variant of the above routine is included below, which can be used to compute the reciprocal of the square root, i.e., ${\displaystyle x^{-1/2}}$ instead, was written by Greg Walsh. The integer-shift approximation produced a relative error of less than 4%, and the error dropped further to 0.15% with one iteration of Newton's method on the following line.^[18] In computer graphics it is a very efficient way to normalize a vector.

float invSqrt(float x) { float xhalf = 0.5f * x; union { float x; int i; } u; u.x = x; u.i = 0x5f375a86 - (u.i >> 1); /* The next line can be repeated any number of times to increase accuracy */ u.x = u.x * (1.5f - xhalf * u.x * u.x); return u.x;}

Some VLSI hardware implements inverse square root using a second degree polynomial estimation followed by a Goldschmidt iteration.^[19]

Negative or complex square

If S < 0, then its principal square root is $${\displaystyle {\sqrt {S}}={\sqrt {\vert S\vert }}\,\,i\,.}$$

If S = a+bi where a and b are real and b ≠ 0, then its principal square root is $${\displaystyle {\sqrt {S}}={\sqrt {\frac {\vert S\vert +a}{2}}}\,+\,\operatorname {sgn}(b){\sqrt {\frac {\vert S\vert -a}{2}}}\,\,i\,.}$$

This can be verified by squaring the root.^[20][21]Here $${\displaystyle \vert S\vert ={\sqrt {a^{2}+b^{2}}}}$$

is the modulus of S. The principal square root of a complex number is defined to be the root with the non-negative real part.

See also

• Alpha max plus beta min algorithm
• nth root algorithm

Notes

1. The factors two and six are used because they approximate the geometric means of the lowest and highest possible values with the given number of digits: ${\displaystyle {\sqrt {{\sqrt {1}}\cdot {\sqrt {10}}}}={\sqrt[{4}]{10}}\approx 1.78\,}$ and ${\displaystyle {\sqrt {{\sqrt {10}}\cdot {\sqrt {100}}}}={\sqrt[{4}]{1000}}\approx 5.62\,}$.
2. The unrounded estimate has maximum absolute error of 2.65 at 100 and maximum relative error of 26.5% at y=1, 10 and 100
3. If the number is exactly half way between two squares, like 30.5, guess the higher number which is 6 in this case
4. This is incidentally the equation of the tangent line to y = x² at y = 1.

References

1. Jackson 2011.
2. Fowler & Robson 1998.
3. Heath 1921.
4. Bailey & Borwein 2012.
5. Simply Curious 2018.
6. Guy & UKC 1985.
7. Steinarson, Corbit & Hendry 2003.
8. Wilkes, Wheeler & Gill 1951.
9. Campbell-Kelly 2009.
10. Gower 1958.
11. Goldschmidt, Robert E. (1964). Applications of Division by Convergence (PDF) (Thesis). M.Sc. dissertation. M.I.T. OCLC 34136725. Archived (PDF) from the original on 2015-12-10. Retrieved 2015-09-15.
12. "Authors". IBM Journal of Research and Development. 11: 125–127. 1967. doi:10.1147/rd.111.0125. Archived from the original on 18 July 2018.
13. Markstein 2004.
14. see: Generalized continued fraction#Notation
15. see: Continued fraction#Notations
16. see: Periodic continued fraction
17. Sardina 2007, 2.3j on p.10.
18. Lomont 2003.
19. Piñeiro & Díaz Bruguera 2002.
20. Abramowitz & Stegun 1964, Section 3.7.26.
21. Cooke 2008.

Bibliography

• Abramowitz, Miltonn; Stegun, Irene A. (1964). Handbook of mathematical functions with formulas, graphs, and mathematical tables. Courier Dover Publications. p. 17. ISBN 978-0-486-61272-0.
• Bailey, David; Borwein, Jonathan (2012). "Ancient Indian Square Roots: An Exercise in Forensic Paleo-Mathematics" (PDF). American Mathematical Monthly. Vol. 119, no. 8. pp. 646–657. Retrieved 2017-09-14.
• Campbell-Kelly, Martin (September 2009). "Origin of Computing". Scientific American. 301 (3): 62–69. Bibcode:2009SciAm.301c..62C. doi:10.1038/scientificamerican0909-62. JSTOR 26001527. PMID 19708529.
• Cooke, Roger (2008). Classical algebra: its nature, origins, and uses. John Wiley and Sons. p. 59. ISBN 978-0-470-25952-8.
• Fowler, David; Robson, Eleanor (1998). "Square Root Approximations in Old Babylonian Mathematics: YBC 7289 in Context" (PDF). Historia Mathematica. 25 (4): 376. doi:10.1006/hmat.1998.2209.
• Gower, John C. (1958). "A Note on an Iterative Method for Root Extraction". The Computer Journal. 1 (3): 142–143. doi:10.1093/comjnl/1.3.142.
• Jackson, Terence (2011-07-01). "95.42 Irrational square roots of natural numbers — a geometrical approach". The Mathematical Gazette. 95 (533): 327–330. doi:10.1017/S0025557200003193. ISSN 0025-5572. S2CID 123995083.
• Guy, Martin; UKC (1985). "Fast integer square root by Mr. Woo's abacus algorithm (archived)". Archived from the original on 2012-03-06.
• Heath, Thomas (1921). A History of Greek Mathematics, Vol. 2. Oxford: Clarendon Press. pp. 323–324.
• Lomont, Chris (2003). "Fast Inverse Square Root" (PDF).
• Markstein, Peter (November 2004). Software Division and Square Root Using Goldschmidt's Algorithms (PDF). 6th Conference on Real Numbers and Computers. Dagstuhl, Germany. CiteSeerX 10.1.1.85.9648.
• Piñeiro, José-Alejandro; Díaz Bruguera, Javier (December 2002). "High-Speed Double-Precision Computationof Reciprocal, Division, Square Root, and Inverse Square Root". IEEE Transactions on Computers. 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).
• Simply Curious (5 de junio de 2018). "A la caza del manuscrito de Bakhshali". Blog Simply Curious . Consultado el 21 de diciembre de 2020 .
• Steinarson, Arne; Corbit, Dann; Hendry, Mathew (2003). "Función 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". MathWorld .
• Raíces cuadradas por sustracción
• 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