C語言基礎(chǔ) - 數(shù)學庫 - 跨越數(shù)學和代碼的鴻溝
這篇文章應(yīng)個人認為應(yīng)該是比較簡單，但也有一定深度的。看到有些后輩不太理解數(shù)學在編程里的作用，所以這次用一個非常簡單的實例，給大家講述一下代碼中神奇的數(shù)學原理。
引子
如果游戲圈最近有什么大新聞，那一定就是switch被破解了，而且是被破解連底褲都不剩，簡直可憐。我個人不太鼓勵普通玩家破解，但是也得承認，我個人對于自制軟件和老金一直有很大興趣。為了體驗ns自制軟件軟件開發(fā)，我個人甚至專門另外購置一臺ns研究。
要說ns的破解，就不得不提到34c3大會。在大會上，Plutoo、Derrek、Naehrwert三位大神對switch內(nèi)核權(quán)限漏洞的利用技巧進行了展示。
34c3大會上還展示了一個名為34c3-demo的demo，之后，homebrew(自制軟件)便一日千里。而本文的主題，就藏在34c3-demo之中。
34c3-demo給出了求二為底的指數(shù)函數(shù)，二為底的對數(shù)函數(shù)，三角函數(shù)，x的y次方這樣常用函數(shù)的實現(xiàn)。時間復雜度均為 O(1)。
效率是開發(fā)者永恒的追求，這個數(shù)學庫，很有研究價值。
fast_exp2
fast_log2
fast_sinf & fast_cosf
fast_powf
fast_InvSqrt(卡馬克快速平方根)
數(shù)學證明
受限于篇幅，只為大家推導一下快速平方根算法。
牛頓迭代算法
該算法的本質(zhì)其實就是牛頓迭代法（Newton-Raphson Method，簡稱NR），而NR的基礎(chǔ)則是泰勒級數(shù)（Taylor Series）。NR是一種求方程的近似根的方法。首先要估計一個與方程的根比較靠近的數(shù)值，然后根據(jù)公式推算下一個更加近似的數(shù)值，不斷重復直到可以獲得滿意的精度。其公式如下
則方程f(x)的第n+1個近似根為：
NR的公式可以看出：理論上，只要迭代次數(shù)足夠，總能逐漸趨近于準確解。NR最關(guān)鍵的地方就是估算第一個近似根。如果第一個根和結(jié)果很接近，那么只需要幾次迭代就能得到精度足夠的解。
求平方根倒數(shù)
求平方根的倒數(shù)，其實就是求1/x^2?a=0的解。將該方程用牛頓迭代法解開：
如果把1/2放到括號內(nèi)，就得到倒數(shù)第二行代碼x = x*(1.5f - xhalf*x*x)
接下來，就要求第一個近似根xn，這也是整個函數(shù)最神奇的地方，因為只用一次迭代過程就得到了這個解：
i = 0x5f3759df - (i >> 1);
float數(shù)據(jù)類型
float數(shù)據(jù)類型位數(shù)作用：
所以，32位浮點數(shù)用十進制實數(shù)表示就是：
開根號取倒數(shù)就是：
0x5f3759df是哪來的
語句(i >> 1)的作用就是將指數(shù)除以2，得到2^(-E/2)的部分。
對于實數(shù)R>0，假設(shè)在IEEE的浮點數(shù)表示中，指數(shù)為E，尾數(shù)為M，則其原理可以簡述為為IEEE的浮點數(shù)中，尾數(shù)M省略了最前面的1，所以實際的尾數(shù)是1+M。如果你在大學上數(shù)學沒忘干凈，那么當你看到(1+M)^(-1/2)這樣的形式時，應(yīng)該會馬上聯(lián)想的到它的泰勒級數(shù)展開，而該展開式的第一項就是常數(shù)。
將(1+M)^(-1/2)按泰勒級數(shù)展開，取第一項
在不考慮指數(shù)符號的情況下，(M/2)*2^(E/2)正是(R>>1)。
在IEEE浮點數(shù)中，指數(shù)的符號可以考位移實現(xiàn)(指數(shù)位的階碼 = 階碼真值 + 127)，而2^(-E/2)是常數(shù)項。所以原式可以化為：
之后，只要求出另誤差最小的C值即可。也就是0x5f3759df(不過其實存在精度更高的C值，為0x5f375a86，這個C值的由來就是另一段逸聞了)。
faster math
上面的對float特化函數(shù)已經(jīng)夠快了(時間復雜度為O(1))，但是，如果我還嫌慢，怎么辦。那就要借助SIMD了。fastapprox項目提供了如下函數(shù)的近似向量化實現(xiàn)：
exponential, logarithm, and power
lgamma and digamma
cosh, sinh, tanh
cos, sin, tan
sigmoid and erf
Lambert W
