The integer square root of a positive integer n is the positive integer m>=√n.
One way of calculating √n is to use Newton’s method. Here is the formula:
{xk+1=12(xk+nxk),k>=0,x0>0stop when |xk+1−xk|<1ensure ⌊xk+1⌋=⌊√n⌋C Implementation
// Square root of integer
unsigned long int_sqrt ( unsigned long s )
{
unsigned long x0 = s >> 1; // Initial estimate
// Sanity check
if ( x0 )
{
unsigned long x1 = ( x0 + s / x0 ) >> 1; // Update
while ( x1 < x0 ) // This also checks for cycle
{
x0 = x1;
x1 = ( x0 + s / x0 ) >> 1;
}
return x0;
}
else
{
return s;
}
}
Swift Implementation
func int_sqrt(_ x: Int) -> Int {
if x == 0 { return 0 }
var r = x >> 1
while r*r > x {
r = (r + x/r) >> 1
}
return r
}
Comments
Join the discussion for this article at here . Our comments is using Github Issues. All of posted comments will display at this page instantly.