平方根倒数速算法

背景

最近的GitHub Copilot好像出了个不大不小的新闻，AI程序员的『抄袭』好像让大家有了共同话题。^[1]在这里我们不讨论Copilot的问题，毕竟技术的发展需要时间。我们来看看这个事件中的另一个主角：平方根倒数速算法。

历史沿革

1. 就现在所知，此算法最早由Gary Tarolli在SGI Indigo的开发中使用。^[2]
2. 但后来的调查显示，该算法在这之前就于计算机图形学的硬件与软件领域有所应用，如SGI和3dfx就曾在产品中应用此算法。^[2]
3. 此算法最早可能是于90年代前期由SGI所发明。^[2]
4. 此算法的热议来源于其出现在了1999年的《雷神之锤III竞技场》源代码中。^[2]
5. 现在的准程序员对他的了解更多的可能来源于一串神奇的魔法数字：0x5f3759df。^[2]

源代码^[1]

float Q_rsqrt( float number )
{
    long i;
    float x2, y;
    const float threehalfs = 1.5F;

    x2 = number * 0.5F;
    y  = number;
    i  = * ( long * ) &y;                       // evil floating point bit level hacking
    i  = 0x5f3759df - ( i >> 1 );               // what the fuck? 
    y  = * ( float * ) &i;
    y  = y * ( threehalfs - ( x2 * y * y ) );   // 1st iteration
//  y  = y * ( threehalfs - ( x2 * y * y ) );   // 2nd iteration, this can be removed

    return y;
}

再说魔法数字0x5f3759df

1. 一个朴素的想发是，最简单的想发是牛顿法，但是牛顿法依赖频繁的浮点数运算。而在计算机上浮点数的运算远远慢于整数运算，同时也慢于位运算 & 逻辑运算。
2. 更进一步，是否可以通过推导，将之前方法的浮点数运算转为整数运算，或位运算以及逻辑运算。
3. 一个复杂的推导方案出来了。^[3]

说在最后

当年计算机资源紧张的时候，看把我们的前辈们逼成什么样了。摩拜当年的大神。

参考文献

[1] https://baijiahao.baidu.com/s?id=1704248449970053334
[2] https://baike.baidu.com/item/%E5%B9%B3%E6%96%B9%E6%A0%B9%E5%80%92%E6%95%B0%E9%80%9F%E7%AE%97%E6%B3%95/4075273
[3] https://www.cnblogs.com/saaav/p/5807736.html
[4] http://www.matrix67.com/data/InvSqrt.pdf