6

在实施“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^(exponent(y)-bias) 添加到结果中。它似乎给了我大约 3 个额外的位，但我是否忽略了什么？

4

2 回答 2

3

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

f(y) = x - 1/y²

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

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

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

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

于 2013-02-07T20:53:03.870 回答
2

由于此方法是一种近似值，因此结果有时会被高估，而有时会被低估。您可以在McEniry 的论文中找到一些关于此错误如何针对不同配置分布的不错的数字，以及它们背后的数学原理。

因此，除非您有可靠的证据证明在您的应用领域中结果明显有偏差，否则我宁愿按照Lomont 的文档中的建议调整魔法常数:-)

于 2013-02-07T19:33:29.077 回答