開根號倒數 (InvSqrt(), 1 / sqrt(x)) 速算法

4 十二月, 2006 (12:54) | 電腦與網路

好可怕的奇技淫巧 !!

前兩天有一則新聞，大意是說 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 (有人整理了一份列表)。

PS3. 看到像這樣的強者，就更覺得我們根本就只是混飯吃的打字工人而已，離 Programmer 還差個十萬八千里啊… orz

2006/12/21 Update : 有續集，追到 Greg Walsh，他跑去 slashdot 上面留言了。

Technorati Tags: , ,

Comments

Trackback from Beyond Belief
Date: 2006/12/4, 6:43 下午

Fast InvSqrt()…

寫程式的人喜歡看別人的 code，一來增進功力，二來也可以收為己用
當見到短小精幹，卻有妙用無窮的碼，除了歡喜讚嘆，也有很大的好奇心想知道出自於何人之手，期見大師之風範
Fast InvS…

Comment from jjgod
Date: 2006/12/4, 9:27 下午

MIT 这份文件，其中绝大多数已经没有意义了吧。

Pingback from InvSqrt at 維尼的蜂巢
Date: 2006/12/4, 11:46 下午

[...] 今天看到這個http://blog.ijliao.info/archives/2006/12/04/2739/ [...]

Pingback from fcamel / chlo’s Blog » 2006-12-05 Miscellaneous Information
Date: 2006/12/5, 12:50 上午

[...] 1/sqrt(x)的奇技：話說很

Comment from william
Date: 2006/12/5, 12:09 下午

文中的「Quack III」應該改為「Quake III」。

Comment from food.poison
Date: 2006/12/5, 3:47 下午

假如說是 Quake III 的 code 話, 八成是 John Carmack 寫的…

找了一下, 似乎真的是:
http://www.codemaestro.com/reviews/review00000105.html

Comment from ijliao
Date: 2006/12/5, 4:08 下午

您一定沒去看那篇追追追 :p
他有寫信去問 John Carmack，結果不是…

Trackback from Neko的音樂心情日記
Date: 2006/12/6, 10:42 下午

0×5f3759df 追追追…

朋友今天丟給我一個網址：
http://www.beyond3d.com/articles/fastinvsqrt/

大意是有人想追查出這段令人嘆為觀止…

Trackback from electronic_blue
Date: 2006/12/10, 5:34 下午

Square Root Reciprocal…

今天看到了這篇文章：「開根號倒數 (InvSqrt(), 1 / sqrt(x)) 速算法」，本著科學家求真的態度，還是決定來實際測測看它直接用 sqrt() 的差別。

測試碼如下：
void inv_sqrt_v1(float* begin, float* end, floa…

Comment from tyuan
Date: 2006/12/13, 6:08 下午

我如果沒記錯，我讀大學時看過一本書裡面有一堆數學函數的速算法。我想這技巧應該不稀奇啦。不過我太多年沒走這行了，許多事不是記得很清楚了。

現在算這種東西應該不需要這樣解了吧，CPU裡都有硬體在解了。

Pingback from Victor’s Blog » InvSqrt()
Date: 2006/12/15, 7:51 下午

[...] 看到開

Write a comment