維基百科:優良條目/平方根倒數速算法
外觀
![](http://upload.wikimedia.org/wikipedia/commons/thumb/8/8d/Reflection_for_Semicircular_Mirror.svg/190px-Reflection_for_Semicircular_Mirror.svg.png)
反平方根快速演算法是用於快速計算(即的平方根的倒數,在此需取符合IEEE 754標準格式的32位浮點數)的一種算法。此算法最早可能是於90年代前期由SGI所發明,後來則於1999年在《雷神之錘III競技場》的原始碼中應用,但直到2002-2003年間才在Usenet一類的公共論壇上出現。這一算法的優勢在於減少了求平方根倒數時浮點運算操作帶來的巨大的運算耗費,而在電腦圖學領域,若要求取照明和投影的波動角度與反射效果,就常需計算平方根倒數。此算法首先接收一個32位帶符浮點數,然後將之作為一個32位整數看待,以將其向右進行一次邏輯移位的方式將之取半,並用十六進制「魔術數字」0x5f3759df減之,如此即可得對輸入的浮點數的平方根倒數的首次近似值;而後重新將其作為浮點數,以牛頓法反覆迭代,以求出更精確的近似值,直至求出符合精確度要求的近似值。在計算浮點數的平方根倒數的同一精度的近似值時,此算法比直接使用浮點數除法要快四倍。此算法最早被認為是由約翰·卡馬克所發明,但後來的調查顯示,該算法在這之前就於計算機圖形學的硬件與軟件領域有所應用,如SGI和3dfx就曾在產品中應用此算法。而就現在所知,此算法最早由Gary Tarolli在SGI Indigo的開發中使用。雖說隨後的相關研究也提出了一些可能的來源,但至今為止仍未能確切知曉算法中所使用的特殊常數的起源。