¿Qué algoritmo usan las computadoras para calcular sqrt (x)?

Podría decirse que la mayoría de los lenguajes de programación invocan la función sqrt () en en su código nativo. La implementación es en programación C.

Fuente de sqrt.c:

https://opensource.apple.com/sou…

Explicando el algoritmo de la descripción,

El algoritmo utiliza el método de Newton para calcular la raíz cuadrada doble redondeada correctamente IEEE-754, comenzando con una estimación de 8 bits para: g Å Ãx e y Å 1 / 2Ãx. Usando instrucciones MAF, cada iteración refina las aproximaciones originales gy e con el modo de redondeo establecido en el más cercano. El paso final calcula g con el redondeo de la persona que llama restaurado. Esto a su vez garantiza el redondeo y las excepciones IEEE adecuadas. INEXACT es la única posible excepción planteada en este cálculo. Las conjeturas iniciales para gy e se determinan a partir del argumento x a través de la búsqueda de tabla en la matriz SqrtTable [256].

Es una relación de recurrencia, que funciona con cualquier valor inicial, normalmente la comenzamos con [math] \ frac {x} {2} [/ math]. La secuencia [math] sqrtx_ {n + 1} [/ math]: = [math] \ frac {1} {2} (sqrtx_n + \ frac {x} {sqrtx_n}) [/ math] converge y el valor límite es el raíz cuadrada de x. La convergencia es increíblemente rápida, pero recuerde que no existe la raíz cuadrada de los números negativos, de la cual no se requiere que este algoritmo sepa, en ausencia de manejo de errores.

Para demostrar la convergencia de la recurrencia, podemos usar la ventana inmediata de VBA. Solo necesitamos 5 iteraciones para obtener [math] \ sqrt {2} [/ math] con una precisión decimal de 14 dígitos, eso es realmente rápido.

[matemáticas] x = 1 \\ x = (x + 2 / x) / 2:? x \\ 1,41421356237309 \\ 1,41421356237309 \\ 1,41421356237469 \\ 1,41421568627451 \\ 1,41666666666667 \\ 1 , 5 [/ matemáticas]

Una implementación común, dependiendo de la sofisticación del procedimiento, es buscar primero la [matemática] \\ n \\ [/ matemática] más cercana de tal manera. (El cuadrado perfecto más cercano, es rápido de encontrar y es un gran lugar para comenzar a buscar).

[matemáticas] n ^ 2> x> (n-1) ^ 2 [/ matemáticas]

Entonces puedes calcular alguna diferencia:

[matemáticas] \ Delta {x_s} = n ^ 2 – x [/ matemáticas]

Geométricamente hablando, estamos tratando con x

[matemáticas] x = \ frac {\ Delta {x_s}} {2n} [/ matemáticas]

[matemáticas] Definir algunas: [/ matemáticas]

[matemáticas] \ kappa = n + \ Delta {x_s} [/ matemáticas]

[matemática] \ implica \ sqrt (x) \ aprox \ kappa + \ frac {{\ Delta {x_s}} ^ 2} {2 \ kappa} [/ matemática]