https://mp.weixin.qq.com/s/XbSiJ5l7MmOAu18LoqVRCA
https://www.bilibili.com/video/BV18j411i7bp/?spm_id_from=333.880.my_history.page.click
John Carmack（约翰·卡马克）这个名字也许玩家听起来比较陌生，但如果说到他的贡献相信大家就不陌生了。如今我们玩到的FPS和3A大作都是这位大神的功劳，毫不夸张的说卡马克可谓是游戏发展史上上的3D引擎之父、程序员之神。他的FPS设计理念以及引擎构架，为整个游戏市场开辟出了一条新的道路，几乎市面上所有的第一人称射击游戏，都受到了他的影响。
约翰·卡马克
“what the fuck?”这句婉转优美的注释正是出自3D引擎之父、程序员之神约翰·卡马克。
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;
}而这句注释指向的代码只有短短的四行，但就这4行代码却永远的改变了电脑游戏，影响了后续的整个程序世界。
可以说这段代码将程序员和300年前的牛顿来了一波梦幻联动
牛顿用极度优雅的方式将二进制和微积分的思想的精华做了浓缩
下面让我们来了解让卡马克给出锐评的“平方根倒数快速算法”
平方根倒数快速算法（Fast Inverse Square Root），又称为“快速平方根倒数算法”或“0x5f3759df算法”，是一种用于计算数值的平方根倒数（1/√x）的快速算法。这个算法最著名的实现是在1999年发布的计算机游戏《雷神之锤III竞技场》（Quake III Arena）中。这个算法的关键在于利用浮点数的二进制表示和一个神奇数字（0x5f3759df）来得到一个接近真实平方根倒数的初始近似值，然后通过牛顿迭代法（Newton's method）进行精细调整。
下面是这个算法解释：
float Q_rsqrt( float number )
{
long i;
float x2, y;
const float threehalfs = 1.5F;
x2 = number * 0.5F;
y = number;
i = ( long ) &y; // 获取x的二进制表示
i = 0x5f3759df - (i >> 1); // 初始近似值的计算
y = ( float ) &i; // 将计算结果解释为浮点数
y = y (threehalfs - ( x2 y * y ) ); // 牛顿迭代
y = y (threehalfs - ( x2 y * y ) );
return y;
}推导过程涉及对IEEE 754标准的浮点数表示的理解。在IEEE 754标准中，一个浮点数由符号位、指数位和尾数位组成。对于32位的浮点数（float），其结构如下：
符号位：1位
指数位：8位
尾数位：23位
推导的关键步骤如下：
初始近似值：
通过对浮点数的二进制表示进行操作，算法初始生成一个近似值。这个操作基于这样的观察：对于32位浮点数，平方根倒数的指数部分大概是原数指数的一半。因此，通过将原数的二进制表示右移一位并从一个特定的常数中减去，可以得到一个较为合理的初始近似值。这个特定的常数就是0x5f3759df。
牛顿迭代：
初始近似值会通过牛顿迭代法进行精细调整。牛顿迭代法是一种迭代求解函数零点的方法。在这个场景中，我们想要求解f(x) = 1/x^2 - S = 0这个函数的零点，其中S是我们要计算平方根倒数的数。对于f(x)，牛顿迭代的迭代公式为：
x_{n+1} = x_n - f(x_n) / f'(x_n)将f(x)代入并简化后，我们得到了更新近似值的公式：
x_{n+1} = x_n (1.5 - xhalf x_n * x_n)其中xhalf是原数x的一半。这个迭代公式会迅速收敛到真实的平方根倒数。
这个算法的神奇之处在于，尽管它的起点是一个基于经验的近似，但它通常能在只进行一次迭代的情况下提供足够精确的结果，这使得它在计算密集型应用中非常有用，比如图形处理。
然而，由于现代处理器和编译器的优化，以及数学库的高效实现，这个算法的实际应用已经不如以前广泛。现代计算机系统可以更快、更准确地计算平方根倒数。尽管如此，这个算法在计算机科学历史上仍然是一个有趣的趣闻。
代码中的这两行：
y = y (threehalfs - ( x2 y * y ) ); // 牛顿迭代
y = y (threehalfs - ( x2 y * y ) );两行代码实际上是相同的，它们都是牛顿迭代法的一个步骤，用于精细调整初始近似值，以更接近真实的平方根倒数。这个迭代步骤是基于牛顿-拉弗森迭代法（也称作牛顿-拉弗森迭代除法），它是牛顿迭代法的一个特例，用于快速找到函数f(y) = 1/y^2 - x的零点，其中x是我们想要计算其平方根倒数的数。
这个迭代步骤的数学表达式为：
y_{n+1} = y_n (1.5 - x y_n^2 / 2)这里的threehalfs代表常数1.5，x2是原始数x的一半，y是当前的近似值。这个迭代公式可以从牛顿迭代法的一般形式导出：
y_{n+1} = y_n - f(y_n) / f'(y_n)对于f(y) = 1/y^2 - x，其导数f'(y) = -2/y^3，代入后得到：
y_{n+1} = y_n - (1/y_n^2 - x) / (-2/y_n^3)
y_{n+1} = y_n + y_n / 2 - x * y_n^3 / 2
y_{n+1} = y_n (1.5 - x y_n^2 / 2)这是牛顿迭代法中的一个迭代步骤。在代码中，这一步骤被重复执行了两次，这通常是为了提高精度。在实际应用中，一次迭代通常已经足够接近真实值，但两次迭代可以进一步提高结果的准确性。在实际使用中，你会根据所需的准确度来决定执行几次迭代。通常情况下，一到两次迭代已经足够产生一个非常接近实际值的结果。
评论区