6

「カーマックの逆平方根」アルゴリズムを実装すると、結果が偏っているように見えることに気付きました。次のコードは、より良い結果をもたらすようです。

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

主な違いは、最後から 2 番目の「more magic」行にあります。最初の結果はかなり一定の係数で低すぎたため、1 つの命令だけで 19 * 2^(exponent(y)-bias) が結果に追加されます。約 3 ビット余分に得られるようですが、何か見落としがありますか?

4

2 に答える 2

3

ニュートン法は偏りを生じます。ゼロを求める関数

f(y) = x - 1/y²

は凹状であるため、- で開始しない限りy ≥ √(3/x)、ニュートン法は≤ 1/√x正確な算術演算による近似値のみを生成します (正確な結果から開始しない限り、厳密に小さくなります)。

浮動小数点演算では、場合によっては近似値が大きすぎることがありますが、通常、最初の 2 回の反復では発生しません (通常、最初の推定値が十分に近くないため)。

そうです、偏りがあり、一般的に少量を追加すると結果が改善されます. しかしいつもではない。たとえば、1.25 または 0.85 付近の領域では、調整なしの結果の方が調整ありよりも優れています。他の地域では、この調整により精度が 1 ビット向上し、さらに別の地域ではさらに精度が向上します。

いずれにせよ、追加するマジック定数はx、最良の結果を得るために最も頻繁に取得される領域に調整する必要があります。

于 2013-02-07T20:53:03.870 に答える
2

この方法は概算であるため、結果は過大評価される場合もあれば、過小評価される場合もあります。McEniryの論文には、このエラーがさまざまな構成でどのように分布しているか、およびその背後にある数学に関するいくつかの優れた図があります。

したがって、アプリケーションのドメインで結果が明らかに偏っているという確固たる証拠がない限り、Lomontのドキュメントで提案されているように魔法の定数を調整することをお勧めします:-)

于 2013-02-07T19:33:29.077 に答える