著名的快速反平方根是一些神秘的代码，不是由编程传奇人物John Carmack编写的，用于计算$1/\sqrt{x}$的快速近似值：
//来自地震3竞技场的代码。Float q_rsqrt(Float Number){long i；Float x2，y；Const Float Three Halfs=1.5F；x2=number*0.5F；y=number；i=*(long*)&；y//邪恶的浮点位级黑客攻击i=0x5f3759df-(i&>；&>1)；//他妈的是什么？Y=*(浮点*)&；i y=y*(Three Halfs-(x2*y*y))；//第一次迭代//y=y*(Three Halfs-(x2*y*y))；//第二次迭代，返回y；}。
游戏总是计算平方根和反平方根，以找到向量的长度并将其归一化，但是使用sqrt()函数可能非常慢。上面的代码通过一些整数魔术更快地找到近似结果。我很好奇它是如何工作的，但维基百科上描述它的页面写得太糟糕了，所以更容易从头开始弄清楚。这是我找到的东西。
代码的工作方式是计算$1/\sqrt{x}$(也可以写为$x^{-1/2}$)的初始近似值，然后使用牛顿-拉夫森方法的一次或两次迭代进行优化。如果你不熟悉牛顿-拉夫森方法，别担心--它不是很复杂，也不是很聪明，所以如果你愿意，你可以忽略它。网络上有一大堆很好的视觉解释(比如这个)，所以我就不在这里赘述了。
该方法的核心是浮点数的位操作，因此我们需要知道它们是如何工作的。但是，使用一种没有人使用的奇怪的数字格式来解释这种方法会更简单。
我们可以用高位表示符号(0表示正数，1表示负数)，其余位表示正实数。使用专用位来表示符号称为符号和幅度。因为我们不能取负数的平方根，所以我们可以假设符号位始终为0。
我们可以将接下来的8位解释为值的整数部分，其余的位是小数部分。在本例中，值是二进制的10001010.0100001(我们可以去掉尾随的零，就像十进制数一样)。这相当于十进制值$138.2578125。$我们可以使用这个值，我将它表示为$f$，以几种不同的方式表示数字。如果我们将31位值视为无符号整数$u$(即$u=\mathrm{0b01000101001000010000000000000000}=1159790592$)，则。
$$f=\frac{u}{2^{23}}$$我们可以只设置$x=f$，即我们认为01000101 00100001 00000000 00000000代表数字$138.2578125。$此格式称为固定点，因为小数点始终固定在同一位置。它有一些特殊用途，但并不常用，因为它的主要弱点是：它可以表示的值范围非常有限：在本例中，最多只能有128.9999999个值。
我们可以通过对不动点取幂来增加我们可以表示的值的范围，即$f=2^{x-127}$。所以，不考虑01000101 00100001 00000000 00000000来表示$138.2578125，我们说它表示数字$2^{138.2578125-00000000}=2448.7，这被称为对数系统(Lns)。使用$^{-127}$偏移量，以便我们可以表示小于$1的数字。$现在我们可以表示最大值为$2^{128.9999999}的数字。$虽然我们确实失去了一些很好的属性，但最关键的是很难使用此数字系统实现加法和减法。
为了使加法和减法更容易实现，我们可以区别对待$f$的整数部分和小数部分，让我们称它们为$f_e$和$f_m$。我们用$x=2^{f_e-127}\x(1+f_m)$使整数部分对数，小数部分线性。在我们的例子中，$2^{138-127}\乘以1.2578125=2576。$这意味着$2$的指数总是整数，这是计算机很容易处理的。这种格式被称为浮点，因为小数点是浮动的(不用担心)。几乎所有的代码都使用这种实数格式，并且几乎所有的处理器都有对它的硬件支持。这也是C中的实数是浮点数的原因。
总而言之，相同的位模式可能意味着三个不同的数字，具体取决于我们使用的数字格式：
如果我们使用LNS数，我们不需要技巧来计算平方根的倒数-我们可以很容易地精确地计算它。回想一下，无符号整数$u$的LNS解释为。
$$2^{u/2^{23}-127}$(2^x)^{-1/2}=2^{-x/2}$$因此要找到将给出反平方根的无符号整数$q$，我们需要求解。
$$2^{q/2^{23}-127}=2^{-(u/2^{23}-127)/2}$q/2^{23}-127=-(u/2^{23}-127)/2$q/2^{23}-127=-(u/2^{23})/2+127/2$q/2^{23}=190.5-(u/2^{23})/2$q=190.5\x 2^{23}-u/2$$。并使用位移位除以2。
看起来眼熟吗？这与我们之前看到的神秘路线非常接近！但是，我想你会问，这是给这些奇怪的LNS号码的！。实际的浮点数是多少？"；
上面的公式计算LNS数的精确反平方根。诀窍在于浮点数实际上与LNS数非常相似！它们的差异永远不会超过$\frac{2}{e\log2}=1.0615的因子。$下图显示了重新解释为浮点数时的lns编号的值。换句话说，当我们获取LNS数的位模式，并计算出如果这些位是浮点数，它们代表什么值时，我们得到的值。如你所见，他们非常接近！
查看LNS和浮点之间差异的另一种方法是改变$f$，并绘制LNS和浮点结果。
您可以看到LNS是如何在2的整数幂之间完全对数的，但是浮点在这些点之间是线性的。所有这些都只是说LNS和浮点数非常相似，所以LNS数的精确平方根倒数仍然非常接近浮点数的平方根倒数！但是为什么代码使用0x5f3759df而不是0x5F400000呢？
我们有一个计算，用LNS数给出一个精确的结果，用浮点数给出一个近似的结果。这个近似值有多好？对于不同的输入，我们可以画出近似输出与正确输出的比率。使用对数刻度，这样以恒定因子(例如$\x 2$或$\div 2$)计算出来的结果看起来是一样的。绿线表示初始近似后的结果，蓝线表示牛顿-拉夫森迭代一次后的结果。越接近1(红线)越好。
使用$190.5$(0x5F400000)的减法(我刚刚编造的一个词)，您可以看到初始近似值总是太高(绿线在红线之上)。这是因为浮点数始终大于相应的LNS数。估计约为1元至1.09元，是实际答案的1倍。如果我们可以将输出乘以大约$0.96$的恒定因子，那么我们就可以平衡$1$上下的误差，这将减少最大误差。
这很容易做到，只需将减法剂减去少量即可。我可以详细介绍一下，但是您可以通过在上面滑动滑块很容易地看到效果。看看你能犯的最大错误有多小，然后单击Carmack按钮查看Quake 3使用的值。
这是相当接近最佳的！但是..。也许有一种方法我们可以做得更好。请注意，牛顿-拉夫森迭代一次后的输出总是太小(蓝线在红线下方)。有没有办法把它乘以略高于1美元的某个常数因子？是!。我们所要做的就是稍微修改一下原始代码中的0.5。试着玩一下这个“半边”滑块。事实上，当我们还在做这件事的时候，如果我们也改变代码中的1.5，并将整个代码输入到我编写的一个拼凑在一起的优化程序中，会发生什么呢？我们可以做得更好一点！单击额外的按钮，查看允许更改两个或三个参数时的优化结果。
基本上就是这样。总而言之，使用LNS数字，我们可以使用0x5F400000计算出精确的解。LNS数与浮点数非常接近，因此相同的代码给出了浮点数的近似解决方案。但是浮点数总是大于LNS数，所以近似中存在偏差，可以通过从0x5F400000中减去少量来纠正。
如果有什么不清楚或我弄错了，请告诉我。继续往下看，我假装你已经问了几个额外问题的答案。
是!。我开始这样做，但是因为误差曲线有3到4个部分，所以很快就变得非常单调乏味。数值优化要容易得多。
$$q=190.5-\frac{u}{2}$q=\frac{381-u}{2}$x^{\pm 2^n}$$其中$n$是整数(正数或负数)。例如，$x^{1/2}$，$x^{-8}$，$x^2$，尽管您可能不会将其用于正指数，因为您可以只使用乘法来获得准确的答案。
它可以用来做立方根之类的东西吗？也许吧。我们需要解决的问题是：
$$2^{q/2^{23}-127}=2^{(u/2^{23}-127)/3}$q/2^{23}-127=\frac{u/2^{23}-127}{3}$q/2^{23}=\frac{u/2^{23}-127}{3}+127$q=\frac{u}{3}+\frac{2\x 127}{3}*2^{23}=\frac{u}{3}+。\mathm{0x2A555555}$$因此我们的(未优化；读者练习)魔术线条将如下所示(未经过测试！)。
整数除法不如位移位快，但是因为我们除以常数，所以大多数编译器能够将其优化为乘法和位移位。怎么做到的？你问吗？让我查一下维基百科。