I’m creating a program for finding the square root of a number, and I came across the Newton-Raphson method, an algorithm that solves my task.

I only saw the pseudocode for the algorithm, but I never really understood why it worked. Can someone explain to me why it works without all the heavy math?

In: Mathematics

There is a [neat animation on the Wikipedia page](https://en.wikipedia.org/wiki/File:NewtonIteration_Ani.gif) which gives an idea of how this works.

Essentially you are pretending that your function is a straight line, not a curve, and then finding where the 0 would be.

You then assume that your new point is closer than your earlier one and try again – finding the new line (tangent to the curve at this point) and finding where that crosses the x-axis. And you repeat.

It doesn’t always work, but when it does, it tends to work fairly quickly.

Let’s say we’re looking for X, and we have A that is smaller then X and B that’s bigger then X.

In which case A+B / 2 will be a good approximation of X (even though A, or B can be closer to X in certain cases). Think middle of the road, of which A and B are boundaries.

Now in case of a square root:

1. Assume N = sqrt(M). We don’t know what N is.

2. Let’s say X0 is our best guess as what N is. It can be either bigger then N or smaller. But at the same time A / X0 will be either smaller, or bigger then N.

3. That means that N is between X0 and M/X0. We can use the fact above and say A = N and B = M/X0

4. So X1 = (X0 + N/X0) / 2

5. Repeat 2-4 enough time, that you get close enough 🙂

Example. We’re looking for root of 10

1. A = 5

B = 10/5 = 2

X1 = (2 + 5) / 2 = 2.5

2. A = 2.5

B = 10 / 2.5 = 4

X2 = (2.5 + 4) / 2 = 3.25

3. A = 3.25

B = 10 / 3.25 ~= 3.07

X3 = (3.25 + 3.07) / 2 = 3.16

As you can see after 3 steps by narrowing down the left and right side we’re reached the result with 2 significant digits which is 3.16.

What’s important is always choosing a correct functions so that outcome always lies between A and B.

It’s using the derivative as an approximation of the line between the current guess and the zero of the function.

If you think of a line representing a function, square root in your example, and a current guess (X), then the derivative of the function represents the slope at X. This slope is a line that crosses the zero axis, and since it’s a straight line the crossing point is easy to calculate. That zero point is a better guess for the zero than X, so if you start from that point and iteratively repeat the process you can get very close to the actual zero very quickly.