Slashdot Mirror
Top Ten Algorithms of the Century
brian writes "'Great algorithms are the poetry of
computation,' says Francis Sullivan of the Institute for Defense Analyses'
Center for Computing Sciences in Bowie, Maryland. He and Jack Dongarra of the
University of Tennessee and Oak Ridge National Laboratory have put together a
sampling that might have made Robert Frost beam with pride--had the poet been a
computer jock. Their list of 10 algorithms having 'the greatest influence
on the development and practice of science and engineering in the 20th
century' appears in the January/February issue of Computing in Science
& Engineering. If you use a computer, some of these algorithms are no doubt
crunching your data as you read this."
the significance of the fortran compiler is not necessarily because of any particular optimizing techniques that the compiler used. Rather the invention of the optimizing fortran compiler is significant because it was the first time that a compiler was written that could be as efficient or more efficient than a reasonably experience programmer doing his own hand rolled assembly. The compiler was written specifically with the goal of being efficient at numerical operations while still using normal mathematical notation (ie. w = x + y + z; as opposed to add w, x, y; add w, w, z; ) this allowed programmers to be much more efficient without sacrificing execution speed. this was a vastly innovative concept as the time, as the reigning concept at the time was that no good programmer would use a compiled language, it being too much slower than writing the program in straight assembler.
it was also instrumental in the vast popularity of the (IBM?) computer it was originally developed for and sold with.
disclaimer: this is all stuff that i remember from my programming languages class last year. it may not be completely correct, as i don't really know anything about fortran other than what i learned in that class...
If I don't put anything here, will anyone recognize me anymore?
This one was widely used back in the 80's:
10 PRINT "RADIO SHACK SUCKS!!!!!"
20 GOTO 10
Here's my commentary on the some of the algorithms selected. I've included brief descriptions/references to further information where useful.
...
The Metropolis Algorithm for Monte Carlo: Based on the thermodynamic equivalent of crystals forming in cooling solids. As opposed to the naive optimization algorithm, the Metropolis algorithm sometimes allows a step to be taken even when it decreases the objective evaluation function with a probablity equal to the value of an exponentially decaying "entropy" function. _Numerical Recipes_ has a nice description, although their example is quite abysmal. The GNU Scientific Library (sourceware.cygnus.com/gsl) has an implementation of the algorithm, referred to as simulated annealing.
The Fortran Optimizing Compiler: compiler techniques in general have improved enormously since the 1950s...this selection doesn't really make much sense to me, as this field has been more about continous and gradual improvement, whether than the developement of some breakthrough optimization techniques. If anything, the pioneering work of Zhang and Roberts establishing the computation infeasibilty of an "universal optimizer" is a much more interesting result.
QR Algorithm for Computing Eigenvalues: Elegant method for determining the values for which A*x_i=\lambda\_i*x_i for a square matrix A. the eigenvalues and corresponding eigenvectors (the vectors belonging the the nullspace of (A-\lambda\_i*I)) are in a certain sense the natural frequencies of a matrix. Determining the eigenvalues without solving the characteristic polynomial (as with the QR method) is critical for avoiding numerical analysis problems.
Some notable algorithms which seem to be missing:
-Sieving techniques for the decomposition of large composites into prime factors
-RSA/other asymmetric key exchange algorithms
-Huffman codes, LZ sliding-window compression techniques, arithmetic encoding
-MDS matrices, error correction codes, cyclic redundancy checks
-The linear feedback shift register
-Predictor/corrector methods, adaptive numerical intergration and approximation of ODEs and PDEs
-Lenstra-Lenstra-Lovasz lattice basis reduction algorithm
-Berlekamp's Q-matrix algorithm for the factorization of polynomials
But, not that interesting. Its just a list, no details. I suppose they figure we already know this stuff is, I sure don't (other then the FFT, quicksort, and optimizing compiler). I would have liked to have seen a more indepth description of what each algorithem did and what its impact had actualy been...
ReadThe ReflectionEngine, a cyberpunk style n
Dictionary of Algorithms, Data Structures, and Problems is a pretty good "dictionary" of algorithms. Another good place, if you know the name of the algorithm, is of course Google...
BUBBLE SORT!!!!!!
:)
Seriously, it's first sort most of us learn, and it has the cutest name.
One of the profs who teaches an algorithms course at my university always shows his class a program that displays performance graphs as various sorts chew through large data sets. Invariably, most of the students cheer for bubble sort, even though we know it will loose. Favouring the under-dog, I guess
Dana
You forgot the most widely used algorithm on the planet....
10 IN
20 OUT
30 GOTO 10
======
"Rex unto my cleeb, and thou shalt have everlasting blort." - Zorp 3:16
Sacred cows make the best burgers.
The following algorithm, though peculiarly simple, was single-handedly responsible for DOUBLING sales of shampoo:
1. Lather
2. Rinse
3. Repeat
I seem to recall that Nolan Bushnell did a similar thing in the instructions for Pong. Does anyone recall what those were?
Rather use this link - it has the missing explanations.
And this link explains integer relations.
Why are you surprised that the list is "heavily biased towards scientific and numerical applications"? The list comprises the algorithms that they believe have had 'the greatest influence on the development and practice of science and engineering in the 20th century.' I would _expect_ this list to be almost exclusively biased towards "scientific and numerical applications."
I'm not surprised that the Fortran compiler is included. Like it or not, Fortran is the grand-daddy of high-level languages for science and numerical apps.
"It's too bad stupidity isn't painful." - A. S. LaVey
This algorithm decreases the amount of time used to multiply to matricies from O(N^3) to around O(N^2.72) (or less) by breaking the matrix up into little pieces that are multiplied by each other (or broken into smaller pieces with the same process) then added together to get the result.
The primary speedup in this algorithm is that additions are much faster for a computer to complete than multiplications, and a single multiplication can be replaced with several additions.
The other benefit of this algorithm is that it divides the work into subproblems that can be dispatched to alternate processors and then recombined centrally.
Unfortunately, due to the large overhead costs of this method it only works well on very large data sets, such as 1000x1000 or larger arrays. Once you get below this size it is best to use the standard matrix multiplication.
Here is a section of code from a matrix multiplication algorithm using this method I wrote for an algorithm analysis class: if (this.length == 2) /* 2x2 matrix */
{
int x1, x2, x3, x4, x5, x6, x7;
int x1a, x1b, x6a, x6b, x7a, x7b, x2a, x3b, x4b, x5a;
x1a = a11.add(a22).getElement(0,0);
x1b = b11.add(b22).getElement(0,0);
x1 = x1a * x1b;
x2a = a21.add(a22).getElement(0,0);
x2 = x2a * b11.getElement(0,0);
x3b = b12.sub(b22).getElement(0,0);
x3 = a11.getElement(0,0) * x3b;
x4b = b21.sub(b11).getElement(0,0);
x4 = a22.getElement(0,0) * x4b;
x5a = a11.add(a12).getElement(0,0);
x5 = x5a * b22.getElement(0,0);
x6a = a21.sub(a11).getElement(0,0);
x6b = b11.add(b12).getElement(0,0);
x6 = x6a * x6b;
x7a = a12.sub(a22).getElement(0,0);
x7b = b21.add(b22).getElement(0,0);
x7 = x7a * x7b;
c11 = new Matrix(1);
c12 = new Matrix(1);
c21 = new Matrix(1);
c22 = new Matrix(1);
c11.setElement(0, 0, x1 + x4 - x5 + x7);
c12.setElement(0, 0, x3 + x5);
c21.setElement(0, 0, x2 + x4);
c22.setElement(0, 0, x1 + x3 - x2 + x6);
}
--
Eric is chisled like a Greek Godess
marotti.com
I think they left out two important categories of algorithms. They should have had at least on data compression algorithm (LZW, wavlet, or something like that) and an encryption algorithm (DES or RSA).
And the Fortran optimization one is... well, that's not really an "algorithm", now is it? It's a whole bunch of algorithms, and presumably each Fortran compiler does different things to optimize. Again, the numerical/scientific bias is obvious though... who else would use Fortran today?
Some algorithms (and data structures) I'd nominate are (note that I'm purposely avoiding numerical algorithms here, because the article aleady lists more than enough good ones):
I don't see random sort anywhere in the list?
Oh, for those who don't know: It's the winning entry in a competition held at IBM. The competition was about the slowest search algorithm.
--The knowledge that you are an idiot, is what distinguishes you from one.
--The knowledge that you are an idiot, is what distinguishes you from one.
Why is this important? Convolution, the primary operation involved in computing all kinds of neat filters, can be performed in O(n^2) time in time space, but O(n) time in frequency space. (i.e. it's a lot faster to perform image filtering in Fourier space). The problem is that the normal Fourier transform takes O(n^2) time, so you can't get into and out of Fourier space to justify performing filtering there.
With the FFT, filtering can be performed in O(n*lg n) time, since you can hop into Fourier space quickly, perform the filter, and hop back (the constants work out to this being useful after n ~= 100,000, which is a reasonable point for audio and most images).
The FFT is a great example of an algorithm that suddenly tipped the asymptotic scales and revolutionized an entire discipline.
-m