Square Root Algorithms

A sequence of approximations to can be derived by factoring

(1)

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

(2)

(3)

and

			(4)
			(5)
			(6)

Therefore, and are given by the recurrence relations

			(7)
			(8)

with . The error obtained using this method is

(9)

The first few approximants to are therefore given by

(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 . The fact that if is an approximation to , then is a better one (the 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 . Then , so the sequence

(11)

converges quadratically to the root. The first few approximants to are therefore given by

(12)

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

Wolfram Web Resources