Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!csd4.milw.wisc.edu!bionet!apple!sun-barr!texsun!texbell!swbatl!wuarchive!wugate!wucs2!wucs1!kcc
From: kcc@wucs1.wustl.edu (Kenneth Charles Cox)
Newsgroups: comp.lang.c
Subject: Re: Integer square root routine needed.
Message-ID: <941@wucs1.wustl.edu>
Date: 2 Aug 89 18:41:04 GMT
References: <7415@ecsvax.UUCP>
Reply-To: kcc@wucs1.UUCP (Kenneth Charles Cox)
Distribution: usa
Organization: Washington University, St. Louis, MO
Lines: 58

In article <7415@ecsvax.UUCP> utoddl@ecsvax.UUCP (Todd M. Lewis) writes:
>This may be the wrong place to post this, but I need C source
>to a reasonably fast integer square root routine.  (Actually
>a clear description of an efficient algorithm would do--I can
>write the code myself.)

>So, How does one efficiently go about taking the square root
>of a long?

The following is the base-2 version of the square-root extraction
algorithm in which pairs of digits are brought down at each step.
I once thought of entering this in the Obfuscated C Code contest.

Advantages:
	It is exact, in the sense that isqrt(n) = k means k*k <= n
	and (k+1)*(k+1) > n, for n >= 0.
	Uses only subtraction, shifting, and bitwise logical ops.
Disadvantages:
	Requires BITS/2-1 iterations; so if your longs are 32 bits,
	it uses 15 iterations.

I don't have any comparisons of this with other methods.  It would
depend a lot on the hardware; if * and / are expensive, this may
be faster than (for example) Newton-Raphson despite the greater
number of iterations.  I would be interested in the results of a
timing comparison if you make one.


#define BITS (8*sizeof(long))	/* bits in a long */
long
isqrt(n)
register long n;
{
register long root,rem,t1,i;

	if (n < 0) return(-1);
	if (n == 0) return(0);

	for (i = BITS-2; !(n&(3 << i)); i -= 2);
	rem = ((n>>i)&3)-1;
	root = 1;

	for (i -= 2; i >= 0; i -= 2) {
		rem = (rem << 2) | ((n>>i)&3);
		t1 = root<<2;
		if (rem >= t1) t1 |= 1;
		root <<= 1;
		if (rem >= t1) {
			root |= 1;
			rem -= t1;
		}
	}
	return(root);
}

--------------
Ken Cox
kcc@wucs1.wustl.edu