From: martin@math.rwth-aachen.de (  Martin Schoenert)
Subject: Re: Hardware Support for Numeric Algorithms
Organization: Rechnerbetrieb Informatik  /  RWTH Aachen
Date: 12 Nov 92 08:08:09 GMT

rbe@yrloc.ipsa.reuter.COM (Robert Bernecky) writes:

    I write programs for correctness and maintainability first, THEN worry
    about little details such as performance. If you create something that's

bs@gauss.mitre.org (Robert D. Silverman) replied:

    You've probably never done any large scale computing.

    I measure the run time of my algorithms in MIPS-YEARS.  A MIPS-YEAR
    is a 1 MIPS machine running for 1 year, or approximately 3.1 x 10^13
    instructions.  Jobs that take several hundred MIPS-YEARS are not uncommon.

rbe@yrloc.ipsa.reuter.COM (Robert Bernecky) replied:

    Bad guess, unless Crays, 3090s (Yes, I know they barely count) and
    a bit of CM-2 don't count.
    Perhaps your code REALLY is MIPS-years in complexity. OR, it could
    be that failure to design properly leads to that complexity, whereas
    careful thought could reduce it to months or less. Since I don't
    understand your problem, I can only speculate. However, I DO know
    that algorithmic excellence is the way to get speed, NOT dinking
    around with what you perceive to be a bottleneck at the bit-diddling
    level. AFTER you have the algorithm right, THEN you start tweaking
    bits. Optimization before design is usually a bad idea. 

What  you  say  about  working  on  the  algorithm  first  and  only then
optimizing the  code is in principle right.  But as a  matter of fact  it
isn't a counterargument.

Bob is talking about factorizations of large integers  (at least I assume
so).  There are several extremly brilliant  mathematicians doing  nothing
but trying  to find an even better  algorithm to factorize integers.  And
there have been several new algorithms in the  last years (elliptic curve
method,  [multiple]  polynomial  quadratic  sieve,  number  field sieve).
Those algorithms have  been implemented very carefully, with all kinds of
optimizations.  Still  if you take such an implementation and apply it to
the currently  most wanted  factorizations they *will* run for MIPS years
(e.g.  Lenstra,   Lenstra,   Manasse,  and   Pollard  estimated that  the
factorization of F_9 = 2^512 + 1 took about 340 MIPS years).

bs@gauss.mitre.org (Robert D. Silverman) continued:

    Needless to say, there are people who have to worry about speed FIRST,
    and that other considerations are (almost) irrelevent.

rbe@yrloc.ipsa.reuter.COM (Robert Bernecky) replied:

    Are you saying that speed is more important than correct answers? 
    {I don't think so, but I though I had better ask.}

No, I don't think that this is what Bob is talking about.  However in the
area of integer factorization correctness is easy to achieve, because you
can  check your answers  so easily.   But  reasonable  efficiency can  be
*very* difficult to obtain.

Martin.

-- .- .-. - .. -.  .-.. --- ...- . ...  .- -. -. .. -.- .-
Martin Sch"onert,   Martin.Schoenert@Math.RWTH-Aachen.DE,  +49 241 804551
Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, D 51 Aachen, Germany
Newsgroups: comp.arch