Methods of computing square roots

Most square root computation methods are iterative: after choosing a suitable initial estimate of ${\displaystyle {\sqrt {S}}}$, an iterative refinement is performed until some termination criterion is met. One refinement scheme is Heron's method, a special case of Newton's method. If division is much more costly than multiplication, it may be preferable to compute the inverse square root instead.


Other methods are available to compute the square root digit by digit, or using Taylor series. Rational approximations of square roots may be calculated using continued fraction expansions.


The method employed depends on the needed accuracy, and the available tools and computational power. The methods may be roughly classified as those suitable for mental calculation, those usually requiring at least paper and pencil, and those which are implemented as programs to be executed on a digital electronic computer or other computing device. Algorithms may take into account convergence (how many iterations are required to achieve a specified precision), computational complexity of individual operations (i.e. division) or iterations, and error propagation (the accuracy of the final result).


A few methods like paper-and-pencil synthetic division and series expansion, do not require a starting value. In some applications, an integer square root is required, which is the square root rounded or truncated to the nearest integer (a modified procedure may be employed in this case).

Exponential identity[edit]

Pocket calculators typically implement good routines to compute the exponential function and the natural logarithm, and then compute the square root of S using the identity found using the properties of logarithms (${\displaystyle \ln x^{n}=n\ln x}$) and exponentials (${\displaystyle e^{\ln x}=x}$): $${\displaystyle {\sqrt {S}}=e^{{\frac {1}{2}}\ln S}.}$$ The denominator in the fraction corresponds to the nth root. In the case above the denominator is 2, hence the equation specifies that the square root is to be found. The same identity is used when computing square roots with logarithm tables or slide rules.

A two-variable iterative method[edit]

This method is applicable for finding the square root of ${\displaystyle 0<S<3\,\!}$ and converges best for ${\displaystyle S\approx 1}$. This, however, is no real limitation for a computer-based calculation, as in base 2 floating-point and fixed-point representations, it is trivial to multiply ${\displaystyle S\,\!}$ by an integer power of 4, and therefore ${\displaystyle {\sqrt {S}}}$ by the corresponding power of 2, by changing the exponent or by shifting, respectively. Therefore, ${\displaystyle S\,\!}$ can be moved to the range ${\textstyle {\tfrac {1}{2}}\leq S<2}$. Moreover, the following method does not employ general divisions, but only additions, subtractions, multiplications, and divisions by powers of two, which are again trivial to implement. A disadvantage of the method is that numerical errors accumulate, in contrast to single variable iterative methods such as the Babylonian one.


The initialization step of this method is $${\displaystyle {\begin{aligned}a_{0}&=S\\c_{0}&=S-1\end{aligned}}}$$ while the iterative steps read $${\displaystyle {\begin{aligned}a_{n+1}&=a_{n}-a_{n}c_{n}/2\\c_{n+1}&=c_{n}^{2}(c_{n}-3)/4\end{aligned}}}$$ Then, ${\displaystyle a_{n}\to {\sqrt {S}}}$ (while ${\displaystyle c_{n}\to 0}$).


The convergence of ${\displaystyle c_{n}\,\!}$, and therefore also of ${\displaystyle a_{n}\,\!}$, is quadratic.


The proof of the method is rather easy. First, rewrite the iterative definition of ${\displaystyle c_{n}}$ as $${\displaystyle 1+c_{n+1}=(1+c_{n})(1-{\tfrac {1}{2}}c_{n})^{2}.}$$ Then it is straightforward to prove by induction that $${\displaystyle S(1+c_{n})=a_{n}^{2}}$$ and therefore the convergence of ${\displaystyle a_{n}\,\!}$ to the desired result ${\displaystyle {\sqrt {S}}}$ is ensured by the convergence of ${\displaystyle c_{n}\,\!}$ to 0, which in turn follows from ${\displaystyle -1<c_{0}<2\,\!}$.


This method was developed around 1950 by M. V. Wilkes, D. J. Wheeler and S. Gill^[8] for use on EDSAC, one of the first electronic computers.^[9] The method was later generalized, allowing the computation of non-square roots.^[10]

Taylor series[edit]

If N is an approximation to ${\displaystyle {\sqrt {S}}}$, a better approximation can be found by using the Taylor series of the square root function: $${\displaystyle {\sqrt {N^{2}+d}}=N\sum _{n=0}^{\infty }{\frac {(-1)^{n}(2n)!}{(1-2n)n!^{2}4^{n}}}{\frac {d^{n}}{N^{2n}}}=N\left(1+{\frac {d}{2N^{2}}}-{\frac {d^{2}}{8N^{4}}}+{\frac {d^{3}}{16N^{6}}}-{\frac {5d^{4}}{128N^{8}}}+\cdots \right)}$$


As an iterative method, the order of convergence is equal to the number of terms used. With two terms, it is identical to the Babylonian method. With three terms, each iteration takes almost as many operations as the Bakhshali approximation, but converges more slowly. Therefore, this is not a particularly efficient way of calculation. To maximize the rate of convergence, choose N so that ${\displaystyle {\frac {|d|}{N^{2}}}\,}$ is as small as possible.

Negative or complex square[edit]

If S < 0, then its principal square root is $${\displaystyle {\sqrt {S}}={\sqrt {\vert S\vert }}\,\,i\,.}$$


If S = a+bi where a and b are real and b ≠ 0, then its principal square root is $${\displaystyle {\sqrt {S}}={\sqrt {\frac {\vert S\vert +a}{2}}}\,+\,\operatorname {sgn}(b){\sqrt {\frac {\vert S\vert -a}{2}}}\,\,i\,.}$$


This can be verified by squaring the root.^[20][21] Here $${\displaystyle \vert S\vert ={\sqrt {a^{2}+b^{2}}}}$$


is the modulus of S. The principal square root of a complex number is defined to be the root with the non-negative real part.