John Carmack在Quake III源代碼中有一個特殊的功能，它計算浮點的平方根，比常規的快4倍(float)(1.0/sqrt(x))，包括一個奇怪的0x5f3759df常量。請參閱下面的代碼。有人可以逐行解釋這里究竟發生了什么以及為什么這比常規實現快得多？float Q_rsqrt( float number ){ long i; float x2, y; const float threehalfs = 1.5F; x2 = number * 0.5F; y = number; i = * ( long * ) &y; i = 0x5f3759df - ( i >> 1 ); y = * ( float * ) &i; y = y * ( threehalfs - ( x2 * y * y ) ); #ifndef Q3_VM #ifdef __linux__ assert( !isnan(y) ); #endif #endif return y;}
3 回答
慕勒3428872
TA貢獻1848條經驗 獲得超6個贊
僅供參考?？R克沒有寫下來。Terje Mathisen和Gary Tarolli都為此獲得了部分（并且非常適度）的信用，并且還記入其他一些來源。
這個神話常數是如何產生的，這是一個神秘的東西。
引用加里塔羅利：
實際上這是以整數形式進行浮點計算 - 花了很長時間才弄清楚這是如何以及為什么這樣做的，我不記得細節了。
由專家數學家（Chris Lomont）開發的一個稍好的常數，試圖弄清楚原始算法是如何工作的：
float InvSqrt(float x)
{
float xhalf = 0.5f * x;
int i = *(int*)&x; // get bits for floating value
i = 0x5f375a86 - (i >> 1); // gives initial guess y0
x = *(float*)&i; // convert bits back to float
x = x * (1.5f - xhalf * x * x); // Newton step, repeating increases accuracy
return x;
}
盡管如此，他最初嘗試的數學'上級'版本的id's sqrt（幾乎相同的常數）證明不如最初由加里開發的版本，盡管在數學上更“純粹”。他無法解釋為什么id是如此優秀的iirc。
狐的傳說
TA貢獻1804條經驗 獲得超3個贊
當然，最近發現它比僅僅使用FPU的sqrt（特別是在360 / PS3上）要慢得多，因為在float和int寄存器之間進行交換會導致load-hit-store，而浮點單元可以做倒數平方根源于硬件。
它只是展示了隨著底層硬件性質的變化，優化必須如何發展。
繁花不似錦
TA貢獻1851條經驗 獲得超4個贊
Greg Hewgill和IllidanS4給出了一個很好的數學解釋鏈接。對于那些不想過多介紹細節的人，我會在這里總結一下。
除了一些例外，任何數學函數都可以用多項式和來表示：
y = f(x)
可以完全轉化為：
y = a0 + a1*x + a2*(x^2) + a3*(x^3) + a4*(x^4) + ...
其中a0，a1，a2，...是常數。問題是對于許多函數，比如平方根，對于精確值，這個和有無限數量的成員，它不會在某個x ^ n處結束。但是，如果我們停在某個x ^ n處，我們仍然會得到一些精確度的結果。
所以，如果我們有：
y = 1/sqrt(x)
在這種特殊情況下，他們決定丟棄所有超過秒的多項式成員，可能是因為計算速度：
y = a0 + a1*x + [...discarded...]
現在，任務已經下降到計算a0和a1，以便y與精確值的差異最小。他們計算出最合適的值是：
a0 = 0x5f375a86
a1 = -0.5
所以，當你把它變成等式時，你得到：
y = 0x5f375a86 - 0.5*x
這與您在代碼中看到的行相同：
i = 0x5f375a86 - (i >> 1);
編輯：實際上這里y = 0x5f375a86 - 0.5*x不一樣，i = 0x5f375a86 - (i >> 1);因為將float移動為整數不僅除以2而且將指數除以2并導致其他一些偽影，但它仍然歸結為計算一些系數a0，a1，a2 ......。
在這一點上，他們發現這個結果的精度不足以達到目的。所以他們另外只做了牛頓迭代的一步來提高結果的準確性：
x = x * (1.5f - xhalf * x * x)
他們本可以在一個循環中完成一些迭代，每個迭代都會改進結果，直到滿足所需的精度。這正是它在CPU / FPU中的工作原理！但似乎只有一次迭代就足夠了，這也是對速度的祝福。CPU / FPU根據需要進行盡可能多的迭代，以達到存儲結果的浮點數的精度，并且它具有適用于所有情況的更通用的算法。
簡而言之，他們所做的是：
使用（差不多）與CPU / FPU相同的算法，利用1 / sqrt（x）的特殊情況下的初始條件的改進，并且不計算精確CPU / FPU的所有方式將轉到但更早停止，因此獲得計算速度。
添加回答
舉報
0/150
提交
取消