[comp.graphics] roots

rokicki@Neon.Stanford.EDU (Tomas G. Rokicki) (12/31/89)

Here's a different root algorithm I just made up (based on decimal root
extraction ala long division.)  I'm sure it's in widespread use already
but I just had to reply to that `solution' that required a multiplication
per step . . .

unsigned long root(v) /* for up to 32-bit values */
register unsigned long v ;
{
   register unsigned long t, r ;

   for (t=0x40000000, r=0; t; t >>= 2)
      if (t + r <= v) {
         v -= t + r ;
         r = (r >> 1) | t ;
      } else
         r = r >> 1 ;
   return r ;
}