FACTOID # 19: Single guys should check out The Virgin Islands, where the women outnumber the men.
 
 Home   Encyclopedia   Statistics   Countries A-Z   Flags   Maps   Education   Forum   FAQ   About 
 
WHAT'S NEW
RECENT ARTICLES
More Recent Articles »
 

FACTS & STATISTICS    Simple view

  1. Select countries to view: (hold down Control key and click to select several)

     

     

    Compare:

     

     
  1. Select fact or statistic: (* = graphable)

     

     

     

  2. (OPTIONAL) Compare to statistic: (both need to be graphable)

     

     

     

  3. View result as:

     

       
(OR) SEARCH ALL encyclopedia, stats & forums:   

Encyclopedia > 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, To meet Wikipedias quality standards, this article or section may require cleanup. ... Euclid, detail from The School of Athens by Raphael. ... A negative number is a number that is less than zero, such as −3. ... The integers consist of the positive natural numbers (1, 2, 3, …), their negatives (−1, −2, −3, ...) and the number zero. ...

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

For example, isqrt(27) = 5 because 5 * 5 = 25 < 27 and 6 * 6 = 36 > 27.

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 In numerical analysis, Newtons method (or the Newton-Raphson method) is an efficient algorithm for finding approximations to the zeros (or roots) of a real-valued function. ... A Sierpinski triangle —a confined recursion of triangles to form a geometric lattice. ...

{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 In mathematics, a sequence is a list of objects (or events) arranged in a linear fashion, such that the order of the members is well defined and significant. ... In mathematics, the concept of a limit is used to describe the behavior of a function as its argument either gets close to some point, or as it becomes larger and larger; or the behavior of a sequences elements, as their index becomes larger and larger. ... In numerical analysis (a branch of mathematics), the speed at which a convergent sequence approaches its limit is called the rate of convergence. ...

| xk + 1 − xk | < 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. In mathematics, an irrational number is any real number that is not a rational number, i. ... In mathematics, a rational number (or informally fraction) is a ratio or quotient of two integers, usually written as the vulgar fraction a/b, where b is not zero. ... This article presents the essential definitions. ...


Stopping criterion

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

| xk+1 − xk | < 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+1 − xk | < 0.5.

See also


  Results from FactBites:
 
Square root Summary (1805 words)
Per the fundamental theorem of algebra, there are two solutions to the square root of any number (although these roots may not be distinct, as in the square root of zero).
Square roots of positive integers are often irrational numbers, i.e., numbers not expressible as a ratio of two integers.
In geometrical terms, the square root function maps the area of a square to its side length.
Square root - Wikipedia, the free encyclopedia (1274 words)
Square roots of positive integers are often irrational numbers, i.e., numbers not expressible as a ratio of two integers.
In geometrical terms, the square root function maps the area of a square to its side length.
Thus defined, the square root function is holomorphic everywhere except on the non-positive real numbers (where it isn't even continuous).
  More results at FactBites »


 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments
Please enter the 5-letter protection code

Want to know more?
Search encyclopedia, statistics and forums:
 


Lesson Plans | Student Area | Student FAQ | Reviews | Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms.