Kaie"s Blog 2.0 beta!
Back to "Top"

My Secret Notebook
 Show "Table of Contents"
Contact Me
Subscribe to my Posts feed
Subscribe to my Comments feed
My Flickr
Back to "Top"
My Secret Notebook
 Show "Table of Contents"
Contact Me
Subscribe to my Posts feed
Subscribe to my Comments feed
My Flickr

Tuesday, December 12, 2006

[Programming] Quake3's Fast InvSqrt()

今天在「苦牢之最後一年」這個Blog中看到了一篇我很感興趣的文章,「開根號倒數 (InvSqrt(), 1 / sqrt(x)) 速算法」,看完的心得果真如原PO所說的:好可怕的奇技淫巧!! XD

.Fast InvSqrt 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;
}
話說上面那段Code,比原本用sqrt()去實作出來的功能快上四倍左右!!
PS. 這個 function 之所以重要,是因為求 開根號倒數 這個動作在 3D 運算 (向量運算的部份) 裡面常常會用到,如果你用最原始的 sqrt() 然後再倒數的話,速度比上面的這個版本大概慢了四倍吧… XD -- 引用自: 開根號倒數 (InvSqrt(), 1 / sqrt(x)) 速算法

又再次見識到真正的Programmer,能夠把這麼基本、常用的指令,提升這麼多的效率,果真不是蓋的...要是當初沒這指令的話,我想Quake3要跑得動,可能要再延後個一年半載吧...XD

後來這個人 Shan-yung Yang 本著科學家追根究底的態度,直接來個實作,真是好樣的,數據出來後,更具說服力了! 原始文章在這: Square Root Reciprocal,作者有提供Source Code,可供下載測試...^_^

並且,重點是他也實作了另一個透過CPU支援的SSE指令集版本( CPU: Athlon64 X2 4400+ ),發現SSE這個指令的版本更快(大約比一般的 sqrt() 快十五倍左右),結論是:隨著architecture 的演進所造成的影響,也許十年後直接用 sqrt() 才是最快的方法..XD!!

2 Comments:

Who: Anonymous Class:
When: August 30, 2007 8:45 AM  

For a better explanation about this, check out http://www.mceniry.net/papers/Fast%20Inverse%20Square%20Root.pdf

Who: Tsung-Kai Chen Class:
When: August 30, 2007 9:05 AM  

To Anonymous:
Thanks for your information ...