„Benutzer:DerSpezialist/Ganzzahlige Quadratwurzel“ – Versionsunterschied

In number theory, 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 .$

For example, ${\mbox{isqrt}}(27)=5$ because $5\cdot 5=25\leq 27$ and $6\cdot 6=36>27$.

Algorithm

One way of calculating ${\sqrt {n}}$ and ${\mbox{isqrt}}(n)$ is to use Newton's method to find a solution for the equation $x^{2}-n=0$, giving the recursive formula

${x}_{k+1}={\frac {1}{2}}\left(x_{k}+{\frac {n}{x_{k}}}\right),\quad k\geq 0,\quad x_{0}>0.$

The sequence $\{x_{k}\}$ converges quadratically to ${\sqrt {n}}$ as $k\to \infty$. It can be proven that if $x_{0}=n$ is chosen as the initial guess, one can stop as soon as

$|x_{k+1}-x_{k}|<1$

to ensure that $\lfloor x_{k+1}\rfloor =\lfloor {\sqrt {n}}\rfloor .$ However, it is usually more efficient to choose a better initial guess for n.

Domain of computation

Although ${\sqrt {n}}$ is irrational for almost all $n$, the sequence $\{x_{k}\}$ contains only rational terms when $x_{0}$ is rational. Thus, with this method it is unnecessary to exit the field of rational numbers in order to calculate ${\mbox{isqrt}}(n)$, a fact which has some theoretical advantages.

Stopping criterion

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

$|x_{k+1}-x_{k}|<c\$

ensures $\lfloor x_{k+1}\rfloor =\lfloor {\sqrt {n}}\rfloor$ in 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

• A geometric view of the square root algorithm