世界上最快的浮点开方算法

《世界上最快的浮点开方算法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、任何一个3D引擎都是通过其内部的数学模型和实现工具来展现它的力量与速度的，Quake III中使用了一个非常有意思的技巧来计算平方根倒数（inverse square root）　　Carmack's 不寻常平方根倒数 卡马克算法　　第一个跳出来的便是对函数Q_rsqrt中对0x5f3759df的使用，这个数计算了一个浮点数的inverse square root，但是为什么这个函数有这样的功能呢？ 　　观察q_math.c原本的函数： 　　[c-sharp] viewplaincopyprint?1.float Q_rsqrt( float number )    2.{  3.  l

2、ong i;   4.  float x2, y;    5.  const float threehalfs = 1.5F;    6.  x2 = number * 0.5F;   7.  y  = number;  8.  i  = * ( long * ) &y;  // evil floating point bit level hacking    9.  i  = 0x5f3759df - ( i >> 1 );  10.  y  = * ( float * ) &i;  11.  y  = y * ( threehalfs - ( x2 * y * y ) ); // 1

3、st iteration    12.  y  = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can be removed    13.y  = y * ( threehalfs - ( x2 * y * y ) );//增加精度值14.  return y;   //返回倒数 15.}    　　它不仅有效，甚至在某些CPU上，Carmack的Q_rsqrt 比(float)(1.0/sqrt(x)的计算快4倍，尽管sqrt()通常使用的是FSQRT的汇编指令！　　在另一个文件code/common/cm_t

4、race.c 中，我们发现了更简洁的对同样HACK的实现。这一次，它被用来计算一个float - sqrt(x)的平方根。注意，其中的唯一不同是在返回值上－－用返回*y取代了返回y。  　　[c-sharp] viewplaincopyprint?1.float SquareRootFloat(float number) {  2.    long i;   3.    float x, y;   4.    const float f = 1.5F;    5.    x = number * 0.5F;  6.    y  = number;   7.    i  = * ( lon

5、g * ) &y;    8.    i  = 0x5f3759df - ( i >> 1 );    9.    y  = * ( float * ) &i;    10.    y  = y * ( f - ( x * y * y ) );    11.    y  = y * ( f - ( x * y * y ) );    12.    return number * y;    //返回开方13.}   　　牛顿对根的近似值 　　上面的代码执行了众所周知的牛顿对根的近似值，像绝大多数其它迭代求近似值的计算一样，牛顿近似值假定是迭代的；每一次迭代都增强了它的准确度直至达到需要的

6、准确度。　　在牛顿近似值中的一般想法是我们我们猜测一个数x的平方根值y，我们可能通过一个简单的操作用x/y来拉平y来取得更好的猜测，使其更接近实际的平方根，例如，我们像下面这样计算2的平方根，我们假定初始的猜测是1：　　[c-sharp] viewplaincopyprint?1.2/1 = 2 ;  (2 + 1) / 2 = 1.5   2.2/1.5 = 1.3333; ( 1.5 + 1.3333 ) / 2 = 1.4167   3.2/1.4167 = 1.4117;  ( 1.4167 + 1.4117 ) / 2 = 1.4142   4.And so on...    

7、　　如前面所提到的，牛顿的近似值是一个大家所熟知的用以快速计算平方根的方法。但是，Carmack在初始的猜测中就选取的不寻常的值，它彻底加强了准确度并且将Quake III中计算所要的值的迭代次数降到了1次！魔数 　　这个函数中真正有意思的方面是神奇的常量0x5f3759df，用来计算初始猜测的，在 　　[c-sharp] viewplaincopyprint?1.i  = 0x5f3759df - ( i >> 1 );