Square root algorithms

Square root algorithms compute the non-negative square root S {\displaystyle {\sqrt {S}}} of a positive real number S {\displaystyle S} . Since all square roots of natural numbers, other than of perfect squares, are irrational, square roots can usually only be computed to some finite precision: these algorithms typically construct a series of increasingly accurate approximations. Most square root computation methods are iterative: after choosing a suitable initial estimate of S {\displaystyle {\sqrt {S}}} , an iterative refinement is performed until some termination criterion is met. One refinement option 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).