c - Carmack/Welsh 平方根反比算法是否有偏差

Question

实现"Carmack's Inverse Square Root" algorithm时我注意到结果似乎有偏见。下面的代码似乎给出了更好的结果:

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;
}

关键区别在于倒数第二行“more magic”。由于初始结果因相当恒定的因素而过低，因此只需一条指令即可将 19 * 2^(exponent(y)-bias) 添加到结果中。它似乎给了我大约 3 个额外的位，但我是否忽略了什么？

Answer 1

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

f(y) = x - 1/y²

是凹的，所以 - 除非你从 y ≥ √(3/x) 开始 - 牛顿法只产生近似值 ≤ 1/√x(并且严格更小，除非你从精确的结果开始)用精确的算术。

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

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

在任何情况下，为了获得最佳结果，应将要添加的魔法常量调整到最常取 x 的区域。