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 IdeaCopy Anchor Link

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 RootCopy Anchor Link

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.

CodeCopy Anchor Link

/**
 * Calculates the square root of the number with given tolerance (precision)
 * by using Newton's method.
 *
 * @param number - the number we want to find a square root for.
 * @param [tolerance] - how many precise numbers after the floating point we want to get.
 * @return {number}
 */
export default function squareRoot(number, tolerance = 0) {
  // For now we won't support operations that involves manipulation with complex numbers.
  if (number < 0) {
    throw new Error('The method supports only positive integers');
  }

  // Handle edge case with finding the square root of zero.
  if (number === 0) {
    return 0;
  }

  // We will start approximation from value 1.
  let root = 1;

  // Delta is a desired distance between the number and the square of the root.
  // - if tolerance=0 then delta=1
  // - if tolerance=1 then delta=0.1
  // - if tolerance=2 then delta=0.01
  // - and so on...
  const requiredDelta = 1 / (10 ** tolerance);

  // Approximating the root value to the point when we get a desired precision.
  while (Math.abs(number - (root ** 2)) > requiredDelta) {
    // Newton's method reduces in this case to the so-called Babylonian method.
    // These methods generally yield approximate results, but can be made arbitrarily
    // precise by increasing the number of calculation steps.
    root -= ((root ** 2) - number) / (2 * root);
  }

  // Cut off undesired floating digits and return the root value.
  return Math.round(root * (10 ** tolerance)) / (10 ** tolerance);
}

ReferencesCopy Anchor Link

• Methods of computing square roots on Wikipedia
• Newton's method on Wikipedia