Truco rápido inversa de raíz cuadrada

Question

He encontrado lo que parece ser un interesante método para el cálculo de $$\frac{1}{\sqrt x}$$ extremadamente rápido en este sitio web, con más explicación aquí.

Sin embargo, el equipo de ciencia-lingo y "flotante"-materias me dejó en la oscuridad en cuanto a cómo funciona. Yo en realidad no sé lo que el algoritmo es porque no puedo leer el código C, así que es posible que alguien

1. Explicar el algoritmo en términos matemáticos
2. Explicar por qué funciona

(Tengo la impresión de que está utilizando el método de Newton con una inteligente elección de primera conjetura.)

---

Para la comodidad de los lectores I (la Cadena del usuario), me permití incluir el código de C++:

float InvSqrt(float x)
      {
      float xhalf = 0.5f*x; // store 0.5x since x will be changed
      int i = *(int*)&x; // convert to binary integer
      i = 0x5f3759df - (i>>1); // the smart trick
      x = *(float*)&i; // convert binary back to decimal
      x = x*(1.5f-xhalf*x*x); // Newton-Raphson step
      return x;
      }

Answer 1

Primero de todo, la descripción del objetivo general de que el algoritmo es correcto! De hecho, ES el de Newton-Raphson el método con un inteligente estimación inicial. Sólo voy a comentar llegar a la inteligente adivinar.

La conversión a binario

Tratando de frase en la mayoría de los términos matemáticos, el equipo toma un número decimal $x\in[1\cdot 2^{-127},2\cdot 2^{128})$ y calcula un modelo lineal por tramos de aproximación a la base de $2$ logaritmo encontrando $q\in[0,1)$ y un entero $e\in[-127,128]$ tal que $$ x=(1+q)\cdot 2^e $$ Esta expresión depende linealmente de $q$ y de manera exponencial en $e$ y tenemos la aproximación lineal por tramos $$ \log_2(x)\aprox e+q=\underbrace{\lfloor \log_2(x)\rfloor}_e+\underbrace{x/2^{\lfloor \log_2(x)\rfloor}-1}_q $$ Aquí está un diagrama de la situación con $\log_2(x)$ como la curva azul y $e+q$ como el rojo polígono:

Para almacenar esta información, el equipo se transforma en un entero positivo $$ i=\lfloor(e+127+q)\cdot 2^{23}\rfloor $$ donde la parte entera de la $(e+127+q)$ es de la no-negativo $(e+127)\in[0,255]$. Tenga en cuenta que el piso de la función que se utiliza aquí, que es esencialmente de truncar el número de $(1+q)$ después $23$ dígitos binarios de $q$, conduce a una pérdida de precisión en la mayoría de las $2^{-23}\approx 0.000000119$. Esto no es mucho, y vamos a ignorar que en el siguiente para una mejor representación.

Dígito binario cambio

El código de $\texttt{(i>>1)}$ toma el entero $\texttt{i}$ y los desplazamientos de sus dígitos binarios a la derecha, dejando caer el último dígito. Así que con $\texttt{i=1010}$ o $\texttt{i=1011}$ tenemos $\texttt{(i>>1)=101}$. En efecto, nos han $$ \texttt{(i>>1)}=\lfloor i/2\rfloor $$ De nuevo la función del suelo tiene un efecto relativamente pequeño así que haremos caso omiso de ella.

La "magia" número

Usted puede consultar con Wolfram Alpha que reconociendo $\texttt{0x5f3759df}$ como hexadecimal tenemos $$ \begin{align} \texttt{0x5f3759df}&=1597463007 \\ &= 190.43243014812469482421875\cdot 2^{23} \end{align} $$ Por razones de brevedad que nos acaba de escribir $190.43243$. Así, el código de la línea de $\texttt{i=0x5f3759df-(i>>1)}$ cambios $i$ con el nuevo valor $$ \begin{align} i_*&= 190.43243\cdot 2^{23}-i/2 \\ &=[190.43243-(e+127+q)/2]\cdot 2^{23} \\ &=[126.93243-(e+q)/2]\cdot 2^{23} \\ &\approx(127+\log_2(1/\sqrt x))\cdot 2^{23} \end{align} $$ Así, cuando el número entero $i_*$ arriba se transforma hacia atrás a través de la aproximación lineal a trozos en un número decimal tenemos $$ \begin{align} x_*&=\left(1+\text{frac}(126.93243-(e+q)/2)\right)\cdot 2^{\lfloor 126.93243-(e+q)/2\rfloor-127}\\ &\approx [1+\text{frac}(126.93243+log_2(1/\sqrt x))]\cdot 2^{\lfloor\log_2(1/\sqrt x)\rfloor} \\ &\approx 2^{\log_2(1/\sqrt x)} \\ &=1/\sqrt x \end{align} $$

¿Por qué no 190.5?

Esto es simplemente para equilibrar la función de error de la expresión anterior para minimizar los errores. Con 190.5 tendríamos $127$ en lugar de $126.93243$, pero debido a las aproximaciones lineales involucrada, esto daría lugar a desequilibrios en los errores de manera que algunos de los números de $x$ daría lugar a una casi perfecta $x_*=1/\sqrt x$, mientras que en otros números de $x$ trabajo relativamente mal en comparación con eso. Cambio por $190.5-190.43243=0.06757$ apparantly hace el truco de equilibrio de errores mejor.

En tanto que el artículo que enlaza a y en una más reciente artículo por otro autor, se han realizado algunos trabajos derivados mejoras constantes de $190.43243$. No he leído cuidadosamente las secciones acerca de que en cualquiera de los artículos, aunque.

Espero que esto aclara el principio general de que el algoritmo sin entrar en demasiado grande ni demasiado pequeño detalle en cuanto al objetivo de tu pregunta.