理解《雷神之锤》的快速平方根-更好的解释

一个文章而且研究论文描述了一种在《雷神之锤》中使用的快速且看似神奇的方法去计算反平方根($1/\√{x}$)。

我不是图形专家，但我理解为什么平方根是有用的。的勾股定理计算点之间的距离，除以距离有助于规范化向量。(正常化通常只是除法的一个花哨术语。)

像《雷神之锤》这样的3D游戏每秒都要除以无数次的距离，所以“微小的”性能改进具有巨大的帮助。我们不想取平方根，然后用常规的方法除法取幂和除法是非常非常昂贵的CPU。

在这些条件下，以下是获得$1/\sqrt{x}$的神奇公式，就像在Quake中发现的那样(我的评论插入):

float InvSqrt(float x){float xhalf = 0.5f * x;I = *(Int *)&x;//存储整数I = 0x5f3759df - (I >> 1);//牛顿方法的初始猜想x = *(float*)&i;//将新位转换为float x = x*(1.5f - xhalf*x*x);//牛顿方法返回x;｝

Yowza !以某种方式，这段代码只使用$1/\sqrt{x}$乘法而且移位操作．不涉及除法或指数——它是如何工作的?

我的理解:这个不可思议的黑客估计用牛顿近似法求逆根，并从一个很好的初始猜想开始。

为了进行猜测，它使用科学计数法中的浮点数，并对指数求负&二分之一，以得到接近根号倒数的值。然后它运行了一轮牛顿近似法来进一步完善估计，然后，我们得到了接近平方根倒数的东西。

牛顿近似法

牛顿法可以用来求任何函数的近似根。您可以不断迭代该方法以越来越接近根，但是这个函数只使用了1步!下面是一个关于牛顿方法的速成班(对我来说是新的):

假设你有一个函数f(x)，你想找到它的根(也就是f(x) = 0的地方)，让我们把你最初的猜测称为“g”。牛顿法给了你一种方法来得到一个新的，更好的根的猜测:

$文本\ displaystyle{\{新猜}= g - \压裂{f (g)} {f (g)}}$

你可以不断重复这个过程(把你的新猜想代入公式中)，得到更接近根的值。最终你得到了一个“新猜测”，使得f(新猜测)非常非常接近于零——它是一个根!(或者像他们说的，足够接近政府工作)。

在我们的例子中，我们想要平方反比函数。假设我们有一个数字$i$(这是我们开始的全部，对吧?)，并且想要找到反平方根:$1/\√{i}$。如果我们将猜测的“x”作为倒数根，那么原始数字和猜测的“x”之间的误差是:

$\ displaystyle{{错误}(x) = \ \文本压裂{1}{x ^ 2} -我}$

这是因为x大约是$1/\√{i}$。对x求平方得到$1/i$，求倒数得到$i$。如果我们把这两个值相减，就能求出误差。

显然，我们希望误差尽可能小。这意味着找到使误差(x) = 0的“x”，这与找到误差方程的根是一样的。如果我们把误差(x)代入牛顿近似公式:

$\ displaystyle {{newguess} = g - \ \文本压裂{\文本{错误}(g)}{{错误}\文本”(g)}}$

然后求导:

$\displaystyle{\text{error}(g)= g^{-2} - i}$

$文本\ displaystyle{\{错误}' (g) = 2 g ^ {3}}$

我们可以把它们代入，得到更好的猜测公式:

$\ displaystyle {{newguess} = g - \ \文本压裂{g ^{2} -我}{2 g ^ {3}}}$

$\displaystyle{\text{newguess} = g - (-0.5g + 0.5g ^3)}$

$\displaystyle{\text{newguess} = 1.5g - 0.5 g^3}$

$\displaystyle{\text{newguess} = g (1.5 - 0.5 g^2)}$

这正是你在上面的代码中看到的方程，记住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}$。运行几轮牛顿法很快就会收敛到真实的结果。(试一下n= 2,4,10，等等)

所以我的朋友们，问题就变成了:“我们如何做出一个好的初步猜测?”

猜得准

平方根的倒数是多少呢?这是一个有点棘手的问题——我们对平方根倒数的最佳猜测是平方根倒数本身!

好吧，高手，你会问，我们如何得到$1/\√{x}$?

这就是魔法发挥作用的地方。假设你有一个指数形式的数字或科学记数法:

$\displaystyle{10^6 = \text{100万}}$

现在，如果你想求普通的平方根，你只需要把指数除以2:

$\ displaystyle {\ sqrt{10 ^ 6} = 10 ^{\压裂{6}{2}}= 10 ^ 3 = 1000}$

如果你想要逆平方根，指数除以-2，翻转符号:

$\ displaystyle{\压裂{1}{\ sqrt{10 ^ 6}} = 10 ^{\压裂{6}{2}}= 10 ^{3}= \压裂{1}{1000}}$

那么，我们怎样才能得到一个数的指数而不需要其他昂贵的运算呢?

浮点数以尾数指数形式存储

嗯，我们很幸运。浮点数是由计算机以尾数指数形式存储的，因此可以提取和除指数!

但是代码没有显式地做除法(对CPU来说代价很高)，而是使用了另一种聪明的方法:移位位。右移一个位置等同于除以二(你可以试着取2的任意次方，但它将截断其余部分)。如果你想得到一个负数，而不是乘以-1(乘法很昂贵)，只需从“0”减去这个数字(减法很便宜)。

因此，代码将浮点数转换为整数。然后它将位移位1，这意味着指数位除以2(当我们最终将位转换回浮点数时)。最后，为了求指数的负数，我们从神奇的数字0x5f3759df中减去。这做了几件事:它保留尾数(非指数部分，又名5 in: $5 \cdot 10^6$)，处理奇数-偶数指数，从指数移动位成尾音，还有各种古怪的东西。这篇论文有更多的细节和解释，我第一次没有完全理解。一如既往，如果你对正在发生的事情有更好的解释，欢迎发表评论。

结果是，我们得到了一个最初的猜测，它非常接近于真正的平方根倒数!然后，我们可以用牛顿的方法做一轮来完善猜想。更多的轮是可能的(在额外的计算成本)，但一个轮是所需的精度。

那么，为什么是这个神奇的数字呢?

伟大的黑客是如何存储整数和浮点数。像$5.4 \cdot 10^6$这样的浮点数将它们的指数存储在一个不同于“5.4”的比特范围内。当你移位整个数字时，你将指数除以2，以及将数字(5.4)除以2。这就是神奇数字出现的地方——它对这个除法做了一些很酷的修正，我不太理解。然而，有几个神奇的数字可以使用——这个恰好可以最小化尾数的错误。

这个神奇的数字还可以校正偶数/奇数指数;这篇论文提到你还可以找到其他神奇的数字来使用。

资源

reddit(用户pb_zeppelin)和slashdot上有进一步的讨论:

理解《雷神之锤》的快速平方根

牛顿近似法

猜得准

浮点数以尾数指数形式存储

那么，为什么是这个神奇的数字呢?

资源

本系列的其他文章

加入45万每月读者