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

所以一次迭代应该是x1 = x - f(x)/f'(x) = x / 2 + 1 / (2 * r * x)，对吧？

怎么来的x * (1.5 - ((r / 2) * x * x))？（注意我在这里替换xhalf为r / 2）

编辑

好的f(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

6

维基百科说函数是（使用你的变量名）：

f(x) = 1/x 2 - r

然后我们有：

f'(x) = -2/x 3

迭代是：

x - f(x)/f'(x) =

x - (1/x 2 - r)/(-2 / x 3 ) =

x + x 3 /2 * (1/x 2 - r) =

x + x/2 - r/2 * x 3 =

x * (1.5 - r/2 * x * x)

这就是你在代码中看到的。

于 2013-07-04T17:19:30.537 回答
3

牛顿法是根据迭代定义的

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

（其中 f'(x) 是 f(x) 的一阶导数）。要找到 r 的逆根，需要找到函数 f(x) = x - 1/sqrt(r) 的零点（或等效地，f(x) = x 2 - 1/r）。只需取导数，将其插入迭代步骤的定义中，进行简化，您就会得到答案。

实际上，代码中使用的确切形式来自使用第三种等效形式：

f(x) = x -2 - r

推导的详细步骤见这篇文章。它也源自关于快速平方根的维基百科文章。

于 2013-07-04T17:02:33.733 回答