Square Root (Newton's Method)

In numerical analysis, a branch of mathematics, there are several square root algorithms or methods of computing the principal square root of a non-negative real number. As, generally, the roots of a function cannot be computed exactly. The root-finding algorithms provide approximations to roots expressed as floating point numbers.

Finding is the same as solving the equation for a positive x. Therefore, any general numerical root-finding algorithm can be used.

Newton's method (also known as the Newton–Raphson method), named after Isaac Newton and Joseph Raphson, is one example of a root-finding algorithm. It is a method for finding successively better approximations to the roots of a real-valued function.

Let's start by explaining the general idea of Newton's method and then apply it to our particular case with finding a square root of the number.

Newton's Method General Idea

The Newton–Raphson method in one variable is implemented as follows:

The method starts with a function f defined over the real numbers x, the function's derivative f', and an initial guess x0 for a root of the function f. If the function satisfies the assumptions made in the derivation of the formula and the initial guess is close, then a better approximation x1 is:

Geometrically, (x1, 0) is the intersection of the x-axis and the tangent of the graph of f at (x0, f (x0)).

The process is repeated as:

until a sufficiently accurate value is reached.

Newton's Method of Finding a Square Root

As it was mentioned above, finding is the same as solving the equation for a positive x.

The derivative of the function f(x) in case of square root problem is 2x.

After applying the Newton's formula (see above) we get the following equation for our algorithm iterations:

x := x - (x² - S) / (2x)

The x² − S above is how far away x² is from where it needs to be, and the division by 2x is the derivative of x², to scale how much we adjust x by how quickly x² is changing.

References