传奇的快速逆平方根

在90年代，3D电子游戏还处于起步阶段，渲染3D图形的能力受到硬件的限制。 这导致程序员设计出创造性的方法来解决硬件限制。 1999年，id Software的第一人称射击游戏Quake III Arena中引入了一种这样的创新，即快速逆平方根函数。

平方根倒数在视频游戏图形中特别是在3D游戏引擎中很有用。 寻路，照明，反射和许多其他游戏编程技术都需要向量归一化，这涉及平方根的倒数运算。 平方根的倒数依赖于浮点除法，对于处理器而言很昂贵。 在像Quake III Arena这样的节奏快，图形强度大的游戏中，这些计算每秒进行数百万次，因此，即使这种计算性能稍有提高，也可以显着提高图形计算速度，并最终提高游戏的帧速率。 那么id Tech 3引擎的程序员如何解决昂贵的反平方根函数呢？ 他们实现了非常准确，非常快速的近似。

• 为什么Playdead的内幕是我多年来玩过的最好的电子游戏。
• 为什么我对玩游戏不感到内gui
• 是否将随机战利品箱视为赌博？ –布赖恩·赖特
• 我为什么喜欢Docker：Minecraft的用例
• 快速PAX AUS 2016狂欢

这就是荣耀：Quake III Arena的快速反平方根源代码！ C预处理程序指令已被删除，但是代码和注释与Quake引擎中显示的相同。

 浮点数Q_rsqrt（浮点数）
 {
    我长
    浮点数x2，y;
     const float threehalfs = 1.5F;

     x2 =数字* 0.5F;
     y =数字；
     i = *（long *）＆y;  //邪恶的浮点位级别黑客
     i = 0x5f3759df-（i >> 1）;  //他妈的是什么？
     y = *（float *）＆i;
     y = y *（Threehalfs-（x2 * y * y））;  //第一次迭代
 // y = y *（threehalfs-（x2 * y * y））;  //第二次迭代 
                                                //可以删除

     返回 y；
 } 

好吧…这太荒谬了。 伏都教黑魔法无非是，但让我尝试解释一下。 这种近似的总体思路实质上是牛顿-拉夫森迭代。 Newton-Raphson求根方法的工作方式如下：给定数字根c的近似值，使用y = c/2 * (3 — xc²)可以找到更好的近似值。 快速平方根反函数从一个真正聪明的第一个猜测开始实现一个Newton-Raphson迭代。

让我们仔细看看它是如何工作的：

y = number;
在C语言中，单精度浮点数作为32位数字存储在内存中。 第31位表示符号，第30–23位表示8位指数，而第22–0位表示23位尾数—左数为小数的二进制数。

i = * ( long * ) &y;
相同的32位数字也可以解释为整数，其中最高有效位存储符号。

( i >> 1 );
向右移一位将插入0作为最高有效位，并删除数字的最低有效位。 这有效地将数字的整数解释除以2。但是，如果将相同的数字解释为浮点数，则更改要比除以2更为剧烈。按位移位会将指数取反并将其除以2，则将a移位从指数到尾数位，然后掉下尾数的最低有效位。

i = 0x5f3759df — ( i >> 1 );
克里斯·洛蒙（Chris Lomont）在他的论文中解释说，在Quake III Arena的快速反平方中使用的初始猜测是“分段线性的，在所有情况下近似函数都不相同。”将数字的位右移一位时，两种可能的情况：数字的指数是偶数还是奇数。 选择魔术十六进制数0x5f3759df，以使这两种情况之间的误差最小。 因此，无论移位后的数字是奇数还是偶数，从幻数中减去该数字都会得出原始数字的平方根的倒数的精确近似值（一旦将结果i重新解释为浮点数）。

y = * ( float * ) &i;
此时， i作为整数存储在内存中。 该函数重新解释i并将结果作为浮点数存储在内存中。 此数字是输入值的平方根的倒数的相对准确的初始猜测。

y = y * ( threehalfs — ( x2 * y * y ) );
执行一次Newton-Raphson迭代以计算输入的反平方根的更精确近似值。 Newton-Raphson迭代的结果是函数的返回值。 结果非常准确，最大误差为0.175％。

这段代码的真正天才是：

  i = 0x5f3759df-（i >> 1）; 

如我之前所说，巫毒黑魔法。 它从哪里来的？ 地球上谁想到了这样的法术？

快速逆平方根有一个有趣的历史。 直到2006年，即游戏发布7年后，以及最初编写代码的大约20年后，才公布了原始作者。 AMD RTG欧洲游戏工程团队的高级经理Rys Sommerfeldt于2004年对该功能的起源进行了调查。他开始与Quake III的首席程序员John Carmack进行搜索，他否认了作者身份，并建议使用该功能的大师Terje Mathisen。 x86汇编程序设计人员，帮助优化了Quake III引擎。

Sommerfeldt与Mathisen取得了联系，他回答说，事实上，他早在5年前就编写了平方根逆函数，但是Quake快速平方根逆函数不是他所写的。 他建议看起来像是麻省理工学院的HAKMEM文档中提供的东西。

Sommerfeldt的更多调查工作使他与NVIDIA取得联系，建议他向NVIDIA的雇员，3dfx的创始成员Gary Tarolli询问。 索默费尔特给加里（Gary）发了电子邮件，加里（Gary）回答说，该功能肯定是通过键盘多次传递的。 加里说，他在IRIS Indigo工作站计算机上的工作中模拟了不同的十六进制常数，但他不是原始作者。 在没有其他线索的情况下，调查处于休眠状态约一年。

当Sommerfeldt撰写的文章广为宣传时，它最终成为Fast Inverse Square Root Root Function的原始作者Greg Walsh的眼球！ * 掌声雷动 * Greg Walsh是计算机世界的丰碑。 他帮助Xerox PARC设计了第一个所见即所得（“所见即所得”）文字处理器，并帮助创立了Ardent Computer。 格雷格（Greg）与Matlab的作者克莱夫·莫勒（Cleve Moler）紧密合作，而在Ardent任职的正是格雷夫·克莱夫（Greg），他提出了快速逆平方根函数的灵感。