Carmack/Welsh逆平方根算法是否有偏差

Question

在实现"Carmack的反平方根"算法时,我注意到结果似乎有偏差.以下代码似乎可以提供更好的结果:

float InvSqrtF(float x)
{
    // Initial approximation by Greg Walsh.
    int i  = * ( int* ) &x;
    i  = 0x5f3759df - ( i >> 1 );
    float y  = * ( float * ) &i;
    // Two iterations of Newton-Raphson's method to refine the initial estimate.
    x *= 0.5f;
    float f = 1.5F;
    y  = y * ( f - ( x * y * y ) );
    y  = y * ( f - ( x * y * y ) );
    * ( int * )(&y) += 0x13; // More magic.
    return y;
}

关键的区别在于倒数第二个"更神奇"的界限.由于初始结果因相当恒定的因子而过低,因此仅使用一条指令就可将19*2 ^(指数(y) - 偏差)添加到结果中.它似乎给了我大约3个额外的位,但我忽略了什么？

Answer 1

牛顿方法会产生偏差。要找到零的函数，

\n\n

f(y) = x - 1/y\xc2\xb2\n

\n\n

是凹的，所以 - 除非你从 an 开始y \xe2\x89\xa5 \xe2\x88\x9a(3/x)- 牛顿法只能\xe2\x89\xa4 1/\xe2\x88\x9ax用精确的算术产生近似值（并且严格更小，除非你从精确的结果开始）。

\n\n

浮点运算偶尔会产生太大的近似值，但通常不会在前两次迭代中产生（因为初始猜测通常不够接近）。

\n\n

所以，是的，存在偏差，添加少量通常会改善结果。但不总是。例如，在 1.25 或 0.85 附近的区域，没有调整的结果比调整后的结果更好。在其他地区，这种调整会带来一点额外的精度，而在其他地区则更多。

\n\n

无论如何，要添加的魔法常数应该调整到x最常获取最佳结果的区域。

\n