Slashdot Mirror
The Art of Don E. Knuth
Snuffy writes "Salon has a nice feature on our hero. It's a full length feature, talking about his long-term project writing of The Art of Computer Progamming "
← Back to Stories (view on slashdot.org)
← Back to Stories (view on slashdot.org)
They just migrate to Windows.
But seriously, folks... I was reading O'Reilly's new tome on Perl Algorithms and I was struck by a point mentioned in this article; no-one cares about efficiency any more. Just let your PIII do the work.
We've all heard (and probably given) rants on how VB et al will be the death of the program, but it's good to have Knuth around to remind us that programming can still be an art form.
Sometimes I think things are just too easy these days :) I got exicted yesterday morning when I used mod for the first time in YEARS. I think that means I'm desperate for some real work!
License: By reading this you are agreeing that you agree with me.
I notice that Knuth appears to be deeply religious (for example his book 3:16 illuminated or his music based on Revelation). I find that interesting: around Slashdot, the assumption most often expressed is that anyone religious must be an irrational fool. Yet, when you look at people like Knuth, or Larry Wall, they are obviously not foolish in at least some technical areas.
You have to wonder what the difference is... Why so many geeks are non-religious, but it seems that some at the very top are deeply religious (Knuth's only real competition is Linus in my book).
Maybe the assumption that religious = irrational is at fault?
While the "The Art of Computer Programming" is anything but easy reading, it's time well spent, even if you don't read the entire book. I bought the first 2 volumes a few years ago and the only way I could read through them, was to:
... in most cases the response is a blank stare that sometimes makes me feel as if I were speaking Klingon. I'm very glad, that during my college years (10+ years ago), they shoved all sorts of algorithms down my throat ... it seems that these days a lot of people graduating with IS (and to a lesser degree CS) degrees, wouldn't recognize an elegant algorithm if it came up and bit them in the ass ...
1) Read a few pages
2) Think about it
3) Re-read the pages from step 1
4) Let it sink in for a week or so
5) Re-read the pages from step 1 again.
Usually, once I had reached step 5, I felt that I actually understood what Knuth was talking about. If anybody ever tells you that languages like C and C++ are the past and Visual Whatever is the future, ask them a few questions about differnet sorting and searching algorithms
--> Robert
And you can help!
DEK has released updated docs and supporting software. The initial conversion of the programs is done by volunteers.
While the bits from Vol. 1 have been passed out to volunteers already, the MIX stuff from Vol. 2 is getting assigned for conversion these days.
There's a link on the salon page to an article closely related to this, IMO a quite decent piece (and actually a quite good summary of the reasons why I personally stick to vi, makefiles and all that good stuff).
Check it out at http://www.salon1 999.com/21st/feature/1998/05/cov_12feature2.html.
If you know n is small, (e.g. the number of lines in /etc/hosts), it won't matter what you do. If n is big, (e.g. a 100 meg log file), your choice of algorithm matters. If you're counting nanoseconds in a tight loop, then you're presumably already using a fast algorithm, but the exact variant is important. For example, heapsort is guaranteed O(n log n), but quicksort is often preferred because, although O(n^2) worst case, it's O(n log n) on the average, and the constant is lower than for heapsort. A lot of Knuth is about deriving these constants. Knuth goes even farther than this, e.g. showing how to derive the constants for different ways of choosing the pivot in a quicksort.
It's exhausting, non-productive and insane to apply this sort of analysis to everything. But once you've focused on the performance-critical parts of your program, Knuth's detailed analysis is essential.
As somebody who teaches algorithms and complexity, I should say that a good fraction of students seem disinterested in an good algorithms course. They are more interested in the syntax of C++ or Java than in developing their algorithmic skills. They somehow do not realize that any professional programmer should be able to pick a programming language in three to four days. (At least a good working knowledge.) What therefore distinguishes two programmers is how algorithmic one is.
/. This will probably enthuse more youngsters into taking algorithmics more seriously.
I have also met many programmers in the industry who do not know what a Turing machine is and are surprised to hear that there such things as an unsolvable problem! After all, cannot a computer solve everything!? And of course, NP-completeness is some near mystical theory with no relevance.
This is the second article on Knuth in a week on
Being extremely brilliant in science or math does not mean that a person cannot be not irrational or religious. OTOH, being completely rational doesn't make one a brilliant mind either. Many accomplished genuises were extremely good in their field, and yet irrational in other respects.
t obio.html
* Godel came up with one the most elegant and logical proofs in math, yet in his later years was paranoid about being infected by microorganisms in his food and ended up starving to death. A notably illogical way to die.
* Ramanujan, who was self taught and considered one of the most brilliant mathematicians of the century, was devoutly religious and was eccentric enough that he carried a doctor's certificate stating he was sane.
* Emannuel Swedenborg was a deeply religious and profound scholar with an allegedly stupendous IQ.
* John Forbes Nash, who won the Nobel for a thesis he wrote at 21, became schizophrenic later. There's an unforgettable exchange in his biography, "A Beautiful Mind", by Sylvia Nasar (an excellent book).
Mackey: "How could you, a mathematician... believe that extraterrestrials are sending you messages?"
Nash: "Because, the ideas I had about supernatural beings came to me the same way that my mathematical ideas did. So I took them seriously."
Of course, this does not mean that Knuth or any genius is bound to be eccentric or worse. The point is - the history of math and science is replete with people of enormous logic, who were quite irrational and non-scientific outside their core field of accomplishment.
In any case, religion has more to do with faith and finding personal meaning, not with exhibiting scientifically rigorous proof (which would be quite irrational indeed, not to mention a career-limiting-move. )
L.
PS - found this thoughtful remark from Nash describing his delusions
http://www.nobel.se/laureates/economy-1994-2-au
Thus further time passed. Then gradually I began to intellectually reject some of the delusionally influenced lines of thinking which had been characteristic of my orientation.This began, most recognizably, with the rejection of politically-oriented thinking as essentially a hopeless waste of intellectual effort.
So at the present time I seem to be thinking rationally again in the style that is characteristic of scientists. However this is not entirely a matter of joy as if someone returned from physical disability to good physical health. One aspect of this is that rationality of thought imposes a limit on a person's concept of his relation to the cosmos. For
example, a non-Zoroastrian could think of Zarathustra as simply a madman who led millions of naive followers to adopt a cult of ritual fire worship. But without his "madness" Zarathustra would necessarily have been only another of the millions or billions of human individuals who have lived and then been forgotten.
Statistically, it would seem improbable that any mathematician or scientist, at the age of 66, would be able through continued research efforts, to add much to his or her previous achievements. However I am still making the effort and it is conceivable that with the gap period of about 25 years of partially deluded thinking providing a sort of vacation my situation may be atypical. Thus I have hopes of being able to achieve something of value through my current studies or with any new ideas that come in the future.
Of course he focuses on the text. if you start focusing on what you believe to be the meaning of the scripture, it becomes, in fact, completely meaningless, since you can interpret it any way you want. To get any sort of useful analysis you have to look at what's actually written, not what your political agenda, religion, or hopes want you to believe is meant.
10 PRINT CHR$(205.5+RND(1)); : GOTO 10
Have you ever felt genuine faith before? If not, you have no place to say it is irrational. Feelings afterall, are very rational.
Feelings are indeed quite irrational. Feelings are abstract emotions, not reasoned responses. The term "rational" refers to reasoning, not emotional responses. Faith is an emotional response, and hence not any more rational than nostalgia, lust, or annoyance are.
And so the prospect of faith, a belief in something with no physical evidence, can only be thought as irrational to those who have never felt it before. Or to those whose faith has let them down and have become disillusioned with their beliefs.
The concept makes perfect sense - it's the belief in something without evidence that it is correct. This belief is usually based on either a hope or desire for something to be true, some sort of "gut feeling" (some prefer to think of this "gut feeling" as a message from God) that it is true, or both. Either way, it's not rational - i.e. a reasoned response.
This I would not call faith at all. Faith is more akin to a desire, or hope for something to be true. It often influences one's actions, and sometimes the consequences positively affirm the faith.
Exactly. it's a hope for something to be true, rather than any sort of evidence that the thing is indeed true. One can hope for whatever one wants, but this doesn't increase the chances of it actually happening.
10 PRINT CHR$(205.5+RND(1)); : GOTO 10
Actual working programmers have relatively rare opportunities to apply such knowledge. Most of the hard but tidy problems are Somebody Else's problems, and neatly tucked away behind some interface which has to be learned and used.
;) ). It's just that most programmers I've met and worked with seldom have any need to do anything themselves that is more complicated than looping through a list.
The problems most real programmers face are trivial, but extremely numerous. They glue this bit to that, make an interface that the customer can live with, add this little feature, find that 3-year-old typo that ruins the app, etc. The problems are mostly in understanding what has to be done and learning the interfaces to the parts it affects.
As for unsolvable problems, my experience is that these are academic hair-splitting. Like that old saw: "It is impossible to create a program which detects infinite loops." This is only mathematically true, not practically relevant. One could trivially write a program which expresses the conditions under which each loop will be infinite, and non-trivially sort these into always true, sometimes true, maybe true, and never true. Furthermore, it could deduce more abstract conditions for the "sometimes" and "maybe" cases and sometimes reduce them to "always" or "never". Ultimately, it could warn the programmer that the program will never terminate no matter what the inputs (a clear and obvious bug), or in many cases it could give conditions which the input must meet for the program to terminate (and, of course, point out those areas of the program which it can't understand as potential trouble spots, and hand this information over to the debugger). It would not be theoretically perfect, but it could be extremely useful, and it might even be possible to write every useful program in such a way that the loop-checker could verify it.
There's a big difference between a problem being mathematically impossible to correctly answer in all conceivable situations with a yes or no, and a problem being impossible to answer correctly in most practical cases and to tell a human to deal with the rest.
In other words, special cases are the stuff of the real world, with the need for general solutions few and generally encapsulated into libraries.
Most working programmers work with small data sets, and when they don't, they are usually accessing a database. They don't care about "for sufficient values of N" because for sufficient values of N their programs give up and print an error message (or just crash).
Don't get me wrong, I have the available volumes of TAoCP in the latest editions and have read them (not that I remember a great deal of detailed information from them, I still look through them and other books when I want a hashing function or a pseudo-random number generator). Being a games programmer, I am very concerned with efficiency so I have a great many opportunities to apply my knowledge of algorithms and data structures; often to intractable problems (fortunately, for games you can often get away with just making it look like you've solved the problem
Most programmers can't pick up a the skills and habits of writing effectively and efficiently in a new language in a few days either. More importantly, they can't pick up a new library in a few days. What distinguishes two programmers in terms of usefulness is rarely "how algorithmic one is," but one's ability to learn new interfaces quickly, to write thousands of lines of clean, readable code and to spot common errors quickly. Even more important is that intangible ability to just make it work, to dive into that horrible tangle of a million lines of poorly written code and come back up with a new feature or a fixed bug without bringing the system down. That is the real complexity working programmers deal with. Skill with algorithms is trivial next to this ability to cope.
In other words, software engineers don't need to be computer scientists (though it can help).
Your responses seem to indicate that your thinking is oddly similar to mine, despite the fact that we come to nearly opposite conclusions.
One thing that I'm not clear on is that, if you recognize that faith is something that one believes without solid evidence, how does one decide what to believe in? Why become Muslim, or Christian, or Hindu, or Jewish, or Wiccan? More importantly, why become any of these? What's wrong with making up your own hope/belief and having faith in that?
10 PRINT CHR$(205.5+RND(1)); : GOTO 10