Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!csd4.milw.wisc.edu!bionet!ames!sun-barr!newstop!texsun!texbell!uhnix1!sugar!ficc!cliff
From: cliff@ficc.uu.net (cliff click)
Newsgroups: comp.lang.c
Subject: Re: Integer square root routine needed.
Summary: Integer square root
Message-ID: <5392@ficc.uu.net>
Date: 31 Jul 89 22:11:47 GMT
References: <7415@ecsvax.UUCP>
Organization: Ferranti International Controls
Lines: 40

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.) 

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@ficc.uu.net, +1 713 274 5368 (w).
Disclaimer: lost in the vortices of nilspace...       +1 713 568 3460 (h).