Edison.X. Blog

 
有時程式寫到一半的時候會想計算、查詢一些特定的常數，
像是 PI ( acos(-1.0) 最準 ) , 根號 PI , ln(2) 等等，
一些被包含在 cmath 裡，一些沒有，

 

題目敘述
 

這問題要解得好，不容易。先考慮一般比較簡單的情況，只考慮真分數，並以 32 / 99 為例 假設 Q=32
32 * 10 = 320 , 320 / 99 = (3) 餘 23
23 * 10 = 230 , 230 / 99 = (2) 餘 32

這是個讓 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
http://www-graphics.stanford.edu/~seander/bithacks.html
這篇文章在探討 bitwise 操作，裡面有提出許多平常運算加速之方式，但建議要用的話還是包成 function 或 marco 再使用, 不然會看不懂。