平方根倒数速算法

编程中，在对某一向量进行归一化时，经常需要做上图中的运算， 翻译为代码就是：

y = 1.0 / sqrt(x);

平方根倒数速算法（Fast Inverse Square Root）是一种用于快速计算逆平方根的算法。

其原理是将先将浮点数当作整数位移，再与神奇数字（0x5f3759df）做减法，这样得到的浮点数结果即是对输入数字的平方根倒数的粗略估计值，最后再进行一次牛顿迭代法，以使之更精确。

该算法最早来源于一款雷神之锤3的游戏，据说比用sqrt()函数的效率要高四倍，但我实际测试下来却发现并非如此，两者的耗时非常接近，可能和不同的硬件、编译器、sqrt()库函数的实现相关，附上测试源码如下：

#include <stdio.h>
#include <time.h>
#include <math.h>
#include <stdint.h>

float FastInvSqrt(float number)
{
    const float half = number * 0.5F;
    union {
        float f;
        uint32_t i;
    } conv = {.f = number};

    conv.i = 0x5f3759df - (conv.i >> 1);
    conv.f *= 1.5F - (half * conv.f * conv.f);
    return conv.f;
}

int main()
{
    clock_t clock1, clock2;
    float x, result, t1, t2;

    // 1.0 / sqrt()
    clock1 = clock();
    x = 0.0;
    while (x < 10000.0) {
        x += 0.001;
        result = 1.0 / sqrt(x);
    }
    clock2 = clock();

    t1 = (float)(clock2 - clock1) / (CLOCKS_PER_SEC) * 1000;
    printf("1.0 / sqrt(x)  : %f ms\n", t1);

    // FastInvSqrt()
    clock1 = clock();
    x = 0.0;
    while (x < 10000.0) {
        x += 0.001;
        result = FastInvSqrt(x);
    }
    clock2 = clock();

    t2 = (float)(clock2 - clock1) / (CLOCKS_PER_SEC) * 1000;
    printf("FastInvSqrt(x) : %f ms\n", t2);

    return 0;
}

本地电脑的测试结果如下：