home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / arch / 10857 < prev    next >
Encoding:
Internet Message Format  |  1992-11-18  |  2.3 KB
  1. Path: sparky!uunet!mcsun!uknet!strath-cs!sproven
  2. From: sproven@cs.strath.ac.uk (Simon B Proven IE91)
  3. Newsgroups: comp.arch
  4. Subject: Re: integer distance or sqrt
  5. Message-ID: <11027@baird.cs.strath.ac.uk>
  6. Date: 18 Nov 92 15:39:17 GMT
  7. References: <CLIFFC.92Nov15184340@miranda.rice.edu> <MOSS.92Nov16094710@CRAFTY.cs.cmu.edu> <1992Nov17.143914.19700@mcs.drexel.edu>
  8. Sender: news@cs.strath.ac.uk
  9. Organization: Comp. Sci. Dept., Strathclyde Univ., Glasgow, Scotland.
  10. Lines: 42
  11. Nntp-Posting-Host: hunter-08
  12.  
  13. In article <1992Nov17.143914.19700@mcs.drexel.edu> dmagagno@mcs.drexel.edu (David Magagnosc) writes:
  14. >This reminds me of something I came up with not long after the
  15. >Midatlantic ACM Region Programming Contest last year.  One of the
  16. >problems involved computing square roots by the long division-like
  17. >method (which they claimed we all learned in elementary school).
  18. >I translated it to binary, applied the techniques used for division,
  19. >and came up with a sort of non-restoring square root.
  20.  
  21. >Now, the convergence is linear (2 bits of input for 1 bit of output
  22. >per iteration), but it uses only elementary operations like shifts
  23. >and adds, so its run time should be comparable to a single division.
  24. >Newton's method, on the other hand, typically uses division on
  25. >every iteration.
  26.  
  27. >So, the real question is, has someone done something like this before?
  28. >How does it really compare for smallish (under 32 or maybe even 64
  29. >bit) square roots?
  30.  
  31. I wrote a FP library last year on the ARM(2/3) and tried both the Newton
  32. method and the long division type method.  With a good approximation from
  33. the Newton method I was getting 6,000 or so sqrts per second on an 8MHz
  34. ARM2.  My implementation of the long-division type algorithm got about
  35. 30,000 sqrts per second.
  36.  
  37. QED? :)
  38.  
  39. >Oh yes, it can also be extended very easily to compute fixed point
  40. >square roots of integers -- as many bits as you like.
  41.  
  42. Yes - in the fp library, the routine gets 24 bits of output from 24 bits
  43. of input, by assuming that there are another 24 0s tagged onto the input.
  44.  
  45. >
  46. >D. Magagnosc
  47. >-- 
  48. >496620796F752063616E207265616420746869732C20796F752063616E206265636F6D65206120
  49. >636F6D70757465722070726F6772616D6D657220616E6420676574206120676F6F64206A6F622E
  50.  
  51. mad@bike
  52. -- 
  53. * Simon Proven -  Secretary, University of Strathclyde Green Group *
  54. * sproven@cs.strath.ac.uk             REAL (tm) peeps ride bike :) *
  55.