Algoritmo de raíz cuadrada más rápido

Question

(edit, 9 años más tarde... hola desarrolladores inteligentes de contratos, ¡sé que por eso están aquí jaja)

¿Cuál es el algoritmo más rápido para encontrar la raíz cuadrada de un número?

Creé uno que puede encontrar la raíz cuadrada de "$987654321$" a $16$ lugares decimales en solo $20$ iteraciones

He probado el método de Newton y también mi propio método (el código de Newton se encuentra a continuación)

¿Cuál es el algoritmo conocido más rápido para tomar la segunda raíz de un número?

Mi código para el Método de Newton (*Edit: hubo un error en mi código, está corregido en los comentarios de abajo):

    a=2   //2a raíz
    b=97654321   //base
    n=1   //suposición inicial
    c=0   //iteración actual (esta es una variable cambiante)
    r=500000   //número total de iteraciones a ejecutar
    while (c  " + c)
    }

Answer 1

¡Si utilizas el método de Halley, muestras convergencia cúbica! Este método es el segundo en la clase de los métodos de Householder.

El método de Halley es: $$ x_{n+1} = x_n - \frac{2f(x_n)f'(x_n)}{2[f'(x_n)]^2-f(x_n)f''(x_n)} $$ Si permitimos que $$f(x) = x^2 - a$$ que cumple con los criterios, (segunda derivada continua)

Entonces el método de Halley es:

$$ x_{n+1} = x_n - \frac{\left(2x_n^3 - 2ax_n\right)}{3x_n^2 + a} $$ Lo cual se simplifica a: $$ x_{n+1} = \frac{x_n^3 + 3ax_n}{3x_n^2 + a} $$ También añadiré este documento que discute extensiones del método newtoniano.

Existe una extensión debido a Potra y Pták llamada el "método de dos pasos" que puede ser reescrito como el esquema iterativo $$x_{n+1} =x_n \frac{f(x_n)+f\left(x_n \frac{f(x_n)}{f(x_n)}\right)}{f'(x_n)}$$ que converge cúbicamente en algún vecindario de la raíz $x^{*}$ que no requiere el cálculo de la segunda derivada.

Ver: Sobre métodos de tipo Newton con convergencia cúbica para más información sobre este tema.

Como Hurkyl y otros han señalado, lo mejor es simplemente utilizar el Método de Newton. Estos métodos alternativos generalmente vienen con más operaciones por iteración. No valen realmente el costo computacional, pero son una buena comparación.

Answer 2

El método de Newton para resolver $f(x)=x^2-N=0$ lleva a la recurrencia $x_{n+1}=x_n-\frac{x_n^2-N}{2x_n}=\frac{x_n+N/x_n}2$, también conocido como método de Herón. Dado que $f'(x)\ne0$ en la raíz, la convergencia es cuadrática (es decir, el número de decimales correctos se duplica con cada paso una vez que se alcanza una precisión umbral). Los resultados dependen, por supuesto, del valor inicial. Simplemente adivinando $x_0=1$ llegamos a $$x_{1} = 493827161.00000000000\\ x_{2} = 246913581.49999999899\\ x_{3} = 123456792.74999998937\\ x_{4} = 61728400.374999909634\\ x_{5} = 30864208.187499266317\\ x_{6} = 15432120.093744108961\\ x_{7} = 7716092.0468278285538\\ x_{8} = 3858110.0230600438248\\ x_{9} = 1929183.0086989850523\\ x_{10} = 964847.48170274167713\\ x_{11} = 482935.55973452582660\\ x_{12} = 242490.33277426247529 \\ x_{13} = 123281.64823302696814 \\ x_{14} = 65646.506775513694016 \\ x_{15} = 40345.773393104621684 \\ x_{16} = 32412.760144718719221 \\ x_{17} = 31441.958847358050036 \\ x_{18} = 31426.971626562861740 \\ x_{19} = 31426.968052932067262 \\ x_{20} = 31426.968052931864079 $$
con un error suficientemente pequeño.

Answer 3

No es un "algoritmo" legítimo, pero de todas formas es un truco ingenioso que una vez usé en un código que requería tomar una raíz cuadrada inversa millones de veces (cuando hacía astrofísica computacional) se encuentra aquí:

http://es.wikipedia.org/wiki/Raíz_cuadrada_inversa_rápida

Sí utiliza algunas iteraciones del método de Newton, pero solo después de algunos trucos muy inteligentes.

Recuerdo que ingenuamente usaba la optimización por ensayo y error para encontrar un "número mágico" que se acercara más a una raíz cuadrada directa, aunque por supuesto era mucho más lento (pero aún más rápido que simplemente llamar a "sqrt" de math.h) y tenía un error más alto que el truco anterior.

Answer 4

En caso de que te refieras no a la velocidad teórica sino al algoritmo que ejecuta más rápido en una computadora, entonces es el "quake 3" algoritmo o alguno de sus derivados que, creo, está implementado como la función sqrt de GCC en los niveles de optimización 2 y 3. Es irónico que el factor determinante aquí sea un valor y una implementación inicial ingeniosa en vez del esquema iterativo real. En mi computadora portátil normal, toma aproximadamente 2.0e-09s llamar a sqrt con gcc -O2 o gcc -O3, lo cual es aproximadamente 2.8 veces menos que lo que el segundo lugar, la implementación estándar de sqrt ofrece.

Answer 5

Acabo de darme cuenta de que nadie ha señalado el siguiente truco: para calcular $1/\sqrt{n}$, el método de Newton utilizado para encontrar una raíz de $f(y) = 1/y^2 - n$ da la iteración

$$ y \leftarrow \frac{3y - ny^3}{2}$$

Creo que en algunos rangos, es más rápido calcular una estimación de $\sqrt{n}$ usando el método de Newton para calcular primero $1/\sqrt{n}$ y luego invertir la respuesta que usar directamente el método de Newton.

Probablemente sea más rápido calcular esto como

$$ \frac{3y - ny^3}{2} = y - \frac{n y^2 - 1}{2}y$$

La cuestión radica en que si $y$ es una buena aproximación de $1/\sqrt{n}$, entonces $n y^2 - 1$ es una buena aproximación de $0, lo que reduce la cantidad de precisión que necesitas mantener y puedes hacer trucos para acelerar el cálculo de un producto si ya conoces muchos de sus dígitos.

---

Pero es posible que puedas hacerlo aún mejor calculando una aproximación de ambos $x \sim \sqrt{n}$ e $y \sim 1/\sqrt{n}$ simultáneamente. No he trabajado en los detalles.

La razón para esperar que esto funcione es que un cálculo de actualización mejor para $x$ puede estar disponible porque $ny \sim n/x$, y luego una forma más rápida de actualizar $y$ basándose en $y \sim 1/x$ en lugar de $y \sim 1/\sqrt{n}$.