3

わかりました、多くの人が有名な高速逆平方根を知っていると思います (独自の平方根関数の記述と0x5f3759dfの詳細を参照してください) 。

ここにコードがあります

float FastInvSqrt(float x) {
  float xhalf = 0.5f * x;
  int i = *(int*)&x;         // evil floating point bit level hacking
  i = 0x5f3759df - (i >> 1);  // what the fuck?
  x = *(float*)&i;
  x = x*(1.5f-(xhalf*x*x)); // one Newton Method iteration
  return x;
}

わかりました、魔法0x5f3759dfがどのようなものかをこれ以上知る必要はありません。

私が理解していないのは、なぜx*(1.5f-(xhalf*x*x))反復なのNewton Methodですか?

分析してみましたが、わかりません。

r が実数で、x が r の逆平方根であると仮定しましょう。

1 / (x^2) = r、f(x) = r*(x^2)-1そしてf'(x) = 2 * r * x

したがって、1回の反復は であるはずx1 = x - f(x)/f'(x) = x / 2 + 1 / (2 * r * x)ですよね?

どうしてx * (1.5 - ((r / 2) * x * x))ですか？（ここに置き換えxhalfたことに注意してr / 2ください）

編集

OKf(x) = x^2 - 1/rは別の形式です。計算させてください

f(x) = x^2 - 1 / r

f'(x) = 2 * x

それでx1 = x - (f(x)/f'(x)) = x - (x^2 -(1 / r))/(2*x) = x / 2 + 1 / (2 * r * x)、それでもコードで使用されている式とはかなり異なりますよね?

4

2 に答える 2

3

ニュートン法は反復の観点から定義されています

x i+1 = x i - f(x i ) / f'(x i )

(ここで、f'(x) は f(x) の 1 次導関数です)。r の逆根を見つけるには、関数 f(x) = x - 1/sqrt(r) (または、同等に、f(x) = x 2 - 1/r) のゼロを見つける必要があります。微分を取り、反復ステップの定義にプラグインし、単純化するだけで、答えが得られます。

実際、コードで使用されている正確な形式は、3 番目の同等の形式を使用したものです。

f(x) = x -2 - r

派生の詳細な手順については、この記事を参照してください。また、高速逆平方根に関するウィキペディアの記事でも導出されています。

于 2013-07-04T17:02:33.733 に答える