Métodos 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 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).

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.

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

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

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

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.

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.

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.

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

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.

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

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

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

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]

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

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.

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

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.

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

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]

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

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]

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

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

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