快速平方根倒數演算法常數

❶ 平方根倒數速演算法的演算法的切入點

浮點數的平方根倒數常用於計算正規化矢量。 3D圖形程序需要使用正規化矢量來實現光照和投影效果，因此每秒都需做上百萬次平方根倒數運算，而在處理坐標轉換與光源的專用硬體設備出現前，這些計算都由軟體完成，計算速度亦相當之慢；在1990年代這段代碼開發出來之時，多數浮點數操作的速度更是遠遠滯後於整數操作，因而針對正規化矢量演算法的優化就顯得尤為重要。下面陳述計算正規化矢量的原理：
要將一個矢量標准化，就必須計算其歐幾里得范數以求得矢量長度，而這時就需對矢量的各分量的平方和求平方根；而當求取到其長度並以之除該矢量的每個分量後，所得的新矢量就是與原矢量同向的單位矢量，若以公式表示： 可求得矢量v的歐幾里得范數，此演算法正類如對歐幾里得空間的兩點求取其歐幾里得距離， 而求得的就是標准化的矢量，若以代表，則有， 可見標准化矢量時需要用到對矢量分量的平方根倒數計算，所以對平方根倒數計算演算法的優化對計算正規化矢量也大有裨益。
為了加速圖像處理單元計算，《雷神之錘III競技場》使用了平方根倒數速演算法，而後來採用現場可編程邏輯門陣列的頂點著色器也應用了此演算法。

❷ 平方根倒數速演算法的歷史與考究

《雷神之錘III》的代碼直到QuakeCon 2005才正式放出，但早在2002年（或2003年）時平方根倒數速演算法的代碼就已經出現在Usenet與其他論壇上了。最初人們猜測是卡馬克寫下了這段代碼，但他在詢問郵件的回復中否定了這個觀點，並猜測可能是先前曾幫id Software優化雷神之錘的資深匯編程序員Terje Mathisen寫下了這段代碼；而在Mathisen的郵件里他表示在1990年代初他只曾作過類似的實現，確切來說這段代碼亦非他所作。現在所知的最早實現是由Gary Tarilli在SGI Indigo中實現的，但他亦坦承他僅對常數R的取值做了一定的改進，實際上他也不是作者。Rys Sommefeldt則在向以發明MATLAB而聞名的Cleve Moler查證後認為原始的演算法是Ardent Computer公司的Greg Walsh所發明，但他也沒有任何決定性的證據能證明這一點。
目前不僅該演算法的原作者不明，人們也仍無法明確當初選擇這個「魔術數字」的方法。Chris Lomont在研究中曾做了個試驗：他編寫了一個函數，以在一個范圍內遍歷選取R值的方式將逼近誤差降到最小，以此方法他計算出了線性近似的最優R值0x5f37642f（與代碼中使用的0x5f3759df相當接近），但以之代入演算法計算並進行一次牛頓迭代後，所得近似值與代入0x5f3759df的結果相比精度卻仍略微更低；而後Lomont將目標改為遍歷選取在進行1－2次牛頓迭代後能得到最大精度的R值，並由此算出最優R值為0x5f375a86，以此值代入演算法並進行牛頓迭代後所得的結果都比代入原始值（0x5f3759df）更精確，於是他的論文最後以「原始常數是以數學推導還是以反復試錯的方式求得」的問題作結。在論文中Lomont亦指出64位的IEEE754浮點數（即雙精度類型）所對應的魔術數字是0x5fe6ec85e7de30da，但後來的研究表明代入0x5fe6eb50c7aa19f9的結果精確度更高（McEniry得出的結果則是0x5FE6EB50C7B537AA，精度介於兩者之間）。在Charles McEniry的論文中，他使用了一種類似Lomont但更復雜的方法來優化R值：他最開始使用窮舉搜索法，所得結果與Lomont相同；而後他嘗試用帶權二分法尋找最優值，所得結果恰是代碼中所使用的魔術數字0x5f3759df，因此McEniry確信這一常數或許最初便是以「在可容忍誤差范圍內使用二分法」的方式求得。

❸ 平方根的倒數用c語言怎麼表示

平方根的倒數用c語言用double sqrt(double)表示。

C語言中平方根的函數是：double sqrt(double)；參數介紹：（）中是double，返回值可能是double 也可能是int；該函數頭文件：math.h；該函數功能： 計算一個非負實數的平方根；說明：sqrt系Square Root Calculations（平方根計算），通過這種運算可以考驗CPU的浮點能力。

結論：

被開方數越大，對應的算術平方根也越大（對所有正數都成立）。一個正數如果有平方根，那麼必定有兩個，它們互為相反數。顯然，如果知道了這兩個平方根的一個，那麼就可以及時的根據相反數的概念得到它的另一個平方根。

❹ 平方根的倒數怎麼算呀

解：通項：1/(√n) （其中n>0）
分子，分母同時乘以√n,即：
1/(√n) = （√n) /[（√n)*（√n)]=（√n)/n(即n分之根號下n的意思)

因此像平方根3的倒數就是√3/3 （3分之根號下3）,不知你明白了沒？

❺ 算術平方根的演算法

數的開方是一種運算，一個正數有兩個平方根，這兩個平方根互為相反數，記作
，零的平方根是零，負數沒有平方根。正數a的正的平方根，也叫做a的算術平方根，記作
，零的算術平方根仍舊是零，也就是在算術平方根的記號
中，a可以是正數，也可以是零，即a為非負數，平方根與算術平方根有相似之處，容易混淆，它們的相同點是被開方數都必須是非負數，並且零的平方根與算術平方根都是零，當a表示正數時，只要求出a的算術平方根
，便可知a的負平方根
，因此，可馬上求出a的平方根，但它們又有本質的區別，正數a的平方根為
，是正負兩個值，而算術平方根是兩個值中的正值
，即算術平方根是一個非負數。

❻ 《微微一笑很傾城》中肖奈大神說的平方根倒數速演算法是什麼鬼

平方根倒數速演算法

平方根倒數速演算法是適用於快速計算（積的平方根的倒數，在此需取符合IEEE 754標准格式的32位浮點數）的一種演算法。

平方根倒數速演算法（英語：Fast Inverse Square Root，亦常以「Fast InvSqrt()」或其使用的十六進制常數0x5f3759df代稱）是用於快速計算（積的平方根的倒數，在此需取符合IEEE 754標准格式的32位浮點數）的一種演算法。此演算法最早可能是於90年代前期由SGI所發明，後來則於1999年在《雷神之錘III競技場》的源代碼中應用，但直到2002－2003年間才在Usenet一類的公共論壇上出現。這一演算法的優勢在於減少了求平方根倒數時浮點運算操作帶來的巨大的運算耗費，而在計算機圖形學領域，若要求取照明和投影的波動角度與反射效果，就常需計算平方根倒數。

此演算法首先接收一個32位帶符浮點數，然後將之作為一個32位整數看待，以將其向右進行一次邏輯移位的方式將之取半，並用十六進制「魔術數字」0x5f3759df減之，如此即可得對輸入的浮點數的平方根倒數的首次近似值；而後重新將其作為浮點數，以牛頓法反復迭代，以求出更精確的近似值，直至求出符合精確度要求的近似值。在計算浮點數的平方根倒數的同一精度的近似值時，此演算法比直接使用浮點數除法要快四倍。

中文名

平方根倒數速演算法

外文名

Fast Inverse Square Root

定義

適用於快速計算的一種演算法

備注

最早被認為由約翰·卡馬克所發明

❼ 平方根倒數速演算法的注釋

由於現代計算機系統對長整型的定義有所差異，使用長整型會降低此段代碼的可移植性。具體來說，由此段浮點轉換為長整型的定義可知，如若這段代碼正常運行，所在系統的長整型長度應為4位元組（32位），否則重新轉為浮點數時可能會變成負數；而由於C99標準的廣泛應用，在現今多數64位計算機系統（除使用LLP64數據模型的Windows外）中，長整型的長度都是8位元組。 此處「浮點數」所指為標准化浮點數，也即有效數字部分必須滿足，可參見David Goldberg. What Every Computer Scientist Should Know About Floating-Point Arithmetic. ACM Computing Surveys. 1991.March, 23 (1): 5–48. doi:10.1145/103162.103163. Lomont 2003確定R的方式則有所不同，他先將R分解為與，其中與分別代表R的有效數字域和指數域。

❽ 怎麼計算某數的平方根

如果一個數的開方是無理數. 直接就用：

如√20即簡寫，不必具體寫出該數.

平方根就是開二次方運算的值. 它的逆運算就是乘二次方.

//
// 計算參數x的平方根的倒數
//
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;
}
該演算法的本質其實就是牛頓迭代法（Newton-Raphson Method，簡稱NR），而NR的基礎則是泰勒級數（Taylor Series）。NR是一種求方程的近似根的方法。首先要估計一個與方程的根比較靠近的數值，然後根據公式推算下一個更加近似的數值，不斷重復直到可以獲得滿意的精度。其公式如下：

函數：y=f(x)

其一階導數為：y'=f'(x)

則方程：f(x)=0 的第n+1個近似根為

x[n+1] = x[n] - f(x[n]) / f'(x[n])
NR最關鍵的地方在於估計第一個近似根。如果該近似根與真根足夠靠近的話，那麼只需要少數幾次迭代，就可以得到滿意的解。

現在回過頭來看看如何利用牛頓法來解決我們的問題。求平方根的倒數，實際就是求方程1/(x^2)-a=0的解。將該方程按牛頓迭代法的公式展開為：

x[n+1]=1/2*x[n]*(3-a*x[n]*x[n])
將1/2放到括弧裡面，就得到了上面那個函數的倒數第二行。

接著，我們要設法估計第一個近似根。這也是上面的函數最神奇的地方。它通過某種方法算出了一個與真根非常接近的近似根，因此它只需要使用一次迭代過程就獲得了較滿意的解。它是怎樣做到的呢？所有的奧妙就在於這一行：

i = 0x5f3759df - (i >> 1); // 計算第一個近似根
超級莫名其妙的語句，不是嗎？但仔細想一下的話，還是可以理解的。我們知道，IEEE標准下，float類型的數據在32位系統上是這樣表示的（大體來說就是這樣，但省略了很多細節，有興趣可以GOOGLE）：

bits：31 30 ... 0
31：符號位
30-23：共8位，保存指數（E）
22-0：共23位，保存尾數（M）
所以，32位的浮點數用十進制實數表示就是：M*2^E。開根然後倒數就是：M^(-1/2)*2^(-E/2)。現在就 十分清晰了。語句i>>1其工作就是將指數除以2，實現2^(E/2)的部分。而前面用一個常數減去它，目的就是得到M^(1/2)同時反轉所有指數的符號。

至於那個0x5f3759df，呃，我只能說，的確是一個超級的Magic Number。

那 個Magic Number是可以推導出來的，但我並不打算在這里討論，因為實在太繁瑣了。簡單來說，其原理如下：因為IEEE的浮點數中，尾數M省略了最前面的1，所以實際的尾數是1+M。如果你在大學上數學課沒有打瞌睡的話，那麼當你看到(1+M)^(-1/2)這樣的形式時，應該會馬上聯想的到它的泰勒級數展開， 而該展開式的第一項就是常數。下面給出簡單的推導過程：

對於實數R>0，假設其在IEEE的浮點表示中，
指數為E，尾數為M，則：

R^(-1/2)
= (1+M)^(-1/2) * 2^(-E/2)

將(1+M)^(-1/2)按泰勒級數展開，取第一項，得：

原式
= (1-M/2) * 2^(-E/2)
= 2^(-E/2) - (M/2) * 2^(-E/2)

如果不考慮指數的符號的話，
(M/2)*2^(E/2)正是(R>>1)，
而在IEEE表示中，指數的符號只需簡單地加上一個偏移即可，
而式子的前半部分剛好是個常數，所以原式可以轉化為：

原式 = C - (M/2)*2^(E/2) = C - (R>>1)，其中C為常數

所以只需要解方程：
R^(-1/2)
= (1+M)^(-1/2) * 2^(-E/2)
= C - (R>>1)
求出令到相對誤差最小的C值就可以了

上面的推導過程只是我個人的理解，並未得到證實。而Chris Lomont則在他的論文中詳細討論了最後那個方程的解法，並嘗試在實際的機器上尋找最佳的常數C。有興趣的朋友可以在文末找到他的論文的鏈接。

所以，所謂的Magic Number，並不是從N元宇宙的某個星系由於時空扭曲而掉到地球上的，而是幾百年前就有的數學理論。只要熟悉NR和泰勒級數，你我同樣有能力作出類似的優化。

在GameDev.net上有人做過測試，該函數的相對誤差約為0.177585%，速度比C標准庫的sqrt提高超過20%。如果增加一次迭代過程，相對誤差可以降低到e-004 的級數，但速度也會降到和sqrt差不多。據說在DOOM3中，Carmack通過查找表進一步優化了該演算法，精度近乎完美，而且速度也比原版提高了一截（正在努力弄源碼，誰有發我一份）。

值得注意的是，在Chris Lomont的演算中，理論上最優秀的常數（精度最高）是0x5f37642f，並且在實際測試中，如果只使用一次迭代的話，其效果也是最好的。但奇怪的是，經過兩次NR後，在該常數下解的精度將降低得非常厲害（天知道是怎麼回事！）。經過實際的測試，Chris Lomont認為，最優秀的常數是0x5f375a86。如果換成64位的double版本的話，演算法還是一樣的，而最優常數則為0x5fe6ec85e7de30da（又一個令人冒汗的Magic Number - -b）。

這個演算法依賴於浮點數的內部表示和位元組順序，所以是不具移植性的。如果放到Mac上跑就會掛掉。如果想具備可移植性，還是乖乖用sqrt好了。但演算法思想是通用的。大家可以嘗試推算一下相應的平方根演算法。

下面給出Carmack在QUAKE3中使用的平方根演算法。Carmack已經將QUAKE3的所有源代碼捐給開源了，所以大家可以放心使用，不用擔心會收到律師信。

//
// Carmack在QUAKE3中使用的計算平方根的函數
//
float CarmSqrt(float x){
union{
int intPart;
float floatPart;
} convertor;
union{
int intPart;
float floatPart;
} convertor2;
convertor.floatPart = x;
convertor2.floatPart = x;
convertor.intPart = 0x1FBCF800 + (convertor.intPart >> 1);
convertor2.intPart = 0x5f3759df - (convertor2.intPart >> 1);
return 0.5f*(convertor.floatPart + (x * convertor2.floatPart));
}
另一個基於同樣演算法的更高速度的sqrt實現如下。其只是簡單地將指數除以2，並沒有考慮尾數的方根。要看懂該代碼的話必 須知道，在IEEE浮點數的格式中，E是由實際的指數加127得到的。例如，如果實數是0.1234*2^10，在浮點表示中，E（第23-30位）的值其實為10+127=137。所以下面的代碼中，要處理127偏移，這就是常數0x3f800000的作用。我沒實際測試過該函數，所以對其優劣無從評 論，但估計其精度應該會降低很多。

float Faster_Sqrtf(float f)
{
float result;
_asm
{
mov eax, f
sub eax, 0x3f800000
sar eax, 1
add eax, 0x3f800000
mov result, eax
}
return result;
}
除了基於NR的方法外，其他常見的快速演算法還有多項式逼近。下面的函數取自《3D游戲編程大師技巧》，它使用一個多項式來近似替代原來的長度方程，但我搞不清楚作者使用的公式是怎麼推導出來的（如果你知道的話請告訴我，謝謝）。

//
// 這個函數計算從(0,0)到(x,y)的距離，相對誤差為3.5%
//
int FastDistance2D(int x, int y)
{
x = abs(x);
y = abs(y);
int mn = MIN(x,y);
return(x+y-(mn>>1)-(mn>>2)+(mn>>4));
}
//
// 該函數計算(0,0,0)到(x,y,z)的距離，相對誤差為8%
//
float FastDistance3D(float fx, float fy, float fz)
{
int temp;
int x,y,z;
// 確保所有的值為正
x = int(fabs(fx) * 1024);
y = int(fabs(fy) * 1024);
z = int(fabs(fz) * 1024);
// 排序
if (y < x) SWAP(x,y,temp)
if (z < y) SWAP(y,z,temp)
if (y < x) SWAP(x,y,temp)
int dist = (z + 11 * (y >> 5) + (x >> 2) );
return((float)(dist >> 10));
}
還有一種方法稱為Distance Estimates（距離評估？），如下圖所示：

紅線所描繪的正八邊形上的點為：

octagon(x,y) = min((1/√2) * (|x|+|y|), max(|x|,|y|))
求出向量v1和v2的長度，則：

√(x^2+y^2) = (|v1|+|v2|)/2 * octagon(x,y)
到目前為止我們都在討論浮點數的方根演算法，接下來輪到整數的方根演算法。也許有人認為對整型數據求方根無任何意義，因為會得 到類似99^(1/2)=9的結果。通常情況下確實是這樣，但當我們使用定點數的時候（定點數仍然被應用在很多系統上面，例如任天堂的GBA之類的手持設備），整數的方根演算法就顯得非常重要。對整數開平方的演算法如下。我並不打算在這討論它（事實是我也沒有仔細考究，因為在短期內都不會用到- -b），但你可以在文末James Ulery的論文中找到非常詳細的推導過程。

//
// 為了閱讀的需要，我在下面的宏定義中添加了換行符
//
#define step(shift)
if((0x40000000l >> shift) + sqrtVal <= val)
{
val -= (0x40000000l >> shift) + sqrtVal;
sqrtVal = (sqrtVal >> 1) | (0x40000000l >> shift);
}
else
{
sqrtVal = sqrtVal >> 1;
}
//
// 計算32位整數的平方根
//
int32 xxgluSqrtFx(int32 val)
{
// Note: This fast square root function
// only works with an even Q_FACTOR
int32 sqrtVal = 0;
step(0);
step(2);
step(4);
step(6);
step(8);
step(10);
step(12);
step(14);
step(16);
step(18);
step(20);
step(22);
step(24);
step(26);
step(28);
step(30);
if(sqrtVal < val)
{
++sqrtVal;
}
sqrtVal <<= (Q_FACTOR)/2;
return(sqrtVal);
}

❾ 平方根倒數速演算法的介紹

平方根倒數速演算法最早被認為是由約翰·卡馬克所發明，但後來的調查顯示，該演算法在這之前就於計算機圖形學的硬體與軟體領域有所應用，如SGI和3dfx就曾在產品中應用此演算法。而就現在所知，此演算法最早由Gary Tarolli在SGI Indigo的開發中使用。雖說在隨後的相關研究中也提出了一些可能的來源，但至今為止仍未能確切知曉此常數的起源。

❿ 平方根倒數速演算法的將浮點數轉化為整數

要理解這段代碼，首先需了解浮點數的存儲格式。一個浮點數以32個二進制位表示一個有理數，而這32位由其意義分為三段：首先首位為符號位，如若是0則為正數，反之為負數；接下來的8位表示經過偏移處理（這是為了使之能表示-127－128）後的指數；最後23位表示的則是有效數字中除最高位以外的其餘數字。將上述結構表示成公式即為，其中表示有效數字的尾數（此處，偏移量，而指數的值決定了有效數字（在Lomont和McEniry的論文中稱為「尾數」（mantissa））代表的是小數還是整數。以上圖為例，將描述帶入有），且，則可得其表示的浮點數為。 符號位 0 1 1 1 1 1 1 1 = 127 0 0 0 0 0 0 1 0 = 2 0 0 0 0 0 0 0 1 = 1 0 0 0 0 0 0 0 0 = 0 1 1 1 1 1 1 1 1 = −1 1 1 1 1 1 1 1 0 = −2 1 0 0 0 0 0 0 1 = −127 1 0 0 0 0 0 0 0 = −128 8位二進制整數補碼示例
如上所述，一個有符號正整數在二進制補碼系統中的表示中首位為0，而後面的各位則用於表示其數值。將浮點數取別名存儲為整數時，該整數的數值即為，其中E表示指數，M表示有效數字；若以上圖為例，圖中樣例若作為浮點數看待有，，則易知其轉化而得的整數型號數值為。由於平方根倒數函數僅能處理正數，因此浮點數的符號位（即如上的Si）必為0，而這就保證了轉換所得的有符號整數也必為正數。以上轉換就為後面的計算帶來了可行性，之後的第一步操作（邏輯右移一位）即是使該數的長整形式被2所除。