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