home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / arch / 10777 < prev    next >
Encoding:
Text File  |  1992-11-15  |  1.8 KB  |  56 lines
  1. Newsgroups: comp.arch
  2. Path: sparky!uunet!mcsun!sunic!dkuug!imada!news
  3. From: breese@monet.imada.ou.dk (Bjoern Reese)
  4. Subject: Re: integer distance or sqrt
  5. Message-ID: <1992Nov16.110102.17077@imada.ou.dk>
  6. Sender: news@imada.ou.dk (USENET News System)
  7. Organization: Dept. of Math. & Computer Science, Odense University, Denmark
  8. References: <CLIFFC.92Nov15184340@miranda.rice.edu>
  9. Date: Mon, 16 Nov 1992 11:01:02 GMT
  10. Lines: 44
  11.  
  12. In article <CLIFFC.92Nov15184340@miranda.rice.edu> cliffc@rice.edu (Cliff  
  13. Click) writes:
  14. > bbs.dennis@tsoft.sf-bay.org (Dennis Yelle) writes:
  15. > > I first considered asking for a integer sqrt, but maybe if the context is 
  16. > 
  17. > I sent him an integer square root code using Newton's Method.  I've done 
  18. > this problem before and I'm sure there are better methods out there.  Does 
  19. > somebody want to post/email something better than Newton's?
  20.  
  21. Try this one:
  22.  
  23. Heron(x)   {Fast integer squareroot routine}
  24.    IF x <= 64 THEN
  25.       y = 2 + (x >> 3)  {shift right 3 times}
  26.    ELSE
  27.       IF x <= 1024 THEN
  28.          y = 8 + (x >> 5)
  29.       ELSE
  30.          IF x <= 8192 THEN
  31.             y = 32 + (x >> 7)
  32.          ELSE
  33.             IF x <= 32767 THEN
  34.                y = 64 + (x >> 8)
  35.             ELSE
  36.                y = 128 + (x >> 9)
  37.             ENDIF
  38.          ENDIF
  39.       ENDIF
  40.    ENDIF
  41.    root := (y + x DIV y) >> 1
  42.  
  43. This algorithm is faster than Newton's Method, as it only
  44. consists of compares, adds and shifts, and no loops :) Oh
  45. yes, and a single integer division.
  46.  
  47. I found it some years ago in a german magazine called "MC."
  48. It was dubbed "Heron's Algorithm." As you can see it is a
  49. 16 bit implementation. Does anybody have further information
  50. about this algorithm? (like, how to extend it to 32 bits.)
  51.  
  52. --
  53.  
  54. Bjoern Reese                   |     Email: breese@imada.ou.dk
  55. Odense University, Denmark     |     Voice: +45 65 932 182 (private)
  56.