home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / arch / 10861 < prev    next >
Encoding:
Internet Message Format  |  1992-11-18  |  4.3 KB
  1. Path: sparky!uunet!ogicse!emory!sol.ctr.columbia.edu!eff!news.oc.com!convex!weeks
  2. From: weeks@convex.com (Dennis Weeks)
  3. Newsgroups: comp.arch
  4. Subject: Re: integer distance or sqrt
  5. Summary: Two long-forgotten algorithmic approaches
  6. Keywords: square root, CORDIC
  7. Message-ID: <1992Nov18.161514.28700@news.eng.convex.com>
  8. Date: 18 Nov 92 16:15:14 GMT
  9. Article-I.D.: news.1992Nov18.161514.28700
  10. References: <55F0TB1w165w@tsoft.sf-bay.org> <CLIFFC.92Nov15184340@miranda.rice.edu>
  11. Sender: Dennis Weeks
  12. Organization: Engineering, CONVEX Computer Corp., Richardson, Tx., USA
  13. Lines: 59
  14. Nntp-Posting-Host: mozart.convex.com
  15. X-Disclaimer: This message was written by a user at CONVEX Computer
  16.               Corp. The opinions expressed are those of the user and
  17.               not necessarily those of CONVEX.
  18.  
  19. > I sent him an integer square root code using Newton's method.  I've done
  20. > this problem before and I'm sure there are better methods out there.  Does
  21. > somebody want to post/email something better than Newton's?
  22.  
  23. B. Reese's description of Heron's algorithm is interesting, although the
  24. obvious consequence of extension beyond 16 bits is increasing the number of
  25. nested if's (or case labels), and if you ever go to 64-bit integers that
  26. could really get out of control...  Here are two algorithms which I discovered
  27. long ago, which may also be worthy of consideration.
  28.  
  29. The first old mentod uses base 2 arithmetic instead of base 10, but basically
  30. just follows the method we all learned in high-school algebra class; I have
  31. seen it mentioned in some old computer architecture/algorithm books, and saw a
  32. particularly good implementation done by Eduardo D. Lara, at Link (the flight
  33. simulation division of Singer) in Sunnyvale, California.  I later implemented
  34. the same algorithm, for 32-bit integers, on an early Intel 8-bit chip.
  35.  
  36. Just after that I attended a talk by Tien Chi Chen at UC Berkeley, where he
  37. described an algorithm that was much faster -- the complexity is comparable
  38. to a multiplication algorithm, where the number of add-like operations is a
  39. function of the number of 1's in the operand (here it's not the original bit
  40. count, because the source operand gets subtractively modified during succes-
  41. sive algorithm steps, but statistically it's still like a small constant
  42. multiple of straightforward multiplication time).  In addition to square
  43. root, he does division, log,* and exponential functions -- all based on
  44. shift-and-add/subtract operations with execution time/complexity comparable
  45. to integer multiplication.  (He operates on the mantissa of floating-point
  46. numbers, and the same approach applies to integers.)
  47.  
  48. Chen published a paper describing this algorithm,
  49.     T. C. Chen [1972] The Automatic Generation of Exponentials,
  50.         Logarithms, Ratios and Square Roots.
  51.         IBM Journal of Research and Development 16: 380-388
  52.         (July 1972)
  53. His paper has been cited by several other authors, and if you have heard of
  54. the "CORDIC" technique you will recognize a lot of resemblance to Chen's
  55. algorithm.  His major "value added" was hardware to locate the leftmost 1
  56. in a binary integer representation; I know that sort of thing existed in
  57. several minicomputers in the 70's and 80's, and hope it's available on most
  58. machines now -- without it you'll just have to do that in software.
  59.  
  60. Because it depends on locating the leftmost bit, etc., I doubt that it could
  61. be implemented in C (certainly not in Fortran), raising another issue about
  62. Hardware Support for Numeric Algorithms, which I note has mostly become "how
  63. high-level languages need to be expanded to comply with mathematical needs" --
  64. but even in assembly language, with or without a "locate leftmost bit" opcode,
  65. it's quite easy to write this (Chen modeled it in APL for verification
  66. purposes, but I believe he relied on assembler for efficient execution).
  67.  
  68. Good luck...
  69. DW
  70.  
  71.   * about Chen's log -- all the other algorithms, given that there isn't an
  72.     exact integer result for an integer operand, have relative errors which
  73.     are less than the least significant bit of the operand.  However, Chen's
  74.     Log has an _absolute_ error near the least significant bit, meaning that
  75.     a log of a floating-point mantissa which is very near to 1.0 will have a
  76.     surprisingly large relative error because log(1+epsilon) is close to
  77.     epsilon (if epsilon is very small) and the log error is also near epsilon.
  78.