Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!csd4.milw.wisc.edu!cs.utexas.edu!uunet!elf115!rec
From: rec@elf115.uu.net (Roger Critchlow)
Newsgroups: comp.lang.c
Subject: Re: Integer square root routine needed.
Summary: ACM ALGORITHM 650
Message-ID: <177@elf115.uu.net>
Date: 2 Aug 89 18:33:12 GMT
References: <7415@ecsvax.UUCP> <5392@ficc.uu.net> <7204@microsoft.UUCP>
Organization: ELF, Sea Cliff, NY
Lines: 42

/*
** ALGORITHM 650:
** Efficient Square Root Implementation on the 68000
** Kenneth C. Johnson
** ACM Transactions on Mathematical Software,
** Vol 13, No. 2, June 1987, Pages 138-151.
**
** The result is rounded to the nearest integer
** unless TRUNCATE is #defined.
*/

typedef unsigned long uint;	/* 32 bit int for obsolete compiler :-) */

#define two_to_the(x)	((uint)1 << (x))

uint isqrt(x) uint x;
{
  register uint u, v, q, w;

  u = x;
  q = two_to_the(16) * (two_to_the(16)-1);

  if (u > q)
    return two_to_the(16);

  for (w = two_to_the(31); w > 0; w >>= 2) {
    v = (q - w) >> 1;
    if (u > v) {
      u -= v;
      q = v + w;
    } else
      q = v;
  }

  q >>= 1;

#if TRUNCATE
  return (u < q) ? q-1 : q;
#else
  return q;
#endif
}