A little bit of history about the book series may help understand what is in it.
In 1956, Knuth graduated high school and entered college, where he encountered a computer for the first time (the IBM 650, to which the series of books is dedicated). He took to programming like a fish to water, and by the time he finished college in 1960, he was a legendary programmer, single-handedly writing several compilers on par with or better than professionals (and making good money too). In 1962 when he was a graduate student (and also, on the side, a consultant to Burroughs Corporation), the publisher Addison Wesley approached him with a proposal to write a book about writing compilers (given his reputation), as these techniques were not well-known. He thought about it and decided that the scope ought to be broader: programming techniques were themselves not well-known, so he would write about everything: “the art of computer programming”.
This was a time when programming a computer meant writing in that computer's machine code (or in an assembly language for that machine) — and some of those computers were little more than simple calculators with branches and load/store instructions. The techniques he would have to explain were things like functions/subroutines (a reusable block of assembly code, with some calling conventions), data structures like lists and tries, how to do arithmetic (multiplying integers and floating-point numbers and polynomials), etc. He wrote up a 12-chapter outline (culminating in "compiler techniques" in the final chapter), and wrote a draft against it. When it was realized the draft was too long, the plan became to publish it in 7 volumes.
He had started the work with the idea that he would just be a “journalist” documenting the tricks and techniques of other programmers without any special angle of his own, but unavoidably he came up with his own angle (the analysis of algorithms) — he suggested to the publishers to rename the book to “the analysis of algorithms”, but they said it wouldn't sell so ACP (now abbreviated TAOCP) it remained.
He polished up and published the first three volumes in 1968, 1969, and 1973, and his work was so exhaustive and thorough that he basically created the (sub)field. For example, he won a Turing Award in 1974 (for writing a textbook, in his free time, separate from his research job!). He has been continually polishing these books (e.g. Vols 1 and 2 are in their third edition that came out in 1997, and already nearly the 50th different printing of each), offering rewards for errors and suggestions, and Volume 4A came out in 2011 and Volume 4B in 2023 (late 2022 actually).
Now: what is in these books? You can look at the chapter outlines here: https://en.wikipedia.org/w/index.php?title=The_Art_of_Comput... — the topics are low-level (he is interested in practical algorithms that one could conceivably want to write in machine code and actually run, to get answers) but covered in amazing detail. For example, you may think that there's nothing more to say about the idea of “sequential search” than “look through an array till you find the element”, but he has 10 pages of careful study of it, followed by 6 pages of exercises and solutions in small print. Then follow even more pages devoted to binary search. And so on.
(The new volumes on combinatorial algorithms are also like that: I thought I'd written lots of backtracking programs for programming contests and whatnot, and “knew” backtracking, but Knuth exhausted everything I knew in under a page, and followed it with dozens and dozens of pages.)
If you are a certain sort of person, you will enjoy this a lot. Every page is full of lots of clever and deep ideas: Knuth has basically taken the entire published literature in computer science on each topic he covers, digested it thoroughly, passed it through his personal interestingness filter, added some of his own ideas, and published it in carefully written pages of charming, playful, prose. It does require some mathematical maturity (say at the level of decent college student, or strong high school student) to read the mathematical sections, or you can skim through them and just get the ideas.
But you won't learn about, say, writing a React frontend, or a CRUD app, or how to work with Git, or API design for software-engineering in large teams, or any number of things relevant to computer programmers today.
Some ways you could answer for yourself whether it's worth the time and effort:
• Would you read it even if it wasn't called “The Art of Computer Programming”, but was called “The Analysis of Algorithms” or “Don Knuth's big book of super-deep study of some ideas in computer programming”?
• Take a look at some of the recent “pre-fascicles” online, and see if you enjoy them. (E.g. https://cs.stanford.edu/~knuth/fasc5b.ps.gz is the one about backtracking, and an early draft of part of Volume 4B. https://cs.stanford.edu/~knuth/fasc1a.ps.gz is “Bitwise tricks and techniques” — think “Hacker's Delight” — published as part of Volume 4A. Etc.)
I find reading these books (even if dipping into only a few pages here and there) a more rewarding use of time than social media or HN, for instance, and wish I could make more time for them. But everyone's tastes will differ.
The story there is that he had written this in high school, combining the style of MAD magazine with the textbook “system of weights and measures”, as one of his submissions to the Westinghouse Science Talent Search (1956). A few months later when he was in college he sent it to MAD magazine with (basically) “you guys may like this”, and to his surprise they treated it as a submission and decided to publish it (with illustrations by Wallace Wood); it came out in June 1957. Later when writing his CV Knuth decided to start counting from this as his first publication.
I would add that one thing which is very relevant today but not covered much is memory hierarchies and parallel/distributed programming. For that you might want to accompany TAOCP with one of the heavyweight teaching books on Parallel Algorithms.
I was trying to find the book I had at university, which was excellent. However I can't find it right now. I would suggest looking at book recommendations from reputable university courses on parallel architectures.
Of course but i am curious to know somebody's personal preference (i have my own collection and preference) particularly when they juxtapose it with TAOCP. It would be nice if you could find the book which seems to have made a significant impression on you and add it here so it is useful to others.
Sure. IMO it is important to have an overall picture of the fields of Concurrent/Parallel/Distributed architecture/programming before delving into the details of a language/library implementation. To that end i have found the following books useful;
1) Foundations of Multithreaded, Parallel, and Distributed Programming by Gregory R. Andrews - This is one of my favourites even though old. You get to learn/compare the different paradigms in one single book.
2) Parallel Programming: Concepts and Practice by Bertil Schmidt et al. - This is a more recent book with good explanations/coverage including CUDA.
3) The Art of Multiprocessor Programming by Maurice Herlihy et al. - Well known classic though with a main focus on shared-memory architectures.
Along with the above you also need more detailed language/library specific implementation books;
a) C++ Concurrency in Action by Anthony Williams.
b) Programming with POSIX Threads by David Butenhof.
c) UNIX Systems Programming: Communication, Concurrency and Threads by Kay Robbins and Steve Robbins.
Finally; for studying concurrency at the OS level where software meets hardware, i have found nothing better than;
i) Unix Systems for Modern Architectures: Symmetric Multiprocessing and Caching for Kernel Programmers by Curt Schimmel.
I've wanted to buy these since the late 90s when I used to enjoy thinking about algorithms in the abstract, but never bought them because at the start of my career I felt quite poor and it didn't seem like a good use of my money.
In 2015, I decided I was no longer poor and should buy the box-set as a treat. I set aside time to read a chapter in the first week after it arrived, but realised that it would take years to read and actually understand the material in that one book, let alone the other two. I decided I'd just dig in from time to time, but found that I never actually did, because in all honestly I'm less interested in abstract algorithms now, and prefer to spend free time doing other things in life that don't involve computers.
So, my copy is still essentially untouched after almost a decade.
Don't feel too bad -- I strongly believe that 99.99% of the copies of TAOCP are never read beyond the first chapter.
I'd love to own them and be the kind of person to read them, but I know I would also struggle to give them the proper attention (not with the hundred other books to read on my shelf).
Weirdly, probably not. I know if I sold it, then I'd suddenly get the urge to read it.
Also, it's really heavy (I'd say at least over 1kg), so by the time I sold it at less than the current price because it's no longer new (also mine is 1-4A, the current edition is 1-4B) and paid postage to package and ship it somewhere, it's probably not really worth the effort.
Older editions might actually fetch good prices. That's because newer editions aren't just new material plus minor edits and corrections. They also drop old material.
For example if you are interested in large integer arithmetic the 2nd edition of Volume 2 has some exercises that develop some methods that, if I recall correctly, I found more suited to my needs than the methods in the text when I was working on a large integer library.
The 3rd edition dropped those. I've long forgotten most of what I learned when working on my large integer library, but if I had to learn that subject again I'd probably actually start with the 2nd edition, and then check the 3rd edition to add to that.
You should imagine that you are forced to sell it every day. Eventually you'll either sell it (or donate it (your local library might appreciate it)) or start reading it.
OP imagines that there is a point in the future where they read the book without commiting to it. Selling/donating it would put an end to that possibility and force OP to imagine a future where they cannot read it, and hopefully helps them assessing one va the other, and prioritizing accordingly.
This is a really nice comment, but I find the comparison at the end so strange. You shouldn't compare reading these books to using social media, a better comparison would be: given a limited amount of time, should you read these books, or some other one?
> This is a really nice comment, but I find the comparison at the end so strange. You shouldn't compare reading these books to using social media, a better comparison would be: given a limited amount of time, should you read these books, or some other one?
I don't get what you find strange about comparing reading TAOCP vs reading social media. Your time is limited, and each activity that you choose bears an opportunity cost. Of course it is an interesting question to ask whether you should read another book instead, but I bet that most people waste a lot more time on social media than reading a book that is not TAOCP, so svat's comparison does make a lot of sense in my opinion.
I read social media when I'm too tired to really engage with anything in a serious way.
I (try to) read TAOCP sometimes when I have a surplus of energy and ambition.
Admittedly, sometimes ambition comes along a little bit after I force myself to do something challenging, but TAOCP is so difficult for me that I really have to be feeling it to make any headway.
Reading professional material means you want to improve yourself/your craft/your knowledge, while reading social media is shown to have mostly negative effects, so obviously nobody is going to advocate the latter.
Yeah good point, the reason for the strange comparison is that I started to write “I wish I could make more time for [TAOCP]” and was immediately forced to confront my time spent on social media/HN, so I did. :)
There is also a contrast between the two: they lie on opposite ends of a spectrum from shallow to deep, of things that make you really think / put in honest effort, and also give a deeper enjoyment.
As for reading other (good) books: like anything else, it's ultimately a question of what gives you most joy, I guess. Learning (say) real analysis from Rudin would also be deep and make you work, but Knuth has more jokes.
Principia was an attempt to derive math from logical ground up, motivated by ideas about the foundations of mathematics and logic (wrong ones, it turned out). Knuth is more like A Magical Mystery Tour of Algorithms, wherein Knuth is both tour guide and man behind the curtain.
"Wrong" is too strong. The fundamental bases it used are not generally used today, but it was the first of its kind and inspired much. Many of its details are still fine.
If you are interested in the underlying goal of Principia Mathematica, I urge you to check out the Metamath Proof Explorer (MPE):
https://us.metamath.org/mpeuni/mmset.html
By itself, Metamath doesn't have built-in axioms. MPE uses Metamath to first state a small set of widely-accepted axioms, namely classical logic and ZFC set theory, and then proves a tremendous amount of things, building up to a lot of mathematics from careful formal proofs that rigorously prove every step.
Some things cannot be proven, but that doesn't mean that proof is dead.
Yes, it was a tad tendentious, but I don’t think anyone really buys the logicist program anymore.
Don’t get me wrong, PM is marvelous and there’s no gainsaying its enormous historical impact.
If your characterization of Metamath is correct, I don’t think that’s in the spirit of PM at all. One of the major problems PM had was the rejection of (what later became) the Axiom of Choice in favor of Russell’s convoluted theory of types. Indeed, that set theory (ZFC) is needed to get the rest of the way R&W were trying to go is one of the signal failures of the logicist program behind PM.
If you believe the big advantage of Principia Mathematica was that it starts with a very few axioms and then manages to formally and exactly prove many things, then MPE is a worthy successor. I'm in that camp.
However, if you think the main point of Principia Mathematica was the very specific set of axioms that they chose, then that's different. The PM authors chose to use a "ramified" theory of types, which is complex. It does have sets, it's just not ZFC sets. Few like its complexities. Later on Quine found a simplification of their approach and explained it in "New Foundations for Mathematical Logic". There's a Metamath database for that "New Foundations" axiom set as well (it's not as popular, but it certainly exists):
https://us.metamath.org/index.html
Strictly speaking that's true for any system that can handle arithmetic (as proved by Goedel). You can show an inconsistency, but you can't prove consistency. No one's found an inconsistency.
Yes, I was too loose with me words again. I was gesturing at relative consistency (especially, at least, when compared to the lack of serious doubt about ZF/C’s consistency), as well as the work of folks like RB Jensen and Randall Holmes.
The biggest problem NF has is, as usual, a social one: there just ain’t a lot of people working on, or interested in working on, NF compared to other set theories.
Also check out the Principia Rewrite project, which aims to use the interactive theorem prover Coq to ensure each proof step is a valid step according to Principia’s axioms and that no steps are skipped, even by accident.
It's a bit extreme imo to call Principia wrong. It isn't wrong so much as it will never completely succeed. These are two different things. The logical perspective presented in Principia is still sound and a relatively useful framework for understanding most of mathematics, and it's a monumental and impressive piece of work. I find it hard to believe anyone who has read it wouldn't leave with a better overall comprehension of what exactly it is that we are doing when we do mathematics.
I didn’t say PM was wrong. I said the ideas behind it were—-although I should’ve said idea (singular) insofar as I was thinking in particular of the strong form of logicism motivating Russell.
My understanding of the flaws of PM is in its attempts to avoid self-reference, which was sort of folly from the beginning as proven by Godel. I learned this from I Am A Strange Loop, and I'm not sure how accurate it is historically. But Godel's Incompleteness Theorem is one of the most interesting things I've ever read about.
The principal flaw of PM if you were to read it now is that it is an evolutionary dead end.
The elementary vernacular foundations of modern mathematics is (more or less) naive set theory; the starting tools of serious foundational work (as arcane as it is even within maths as a whole) are logic and more rigorous set theory, perhaps with some computability mixed in; the main tool of a mathematician who wants to reason in great generality is category theory (with some handwaving in the direction of the previous point about universe hierarchies and whatnot). There are some signs of convergence between these (and of mainstream mathematicians starting to once again take foundations seriously), but at the basic level those are what you’ll be dealing with.
None of them existed in their current form at the time PM was written, even logic (no Kripke semantics! no forcing! and no Gödel of course). Some did not yet exist at all. Some changed quite drastically in direct response to PM. And of course PM is the origin of (embryonic) type theory, which is the inspiration of the unified approach I referenced above. So as a historically important text, sure, if that’s what you want, but as a gateway to understanding more interesting maths it’d be terribly inefficient.
In that respect TAoCP was uniquely lucky. It was also a self-obsoleting book: it ceased to be comprehensive months after it was published, exactly because it told you everything there was to know about algorithms to date. Yet none of the stuff that’s in it is itself obsolete, there’s just immesurably more stuff now. PM, on the other hand, was attempt at “rationalization” in the 19th-century sense, and mostly a failed one except for serving as fertilizer for all of the later ones.
It wasn't a folly from the beginning because it seemed like it could be done when Russel and Whitehead started on the PM. It was only after it was published that Gödel proved it to have been a folly.
In some ways, it's the opposite: Knuth is super practical and any theory is only in the service of whatever is actually relevant to writing better programs and getting answers. See e.g. this older comment of mine comparing CLRS and TAOCP: https://news.ycombinator.com/item?id=21924265 — where others may say O(lg n), Knuth will say that a trie search inspects an average of lg N + 1.33 bits for a successful search and lg N − 0.11 for an unsuccessful one.
But then again, as a result of all this work from him, pulling together and categorizing and cataloguing and analyzing all the disparate ad-hoc “tricks” that programmers had come up with, Knuth basically put (this area of) computer science on good foundations and made it a respectable academic discipline. So in that sense he successfully executed a Principia-like project.
To put it another way, the computer programming/algorithms world is generally divided into hackers who derive satisfaction from elegant ways of bending computers to their will, and theorists who are happy to talk asymptotics, treat their problems abstractly as a branch of mathematics, and often never write a single program. What sets Knuth apart is that he straddles both words: is firmly a hacker at heart, but is able to bring prodigious theoretical skill to bear on the area.
It continues to surprise me that Principia Mathematica (PM) still gets mentioned so regularly in discussions related to computer science topics. As far as I can tell, PM was one of the least influential works in any branch of mathematics or logic or philosophy or computer science. It is must be one of the least-read books (3 volumes, 1994 pages) ever written. PM's sole claim to fame is that it was mentioned in Kurt Goedel's famous paper "Ueber formal unentscheidbare Saetze der Principia Mathematica und verwandter Systeme I". The emphasis strongly is on "verwandter Systeme" - related systems, of which PM is just one example.
I really hope at some point he stops writing and speed sketches the rest of the "book" so that it can be completed after his inevitable passing at the level of his vision.
---
PS- not to be "that guy" but I do think that a future edition should port the MMIX to RISC-V because it'll be actually runnable and I'd bet money that RISC-V is the educational standard going forward for the next 50 years.
In 1956, Knuth graduated high school and entered college, where he encountered a computer for the first time (the IBM 650, to which the series of books is dedicated). He took to programming like a fish to water, and by the time he finished college in 1960, he was a legendary programmer, single-handedly writing several compilers on par with or better than professionals (and making good money too). In 1962 when he was a graduate student (and also, on the side, a consultant to Burroughs Corporation), the publisher Addison Wesley approached him with a proposal to write a book about writing compilers (given his reputation), as these techniques were not well-known. He thought about it and decided that the scope ought to be broader: programming techniques were themselves not well-known, so he would write about everything: “the art of computer programming”.
This was a time when programming a computer meant writing in that computer's machine code (or in an assembly language for that machine) — and some of those computers were little more than simple calculators with branches and load/store instructions. The techniques he would have to explain were things like functions/subroutines (a reusable block of assembly code, with some calling conventions), data structures like lists and tries, how to do arithmetic (multiplying integers and floating-point numbers and polynomials), etc. He wrote up a 12-chapter outline (culminating in "compiler techniques" in the final chapter), and wrote a draft against it. When it was realized the draft was too long, the plan became to publish it in 7 volumes.
He had started the work with the idea that he would just be a “journalist” documenting the tricks and techniques of other programmers without any special angle of his own, but unavoidably he came up with his own angle (the analysis of algorithms) — he suggested to the publishers to rename the book to “the analysis of algorithms”, but they said it wouldn't sell so ACP (now abbreviated TAOCP) it remained.
He polished up and published the first three volumes in 1968, 1969, and 1973, and his work was so exhaustive and thorough that he basically created the (sub)field. For example, he won a Turing Award in 1974 (for writing a textbook, in his free time, separate from his research job!). He has been continually polishing these books (e.g. Vols 1 and 2 are in their third edition that came out in 1997, and already nearly the 50th different printing of each), offering rewards for errors and suggestions, and Volume 4A came out in 2011 and Volume 4B in 2023 (late 2022 actually).
Now: what is in these books? You can look at the chapter outlines here: https://en.wikipedia.org/w/index.php?title=The_Art_of_Comput... — the topics are low-level (he is interested in practical algorithms that one could conceivably want to write in machine code and actually run, to get answers) but covered in amazing detail. For example, you may think that there's nothing more to say about the idea of “sequential search” than “look through an array till you find the element”, but he has 10 pages of careful study of it, followed by 6 pages of exercises and solutions in small print. Then follow even more pages devoted to binary search. And so on.
(The new volumes on combinatorial algorithms are also like that: I thought I'd written lots of backtracking programs for programming contests and whatnot, and “knew” backtracking, but Knuth exhausted everything I knew in under a page, and followed it with dozens and dozens of pages.)
If you are a certain sort of person, you will enjoy this a lot. Every page is full of lots of clever and deep ideas: Knuth has basically taken the entire published literature in computer science on each topic he covers, digested it thoroughly, passed it through his personal interestingness filter, added some of his own ideas, and published it in carefully written pages of charming, playful, prose. It does require some mathematical maturity (say at the level of decent college student, or strong high school student) to read the mathematical sections, or you can skim through them and just get the ideas.
But you won't learn about, say, writing a React frontend, or a CRUD app, or how to work with Git, or API design for software-engineering in large teams, or any number of things relevant to computer programmers today.
Some ways you could answer for yourself whether it's worth the time and effort:
• Would you read it even if it wasn't called “The Art of Computer Programming”, but was called “The Analysis of Algorithms” or “Don Knuth's big book of super-deep study of some ideas in computer programming”?
• Take a look at some of the recent “pre-fascicles” online, and see if you enjoy them. (E.g. https://cs.stanford.edu/~knuth/fasc5b.ps.gz is the one about backtracking, and an early draft of part of Volume 4B. https://cs.stanford.edu/~knuth/fasc1a.ps.gz is “Bitwise tricks and techniques” — think “Hacker's Delight” — published as part of Volume 4A. Etc.)
• See what other people got out of the books, e.g. these posts: https://commandlinefanatic.com/cgi-bin/showarticle.cgi?artic... https://commandlinefanatic.com/cgi-bin/showarticle.cgi?artic... https://commandlinefanatic.com/cgi-bin/showarticle.cgi?artic... are by someone who read the first three volumes in 3 years. For a while I attended a reading group (some recordings at https://www.youtube.com/channel/UCHOHy9Rjl3MlEfZ2HI0AD3g but I doubt they'll be useful to anyone who didn't attend), and we read about 0.5–2 pages an hour on average IIRC. And so on.
I find reading these books (even if dipping into only a few pages here and there) a more rewarding use of time than social media or HN, for instance, and wish I could make more time for them. But everyone's tastes will differ.