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.
I didn't realize it had been blurbed by a professor emeritus at a seminary (as well as Martin Gardner).
Glad to know that the problem isn't totally me :)
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.
Opened the book, thought "no, it can't be". Agonized for days and weeks if I'm making a fool of myself.
Sent the bug report.
First word in first sentence in first paragraph in first chapter was wrong. Got my cheque. ;-)
But the number of parameters is finite, and all parameters have a finite number of possible values.
His errata changed the wording thus:
Zillions of alphabets can be generated by the programs in this book. (https://ftp.rrze.uni-erlangen.de/ctan/systems/knuth/dist/err...)
I was so excited.
I then checked the errata. It was known.
It took another 20 years before I found an actual mistake, regarding the early history of superimposed codes. A very specialized topic where I have one of the few copies of the patent challenge distinguishing between random superimposed codes and arbitrarily selected superimposed codes.
I have a check.
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.
Whether these things positively exists outside of one mental experiment is an other matter, but so is the notion of individual and self.
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.
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.
That man had a family...
It's good to remind myself that I'm basically a plumber for the internet tubes.
Consider, as an example, Fascicle 5b, Introduction to Backtracking. His citations in the first 25 pages are from 1899, 1918, 2017, 1957, 1967, 1963, 1900, 1947, 1882, 1848, 1849, 1850, and 1960. Had he somehow managed to write this chapter in 01968 instead of 02019 he would only have been missing one of them, though surely the illustrations and experimental results of his own he reports would not have been as excellent, and surely the overall framing of the section benefits from the additional 61 years of hindsight.
In fact, although enormous progress has been made in backtracking in recent years, it hasn't affected the introductory aspects of the question. But clearly you can learn an enormous amount about backtracking without straying into the literature of the current millennium.
Of course other resources exist, many of which cite TAOCP or are derived from it
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.
(Adapted from Feynman, who apologized for errors in his Lectures, but refused to accept blame for anyone who cited them in a dispute. The truth speaks for itself.)
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.
Also, while no fast algorithms are known (and may never be depending on if p=np) some are faster than others depending on the properties of your inputs, and choosing the right one can mean saving a lot of time and effort.
That's the only time I've ever used them though.
This way my computing is based on a strong foundation...
Your laptop stand will likely become a family heirloom in the decades to come.
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.
(But ignore everything Skiena says about generating random numbers.)
https://www.edwardtufte.com/bboard/q-and-a-fetch-msg?msg_id=...
Ctrl-f "Sedgewick".
Most of the time, perspiring with worry that a 1960s article might have scooped me.
Disclaimer: I'm nowhere close to finishing any of the books.
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 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.
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.
I would love to have a career working on problems like this but can't imagine how I'd get a job doing anything but commonplace back-end work.
My path involved working at a series of tiny startups through the first 15 years of my career - the 1990s and early 2000s. At the smallest, I was the only engineer. At the largest, there were 8. At that scale, you learn to do everything (seriously: front end, back end, databases, assembling servers, networking the office, setting literal rat traps, cleaning the cat litter after "upgrading" the rat traps, ...). You also get an opportunity to get to know people very well and build a lot of mutual trust with some of them.
In 2005, the head of engineering from the "big" startup was helping to start a new subsidiary of an established tech company and needed someone to develop indexing and search for the device mentioned above. He asked me to join.
In 2010, the head of marketing at one of those startups was now an executive at a soon-to-IPO company who needed to scale their ad delivery system. She asked me to join.
Both of those relationships had turned into friendships long before they asked me to join their newer endeavors. They knew what I was good at and what motivated me. That resulting in me being deeply trusted the day I joined and being given a lot of freedom to create solutions. So, I guess one way to get this kind of work is experience, relationship building, and some luck.
Thank you for sharing it.
It was actually probably more insightful and useful than I think you may have realized.
In terms of actual programming use, not much, but I still haven't read the other volumes yet.
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 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 enjoyed the dancing links stuff from a recent fascicle. I used it to build a sudoku solver in C. So it's moderately useful.
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.
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.
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.
Algorithm training is useful on most jobs for preventing you from going accidentally quadratic.
That being said, if you already know ASM/C then maybe it wouldn't be as useful.