開根號倒數速算法

作者: harp (豎琴海豹) 站內: CgGroup
標題: [閒聊][轉錄]開根號倒數 (1 / sqrt(x)) 速算法  (from ptt2)
時間: Thu Jan  4 19:17:17 2007

恩嗯....這應該跟我們超相關吧.....:P

=============================================
好可怕的奇技淫巧 !!

前兩天有一則新聞，大意是說 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

Technorati Tags: programming, optimization, math


以上來自於：http://blog.ijliao.info/archives/2006/12/04/2739/
HackMen的網址：http://home.pipeline.com/~hbaker1/hakmem/hakmem.html

[m
--
[1;32m※ Origin: [33mVisionBBS @ CSIE.NCKU [37m [m
[1;32m※ From  : [36mhandsome.csie.ncku.edu.tw [m
※ X-Info: NDark -> ndark@vision.csie.ncku.edu.tw
※ X-Sign: 12PQ1AKbqCUfEbAMYNBw (07/01/04 21:47:00 )