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).
return First_post_algo();
http://www.rootstrikers.org/
Algorithmists have Moore's Law envy.
Take the cheese to sickbay, the doctor should see it as soon as possible - B'Elanna Torres, "Learning Curve"
Even in the 1980's it was recognized in avionics that algorithm improvement accounted for several orders of magnitude of speed in computing -- out performing hardware advances of the day. We highlighted that article in Avionics Weekly -- proudly displaying it outside our cubicles.
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.
Moore's Law is that the number of transistors on a single integrated circuit would double - it has nothing to do with speedup.
//TODO: create a signature
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.
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.
Now, you have to disassemble the binary to make sure the compiler properly implemented tail recursion!
Sleep your way to a whiter smile...date a dentist!
Looks like both Moore's Law and the improvement in algorithms together don't beat out Gates's Law: Software bloat doubles every 18 months.
Disinfect the GNU General Public Virus!
Actually, the algorithm came from The Art of Computer Programming, and so it was written in assembly language to begin with.
Palm trees and 8
Remember when you were a youngster and you had to learn about O() ?
Well, over the years you lose sight of the importance of that.
Not too long ago, just for fun, I implemented a DFT naively, O(n^2), and as an FFT (O(n log n).
Try that and run it for 65536 points and see what happens, even on a fast machine...
Consider for example the humble matrix solver. Iterative solvers (only applicable for certain problem spaces) can get you n lg n sort of behaviors, as compared to n^3 for generalized gaussian elimination.
It's important to use the right algorithm !
Absolute statements are never true
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.
i read a sci-fi story once, i forget who it was by, where some space travellers found themselves in a situation where their computer failed. so they taught themselves maths, plotted the stars, learned to do trigonometry in their heads, and over the course of many months, the 30 or so travellers managed to work in parallel to calculate an approximate but accurate enough path to get themselves within range of rescuers.
then, there is another sci-fi story, called "The End of Eternity", which dates back to when the title "Computer" was utilised in exactly the same way as "Professor" is utilised, now. the hero of the story was a human named "Computer Harkan". Computer. "one who computes".
the point of mentioning these two things is very very simple: prior to modern "computers", parallel "Computing" algorithms were commonplace, well known, and heavily relied on. Along came "computers" and - you know what's coming next - exceedingly rapidly, all that incredibly valuable "parallel" expertise was lost, in favour of single-step, single-process algorithms. i believe we're paying for that loss of expertise, somewhat.
oo - please post your ~/.fvwmrc online somewhere! *excited*. i run fvwm too, i run fvwm too!
... 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