亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

[轉]Quake-III代碼里神奇的浮點開方函數

系統 1902 0

[轉]Quake-III代碼里神奇的浮點開方函數

[轉]Quake-III代碼里神奇的浮點開方函數

2010-09-30 19:42:18
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引擎的原碼。
???這是QUAKE-III原代碼的下載地址:
?? http://www.fileshack.com/file.x?fid=7547

(下面是官方的下載網址,搜索 “quake3-1.32b-source.zip” 可以找到一大堆中文網頁的
ftp://ftp.idsoftware.com/idstuff/source/quake3-1.32b-source.zip)

???我們知道,越底層的函數,調用越頻繁。3D引擎歸根到底還是數學運算。那么找到最底層的數學運算函數(在game/code/q_math.c), 必然是精心編寫的。里面有很多有趣的函數,很多都令人驚奇,估計我們幾年時間都學不完。

在game/code/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 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

???#ifndef Q3_VM
???#ifdef __linux__
?????assert( !isnan(y) ); // bk010122 - FPE?
???#endif
???#endif
???return 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。卡馬克真牛,他是外星人嗎?

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

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

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



論文下載地址:
http://www.math.purdue.edu/~clomont/Math/Papers/2003/InvSqrt.pdf
http://www.matrix67.com/data/InvSqrt.pdf

參考:<IEEE Standard 754 for Binary Floating-Point Arithmetic><FAST INVERSE SQUARE ROOT>


最后,給出最精簡的1/sqrt()函數:
float InvSqrt(float x)
{
???float xhalf = 0.5f*x;
???int i = *(int*)&x; // get bits for floating VALUE
???i = 0x5f375a86- (i>>1); // gives initial guess y0
???x = *(float*)&i; // convert bits BACK to float
???x = x*(1.5f-xhalf*x*x); // Newton step, repeating increases accuracy
???return x;
}
大家可以嘗試在PC機、51、AVR、430、ARM、上面編譯并實驗,驚訝一下它的工作效率。

?

前兩天有一則新聞,大意是說 Ryszard Sommefeldt 很久以前看到這麼樣的一段 code (可能出自 Quake III 的 source code):
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;

}

他一看之下驚為天人,想要拜見這位前輩高人,但是一路追尋下去卻一直找不到人;同時間也有其他人在找,雖然也沒找到出處,但是 Chris Lomont 寫了一篇論文 (in PDF) 解析這段 code 的演算法 (用的是 Newton’s Method,牛頓法;比較重要的是後半段講到怎麼找出神奇的 0x5f3759df 的)。

PS. 這個 function 之所以重要,是因為求 開根號倒數 這個動作在 3D 運算 (向量運算的部份) 裡面常常會用到,如果你用最原始的 sqrt() 然後再倒數的話,速度比上面的這個版本大概慢了四倍吧… XD

PS2. 在他們追尋的過程中,有人提到一份叫做 MIT HACKMEM 的文件,這是 1970 年代的 MIT 強者們做的一些筆記 (hack memo),大部份是 algorithm,有些 code 是 PDP-10 asm 寫的,另外有少數是 C code (有人整理了一份列表)。


附:牛頓迭代法快速尋找平方根

???????下面這種方法可以很有效地求出根號a的近似值:首先隨便猜一個近似值x,然后不斷令x等于x和a/x的平均數,迭代個六七次后x的值就已經相當精確了。
???????例如,我想求根號2等于多少。假如我猜測的結果為4,雖然錯的離譜,但你可以看到使用牛頓迭代法后這個值很快就趨近于根號2了:

( 4 + 2/ 4 ) / 2 = 2.25
( 2.25 + 2/ 2.25 ) / 2 = 1.56944..
( 1.56944..+ 2/1.56944..) / 2 = 1.42189..
( 1.42189..+ 2/1.42189..) / 2 = 1.41423..
....

?


??????
???????這種算法的原理很簡單,我們僅僅是不斷用(x,f(x))的切線來逼近方程x^2-a=0的根。根號a實際上就是x^2-a=0的一個正實根,這個函數的導數是2x。也就是說,函數上任一點(x,f(x))處的切線斜率是2x。那么,x-f(x)/(2x)就是一個比x更接近的近似值。代入 f(x)=x^2-a得到x-(x^2-a)/(2x),也就是(x+a/x)/2。

源地址: http://blog.renren.com/GetEntry.do?id=491777510&owner=245298353

?

2010-09-30 19:48:39
雷Sir

非常好奇這位天才是如何找到這個數值的

2011-09-24 10:58:20
jarodChange (人生在世 吃喝二字)

前輩牛逼人

2011-09-24 19:09:10
夢斷代碼 (夏天是時間的分隔符。)

膜拜

2011-09-25 21:25:10
S.A.M (千百次修訂)

數學的暴力。。

2011-09-25 22:14:48
hd熊貓人 (三更有夢書當枕。)

無聊的時候窮舉的,我想。

2011-09-25 22:19:29
S.A.M (千百次修訂)

素認為,密碼心理學就是提高窮舉的命中概率。

2012-06-05 10:36:54
光之翼

剛讀到這段代碼,膜拜

[轉]Quake-III代碼里神奇的浮點開方函數


更多文章、技術交流、商務合作、聯系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯系: 360901061

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!!!

發表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 国产成人成人一区二区 | 在线看污网站 | 婷婷在线观看视频 | 四虎成人精品在永久免费 | 色老头xxxwww作爱视频 | 免费视频一区二区性色 | 中国jizz日本| 久久一二| 亚洲精品国产第一综合99久久 | 91国在线 | 国产一区二区三区不卡在线观看 | 国产精品成人四虎免费视频 | 九九热这里只有国产精品 | 涩涩99 | 久久综合精品不卡一区二区 | 久久机热re这里只有精品15 | 亚洲欧美日本另类 | 亚洲激情视频网 | 伊人成人在线视频 | 欧美综合网 | 亚洲国产成人精品一区91 | 久久天堂网 | 九色国产 | 国产一区二区三区不卡免费观看 | 久久免费看| 亚洲国产品综合人成综合网站 | 久久成人免费观看全部免费 | 在线视频不卡国产在线视频不卡 | 国产综合欧美 | 亚洲国产字幕 | 色老头xxxxbbbb视频 | 婷婷丁香亚洲 | 日韩在线视频一区二区三区 | 国产野花视频天堂视频免费 | 欧美一区二区三区在线可观看 | 91久久精品国产免费一区 | 奇米影视在线播放 | 欧美乱大交xxxxx在线观看 | 国产成人精品视频免费 | 午夜黄色毛片 | 四虎精品成人免费视频 |