home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / arch / 10639 < prev    next >
Encoding:
Internet Message Format  |  1992-11-11  |  3.7 KB
  1. Xref: sparky comp.arch:10639 comp.lang.misc:3600
  2. Newsgroups: comp.arch,comp.lang.misc
  3. Path: sparky!uunet!zaphod.mps.ohio-state.edu!darwin.sura.net!Sirius.dfn.de!Urmel.Informatik.RWTH-Aachen.DE!martin
  4. From: martin@math.rwth-aachen.de (  Martin Schoenert)
  5. Subject: Re: Hardware Support for Numeric Algorithms
  6. Message-ID: <martin.721555689@bert>
  7. Sender: news@Urmel.Informatik.RWTH-Aachen.DE (Newsfiles Owner)
  8. Nntp-Posting-Host: bert.math.rwth-aachen.de
  9. Organization: Rechnerbetrieb Informatik  /  RWTH Aachen
  10. References: <BwJ4uz.1rA@rice.edu> <1992Oct23.004313.29196@ntuix.ntu.ac.sg> <1992Oct29.153514.22927@yrloc.ipsa.reuter.COM> <1992Nov5.202412.7266@linus.mitre.org> <1992Nov10.153705.27804@yrloc.ipsa.reuter.COM>
  11. Date: 12 Nov 92 08:08:09 GMT
  12. Lines: 61
  13.  
  14. rbe@yrloc.ipsa.reuter.COM (Robert Bernecky) writes:
  15.  
  16.     I write programs for correctness and maintainability first, THEN worry
  17.     about little details such as performance. If you create something that's
  18.  
  19. bs@gauss.mitre.org (Robert D. Silverman) replied:
  20.  
  21.     You've probably never done any large scale computing.
  22.  
  23.     I measure the run time of my algorithms in MIPS-YEARS.  A MIPS-YEAR
  24.     is a 1 MIPS machine running for 1 year, or approximately 3.1 x 10^13
  25.     instructions.  Jobs that take several hundred MIPS-YEARS are not uncommon.
  26.  
  27. rbe@yrloc.ipsa.reuter.COM (Robert Bernecky) replied:
  28.  
  29.     Bad guess, unless Crays, 3090s (Yes, I know they barely count) and
  30.     a bit of CM-2 don't count.
  31.     Perhaps your code REALLY is MIPS-years in complexity. OR, it could
  32.     be that failure to design properly leads to that complexity, whereas
  33.     careful thought could reduce it to months or less. Since I don't
  34.     understand your problem, I can only speculate. However, I DO know
  35.     that algorithmic excellence is the way to get speed, NOT dinking
  36.     around with what you perceive to be a bottleneck at the bit-diddling
  37.     level. AFTER you have the algorithm right, THEN you start tweaking
  38.     bits. Optimization before design is usually a bad idea. 
  39.  
  40. What  you  say  about  working  on  the  algorithm  first  and  only then
  41. optimizing the  code is in principle right.  But as a  matter of fact  it
  42. isn't a counterargument.
  43.  
  44. Bob is talking about factorizations of large integers  (at least I assume
  45. so).  There are several extremly brilliant  mathematicians doing  nothing
  46. but trying  to find an even better  algorithm to factorize integers.  And
  47. there have been several new algorithms in the  last years (elliptic curve
  48. method,  [multiple]  polynomial  quadratic  sieve,  number  field sieve).
  49. Those algorithms have  been implemented very carefully, with all kinds of
  50. optimizations.  Still  if you take such an implementation and apply it to
  51. the currently  most wanted  factorizations they *will* run for MIPS years
  52. (e.g.  Lenstra,   Lenstra,   Manasse,  and   Pollard  estimated that  the
  53. factorization of F_9 = 2^512 + 1 took about 340 MIPS years).
  54.  
  55. bs@gauss.mitre.org (Robert D. Silverman) continued:
  56.  
  57.     Needless to say, there are people who have to worry about speed FIRST,
  58.     and that other considerations are (almost) irrelevent.
  59.  
  60. rbe@yrloc.ipsa.reuter.COM (Robert Bernecky) replied:
  61.  
  62.     Are you saying that speed is more important than correct answers? 
  63.     {I don't think so, but I though I had better ask.}
  64.  
  65. No, I don't think that this is what Bob is talking about.  However in the
  66. area of integer factorization correctness is easy to achieve, because you
  67. can  check your answers  so easily.   But  reasonable  efficiency can  be
  68. *very* difficult to obtain.
  69.  
  70. Martin.
  71.  
  72. -- .- .-. - .. -.  .-.. --- ...- . ...  .- -. -. .. -.- .-
  73. Martin Sch"onert,   Martin.Schoenert@Math.RWTH-Aachen.DE,  +49 241 804551
  74. Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, D 51 Aachen, Germany
  75.