这是游戏雷神之锤中的一段代码，出自于 John Carmack 之手，在那个硬件受限的年代，这段代码彻底地改变了整个游戏界。
"what the fuck?" 这是平方根倒数快速幂算法中作者的注释。如果不借助其他外来库的情况下，我们能想到什么好的方法，让计算机快速求解 $\sqrt{2}\approx1.41421356\ $ 的浮点型？夹逼法、连分法、二分法、泰勒展开式？约翰卡马克告诉我们还有极致。
1. 夹逼法
# Python 3.10.0 +
def PinchSqrt2(epoch: int) -> float:
"""夹逼求解根号二.
Args:
epoch (int): 迭代次数.
Returns:
float: 根号二近似值.
"""
x1 = 1
for _ in range(0, epoch, 1):
tmp = x1
x2 = 2 / tmp
x1 = (tmp + x2) / 2
return x1
print(PinchSqrt2(epoch=12))2. 连分法
$\sqrt{2}=1+\dfrac{1}{2+\dfrac{1}{2+\dfrac{1}{2+\cdots}}}$
# Python 3.10.0 +
def ConsecutiveDivisionSqrt2(epoch: int) -> float:
"""连分求解根号二.
Args:
epoch (int): 迭代次数.
Returns:
float: 根号二近似值.
"""
ans = 0 # 初始化可任取, 别取 -2 就好.
for _ in range(0, epoch, 1):
ans = 1 / (2 + ans)
return ans + 1
print(ConsecutiveDivisionSqrt2(12))3. 二分法
# Python 3.10.0 +
def BisectionSqrt2(precision: float) -> float:
"""二分求解根号二
Args:
precision (float): 最终收敛结束精度.
Returns:
float: 根号二近似值.
"""
left = 1
right = 2
while (right - left) > precision:
middle = (left + right) / 2
if (middle ** 2) < 2:
left = middle
else:
right = middle
return (left + right) / 2
print(BisectionSqrt2(precision=1e-7))4. 泰勒级数
$(1+x)^n=1+\displaystyle\sum_{k=1}^{\infty}\dfrac{\displaystyle\prod\limits_{t=0}^{k-1}(n-t)}{k!}x^k$
$\Rightarrow2^{0.5}=1+\dfrac{1}{2}-\dfrac{1}{8}+\dfrac{1}{16}-\dfrac{5}{128}+\cdots$
# Python 3.10.0 +
def TaylorSqrt2(order: int) -> float:
"""泰勒级数求解根号二.
Args:
order (int): 展开阶数.
Returns:
float: 根号二近似值.
"""
ans = 1
for _ in range(0, order, 1):
ans = 1 / ans + 0.5 * ans
return ans
print(TaylorSqrt2(7))夹逼、连分、二分、泰勒，上面这四种算法都需要进行循环，时间复杂度可以近似看作 $\ O(n)\ $ 或 $\ O(\log n)$，那如果不进行循环，有没有方法能将复杂度降到线性级别，是否还能更快地计算出 $\sqrt{2}\ $ 的近似值呢？卡马克的注释究竟是什么意思？$\rm 0x5f3759df\ $ 这个十六进制幻数代表什么？
卡马克平方根倒数快速幂算法
雷神之锤游戏的渲染会经常遇到曲面物体，对于计算机而言，画直线轻而易举，但曲线就会涉及大量的运算，光照射到曲面上，会反射，而要获得到反射光的效果，就需要得知曲面上入射点的单位法向量【点击查看 DezemingFamily 介绍的原理】，这个过程速度越快，游戏的帧率就会越高。
问题的核心抽象为，如何让电脑快速运算平方根倒数？
$f(x)=\dfrac{1}{\sqrt{x}}$
按照前面夹逼、连分、二分、泰勒这四种方法，先求出 $\sqrt{2}\ $ 的浮点型，再取倒数，但这样的速度太慢了，尤其当构成曲面（曲线）的平面（直线）众多时，大量光线照射到墙体，CPU 每次计算单位法向量都要慢一点，累积下来，游戏帧率就会大幅度下降。虽然现在我们有 NVIDIA 的显卡，但在当时，只能依靠 CPU 的算力，平方根倒数算法无疑是让每个人都能畅玩雷神之锤这样的 3D 游戏。