Quake-III Arena (雷神之錘3)是90年代的經典游戲之一。

?

該系列的游戲不但畫面和內容不錯，而且即使計算機配置低，也能極其流暢地運行。這要歸功于它3D引擎的開發者約翰-卡馬克（John Carmack）。事實上早在90年代初DOS時代，只要能在PC上搞個小動畫都能讓人驚嘆一番的時候，John Carmack就推出了石破天驚的Castle Wolfstein, 然后再接再勵，doom, doomII, Quake...每次都把3-D技術推到極致。他的3D引擎代碼資極度高效，幾乎是在壓榨PC機的每條運算指令。當初MS的Direct3D也得聽取他的意見，修改了不少API。

最近，QUAKE的開發商ID SOFTWARE遵守GPL協議，公開了QUAKE-III的原代碼，讓世人有幸目睹Carmack傳奇的3D引擎的原碼。

我們知道，越底層的函數，調用越頻繁。3D引擎歸根到底還是數學運算。

那么找到最底層的數學運算函數（game/code/q_math.c），必然是精心編寫的。里面有很多有趣的函數，很多都令人驚奇，估計我們幾年時間都學不完。

在/code/game/q_math.c里發現了這樣一段代碼。

它的作用是將一個數開平方并取倒，經測試這段代碼比(float)(1.0/sqrt(x))快4倍：

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 hackingi = 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#ifndef Q3_VM #ifdef __linux__assert( !isnan(y) ); // bk010122 - FPE? #endif #endifreturn y; }

函數返回1/sqrt(x)，這個函數在圖像處理中比sqrt(x)更有用。

注意到這個函數只用了一次疊代！（其實就是根本沒用疊代，直接運算）。編譯，實驗，這個函數不僅工作的很好，而且比標準的sqrt()函數快4倍！要知道，編譯器自帶的函數，可是經過嚴格仔細的匯編優化的啊！

這個簡潔的函數，最核心，也是最讓人費解的，就是標注了“what the fuck?”的一句：i = 0x5f3759df - ( i >> 1 );

再加上y = y * ( threehalfs - ( x2 * y * y ) );

兩句話就完成了開方運算！而且注意到，核心那句是定點移位運算，速度極快！特別在很多沒有乘法指令的RISC結構CPU上，這樣做是極其高效的。

算法的原理其實不復雜,就是牛頓迭代法,用x-f(x)/f'(x)來不斷的逼近f(x)=a的根。

簡單來說比如求平方根,f(x)=x^2=a ,f'(x)= 2*x,f(x)/f'(x)=x/2,把f(x)代入x-f(x)/f'(x)后有(x+a/x)/2，現在我們選a=5,選一個猜測值比如2，那么我們可以這么算

?

5/2 = 2.5;

(2.5+2)/2 = 2.25;

5/2.25 = xxx;

(2.25+xxx)/2 = xxxx

...

這樣反復迭代下去，結果必定收斂于sqrt(5)，沒錯，一般的求平方根都是這么算的，但是卡馬克(quake3作者)真正牛B的地方是他選擇了一個神秘的常數0x5f3759df 來計算那個猜測值，就是我們加注釋的那一行,那一行算出的值非常接近1/sqrt(n),這樣我們只需要2次牛頓迭代就可以達到我們所需要的精度.好吧 如果這個還不算NB,接著看:

普渡大學的數學家Chris Lomont看了以后覺得有趣，決定要研究一下卡馬克弄出來的這個猜測值有什么奧秘。Lomont也是個牛人，在精心研究之后從理論上也推導出一個最佳猜測值，和卡馬克的數字非常接近, 0x5f37642f?？R克真牛，他是外星人嗎？

傳奇并沒有在這里結束。Lomont計算出結果以后非常滿意，于是拿自己計算出的起始值和卡馬克的神秘數字做比賽，看看誰的數字能夠更快更精確的求得平方根。結果是卡馬克贏了... 誰也不知道卡馬克是怎么找到這個數字的。

最后Lomont怒了，采用暴力方法一個數字一個數字試過來，終于找到一個比卡馬克數字要好上那么一丁點的數字，雖然實際上這兩個數字所產生的結果非常近似，這個暴力得出的數字是0x5f375a86。

Lomont為此寫下一篇論文，"Fast Inverse Square Root"。

最后，給出最精簡的1/sqrt()函數：

float InvSqrt(float x) {float xhalf = 0.5f * x;int i = *(int *)&x;i = 0x5f3759df - (i>>1);x = *(float *)&i;x = x * (1.5f - xhalf * x * x);return x; }

?

總結

以上是生活随笔為你收集整理的0x5f3759df的数学原理的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。