Newton’s method is a method for finding approximations to the roots of a given function.

The method itself is very simple, you give an initial guess of the root, $$x_0$$, and calculate further values using the following equation: $$x_{n+1}=x_n-\frac{f’(x_n)}{f(x_n)}$$.
Generally, each term in the sequence is more accurate in comparison to the previous terms.

## How does it work

Let $$f(x)$$ be the function whose root we are looking for.
Let $$x_0$$ be our initial guess for the root.
Let $$x_n$$ be our latest guess for the root.

In each step we take our best guess, $$x_n$$, and try to make it more accurate.
To do so, we draw the tangent in the point $$(x_n, f(x_n))$$ and find its root, which we than call $$x_{n+1}$$.
$$x_{n+1}$$ will be more accurate (usually).

A demonstration: (click on the image to enlarge it)

The math behind this is not very difficult.
The equation of the tangent line is: $$y-f(x_n)=f’(x_n)(x_{n+1}-x_n)$$.
We look for $$x_{n+1}$$ when $$y=0$$, hence
$$0-f(x_n)=f’(x_n)(x_{n+1}-x_n) \\\Rightarrow -f(x_n)=x_{n+1}f’(x_n)-x_nf’(x_n) \\\Rightarrow x_{n+1}f’(x_n)=x_nf’(x_n)-f(x_n) \\\Rightarrow x_{n+1}=x_n-\frac{f(x_n)}{f’(x_n)}$$

## Example – Square Root

Say we want to calculate the square root of $$a$$.
We need to find a value of $$x$$ such that $$x=\sqrt{a}\Rightarrow x^2=a\Rightarrow x^2-a=0$$.
So, we are looking for the non-negative root ($$x=\sqrt{a}\ge0$$) of the function $$f(x)=x^2-a$$.
The derivative of this function is $$f’(x)=2x$$.
And therefore:
$$x_{n+1}=x_n-\frac{x_n^2-a}{2x_n}=\frac{2x_n^2-x_n^2+a}{2x_n}=\frac{x_n^2+a}{2x_n}=\frac{x_n}{2}+\frac{a}{2x_n}$$

### Calculating $$\sqrt{2}$$

Let’s try and find an approximation for $$\sqrt{2}$$ with initial guess $$x_0=1$$.
$$x_1=\frac{1}{2}+\frac{2}{2\times1}=\frac{3}{2} \\ x_2=\frac{3}{2\times2}+\frac{2\times2}{2\times3}=\frac{17}{12} \\ x_3=\frac{17}{2\times12}+\frac{2\times12}{2\times17}=\frac{577}{408} \\ x_4=\frac{577}{2\times408}+\frac{2\times408}{2\times577}=\frac{665857}{470832}\approx1.414213562$$
The error from the real value is lower than $$0.0000000000016$$!
We have got this amazing result with only four steps!

Calculating further will produce very accurate massive fractions:
$$|x_5-\sqrt{2}|<9\times10^{-25} \\ |x_6-\sqrt{2}|<2.9\times10^{-49} \\ |x_7-\sqrt{2}|<2.9\times10^{-98}$$

### Implementation

The C# implementation is super easy.

The parameters are $$a$$, which is the number whose square root we are looking for, and $$times$$, which determines the number of calculations.

public double Sqrt(double a, int times)
{
if (a < 0)
throw new Exception("Can not sqrt a negative number");
double x = 1;
while (times-- > 0)
x = x / 2 + a / (2 * x);
return x;
}

## Conclusions

Newton’s method is a very efficient way to find roots of functions, including square roots of numbers.
It is much more efficient than the method I introduced in my article Square Root Algorithm.