Processing math: 100%

Newton's Method to Solve Integer Square Root

«  Akra-Bazzi Theorem
Binary Search Template  »

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+1xk|<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
}

Reference

Published on 16 Jan 2021 Find me on Facebook, Twitter!

«  Akra-Bazzi Theorem
Binary Search Template  »

Comments

    No comments found for this article.

Join the discussion for this article at here . Our comments is using Github Issues. All of posted comments will display at this page instantly.