Quake III中不可思议的求解平方根实现方法
任何一个3D引擎都是通过其内部的数学模型和实现工具来展现它的力量与速度的,and trust John Carmack of ID software for using really good hacks. 结果,Quake III中使用了一个非常有意思的技巧来计算平方根倒数(inverse square root)
前言
ID software最近发布了它的带有Gpl许可证的Quake III引擎源代码,在这篇文章中我们将会看到Carmark是怎样用他的black magic来极其迅速地计算一个浮点数的平方根的。
Carmack's 不寻常平方根倒数
对文件game/code/q_math.c的快速一瞥就显示出了许多有趣的performance hacks。
第一个跳出来的便是对函数Q_rsqrt中对0x5f3759df的使用,这个数计算了一个浮点数的inverse square root,但是为什么这个函数有这样的功能呢?
观察q_math.c原本的函数:
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 level hacking
i = 0x5f3759df - ( i >> 1 ); // what the *?
y = * ( float * ) &i;
y = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration
// y = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can be removed
#ifndef Q3_VM
#ifdef __linux__
assert( !isnan(y) ); // bk010122 - FPE?
#endif
#endif
return y;
}
br/>它不仅有效,甚至在某些CPU上,Carmack的Q_rsqrt 比(float)(1.0/sqrt(x)的计算快4倍,尽管sqrt()通常使用的是FSQRT的汇编指令!
在另一个文件code/common/cm_trace.c 中,我们发现了更简洁的对同样HACK的实现。这一次,它被用来计算一个float - sqrt(x)的平方根。注意,其中的唯一不同是在返回值上--用返回*y取代了返回y。
/*
================
SquareRootFloat
================
*/
float SquareRootFloat(float number) {
long i;
float x, y;
const float f = 1.5F;
x = number * 0.5F;
y = number;
i = * ( long * ) &y;
i = 0x5f3759df - ( i >> 1 );
y = * ( float * ) &i;
y = y * ( f - ( x * y * y ) );
y = y * ( f - ( x * y * y ) );
return number * y;
}