I can get as excited about an n log n solution as anyone, but I don’t pretend to be a real expert in algorithmic analysis. But I’m interested.
One upon a time, I remember people claiming that more of the tremendous increase in speed of computations was due to improved algorithms than faster hardware. It wasn’t a ridiculous claim.
Moore’s law is slowing down, but surely the rate of algorithm improvement has as well. Hard to see how you trump the FFT.
West Hunter 
Most of the low-hanging algorithmic fruit has indeed been plucked. There are still people doing interesting work in the “basically pure math” branch of CS, but in terms of concrete/business results these days it’s all about operations. Google has open sourced most of their machine learning libraries, but good luck ingesting 10^18 events per second without their infrastructure. The basic algorithms in use there were invented in the late 90s but it’s only recently that hardware has become cheap / parallel enough to do things efficiently.
For numerical math, there’s still some room for improvements:
On the FFT, there’s some improvements in butterfly architectures and stuff to make them better for hardware implementation. FFTs and inverse FFTs get used a lot in modern OFDM radio systems like WiFi and LTE. However, the actual implementation in RF chips is often is a bunch of multiply-accumulate block RAM subsystems – at least that’s what I do and I think it trumps FFT and IFFT in practice.
I think the great potential increase can come from better representations of what are now done as floating point numbers. Most numerical methods needed end up using a lot of multiply and accumulates. This is difficult with floating point and multiply is hard because it needs a barrel shifter. An alternative is a logarithmic number system which makes multiply easy but the problem is that add and subtract become hard. NVIDIA and hearing aid electronics have gotten clever with this stuff. There’s gotta be a way to come up with a number system that is easy for both X and +… it’d be a real advance.
Neural nets can be done better in HW. The Palm Pilot guy, Jeff Hawkins and IBM has been working on some short cuts as well as a friend of mine.
There’s a lot of tricks with bloom filters, bitmaps, and ternary CAMs.
Bloom filters are absolutely the most fun data structures.
A great deal of code, maybe most of it, is still written in COBOL, because most code is written for business and finance.
https://cis.hfcc.edu/faq/cobol
PS. The Shuttles flew on FORTRAN, which is still widely used in engineering.
That’s mostly maintenance on old code though, and the reasons for it have more to do with cost and managerial inertia than anything.
FORTRAN is still used – and a lot – because it is jim dandy for primarily numeric computations and the upgraded versions of FORTRAN include features that are absolutely alien to the original product, e.g., block structure, typing, and calls by value, reference, and value return. My last serious programming jobs, for an engineering firm and a medical database system, primarily involved FORTRAN. I’ve several times worked on projects that involved upgrading large systems from an older to a newer version of FORTRAN.
COBOL is another story. It now exists only in legacy systems and these are becoming steadily rarer. I once worked for a major bank that bought a brand new mainframe, installed on it a simulator of a decades earlier computer system and then used this simulator to run legacy COBOL code. It was like buying a brand new Lamborghini, ripping out the engine and transmission, and attaching a plow horse to the result. But I guessed it saved them money programming several million lines of code.
You write, “it saved them money programming several million lines of code”. Probably the crucial point was that they didn’t have to replace all of those lines before they could get rid of the old hardware. The conversion can proceed piecemeal over many years.
The claim is, that in terms of lines of new code per year, most of it is in COBOL. Indeed, much of that is to support and extend legacy systems. But, the point is, people are still writing it.
The claim is false.
The main reason COBOL still exists is that the cost of even reading it is too high to bear so its easier to just keep the old systems on in many cases.
No one is writing new COBOL.
“One upon a time, I remember people claiming that more of the tremendous increase in speed of computations was due to improved algorithms than faster hardware.”
Complete and utter bilge. The people making that claim were Computer Scientists, and we ought to know by now that anything which calls itself a Science is not. As an Intel engineer famously said, back in the 90’s, “We keep makin’ ’em faster and faster, and the software boys keep pissin’ it away.”
Back when mainframe resources were limited to a few hundred thousand bytes of RAM, CPU speeds were orders of magnitude slower than they are now, and peripheral storage was slow and held amounts of data smaller than that comprising most current PCs’ RAMs, programmers used whole tool kits of clever techniques for, e.g., inverting large matrices, maxima and minima problems, and solutions of ODEs and PDEs. Some – not all – programmers have been made lazy and even stupid by the plethora of resources now available, substituting brute force for cleverness and finesse. IIRC some federal technical agency started a program to save old programming techniques on the theory that they might come in handy some day.
It reminds me of a situation a colleague once found himself in. He was trying to prove a result that, as I recall, involved computing the determinants of n-by-n matrices whose entries were regular expressions of trigonometric functions, e.g., cos^n(m*theta). (That expression is made up to give an example of the concept.) After racking his brain for months he accidentally stumbled upon a general method that had once been a standard part of the English public schools’ sixth form advanced math curriculum!!!
I said that I wasn’t a real expert in that kind of thing. But, once upon a time, I applied a variant of the Sherman-Morrison theorem when updating the LU factorization of a (sparse) matrix, dropping the operations count from O(n^3) to O(n), when N was around 10,000. Key was that the change was of rank 1 while leaving the sparsity pattern unchanged. More than a million times faster.
Then there was the time someone was calculating the moments of a set of data from a CCD , which involved recalculating the positions of something like a million points. I pointed out that you could get the answer just by solving a quadratic equation… Also a bit faster.
Third example: I turned a five-dimensional integral into two steps: one 3-D integral with radial symmetry, followed by a two-D FFT. Changed from impossible to fairly easy.
In developing any serious program, you want to keep in mind an algorithmic analysis of all the key procedures.
Not a real expert: I’m not much on string processing, and I’m no Knuth. I have a good engineering familiarity in areas like linear algebra & Fourier analysis.
Not to put too fine a point on it – you’re utterly wrong.
Ah, the Sherman-Morrison update; them wuz the days.
“Then there was the time … you could get the answer just by solving a quadratic equation”: I’ve had that experience too.
Dear God, all that stuff was tremendous fun. And best of all, I did my programming in languages far superior to FORBLOODYTRAN.
Recognizing a symmetry and reformulating the numerical problem can save orders of magnitude in processing. So can finding a near analytical solution and correcting the errors with numerical perturbation analysis. Finding a true analytical solution is better yet, but is often impossible.
The difficulty is that you have to understand the problem to do those things. You can’t just follow steps on an instruction list or populate an input file. Which is what a lot on engineers are trained to do.
Question: what fraction of programmers understand algorithms at, say, the level of the Cormen/Leiserson/Rivest/Stein text?
I don’t think there is a general answer to that question.
In the ideal case you have an engineer who is an expert in his/her field, understands the math well enough to get the algorithms right, and does the programming.
Next best is a team of two or three people who cover all three bases and actually work together.
All too common is an engineer who has only a general idea of algorithms throwing the problem over a cubicle wall to a programmer who has only a general idea of algorithms.
What helps is when some party to the analysis recognizes they need help from someone who actually knows how to do the math.
I think an understanding of algorithms isn’t nearly as important as the willingness to ask if there is a better way to solve a problem. That’s gotten you farther than anything you learned in school, hasn’t it Greg?
Probably. Although things get reused: I learned big-O notation in number theory classes.
I believe the big-O, little-o notation was first introduced by Landau in his thesis. It mestasized from analytic number theory to the rest of analysis.
About 5-10% of working programmers would be my guess. 100% at a place like Google, approximately 0% in “web development” and related fields – most programmers are self taught and you really can get a lot done just by writing glue code these days – glorified plumbing that connects pre-existing libraries and snippets downloaded from the internet. The book is required reading in most CS programs, and I would expect your EE/physics/ME types would be able to handle it, but my suspicion is that most programmers don’t come from that kind of background.
What fraction of programmers understand algorithms? A minority, at least here in Spain. I have had trouble explaining even simpler things like linear algebra and the chain rule for multiple variables to some people that should know it better.
In Israel every University graduate would understand these , other wise they would not graduate.
But as for hand-on experience through their careers, i would say about 20%.
I once had some guys show me an approach to determining the misalignment of an element in an optical system by reconstructing and comparing the wavefront over two parts of the aperture. I pointed out that they could get the result by applying some simple algebra to the subaperture tilts without reconstructing the wavefronts. I even did the algebra for them. They acknowledged I was right, and even added my approach to their report. But they kept theirs as the baseline because they had enough processing power to do it …
Reconstructing the wavefront from the tilts is only n log n anyhow.
It is, but if they’d really understood the problem they wouldn’t have gone down the path they did. They weren’t numerical optics guys (nor was I!), and several people spent days trying to figure out something that could be done more simply with a couple of hours of algebra.
In effect they were reconstructing the wavefront from subaperture tilts so they could figure out the tilt in different parts of the aperture. They were basically reconstructing the wavefront so they could extract from it they data they started with.
I’ve heard it formulated as “Grove giveth and Gates taketh away”.
Yes and no, for two reasons. For general purpose, basic algorithms, we’re unlikely to get massive improvements. The FFT on many types of data, sorting in general, lots of optimization type problems. Finding something that works well across the board, and has detectable or avoidable worst case conditions has been done for many algorithms. Much of the work now (in CS, admittedly, but also in the field) is finding subclasses with more efficient solutions. If we know that the data looks like this, which algorithm works best? What shortcuts can we take?
The second reason is that as we move into new areas, say machine learning, we don’t understand the problem or the data, and use techniques that work in other fields. As we better understand the problem, we select tools (algorithms, architectures, data representations) that are a better fit.
PS – This is technology, not science. As an engineering prof of mine said, “Every nontrivial question has an answer that begins with ‘It depends…'”.
When I was 13 or 14, the first PC games that rendered a 3d perspective in real time (Wolfenstein 3d and Ultima Underground and so forth) came out. It was clear that they were just mapping 2d pictures onto polygons, so my friend (who had made a couple simple freeware games already) and I spent a month or so trying to map 2d images onto polygons in Pascal. It worked– it looked a little like a still image from Wolfenstein, though clumsier. It just took 10 seconds per image to load, while their game animated at 15 frames per second or so.
That was about it for me and programming. My friend stuck with it, and makes XBox games now, I think.
Pushing stuff from software to hardware has been the major improvement in graphics processing for the last 40 years, starting with the hardware Z-buffer.
It still seems like hardware is where things will actually get faster.
I always hear people saying to work smarter instead of harder, but the people publishing the most papers, at least in my field, have the most massive amounts of cheap slave labor (grad students and post docs).
Sounds like willing cheap slave labor is the definition of “work smarter”
There are still some areas of potentially vast improvement, where we haven’t found provably-best algorithms.
In traditional computing, matrix multiplication is still an unsolved problem. Most LA packages use naive (O(n^3)) or Strassen, (O(n^~2.8)), n in number of matrix entries. The least complex known algorithm is Coppersmith-Winograd at O(n^2.3), but it is almost never or never used in practice because of its enormous prefactor. The payoff only comes for absurdly high n. The highest known lower bound complexity is O(n^2).
Then, active research is ongoing in:
Algorithms for quantum computing.
Algorithms that parallelize well onto many processors.
Algorithms that operate efficiently on pure data structures. (These might not be that important, but they’d sure be handy to have).
Most important of all, there have been explosive advances in machine learning algorithms in the last five years alone.
I remember reading an assessment of the improvements in computational fluid dynamics circa 1985, that made the claim that algorithm improvements had been even larger than hardware improvements over the previous 20/30/something years. The crux seemed to be that simulating fluid dynamics isn’t a simple algorithmic problem, like “invert a matrix” or “do a Fourier transform”, the goal is “produce useful results”, and there are an unlimited number of possible approximations to the original differential equations. The big improvements come from finding new approximation schemes that allow useful results to be calculated with fewer arithmetic operations. (Immediately after which, people start simulating larger and more difficult problems.)
Once the best algorithm for solving a type of problem is near the theoretical limit for computational growth with size for that type of problem, improvements are at the margin. There are three ways forward:
Fast algorithms that give approximate, but close enough answers. (Useful in some applications, especially dealing with dynamic, real-time problems.)
Improved use of parallel processing. The optimal algorithm for serial processing may be less useful than a non-optimal but highly parallel algorithm.
Quantum computing. This is appealing because some classes of problems hugely favor quantum over digital approaches. Here algorithms are ahead of hardware. Stable, many qubit processors would immediately open up significant opportunities, But they are hard to build.
The last time I checked, the number of algorithms for which a quantum computer offered a big speedup was limited: factoring and discrete logarithms (Shor’s algorithm), Pell’s equation, some searches (Grover’s algorithm). Also quantum mechanical systems.. but that is a really small fraction of the actual computing done. Although I’d buy one.
Quite true, but where they make a big difference they make a BIG DIFFERENCE! Which is why several governments are very interested in them.
I doubt the average person will ever need one. They certainly aren’t needed for texting or watching porn on the internet …
Search problems are huge. Quantum computing doesn’t look good because you’re comparing quantum algorithms with optimal results and/or provable running time against classical heuristics whose performance is only known empirically. Once we have real quantum computers, people will experiment with combining heuristics with Grover’s algorithm. Maybe it won’t work, but maybe it will be a huge improvement.
And yet speech recognition on smartphones has gotten vastly more useful over the last 5 years.
Part of the reason is they are just throwing ever greater amounts of experience at the problem.
The underlying algorithm changed within the last five years.
Google was using a Gaussian Mixture model to do its speech processing five years ago*. Sometime around 2013 or 2014 they switched over to a deep neural network model that had only been published by Geoff Hinton in 2009.
This is one of the applications of machine learning that I said is most important and seeing explosive growth. Now it’s DNNs and RNN’s all over the place: http://research.google.com/pubs/SpeechProcessing.html
Almost positive they’re not running Dweeb Learning on smartphones (or phoning home and doing it in “da cloud”). Plain old HMM or even VQ approaches work extremely well if you can solve a few of the noise problems. There are also a lot of heuristics which make things work better.
Google research, of course, is doing a lot of Dweeb Learning.
True, academia has contributed to this as well.
I see a lot more people today that wrote their MA/PHD theses on NLP.
http://spectrum.ieee.org/computing/software/a-faster-fast-fourier-transform
“””A Faster Fast Fourier Transform”””
http://news.mit.edu/2012/faster-fourier-transforms-0118
“””Under some circumstances, the improvement can be dramatic — a tenfold increase in speed. “””
But the old tried and true methods of programming still remain supreme: https://www.gitbook.com/book/tra38/essential-copying-and-pasting-from-stack-overflow/details (Note to those not in on the joke: This book does not really exist.)
I would not be surprised to find myself reading that book in a few years, probably while listening to Toad the Wet Sprocket, or maybe an Isotopes game.
I’ve been writing code since I was in elementary school and professionally for 25 years. I only recently ran into a coworker who was submitting massively overly complicated solutions to simple problems. I would ask him why he chose a particular value, for say network timeout behavior, and he was saying things like “oh, that’s a typical/common value”. I’d say “under what conditions/assumptions?” and he’d hem and haw. I cut my teeth on books likes Stevens, and some of the first google hits I got on some of the details in question, I found the code he was cribbing. It wasn’t common at all. It was some other dudes specific solution.
Steve Hsu shared a similar sentiment a few months ago:
http://infoproc.blogspot.com/2016/02/moores-law-and-ai.html
“Hint to technocratic planners: invest more in physicists, chemists, and materials scientists. The recent explosion in value from technology has been driven by physical science — software gets way too much credit. From the former we got a factor of a million or more in compute power, data storage, and bandwidth. From the latter, we gained (perhaps) an order of magnitude or two in effectiveness: how much better are current OSes and programming languages than Unix and C, both of which are ~50 years old now?”
Although he’s comparing hardware to software, not to algorithms per se.
The FFT is a great thing; even worth going out of your way to use it.
In other words, it’s high time to put the effete cosmologists and string theorists to work in reeducation campuses.
Not all cosmologists and string theorists are effete.
Even the manlier ones just need to work on something more practical.
A wealthier society can afford more pure research.
People doing pure research like string theory are smart and would be useful doing more practical things (?).
Economic growth is strongly linked to progress in practical areas of science.
So, closing down string theory today and redirecting string theorists into building Von Neumann machines should result in us knowing more about high-energy physics in 2100 than if we continue on our present course.
So if you really love high energy theory – quit.
On consideration, I don’t find Hsu’s comment very insightful. Software isn’t primarily built in order to be fast (just not intolerably slow), but to provide more, more, more features as quickly as is feasible. Hardware is built in order to run software, often old software, the result of which is what provides the value of the system as a whole. That’s what makes the computer world go round.
Nevertheless, I’d agree (if perhaps only by accident) that more effort is needed on materials. It’s high time that we get a replacement for CMOS, you know.
You are talking about the kind of software people use to send text messages and view porn on the internet. I believe Greg was more focused on software to work hard technical problems. Two different realms. But they borrow from each other.
Or software that’s even more prosaic for that matter. Then after a while the rest of the world mostly hitchhikes on their boring platforms.
But I’d say this is by now well known so let’s leave it at that. We could also ask, as good engineers, if hardware has improved so much more quickly, so many magnitudes more, why not skip the slowly improving software and implement the whole thing, the Hsu device, whatever it is, in hardware? The trade offs, depending on the problem domain, will reveal themselves on contemplation. (In some cases, the answer is hardware-only.) Frequent pro-software answers: Flexibility, cost, ease of development, easier bug fixes and upgrades and repurposing, long-term portability, etc. Usually not pure performance, though often enough cost-performance.
D-r Cochran, apologies for the OT; would you consider this option for BE: There might be another reason “basal eurasians” were equally distant to each neolithic populations regardless of its geographic location and why they did not have neanderthal admixture but it did not make them closer to africans than to eurasians.
They did not had to be migrants to an isolated place and they did not had to admix with unknown hominids in order to preserve the genetic distance equal to any other human group.
All they had to be is to be the source population of all migrations of HS, which is, the original non admixed HS, living in the ancestral lands of HS. The population that never moved until the mesolite or the beginning of neolithic , when the neanderthals were long gone and everyone else had settled in different part of the globe, incurring some admixture with other hominids on its way .
They did not have to live with another archaic hominin group because they were the archaic hominin group in the respective area – I mean the area where HS originates from. They would have wiped or admixed with competing hominid species in this area hundreds of thousand of years before the HS migrations began.
Again, sincere apologies for the OT.
It may be possible to use a quantum computer to optimize more conventional chip architectures, with a weighted graph theoretical quantum algorithm.
I think it depends on the problem. For some simple problems like computing an FFT there just isn’t a lot of room for improvement. For higher level problems like weather forecasting I expect there is.
If you look at computer programs for playing chess or go there have been a lot of algorithmic improvements over the years.
Is there anything in that idea that memristors could allow the program to be moved to the data, so bypassing the bottleneck of the CPU?
“…Hard to see how you trump the FFT…”
https://en.wikipedia.org/wiki/Wavelet
Are wavelets used in practice? I studied Math/EE with a focus on digital signal processing, but I didn’t start to hear about wavelets until after my grad studies ended, and around the time that my professional programming career was transitioning from physical layer to mid-stack networking development.
Are wavelets interesting in theory? In the way that a Dym/Mckean kind of text exits for them.
BTW, a few days ago I tried to offer up some comments on the question of general algorithm knowledge in the developer community. But, I’ve been around so many different types of developers that it seemed a bit daunting to make a coherent, consistent point out of it. I’d be surprised if more than 1 or 2% of all developers could be trusted with being given a relatively simple, eg sort, algorithm and translating it into bug-free code. The world is increasingly filled with a bunch of useless tinkers (and I mean that in the most disparaging sense of the word, not in a way that Lord British may have intended). The StackOverflow cut/paste joke is entirely accurate.
Wavelets are used extensively in image and speech processing – anything really with locally correlated data. It used to be you had to code your wavelets directly – convolution kernels and such – but now with deep learning they are used more implicitly, i.e. the multilayer network learns wavelets in the early layers. Understanding of wavelets is crucial for understanding what is going on in these early layers.
There is room for improvement even on very low level, very widel applicable. E.g., Gustafson’s “Unum” floating point sounds potentially very important:
http://comments.gmane.org/gmane.comp.clustering.beowulf.general/32896
I don’t think there are any fast libraries for Unum math though (just the Mathematica prototype), and it might require CPU hardware support to be fast at all. So unless Intel or somebody seizes on the idea (and is convinced it will work), it could be quite a while before it ever sees any use.
Perhaps you’ve heard about the advances in sparse FFT?
http://groups.csail.mit.edu/netmit/sFFT/
Further there are a lot of interesting problems in TCS besides just basic algorithmic questions.
In particular, I would guess that work in sublinear streaming algorithms is going to have a good-sized impact in the future.
There continues to be progress in algorithms; numeric linear algebra is a particularly exciting field right now. The programmers are completely unaware of them, so they often don’t get used. No brainer must-use stuff like “the hashing trick” (constructing dummy variables from categoricals on the fly); while it happens to exist in scikit learn in Python, and is the basis for large scale machine learning frameworks like V-W, it hasn’t really migrated to common use. Most programmers don’t know much; they’re just plumbers. Unless an efficient algorithm is implemented in their preferred framework, they’ll never use it.
Worse than that, even when it is implemented (like all those alternative solvers in LAPACK), most people don’t know enough to use them.
I partially agree.
“Most programmers don’t know much; they’re just plumbers”
I often use the word carpenters or mechanics to describe what we do, some of my colleagues don’t like it :).
This is due to the fact that most programmers are hired to maintain and support existing products, but these product in order to survive on the market will need to evolve, and in most of the places i have worked there is usually a sub group of programmers that does this, even if they are not topnotch mathematicians, they usually have a very good grasp on designing efficient algorithms.
One of the places i have worked in, had a dedicated algorithms team (MAs and PHDs in math and electronics), but very quickly we found that most of them make lousy programmers, they did the hardcore math stuff but themselves, and later we had to sit together and make the whole thing more “machine friendly”.