Why `x = x*(1.5f-(xhalf*x*x));` can be a Newton Method iteration?

Question

Ok, by far, I guess many people know the famous fast inverse square root (see more on Writing your own square root function and 0x5f3759df)

Here is the code

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

---

Ok, i do NOT need to know more how magic 0x5f3759df is.

What I don't understand is why x*(1.5f-(xhalf*x*x)) is a Newton Method iteration?

I tried analyse but just can't get it.

So let's assume r is the real number and x is the inverse sqrt of r.

1 / (x^2) = r, then f(x) = r*(x^2)-1 and f'(x) = 2 * r * x

So one iteration should be x1 = x - f(x)/f'(x) = x / 2 + 1 / (2 * r * x), right?

How comes x * (1.5 - ((r / 2) * x * x))? (note I replaced xhalf with r / 2 here)

---

Edit

Ok f(x) = x^2 - 1/r is another form, let me calculate

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

f'(x) = 2 * x

So x1 = x - (f(x)/f'(x)) = x - (x^2 -(1 / r))/(2*x) = x / 2 + 1 / (2 * r * x), still it is quite different from the formula used in the code, right?

Answer 1

Wikipedia says function is (using your variable names):

f(x) = 1/x² - r

Then we have:

f'(x) = -2/x³

And iteration is:

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

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

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

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

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

And this is what you see in code.

Answer 2

Newton's method is defined in terms of the iteration

x_i+1 = x_i - f(x_i) / f'(x_i)

(where f'(x) is the first derivative of f(x)). To find the inverse root of r, one needs to find the zero of the function f(x) = x - 1/sqrt(r) (or, equivalently, f(x) = x² - 1/r). Simply take the derivative, plug it in to the definition of the iteration step, simplify, and you have your answer.

Actually, the exact form used in the code comes from using a third equivalent form:

f(x) = x^-2 - r

See this article for the detailed steps of the derivation. It's also derived in the Wikipedia article on fast inverse square root.