为什么`x = x*(1.5f-(xhalf*x*x));`可以是牛顿方法迭代？

Question

好吧,到目前为止,我想很多人都知道着名的快反平方根(详见编写自己的平方根函数和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的逆sqrt.

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),它仍然与代码中使用的公式完全不同,对吧？

Answer 1

维基百科称功能是(使用您的变量名称):

f(x)= 1/x ² - r

然后我们有:

f'(x)= -2/x ³

迭代是:

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

x - (1/x ² - r)/( - 2/x ³)=

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

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

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

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