TOPICS
Search

Square Root Algorithms


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

 a^2-nb^2=+/-1
(1)

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

 (a+bsqrt(n))(a-bsqrt(n))=+/-1
(2)
 (a+bsqrt(n))^k(a-bsqrt(n))^k=(+/-1)^k=+/-1,
(3)

and

(1+sqrt(n))^1=1+sqrt(n)
(4)
(1+sqrt(n))^2=(1+n)+2sqrt(n)
(5)
(1+sqrt(n))(a+bsqrt(n))=(a+bn)+sqrt(n)(a+b).
(6)

Therefore, a and b are given by the recurrence relations

a_i=a_(i-1)+b_(i-1)n
(7)
b_i=a_(i-1)+b_(i-1)
(8)

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

 |a/b-sqrt(n)|=1/(b(a+bsqrt(n)))<1/(2b^2).
(9)

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

 1,1/2(1+n),(1+3n)/(3+n),(1+6n+n^2)/(4(n+1)),(1+10n+5n^2)/(5+10n+n^2),....
(10)

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

 x_k=1/2(x_(k-1)+n/(x_(k-1)))
(11)

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

 1,1/2(1+n),(1+6n+n^2)/(4(n+1)),(1+28n+70n^2+28n^3+n^4)/(8(1+n)(1+6n+n^2)),....
(12)

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 Web Resource. https://mathworld.wolfram.com/SquareRootAlgorithms.html

Subject classifications