Fast inverse square root 平方根倒数速算法
平方根倒数速算法是用于快速计算
2/1
x
�
(即 x 的平方根的倒数)
的一种算法。浮点数的平方根倒数常用于计算正规化向量。3D 图形
程序需要使用正规化向量来实现光照和投影效果,因此每秒都需要做
上百万次平方根倒数运算,而在处理坐标转换与光源的专用硬件设备
出现前,这些计算都由软件完成,计算速度亦相当之慢;在 1990 年
代这段代码开发出来之时,多数浮点数操作的速度更是远远滞后于整
数操作,因而针对正规化向量算法的优化就显得尤为重要。
算法步骤
算法首先接收一个 32 位带符浮点数,然后将之作为一个 32 位的
整数看待,以将其向右进行一次逻辑移位的方式将之取半,并用十六
进制“魔术数字”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 ) ); //
牛顿迭代
// y = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration
return y;}
算法原理
将浮点数转化为整数
一个浮点数以 32 个二进制表示一个有理数,其中首位是符号位