Donald Knuth turns 80, seeks problem-solvers for The Art of Computer Programming | Hacker News Reader

Donald Knuth turns 80, seeks problem-solvers for The Art of Computer Programming

developers.slashdot.org

204 pointsMilnerRoute41 comments

I am sure this is controversial, but how many people have actually read these books? It's unfortunate because they are held in high regard, but the impact seems reduced for what it could be. I definitely could be wrong. I would love to at least peruse through them, but they seems to be hard to find as a full set at a decent price.

> they seems to be hard to find as a full set at a decent price

All of Knuth's work on TAOCP since Volume 3 (basically everything that he's written for 4A and 4B, starting over a decade ago) is essentially available for free online, in the form of preliminary drafts that Knuth put up online. You can find them nicely collected here: http://www.cs.utsa.edu/~wagner/knuth/ Of course the pleasure of holding a beautiful hardcover book in your hand is missing, but all the content is mostly there.

To answer your earlier question, not many people have read all the books in their entirety, though there are a few. This is simply because the books go very deep on their topics, and most people would prefer to just dip in.

I read a few pages of one of the recent fascicles a while ago, doing all the exercises etc. It was a lot of fun, and also took about a month to read about a dozen pages. But the experience was rewarding (also got a check from Knuth!), and the writing in TAOCP was easier to understand than it would have been to read the original papers that he had digested. (Comment about this a few months ago: https://news.ycombinator.com/item?id=15035767)

I don't "read" "them", but I dive into sections haphazardly and read them for pleasure; they're invariably rewarding. Like a textbook, you can (and probably should) build a syllabus out of parts of the books, rather than plowing through them in a straight line.

You almost certainly already know this, but this is a good place to mention it for those who might not: when reading these books for pleasure or personal interest, as opposed to just trying to get an answer to "I need to do X...what should I do?", don't overlook earlier editions.

These books are not like too many textbooks today, where new editions are largely minor tweaks and maybe some changed exercises in order to make it harder for students to get by with used copies from prior years.

With Knuth, a new edition means there have been many very significant changes. Whole new algorithms are added, and older ones are dropped.

For example, the section on arbitrary precision integer multiplication in Volume II underwent major changes from 1st to 2nd edition, and even bigger changes from 2nd to 3rd edition.

If you just need to implement arbitrary precision multiplication, 3rd edition is for you. But if arbitrary precision multiplication is something that is interesting enough to you that you are actually studying it for fun, you'll probably want all three editions of Volume II.

Additionally, the difficulty points on some problems changed as new proofs were discovered. In particular, Fermat's last theorem went from M50 (math required, Research problem) to HM45 (Higher math required, more than a team project but less than a Research problem).

Additionally, somewhere along the way, the marvelous tape sorting fold out pages have dissappeared from the Sorting and Searching volume.

It's been 40 years or so since I read TAOCP in any depth. But you seem pretty familiar with it, so I'll ask you the following, maybe you remember:

I think it was somewhere in Volumes 1, 2 or 3 (but maybe an entirely different book not even by Knuth) where one of the exercises says something like:

19. M50 ...solve this quite complex problem .... For the instructor who assigns all odd numbered exercises.

A little bit of humor in an otherwise quite dry set of books.

I am familiar with some sections of it.

I don't remember that particular one, but there are odd bits of humor throughout his work. "MIX is the world's first polyunsaturated computer."

Browsing through it again, I see a reference in section 1.2.8 about Fibonacci numbers, problem 37 references a paper by R. E. Gaskell and M. J. Whinihan. I worked with Mike Whinihan in a previous lifetime. He got his PhD in economics at U of Chicago in just three years, to the dismay of his classmates. He wrote that paper "Fibonacci Nim" when he was in High School. And looking at the beginning of Chapter 2 "Information Structures" he mentions structures in "algebraic language like FORTRAN, C, or Java" (third edition). In the first edition, neither C nor Java had yet been invented.

Or, follow his "Procedure for Reading This Set of Books" on page xv (page xii in the Third Edition)

In the book Coders at Work, Peter Seibel asked a number of famous programmers, including Knuth, if they had read all of TAoCP. Only one said that he had. Knuth, likely with tongue in cheek, said that he had not. But of course, he wrote it, so apparently he is not counting that.

I have read some sections in great detail, e.g., the section on multi-precision arithmetic. This was essential for writing floating point libraries.

The multiple-precision arithmetic section of mine is easily found by looking at the colour on the edge of those pages. There is no better treatment of this subject out there.

As far as I know, the section on random number generation is the only treatment of that subject anywhere, better or worse.

I don't think that this is quite true.

On page 189 of Volume 2 (Third edition) there are two paragraphs discussing previous literature, including bibliographies. I do recall prior to the publication of Vol 2 that there were numerous ACM articles discussing this topic.

But Knuth's exposition is certainly comprehensive compared to anything else.

(But I don't see anything about CSPRNG)

Just my own opinion reading all of these books would be less useful than picking particular interesting sections and both reading and doing the exercises.

The exercises are, if anything, underrated.

I did actually read all three of the first ones, and attempted (at least) almost all of the exercises. It took me about three years. I enjoyed it, but I will say that the _practical_ benefit of reading through all of these books is questionable; it's more like climbing mount everest and looking down from the top, saying, "wow, I really did it". I did come across a set of all three cheap at a used book store - I don't think I could ever have justified paying full price for the set. The only part I sort of skimmed over was section 5.4 in volume 3 that covers the algorithms for using banks of external tape drives to sort more data than you can fit in memory (taking into account the time taken for the tapes to get up to full speed and whether or not the tape drives support backwards reading). Fascinating stuff, but I couldn't motivate myself to expend as much effort into trying to work the exercises as I did with the rest of the series. Still, reading through TAOCP is quite an experience - if anything, it's a good reality check if you were ever thinking you were about as smart as a person could be.

It's not controversial just a naive juxtaposition of computer science and what most of us do which is yeoman programming. Do people work through Calculus textbooks? Are textbooks a reasonable price? These are low volume prints; it takes a lot of people to publish and run a press printing of a book.

I keep meaning to buy a set, but they are so dang expensive.

Though, I'll admit I have purchased several 'classic' CS books over the years that have been sitting on my bookshelf, unread, for an embarrasingly long period of time.

You can buy pdf copies on informit.com. If you wait for major holidays (black friday is best), most of the books will be 50-60% off.

I plan to buy the whole set and try reading them only when they are finished.

I have the full set, but sadly I’ve just never bothered to do more than skim a few pages.

At one point I thought, maybe if I read just one page a day I can digest I’ll eventually finish it all some day, but sadly it will take more commitment than that.

Also, I’m not really sure what the benefit will be in the end or what difference it will make to my life.

>Also, I’m not really sure what the benefit will be in the end or what difference it will make to my life.

The same can be said for any book.

If you read them, they will benefit your life immensely imho.

Yes, but the advantage other books have is more people have read them and given their reviews on how it has helped them.

So few people have read TAOCP that there's not really much information out there about how it benefits them, if at all. The problem with books that go very deep into niche topics is you might never find something that relates to that topic in your actual life in some meaningful way.

> I fear that the most probable hypothesis is that nobody has been sufficiently motivated to check these things out carefully as yet.

For some motivation, you might still get a check from Knuth if you find an error. https://en.wikipedia.org/wiki/Knuth_reward_check

It is not a real check. It is for putting on your wall.

Well, that's because our banking system is terrible and because showing off a knuth check is worth more than cashing it, people shared pictures of said checks which allowed check fraud.

Don't people cash cheques by taking photos of them? Or is that a Canadian thing? (Ie. Can't you do both?)

Yes

You can do both. Many banks now let you take pictures of the check using your cellphone to cash them out.

Few people would cash it, anyway.

That's why he switched away from real cheques.

Uhhh no, he switched away from real cheques because of bank fraud: https://www-cs-faculty.stanford.edu/~knuth/news08.html (this page seems to have certificate issues)

https://www-cs.stanford.edu/~knuth/news08.html seems to have the desired content, minus certificate error.

I am getting a cert error on this page one would hav ehoped that Stanford would not have problems with certs ;-)

I am pretty sure they get unlimited free certificates from Incommon :D

For people that complain that TAOCP is too expensive: All volumes can be freely read on Safari books, which is free if you are an ACM member.

50 usd for a hard cover text book isn't exactly expensive

https://www.amazon.com/Art-Computer-Programming-Vol-Fundamen...

Agreed.

Is volume 4, fasicle 6 available for download, or do we need to buy the book itself?

I'm very interested in SAT solvers, as this has deep connections to statistical mechanics and condensed matter physics.

It is independently available as a paperback, but also the "pre-fascicle" (draft version) is available for download: http://www-cs-faculty.stanford.edu/~knuth/fasc6a.ps.gz or click on 6A at http://www.cs.utsa.edu/~wagner/knuth/ specifically: http://www.cs.utsa.edu/~wagner/knuth/fasc6a2015.09.23.pdf

His programs (SAT solvers) are also available on his site at https://cs.stanford.edu/~knuth/programs.html (They are in CWEB and you'll have to use cweave and ctangle to read and run those programs respectively; if you just want to read I've typeset them here: https://github.com/shreevatsa/knuth-literate-programs/tree/1...)

Knuth has also given a couple of talks about satisfiability around the time he wrote the book:

- https://www.pathlms.com/siam/courses/3028/sections/4140/vide... (July 2016, at SIAM Annual Meeting)

- https://www.youtube.com/watch?v=g4lhrVPDUG0 (December 2016, at Brown University)

Look at https://cs.stanford.edu/~knuth/news16.html#lectures for slides and handouts from these talks.

I attended one of his talks (but not the ones you mention), during which he described how he was approaching the topic. He said he was reading the most important papers on sat problems in chronological order, and implementing each of the algorithms he found along the way. At the time of the talk, he was half-way through the ‘80s, IIRC.

A lesson in commitment and perseverance for me. And a very funny talk as well (Knuth likes jokes!)

knuth only touches on the condensed matter (survey, beliefprop) in like one section in the whole book, i recall. beautiful presentation, nothing about, say, the d1RSB and s1RSB transition or anything like that. try montanari's book

Yes I have montanari's book.

Reply on news.ycombinator.com