Methods of computing square roots

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. For the square roots of a negative or complex number, see below.
Finding ${\displaystyle {\sqrt {S}}}$ is the same as solving the equation ${\displaystyle f(x)=x^{2}-S=0\,\!}$ for a positive ${\displaystyle x}$. Therefore, any general numerical root-finding algorithm can be used. Newton's method, for example, reduces in this case to the so-called Babylonian method:

${\displaystyle x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}=x_{n}-{\frac {x_{n}^{2}-S}{2x_{n}}}={\frac {1}{2}}\left(x_{n}+{\frac {S}{x_{n}}}\right)}$

These methods generally yield approximate results, but can be made arbitrarily precise by increasing the number of calculation steps.

Contents

• 1 Rough estimation
• 2 Babylonian method
  • 2.1 Example
  • 2.2 Convergence
    • 2.2.1 Worst case for convergence
• 3 Digit-by-digit calculation
  • 3.1 Basic principle
  • 3.2 Decimal (base 10)
    • 3.2.1 Examples
  • 3.3 Binary numeral system (base 2)
    • 3.3.1 Example
• 4 Exponential identity
• 5 Bakhshali approximation
  • 5.1 Example
• 6 Vedic duplex method for extracting a square root
  • 6.1 Basic principle
  • 6.2 Example
• 7 A two-variable iterative method
• 8 Iterative methods for reciprocal square roots
  • 8.1 Goldschmidt’s algorithm
• 9 Taylor series
• 10 Other methods
• 11 Continued fraction expansion
  • 11.1 Algorithm
  • 11.2 Example, square root of 114 as a continued fraction
  • 11.3 Generalized continued fraction
• 12 Using Pell's equation
• 13 Approximations that depend on the floating point representation
  • 13.1 Reciprocal of the square root
• 14 Negative or complex square
• 15 See also
• 16 Notes
• 17 External links