[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)