Integer square root routine needed.
cliff click
cliff at ficc.uu.net
Tue Aug 1 08:11:47 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.)
Here's mine:
/********* C code to perform integer square root *************/
long sqrt();
main()
{
register long i;
for(i=0; i < 100; i++)
printf("%ld->%ld\t",i,sqrt(i));
printf("\n32767=%ld, 16000=%ld",sqrt(32767L),sqrt(16000L));
printf("\n2000000000=%ld\n",sqrt(2000000000L));
printf( " 123456789=%ld\n",sqrt( 123456789L));
}
long sqrt(a) /* Integer square root */
long a;
{
register unsigned long b,c;
if( a <= 1 ) return a; /* Can't handle zero, one */
c = b = a; /* Start at start */
while( b ) c>>=1,b>>=2; /* Get sqrt accurate to 1 bit in c */
for( b = 0; b < 4; b++ ) /* 4 iterations of newtons */
c = ((a+c*c)>>1)/c; /* Newtons method */
/* c = ((a>>1)+((c*c)>>1))/c; /* Slightly slower, prevents overflow, loses 1 bit */
return c; /* Return it */
}
--
Cliff Click, Software Contractor at Large
Business: uunet.uu.net!ficc!cliff, cliff at ficc.uu.net, +1 713 274 5368 (w).
Disclaimer: lost in the vortices of nilspace... +1 713 568 3460 (h).
More information about the Comp.lang.c
mailing list