[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!!