Integer-Based Square Roots

roots

While working on a recent project, I had the need to calculate the square root of a (long) integer. I remembered I wrote some integer-based math functions way-back in the early 90’s. So I searched through a pile of old 3.5” floppy disks, and found it. The routine is listed below (notice the old style function declaration).

I couldn’t recall any of the details that I used in writing that function, so I did some searching on the Internet, and was quickly led to this book, The Math Toolkit for Real-Time Development, by Jack W. Crenshaw. The gist of the algorithm can be found in his EE Times article, Rooting for “Integer Square Roots”.

long sqrt()
register long n;
{
	register long l, k;
	long i, j;

	if (n == 0)
		return(0);
	k = 1;
	j = 0;
	do {
		l = j;
		j = k;
		k = (j + (n / j)) >> 1;
	}
	while (k != l);
	return(j);
}
Advertisements

About Jim Eli

µC experimenter
This entry was posted in Uncategorized and tagged , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s