algorithm - 约翰卡马克不寻常的快速平方根反函数(Quake III)

Question

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

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;
}

Answer 1

仅供引用。不是卡马克写的。 Terje Mathisen 和 Gary Tarolli 都对此给予了部分(而且非常适度)的赞誉，同时也赞扬了一些其他来源。

神话中的常数是如何推导出来的是一个谜。

引用 Gary Tarolli 的话:

Which actually is doing a floating point computation in integer - it took a long time to figure out how and why this works, and I can't remember the details anymore.

稍微好一点的常数，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 的 iirc 如此出色。