约翰·卡马克的不寻常的快反平方根（雷神之锤III） [英] John Carmack's Unusual Fast Inverse Square Root (Quake III)

问题描述

约翰·卡马克在雷神之锤III源$ C ​​$ C一个特殊的函数计算浮点数的平方根倒数，4比普通快（浮点）（1.0 / SQRT（X）），其中包括一个奇怪的 0x5f3759df 不变。请参见下面的code。有人可以解释究竟是怎么回事一行行，为什么这个作品比普通实现如此之快？

浮动Q_rsqrt（浮点数） {   我长;   浮X2，Y;   常量浮threehalfs = 1.5F;   X2 =数量* 0.5F;   Y =号;   I = *（长*）及; Y;   I = 0x5f3759df - （ⅰ＆GT;大于1）;   Y = *（浮点*）及I;   Y = Y *（threehalfs - （X2 * Y * Y））;   #ifndef的Q3_VM   #ifdef来__linux__     断言（！isnan（Y））;   #ENDIF   #ENDIF   返回是; }

解决方案

仅供参考。卡马克没有写出来。泰耶马蒂森和加里Tarolli都接受部分（很少的）它的信用，以及计入其他来源。

如何神话不断被衍生为一个谜。

要引用加里Tarolli：

  

这实际上是做一个浮动   计算点整数 - 花   很长一段时间来弄清楚如何以及为什么   这个工作的，我不记得了   详细信息了。

一个稍微好一点不变，由专家数学家（克里斯Lom​​ont）试图找出如何工作的原算法开发的：

 浮动InvSqrt（浮X）
{
  浮xhalf = 0.5F * X;
  INT I = *（INT *）及X; //得到位浮点值
  I = 0x5f375a86-（ⅰ＆GT;大于1）; //使最初的猜测Y0
  X = *（浮点*）及I; //转换位回浮
  X = X *（1.5F-xhalf * X * X）; //牛顿步，重复精度提高
  返回X;
}
 

尽管如此，他首次尝试的id开方的数学上级的版本（这来了几乎相同的常）被证明不如由加里初步形成一个尽管是数学上多素净。他无法解释为什么的ID是那么优秀的IIRC。

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

解决方案

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.

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

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.

这篇关于约翰·卡马克的不寻常的快反平方根（雷神之锤III）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！