Knuth's Art of Computer Programming, V 4B, has gone into print

Well, the editor wars are over folks.

More seriously, Don Knuth is a treasure. One of the coolest things about computing science is how all the greats in the field are either alive, or within the living memory of people who are.

> as fast as any 20 year old. I I certainly hope so. Though I think it's more likely that Knuth can be as fast as other 20-year olds, but not as the 20-year old of himself.

He had recently been working on 3:16 and showed us some of the original calligraphy that he had at home at the time.

What a lovely man, as well as being a multi-talented genius.

> So I sat down with him and proofread the pages as they came out of the typewriter. It seemed that he was composing and typing as fast as I could read. By morning the manual was done. Years later when don's first book came but, he told me that if I would proofread it for him that he would pay me a dollar for every error that I found, including typographical errors. I took the offer as a great personal compliment at the time, but I think that he probably made that a standing-offer to anyone.

also from earlier in that essay:

> don claimed that he could write the compiler and a language manual all by himself during his three and a half month summer vacation. He said that he would do it for $5000. Our Fortran compiler required a card reader, card punch. line printer and automatic floating point. Don said that he would not need the card reader or card punch, but he wanted a magnetic tape unit and paper tape. I asked Gerard Guyod how Brad could have been suckered into paying this college kid $5000 to write something that had to be a piece of junk if he was only going to spend three and a half months on it. Gerard whispered his response to me. He said "We think that he already has it written. He probably did it in his spare time while working in the computer center at Case Institute." I still wasn't entirely satisfied with that answer because I was a college graduate whose first job was for 5325 per month and I had just changed jobs and was making $525 per month. Besides that it was taking mortal human beings 25 man-years to write compilers: not three and a half man-months. I thought that Brad had taker leave of his senses.

From your wiki link:

  Initially, Knuth sent real, negotiable checks to recipients. He stopped doing
  so in October 2008 because of problems with check fraud. As a replacement, he
  started his own "Bank of San Serriffe", in the fictional nation of
  San Serriffe, which keeps an account for everyone who found an error since
  2006.[2] Knuth now sends out "hexadecimal certificates" instead of negotiable
  checks.

I suggest skipping around on an "as needed" basis.

Try Volume 1, Section 2.2 "Linear Lists", as a starting point. I promise you its an easier read than you expect. Despite being relatively easy material, you will probably learn something about arrays with just maybe ~3 or ~4 pages worth of reading material.

Start at the start of Section 2.2. Maybe work your way backwards to Section 2.1 as you realize its not as hard as you think (so you start at the "proper" starting point). And then go on from there.

Its really basic stuff. But hitting "rock bottom" on the subject of arrays, stacks, queues, and such is fascinating.

Which is to say I don't think many people have actually worked their way all through them. Neither have I, there's no shame in that.

And, as you point out, it's not too late to give it a try.

For example, the first volume consists of 2 "chapters". Each chapter spans about 250 pages on its own. So actually not a chapter, but a section, or maybe even a book in its own right. Then, each chapter is broken into sections and subsections that flow one into the next. There's a fundamental lack of whitespace and breathing room in a book that is supposedly "beautifully formatted".

At the very beginning of the book, there is a flowchart for how you're expected to read the book. It's not linear. It's not even close to linear, even within a specific topic. So why not just format the book in the suggested reading order?

I don't agree that Knuth is a great communicator. He's verbose when he could be succinct. He's taciturn when he should expound. He's prone to flowery language with humorous barbs in his introductions (and they can be quite funny, if you are clued in enough to what he's talking about already), but then spews dense mathematical notation when he gets into details.

So yeah, there's a lot of interesting information in the book, but it's a struggle to read it. Some people will say it's supposed to be a struggle, it's meant to make you work. Why? Programming is already hard on its own. Why make the act of reading about programming hard, too? I think, for the amount of effort being put into them, they could have been written more clearly. It makes the books feel like they are designed to mark an in-crowd of mathematicians who learned programming rather than to teach people computer science.

Disclaimer: I'm nowhere close to finishing any of the books.

Regarding more classical algorithms, I never bothered reading the other fascicles. I think there are much more practical references but none is as complete and detailed as Knuth's treatment. He goes to the bottom of any algorithm, not just proving it has the right complexity but also asking what inputs are the most difficult, what other problems it can solve, etc. In the end you understand the field much better and have a good idea of what the boundary of knowledge (ie research) looks like.

But, and I say that as an ICPC world finalist, if you just want to solve practical problems you probably won't need TAOCP.

I enjoyed the dancing links stuff from a recent fascicle. I used it to build a sudoku solver in C. So it's moderately useful.

That's the only time I've ever used them though.

The point of a job, unless you're lucky enough to get a job where you can change the world, is to pay your living expenses so that you have the leisure to do things like read TAOCP and write Sudoku solvers. If that's not your idea of an enjoyable vacation, don't read it; you'll regret it.

Most of the time, perspiring with worry that a 1960s article might have scooped me.

The book showed me the method of how to do it efficiently in a manner that could be adapted to the 16 bit architecture I was working with. It also showed me how to detect and handle overflow situations, as well as when they would happen. It kept me from creating a buggy, error-prone pile of crap code that I'm certain I would have created at the time.

At the same time, it took me a couple of days of study to understand the two or three pages I was interested in. The material was the most condensed material I have consumed in computer science. Like you say, you have to learn a new machine architecture and assembly language to understand the examples. Things you learn from those books come at a high cost in terms of time and effort.

It reminds me of studying the bible, where cross checking, reading different translations, studying hebrew and greek, and the culture of the day are all necessary if you want to get the best understanding you can. The TAOCP books are scholarly articles and almost a kind of shorthand notation of computer science concepts.

For example, in Volume 4A there's a simple technique for comparing two pointers in bit-reversed form. This technique was patented by Hewlett-Packard as a method of randomizing search trees (treaps):

https://bugfix-66.com/fdb8bb4fa84cf810aa25ff40c88a13c1874410...

From Volume 3, here is by far the fastest method of sorting integers (Singleton's method), an algorithm I have used professionally several times (e.g., for beam search in a speech decoder):

https://bugfix-66.com/834f0677c85b23c0bf1047d3654ab7c27ff054...

Knuth's books are just packed with gems like that.

The meticulous high quality of the books is also remarkable. However, if you look very carefully you can find rare mistakes. I received payment from Knuth and have an account at his bank:

https://www-cs-faculty.stanford.edu/~knuth/boss.html

Getting your name on the above list was once a Hacker rite of passage.

I suspect that most of these algorithms have been implemented and available as libraries for people to use. The challenge of programming has moved from designing such isolated algorithms to modeling the problems, modularizing the code, creating an evolutionary path for a system, and balancing the wants of tomorrow with the needs of today.

Still, if you are working at the core problems of organizing, searching, sorting, managing data, you might might the books useful.

I implemented it to a tee, only to see it fail (I think in the part that merges abandoned blocks). I banged my head against this problem for days before finally daring to entertain the notion that the algorithm might be flawed. This was TAOCP after all!

Turned out my university library had an old edition and I had run into one of the scarce bugs in it (which had been duly fixed in the next edition).

So yes, I have used TAOCP on the job and, to prove it, a scar of which I am rather proud.

I read some of Vol 2, Seminumerical Algorithms, to hone my instincts on how random numbers work in practice. I have referred to it on occasion when people say things like, "if we seed the random number generator, take the random number, then feed that into the seed, the result would be more random."

I read most of Vol 3, Sorting and Searching, when applying for jobs. It was more interesting than leetcode grinding. I don't know if it was more useful, but it was better for my sanity.

I thought a little about it and saw that it would degenerate into sat solving.

I checked taocp and indeed my colleague's idea was in there. Also a faster algorithm was presented in the relevant section. I lended the book to him and we saved around a month of work.

If you have constraints, i.e. not enough compute, not enough memory, not enough storage, then you'll need a solution and, odds are, somebody has had the same problem before and it's been written up already in Knuth's TAOCP. Of course, the problem won't be exactly in the form it's been written up, but you have to have enough experience and knowledge to know the abstract form of your problem in order to figure out what parts of TAOCP would be useful to you.

Want a concrete example? Well, I'm in the generation that go to assume that storage was basically constant access regardless of whether you wanted to access the 1st byte, or the Nth one. New, high-performance memory like NAND flash, is weird because it's fundamentally unreliable. In order to make NAND reliable you have to do stuff, and some of the stuff you can do, makes NAND look like tape, and accessing tape is best done sequentially. Guess what TAOCP has? All these great ideas about maximizing random access to sequential media.

In terms of actual programming use, not much, but I still haven't read the other volumes yet.

TAoCP is aiming at damn near "perfection" of programming. Donald Knuth is analyzing the exact assembly language of all of his decision-making with these algorithms. The assembly language is represented as a random variable, and an _exact_ count of those assembly language statements (in loops and other complex jumps) is analyzed.

Everything from the highest-level algorithm design / mathematical concepts is discussed... down to the lowest-level assembly level details / implementation of the code. And everything in between.

-----------

As such, when Knuth / TAoCP covers a subject, it feels comprehensive, in a way that no other writer has ever accomplished.

So how does this work out in practice? Well, there's plenty of tutorials on hash tables out there. But only Knuth's writing on Hash tables / linear probing has ever hit the entire subject for me.

Other books will go over linear probing vs quadratic probing vs double-hashing. Meanwhile, Knuth carefully derives the formulas of each, and how it changes at the assembly level implementation.

-----

Is that useful for workplace environment? Probably not. In work, you only need to know "Linear Probing Hash Tables work like this, do it", and maybe not the analysis of it.

But if you're doing more fundamental programming, such as "GPU Implementation of Hash Table", something that very few other people have done... the Knuth-level analysis is the only thing that hits "rock bottom" and gives me all the insight "behind" the data-structure and its design.

I'd say Knuth's stuff is for people who invent new fundamental data-structures or other implementation details like that. Its not for typical workplace programming.

--------

For anyone who wants to know Knuth's writing style, I think his writing on Alpha-beta pruning (from the 1970s) is an excellent introduction to Knuth's writing style.

"An Analysis of Alpha-Beta Pruning" by Knuth / Moore, 1975.

Alpha-beta pruning always was kinda mystical to me. But Knuth recognizes the intermediate steps needed to understand the subject fully. The brilliance of discussing F1 (branch-and-bound) before discussing F2 (alpha-beta pruning) cannot be understated.

Knuth recognized that branch-and-bound is what most people thought of by Alpha-beta pruning. But then comes up with specific examples where F2 (true alpha-beta pruning) makes a difference over F1. And then uses math to demonstrate how often these cases come up.

Does it help in implementing AB pruning? I dunno. But it helps a lot if you wanna change AB pruning / change the fundamental search and understand why things are done that way. You only need to study "F2" if you're copy/paste programming. But the study and analysis into "F1" (branch and bound) holds deeper understandings to the entire concept of search trees.

Even if you never, ever, ever will program F1.

At any rate, don't judge the book on the first part - the first part is important to get the rest of the book, and it's as well written as the rest, but it doesn't reflect how much fun (again, fun for those who are into programming in itself) the rest of the book is.

I have so far found 1-2 references that I could otherwise not decode, plus wanted to know about n-way sorting.

And that's how I would recommend to use it. I have it on my shelf to pull it out if I have to. Which is rare but it does happen. And as such it proved value to me, on the job, as I know how to get into these things as needed. But it has a similar insane price to usefulness ratio as an encyclopedia.

What I've done so far? Everything from Sysadmin to DevOps to Engineer (data heavy) to SRE to Data Engineer.

If you want to learn DSA then you should probably start with something that goes less deep, is less complete but covers useful algorithms from many areas.

I read the section on Hash Tables while at work because one of our hash table implementations was exactly what he proposed in his book and there was no explanation on why some things were done, especially the choice of the hashing functions. I first tried looking for the information in other books (like Cormen et al.) but everybody just simply references the book from Knuth without explaining things either. So I bought it just for that...

I really really wanted to have time to read the rest of it. But also my comic book collection and a whole lot of other books I bought in the last 30 years. Maybe one day.

Algorithm training is useful on most jobs for preventing you from going accidentally quadratic.

I did read all three - it took me about three years to get through all three and (at least try to) work each exercise. Useful on the job? No, not really, but I can't think of a non-fiction book(s) I've enjoyed reading much more than these. All of the code examples are in assembler, and not just any assembler, his own imaginary assembler (but you can download a compiler and an emulator for it). I'd be hard-pressed to come up with anything that he covers here that's not already part of the standard library of any programming language you could possibly consider using - but it's still great reading, and illuminating in indirect ways.

I worked as an OS Architect at IBM and then Chief Scientist at a very successful startup. Subjects like analysis of algorithms, memory management, optimizing disk access, search tries, random number generation, and many more found in TAOCP have all been useful in my professional life. I've had to give many technical presentations and to present my designs to committees of experts and CS professors. Knuth wasn't the only source of my preparation for this kind of work, but he was a very important source.

Are there better books on algorithms? Maybe. I also like the popular Introduction to Algorithms [1], Sedgwick's Algorithms [2], and Skeina's Algorithm Design Manual [3]. All of these are good and all of them sit on the shelf right next to Knuth's books. Depending on the subject, any one of these might have the best treatment. BTW, Sedgwick was a Ph.D. student of Knuth.

To keep up with the literature I also recommend a membership in the ACM with access to their digital library.

[1] Thomas H. Cormen , Charles E. Leiserson, et al. (2022), Introduction to algorithms, MIT Press.

[2] Robert Sedgewick and Kevin Wayne, (2011), Algorithms, Addison-Wesley.

[3] Steven S. Skiena, (1997), The algorithm design manual, Springer.

One job involved indexing arbitrarily large books (gigabyte+ was not uncommon) on an embedded CPU with less than 1MB of RAM available to the indexer (this is 15+ years ago, before smart phones). It also involved searching hundreds of those books in a few seconds with ~8MB of RAM available. Indexing was taking place on a single core CPU while the user was using the device, so the indexer had to be able to stop its work within a few milliseconds of any user action and resume later without losing progress. On the surface, Knuth's concepts felt old fashioned (abstract assembly language and talk of multiple tape drives for intermediate storage). But that mapped very well onto this indexing problem. Books and indexes resided on an SD card and individual files on the SD card could act very much like Knuth's individual tape drives. Doing append only operations on those files (as you would want to do on a tape drive) proved fast and reliable. My 1MB of RAM would have been an embarrassment of riches when the original volumes of TAOCP were released. I don't remember if any of the algorithms that shipped as part of that device were straight out of TAOCP, but the thinking involved was heavily influenced by those books. Whenever I was stuck, it was back to Knuth.

My next job was focused on distributed systems. We were rebuilding an ads system because the older one couldn't handle the scale needed. That involved lots of MapReduce and lots of stream processing (before there were good open source stream processing packages to build on top of, this started in 2010). Those same tape drive oriented algorithms came right to the surface again. When processing TB or PB of data, you want single pass algorithms wherever you can come up with them - merely linear isn't good enough. Same as tape drives - there's a huge benefit if you can avoid having to rewind. And so many stream processing primitives (windowed joins, groupings, etc.) are exactly what people were doing with tape drives 50 years ago. Now we were using many GBs of RAM spread across many machines, but relative to the amount of data being processed, it was still miniscule.

This all required spotting the similarities between the world Knuth drew his examples from and the constraints I was working under. But once I did, his concepts were quite useful. And the framework for thinking about things was more valuable to me than any specific algorithm or data structure. It was much more useful to me as a narrative to read rather than a reference to pull something out of.

https://youtu.be/9IM_dqjBkIw

His books were the reason he started TeX.

Donald is 84. And each time I’m reminded of that I get sad, it’s very unlikely we’ll get another 30 years of his work.

It looks like he started working on it in 1962.

Just imagine being that intelligent and pouring 60 years of your life into something like this.

Once I recognized him, I told him that I preordered a set of the latest edition of The Art of Computer Programming. He made a joke about collecting royalties from all the books he sold.

I'm glad I had the opportunity to speak to Donald Knuth! I actually saw him earlier this year at a Stanford symposium, but I didn't get to speak to him.

Since it's divided into sections, you can poke it before bed now and then. You don't even have to buy it: https://aquinas.cc

but hey maybe impressive no damage from being lugged around between check outs :)

Honestly after working through those books, you could probably complete self-studying an undergraduate mathematics curriculum.

[0] https://artofproblemsolving.com/store

That apart, I (and Knuth) recommend just skipping the math parts when they get hard. You can always come back to them later if you're interested.

This is what he says in the preface to Vol 1 (p. viii):

> A few words are in order about the mathematical content of this set of books. The material has been organized so that persons with no more than a knowledge of high-school algebra may read it, skimming briefly over the more mathematical portions; yet a reader who is mathematically inclined will learn about many interesting mathematical techniques related to discrete mathematics. This dual level of presentation has been achieved […] also by arranging most sections so that the main mathematical results are stated before their proofs. […]

> A reader who is interested primarily in programming rather than in the associated mathematics may stop reading most sections as soon as the mathematics becomes recognizably difficult. On the other hand, a mathematically oriented reader will find a wealth of interesting material collected here. Much of the published mathematics about computer programming has been faulty, and one of the purposes of this book is to instruct readers in proper mathematical approaches to this subject. Since I profess to be a mathematician, it is my duty to maintain mathematical integrity as well as I can.