Square root algorithms

Square root algorithms compute the non-negative square root of a positive real number. Because the square roots of natural numbers that are not perfect squares are irrational, these algorithms usually build a series of increasingly accurate approximations rather than an exact answer. Most of them are iterative: they choose an initial estimate and refine it until a termination criterion is met, with Heron's method, a special case of Newton's method, as one common choice. Other approaches work digit by digit, use Taylor series or use continued fraction expansions, and when division is much costlier than multiplication it can be better to compute the inverse square root instead. The method chosen depends on the accuracy needed and the tools available, and procedures for the square root of 2 are known from ancient Babylon in the 17th century BCE.