Integer square root

Integer square root

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 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.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • Square root — Measured fall time of a small steel sphere falling from various heights. The data is in good agreement with the predicted fall time of , where h is the height and g is the acceleration of gravity. In mathematics, a square root of a number x is a… …   Wikipedia

  • Square root of 2 — The square root of 2, also known as Pythagoras constant, often denoted by:sqrt{2} or √2but can also be written as:2^{1/2},,is the positive real number that, when multiplied by itself, gives the number 2. Its numerical value approximated to 65… …   Wikipedia

  • Square root of a matrix — In mathematics, the square root of a matrix extends the notion of square root from numbers to matrices. A matrix B is said to be a square root of A if the matrix product B · B is equal to A.[1] Contents 1 Properties 2 Computation methods …   Wikipedia

  • Square root of 5 — The square root of 5 is the positive real number that, when multiplied by itself, gives the prime number 5. This number appears in the formula for the golden ratio. It can be denoted in surd form as::sqrt{5}.It is an irrational algebraic number.… …   Wikipedia

  • Square number — In mathematics, a square number, sometimes also called a perfect square, is an integer that can be written as the square of some other integer; in other words, it is the product of some integer with itself. So, for example, 9 is a square number,… …   Wikipedia

  • Root of unity — The 5th roots of unity in the complex plane In mathematics, a root of unity, or de Moivre number, is any complex number that equals 1 when raised to some integer power n. Roots of unity are used in many branches of mathematics, and are especially …   Wikipedia

  • root — root1 rootlike, adj. /rooht, root/, n. 1. a part of the body of a plant that develops, typically, from the radicle and grows downward into the soil, anchoring the plant and absorbing nutriment and moisture. 2. a similar organ developed from some… …   Universalium

  • Root system — This article discusses root systems in mathematics. For root systems of plants, see root. Lie groups …   Wikipedia

  • Root — /rooht/, n. 1. Elihu /el euh hyooh /, 1845 1937, U.S. lawyer and statesman: Nobel peace prize 1912. 2. John Wellborn /wel beuhrn/, 1851 91, U.S. architect. * * * In botany, the underground anchoring part of a plant. It grows downward in response… …   Universalium

  • Root rectangle — In geometry, a root rectangle is rectangle in which the ratio of the longer side to the shorter is the square root of an integer, such as √2, √3, etc.cite book author=Jay Hambidge authorlink=Jay Hambidge title=Dynamic Symmetry: The Greek Vase… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”