1. 《雷神之锤 III 竞技场》快速求平方根导数源代码

• 此处先列出其源代码，这段代码的目标是计算一个浮点数平方根的导数，也就是如下形式：$$f(x)=\frac{1}{\sqrt{x}}$$
• 这段代码可以说非常难以理解，尤其是 $0x5f3759df$ 更是莫名奇妙，不知所云。

float Q_rsqrt( float number )
{
    long i;
    float x2, y;
    const float threehalfs = 1.5F;

    x2 = number * 0.5F;
    y  = number;
    i  = * ( long * ) &y; // evil floating point bit level hacking
    i  = 0x5f3759df - ( i >> 1 );  // what the fuck? 
    y  = * ( float * ) &i;
    y  = y * ( threehalfs - ( x2 * y * y ) );  // 1st iteration 
    // 2nd iteration, this can be removed
    // y  = y * ( threehalfs - ( x2 * y * y ) ); 

    return y;
}

2. 前置知识

• IEEE754-浮点数的表示方法，可以参考我的另外一篇文章 《IEEE754 -浮点数的表示》。

3. 推导过程

3.1 第一步:对要计算的公式两边同时取 $log$

• 正本清源，我们要求的就是这样一公式$$\begin{gathered} y=\frac{1}{\sqrt{x}} \\ y=x^{-\frac{1}{2}} \end{gathered}$$

• 对等式两边同时取以2为底的对数

  不要问为什么取对数，取对数并不是目的，这只是一种 计算的技巧，在这里只需要知道等式两部同时取对数后仍然是相等的

  $$\begin{gathered} {\log }_2(y)={\log }_2(x^{-\frac{1}{2}}) \\ {\log }_2(y)=-\frac{1}{2}{\log }_2(x) \end{gathered}$$

3.2 第二部：计算出对浮点数取log的整数表达形式

• 将《IEEE754 -浮点数的表示》 中提到的浮点数表达式带入 第一步 所推导出的公式, 计算出对浮点数取$log$的整数表达形式

• 《IEEE754 -浮点数的表示》 提到浮点数的计算公式为：$$(-1{)}^S\ast (1+\frac{F}{2^{23}})\ast 2^{(E-127)}$$

• 不考虑符号位。对其取对数
  $${\log }_2\left(\left(1+\frac{\mathrm{F}}{2^{23}}\right)\ast 2^{\mathrm{E}-127}\right)$$

• 化简一步
  $${\log }_2\left(1+\frac{\mathrm{F}}{2^{23}}\right)+\mathrm{E}-127$$

• 推导到这一步似乎没办法化简了，我们知道 $\frac{F}{2^{23}}$ 是一个大于0，小于1的数，令$x=\frac{F}{2^{23}}$，我们画出 ${\log }_2(1+x)$的曲线图,在0 - 1的范围内近乎是一条直线，所以 ${\log }_2(1+x)\approx x$
  

• 加入误差修正(假设误差为$\mu$)，如下图修正0.045的效果看起来更好一点，所以 ${\log }_2(1+x)\approx x+\mu$

  此处的关键就是找到一个$\mu$, 使得总体误差最小，根据前人的计算 $\mu =0.0450465$左右，整体误差最小,

  

• 带入上面公式
  $$\begin{gathered} {\log }_2\left(1+\frac{\mathrm{F}}{2^{23}}\right)+\mathrm{E}-127 \\ \approx x+\mu +E-127 \\ \approx \frac{F}{2^{23}}+\mu +E-127 \\ \approx \frac{F}{2^{23}}+E+u-127 \\ \approx \frac{F}{2^{23}}+\frac{2^{23}E}{2^{23}}+u-127 \\ ------ \\ \approx \frac{1}{2^{23}}(F+2^{23}\ast E)+u-127 \end{gathered}$$

• 观察最终计算出的公式，红框中的部分就是 《IEEE754 -浮点数的表示》所提到的 浮点数二进制的整形表达形式
  

3.3 第三部：将 第二步 带入 第一步

• 化简一下公式
  $$\begin{gathered} lo{g}_2(y)=-\frac{1}{2}{\log }_2(x) \\ \frac{1}{2^{23}}({\mathrm{F}}_y+2^{23}\ast {\mathrm{E}}_y)+\mu -127=-\frac{1}{2}\left(\frac{1}{2^{23}}({\mathrm{F}}_x+2^{23}\ast {\mathrm{E}}_x)+\mu -127\right) \\ ------ \\ ({\mathrm{F}}_y+2^{23}\ast {\mathrm{E}}_y)=\frac{3}{2}\ast 2^{23}(127-\mu )-\frac{1}{2}({\mathrm{F}}_x+2^{23}\ast {\mathrm{E}}_x) \end{gathered}$$
• 结果已经呼之欲出了，如下图所示,红框代表的是$y$的二进制值， 蓝框代表的是$x$的二进制值。
  

$$\begin{gathered} y_{二进制}=\frac{3}{2}\ast 2^{23}(127-\mu )-\frac{1}{2}(x_{二进制}) \\ 令\mu =0.0450465679168701171875（这其实是根据魔数0x5f3759df反推出来的），使误差最小 \\ ---- \\ {y}_{二进制}=0x5f3759df-\frac{1}{2}(x_{二进制}) \end{gathered}$$

4.最后在使用牛顿迭代法再次逼近一次结果，提高精度

• 经过上面推导，已经求出来一个值了，这个值存在一定的误差，如果接受不了这个误差，就可以使用牛顿求根法进行一次或多次逼近以提高精度，如果能够接受这种误差便可以结束了

4.1 认识牛顿迭代

• 牛顿迭代法的核心如下图所示，通俗点来讲就是通过已知点，不断逼近$f(x)=0$的点
  

• 通用公式如下，很好理解：$$x_{n+1}=x_n-\frac{f(x_n)}{f’(x_n)}$$

  以$x_0$到$x_1$为例，通过$y_1$除以斜率计算出$x_0-x_1$ 之间的距离，斜率就是在$y_0$ 这个点上求导

4.2 对$y=\frac{1}{\sqrt{x}}$进行牛顿迭代

• 两边同时求平方进行一步变换，目的是消除根号
  $$\begin{gathered} y=\frac{1}{\sqrt{x}} \\ {y}^2=\frac{1}{x} \end{gathered}$$
• 两边同时取倒数，目的是将方程转换为以 $y$ 为变量的表达式$$\frac{1}{y^2}=x$$
• 整理一下,得到$f(x)=0$ 的形式：$$\frac{1}{y^2}-x=0$$
• 回想一下我们的目标,$x$ 是我们要开计算平方根导数的值，$y$是要计算的结果,我们之前已经计算出了一个不太精确的$y$,现在的目标就是通过这个不太精确的$y$逼近下一个点，
• 带入牛顿迭代法的通用公式$$\begin{gathered} f(y)=\frac{1}{y^2}-x \\ {f}^{\prime }(y)=\frac{-2}{y^3} \\ ----------- \\ {y}_{n+1}=y_n-\frac{f(y_n)}{f^{\prime }(y_n)} \\ ----------- \\ {y}_{n+1}=y_n-\frac{\frac{1}{y_n^2}-x}{\frac{-2}{y_n^3}} \\ {y}_{n+1}=\frac{y_n(3-x{y}_n^2)}{2} \\ --------------------------------- \\ {y}_{n+1}=y_n(1.5-0.5x{y}_n^2) \end{gathered}$$
  
• 至此，公式与代码都对上了

5. 代码讲解