Home > Integer square root

In mathematics and Number theory, the integer square root (isqrt) of a number n in the reals which is non-negative and non-zero is the number m which is the greatest integer less than or equal to the square root of n.

1 Calculating the integer square root

The first and most obvious, but least satisfactory method of calculating the integer square root of a number n is to simply take its square root, and round down. This is actually quite optimal for small numbers, but in number theory, where exactness is everything, conversions from floating-point to integers are absolutely unsatisfactory.

However, luckily enough, there are more appropriate ways to calculate the integer square root of a number n.

2 Newton's Iteration

The beauty of Newton's Iteration for finding the integer square root of a number n is that it can use solely integers, which is essential for accurate number theory. Newton's Iteration is simply defined as the Recursive function,

This recurrence converges quadratically as

2.1 Proof

Assuming that Newton's method for approximating roots is valid, we can also prove that Newton's Iteration is valid.

Start with the function , and notice that the roots of the equation are ± Now use and and write down Netwon's root-finding method:

which can be simplified to obtain:

And finally, if (4) is used to define the recursive function of Newton's method, then the result is (2).

3 External links

• Newton's Iteration -- from MathWorld
• Newton's Method