- Integer square root
In
number theory , the integer square root (isqrt) of apositive integer "n" is the positive integer "m" which is the greatest integer less than or equal to thesquare root of "n",: mbox{isqrt}( n ) = lfloor sqrt n floor.
For example, mbox{isqrt}(27) = 5 because 5cdot 5=25 le 27 and 6cdot 6=36 > 27.
Algorithm
To calculate sqrt{n}, and in particular, mbox{isqrt}( n ), one can use
Newton's method for the equation x^{2} - n = 0, which gives us the recursive formula: x}_{k+1} = frac{1}{2}left(x_k + frac{ n }{x_k} ight), quad k ge 0, quad x_0 > 0.One can choose for example x_{0} = n as initial guess.The
sequence x_k } converges quadratically to sqrt{n} as k o infty. It can be proven (the proof is not trivial) that one can stop as soon as:x_{k+1}-x_{k}| < 1to ensure that lfloor x_{k+1} floor=lfloor sqrt n floor.Domain of computation
Although sqrt{n} is irrational for most n, the sequence x_k } contains only rational terms. Thus, with Newton's method one never needs to exit the field of rational numbers in order to calculate mbox{isqrt}( n ), a fact which has some theoretical advantages.
topping criterion
One can prove that c=1 is the largest possible number for which the stopping criterion :x_{k+1} - x_{k}| < censures lfloor x_{k+1} floor=lfloor sqrt n floorin the algorithm above.
Since actual computer calculations involve roundoff errors, a stopping constant less than 1 should be used, e.g.:x_{k+1} - x_{k}| < 0.5.
See also
*
Methods of computing square roots External links
* [http://www.codecodex.com/wiki/index.php?title=Calculate_an_integer_square_root Code to calculate the integer square root]
* [http://mathcentral.uregina.ca/RR/database/RR.09.95/grzesina1.html A geometric view of the square root algorithm]
Wikimedia Foundation. 2010.