Every so often Lance tweets about some science policy report. My natural tendency, like any good techie, is to keep my distance from such reports. I do recognize that they serve an important social function (like dentists or lawyers) but personally I would want to have as little as possible to do with them. However, I do sometimes skim over them, trying to gain some fuzzy insight or point of view. Here is an observation I picked from the Report to the President and Congress: Designing a Digital Future: Federally FUnded R&D in Networking and IT:
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. (…) 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 algorithms! Grötschel also cites an algorithmic improvement of roughly 30,000 for mixed integer programming between 1991 and 2008.
[…] This post was mentioned on Twitter by TCS blog aggregator. TCS blog aggregator said: Progress in Algorithms Beats Moore’s Law « Algorithmic Game-Theory/Economics: http://bit.ly/fYXJVY […]
Ascribing a 1000x improvement to “increased processor speed” seems very questionable. What’s the methodology? Possible issues: What about having more memory (2003-era memory today is easily 10^6 faster than 1988-era disk)? What about (algorithmically) better hardware-designs — things like better out-of-order execution, branch prediction and prefetching? It would be better to test the old and new algorithms on the same hardware.
I assume it’s just an assumption made to illustrate the partitioning of efficiency gain between hardware speedup and algorithmic optimizations, not a claim about factual hardware improvements in reality.
[…] 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 […]
@Anon67
Roughly passed 20 years. 20 years is about 10 cycles of improvement. 10 cycles of improvement equals 2^10. 2^10 = 1024. Q.E.D.
After a second thought. The moore law isn’t about brute speed, rather is about transistor count; so, while I think they thought roughly in the lines I mentioned, I’m not completely sure if their claim holds.
OTOH, as noted by Anon67, we could assign those to architectural improvements in hardware. This again leaves us with a factor 1000 for Moore’s Law and the rest for algorithmic improvements of soft- and hardware combined; the sw/hw-distinction if kind of fuzzy anyways.
[…] 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 […]
Robert Bixby (of Rice University and ILOG (now IBM)) has written an interesting paper on this and given presentations that update the material in the paper. I believe that Groetschel is quoting some of these numbers from Bixby’s work. See the 2002 paper published in Operations Resaerch, “Solving Real-World Linear Programs: A Decade and More of Progress.”
You can download a copy from:
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.74.821&rep=rep1&type=pdf
Congrats !
Your post somehow made it to /.
[…] seems that a recent blog post of mine got slashdotted. Looking at my blog’s stats, I see that the numbers of visitors to […]
[…] fact, suggests a report quoted here, improvement in algorithm efficiency has contributed more – by an order of magnitude – […]
Is that Bob Ross in the favicon?
=== popurls.com === popular today…
yeah! this story has entered the popular today section on popurls.com…
hi, would creating a binary table(0,1)on a basket ball court and putting tiny micro chips on each player create an algorthm for winning team performce ,than compared to a lotto ticket be possible,since we can train bees,maybe humans have the same type of inner algorthims
[…] […]
[…] Progress in Algorithms Beats Moore’s Law Every so often Lance tweets about some science policy report. My natural tendency, like any good techie, is to keep […] […]
[…] by floofy to programming [link] [15 comments] reddit: the voice of the internet — news before it happens @ […]
[…] em algoritmos propriciaram um aumento estimado de quarenta e três vezes em igual período. Fonte: Algorithmic Game-Theory/Economics. Posted in: Informativo ← Dream Maker LikeBe the first to like this post. Be […]
[…] Progress in Algorithms beats Moore’s Law […]
[…] Every so often Lance tweets about some science policy report. My natural tendency, like any good techie, is to keep my distance from such reports. I do recognize that they serve an important social function (like dentists or lawyers) but personally I would want to have as little as possible to do with them. However, I do sometimes skim over them, trying to gain some fuzzy insight or point of view. Here is an observation I picked from the Repo … Read More […]
[…] 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. (…) 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….” […]
[…] Posted on December 28, 2010. Filed under: Life in Progress | Every so often Lance tweets about some science policy report. My natural tendency, like any good techie, is to keep my distance from such reports. I do recognize that they serve an important social function (like dentists or lawyers) but personally I would want to have as little as possible to do with them. However, I do sometimes skim over them, trying to gain some fuzzy insight or point of view. Here is an observation I picked from the Repo … Read More […]
[…] algorithms are outpacing Moore’s Law. This is odd because it’s completely opposite to everything I thought I […]
[…] Progress in Algorithms Beats Moore’s Law – December 23, 2010 […]
I like your writing, always successful
[…] Progress in Algorithms Beats Moore’s Law […]
Hey, you have a great blog here! I’m definitely going to bookmark you! I have a http://www.http://kuwait-h.blogspot.com/.
[…] It’s also worth mentioning that our progress in software algorithms has consistently beaten Moore’s Law. […]
[…] that one used to get with just increased clock rates. Last year Noam Nisan wrote on related issues where he quoted from the Report to the President and Congress: Designing a Digital Future: […]
SportsBidding.com is the foremost athletics public auction site exactly where now you may conserve in order to 95% off retail store rather than loose cash!…
[…]Progress in Algorithms Beats Moore’s Law « Algorithmic Game-Theory/Economics[…]…
Buy Rap Beats…
[…]Progress in Algorithms Beats Moore’s Law « Algorithmic Game-Theory/Economics[…]…
Pest control…
[…]Progress in Algorithms Beats Moore’s Law « Algorithmic Game-Theory/Economics[…]…
Interesting post. Keep on with the good work Noam.
Amazing! Its in fact awesome paragraph, I have got much clear idea about from this paragraph.