Slashdot Mirror
Progress In Algorithms Beats Moore's Law
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."
more bloated GUI libraries (bling), and comfier runtimes (different VMs).
Thats an interesting figure because when the alpha came out DEC were predicting 1000 fold improvement in speed over about the same period. They split the improvement over factors of ten: clock speed, parallelism in the CPU and multiple cores were each expected to deliver a factor of ten improvement.
Now while our algorithms might be getting better our programmers definitely are not. A lot of those improved algorithms must be in our APIs. Like the way its easy to use a Hashtable in java now but in the last you might have just searched a linear array.
http://michaelsmith.id.au
What the Good Lord Algorithmic Efficiency Improvements giveth, the Evil Lord Real-Time-Virus-Scanner taketh away.
sed -e 's/Chuck Norris/Rajnikant/g' joke > fact
So how did they magically increase the number of transistors using software? Oh whait, someone didn't know what Moore's law was...
When hardware gets faster it applies more or less uniformly to all algorithms you run on that hardware. When an algorithm is improved it applies to just one specific problem. For some problems we already knew close to optimal algorithms 15 years ago, in those cases there was no way algorithmic improvements could have achieved such a speedup. And in fact the article mentions just one specific problem where algorithmic improvements made it about 43.000 times faster on one specific input. In other words, this number is not nearly as general as the summary makes it sound. The are algorithms that were not speeded up nearly as much, and for any algorithms that were bad enough to begin with, there could have been an even larger speedup - without anybody making a fuss about it.
Do you care about the security of your wireless mouse?
Moore's law is based more on economics than technology. He was just a hands on executive who had a clear vision of what the future would bring. Anybody who actually has read his original paper would realize this. The fact that his theory has held up this long is incredulous.
Doubles and higher-order tuples are an ongoing topic of research, much less mature than research on first posts.
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.
As always, all IMO. Insert "I think" everywhere grammatically possible.
OPTIMIZE YOUR SHIT.
Because tons of hardware is useless if you can't push it to it's limits with efficient code and algorithms.
Game and OS designers, I'm looking right at you.
Still waiting on Serviscope_minor to wake up to fucking reality and realize that Jessica Price isn't going to fuck him.
... Murphy still holds the lead.
Have gnu, will travel.
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 :-)
Bill Stewart
New Fast-Compression-only CPR http://preview.tinyurl.com/dy575ks
Okay here it is. I am in a bit of a rush I am sorry. You will have to fix a few things like putting in your own screen background. It has an fvwm script for monitoring nodes called "System Status". Generally Button1 is for starting things and Button2 is for configuration. It is set up to use ssh-askpass to set your ssh passphrase.
Got to go. My wife is insisting I sit down for christmas dinner.
http://michaelsmith.id.au