Square Root Algorithms

👁 DOWNLOAD Mathematica Notebook
Download Wolfram Notebook

A sequence of approximations 👁 a/b
to 👁 sqrt(n)
can be derived by factoring

(where 👁 -1
is possible only if 👁 -1
is a quadratic residue of 👁 n
). Then

and

Therefore, 👁 a
and 👁 b
are given by the recurrence relations

with 👁 a_1=b_1=1
. The error obtained using this method is

The first few approximants to 👁 sqrt(n)
are therefore given by

This algorithm is sometimes known as the Bhaskara-Brouncker algorithm, and the approximants are precisely those obtained by taking successive convergents to the continued fraction of 👁 sqrt(n)
. The fact that if 👁 a/b
is an approximation to 👁 sqrt(2)
, then 👁 (a+2b)/(a+b)
is a better one (the 👁 n=2
case) was known to Theon of Smyrna in the second century AD (Wells 1986, p. 35).

Another general technique for deriving this sequence, known as Newton's iteration, is obtained by letting 👁 x=sqrt(n)
. Then 👁 x=n/x
, so the sequence

converges quadratically to the root. The first few approximants to 👁 sqrt(n)
are therefore given by

Wolfram's iteration provides a method for finding square roots of integers using the binary representation.

See also

Newton's Iteration, Pythagoras's Constant, Square Root, Wolfram's Iteration

Explore with Wolfram|Alpha

References

Flannery, S. and Flannery, D. In Code: A Mathematical Journey. London: Profile Books, p. 132, 2000.Wells, D. The Penguin Dictionary of Curious and Interesting Numbers. Middlesex, England: Penguin Books, pp. 34-35, 1986.Wolfram, S. A New Kind of Science. Champaign, IL: Wolfram Media, p. 1168, 2002.

Referenced on Wolfram|Alpha

Square Root Algorithms

Cite this as:

Weisstein, Eric W. "Square Root Algorithms." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/SquareRootAlgorithms.html

Subject classifications