home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / arch / 10837 < prev    next >
Encoding:
Internet Message Format  |  1992-11-17  |  1.8 KB
  1. Path: sparky!uunet!ferkel.ucsb.edu!taco!gatech!swrinde!zaphod.mps.ohio-state.edu!cs.utexas.edu!qt.cs.utexas.edu!yale.edu!ira.uka.de!math.fu-berlin.de!news.netmbx.de!Germany.EU.net!mcsun!sunic!dkuug!diku!torbenm
  2. From: torbenm@diku.dk (Torben AEgidius Mogensen)
  3. Newsgroups: comp.arch
  4. Subject: Re: integer distance or sqrt
  5. Message-ID: <1992Nov17.174049.19179@odin.diku.dk>
  6. Date: 17 Nov 92 17:40:49 GMT
  7. References: <55F0TB1w165w@tsoft.sf-bay.org> <CLIFFC.92Nov15184340@miranda.rice.edu> <MOSS.92Nov16094710@CRAFTY.cs.cmu.edu> <1992Nov17.143914.19700@mcs.drexel.edu>
  8. Sender: torbenm@freke.diku.dk
  9. Organization: Department of Computer Science, U of Copenhagen
  10. Lines: 29
  11.  
  12. dmagagno@mcs.drexel.edu (David Magagnosc) writes:
  13.  
  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
  28. before?
  29.  
  30. Yes, and it has ben discussed on the net earlier (I think in
  31. comp.theory or sci.math).
  32.  
  33. >How does it really compare for smallish (under 32 or maybe even 64
  34. >bit) square roots?
  35.  
  36. Very well, depending of course of whether you have fast hardware
  37. division. If division is implemented using shifts, the square root is
  38. usually one-and-a-half times as slow as division.
  39.  
  40.     Torben Mogensen (torbenm@diku.dk)
  41.