从何时开始怕遥望星辰?

快速平方根算法 - 从卡马克的魔法数字谈起

大家应该都听说过雷神之锤 3 中那段神奇的快速平方根倒数算法 —— 它因为使用了魔法数字:0x5f3759df 而闻名:

1
2
3
4
5
6
7
8
float InvSqrt(float x) {
float xhalf = 0.5f*x;
int i = *(int*)&x;
i = 0x5f3759df - (i >> 1);
x = *(float*)&i;
x = x*(1.5f - xhalf*x*x);
return x;
}

事实上,这个算法使用的方法是传统的牛顿迭代法 —— 之所以它能够在常数时间内给出结果,是因为这个魔法数字可以让迭代开始时的值就已经很接近实际根了。

下面我从牛顿迭代开始,一步步实现一个快速平方根算法,并探究这个魔法数字到底是怎么来的。

快速平方根算法 - 从卡马克的魔法数字谈起