打字猴:1.70053661e+09
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 问题 如何验证求目标函数梯度功能的正确性?
[ 上一页 ]  [ :1.70053661e+09 ]  [ 下一页 ]