John Carmack 不寻常的快速反平方根 (Quake III) [英] John Carmack's Unusual Fast Inverse Square Root (Quake III)

问题描述

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

John Carmack has a special function in the Quake III source code which calculates the inverse square root of a float, 4x faster than regular (float)(1.0/sqrt(x)), including a strange 0x5f3759df constant. See the code below. Can someone explain line by line what exactly is going on here and why this works so much faster than the regular implementation?

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 都对它进行了部分(并且非常谦虚)的归功于它，以及归功于其他一些来源.

FYI. Carmack didn't write it. Terje Mathisen and Gary Tarolli both take partial (and very modest) credit for it, as well as crediting some other sources.

这个神话常数是如何得出的有点神秘.

How the mythical constant was derived is something of a mystery.

引用加里·塔罗利的话:

To quote 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.

一个稍微好一点的常数，由专家数学家开发(ChrisLomont)试图弄清楚原始算法的工作原理是:

A slightly better constant, developed by an expert mathematician (Chris Lomont) trying to work out how the original algorithm worked is:

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 如此出色.

In spite of this, his initial attempt a mathematically 'superior' version of id's sqrt (which came to almost the same constant) proved inferior to the one initially developed by Gary despite being mathematically much 'purer'. He couldn't explain why id's was so excellent iirc.

这篇关于John Carmack 不寻常的快速反平方根 (Quake III)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！