快速平方根倒数算法详解
算法概述
快速平方根倒数算法通过一系列令人惊叹的位操作和整数运算，高效计算浮点数 x 的平方根倒数 1/√x。该算法因出现在《雷神之锤3》源代码中而闻名，由约翰·卡马克推广。其核心思想是利用IEEE 754浮点数的二进制表示与对数函数的近似关系，通过整数运算实现快速近似计算。
算法代码
float Q_rsqrt(float number) {
long i;
float x2, y;
const float threehalfs = 1.5F;
x2 = number * 0.5F;
y = number;
i = *(long*)&y; // 将浮点数位模式解释为整数
i = 0x5f3759df - ( i >> 1 ); // 核心计算：整数减半并与魔数相减
y = *(float*)&i; // 将结果解释回浮点数
y = y * ( threehalfs - ( x2 * y * y ) ); // 牛顿迭代法改进精度
return y;
}
历史背景
该算法在1999年为3D图形计算优化而生。当时硬件性能有限，计算反平方根（用于向量归一化、光照计算等）非常耗时。现代硬件已可通过专用浮点单元快速完成此计算，但该算法仍是数值计算和硬件理解的优秀范例。
核心原理
1. 浮点数的二进制表示
IEEE 754单精度浮点数（32位）分为三部分：
- 符号位（1位）：正负号
- 指数位（8位）：表示范围（偏移127）
- 尾数位（23位）：表示具体数值
数值 N 计算公式为：
N = (-1)^S × 2^(E-127) × (1 + M/2^23)
2. 位模式与对数的近似关系
将浮点数的位模式直接解释为整数 I，会发现其与 log₂(x) 存在近似线性关系：
log₂(x) ≈ I / 2²³ - 127
这种近似源于浮点数的指数部分线性编码了数值的数量级。
3. 魔数常数的推导
基于对数性质 log₂(1/√x) = -0.5 × log₂(x)，通过代数变换得到：
I_y ≈ -0.5 × I_x + C
其中 C = (3/2) × 2²³ × (127 - σ)，σ 是优化近似精度的调整参数。
计算当 σ ≈ 0.0450465 时：
C = 1.5 × 2²³ × (127 - 0.0450465) = 1598029824- 转换为十六进制：
0x5f3759df
因此核心操作 i = 0x5f3759df - (i >> 1) 实际上是通过整数移位（相当于除以2）和减法实现对数域的线性近似。
4. 牛顿迭代法改进精度
初始近似误差较大，通过牛顿迭代法优化：
y_{n+1} = y_n × (1.5 - 0.5x × y_n²)
代码中的 y = y * (threehalfs - (x2 * y * y)) 即为此公式的实现。该迭代避免了除法运算，仅使用乘法和加法，单次迭代即可将误差降至约0.175%。
算法特性
- 仅适用于正常浮点数：对零、次正规数（sub-normals）和特殊值（无穷大、NaN）不适用
- 非精确计算：是快速近似算法，误差可控
- 硬件友好：充分利用整数移位、加法和乘法，避免昂贵的浮点除法和开方
结论
快速平方根倒数算法体现了对浮点数底层表示的深刻理解，通过数学近似和数值方法的结合，在硬件限制下实现了高效计算。虽在现代硬件上已无必要，但它仍是计算机科学中数值优化与硬件理解的经典范例，展示了如何将数学洞察转化为高效工程实践。