125

John Carmackは、Quake IIIソースコードに特別な関数を持っており、奇妙な定数(float)(1.0/sqrt(x))を含め、通常の4倍の速さで浮動小数点の逆平方根を計算します。0x5f3759df以下のコードを参照してください。誰かがここで何が起こっているのか、そしてなぜこれが通常の実装よりもはるかに速く機能するのかを行ごとに説明できますか？

float Q_rsqrt( float number )
{
  long i;
  float x2, y;
  const float threehalfs = 1.5F;

  x2 = number * 0.5F;
  y  = number;
  i  = * ( long * ) &y;
  i  = 0x5f3759df - ( i >> 1 );
  y  = * ( float * ) &i;
  y  = y * ( threehalfs - ( x2 * y * y ) );

  #ifndef Q3_VM
  #ifdef __linux__
    assert( !isnan(y) );
  #endif
  #endif
  return y;
}
4

5 に答える 5

80

ご参考までに。カーマックはそれを書きませんでした。TerjeMathisenとGaryTarolliはどちらも、他のいくつかの情報源を信用しているだけでなく、部分的（そして非常に控えめな）信用を持っています。

神話上の定数がどのように導き出されたかは、謎のようなものです。

ゲイリー・タロッリを引用するには：

これは実際に整数で浮動小数点計算を行っています-これがどのようにそしてなぜ機能するのかを理解するのに長い時間がかかりました、そして私はもう詳細を思い出せません。

元のアルゴリズムがどのように機能するかを解明しようとしている専門の数学者（Chris Lomont）によって開発された、わずかに優れた定数は次のとおりです。

float InvSqrt(float x)
{
    float xhalf = 0.5f * x;
    int i = *(int*)&x;              // get bits for floating value
    i = 0x5f375a86 - (i >> 1);      // gives initial guess y0
    x = *(float*)&i;                // convert bits back to float
    x = x * (1.5f - xhalf * x * x); // Newton step, repeating increases accuracy
    return x;
}

それにもかかわらず、彼の最初の試みは、数学的に「優れた」バージョンのidのsqrt（ほぼ同じ定数になりました）は、数学的にはるかに「純粋」であるにもかかわらず、Garyによって最初に開発されたものより劣っていました。彼はなぜidがとても優れたiircだったのか説明できませんでした。

于 2009-08-28T21:52:23.207 に答える
56

もちろん、最近では、FPU の sqrt (特に 360/PS3) を使用するよりもはるかに遅いことが判明しています。これは、float レジスタと int レジスタ間のスワップがロードヒットストアを誘発するのに対し、浮動小数点ユニットは逆二乗を実行できるためです。ハードウェアのルート。

基礎となるハードウェアの性質が変化するにつれて、最適化がどのように進化しなければならないかを示しています。

于 2009-08-28T22:01:40.863 に答える
23

しばらく前に書かれたこの素敵な記事によると...

コードの魔法は、たとえあなたがそれに従うことができなくても、i = 0x5f3759df-（i >> 1）として際立っています。ライン。簡略化されたニュートンラプソンは、推測から始まり、反復でそれを洗練する近似です。32ビットx86プロセッサの性質を利用して、i、つまり整数は、整数キャストを使用して、最初は逆二乗を取りたい浮動小数点数の値に設定されます。次に、iは0x5f3759dfに設定され、マイナス自体が1ビット右にシフトされます。右シフトはiの最下位ビットをドロップし、本質的に半分にします。

本当に良い読み物です。これはほんの一部です。

于 2009-08-28T21:57:52.667 に答える