初始化博客

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

大家应该都听说过雷神之锤 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;
}

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

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