assembly - 这个 sqrt 近似内联汇编函数如何工作？

Question

通读3D游戏编程大师的技巧，我发现了这个用内联汇编编写的排序函数:

inline float FastSqrt(float Value)
{
    float Result;

    _asm
    {
        mov eax, Value
        sub eax, 0x3F800000
        sar eax, 1
        add eax, 0x3F800000
        mov Result, eax
    }

    return(Result);
}

它是实际平方根的近似值，但精度足以满足我的需要。

这实际上是如何运作的？这个神奇的 0x3F800000 值是什么？我们如何通过减法、旋转和加法求平方根？

这是它在 C/C++ 代码中的样子:

inline float FastSqrt_C(float Value)
{
    float Result;

    long Magic = *((long *)&Value);
    Magic -= 0x3F800000;
    Magic >>= 1;
    Magic += 0x3F800000;
    Result = *((float *)&Magic);

    return(Result);
}

Answer 1

很多人指出0x3f800000是 1.0 的表示。虽然这是事实，但它与计算方式无关。要理解它，您需要知道非负 float 是如何存储的。 f = (1+m)*2^x ，与 0 <= m < 1和m作为尾数，x指数。另请注意 x是带有偏差存储的，所以二进制文件中的实际内容是 x+127 。 32 位值由符号位(在我们的例子中为零)和随后存储 x+127 的 8 位指数组成。最后是 23 位尾数，m 。 (请参阅wikipedia article)。

应用一些基本数学，

sqrt(f) = sqrt((1+m)*2^x)
        = sqrt(1+m)*sqrt(2^x)
        = sqrt(1+m)*2^(x/2)

因此，作为一个粗略的近似，我们需要将指数减半，但由于偏差，我们不能仅仅这样做 x/2我们需要(x-127)/2 + 127 。这个127移位到适当的位位置就是神奇的 0x3f800000 .

除以 2 是通过右移一位来实现的。由于这对整个 float 进行操作，因此它也会对尾数产生副作用。

首先，假设原始指数是偶数。那么移出的最低有效位为零。因此，尾数也减半，所以我们最终得到的是:sqrt(f) = (1+m/2)*2^(x/2) 。我们得到的指数是正确的，但尾数是 (1+m/2)而不是sqrt(1+m) 。最大相对误差为 (1.5 - sqrt(2))/sqrt(2) ~ 6%如果 m 就会发生这种情况差不多1含义f接近，但小于 2 的奇次幂。以f=7.99为例。该公式为我们提供了大约 2.998而不是2.827确实有错误 6% .

现在，如果指数是奇数，则最低有效位将为 1当移入尾数时，会导致增加一半。因此，我们得到sqrt(f) = (1.5+m/2)*2^((x-1)/2) 。最大错误实际上是当 m=0 时，这将是 (1.5/sqrt(2)-sqrt(1))/sqrt(1)这又是在 6% 附近。对于上面接近 2 的奇数次方的数字，会发生这种情况。

这两种情况相结合意味着，如果输入值恰好接近 2 的奇数次方，最差的误差约为 6%。对于 2 的偶次幂，结果是准确的。