Edison.X. Blog

有時程式寫到一半的時候會想計算、查詢一些特定的常數，

這問題要解得好，不容易。先考慮一般比較簡單的情況，只考慮真分數，並以 32 / 99 為例 假設 Q=32

32 * 10 = 320 , 320 / 99 = (3) 餘 23

這是個讓 CS 領域驚豔的計算方式，同時裡面使用的 magic number -  0x5f3759df 拿去 google 可得到一狗票的東西，本文並不進行 magic number 之推導，整個推導最詳盡的，應是 這篇pdf 。一開始的原始碼長得像這樣 (轉自 wiki)

float Q_rsqrt( float number )
{
        long i;
        float x2, y;
        const float threehalfs = 1.5F;
 
        x2 = number * 0.5F;
        y  = number;
        i  = * ( long * ) &y;                       // evil floating point bit level hacking [sic]
        i  = 0x5f3759df - ( i >> 1 );               // what the fuck? [sic]
        y  = * ( float * ) &i;
        y  = y * ( threehalfs - ( x2 * y * y ) );   // 1st iteration
//    y  = y * ( threehalfs - ( x2 * y * y ) );   // 2nd iteration, this can be removed
 
        return y;
}

這陣子研究 math.h 與 bitwise 優化問題，找了很多資料後，發現其實別人寫好的 library 實在也很多，原本是要優化三角函式，最後還是只把觀念帶走，下次有空的時候再實際 coding 吧。以下為我找到的參考資料。

(1) Bit Twiddling Hacks