🚀 go-pugleaf

In article <CLIFFC.92Nov15184340@miranda.rice.edu> cliffc@rice.edu (Cliff  
Click) writes:
> bbs.dennis@tsoft.sf-bay.org (Dennis Yelle) writes:
> > I first considered asking for a integer sqrt, but maybe if the context is 
> 
> I sent him an integer square root code using Newton's Method.  I've done 
> this problem before and I'm sure there are better methods out there.  Does 
> somebody want to post/email something better than Newton's?

Try this one:

Heron(x)   {Fast integer squareroot routine}
   IF x <= 64 THEN
      y = 2 + (x >> 3)  {shift right 3 times}
   ELSE
      IF x <= 1024 THEN
         y = 8 + (x >> 5)
      ELSE
         IF x <= 8192 THEN
            y = 32 + (x >> 7)
         ELSE
            IF x <= 32767 THEN
               y = 64 + (x >> 8)
            ELSE
               y = 128 + (x >> 9)
            ENDIF
         ENDIF
      ENDIF
   ENDIF
   root := (y + x DIV y) >> 1

This algorithm is faster than Newton's Method, as it only
consists of compares, adds and shifts, and no loops :) Oh
yes, and a single integer division.

I found it some years ago in a german magazine called "MC."
It was dubbed "Heron's Algorithm." As you can see it is a
16 bit implementation. Does anybody have further information
about this algorithm? (like, how to extend it to 32 bits.)

--

Bjoern Reese                   |     Email: breese@imada.ou.dk
Odense University, Denmark     |     Voice: +45 65 932 182 (private)