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."
But we made up in ... (Score:5, Funny)
more bloated GUI libraries (bling), and comfier runtimes (different VMs).
Re:But we made up in ... (Score:5, Insightful)
On the flip side, people tend to be turned off when they see what my screen looks like. It has gotten to the point where I do not mention that this is "Linux," because I do not want new users to get scared. In the end, looking pretty winds up being more important than how efficiently you use computational resources.
Re: (Score:2)
At work I run fvwm with the mouse configured for left hand use with xmodmap and Button3 on the title bar set to close the window. Right handed users inevitably grab the mouse with their right hand and try to move a window with their Button1.
[OT] fvwm (Score:3)
oo - please post your ~/.fvwmrc online somewhere! *excited*. i run fvwm too, i run fvwm too!
Re: (Score:3)
Re:[OT] fvwm (Score:4)
Okay here it is [glitch.tl]. 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.
Re: (Score:2)
I get a similar effect by using a Dvorak keyboard layout at work (keycaps still in qwerty). Great fun when a coworker tries to enter a password on my keyboard.
Re: (Score:2)
using a Dvorak keyboard layout at work (keycaps still in qwerty).
:)
Re: (Score:3)
On my fvwm, I've set up the 8/9 buttons as follows: doubleclick 8 -> Hide, clidkdrag 8 -> Resize, doubleclick 9 -> Kill, clickdrag 9 -> Move. It seemed a bit weird the
Re: (Score:2)
I suppress titles on some window classes. NEdit has tabs and an information field to tell me which file has focus, so the title bar is redundant there. I might give your approach a go. It sounds interesting.
Re: (Score:2)
DestroyFunc invokeRootMenu
AddToFunc invokeRootMenu
+ I DestroyMenu recreate RootMenu
+ I AddToMenu RootMenu "r00tMenu [Desk $[desk.n]]" Title
+ I AddToMenu RootMenu "New" Function NewTerm
+ I All (Iconic,CurrentScreen) AddToMenu RootMenu ($[w.name])\ [$[w.desk]] WindowId $[w.id] SelectWindow
+ I All (!Iconic,CurrentScreen) AddToMenu RootMenu $[w.name]\ [$[w.desk]] WindowId $[w.id] SelectWindow
+ I AddToMenu RootM
Re: (Score:2)
I also like to have the window titles displayed in the background menu, eg. something like
DestroyFunc invokeRootMenu
AddToFunc invokeRootMenu
+ I DestroyMenu recreate RootMenu
+ I AddToMenu RootMenu "r00tMenu [Desk $[desk.n]]" Title
+ I AddToMenu RootMenu "New" Function NewTerm
+ I All (Iconic,CurrentScreen) AddToMenu RootMenu ($[w.name])\ [$[w.desk]] WindowId $[w.id] SelectWindow
+ I All (!Iconic,CurrentScreen) AddToMenu RootMenu $[w.name]\ [$[w.desk]] WindowId $[w.id] SelectWindow
+ I AddToMenu RootMenu "" Nop
+ I AddToMenu RootMenu "Restart" Restart fvwm2
+ I AddToMenu RootMenu "Quit" Quit
+ I Popup RootMenu
Mouse 1 R A WindowList
Re: (Score:2)
Re: (Score:2)
More screen space was one of the most important to me. You don't have to do as much moving and resizing ;). I was amazed what a difference it made moving from a 15" monitor at 1024x768 to a 19" monitor at 1600x1200. And now 24" wide screen LCDs and dual monitor setups are common. Keep the PDF viewer and browser with reference material and search results on one monitor, and have an integrated development environment on the other. I'm looking forward to 6'x3' tabletop size monitors.
Re: (Score:2)
I've always thought that people who insisted on left-handed mouse configs were pansies, and in fact, every one I've heard complain about it turned out to suffer chronic Munchhausen's syndrome, with many other symptoms.
I am left-handed. The QWERTY layout is one of the few tools that is specifically biased in southpaws' favor. The keyboard is by most measures a more complex object than the mouse, the latter of which can be flailed about until it works.
It's far easier to learn to use a mouse using your right h
Re: (Score:2)
The left handed configuration is more balanced. Backspace, delete and enter are both on the right side of the keyboard. I can select an object with my left and and activate it with the enter key using my right hand.
Re: (Score:2)
The biggest flaw I see with your logic is that the mouse is more of a precision device, so it makes sense to use it with your stronger hand.
I am left handed but I use the mouse right handed. Not because it's "better" but because it's a standard setup and there are so many right handed mice I don't want to limit myself.
Also, when I'm using the mouse and keyboard together I'm rarely typing. Usually I'm hitting backspace/delete, enter, etc. Not that it matters that I have to reach my left hand across the keybo
Re: (Score:2)
Re: (Score:2)
let me guess, you use emacs...
Re: (Score:2)
Re: (Score:2)
Well, the real question is, are users better off as a result? Personally, I found that most of the computationally intensive graphics were not actually helping me get my work done any faster, switched to a more minimal window manager and did all that I could to reduce the amount of CPU time spent on rendering the GUI (disabling special effects wherever I saw them), and discovered that, in fact, I was correct: none of those effects were actually helping me get my work done.
On the flip side, people tend to be turned off when they see what my screen looks like. It has gotten to the point where I do not mention that this is "Linux," because I do not want new users to get scared. In the end, looking pretty winds up being more important than how efficiently you use computational resources.
I'm not going to argue that on a Linux desktop anyway, the special effects are mostly just that, special effects, but you might get yourself into a situation like in a car; ripping the sound dampening material out makes it more efficient, but is not worth it 99.9% of the time. Animation is used in interfaces on a couple OSs that will go nameless to provide a smooth visual transition from one state to another. It isn't a new concept, it's just easier to do with today's hardware. I think the problem is ani
Re: (Score:2)
I'm not going to argue that on a Linux desktop anyway, the special effects are mostly just that, special effects, but you might get yourself into a situation like in a car; ripping the sound dampening material out makes it more efficient, but is not worth it 99.9% of the time.
Except that I never claimed that disabling the effects made me more efficiently, but rather that it did not make me any less efficient. The only effect that is remotely useful is the smooth transition between workspaces, mainly because it helps me subconsciously keep track of "where" I am without using a paging window; even then, only a couple frames of animation is really necessary. Beyond that? Translucent windows? Rotating cubes? Wobbly windows?
Maybe you are right -- maybe the cool looking effe
Re: (Score:2)
Re: (Score:2)
When I studied computer science back in 1989 or so, my professor made a joke. He said that computing power would probably be used only to "draw an animated trashcan" and so we shouldn't be too wildly optimistic about increasing processing power. Ofcourse, we all had a big laugh.
20 years later, the joke doesn't seem so funny anymore.
Re: (Score:2)
I can't talk about runtimes, but my window manager is currently taking up less than 3% of my CPU. If yours is sucking up dramatically more than that then I'm somewhat surprised...
Re: (Score:2)
It is not CPU time, it is wall clock time.
BTW, this is one reason why web applications currently suck, they are extremely slow on best and make you wait for seconds and sometimes even longer on worst.
Re: (Score:2)
Wall clock time? My PC never seems to be waiting on something being drawn, so I'm not sure why graphical fluff would be a problem.
Re: (Score:2)
In other words (Score:2)
Algorithmists have Moore's Law envy.
Re: (Score:2)
Well, they worked hard, studied a lot, improved the algorithms, lots of testing, implementation care, etc
Then some doofus comes and does "select * from table;"
Not for the first time (Score:2)
1000 fold (Score:5, Interesting)
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.
Re:1000 fold (Score:5, Interesting)
Now while our algorithms might be getting better our programmers definitely are not.
Sometimes this is intentional. One of the more fun software competitions I've run across is to write the slowest sorting algorithm. Trivial programming tricks such as do-nothing loops that just run a counter to use time disqualify you, obviously. The judging is solely on the algorithm, by comparing the O(N) functions. One of the winners in the early years was a sort that generated a random permutation of the data, and tested it for sortedness, repeating if it wasn't sorted. And it turns out that there are several progressively worse variants of this, depending on how ridiculous your random-permutation algorithm is.
I should go find this contest again, and see what sorting atrocities they've come up with in the past couple years ...
(I did once read a suggestion that such contests not be widely publicised, out of fear that managers will find them and declare the winning algorithms the new company standards. ;-)
Re: (Score:2)
The judging is solely on the algorithm, by comparing the O(N) functions.
Hehe I once managed to put an expensive function inside the inner loop making a mostly O(N) function more like O(N^2)... that gets very noticable when you got 100k file hashes you're trying to match. It would have made a pretty good run for stupidest algorithm. But when you don't really have a benchmark, the results were correct it wasn't that obvious what I did wrong except it ran very, very slowly.
Re: (Score:2)
You consider n! slow? Really? Try the original bogosort algorithm as proposed by Jon Doyle when he was a researcher at CMU.
1) Given a list of integers to sort, replace each integer in the list with the integer which represents the Ackerman function of that integer
2) Sort the list using any other sorting algorithm you would care to use
3) Take the inverse Ackerman function of each number of the list.
Where v is the list of input values, this algorithm runs in time O(n*A(max(v)-1) (which is a worst case runni
Re: (Score:2)
Yeah; I think that's one of the seminal papers of the subject area. It mentions the sort algorithm that generates permutations and tests each one for being sorted. But it's more general, addressing the problem of solving a problem as reluctantly as possible, while demonstrably making progress with each step.
There are suspicions that various commercial products were written by adherents of this school of software algorithms ...
Re:1000 fold (Score:4, Interesting)
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.
There are more programmers because programming is becoming more accessible, so naturally more people who suck at programming are doing it.
There's another problem: while gains from Moore's law have historically been realized by a recompile or less, most new algorithms require actually changing the code.
Re: (Score:2)
There's another problem: while gains from Moore's law have historically been realized by a recompile or less, most new algorithms require actually changing the code.
I think you're forgetting about actually changing the hardware, in the former case.
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 :-)
Re: (Score:2)
Someone still has to be able to write and maintain the API.
It's like not being allowed to use a calculator in low level math.
Re: (Score:2)
No, but you should understand the algorithms you use, and be able to troubleshoot them, or replace them when needed. If not, you have no business using them -- then you're just connecting black boxes, which is as far from programming as stapling prefab is from carpentry.
Re: (Score:2)
One of the programs I wrote needs to search an array of tens of thousands of 128-bit entries to see if a particular value is in there*, then repeat this hundreds of thousands of times for different searches. I know that the tidy way to do this would be to sort the array first, but I don't - because the thing is executing on a 2.4GHz processor, and I just can't be bothered to write a sorter and binary search just to save a few miliseconds off the processing time.
Re: (Score:2)
Re: (Score:2)
I assumed the point was that the hash version should basically be the same four lines of code. Replace the array with a hash (set) at the instantiation and none of the rest of the code should have to change.
What Good Lord Giveth ... (Score:5, Funny)
Re: (Score:3)
What the Good Lord Algorithmic Efficiency Improvements giveth, the Evil Lord Real-Time-Virus-Scanner taketh away.
Heretic! Thine computer is a vessel of purity whose sole purpose for existence is to be continually purged of impurity. Thou shalt be grateful for the pittance of cycles that our great Real-Tyme Virus Scanner does leave ye to work with your ill begotten "productivity applications."
Transistor increase with software? (Score:5, Informative)
Re: (Score:2)
Virtual Machines?
Re: (Score:2)
Re: (Score:2)
What you don't seem to hear in this argument is that Moore's law is only about manufacturing process. It has no direct impact on performance so there is no point in mentioning it as far as performance is involved.
What could be somewhat relevant would be a hardware architecture improvement vs software architecture improvements comparison.
History shows us that it is indeed more relevant like when Intel went from the Pentium 4 to the Pentium M (i.e. Pentium 3 with a vengeance) eventually leading to the Core ar
Re: (Score:3)
Not so much (Score:5, Insightful)
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.
Re: (Score:2)
While processing power doubles every 18 months
That may have been the case at one point but it hasn't been true recently.
I bought the 13 inch macbook i'm typing this on over 3 years ago. It has a 2.16GHz C2D. When I look at laptops now I still see dual core chips at 2.GHz. Occasionally a quad core is seen but the clock speed (with all four cores running) is only arround that of my macbook (slightly over if you count turbo and buy the extreme edition).
Over in desktop land a similar thing is true, by mid 2007
Re:Not so much (Score:4, Insightful)
The grandparent didn't say "clock speed doubles". It said "processing power doubles". In the last few years those things have been very distinct, in some cases processing power increasing while clock speeds have actually become lower.
Re: (Score:2)
In the last few years those things have been very distinct
P4 to core was a huge increase in performance per clock but that was some time ago and afaict increases since then have been more evoloutionary than revoloutionary.
I stand by my statement that the improvement in the last 3 years is closer to 2x that 4x at least for CPUs that are available at anything like a sane price, The hex cores push that to 3x but only if you have a heavily multi-threaded workload and nearly $1000 to drop on the CPU alone.
See fo
Re: (Score:2)
P4 to core was a huge increase in performance per clock but that was some time ago and afaict increases since then have been more evoloutionary than revoloutionary.
I stand by my statement that the improvement in the last 3 years is closer to 2x that 4x at least for CPUs that are available at anything like a sane price, The hex cores push that to 3x but only if you have a heavily multi-threaded workload and nearly $1000 to drop on the CPU alone.
See for example an anadtech bench comparison of a Q6600 to an i7-950 http://www.anandtech.com/bench/Product/53?vs=100 [anandtech.com]
But again you're talking speed. That's what this benchmark measures. Moore's law, on the other hand, talks about number of transistors.
The improvements that have come with the Westmere architecture are not to be scoffed at (unless all you look at are old code benchmarks[*]). Some of them include
- 32 nm processing
- six cores
- L3 cache shared by all cores
- huge page support
- graphics processor inside the CPU packaging
- lowered power usage
- SSE 4.2 and AES-NI instructions
- real mode virtualization
- Obsoleti
Re: (Score:2)
Over in desktop land a similar thing is true, by mid 2007 we had 2.67 GHz C2Qs. Now we have 3. GHz i7 quads and hexes.
There has been improvement in the last 3 years but afaict it's closer to 2x than 4x.
A Core i series CPU is substantially faster at the same clock speed than a Core 2 series CPU.
Re: (Score:2)
While processing power doubles every 18 months
That may have been the case at one point but it hasn't been true recently.
I suspect that this is the common misunderstanding of Moore's Law. Although Moore's itself refers to the number of transistors, until recently it *was* fair to say that the Moore's increases were accompanied by broadly comparable increases in computational speed, and most people assumed that Moore's referred to the latter, or at least implied it.
Although Moore's Law itself still hasn't been broken, the change in focus to multi-core processors (which I assume we both know *isn't* the same as a 2 or 4 times
Re: (Score:2)
indeed. Said "law" can either increase the number of transistors pr core, or drop the cost pr core as one manage to fit more cores pr wafer and so increase production yields.
Re: (Score:2)
It is true in MANY senses. Take a game like Cube, which uses a very novel and efficient approach to representing and rendering a 3d world for a first person shooter. Send that code back in time to the day's of Wolf3D and it would blow them away on their same old-to-us hardware.
Re: (Score:2)
I think you misinterpret what I mean by "true in any generic sense". I'm talking about the idea of algorithmic performance outpacing hardware performance applying across the board, as the article and summary seem to imply.
I'm entirely aware that new innovative algorithms can make great improvements in specific cases. However, in the vast majority of technology domains, the performance gains of more efficient software rarely outpace the performance gains of hardware over time (in many cases the opposite,
Re: (Score:2)
Do you have any counterexamples? That is, for what problems was the optimal algorithmic solution known 20 years ago?
Re: (Score:2)
Again, you misinterpret me. I never said more optimal algorithmic solutions are not being developed in any domain, just that the rate of performance gain from such optimizations are generally not as rapid as developments in hardware.
For example, database technology. As mature a tech as that is, algorithmic improvements are being made every day, I'm sure. But you can't tell me that the improvement you get in database performance over the past 10 years is more due to better software than better hardware,
Re: (Score:2)
Newer software is adding functionality faster than the algorithmic advances are making it faster.
Re:Not so much (Score:4, Insightful)
And in fact the article mentions just one specific problem where algorithmic improvements made it about 43.000 times faster on one specific input.
I think a more general issue is citing a constant as the speedup for an algorithm. Improvements in algorithms often refer to improvements in the asymptotic efficiency, rather than constant factors. If I asked you how much of an improvement a switch from selection sort to merge sort would be, you would not tell me "it is 1000 times faster" because that would be wrong (except for a particular input size).
Montgomery Scott school of programming (Score:2)
Re: (Score:2)
I do not really care about boot time (after all, the phone does not turn on instantly too), however, software andoperating systems did get slower over time with not much improvement to justify the slowness.
For example, Windows Vista and 7 require much better hardware than Windows XP, but apart from the changes in GUI it's not much different. So, where do the clock cycles and memory go? Windows 2003 (fresh install) runs quite fast inside a VM on one of my PCs (3x Xeon 700MHz, 3GB RAM) with one CPU and 256-38
When the phone reboots a few times a day (Score:2)
OSes on the other hand do need to be boot more, especially laptops if you don't want to lose charge in standby or you care about crypto which only works if you power off. In standby mode, people can freeze the memory and transplant it to another computer.
The other problem is that OSes that boot slow also tend to run slow. The user interface slowness is something developers and
Re: (Score:2)
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.
I get what you're saying, but still agree with the article. There's one trivially simple algorithmic adjustment that's far more common now than 15 years ago: memoizing functions. I told a story [slashdot.org] a while back about changing a coworker's code from running for 4 hours to 8 seconds. The crux of the change was using a Python dict to store the output of a function and re-using it whenever possible, and the 99+% cache hit rate had a magical effect on runtime. It also took half a GB of RAM.
That wouldn't have been a
Re: (Score:2)
some good leds and make 'em blink at hypnotic 4HZ
And if you make 'em blink at 8HZ, you might get a migraine.
Re: (Score:3)
You are right, that is another aspect to it. It is entirely possible that a problem that required lots of disk I/O 15 years ago would fit in RAM today, maybe it would even fit in L3 cache. Under such circumstances it may be that an unmodified algorithm would run a million times faster on a modern computer compared to a computer from 15 years ago. Even if no part of the machine is a million times faster. In fact having enough RAM could mean
45 years later (Score:4, Insightful)
Moore's Law has nothing to do with speedup (Score:2)
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 i
Re: (Score:3)
are we stupid or something? (Score:2)
I'm not sure they know what Moore's law is.
Oh, a submission from tim? of course it's wrong.
nothing new here
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: (Score:2)
Without knowing about the "before" and "after" algorithm, it's hard to know if the "after" algorithm couldn't have been run earlier because there wasn't enough memory.
I've written a lot of stuff that runs a hell of a lot faster lately, but I use a lot more memory than I did 20 years ago.
Any realistic scenario will chalk up around a factor of at least 8000 to memory improvements, leaving, oh, maybe a factor of 5 to pure algorithmic improvements.
Re: (Score:2)
Yeah, but things are still slower (Score:3)
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.
Re: (Score:2)
I've always wondered how they get away with advertising each version of Windows as "the fastest version EVER!"... while steadily increasing the minimum hardware requirements on the box.
You mean it runs faster on a faster computer? Gosh, bowl me over.
we lose sight of algorithmic importance (Score:2)
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
Moral of the story... (Score:3, Insightful)
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.
parallel algorithms (Score:3)
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.
Not all algorithms can be parallelized (Score:2)
http://en.wikipedia.org/wiki/P_complete [wikipedia.org]
Re: (Score:2)
Except - your descriptions don't prove this at all. The second one in particular gives us nothing but the name of the hero.
43,000 fold? (Score:2)
I don't understand, how does it mean algorithm improvement of 43,000 fold? Who needs 43,000 fold when anyone can easily make 1,000,000 fold improvement!
Proof:
Let N=1000
O(N^2) = 1,000,000
O(N) = 1000
O(log N) = 3
O(1) = 1
O(N^2)/O(1) = 1,000,000 / 1 = 1,000,000
Wait till we made improvement in O(N!) problems like traveling salesman and see how huge improvement that's gonna be!
Does This Account For Increases In Memory? (Score:2)
While processing power has increased over the years, the amount of memory that can be built in to a given amount of space has grown at a similar rate. So while it's easy to account for pure processing performance increases, what about algorithms that improved due to the space-time tradeoff [wikipedia.org], which would allow more complex algorithms that use more memory in return for requiring less processing time?
It seems disingenuous to say that algorithm improvements beat Moore's Law if they're really just benefiting from
And yet ... (Score:4, Funny)
... Murphy still holds the lead.
Yes! Faster bubble sorts! (Score:2)
Ah, I remember looking at the sorting algorithm in a low level graphics library. Tightly hand coded, packed to keep every pipeline stage filled and make optimal use of all the parallel units in a VLIW graphics processor, it was probably the most efficient bubble sort I'd ever seen.
I coded up a quicksort to about the same degree of tightness in a couple days, and, golly gee, a whole bunch of code suddenly got faster. Some MUCH faster... That was Lesson 1 for me. Optimize algorithms before optimizing impl
What restraint! (Score:2)
Given the conflict of interest in the report evidenced by:
It's amazing they didn't report a billion-fold increase in algorithms resulting from government funded R&D.
Deployment has improved, not quality (Score:2)
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.
I for one am yet to see any major improvements in speech recognition in the last ten years. It seems that it plateaued around 1995-2000 and hasn't had any decent improvements since.
Meanwhile, speech recognition has seen an increase in deployments in things such as:
Re: (Score:2)
if it's any consolation, human brains still struggle with speech recognition of Australians too
Re: (Score:3)
Re: (Score:2)
Now, you have to disassemble the binary to make sure the compiler properly implemented tail recursion!
Re: (Score:3)
Re: (Score:2)
Re:First post algo (Score:5, Funny)
Doubles and higher-order tuples are an ongoing topic of research, much less mature than research on first posts.
Re: (Score:2)
Patent it, this has to be stopped.