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

在实现"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;
}

关键区别在于倒数第二个“更多魔术”字样。由于初始结果太低了一个相当恒定的因数，因此仅需一条指令即可为结果增加19 * 2 ^(exponent(y)-bias)。似乎给了我大约3个额外的位，但是我是否忽略了某些内容？

最佳答案

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

f(y) = x - 1/y²

是凹面的，因此-除非您以y ≥ √(3/x)开头，否则Newton方法仅使用精确的算术运算生成≤ 1/√x的近似值(严格来说，除非您以确切的结果开头，否则应更小)。

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

因此，是的，存在偏差，并且少量添加通常可以改善结果。但不总是。例如，在1.25或0.85左右的区域中，未进行调整的结果要好于进行调整后的结果。在其他区域，该调整会产生一点额外的精度，而在其他方面则更多。

无论如何，应将要添加的魔术常数调整到最常使用x的区域以获得最佳效果。

关于c - Carmack/Welsh平方根逆算法是否有偏差？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/14748938/