Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!mailrus!csd4.milw.wisc.edu!cs.utexas.edu!uunet!mcvax!ukc!acorn!moncam!paul
From: paul@moncam.co.uk (Paul Hudson)
Newsgroups: comp.lang.c
Subject: Re: Integer square root routine needed.
Message-ID: <PAUL.89Aug1121410@marvin.moncam.co.uk>
Date: 1 Aug 89 11:14:10 GMT
References: <7415@ecsvax.UUCP>
Sender: paul@moncam.co.uk
Organization: Monotype ADG, Cambridge, UK.
Lines: 53
In-reply-to: utoddl@ecsvax.UUCP's message of 31 Jul 89 13:28:11 GMT

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@moncam.co.uk,
	;"	  FAX: +44 (223) 420911		 ...!ukc!acorn!moncam!paul
 `"";";"        These opinions void where prohibited by law.