home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / arch / 10818 < prev    next >
Encoding:
Text File  |  1992-11-17  |  1.5 KB  |  60 lines
  1. Newsgroups: comp.arch
  2. Path: sparky!uunet!zaphod.mps.ohio-state.edu!darwin.sura.net!spool.mu.edu!sol.ctr.columbia.edu!ira.uka.de!math.fu-berlin.de!news.netmbx.de!Germany.EU.net!mcsun!sunic!dkuug!imada!news
  3. From: breese@monet.imada.ou.dk (Bjoern Reese)
  4. Subject: Re: integer distance or sqrt
  5. Message-ID: <1992Nov17.113057.11993@imada.ou.dk>
  6. Sender: news@imada.ou.dk (USENET News System)
  7. Organization: Dept. of Math. & Computer Science, Odense University, Denmark
  8. References: <1992Nov16.172604.4947@sei.cmu.edu>
  9. Date: Tue, 17 Nov 1992 11:30:57 GMT
  10. Lines: 48
  11.  
  12. In article <1992Nov16.172604.4947@sei.cmu.edu> firth@sei.cmu.edu (Robert Firth)  
  13. writes:
  14. > In article <1992Nov16.110102.17077@imada.ou.dk> breese@monet.imada.ou.dk  
  15. (Bjoern Reese) writes:
  16. > 
  17. > >Heron(x)   {Fast integer squareroot routine}
  18. > >   IF x <= 64 THEN
  19. > >      y = 2 + (x >> 3)  {shift right 3 times}
  20. > >   ELSE
  21. >     ...
  22. > >   ENDIF
  23. > >   root := (y + x DIV y) >> 1
  24. > >
  25. > >This algorithm is faster than Newton's Method...
  26. > 
  27. > Maybe so, but Newton's method doesn't tell you that the square
  28. > root of 0 is 1.
  29.  
  30. :( Sorry about that :(
  31.  
  32. Let's fix it.
  33.  
  34. Heron(x)
  35.    IF x = 0 THEN
  36.       y = 1
  37.    ELSE
  38.       IF x <= 64 THEN
  39.       ...
  40.       ENDIF
  41.    ENDIF
  42.    root := (y + x DIV y) >> 1
  43.  
  44. or
  45.  
  46. Heron(x)
  47.    IF x = 0 THEN
  48.       root := 0
  49.    ELSE
  50.       IF x <= 64 THEN
  51.       ...
  52.       ENDIF
  53.       root := (y + x DIV y) >> 1
  54.    ENDIF
  55.  
  56. --
  57.  
  58. Bjoern Reese                   |     Email: breese@imada.ou.dk
  59. Odense University, Denmark     |     Voice: +45 65 932 182 (private)
  60.