Progress In Algorithms Beats Moore's Law 166
Relic of the Future writes "Seen on the blog 'Algorithmic Game Theory,' a report to congress and the president about past and future advances in information technology notes that, while improvements in hardware accounted for an approximate 1,000 fold increase in calculation speed over a 15-year time-span, improvements in algorithms accounted for an over 43,000 fold increase."
Transistor increase with software? (Score:5, Informative)
Anonymous Coward (Score:2, Informative)
Linear Programming is a reasonably obscure optimisation method used in operational research, where you describe a complex management problem in terms of a series of linear inequalities, then use an algorithm to evaluate all the possible solutions until it has found the optimal one. The algorithmic improvements here mean that we have found ways of cutting down the space faster, while still coming to the best solution. For one particular problem with just the right characteristics it's very possible that an improvement of 43,000 times could be achieved, but this is almost certainly an atypical case, and in general improvements due to algorithms are almost certainly going to be a lot smaller than improvements due to processing speed over a long period.
Actual text of statement on relative improvements (Score:5, Informative)
Progress in Algorithms Beats Moore’s Law
Everyone knows Moore’s Law – a prediction made in 1965 by Intel co-founder Gordon Moore that the density of transistors in integrated circuits would continue to double every 1 to 2 years.
Fewer people appreciate the extraordinary innovation that is needed to translate increased transistor den- sity into improved system performance. This effort requires new approaches to integrated circuit design, and new supporting design tools, that allow the design of integrated circuits with hundreds of millions or even billions of transistors, compared to the tens of thousands that were the norm 30 years ago. It requires new processor architectures that take advantage of these transistors, and new system architectures that take advantage of these processors. It requires new approaches for the system software, programming languages, and applications that run on top of this hardware. All of this is the work of computer scientists and computer engineers.
Even more remarkable – and even less widely understood – is that in many areas, performance gains due to improvements in algorithms have vastly exceeded even the dramatic performance gains due to increased processor speed.
The algorithms that we use today for speech recognition, for natural language translation, for chess playing, for logistics planning, have evolved remarkably in the past decade. It’s difficult to quantify the improvement, though, because it is as much in the realm of quality as of execution time. In the field of numerical algorithms, however, the improvement can be quantified. Here is just one example, provided by Professor Martin Grötschel of Konrad-Zuse-Zentrum für Informationstechnik Berlin. Grötschel, an expert in optimization, observes that a benchmark production planning model solved using linear programming would have taken 82 years to solve in 1988, using the computers and the linear programming algorithms of the day. Fifteen years later – in 2003 – this same model could be solved in roughly 1 minute, an improvement by a factor of roughly 43 million. Of this, a factor of roughly 1,000 was due to increased processor speed, whereas a factor of roughly 43,000 was due to improvements in algo- rithms! Grötschel also cites an algorithmic improvement of roughly 30,000 for mixed integer programming between 1991 and 2008.
The design and analysis of algorithms, and the study of the inherent computational complexity of prob- lems, are fundamental subfields of computer science.
Re:Not so much (Score:5, Informative)
Mod parent up. If this claim were true in any generic sense, we'd see newer software generally running ever faster on older hardware, and it wouldn't seem that every generation of hardware improvement goes mostly towards visual eye-candy and anti-virus.
The problems the author cites, notably speech recognition, are cases that are notorious for *not* scaling to CPU power, that is, throwing brute force cycles at the problem only yields marginal benefits. While processing power doubles every 18 months, speech recognition only gets slightly better despite both better hardware and algorithmic advances.
More RAM, Faster CPUs make better Algos possible (Score:4, Informative)
One thing that's happened to improve algorithms, besides having people study Computer Science and take advantage of the work other people have done in academia and open source systems over the past few decades, is that computers are enough bigger and faster that you can solve problems that weren't feasible in the past, because you didn't have enough RAM, or disks were too small and you needed to use tape, or CPUs weren't fast enough to bother using some techniques, and having those tools gives you more choices of algorithms than I had when I was an undergrad in the 70s, or than my professors had when they were learning CS in the 60s and 50s. 640KB wasn't enough for everybody, and I remember a Star Wars funded research project at Princeton in the late 80s that had a VAX with 128MB of RAM crammed into it so they could study what you could do if you really always had enough RAM. (They didn't think 128MB was really quite enough, but it was a good start and they could get it funded, and it was still extravagantly large - they even had a 450MB disk drive just for swap :-)