home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / arch / 10969 < prev    next >
Encoding:
Internet Message Format  |  1992-11-20  |  1.8 KB
  1. Path: sparky!uunet!zaphod.mps.ohio-state.edu!wupost!cs.utexas.edu!sun-barr!news2me.EBay.Sun.COM!seven-up.East.Sun.COM!sungy!weissnics!ulrich
  2. From: ulrich@weissnics.Germany.Sun.COM (Ulrich Graef SUN Frankfurt TSE)
  3. Newsgroups: comp.arch
  4. Subject: Re: integer distance or sqrt
  5. Message-ID: <6839@sungy.Germany.Sun.COM>
  6. Date: 20 Nov 92 17:53:43 GMT
  7. References: <55F0TB1w165w@tsoft.sf-bay.org>
  8. Sender: news@sungy.Germany.Sun.COM
  9. Reply-To: ulrich@weissnics.Germany.Sun.COM
  10. Organization: Sun Microsystems
  11. Lines: 34
  12. Nntp-Posting-Host: weissnics
  13.  
  14. If you are able to spend some memory, you can improve the processing very much.
  15.  
  16.  
  17. First Method:    There are only 2^16  square roots of a number, which is 32 Bits long.
  18.         So generate a table of the squares of the numbers from
  19.              2            2
  20.             0   ... ( 2^16 - 1 )
  21.         and find the square root with a binary search. You need only
  22.         1 comparison, 1 addition, 1 shift and 1 assignment per search step.
  23.         If you unroll the loop, you do not need any loop overhead.
  24.         Disadvantage: the table consumes 256 KB.
  25.  
  26.         You can also use the same table to square your dx and dy, if
  27.         your multiplication is slower than a table lookup.
  28.  
  29.  
  30. Second Method:    Use Newton, but find the first approximation with a table lookup.
  31.                 
  32.         Variant a:    Use a table of the square roots of  0 .. 255 (* 2^24)
  33.                 Perform the lookup with the first byte.
  34.                 You need 2 additional iterations with Newton.
  35.                 The table consumes 1 KB.
  36.  
  37.         Variant b:    Use a table of the square roots of 0 .. (2^16-1)
  38.                                              (* 2^16)
  39.                 Perform the lookup with teh first two bytes.
  40.                 You need 1  Newton iteration (onle`y 1 division!).
  41.                 Disadvantage: the table consumes 256 KB.
  42.  
  43. I think,  if you spend enwough memory (you have no PC?) you can calculate the
  44. distance very fast with the second method, variant b!
  45.  
  46. Uli
  47.          
  48.