平方根倒數速演算法

① 平方根倒數速演算法

關於平方根倒數速演算法如下：

平方根倒數速演算法是適用於快速計算積的算術平方根（以下稱平方根）的倒數（在此需取符合IEEE754標准格式的32位浮點數）的一種演算法。此演算法最早可能是於90年代前期由SGI所發明，後來於1999年在雷神之錘III競技場的源代碼中應用，但直到2002－2003年間才在Usenet一類的公共論壇上出現。

演算法起源

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

如上所述，一個有符號正整數在二進制補碼系統中的表示中首位為0，而後面的各位則用於表示其數值。將浮點數取別名存儲為整數時，該整數的數值即為，其中E表示指數，M表示有效數字；若以上圖為例，圖中樣例若作為浮點數看待有，則易知其轉化而得的整數型號數值為。

由於平方根倒數函數僅能處理正數，因此浮點數的符號位（即如上的Si）必為0，而這就保證了轉換所得的有符號整數也必為正數。以上轉換就為後面的計算帶來了可行性，之後的第一步操作邏輯右移一位即是使該數的長整形式被2所除。