# 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 $$

繼續化簡

$$ \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 的樣子來操作，最後取值。


## 介紹一下基本知識
$$
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