Square Root - Computation

Computation

Most pocket calculators have a square root key. Computer spreadsheets and other software are also frequently used to calculate square roots. Pocket calculators typically implement efficient routines to compute the exponential function and the natural logarithm or common logarithm, and use them to compute the square root of a positive real number a using the identity

or

The same identity is exploited when computing square roots with logarithm tables or slide rules.

The most common iterative method of square root calculation by hand is known as the "Babylonian method" or "Heron's method" after the first-century Greek philosopher Heron of Alexandria, who first described it. The method uses the same iterative scheme as the Newton–Raphson method yields when applied to the function, using the fact that its slope at any point is, but predates it by many centuries. It involves a simple algorithm, which results in a number closer to the actual square root each time it is repeated. The basic idea is that if x is an overestimate to the square root of a non-negative real number a then will be an underestimate and so the average of these two numbers may reasonably be expected to provide a better approximation (though the formal proof of that assertion depends on the inequality of arithmetic and geometric means that shows this average is always an overestimate of the square root, as noted below, thus assuring convergence). To find x :

1. Start with an arbitrary positive start value x (the closer to the square root of a, the fewer iterations will be needed to achieve the desired precision).
2. Replace x by the average between x and a/x, that is:, representing the Newton–Raphson method resulting in ,

(It is sufficient to take an approximate value of the average to ensure convergence)

1. Repeat step 2 until x and a/x are as close as desired.

If a is positive, the convergence is "quadratic," which means that in approaching the limit, the number of correct digits roughly doubles in each next iteration. If a = 0, the convergence is only linear.

Using the identity

the computation of the square root of a positive number can be reduced to that of a number in the range [1, 4). This simplifies finding a start value for the iterative method that is close to the square root, for which a polynomial or piecewise-linear approximation can be used.

The time complexity for computing a square root with n digits of precision is equivalent to that of multiplying two n-digit numbers.

Another useful method for calculating the square root is the Shifting nth root algorithm, applied for .