algorithm - 约翰·卡马克(John Carmack)不寻常的快速反平方根(雷神三世)

John Carmack在Quake III源代码中具有一个特殊功能，该功能可以计算浮点数的反平方根，比常规(float)(1.0/sqrt(x))(包括一个奇怪的0x5f3759df常数)快4倍。请参见下面的代码。有人可以逐行解释这里到底发生了什么，为什么这样做比常规实现快得多？

float Q_rsqrt( float number )
{
  long i;
  float x2, y;
  const float threehalfs = 1.5F;

  x2 = number * 0.5F;
  y  = number;
  i  = * ( long * ) &y;
  i  = 0x5f3759df - ( i >> 1 );
  y  = * ( float * ) &i;
  y  = y * ( threehalfs - ( x2 * y * y ) );

  #ifndef Q3_VM
  #ifdef __linux__
    assert( !isnan(y) );
  #endif
  #endif
  return y;
}

最佳答案

仅供引用。卡马克没有写。 Terje Mathisen和Gary Tarolli都为此付出了部分(非常适度)的赞誉，以及其他一些来源的赞扬。

神话常数的派生方式是一个谜。

引用加里·塔罗利的话:



更好一点的常量developed by an expert mathematician(Chris Lomont)试图确定原始算法的工作方式是:

float InvSqrt(float x)
{
    float xhalf = 0.5f * x;
    int i = *(int*)&x;              // get bits for floating value
    i = 0x5f375a86 - (i >> 1);      // gives initial guess y0
    x = *(float*)&i;                // convert bits back to float
    x = x * (1.5f - xhalf * x * x); // Newton step, repeating increases accuracy
    return x;
}

尽管如此，他的最初尝试是id的sqrt的数学“上乘”版本(几乎达到相同的常数)，尽管在数学上更“纯正”，但事实却不如Gary最初开发的。他无法解释为什么id是如此出色。

关于algorithm - 约翰·卡马克(John Carmack)不寻常的快速反平方根(雷神三世)，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/1349542/