一个 文章 和 研究论文 描述一种快速、看似神奇的方法来计算反平方根($1/\sqrt{x}$)，用于游戏《雷神之锤》中。
我不是图形专家，但理解平方根为何有用。 勾股定理 计算两点之间的距离，除以距离有助于归一化向量。（归一化通常只是除法的花哨说法。）
像《雷神之锤》这样的3D游戏每秒进行无数次（没错，无数次）距离除法，因此即使是“微小”的性能提升也能带来巨大帮助。我们不想用常规方式计算平方根和除法：指数运算和除法的成本非常高。 CPU
基于这些条件，以下是《雷神之锤》中用于计算$1/\sqrt{x}$的神奇公式（我添加了注释）：
float InvSqrt(float x){
float xhalf = 0.5f * x;
int i = *(int*)&x // store floating-point bits in integer
i = 0x5f3759df - (i >> 1); // initial guess for Newton's method
x = *(float*)&i // convert new bits into float
x = x*(1.5f - xhalf*x*x); // One round of Newton's method
return x;
}
哇！不知怎的，这段代码仅用 乘法 和 位移位操作就得到了$1/\sqrt{x}$。其中不涉及除法或指数——它是如何工作的？
我的理解： 这个不可思议的技巧 估计值 使用牛顿近似法求解反根，并从极佳的初始猜测开始。
为了进行猜测，它使用科学记数法表示的浮点数，对指数取反并减半，得到接近反平方根的值。然后执行一轮牛顿近似法来进一步细化估计值，最终得到接近反平方根的结果。
牛顿近似法
牛顿法可用于求任何函数的近似根。你可以不断迭代该方法以越来越接近根，但这个函数只用了1步！以下是牛顿法的速成课程（对我来说是新的）：
假设你有一个函数f(x)且你想求它的根（即f(x)=0的点）。将你的初始猜测称为“g”。牛顿法给出一种方法来获得新的、更好的根近似：
你可以重复这个过程（将新猜测代入公式）以获得更接近根的近似值。最终你会得到一个“新猜测”，使得f(新猜测)非常非常接近零——这就是一个根！（或者像人们说的，足够满足政府工作了）。
在我们的例子中，我们想要反平方函数。假设我们有一个数i（我们一开始只有这个，对吗？）并且想求反平方根：$1/\sqrt{i}$。如果我们猜测“x”是反根，那么原始数与我们猜测“x”之间的误差为：
这是因为x约等于$1/\sqrt{i}$。如果我们对x平方，得到$1/i$，再取倒数，应该得到接近i的值。如果我们减去这两个值，就能找到误差。
显然，我们希望误差尽可能小。这意味着找到使error(x)=0的“x”，这等价于找到误差方程的根。如果将error(x)代入牛顿近似公式：
并求适当的导数：
代入即可得到更好猜测的公式：
这正是上面代码中的方程，记住x是我们的新猜测（g），而“xhalf”是原始值的一半（$0.5 i$）：
x = x*(1.5f - xhalf*x*x);
利用这个公式，我们可以从一个猜测“g”开始，重复公式得到更好的猜测。试试这个演示，使用多次迭代来求反平方根：
在此演示中，我们首先猜测平方根是数字的一半：$\sqrt{n} \sim \frac{n}{2}$，这意味着 $\frac{1}{\sqrt{n}} \sim \frac{2}{n}$。运行几轮牛顿法(Newton's Method)会迅速收敛到真实结果。（尝试 n=2, 4, 10 等）
所以朋友们，问题变成了：“我们如何做出一个好的初始猜测？”
做出良好猜测
对于平方根的倒数(inverse square root)，什么是一个好的猜测？这有点像个陷阱问题——我们对平方根的倒数的最佳猜测就是平方根的倒数本身！
好吧，高手，你问，我们实际上如何得到 $1/\sqrt{x}$？
这就是魔法发生的地方。假设你有一个指数形式或科学记数法(scientific notation)的数字：
现在，如果你想求普通的平方根，你只需将指数除以2：
而如果你想要 逆 平方根，则将指数除以-2来翻转符号：
那么，我们如何在不进行其他昂贵操作的情况下得到一个数的指数呢？
浮点数以尾数-指数形式存储
好吧，我们很幸运。浮点数(Floating-point number)被计算机以尾数-指数(mantissa-exponent)形式存储，因此可以提取并除以指数！
但是，代码并没有显式地进行除法（对CPU来说代价高昂），而是使用了另一个巧妙的技巧：移位。右移一位等同于除以2（你可以尝试任何2的幂但会截断余数）。而如果你想得到一个负数，与其乘以-1（乘法代价高昂），不如从“0”中减去该数（减法代价低廉）。
因此，代码将浮点数转换为整数。然后将其位右移一位，这意味着指数位被除以2（当我们最终将这些位转换回浮点数时）。最后，为了取反指数，我们从魔数(Magic Number) 0x5f3759df 中减去它。这做了几件事：它保留了尾数（非指数部分，例如 $5 \cdot 10^6$ 中的5），处理奇偶指数，将位从指数 转化为 转移到尾数，以及各种奇特的操作。论文中有更多细节和解释，我第一次没有完全理解。一如既往，如果你对正在发生的事情有更好的解释，欢迎评论。
结果是我们得到了一个非常接近真实平方根倒数的初始猜测！然后我们可以进行一轮牛顿法来改进猜测。更多轮也是可能的（但会增加计算开销），但对于所需的精度，一轮就足够了。
那么，为什么是魔数？
这个伟大的技巧在于整数和浮点数的存储方式。像 $5.4 \cdot 10^6$ 这样的浮点数将其指数存储在与“5.4”不同的位范围内。当你对整个数字进行移位时，你既将指数除以2，也将数字（5.4）除以2。这就是魔数的用武之地——它对这个除法进行了一些很酷的修正，我不太理解。然而，有几个魔数可以使用——这个碰巧最小化了尾数的误差。
魔数也修正了奇偶指数； 这篇论文 提到你也可以找到其他魔数来使用。
资源
在reddit（用户pb_zeppelin）和slashdot上有进一步的讨论：
- http://programming.reddit.com/info/t9zb/comments
- http://games.slashdot.org/article.pl?sid=06/12/01/184205 和 我的评论