Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!uwm.edu!cs.utexas.edu!sun-barr!decwrl!shelby!neon!rokicki
From: rokicki@Neon.Stanford.EDU (Tomas G. Rokicki)
Newsgroups: comp.graphics
Subject: roots
Message-ID: <1989Dec30.224826.17106@Neon.Stanford.EDU>
Date: 30 Dec 89 22:48:26 GMT
Sender: USENET News System <news@Neon.Stanford.EDU>
Organization: Computer Science Department, Stanford University
Lines: 18

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 ;
}