# Fast Inverse Square Root 手動推導過程紀錄 ## 來源 https://www.youtube.com/watch?v=p8u_k2LIZyo ### IEEE 754 https://www.h-schmidt.net/FloatConverter/IEEE754.html Mantissa is$M$ Exponent is$E$ $$ 2^{23} \cdot E + M$$ $$ (1 + \dfrac{M}{2^{23}}) \cdot 2 ^ {E-127} $$ 取$log_2$ $$ \log_{2}((1 + \dfrac{M}{2^{23}}) \cdot 2 ^ {E-127}) $$ 化簡 $$ \log_{2}(1 + \dfrac{M}{2^{23}}) + \log_{2}(2 ^ {E-127}) $$ $$ \log_{2}(1 + \dfrac{M}{2^{23}}) + (E-127) $$ quake 的作者利用數學上的技巧偷了一點近似值 當x 數字很小的時候就越接近x 自己，當x 在 0 到 1 之間 加上$\mu$變數，可以調整這個範圍減少整體的平均面積(總之就是減少整體誤差) $$ \log_{2}(1+x) \approx x + \mu $$ ![](https://i.imgur.com/1sV0FDR.png) 繼續化簡 $$ \dfrac{M}{2^{23}} + \mu + (E-127) $$ 變化一下 $$ \dfrac{M}{2^{23}} + E + \mu - 127 $$ $$ \dfrac{M}{2^{23}} + \dfrac{E \cdot 2^{23}}{ 2^{23}} + \mu - 127 $$ $$ \dfrac{M + (E) \cdot 2^{23}}{ 2^{23}} + \mu - 127 $$ $$ \dfrac{(M \cdot 1) + (E \cdot 1 \cdot 2^{23})}{ 2^{23}} + \mu - 127 $$ $$ \dfrac{1}{2^{23}}\cdot(M+E \cdot 2^{23}) + \mu - 127 $$ 所以跟上面的IEEE 754 找到相同的$2^{23} \cdot E + M$ 就是代表跟$log_2(2^{23} \cdot E + M) \approx (2^{23} \cdot E + M)$ ### 把IEEE 754 的float 數字當作long 來操作，但是不進行轉換 得到記憶體位置，然後把整體當作long 的樣子來操作，最後取值。 ![](https://i.imgur.com/TZNgANn.png) ## 介紹一下基本知識 $$ x ^ {2} = x \cdot x \\ x ^ {-1} = \dfrac{1}{x} \\ x ^ {\dfrac{1}{2}} = \sqrt{x} \\ x ^ {-\dfrac{1}{2}} = \dfrac{1}{\sqrt{x}}\\ i = \log(y)\\ 4 = (8 >> 1) \\ \frac{1}{2}x = (x >> 1) \\ \log{(\dfrac{1}{\sqrt{y}}0} = \log{(y^{-\dfrac{1}{2}}))} = -\dfrac{1}{2}\log{(y)} = -(i >> 1) $$ ## magic number 的主要計算過程 $$\Gamma = (1 + \dfrac{M_{\Gamma}}{2^{23}}) \cdot 2 ^ {E_{\Gamma}-127}$$ $$y = (1 + \dfrac{M_{y}}{2^{23}}) \cdot 2 ^ {E_{y}-127}$$ $$\log{(\Gamma)} = -\dfrac{1}{2}\log{(y)}$$ $$ \dfrac{1}{2^{23}}\cdot(M_{\Gamma}+E_{\Gamma} \cdot 2^{23}) + \mu - 127 = -\dfrac{1}{2}\cdot((1 + \dfrac{M_{y}}{2^{23}}) \cdot 2 ^ {E_{y}-127})$$ 然後想要求解的是: $(M_{\Gamma}+E_{\Gamma} \cdot 2^{23})$ $$(M_{\Gamma}+E_{\Gamma} \cdot 2^{23}) = \dfrac{3}{2}\cdot2^{23}\cdot(127-\mu)-\dfrac{1}{2}((M_{y}+E_{y} \cdot 2^{23}))$$ 當中魔法數字：$\dfrac{3}{2}\cdot2^{23}\cdot(127-\mu)$ 向右位移：$-\dfrac{1}{2}((M_{y}+E_{y} \cdot 2^{23})) = -(i >> 1)$ 輸入：$(M_{y}+E_{y} \cdot 2^{23}) = i$ ## 牛頓接近法 https://hackmd.io/@sysprog/arch2025-quiz3-sol https://github.com/eastWillow/ca2025-quizzes/commit/ca69eb95ccc444aa60675741b3ab52844088bd12