平方根倒數速算法是適用於快速計算（積的平方根的倒數，在此需取符合IEEE 754標準格式的32位浮點數）的一種算法。
平方根倒數速算法（英語：Fast Inverse Square Root，亦常以“Fast InvSqrt()”或其使用的十六進制常數0x5f3759df代稱）是用於快速計算（積的平方根的倒數，在此需取符合IEEE 754標準格式的32位浮點數）的一種算法。此算法最早可能是於90年代前期由SGI所發明，後來則於1999年在《雷神之錘III競技場》的原始碼中套用，但直到2002－2003年間才在Usenet一類的公共論壇上出現。這一算法的優勢在於減少了求平方根倒數時浮點運算操作帶來的巨大的運算耗費，而在計算機圖形學領域，若要求取照明和投影的波動角度與反射效果，就常需計算平方根倒數。
此算法首先接收一個32位帶符浮點數，然後將之作為一個32位整數看待，以將其向右進行一次邏輯移位的方式將之取半，並用十六進制“魔術數字”0x5f3759df減之，如此即可得對輸入的浮點數的平方根倒數的首次近似值；而後重新將其作為浮點數，以牛頓法反覆疊代，以求出更精確的近似值，直至求出符合精確度要求的近似值。在計算浮點數的平方根倒數的同一精度的近似值時，此算法比直接使用浮點數除法要快四倍。
基本介紹
算法定義,算法切入,浮點化整,歷史考究,注釋信息,
算法定義
平方根倒數速算法最早被認為是由約翰·卡馬克所發明，但後來的調查顯示，該算法在這之前就於計算機圖形學的硬體與軟體領域有所套用，如SGI和3dfx就曾在產品中套用此算法。而就現在所知，此算法最早由Gary Tarolli在SGI Indigo的開發中使用。雖說在隨後的相關研究中也提出了一些可能的來源，但至今為止仍未能確切知曉此常數的起源。
算法切入
浮點數的平方根倒數常用於計算正規化矢量。3D圖形程式需要使用正規化矢量來實現光照和投影效果，因此每秒都需做上百萬次平方根倒數運算，而在處理坐標轉換與光源的專用硬體設備出現前，這些計算都由軟體完成，計算速度亦相當之慢；在1990年代這段代碼開發出來之時，多數浮點數操作的速度更是遠遠滯後於整數操作，因而針對正規化矢量算法的最佳化就顯得尤為重要。下面陳述計算正規化矢量的原理：
要將一個矢量標準化，就必須計算其歐幾里得範數以求得矢量長度，而這時就需對矢量的各分量的平方和求平方根；而當求取到其長度並以之除該矢量的每個分量後，所得的新矢量就是與原矢量同向的單位矢量，若以公式表示：
- 可求得矢量v的歐幾里得範數，此算法正類如對歐幾里得空間的兩點求取其歐幾里得距離，
- 而求得的就是標準化的矢量，若以代表，則有，
可見標準化矢量時需要用到對矢量分量的平方根倒數計算，所以對平方根倒數計算算法的最佳化對計算正規化矢量也大有裨益。
為了加速圖像處理單元計算，《雷神之錘III競技場》使用了平方根倒數速算法，而後來採用現場可程式邏輯門陣列的頂點著色器也套用了此算法。
浮點化整
要理解這段代碼，首先需了解浮點數的存儲格式。一個浮點數以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所除。
歷史考究
id Software創始人約翰·卡馬克《雷神之錘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確信這一常數或許最初便是以“在可容忍誤差範圍內使用二分法”的方式求得。
注釋信息
- 由於現代計算機系統對長整型的定義有所差異，使用長整型會降低此段代碼的可移植性。具體來說，由此段浮點轉換為長整型的定義可知，如若這段代碼正常運行，所在系統的長整型長度應為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的有效數字域和指數域。
