0x5f3759df这个快速开方中的常数的数学依据是什么？

0x5f3759df 这个神奇的数字，是游戏《雷神之锤》的代码中发现的那个惊人的快速平方根算法的关键。很多人都好奇，为什么偏偏是这个数字？它的背后有什么深厚的数学原理吗？

要理解这一点，我们得先回到数学中最基本的需求之一：如何快速找到一个数的平方根？

在计算机的世界里，进行浮点数运算（就是带小数点的数）通常比整数运算要慢一些，而求平方根又是其中比较复杂的操作。在《雷神之锤》那个年代，CPU的速度远不如现在，每一毫秒的提升都至关重要，特别是在需要大量实时计算的游戏场景中。开发者们就在寻找一种能够尽可能快地逼近平方根的方法，即使这个结果不是绝对精确，但对于游戏来说，足够用了。

这里我们就要引入一个概念：浮点数的内部表示。

计算机存储浮点数，通常遵循一个叫做“IEEE 754”的标准。简单来说，一个浮点数被分成三个部分来存储：

1. 符号位 (Sign Bit): 表示正负，0是正，1是负。
2. 指数位 (Exponent): 表示这个数有多大或多小（用科学计数法里的指数来表示）。
3. 尾数位 (Mantissa/Significand): 表示数值的精度部分。

对于一个正数 `x`，我们想要求 `sqrt(x)`。如果我们在脑海里把 `x` 的浮点数表示“动点手脚”，让它变成 `sqrt(x)` 的浮点数表示，那不就能一步到位了吗？

这里有一个关键的观察：对数的性质。

我们知道 `log(a b) = log(a) + log(b)`，以及 `log(a^b) = b log(a)`。

如果我们考虑 `y = sqrt(x)`，那么 `y y = x`。
取对数的话，`log(y y) = log(x)`，所以 `2 log(y) = log(x)`，最后得到 `log(y) = log(x) / 2`。

换句话说，如果能把一个数的“对数表示”除以2，然后将其“反转”回原来的数值表示，就能得到它的平方根。

神奇的“近似对数”

IEEE 754 标准的浮点数表示，在某种程度上，可以被看作是对数的近似。指数位部分，很大程度上决定了数值的大小（就像科学计数法的指数）。尾数部分则提供了精度。

如果你仔细分析浮点数的存储格式，会发现将指数位“右移”（相当于除以2）以及对尾数进行某种变换，可以近似地实现“取对数再除以2”的操作。

具体来说，对于一个正数 `x`（我们假设它没有隐藏的“1.”部分，而是直接是浮点数表示），其IEEE 754 单精度浮点数表示 `I` 可以大致看作：

`I ≈ C (2^E) M` （这里 C, E, M 是指数和尾数的一些组合）

如果我们想得到 `sqrt(x)`，其表示 `J` 大约是：

`J ≈ C' (2^(E/2)) M'`

重点在于指数 `E` 和尾数 `M`。通过一系列数学推导，可以发现对整数 `I` 进行一个特殊的移位操作，再加上一个常数，可以近似地得到 `J` 的整数表示。

那么，0x5f3759df 又是从哪里来的呢？

这个常数，就是为了让上述“近似对数”操作变得尽可能准确而精心选择的。

数学家们发现，如果我们将一个浮点数的整数表示 `i`，乘以一个特定的常数 `0x5f3759df`，然后进行一次“牛顿拉夫逊迭代”（一种求根的数值方法），就可以非常快速且准确地得到平方根的近似值。

这个常数 `0x5f3759df` 并不是凭空捏造的，而是通过以下方式找到的：

1. 建立精确模型: 首先，建立一个数学模型，描述浮点数表示和实际数值之间的关系，以及如何通过操作浮点数表示来近似求平方根。这涉及到对IEEE 754 标准的深入理解。
2. 误差分析: 针对这个近似模型，分析其误差来源，特别是由于浮点数表示和“近似对数”导致的误差。
3. 优化常数: 在这个误差模型的基础上，找到一个常数，使得通过对该常数的乘法和一次或多次迭代后，能够最小化总体的误差。这个过程通常是高度数学化的，可能涉及到微积分和优化的技术。
4. “美妙的巧合”： 最终发现的 `0x5f3759df` 在很大程度上是数学优化和浮点数表示特性的一个“美妙的巧合”。它能在不牺牲太多精度的情况下，提供一个非常好的起点，使得后续的牛顿迭代法能够快速收敛到准确结果。

简而言之，0x5f3759df 是一个针对 IEEE 754 浮点数格式，通过数学优化手段找到的“魔术数字”，它使得将一个数的浮点数表示“映射”到其平方根的浮点数表示，通过一次特殊的移位、减法（乘以常数并取负代表减法）操作，再辅以一次牛顿迭代，能够高效地得到非常精确的平方根近似值。

这个常数之所以如此出名，不仅因为它在《雷神之锤》中的实际应用，更因为它展示了计算机科学和数学之间如何能产生如此巧妙而高效的解决方案。它不是一个凭空出现的“魔法”，而是对数字表示和数值算法深刻理解的产物。

实名反对一楼 @Yong He 的答案。

单精度的浮点数结构是这样：

那么现在，每个正浮点数 y 可以用尾数和指数的形式写成 ，其中 m 是尾数部分，取值范围是 ；e 是指数部分，一个整数。每个浮点数所对应的「整数形式」则可以用表示，其中 L 是指数部分需要的位移次数（用 2 的幂表示），E 和 M 是指数部分和小数部分的整数版本。两者之间的关系是

对单精度浮点而言，。

考虑对数 ，由于，，取近似，可以算出整体「偏差」最小的，此时两者基本相当。因此我们可以说

……………… (1)

那么，对于 y 的整数形式 Y 而言，展开并带代入 (1) 有：

即

………………(2)

那么对于 来说，，代入 (2) 得：

解得

。

这个就是代码

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

的秘密所在。0x5F3759DF 的具体取值是根据 δ 变的，至于卡马克为啥用 0x5F3759DF 而不是其他相近的值，估计是做实验测的吧……