![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/5/53/OpenArena-Rocket.jpg/640px-OpenArena-Rocket.jpg&w=640&q=50)
反平方根快速演算法
用來求某個實數的平方根的倒數的演算法 / 維基百科,自由的 encyclopedia
反平方根快速演算法(英語:Fast Inverse Square Root,亦常以「Fast InvSqrt()」或其使用的十六進制常數0x5f3759df代稱)是用於快速計算(即
的平方根的倒數,在此
需取符合IEEE 754標準格式的32位元浮點數)的一種演算法。這一演算法的優勢在於減少了求平方根倒數時浮點運算操作帶來的巨大的運算耗費,而在電腦圖學領域,若要求取照明和投影的波動角度與反射效果,就常需計算平方根倒數。
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/5/53/OpenArena-Rocket.jpg/640px-OpenArena-Rocket.jpg)
此演算法首先接收一個32位元帶符浮點數,然後將之作為一個32位元整數看待,以將其向右進行一次邏輯移位的方式將之取半,並用在浮點數規格代表近似值的十六進制「魔術數字」0x5f3759df減之,如此即可得對輸入的浮點數的平方根倒數的首次近似值;而後重新將其作為浮點數,以牛頓法反覆迭代,以求出更精確的近似值,直至求出符合精確度要求的近似值。在計算浮點數的平方根倒數的同一精度的近似值時,此演算法比直接使用浮點數除法要快四倍。
此演算法最早被認為是由約翰·卡馬克於90年代前期在SGI Indigo(英語:SGI Indigo)的開發中使用,後來則於1999年在《雷神之鎚III競技場》的原始碼中應用,但直到2002-2003年間才在Usenet一類的公共討論區上出現[1]。後來的調查顯示,該演算法在這之前就於電腦圖學的硬件與軟件領域有所應用,如SGI和3dfx就曾在產品中應用此演算法,但至今為止仍未能確切知曉演算法中所使用的特殊常數的起源。