[HN Gopher] How quickly do algorithms improve?
       ___________________________________________________________________
        
       How quickly do algorithms improve?
        
       Author : npalli
       Score  : 12 points
       Date   : 2021-10-17 01:33 UTC (21 hours ago)
        
 (HTM) web link (news.mit.edu)
 (TXT) w3m dump (news.mit.edu)
        
       | dataflow wrote:
       | I'm curious how they went about this. A lot of algorithms
       | "improve" older ones through taking e.g. a probabilistic approach
       | (thus introducing failure modes that weren't there previously),
       | or by using mechanical techniques like SIMD, or by parallelizing
       | previously sequential solutions. How do you measure and compare
       | improvements like that? The first one is hard to compare fairly,
       | and the other ones can easily depend on the hardware. Of course
       | there are cases where two algorithms solve exactly the same
       | problem and one is just plain faster too, but did they really
       | evaluate hundreds of those?
        
       | oluckyman wrote:
       | In section III B (p.8) the paper states that "in 1982...Gries[24]
       | devised another linear algorithm" for the maximum subarray
       | problem. I remember that. Jon Bentley visited Cornell, and posed
       | the problem to me and Gries together. We thought on it
       | independently overnight and presented a linear solution to
       | Bentley the next day. Gries had a simpler invariant, and I had
       | simpler code (using min). I never knew he wrote the paper until
       | now, and am not one of the several people he mentions in the
       | Acknowledgement, although he does say "Bentley...challenged US
       | with this problem".
        
         | Jensson wrote:
         | There are a lot of trivial papers to be written when a field is
         | young. Someone has to write them even if the discovery wasn't
         | hard to make.
        
       | vmception wrote:
       | The is a great study showing the algorithms have improved faster
       | than Moore's law and advances in computing in many cases, if only
       | the abstraction allowed for frontend and end users to experience
       | these gains more often.
        
       ___________________________________________________________________
       (page generated 2021-10-17 23:00 UTC)