Integer square root routine needed.
Kenneth Charles Cox
kcc at wucs1.wustl.edu
Thu Aug 3 04:41:04 AEST 1989
In article <7415 at ecsvax.UUCP> utoddl at 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 at wucs1.wustl.edu
More information about the Comp.lang.c
mailing list