今天在看各种算法介绍的时候看到了这么一句话“神奇数字0x5f3759df并不是约翰·卡马克发明的。之所以一开始被误解，主要是许多对卡神光环膜拜已久的游戏程序员在读Quake3源码时吓尿了……”一下子引起了我的好奇心，在查阅了一些资料以后整理整个故事如下。

雷神之锤3

雷神之锤3（Quake3）是90年代的经典FPS游戏，不仅画面精美，而且整个程序优化得很好，在配置一般的电脑上也能流畅地运行。这主要归功于其3D引擎id Tech3，而此引擎是由约翰·卡马克（John Carmack）领导开发的。

卡马克是一个美国码农，id Software的创始人之一，他因在3D技术上的杰出成就而文明。卡马克还是一个开源软件的倡导者，1996年他放出了雷神之锤的源代码，而一个程序员将其改写成了Linux的版本并发给了卡马克。卡马克没有认为这是侵权，反而是要求他的员工们以这个补丁为基础开发雷神之锤的Linux版本。后来的日子id Software也一样公布了雷神之锤2的源代码，在2005年，雷神之锤3的源代码也被放出来了。

（这是官方下载地址ftp://ftp.idsoftware.com/idstuff/source/quake3-1.32b-source.zip）

我们知道，越底层的函数调用越频繁，假如把底层函数优化做好了，效率自然就上去了，3D引擎归根到底还是数学运算。在最底层的运算函数中（game/code/q_math.c中），有许多有趣的函数，有些更是令人惊叹这究竟是如何编写的。

神奇的0x5f3759df

在运算函数文件中可以找到这么一个函数，它的作用是将一个数开方并取倒数，功能上跟系统函数(float)(1.0/sqrt(x))一样，但是效率上快了四倍：

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

#ifndef Q3_VM
#ifdef __linux__
    assert( !isnan(y) ); // bk010122 - FPE?
#endif
#endif
    return y;
}

这个函数最核心，最令人费解的就是标注了“WHAT THE FUCK”的那一句

i = 0x5f3759df - ( i >> 1 );

再加上一句y = y * ( threehalfs - ( x2 * y * y ) );就完成了求开方的运算。

一般的求开方采用的都是牛顿迭代法，比如求sqrt(5)，那么先令A = 2然后B = 5 / A; A = (A + B) / 2;这样循环下去，A和B将会越来越接近，最终的结果就是根号五了。而卡马克给出的这个算法的牛逼之处在于它直接用了0x5f3759df一个数猜测了一个值，通过一次计算就很接近根号N的值了。这样省下了许多次迭代逼近的过程，那么函数效率则也就大大被优化了。

普渡大学的数学家Chris Lomont了解到了这个数字以后很感兴趣，他打算研究一下这个数字的奥秘。这个Lomont也是一个牛人，精心研究以后他从理论上推导出了一个最佳猜测值：0x5f37642f，跟程序中的0x5f3759df十分接近。Lomont得出这个结果以后很满意，他拿自己这个数跟卡马克的神奇数字做速度比赛，结果卡马克赢了……谁也不知道卡马克是怎么求出这个数的……

自己精心推导出的理论最佳值居然输给了卡马克，Lomont也是很不甘心，他用类似穷举的方法一个个地试过来，终于被他找到一个比卡马克的0x5f3759df要好一丁点的数字：0x5f375a86。于是Lomont很高兴地把这个结果写成了论文公之于世……（论文地址：https://www.matrix67.com/data/InvSqrt.pdf）

这个算法也有了自己的名字：平方根倒数速算算法（Fast Inverse Square Root）

算法的发明者

因为约翰·卡马克是整个雷神之锤项目的开发者，所以起初很多人也就简单的认为神奇数字0x5f3759df是卡马克的杰作。但是后来卡马克本人在回复问询邮件的时候否定了这个观点，卡马克回忆可能是雷神之锤项目的一个资深码农Terje Mathisen写下了这段代码。而Mathisen回复邮件则表示他以前的确写过类似的代码，但他并不是先行者。现在了解到最早的实现是Gary Tarilli在SGI Indigo中实现的，但他也表示他只是对常数进行了一些改进，实际上他也不是作者。

虽然并没有定论表示整个算法究竟是谁发明的，但是大家还是津津乐道于卡马克、和他的神奇数字0x5f3759df。

参考资料：
https://www.guokr.com/post/90718/
https://www.matrix67.com/data/InvSqrt.pdf
https://www.matrix67.com/blog/archives/362
https://en.wikipedia.org/wiki/Fast_inverse_square_root
https://en.wikipedia.org/wiki/John_Carmack
https://zh.wikipedia.org/wiki/%E5%B9%B3%E6%96%B9%E6%A0%B9%E5%80%92%E6%95%B0%E9%80%9F%E7%AE%97%E6%B3%95