1700536610
1700536611
平方根倒数速算法
1700536612
1700536613
20世纪90年代曾出现过一款不可思议的游戏——雷神之锤（Quake series）。除了优秀的情节设定和精美的画面外，这个游戏最让人称道的莫过于它的运行效率。在计算机配置低下的年代，一段小动画都是一个奇迹，但雷神之锤却能流畅运行于各种配置的电脑上。 直到2005年Quake Engine开源时，雷神之锤系列游戏的秘密才被揭开。在代码库中，人们发现了许多堪称神来之笔的算法。它们以极其变态的高效率，压榨着计算机的性能，进而支撑起了20世纪90年代3D游戏的传奇。其中的某些算法，甚至比系统原生的实现还要快！今天的主角—— 快速平方根倒数算法（Fast Inverse Square Root）就是其中一个。
1700536614
1700536615
1700536616
在3D 绘图中，计算平方根倒数是一步重要的运算，因为计算机需要大量求解一个矢量的方向矢量，即
1700536617
1700536618
1700536619
1700536620
1700536621
（7.25）
1700536622
1700536623
其中就涉及平方根倒数的计算，这也是最麻烦的一步。如果能在此做一些优化，渲染效率无疑会得到极大提高。先来看雷神之锤中平方根倒数速算法的代码。
1700536624
1700536625
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;}
1700536626
1700536627
从代码中可以看出，算法最后有两步相同的操作，像是在对一个数进行某种迭代。而其中的第二步被注释掉了，似乎是因为和性能损耗相比，对结果的二次迭代意义不大，这也说明一次迭代的结果在误差允许范围内。这些特性让人想到了牛顿法。
1700536628
1700536629
1700536630
1700536631
1700536632
1700536633
牛顿法是一种常用的求方程数值解的方法，具体如下：若在某个区间I中，f(x)连续可导，且有唯一零点x0，则任取x1∈I，定义数列，则有。用牛顿法进行迭代，可以完成对解的任意精度的数值逼近。下面尝试写出的迭代式，首先令，则有
1700536634
1700536635
1700536636
1700536637
1700536638
（7.26）
1700536639
1700536640
1700536641
将xn+1，xn替换成y，将替换成x2，可以发现和算法的最后一步是吻合的。由此可知，雷神之锤中的平方根速算法确实采用了牛顿法。
1700536642
1700536643
1700536644
1700536645
1700536646
百面机器学习：算法工程师带你去面试 [:1700532207]
1700536647
百面机器学习：算法工程师带你去面试 04 梯度验证
1700536648
1700536649
1700536650
1700536651
场景描述
1700536652
1700536653
在用梯度下降法求解优化问题时，最重要的操作就是计算目标函数的梯度。对于一些比较复杂的机器学习模型，如深度神经网络，目标函数的梯度公式也非常复杂，很容易写错。因此，在实际应用中，写出计算梯度的代码之后，通常需要验证自己写的代码是否正确。
1700536654
1700536655
知识点
1700536656
1700536657
微积分，线性代数
1700536658
1700536659
问题 如何验证求目标函数梯度功能的正确性？