# All Science Fair Projects

## Science Fair Project Encyclopedia for Schools!

 Search    Browse    Forum  Coach    Links    Editor    Help    Tell-a-Friend    Encyclopedia    Dictionary

# Science Fair Project Encyclopedia

For information on any area of science that interests you,
enter a keyword (eg. scientific method, molecule, cloud, carbohydrate etc.).
Or else, you can start by choosing any of the categories below.

# Integer square root

In number theory (a branch of mathematics), the integer square root (isqrt) of a positive integer n is the positive integer m which is the greatest integer less than or equal to the square root of n,

$\mbox{isqrt}( n ) = \lfloor \sqrt n \rfloor.$
 Contents

## Algorithm

To calculate √n, and in particular, isqrt(n), one can use Newton's method for the equation x2 - n = 0, which gives us the recursive formula

${x}_{k+1} = \frac{1}{2}\left(x_k + \frac{ n }{x}_{k}\right), \ k \ge 0.$

One can choose for example x0 = n as initial guess.

The sequence {x k} converges quadratically to √n as k→∞. It can be proved (the proof is not trivial) that one can stop as soon as

| xk + 1xk | < 1

to ensure that $\lfloor x_{k+1} \rfloor=\lfloor \sqrt n \rfloor.$

## Domain of computation

Let us note that even if √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 isqrt(n), a fact which has some theoretical advantages in number theory.

## Stopping criterion

One can prove that c = 1 is the largest possible number for which the stopping criterion

| xk+1xk | < c

ensures $\lfloor x_{k+1} \rfloor=\lfloor \sqrt n \rfloor$ in the algorithm above.

Since actual computer calculations involve roundoff errors, one needs to use c < 1 in the stopping criterion, e.g.,

| xk+1xk | < 0.5.