Path: utzoo!utgpu!jarvis.csri.toronto.edu!rutgers!cbmvax!mitchell
From: mitchell@cbmvax.commodore.com (Fred Mitchell - PA)
Newsgroups: comp.graphics
Subject: Integral Square Root
Message-ID: <9170@cbmvax.commodore.com>
Date: 30 Dec 89 07:16:53 GMT
Reply-To: mitchell@cbmvax.UUCP (Fred Mitchell - PA)
Organization: Commodore Technology, West Chester, PA
Lines: 23

I've noticed that there's some interest in integer square root algorithms.
Here's one that is short, fast, and sweet. It depends on the bit-shifting
facilities of C. This one is geared for finding the square-root of a
32-bit unsigned, resulting in a 16-bit root. It should be easy to adapt
to other languages and/or integer sizes. Enjoy!

ULONG  Isqrt(n)
ULONG  n;
{
   register i, r, rb, b;

   for (i = 15, r = 0; i >= 0; --i)
       if ( (rb = r+(b=1<<i)) * rb <= n)
           r += b;
   return (ULONG) r;
}


    -Mitchell
     mitchell@cbmvax.UUCP

     There are evils on this rock greater than even YOU
     can imagine.