Mejor respuesta
1er método
= UNICHAR (8730) da el símbolo de raíz cuadrada en Microsoft Excel.
Probado en Excel 2016
Segundo método
- Vaya a Insertar pestaña y haga clic en el Símbolo del grupo de símbolos.
- En Símbolos, seleccione Operadores matemáticos del subconjunto y use el símbolo de raíz cuadrada.
Respuesta
La mayoría de las CPU modernas proporcionan una operación de raíz cuadrada de forma nativa. Entonces, con un lenguaje de programación típico en hardware moderno típico, es casi seguro que esa será la operación en última instancia.
Así que hablemos del método que usan casi todas las CPU modernas de propósito general.
Representación numérica
Lo primero que debemos entender es cómo una computadora representa realmente el tipo de números de los que estamos hablando. Se almacenan en una especie de notación científica.
Ahora, el tipo de notación científica con la que puede estar familiarizado, donde un número como -134.5 se representa como -1.345 \ times 10 ^ {2}.
Cualquier número que no sea cero se puede representar en esta forma, que conceptualmente tiene tres partes: el signo (es decir, es el número positivo o negativo), la mantisa (un número entre 1 y 10, incluido 1 pero sin incluir 10, en este caso 1,345) y la exponente (la potencia a la que se eleva la base, en este caso 2; tenga en cuenta que el exponente puede ser negativo o cero en general).
La representación que casi todas las computadoras modernas usan es muy similar, excepto que el número se almacena usando una representación binaria en lugar de decimal. Entonces, ignorando el bit de signo y el cero (dado que encontrar la raíz cuadrada de cero es trivial, y la raíz cuadrada de un número negativo no es un número real), los números positivos se almacenan en la forma m \ times 2 ^ {e} donde m es un número entre 1 y 2 (incluyendo 1 pero sin incluir 2).
Esta representación se conoce como «punto flotante», debido a la forma en que puede mover el punto binario (análogo al punto decimal con el que puede estar familiarizado) ajustando el exponente.
La razón por la que todo esto es importante es porque la CPU usa la representación para ayudar a calcular las raíces cuadradas. Suponga que el exponente es par. Entonces:
\ sqrt {m \ times 2 ^ {2 \ epsilon}} = \ sqrt {m} \ times 2 ^ {\ epsilon}
De manera similar, si el exponente es impar, entonces:
\ sqrt {m \ times 2 ^ {2 \ epsilon + 1}} = \ sqrt {2} \ sqrt {m} \ times 2 ^ {\ epsilon}
Recuerde que m está en el rango [1,2). Esto significa que hemos reducido el problema a calcular la raíz cuadrada de cualquier número a uno de calcular la raíz cuadrada de un número en ese rango. O, si no queremos precalcular \ sqrt {2}, un número en el rango [1,4). De cualquier manera, hemos simplificado drásticamente el problema, porque ahora podemos usar métodos que se comportan bien en ese rango de números.
Multiplicación y división
Ahora que hemos llegado hasta aquí, podría pensar (si ha mirado las otras respuestas) que la solución ahora es usar un método como la iteración de Newton-Raphson para calcular el cuadrado raíz. Para calcular la raíz cuadrada de n, elija una suposición inicial x\_0 y repita:
x\_ {i + 1} = \ frac {1} {2} \ left (x\_i + \ frac {n} {x\_i } \ right)
Esta respuesta es incorrecta . Bueno, no está mal porque te dará una respuesta correcta. Pero está mal en que ningún diseñador de CPU que se precie (o cualquier escritor de bibliotecas si tuvieran que implementarlo en software) implementaría la raíz cuadrada de punto flotante de esta manera.
La división por dos es muy barata operación en binario (que, recuerde, es base 2, por lo que solo está cambiando el punto binario en un lugar). Sin embargo, la otra división es una operación muy costosa y, en este caso, debe realizar la operación varias veces.
La división es tan costosa, de hecho, que las CPU modernas utilizan un algoritmo iterativo que es similar a (pero no en realidad) la iteración de Newton-Raphson para realizar la división. Claramente, no queremos hacer esto en hardware, en un bucle interno.
En hardware de computadora moderno, es mucho más económico de realizar una operación de multiplicación que una operación de división. La razón es un poco compleja de explicar; tiene que ver con el hecho de que podemos colocar muchos más transistores en un chip de lo que solíamos, y la multiplicación es un problema que se puede pasar a muchos transistores de manera eficiente. Busque árboles de Wallace si está interesado en los detalles.
En cualquier caso, el punto es que la multiplicación es una operación comparativamente barata. Entonces, si podemos implementar la operación de raíz cuadrada en términos de multiplicación en lugar de división, sería mejor.
Newton-Raphson, tome dos
Ahora viene la primera idea clave: en lugar de calcular la raíz cuadrada, calcule el recíproco de la raíz cuadrada. Es decir, en lugar de \ sqrt {n}, calcula \ frac {1} {\ sqrt {n}}. Resulta que este es un número mucho más fácil de calcular, y si necesita la raíz cuadrada, multiplique este número por n y ya está.
El método de Newton-Raphson para la raíz cuadrada recíproca se ve así . Si x\_0 es una estimación inicial de \ frac {1} {\ sqrt {n}}, repita:
x\_ {i + 1} = \ frac {1} {2} x\_i \ left (3 – n {x\_i} ^ 2 \ right)
Nuevamente, la división por dos es bastante barata, y todo lo demás es multiplicación y suma / resta.
Esta es una excelente manera de implementar en software. Además, vale la pena señalar que en muchas situaciones prácticas (por ejemplo, normalizando un vector usando el teorema de Pitágoras), la raíz cuadrada recíproca es en realidad más útil que la raíz cuadrada, ya que dividir por una raíz cuadrada es menos eficiente que multiplicar por un cuadrado recíproco. root.
Sin embargo, no es así como se implementa normalmente en hardware.
Algoritmo de Goldschmidt
Ahora podemos ver el algoritmo de Goldschmidt, que calcula la raíz cuadrada y la raíz cuadrada recíproca juntas.
Dado b\_0 = n, si podemos encontrar una serie de números Y\_i tal que b\_n = b\_0 { Y\_0} ^ 2 {Y\_1} ^ 2 \ cdots {Y\_ {n-1}} ^ 2 se acerca a 1, luego y\_n = {Y\_0} {Y\_1} \ cdots {Y\_ {n-1}} se acercará a \ frac {1} {\ sqrt {b\_0}} y x\_n = b\_0 {Y\_0} {Y\_1} \ cdots {Y\_ {n-1}} se acercarán a \ sqrt {b\_0}.
La serie que usamos es esencialmente la Paso de actualización de Newton-Raphson:
\ begin {align *} b\_i & = b\_ {i-1} {Y\_ {i-1}} ^ 2 \\ Y\_i & = \ frac {1} {2 } (3 – b\_i) \ end {align *}
Y luego podemos realizar un seguimiento de la raíz cuadrada:
\ begin {align *} x\_0 & = n Y\_0 \\ x\_ {i} & = x\_ {i-1} Y\_i \ end {align *}
Y la raíz cuadrada recíproca:
\ begin {align *} y\_0 & = Y\_0 \\ y\_ {i} & = y\_ {i-1} Y\_i \ end {align *}
Pero si hacemos un seguimiento de x\_i y y\_i, observe que b\_i = x\_ {i-1} y\_ {i-1}. Por lo tanto, nunca tenemos que realizar un seguimiento de b\_i:
\ begin {align *} Y\_i & = \ frac {1} {2} \ left (3 – b\_i \ right) \\ & = 1 + \ frac {1} {2} \ left (1 – b\_i \ right) \\ & = 1 + \ frac {1} {2} \ left (1 – x\_ {i-1} y\_ {i-1} \ right ) \ end {align *}
Y ahora, tampoco necesitamos realizar un seguimiento de Y\_i:
\ begin {align *} x\_i & = x\_ {i-1} \ izquierda (1 + \ frac {1} {2} \ izquierda (1 – x\_ {i-1} y\_ {i-1} \ derecha) \ derecha) \\ & = x\_ {i-1} + x\_ {i- 1} \ frac {1} {2} \ left (1 – x\_ {i-1} y\_ {i-1} \ right) \\ y\_i & = y\_ {i-1} \ left (1 + \ frac {1 } {2} \ left (1 – x\_ {i-1} y\_ {i-1} \ right) \ right) \\ & = y\_ {i-1} + y\_ {i-1} \ frac {1} { 2} \ left (1 – x\_ {i-1} y\_ {i-1} \ right) \ end {align *}
Aquí hay algunos cálculos redundantes, que podemos eliminar, lo que sugiere lo siguiente algoritmo. Dado Y como una aproximación a \ frac {1} {\ sqrt {n}}, establezca:
\ begin {align *} x\_0 & = n Y \\ y\_0 & = Y \ end {align * }
Luego repite:
\ begin {align *} r\_i & = \ frac {1} {2} \ left (1 – x\_i y\_i \ right) \\ x\_ {i +1} & = x\_i + x\_i r\_i \\ y\_ {i + 1} & = y\_i + y\_i r\_i \ end {align *}
Aunque la división por dos es barata, también podemos evitarlo realizando un seguimiento de h\_i = \ frac {1} {2} y\_i en lugar de y\_i. Este es el algoritmo de Goldschmidt.
Suponga que Y es una aproximación a \ frac {1} {\ sqrt {n}}. Establecer:
\ begin {align *} x\_0 & = n Y \\ h\_0 & = \ frac {Y} {2} \ end {align *}
Luego, iterar:
\ begin {align *} r\_i & = \ frac {1} {2} – x\_i h\_i \\ x\_ {i + 1} & = x\_i + x\_i r\_i \\ h\_ {i + 1} & = h\_i + h\_i r\_i \ end {align *}
Luego x\_i converge a \ sqrt {n} y h\_n converge a \ frac {1} {2 \ sqrt {n}}.
Implementando esto en hardware
Hasta ahora todo bien. Sin duda, es un algoritmo muy simple. Pero, ¿por qué es mejor?
Las CPU modernas a menudo tienen un circuito rápido que realiza una operación de acumulación múltiple optimizada, a menudo llamada multiplicación fusionada. agregar, o FMA para abreviar. Si buscó antes la referencia a los árboles de Wallace, debería tener claro cómo FMA podría ser casi tan eficiente como una operación de multiplicación directa.
FMA es una de las primitivas más útiles que existen. Si necesita evaluar un polinomio, por ejemplo:
p (x) = a\_0 + a\_1 x + a\_2 x ^ 2 + \ cdots a\_n x ^ n
puede usar el método de Horner regla, que es esencialmente un grupo de FMA:
\ begin {align *} p\_ {n-1} & = a\_ {n-1} + x a\_n \\ p\_ {n-2} & = a\_ {n-2} + x p\_ {n-1} \\ & \ vdots \\ p\_1 & = a\_1 + x p\_2 \\ p\_0 & = a\_0 + x p\_1 \ end {align *}
El ciclo interno del algoritmo de Goldschmidt son tres FMA y nada más.Por eso es una ventaja: solo necesita un tipo de circuito (posiblemente solo un circuito; tenga en cuenta que los dos segundos FMA son independientes y, por lo tanto, pueden beneficiarse de la canalización) más alguna lógica de control para implementar todo. Y es un circuito que es útil en muchas otras operaciones, por lo que no está desperdiciando mucho hardware solo en la operación de raíz cuadrada.
La penúltima pieza del rompecabezas es cómo obtener una buena inicial estimación, y la respuesta corta es que el mejor método es utilizar una búsqueda de tabla. Incluso una tabla de tamaño modesto, porque solo buscamos raíces cuadradas en un rango tan pequeño, es bastante eficiente.
La última pieza del rompecabezas es: ¿Cómo sabemos cuándo hemos terminado? iterando? Y la respuesta a eso es que sabemos la precisión de los números que estamos usando y qué tan buena es la estimación inicial. A partir de ahí, podemos calcular el número máximo de iteraciones necesarias de antemano. Por lo tanto, no realizamos un bucle como tal, solo hacemos la iteración un número fijo de veces.