反平方根快速演算法 | 平方根算法
反平方根快速演算法(英語:FastInverseSquareRoot,亦常以「FastInvSqrt()」或其使用的十六進位常數0x5f3759df代稱)是用於快速計算x−1/2{displaystyleextstylex{-1/2}}(即x{displaystyleextstylex}的平方根的倒數,在此x{displaystyleextstylex}需取符合IEEE754標準格式的32位元浮點數)的一種演算法。此演算法最早可能是於90年代前期由SGI所發明,後來則於1999年在《雷神之鎚III競技場》的原始碼中應用,但直到2002-2003年間才在Usenet一類的公共論壇上出現[1]。這一演算法的優勢在於減少了求平方根倒數時浮點運算操作帶來的巨大...
反平方根快速演算法(英語:Fast Inverse Square Root,亦常以「Fast InvSqrt()」或其使用的十六進位常數0x5f3759df代稱)是用於快速計算x−1/2{displaystyle extstyle x{-1/2}}(即x{displaystyle extstyle x}的平方根的倒數,在此x{displaystyle extstyle x}需取符合IEEE 754標準格式的32位元浮點數)的一種演算法。此演算法最早可能是於90年代前期由SGI所發明,後來則於1999年在《雷神之鎚III競技場》的原始碼中應用,但直到2002-2003年間才在Usenet一類的公共論壇上出現[1]。這一演算法的優勢在於減少了求平方根倒數時浮點運算操作帶來的巨大的運算耗費,而在電腦圖學領域,若要求取照明和投影的波動角度與反射效果,就常需計算平方根倒數。
此演算法首先接收一個32位元帶符浮點數,然後將之作為一個32位元整數看待,以將其向右進行一次邏輯移位的方式將之取半,並用在浮點數規格代表√2127近似值的十六進位「魔術數字」0x5f3759df減之,如此即可得對輸入的浮點數的平方根倒數的首次近似值;而後重新將其作為浮點數,以牛頓法反覆迭代,以求出更精確的近似值,直至求出符合精確度要求的近似值。在計算浮點數的平方根倒數的同一精度的近似值時,此演算法比直接使用浮點數除法要快四倍。
此演算法最早被認為是由約翰·卡馬克所發明,但後來的調查顯示,該演算法在這之前就於電腦圖學的硬體與軟體領域有所應用,如SGI和3dfx就曾在產品中應用此演算法。而就現在所知,此演算法最早由加里·塔羅利(Gary Tarolli)在SGI Indigo的開發中使用。雖說隨後的相關研究也提出了一些可能的來源,但至今為止仍未能確切知曉演算法中所使用的特殊常數的起源。
演算法的切入點[編輯] 法線常在光影效果實現計算時使用,而這就涉及到向量範數的計算。圖中所標識的就是與一個面所垂直的一些向量的集合。浮點數的平方根倒數常用於計算正規化向量。3D圖形程式需要使用正規化向量來實現光照和投影效果,因此每秒都需做上百萬次平方根倒數運算,而在處理坐標轉換與光源的專用硬體裝置出現前,這些計算都由軟體完成,計算速度亦相當之...