Fast Inverse Square Root 手動推導過程紀錄

來源

https://www.youtube.com/watch?v=p8u_k2LIZyo

IEE 754

https://www.h-schmidt.net/FloatConverter/IEEE754.html

Mantissa is

$M$
Exponent is

$E$

$$2^{23}\cdot E+M$$

$$(1+{\displaystyle \frac{M}{2^{23}}})\cdot 2^{E-127}$$
取

$lo{g}_2$

$${\log }_2((1+{\displaystyle \frac{M}{2^{23}}})\cdot 2^{E-127})$$
化簡

$${\log }_2(1+{\displaystyle \frac{M}{2^{23}}})+{\log }_2(2^{E-127})$$

$${\log }_2(1+{\displaystyle \frac{M}{2^{23}}})+(E-127)$$
quake 的作者利用數學上的技巧偷了一點近似值
當x 數字很小的時候就越接近x 自己，當x 在 0 到 1 之間
加上

$\mu$變數，可以調整這個範圍減少整體的平均面積(總之就是減少整體誤差)

$${\log }_2(1+x)\approx x+\mu$$

繼續化簡

$${\displaystyle \frac{M}{2^{23}}}+\mu +(E-127)$$

變化一下

$${\displaystyle \frac{M}{2^{23}}}+E+\mu -127$$

$${\displaystyle \frac{M}{2^{23}}}+{\displaystyle \frac{E\cdot 2^{23}}{2^{23}}}+\mu -127$$

$${\displaystyle \frac{M+(E)\cdot 2^{23}}{2^{23}}}+\mu -127$$

$${\displaystyle \frac{(M\cdot 1)+(E\cdot 1\cdot 2^{23})}{2^{23}}}+\mu -127$$

$${\displaystyle \frac{1}{2^{23}}}\cdot (M+E\cdot 2^{23})+\mu -127$$

所以跟上面的IEEE 754 找到相同的

$2^{23}\cdot E+M$
就是代表跟

$lo{g}_2(2^{23}\cdot E+M)\approx (2^{23}\cdot E+M)$

把IEEE 754 的float 數字當作long 來操作，但是不進行轉換

得到記憶體位置，然後把整體當作long 的樣子來操作，最後取值。

介紹一下基本知識

$$\begin{gathered} x^2=x\cdot x \\ {x}^{-1}={\displaystyle \frac{1}{x}} \\ {x}^{{\displaystyle \frac{1}{2}}}=\sqrt{x} \\ {x}^{-{\displaystyle \frac{1}{2}}}={\displaystyle \frac{1}{\sqrt{x}}} \\ i=\log (y) \\ 4=(8>>1) \\ \frac{1}{2}x=(x>>1) \\ \log ({\displaystyle \frac{1}{\sqrt{y}}}0=\log (y^{-{\displaystyle \frac{1}{2}}}))=-{\displaystyle \frac{1}{2}}\log (y)=-(i>>1) \end{gathered}$$

magic number 的主要計算過程

$$\mathrm{\Gamma }=(1+{\displaystyle \frac{M_{\mathrm{\Gamma }}}{2^{23}}})\cdot 2^{E_{\mathrm{\Gamma }}-127}$$

$$y=(1+{\displaystyle \frac{M_y}{2^{23}}})\cdot 2^{E_y-127}$$

$$\log (\mathrm{\Gamma })=-{\displaystyle \frac{1}{2}}\log (y)$$

$${\displaystyle \frac{1}{2^{23}}}\cdot (M_{\mathrm{\Gamma }}+E_{\mathrm{\Gamma }}\cdot 2^{23})+\mu -127=-{\displaystyle \frac{1}{2}}\cdot ((1+{\displaystyle \frac{M_y}{2^{23}}})\cdot 2^{E_y-127})$$

然後想要求解的是:

$(M_{\mathrm{\Gamma }}+E_{\mathrm{\Gamma }}\cdot 2^{23})$

$$(M_{\mathrm{\Gamma }}+E_{\mathrm{\Gamma }}\cdot 2^{23})={\displaystyle \frac{3}{2}}\cdot 2^{23}\cdot (127-\mu )-{\displaystyle \frac{1}{2}}((M_y+E_y\cdot 2^{23}))$$

當中魔法數字：

${\displaystyle \frac{3}{2}}\cdot 2^{23}\cdot (127-\mu )$
向右位移：

$-{\displaystyle \frac{1}{2}}((M_y+E_y\cdot 2^{23}))=-(i>>1)$
輸入：

$(M_y+E_y\cdot 2^{23})=i$

牛頓接近法