这篇文章应个人认为应该是比较简单，但也有一定深度的。看到有些后辈不太理解数学在编程里的作用，所以这次用一个非常简单的实例，给大家讲述一下代码中神奇的数学原理。

引子

       如果游戏圈最近有什么大新闻，那一定就是switch被破解了，而且是被破解连底裤都不剩，简直可怜。我个人不太鼓励普通玩家破解，但是也得承认，我个人对于自制软件和老金一直有很大兴趣。为了体验ns自制软件软件开发，我个人甚至专门另外购置一台ns研究。

       要说ns的破解，就不得不提到34c3大会。在大会上，Plutoo、Derrek、Naehrwert三位大神对switch内核权限漏洞的利用技巧进行了展示。

        34c3大会上还展示了一个名为34c3-demo的demo，之后，homebrew(自制软件)便一日千里。而本文的主题，就藏在34c3-demo之中。

       34c3-demo给出了求二为底的指数函数，二为底的对数函数，三角函数，x的y次方这样常用函数的实现。时间复杂度均为 O(1)。

       效率是开发者永恒的追求，这个数学库，很有研究价值。

fast_exp2

fast_log2

fast_sinf & fast_cosf

fast_powf

fast_InvSqrt(卡马克快速平方根)

数学证明

       受限于篇幅，只为大家推导一下快速平方根算法。

牛顿迭代算法

       该算法的本质其实就是牛顿迭代法（Newton-Raphson Method，简称NR），而NR的基础则是泰勒级数（Taylor Series）。NR是一种求方程的近似根的方法。首先要估计一个与方程的根比较靠近的数值，然后根据公式推算下一个更加近似的数值，不断重复直到可以获得满意的精度。其公式如下

则方程f(x)的第n+1个近似根为：

NR的公式可以看出：理论上，只要迭代次数足够，总能逐渐趋近于准确解。NR最关键的地方就是估算第一个近似根。如果第一个根和结果很接近，那么只需要几次迭代就能得到精度足够的解。

求平方根倒数

       求平方根的倒数，其实就是求1/x^2−a=0的解。将该方程用牛顿迭代法解开：

如果把1/2放到括号内，就得到倒数第二行代码x = x*(1.5f - xhalf*x*x)

       接下来，就要求第一个近似根xn，这也是整个函数最神奇的地方，因为只用一次迭代过程就得到了这个解：

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

float数据类型

       float数据类型位数作用：

所以，32位浮点数用十进制实数表示就是：

开根号取倒数就是：

0x5f3759df是哪来的

       语句(i >> 1)的作用就是将指数除以2，得到2^(-E/2)的部分。

       对于实数R>0，假设在IEEE的浮点数表示中，指数为E，尾数为M，则其原理可以简述为为IEEE的浮点数中，尾数M省略了最前面的1，所以实际的尾数是1+M。如果你在大学上数学没忘干净，那么当你看到(1+M)^(-1/2)这样的形式时，应该会马上联想的到它的泰勒级数展开，而该展开式的第一项就是常数。

将(1+M)^(-1/2)按泰勒级数展开，取第一项

在不考虑指数符号的情况下，(M/2)*2^(E/2)正是(R>>1)。

       在IEEE浮点数中，指数的符号可以考位移实现(指数位的阶码 = 阶码真值 + 127)，而2^(-E/2)是常数项。所以原式可以化为：

之后，只要求出另误差最小的C值即可。也就是0x5f3759df(不过其实存在精度更高的C值，为0x5f375a86，这个C值的由来就是另一段逸闻了)。

faster math

       上面的对float特化函数已经够快了(时间复杂度为O(1))，但是，如果我还嫌慢，怎么办。那就要借助SIMD了。fastapprox项目提供了如下函数的近似向量化实现：

• exponential, logarithm, and power

• lgamma and digamma

• cosh, sinh, tanh

• cos, sin, tan

• sigmoid and erf

• Lambert W