这个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.虽然这是事实,但它与计算的工作方式无关.要理解它,您需要知道如何存储非负浮点数.f = (1+m)*2^x,以0 <= m < 1和m为尾数,x指数.另请注意,x存储时存在偏差,因此二进制文件中实际存在的是什么x+127.32位值由符号位(在我们的例子中为零)后跟8位指数存储组成x+127,最后由23位尾数组成m.(参见维基百科文章).

应用一些基本的数学,

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的除法.由于它在整个浮子上运行,因此它对尾数也有副作用.

首先,假设原始指数是偶数.然后,移出的最低有效位为零.因此,尾数也减半,所以我们最终得到的结果是: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的幂,结果是准确的.