快速平方根倒数算法：《雷神之锤3》中的传奇代码

快速平方根倒数算法：《雷神之锤3》中的传奇代码

引用

CSDN

1.

https://blog.csdn.net/weixin_45473792/article/details/140531075

快速平方根倒数算法是游戏开发中一个非常经典的算法，最早出现在id Software的《雷神之锤3》源代码中。该算法通过一系列巧妙的数学变换和位操作，实现了对平方根倒数的快速近似计算，其速度是传统方法的三倍。本文将深入解析这个算法的原理和实现细节。

算法核心思想提炼：

1. 求根号转化为求对数。
2. 用直线近似对数曲线。
3. 找到浮点数二进制表示和其对数之间的关系。
4. 利用3找的关系对浮点数进行线性运算即可得到结果的近似值。
5. 使用牛顿迭代法优化近似值，减小误差。

背景介绍:

2005年，id公司发布了《雷神之锤3：竞技场》的源代码，在源代码中，游戏粉丝们找到了一个算法，十分巧妙，很快出名了，该算法的唯一用途是计算平方根的倒数

以下是算法源代码：

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 hack
    i  = 0x5f3759df - ( i >> 1 );              // what the fuck?
    y  = * ( float * ) &i;
    y  = y * ( threehalfs - ( x2 * y * y ) );  // 1st iteration 
 // y  = y * ( threehalfs - ( x2 * y * y ) );  // 2nd iteration, can be removed
    return y;
}  

为什么游戏引擎要计算平方根的倒数呢？要在游戏引擎内实现物理效果，光影或反射效果的话，要先对向量进行单位化，因而我们需要计算平方根的倒数。要不然的话，向量会过短或过长，若在此基础上处理物理效果的话，会出错的。
他们一开始忘了normalize速度向量，结果造就了游戏史上最传奇的身法之一。
众所周知，向量长度是
所以，如果你要将向量单位化（把向量长度缩放为1），要将向量的三个维度都按照模长缩放
或者类似地，乘以向量模长的倒数
计算
很简单，而且很快，写代码时，可以写成 : x * x + y * y + z * z，加法和乘法是计算机中的基本操作，而且被设计的十分快，然而计算平方根却是十分的慢，除法计算也快不到哪去，我们要处理上千个平面，每个向量都要单位化，这根本行不通！但这也意味着，我们有机会可以提高算法的速度，退一步讲，如果我们可以找到x的平方根倒数的近似结果，只要算法很快，我们就能节省很多时间，快速平方根倒数算法就是找一个近似值，大约有1%的误差，不过速度是普通算法的三倍 。

  
    i  = * ( long * ) &y;                      // evil floating point bit hack
    i  = 0x5f3759df - ( i >> 1 );              // what the fuck?
    y  = * ( float * ) &i;
    y  = y * ( threehalfs - ( x2 * y * y ) );  // 1st iteration   

算法的核心是以上4句，下面将介绍这些简单语句背后的原理

转化为对数

当我们想算x的平方根倒数时，可先用对数将其转化为更好算的形式：
于是将问题转化为求y的对数，再来看浮点数y在计算机内部是如何存储和表示的 ，
如图所示，S是符号位，0代表正，1代表负，E是指数位（8位），M是尾数（23位）这是IEEE754所规定的。 指数位要既可以表示正数，也可以表示负数，所以减去一个偏移量（127），M表示的是小数点后的数字，所以要除以2的23次幂。

直线近似对数曲线

将等式两边同时取对数，在此之前，先介绍使用线性函数近似对数函数的内容，计算过程中需要用到
当μ取0.0430时，平均近似效果最好。

浮点数二进制表示与其对数

接下来两边取对数
由以上推导得出重要认识：在一定程度上，浮点数的二进制表示就是它的对数。在这里，浮点数的二进制表示和浮点数的对数有等式关系，是否可以通过对浮点数的二进制位直接进行一些操作从而得到他的对数呢？ 下面进行论证：
从而就有了这行代码，这里用右移1位执行除以2的运算，虽然会丧失精度，但是会提高速度。

  
    i  = 0x5f3759df - ( i >> 1 );              // what the fuck?
   

而它的前一句，是因为C语言不能对浮点数进行位操作，将它的地址类型强制转化成long型，从而既可以对其进行位操作，同时也不会因为强制类型转换而改变其二进制的内容。

  
    
    i  = * ( long * ) &y;                      // evil floating point bit hack
      

它的后一句又将long型转化为float型。

  
 
    y  = * ( float * ) &i;
      

至此，就得到了一个关于x的平方根倒数的近似值，它存储在变量y里面。

牛顿迭代法

再使用一步牛顿迭代法，使这个近似值误差减小。 先给出牛顿迭代法的计算公式：
构造我们的函数，并且使用以上公式：
即有如下代码：

    y  = y * ( threehalfs - ( x2 * y * y ) );  // 1st iteration