快速平方根算法

视频讲解

🔍 一、算法目标

求：

\[ y = \frac{1}{\sqrt{x}} = x^{-1/2} \]

用于 3D 图形、归一化向量、物理模拟等高性能场景中。

---

🧠 二、浮点数基础（IEEE 754 单精度）

浮点数结构（32位）：

位数	含义
1位	符号位 \(s\)
8位	指数位 \(E\)
23位	尾数 \(m\)

表示公式：

\[ x = (-1)^s \cdot (1 + m) \cdot 2^{E - 127} \]

• 指数是带偏移表示：实际指数 \(e = E - 127\)
• 尾数是小数：用 23 位表示 \(m \in [0, 1)\)，但隐含最高位 \(1\)，因此为 \(1 + m\)

---

🧩 三、从数学角度理解倒数平方根

目标函数：

\[ y = x^{-1/2} \Rightarrow \log_2 y = -\frac{1}{2} \log_2 x \]

✅ 关键点：

• 浮点指数本质上就是对数（log₂）的整数部分
• 整个浮点数的位模式（int）可以近似看成是线性编码的 \(\log_2 x\)

---

⚙️ 四、算法核心：位级魔术变换

🌟 核心魔术步骤：

1. 将 float \(x\) 按位解释为整数 \(I_x\)
2. 位运算得到初始估计：

\[ I_y = \text{magic} - (I_x >> 1) \]

1. 再将 \(I_y\) 解释回 float，得到 \(y\) 的粗略估计
2. 用一次牛顿迭代提升精度

🎩 魔术常数（经验最佳值）：

0x5f3759df

---

🔁 五、牛顿迭代精修步骤

目标是解：

\[ f(y) = \frac{1}{y^2} - x = 0 \]

一次迭代：

\[ y_{n+1} = y_n \cdot \left(1.5 - 0.5 x y_n^2\right) \]

通常迭代一次，精度就足够了。

---

✅ 六、完整 C 语言代码（含注释）

float Q_rsqrt(float number) {
    long i;                       // 用于整数解释
    float x2, y;
    const float threehalfs = 1.5F;

    x2 = number * 0.5F;
    y  = number;

    i  = *(long*)&y;              // 将 float 转换为 int（bit reinterpret）
    i  = 0x5f3759df - (i >> 1);   // 魔术变换：减去一半指数
    y  = *(float*)&i;             // 解释回 float 值

    y  = y * (threehalfs - (x2 * y * y));  // 牛顿迭代一次

    return y;
}

---

📌 七、为什么能奏效？原理简述

原理层面	说明
浮点结构	浮点指数近似 log₂(x) 的整数部分
位模式处理	将 float 的位模式当作 int 操作，实现对 log 的线性变换
魔术数作用	拟合 \(-\frac{1}{2} \log_2(x)\) 的线性函数
迭代修正	牛顿迭代快速提高精度

---

📝 八、总结一句话：

该算法巧妙地利用了浮点数对数式编码的结构，用魔术常数做位移替代对数变换，并用一次迭代达到快速近似倒数平方根的效果。