有人在Quake III的源代碼里面發(fā)現(xiàn)這么一段用來求平方根的代碼:
/*
================
SquareRootFloat
================
*/
float SquareRootFloat(float number) {
long i;
float x, y;
const float f = 1.5F;
x = number * 0.5F;
y = number;
i = * ( long * ) &y;
i = 0x5f3759df - ( i >> 1 ); //注意這一行
y = * ( float * ) &i;
y = y * ( f - ( x * y * y ) );
y = y * ( f - ( x * y * y ) );
return number * y;
}
0x5f3759df？ 這是個(gè)什么東西？ 學(xué)過數(shù)值分析就知道，算法里面求平方根一般采用的是無限逼近的方法，比如
牛頓迭代法，抱歉當(dāng)年我數(shù)值分析學(xué)的太爛，也講不清楚。簡單來說比如求5的平方根，選一個(gè)猜測值比如2，那么我們可以這么算
5/2 = 2.5; 2.5+2/2 = 2.25; 5/2.25 = xxx; 2.25+xxx/2 = xxxx ...
這樣反復(fù)迭代下去，結(jié)果必定收斂于sqrt(5)，沒錯(cuò)，一般的求平方根都是這么算的。而卡馬克的不同之處在于，他選擇了一個(gè)神秘的猜測值0x5f3759df作為起始，使得整個(gè)逼近過程收斂速度暴漲，對(duì)于Quake III所要求的精度10的負(fù)三次方，只需要一次迭代就能夠得到結(jié)果。
好吧，如果這還不算牛b，接著看。
普渡大學(xué)的數(shù)學(xué)家Chris Lomont看了以后覺得有趣，決定要研究一下卡馬克弄出來的這個(gè)猜測值有什么奧秘。Lomont也是個(gè)牛人，在精心研究之后從理論上也推導(dǎo)出一個(gè)最佳猜測值，和卡馬克的數(shù)字非常接近, 0x5f37642f。卡馬克真牛，他是外星人嗎？
傳奇并沒有在這里結(jié)束。Lomont計(jì)算出結(jié)果以后非常滿意，于是拿自己計(jì)算出的起始值和卡馬克的神秘?cái)?shù)字做比賽，看看誰的數(shù)字能夠更快更精確的求得平方根。結(jié)果是卡馬克贏了... 誰也不知道卡馬克是怎么找到這個(gè)數(shù)字的。
最后Lomont怒了，采用暴力方法一個(gè)數(shù)字一個(gè)數(shù)字試過來，終于找到一個(gè)比卡馬克數(shù)字要好上那么一丁點(diǎn)的數(shù)字，雖然實(shí)際上這兩個(gè)數(shù)字所產(chǎn)生的結(jié)果非常近似，這個(gè)暴力得出的數(shù)字是0x5f375a86。
Lomont為此寫下一篇論文，"Fast Inverse Square Root"。
John Carmack， ID的無價(jià)之寶。
來源blog：http://jan.yculblog.com/