home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / arch / 11045 < prev    next >
Encoding:
Text File  |  1992-11-24  |  2.0 KB  |  51 lines
  1. Newsgroups: comp.arch
  2. Path: sparky!uunet!utcsri!geac!itcyyz!yrloc!rbe
  3. From: rbe@yrloc.ipsa.reuter.COM (Robert Bernecky)
  4. Subject: Re: integer distance or sqrt
  5. Message-ID: <1992Nov20.151757.3391@yrloc.ipsa.reuter.COM>
  6. Reply-To: rbe@yrloc.ipsa.reuter.COM (Robert Bernecky)
  7. Organization: Snake Island Research Inc, Toronto
  8. References: <CLIFFC.92Nov15184340@miranda.rice.edu> <1992Nov16.110102.17077@imada.ou.dk>
  9. Date: Fri, 20 Nov 92 15:17:57 GMT
  10. Lines: 39
  11.  
  12. In article <1992Nov16.110102.17077@imada.ou.dk> breese@monet.imada.ou.dk (Bjoern Reese) writes:
  13. >In article <CLIFFC.92Nov15184340@miranda.rice.edu> cliffc@rice.edu (Cliff  
  14. >Click) writes:
  15. >> bbs.dennis@tsoft.sf-bay.org (Dennis Yelle) writes:
  16. >
  17. >I found it some years ago in a german magazine called "MC."
  18. >It was dubbed "Heron's Algorithm." As you can see it is a
  19. >16 bit implementation. Does anybody have further information
  20. >about this algorithm? (like, how to extend it to 32 bits.)
  21.  
  22. This from ACM SIGAPL Quote Quad, Vol 16, no 4, 1986, from
  23. "A Perfect Square Root Routine", by E.E. McDonnell:
  24.  
  25. "Heron, the Alexandrian scientist (possibly as early as the
  26. second century B.C or as late as the third century A.D.) devised
  27. a method for approximating square roots which is still in use today.
  28. The method is an iterative one, and exploits the fact that any
  29. particular estimate Y of the value of the square root R of a positive
  30. number X, if it is not equal to R, may be improved by computing the
  31. average of Y and X divided by Y, that is:
  32.    Y =. (Y +  X%Y) %2
  33.  
  34. If the estimate Y is positive, the method will eventually converge to
  35. the square root. ... The closer the initial estimate Y is to the eventual
  36. root, the fewer will be the number of iterations required. Much has
  37. been written on the subject of choosing best estimates... "
  38.  
  39. (And he goes on to describe how he did it for SHARP APL).
  40.  
  41. Bob
  42.  
  43.  
  44.  
  45.  
  46. Robert Bernecky      rbe@yrloc.ipsa.reuter.com  bernecky@itrchq.itrc.on.ca 
  47. Snake Island Research Inc  (416) 368-6944   FAX: (416) 360-4694 
  48. 18 Fifth Street, Ward's Island
  49. Toronto, Ontario M5J 2B9 
  50. Canada
  51.