Integer square root routine needed.

[Paul Hudson]

Here you are. This came with much sweat & tears about 2 years ago. No
comments, and bad style, sorry.  A real non-quiche-eater program.

/*
 *	@(#)sqroot.c	1.1	6/26/87
 *	Paul's magic square root routine
 */

main()
{
  unsigned i;
  printf("testing them all!\n");
  
  for (i = 1; i != 65536; i += 1)
  {
    if ((i & 255) == 0) printf("%d\r", i);
    if (i != sqroot(i*i))
      printf(" i %d sqroot %d\n", i, sqroot(i*i));
  }
}

sqroot(n)
register unsigned n;
{
  unsigned  result, acc;
  int  j;

 /* find the highest non-zero pair of bits */
  acc = n;
  for (j = -2; acc > 3; j += 2) 
    acc >>=2;
  result = 1;
  acc -= 1;
  for ( ; j >= 0; j -= 2)
  {
    result <<= 1;
    acc = (acc << 2) + ((n >> j) & 03);
    if ((result << 1) < acc)
    {
      acc -= (result << 1) + 1;
      result += 1;
    }
  }
  return result;
  
}


--
Paul Hudson	 MAIL: Monotype ADG, Science Park, Cambridge, CB4 4FQ, UK.
		PHONE: +44 (223) 420018	  EMAIL: paul at moncam.co.uk,
	;"	  FAX: +44 (223) 420911		 ...!ukc!acorn!moncam!paul
 `"";";"        These opinions void where prohibited by law.