Cubic graph: Difference between revisions
en>David Eppstein m clean up citation postscripts, link journal names |
en>David Eppstein Undid revision 558848965 by 24.185.3.4 (talk) there IS a number, there ARE infinitely many, but not there ARE a number nor there IS infinitely many |
||
Line 1: | Line 1: | ||
In [[number theory]], the '''integer square root''' (isqrt) of a [[positive integer]] ''n'' is the positive integer ''m'' which is the [[floor and ceiling functions|greatest integer less than or equal]] to the [[square root]] of ''n'', | |||
: <math>\mbox{isqrt}( n ) = \lfloor \sqrt n \rfloor.</math> | |||
For example, <math>\mbox{isqrt}(27) = 5</math> because <math>5\cdot 5=25 \le 27</math> and <math>6\cdot 6=36 > 27</math>. | |||
==Algorithm== | |||
One way of calculating <math>\sqrt{n}</math> and <math>\mbox{isqrt}( n )</math> is to use [[Newton's method]] to find a solution for the equation <math>x^{2} - n = 0</math>, giving the [[Recursion|recursive]] formula | |||
: <math>{x}_{k+1} = \frac{1}{2}\left(x_k + \frac{ n }{x_k}\right), \quad k \ge 0, \quad x_0 > 0.</math> | |||
The [[sequence]] <math>\{ x_k \}</math> [[Limit (mathematics)|converges]] [[Rate of convergence|quadratically]] to <math>\sqrt{n}</math> as <math>k\to \infty</math>. It can be proven that if <math>x_{0} = n</math> is chosen as the initial guess, one can stop as soon as | |||
:<math>| x_{k+1}-x_{k}| < 1</math> | |||
to ensure that <math>\lfloor x_{k+1} \rfloor=\lfloor \sqrt n \rfloor.</math> | |||
==Domain of computation== | |||
Although <math>\sqrt{n}</math> is [[irrational number|irrational]] for [[almost all]] <math>n</math>, the sequence <math>\{ x_k \}</math> contains only [[rational number|rational]] terms when <math> x_0 </math> is rational. Thus, with this method it is unnecessary to exit the [[field (mathematics)|field]] of rational numbers in order to calculate <math>\mbox{isqrt}( n )</math>, a fact which has some theoretical advantages. | |||
==Stopping criterion== | |||
One can prove that <math>c=1</math> is the largest possible number for which the stopping criterion | |||
:<math>|x_{k+1} - x_{k}| < c\ </math> | |||
ensures <math>\lfloor x_{k+1} \rfloor=\lfloor \sqrt n \rfloor</math> | |||
in the algorithm above. | |||
In implementations which use number formats that cannot represent all rational numbers exactly (for example, floating point), a stopping constant less than one should be used to protect against roundoff errors. | |||
== See also == | |||
* [[Methods of computing square roots]] | |||
==External links== | |||
*[http://mathcentral.uregina.ca/RR/database/RR.09.95/grzesina1.html A geometric view of the square root algorithm] | |||
{{number theoretic algorithms}} | |||
[[Category:Number theoretic algorithms]] | |||
[[Category:Number theory]] | |||
[[Category:Root-finding algorithms]] |
Revision as of 04:17, 8 June 2013
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,
Algorithm
One way of calculating and is to use Newton's method to find a solution for the equation , giving the recursive formula
The sequence converges quadratically to as . It can be proven that if is chosen as the initial guess, one can stop as soon as
Domain of computation
Although is irrational for almost all , the sequence contains only rational terms when is rational. Thus, with this method it is unnecessary to exit the field of rational numbers in order to calculate , a fact which has some theoretical advantages.
Stopping criterion
One can prove that is the largest possible number for which the stopping criterion
ensures in the algorithm above.
In implementations which use number formats that cannot represent all rational numbers exactly (for example, floating point), a stopping constant less than one should be used to protect against roundoff errors.