home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / arch / 10789 < prev    next >
Encoding:
Internet Message Format  |  1992-11-16  |  1.7 KB
  1. Path: sparky!uunet!ogicse!das-news.harvard.edu!cantaloupe.srv.cs.cmu.edu!netnews-2.srv.cs.cmu.edu!moss
  2. From: moss@cs.cmu.edu (Eliot Moss)
  3. Newsgroups: comp.arch
  4. Subject: Re: integer distance or sqrt
  5. Message-ID: <MOSS.92Nov16094710@CRAFTY.cs.cmu.edu>
  6. Date: 16 Nov 92 14:47:10 GMT
  7. Article-I.D.: CRAFTY.MOSS.92Nov16094710
  8. References: <55F0TB1w165w@tsoft.sf-bay.org>
  9.     <CLIFFC.92Nov15184340@miranda.rice.edu>
  10. Sender: news@cs.cmu.edu (Usenet News System)
  11. Reply-To: moss@cs.cmu.edu
  12. Organization: Dept of Comp and Info Sci, Univ of Mass (Amherst)
  13. Lines: 19
  14. In-Reply-To: cliffc@rice.edu's message of 16 Nov 92 00:43:40 GMT
  15. Nntp-Posting-Host: crafty.fox.cs.cmu.edu
  16.  
  17. I don't recall the details, but there are more clever ways to calculate
  18. distance (sqrt(x^2 + y^2)), which avoid the overflow problems of the squaring
  19. and summing. I suspect the principle is something like this (assuming x > y >=
  20. 0): dist = x * sqrt (1 + (y/x)^2). One then applies an appropriate
  21. approximation method to this instance of sqrt (note that 0 <= y/x < 1). Of
  22. course, if you're sure you won't overflow, and an integer result is accurate
  23. enough for you, I'd suggest the direct method, unrolling the Newton's Method
  24. iteration an appropriate fixed number of times by hand. (The algorithm
  25. converges very rapidly, about doubling the number of bits on each iteration;
  26. it is about the only approximation method with such rapid convergence.)
  27. --
  28.  
  29. J. Eliot B. Moss, Associate Professor    Visiting Associate Professor
  30. Department of Computer Science        School of Computer Science
  31. Lederle Graduate Research Center    Carnegie Mellon University
  32. University of Massachusetts        5000 Forbes Avenue
  33. Amherst, MA  01003            Pittsburgh, PA  15213-3891
  34. (413) 545-4206, 545-1249 (fax)        (412) 268-6767, 681-5739 (fax)
  35. Moss@cs.umass.edu            Moss@cs.cmu.edu
  36.