A few years ago I had the pleasure of meeting Knuth in his home, my wife was doing some photography for him. He took me to his room and showed me his setup, he was researching Soduku algorithms at the time. His hands were blisteringly quick, moving between EMacs panes, triggering evaluations and printing of results, as fast as any 20 year old. In his 80s , he hasn’t seemed to suffer any mental decline.
I started talking to him about some of the latest AI research and he mentioned the papers authors, he had already read them! Not only is he still very productive at 84, but he has not ossified into one particular subject but he continues to keep abreast of other related fields.
He also played his huge pipe organ for us, he was gracious, humble, down to earth, truly a treasure. I only wish he could live another hundred years, selfishly so I could see Volumes 5, 6, and 7 of Art of Computer Programming finished.
I should not with some sadness that COVID hit not long after and that year we lost a number of other luminaries in the field like Jon Conway.
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.
Like the 5th picture down you can see him standing (he uses a standing desk!) and if you blow up the screen, you can see part of an emacs window on the left hand side. I believe he also was using emacs shell windows as well, but not 100% sure.
I can't emphasize enough how incredibly nice and welcoming he is. He is bursting with enthusiasm for computers, and my wife and his wife had to almost restrain him so he would sit for his pictures, because he would start talking to me again about computer related stuff.
Hard to tell at this resolution, but it looks like he's using a fairly bare X setup with a tiling window manager and only one Emacs frame on the left. The colours and layout on Emacs look like org-mode. Does he write with org-mode? I would have expected him to write bare TeX, of course. Maybe he's doing something else with org-mode.
He's got Xeyes on the right, and the shell windows could conceivably be Emacs too, but if so, he's customised them to remove the minibuffer.
“The best way to communicate from one human being to another is through story,” Knuth said.
Great quote and great insight. Understanding how the brain works and is stimulated augments communication. Especially important for dry, theoretical subjects.
Look how he use only a single screen and has this extraordinary device nobody uses anymore left of his screen but proves to be one of the best tool to dig deep into code.
As to why Emacs calls everything something else, well, Emacs was first. As to why Emacs doesn't change its names, well, have you ever tried to change Stallman's mind?
I know. I’ve been an emacs user for 30 years, but I tend to just call them buffers. In the old days when I would be using a PPP or SLIP connection into a dialup Unix, my whole screen would be Emacs in VT100 mode so it made a lot more sense to thing of them as windows back then.
We won! Emacs vs VI war over. It's finally over thanks to Knuth! VI users will be forced to pay reparations, and agree to cede territory back to the Emacs military alliance. :)
I also noticed smart people type really fast (if they can touch type) and can switch between multiple windows/tabs fast too. It's not because their fingers move faster than normal people, but because their mind moves smoothly so they can produce a long string of command with stopping to think.
> 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.
As someone whose computing career was improved by learning to touch-type in grade school (Mom had been a secretary, saw that these "personal" computers had keyboards, and bludgeoned the high school to let me in to the summer-school typing class) it's not actually the speed that matters - though that does certainly impress people - it's that it's "automatic". If you're not thinking about letters and where they are, you aren't distracted from the entire sentence (or function) you're holding in your head - it just pours out through your hands into the machine.
(Sometimes I joke about how my hands know emacs, not my brain - but if someone asks me what keys I hit for something, my fingers move and then I work backwards from that.)
(And if you're collecting correlations - I have no musical performance talent at all and have spent maybe 10 hours total poking at musical keyboards - for me, typing is all typing, I expect musical keyboarding is a related but parallel thing, not the same thing.)
I feel this in my soul. My work uses Mac and I'm not used to it. Fn and cmd keys block my reach for alt and control in my vim sessions and make it awkward to go through tabs in the browser with the keyboard.
Fun fact : I have an external keyboard, but it's an MS one, so there is no more drivers, and some keys just won't work (or at least I haven't yet found anyway to remap things.)
I'm an oldster who just got a split ergonomic keyboard for the first time a couple of weeks ago. I'm going through the exact same experience. It's getting better, but my typing/coding speed has been cut in half as I unlearn bad typing habits accumulated over the decades.
Had the same issue recently, with the caveat that I grew up in the UK, then moved to US and back.
I prefer the concept of international standardisation to an American layout in pretty much all areas, with the exception of the keyboard layout; ANSI layouts are far more friendly - for programming, at least. Not just the enter key but the left shift too.
Switched to US layout on everything (because brackets and gt / lt are SO much more conveniently placed) and having to use an ISO keyboard now is just pain. My hands forgot.
One of the smartest people I met as an undergrad at Berkeley was a theoretical chemistry PhD student. He was an extremely slow typist, with mostly hunt and peck. It would be frustrating for me because it would be like 1/4 my comfortable speed (20 vs. 80 wpm?). But being slow there made him faster, because he’d spend a little more time before typing thinking about what to type.
I’ve always had the opposite experience. When I am unable to type well I am massively less effective. This happened when switched from emacs to vim, or got a new keyboard with a weird layout, or broke my thumb, or, hell, anytime I use a phone.
First there’s the cognitive overhead involved with the task itself, as opposed to letting your fingers do the work while you think about real stuff. Second, when you’re slow at typing, typing becomes the bottleneck more often, and your brain is sometimes idling waiting for your typing to catch up. Your brain has the hard part; it should always be the bottleneck. Third, typing fast gives you more options, because you don’t consider “how long will this take me to type out?” when considering different approaches to some immediate challenge. If opening a REPL and evaluating something is going to take you five minutes, you might not do it.
I suspect your friend was a fast worker despite being a slow typist. If he learned to touch-type, he could always have spent the same time thinking as he does now then less time and effort actually typing it.
I understand what you're saying and often feel that way. I think one point to be taken away is not to judge capabilities of X (say, programming) based on Y (typing speed).
However, sometimes I have the opposite desire. I can type on a normal keyboard at 80-90 wpm. On an iPhone I'm probably 1/4-1/3 of that. However, I probably spend 60-90 minutes a day reading/writing emails from my phone. Sometimes going slower allows you go to faster.
> Your brain has the hard part; it should always be the bottleneck.
Or maybe not. Lots of famous people (particularly physicists) talk about the importance of letting the mind wander i.e. the opposite of making sure it's the bottleneck.
I'm a slow phone typist but it's still easy to do. My brain can still think of the next thing to write, or wander.
Interesting - I do this but I learned the skill from sight reading music scores - you have to be playing several bars behind what you’re reading so the skill is in going into autopilot with your fingers as you read. No small coincidence then that Knuth is an organist
I wish modern OS could keep up with my typing and window switching and app launching and ...
I'm constantly perturbed and interrupted when some app window just 'hangs' for a few seconds (some garbage collection going on, probably?). I can't pinpoint any one thing, just... everything seems relatively slow in 2022 compared to, even 10 years ago, and certainly 20. Applications weren't always phoning home to check things during bootup, which I suspect happens a lot now. Our computers are dozens of times faster than in the 90s, and, computationally, some things get done much faster, but others - around UI, it seems - apparently regress.
The worst are the modern async UIs that become responsive early and then reset their state when they fully load - so if you e.g. already typed part of your search string, you can actually briefly see it in the textbox, and then it gets cleared away. Very common on websites, somewhat common on the desktop, in my experience.
Ironically, the old apps that just "hang" for a while during initialization handle this better, because they don't process input at all, so it all just gets queued.
Latency is the worst thing when operating any machinery. I don't know why people tolerate it so much with computers. It's one of the most important things for me when using any software. That's why a long time ago I settled on using tools like emacs, git, i3/sway etc. When I try trendy tools like VSCode etc. I can't believe the latency people put up with.
I've been using i3 for years, there's just nothing that compares to a tiling window.
If I'm in windows I use virtuawin with alt+1, alt+2, etc for switching desktops. Not nearly the same, but works so much better than the builtin crap Windows has.
Paradoxically, I don't use alt+tab in windows to switch between programs. I used to do that, but then around XP (I think) they added the ability for programs to inject themselves into the alt+tab list. That means it's no longer completely consistent, which means I now have to think and check what alt+tab actually does so it stopped being any faster than just using the mouse.
So now if I need to flip between them quickly I'll either put them on different monitors (I use 3) and/or put them on different desktops. The combination makes me effectively as productive without the use of alt+tab. And it feels similar-ish to i3, so it's a bit comfortable in that respect as well.
NOTE: Anyone thinking virtuawin is like i3, it's not. It's just the best virtual desktop on windows (imo of course). Nothing on windows comes close to i3.
Preach it - my inability to figure out or control why the UI decides it's time to ignore what I'm typing in realtime while it's trying to back up a file (or whatever) is the cause of so many frustrations
I'd imagine it's mostly a question of having the freedom to be able to work upon subjects which very much interest you, independently and on your own schedule, without much outside pressure or coercion to produce tangible results that are useful to anyone but yourself.
There may be something to that, at least according to one study. Specifically, this article [1] indicates "embracing new mental challenges may be the key to preserving both brain tissue and brain function."
A colleague and I also had the delight of visiting him, quite a few years ago now. I'd been doing some unusual stuff with TeX, and had been in touch and showed him some examples of our work.
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.
The first three were published together as "Volume 4, Fascicle 5" in 2019, and the last one—Satisfiability—was published as "Volume 4, Fascicle 6" in 2015. Of course the actual publication as Volume 4B has hundreds of fixes and additions beyond what was published earlier, and a lovely preface that you can read here: https://www.informit.com/articles/article.aspx?p=3143614
> You might think that a 700-page book has probably been padded with peripheral material. But I constantly had to "cut, cut, cut" while writing it, because […] new and potentially interesting-yet-unexplored topics kept popping up, more than enough to fill a lifetime; yet I knew that I must move on. […] I wrote nearly a thousand computer programs while preparing this material, because I find that I don't understand things unless I try to program them.
Re "being paid", consider that he took early retirement in 1992 to work on this book that he sees as his life's work (https://cs.stanford.edu/~knuth/retd.html) (and until then was doing in his "side" time, separate from his job of teaching and research), giving up whatever salary a tenured Stanford CS professor's would be, and has been living off savings and royalties since then: he only gets "paid" when people choose to buy the results. (And if he were to focus on money he'd probably put out more newer volumes than 2 in 30 years, rather than keep making newer editions / fixes to earlier volumes…)
But you're right that Knuth has a dream "job" that the rest of us, at least those with the slightest "scholarly" inclinations, can only envy him for: he reads, explores, digests, and explains, the topics he likes and in the way he likes, and the results are great. But when you're already a legendary programmer in college (http://ed-thelen.org/comp-hist/B5000-AlgolRWaychoff.html#7), and have won a Turing Award at 36 (http://hagiograffiti.blogspot.com/2009/01/when-will-singular...) for a book you've been writing in your free time, one can say you're entitled to the life.
You can get a bit of an idea by reading Knuth's "The IBM 650: An Appreciation from the Field", written in 1986 and nostalgically looking back at the 1956–60 period when he entered college and first encountered a computer (the IBM 650). The paper is available here and is gripping reading: http://ed-thelen.org/comp-hist/KnuthIBM650Appreciation.pdf
I consider this the first and last generation of truly self-taught programmers. Earlier programmers either built the computers themselves or were hired and trained on the job; they were professionals. Later programmers (all of us) did have some programming books/tutorials or some sort of community to draw from. But Knuth and his peers just had a machine with a manual describing its opcodes, and practically "discovered" programming independently at each "site", e.g. college. As he writes:
> The IBM 650 was the first computer to be manufactured in really large quantities. Therefore the number of people in the world who knew about programming increased by an order of magnitude. Most of the world's programmers at that particular time knew only about the 650, and were unaware of the already extensive history of computer developments in other countries and on other machines. We can still see this phenomenon occurring today, as the number of programmers continues to grow rapidly.
"Imagine being Noah Webster at work, writing 'thousands of definitions' of words that already exist, and being paid for the privilege!"
There is value in providing reference texts. There is value in providing sample usages of programs to the unfamiliar. There is value in demonstrating alternative means to reach the same goal.
Donald Knuth's work of cataloguing and examining the different branches and leaves of computer science would be valuable even if he weren't also a world-class computer scientist in his own right (which he just happens to be).
If you think Knuth's work is "unproductive" you obviously either don't know much about Knuth, or you just don't know what you are talking about. He has had a profound influence on the field of Computer Science - and everyone who has met him says he's one the nicest, humblest people they've ever met.
I for one would feel privileged to get to meet him.
He is writing programs to help him publish a volume for one of the most important series on computer programming. we have different definitions of the word productive.
This is also an important topic for Knuth and he has published a book on the subject (which I have not read nor discussed with him as the topic is of zero interest to me).
OK, even though the bible doesn't interest me, we once went through the score of the Fantasia Apocalyptica together and it was useful that I knew enough of the bible to discuss some references. There are also musical "puzzles" or clues in the score a few of which I was lucky enough to catch so I didn't come off as a complete dufus.
Not really. It is Paul. The debate was there and the dominate one is peter-james Jerusalem group. Paul actually lost if you read between the lines. Only later as that branch was sort of kill of and Pauline Christianity with the Hugh gentile group won. Then no Jewish law
In Google’s recent “Hacking Google” series [1] they appeared to credit Knuth via his bug reward program in his books [2] as having created the first software bug bounty offer.
Anyone aware of any software bug bounties that predate Knuth’s?
> 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.
As a saddening commentary, Knuth stopped sending those checks in 2008 because of problems with check fraud. Since this refers to Knuth, I carefully parsed that not as "because of check fraud," but, "because of problems with check fraud." There is an interesting difference between those two.
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 think Knuth also created news.ycombinator.com, google.com, and facebook.com. He refused all google stock, however, since they implemented map-reduce incorrectly, using a set of filters. In the case of fb, he was outfoxed, because he didn't have the documents to prove that he created all the algorithms for matching faces.
> He refused all google stock, however, since they implemented map-reduce incorrectly, using a set of filters.
That was a reference to google filtering their presented results instead of being driven more by search results, as they advertise that they are.
> In the case of fb, he was outfoxed, because he didn't have the documents to prove that he created all the algorithms for matching faces.
That sentence was a nod to the accusations against Zuckerberg for stealing the original code for FB.
Of course, this was all presented in the context of the prodigiously productive Donald Knuth for your reading enjoyment. In this way, the comment was meant to show though tongue-in-cheek how great Knuth is for Comp-Sci. It was not an attempt to drag any company through the mud. That happens without me.
Very cool. I own the originals and the 4th but sadly I have to admit that even though I am a reasonably accomplished developer with a couple of CS degrees I have a hard time understanding this work and have not yet really read it. I feel like I am publicly admitting failure just posting this. I still have time to make sure these are not just bookshelf decorations though.
The 1st Chapter is one of the best mathematical discussions I've ever read, bar none. But hardcore math isn't needed for most of us programmers. Knuth knows this.
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.
He wrote his "Concrete Mathematics" book specifically to address your first point. I admit its the only book of his I read cover to cover and it wrecked me.
I agree on the section on linear lists. It was really eye opening for me back when I read it the first time. It's remarkable how much useful information there is about such a seemingly simple concept.
You're not the only one. If we're honest most of us buy the series as a mark of status / pride, not out of any plan to actually read it. I mean yeah I do plan to. Probably once I've retired. But that's a long way away :-)
This is the function my copy of TAOCP serves. I'm not anywhere near knowledgeable enough to digest all of it, but when I need something and I want to understand the ground theory behind it then to Knuth I go.
My most recent use of it was to convince my team that binary search is in fact not a good interview coding question. It's surprisingly tricky and Knuth explains exactly why!
The part where he explains how a binary tree can be unbalanced, and when, was really surprising to me. Never assume that just because your accesses are random that the tree will remain balanced on average.
If you’re interested in reading them (and they are extremely readable), you should first know something (not everything) about programming and discrete mathematics. If you watched some YouTube videos on logic, sets, graphs, etc. you’ll be more than equipped. Knuth has even written a book, Concrete Mathematics, that covers these pre-requisites but it might be faster and easier to watch a Khan Academy video!
Uuuuuh. I know a lot about programming and discrete mathematics (I used to tutor both, and I've used a lot of discrete math throughout my 20 year career as a software developer) and I still struggle with the books. Maybe your definition of "something" varies from mine.
Does Khan Academy cover the math topics of Concrete Mathematics yet? Looking at their list of math courses I don't see a single discrete math course in the bunch.
Right, which was what I was getting at. The person I responded to had written:
> Knuth has even written a book, Concrete Mathematics, that covers these pre-requisites but it might be faster and easier to watch a Khan Academy video!
Which suggests KA as an alternative to CM. Which doesn't follow if it doesn't cover the same material.
Concrete Mathematics is in fact an elaboration on the chapter covering the prereq in TAOCP. It was well worth it considering how great this chapter is.
The best part of TAOCP for me is how incredibly good the exercises are. The gradual difficulty is perfect and from 20 onwards you always get some interring insight from solving them. I am especially M and HM ones which are amongst some of the best maths problems I have seen despite being in a CS book.
Honestly, despite everyone's claims of how "beautiful" the books are, I think they are rather terribly formatted.
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.
Writing style is subjective and I find Knuth's delightful: almost every paper of his that I've read has been fun. Even in his technical papers he writes at the level an undergraduate student with decent mathematical background (or a strong high-schooler) could mostly understand, which suits me just fine, especially compared to some other academics who write only for their peers / graduate-level and higher. And in any case, all the mathematical parts of TAOCP can be safely skipped if one is not interested.
But regarding your complaint about formatting, note that the book design of the TAOCP volumes is not Knuth's doing: someone at Addison-Wesley came up with them in the mid-1960s, and the first three volumes were published with Monotype (hot-metal) typesetting. When Knuth wrote TeX in the late 70s/early 80s, his goal was simply to retain the style of the books. (The layout was fine; the publishers were trying to move to phototypesetting and the fonts were poor https://tex.stackexchange.com/questions/367058, so he needed digital fonts and wrote METAFONT to create them, and he needed TeX just to be able to use those fonts.) Perhaps the book Concrete Mathematics will be a better example for you to critique, as Knuth had more of a hand in its typesetting (though there too a book designer was involved; the article Typesetting Concrete Mathematics has some details, reprinted in the Digital Typography volume and a poor scan of its earlier publication here: https://tug.org/tugboat/tb10-1/tb23knut.pdf).
About chapter length: the initial table of contents was one book of 12 chapters; Knuth wildly underestimated the printed length of what he had written (not many people know he actually wrote the whole book, all 12 chapters, in the 1960s, amounting to about 3500 pages — since then you can say he's been updating the chapters and publishing each section when he thinks it's ready), so the plan changed to seven volumes with the same chapters. And the chapter sections' lengths have themselves grown with the growth of the subject; as you can see, the current volume 4B is just a tiny fraction of the projected Chapter 7: covers 7.2.2.1 and 7.2.2.2.
Also, about the flowchart for how to read the books: it's partly a joke about flowcharts, but the suggested reading order is very much linear: https://i.stack.imgur.com/UCsOx.png — in words, it's just something like "read the chapters in order, skipping starred sections on the first reading. Also, feel free to skip boring sections, and skim math when it gets difficult" (he addresses the mathematics in the preface on p. viii).
That flowchart needs a HEFTY dose of https://www.drakonhub.com/, and I ALMOST had finished remaking it in it just now, but a terrible mistake on my part wiped my progress; thanks, Android. :(
Except everyone who talks about how to read the books successfully--including the books themselves--talk about jumping around in them in a way that requires a lot of skimming.
I don't find the text in any other book I own to be insufficient, or even noticeably that different from Knuth's books (with the obvious exception of some fly-by-night print-on-demand stuff purchased off Amazon in recent years). It's an assertion in want of proof. TeX might be the greatest example of Yak Shaving in human history: Knuth spent at least 30 years between Volumes 3 and 4 to work on TeX because of dissatisfaction with layout in V3.
This is what I'm talking about. Notice the use of colored blocks and whitespace to break up the flow of the page, to callout different asides and section headers.
> everyone who talks about how to read the books successfully
I will be a counterexample: I read all three cover to cover, and seriously attempted every single exercise (although in some cases, "attempted" just meant "actually understand what he's asking, which in itself sometimes took me several days). I didn't skim or jump around at all.
I like TAoCP's typography better in a subjective aesthetic sense. But when I'm actually trying to read, understand, and work-from workbooks/exercises, I find the Linear Algebra example a lot better.
> Why make the act of reading about programming hard
These books are not really programming books, they are math books. There are oodles of "programming" books out there that teach algorithms, like how to implement a quicksort and why X algorithm is better than Y for problem Z. Knuth's books are more like a graduate level algorithms or discrete math course.
>then spews dense mathematical notation when he gets into details
Because the Art of Computer Programming isn't really about programming per se, it's about the theory and analysis of programming IMHO. I'd say O'Reilly books for more famous for learning programming.
I vaguely recall an anecdote being told here on HN where Donald Knuth met Steve Jobs. Steve Jobs said something along the lines of "I admire you very much, I have read all of your books!", to which Donald Knuth replied something to the effect of "I don't think so." (more politely, though, I presume).
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.
https://www.youtube.com/watch?v=DmbGs290qeM -- Dr. Knuth sets the record straight at a talk being given by Randall Munroe (of xkcd fame). Spoiler alert: "I only met him a couple of times [...] and in each case I was impressed by him probably more than he was impressed by me."
the impression i have--i'm not sure where i got it from, could even be from the first book itself--is the art of computer programming's mission is to be a useful resource if, a thousand years from now, computer science finds itself starting from scratch. contemporaries can learn from it, but by even just buying copies you increase the odds that the books can be recovered and used in that hypothetical situation.
Same here. I was toward the end of an associate's degree in programming and finding Knuth Vol 1 in the library stacks felt like discovering there was a whole continent of intellectual effort where I'd only seen a tiny neighborhood. It helped motivate me to go get a BSCS. But 40 years later, I've still only dipped into it from time to time (I did buy my own copy :))
My dad gave me them as a (fantastic) gift. They're tough. I haven't sat down and really gave them the old college try yet, but I want to at some point. I do feel a bit like a phony having them on my shelf without reading them yet though. They are brutal though.
I always viewed them as more of a reference where I could read up how to find and implement somewhat specialized algorithms. I really lack the discipline/interest to read those from front to back, so you are not alone. Incredible books though!
I've felt exactly like this about NKS. I have tried many times to understand it, but I come up empty. Half the time I think "well, maybe IT IS just nonsense?" and half the time I think I'm probably just not mentally sharp enough to get it. But I try every couple years or so, but the activity has yielded little more than being a paperweight in my house and a quiet exercise in looking at pretty pictures for me.
Honestly I wouldn't put NKS in the same level as TAoCP. NKS is way more experimental, TAoCP is more of a survey of the entire field. NKS is mostly analyzing the results of his experiments, TAoCP is more about the complexity analysis and proofs of the various algorithms.
Also, there couldn't be a bigger contrast between Stephen Wolfram and Donald Knuth. Knuth rightly should have a big ego, but he is a very humble, generous man. Wolfram seems to have a chip on his shoulder, fights with other academics, seems to want to be given credit for being "first!" on things.
I love Mathematica, but Wolfram himself is a controversial figure who often gets in the way of his own work.
Nostalgia time! When I graduated years ago, Knuth's books were still all the rage because the central themes in the CS departments in universities were fundamentals: algorithms, compiler theory, operating systems and what not. We referenced TAOCP for implementing the priority queue using fibonacci heap for our OS projects. We studied chapters on vol 2 for some of the numerical algorithms, and etc. We read Parsing Techniques cover to cover to understand how to write a parser. We still carefully studied AI: A Modern Approach and the dragon/dinosaur/tiger book. Every once in a while a discussion on Knuth's work went to the first page of HN or Programming Reddit. Then, we got more and more mature libraries, and we rarely needed to understand 10 different algorithms that solve the same class of problems. Consequently, we got fewer discussion about Knuth's work too. Of course, it's super fun to read his meticulous discussion of combinatorial algorithms in Vol 4. It just that TAOCP does not appear as essential to as many people as a decode ago.
Can someone honestly tell me if they have actually read these books AND found them useful ON TGE JOB? What do you guys do for work?
I tried reading part 1?? Like ten years ago and it was pretty much assembly language or something I believe. And gave up since it wasnt something that I needed in academia back then and there were far better ways to learn DSA
I used them to implement an arbitrary precision math library for an embedded processor that needed to do some precise calculation in an autonomous environment. The embedded processor had no floating point capabilities.
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.
Interesting! A small correction: "innumerate" means "incapable of doing arithmetic"; perhaps you meant "innumerable", which means "incapable of being counted". Also you have "wuthor" for "author", "bible" for "Bible", "donÄt" for "don’t", "WHat" for "What", and "theologician" for "theologian".
My favourite thing about his 3:16 project is the name he gave to the technique (of, effectively, taking a stratified sample of the Bible in order to get an overview of its themes): "the way of the cross section". (If the pun isn't immediately apparent, see https://en.wikipedia.org/wiki/Stations_of_the_Cross.)
I've spent a lot of time doing the latter and had trouble understanding the former the one time I needed it (during a high pressure project where I simply didn't have time or the quiet time to spend two days digesting it).
I've been randomly skipping around inside these books for a long, long time. They're full of little gems that you won't find elsewhere.
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):
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):
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:
In the late 1990s I implemented an algorithm from one of Knuth's books. (An algorithm to generate prime numbers.) I found a mistake!
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.
TAOCP is not job training now, if it ever was; that is trying to get the cart to pull the horse.
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.
Writing a decent Sudoku solver takes just a few hours... I did this last year in order to refresh my memory on how Ruby worked. Reading TAOCP would take a few more hours than that.
Mostly the world changes due to unpredictable emergent phenomena, but occasionally you do get intentional changes as well. But intention is individual, not collective; there's no such thing as collective intention. At best you have many people's intentions in agreement. Rarely does that arise in a workplace.
What do you mean with "collective intention"? A person intention is the result of collective effort of its neurons. Things like collective representations and collective unconscious are well established concepts.
Whether these things positively exists outside of one mental experiment is an other matter, but so is the notion of individual and self.
I'm currently going through Fascicule 6A dedicated to SAT solving and I can tell you it is by far the best reference. I haven't found anywhere else a complete reference that builds a SAT solver from scratch while explaining why each technique is used.
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.
It just means you're not doing anything interesting on your job.
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.
Serious question - why wouldn’t you search for the algorithm you need (or the problem statement) on Google scholar these days? I have the books but if I ever found myself reaching for them at work, I would consult most recent literature
I read a lot of papers I find on Google Scholar, and it's very common that they are wrong, or don't accurately survey related work, or pointless. For an overview of a field or a subfield, you want a review paper, and TAOCP is the best review of algorithms I've found. It's true that some of the volumes are outdated, but in many areas the new work is incremental.
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.
Nowadays, most papers in CS are filler (or even worse, sometimes they're just fraudulent), written to meet arbitrary bureucratic requirments. Sifting through that noise is really tedious.
Over 25 years ago I was researching algorithms for a search engine I had been commissioned to write, and for its disk allocation strategy I had settled on a "buddy algorithm" from The Art of Computer Programming Vol 1. It had nice properties and was easy to make.
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.
If you can't find a bug that exists in your copy of TAOCP, maybe you didn't learn what it was teaching you :-)
(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.)
A colleague of mine had invented a technique for factoring composite numbers, that he thought would be quite fast.
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.
This is exactly what TAOCP can be best at - if you know enough about the problem domain to be dangerous, or even to build a solution, you will know enough to read the relevant portion of TAOCP, where it is very likely you will find value.
We had a very specific use case, where the input was a known composite, and some properties of the factors were known.
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.
My laptop is raised to the height of my other monitors by Feynman's boxed set of Lectures on Physics, Aho & Ullman's Foundations of Computer Science, and a Scott Adams compendium.
This way my computing is based on a strong foundation...
LoL :) we should have a __how you boost your monitor to the right height thread __ I use Mckusik's freebsd book, Brooks computer architecture, Myth and meaning by Levi-Strauss. The last one is for calibration only.
I mean like how about using a cheaper book. Cookbooks are almost literally a dime a dozen at yard sales. Too bad phone books aren't what they used to be.
Printer paper is a good choice as well. Reams are quite sturdy and generally available in offices. You can titrate the height in very small steps if needed. And the stand is easy to reuse when it's no longer needed. Not as low cost as used cookbooks though.
I read these the first time so far back that the extensive section (with the fold out pages) covering sorting on external tape drives was of interest to me. Over the intervening years I've gone back to these books many times to check on my understanding of subjects. (I've also bought and used all of his other books too: TeX, Concrete Mathematics, and other collected works.)
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.
I think #1 and #3 of these make a particularly good combination; they have very different and quite complementary merits. CLRS is rigorous and precise and analytical and theoretical. Skiena is handwavy and pragmatic and not always quite correct. CLRS is written for people who will be implementing complicated algorithms. Skiena is written for people who will be using other people's implementations. CLRS is deep. Skiena is shallow. CLRS is heavy going. Skiena is pretty easy reading.
(But ignore everything Skiena says about generating random numbers.)
Useful on the job? Absolutely. They give me hope that when my life is over I'll have done something more significant than pushing bits between API calls.
Disclaimer: I'm nowhere close to finishing any of the books.
I don't own any of them, but sometimes get them from the library for interview prep. Totally over the top for that, but sometimes inbetween googling and overcomplicated other books it's a nice relief to read through these lines, into which very obviously a lot of thought has gone. The opposite of all the fast-lived crap we have to deal with on a daily basis, and therefore also useful for the job. Motivating, I would say.
CLRS is what I own, but I never found it too helpful for that in particular. For this kind of quick refresher/prep work I found the "Algorithm Design Manual" more practical, because it gets to the point quicker. Then sometimes expanding on some very specific details with the Knuth books, but yeah, that is also partially just for fun.
I used them to implement a random number generator in an embedded system to generate morse code, for training ham radio operators. I also used him KMP algorithm for writing pattern matchers.
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.
> actually read these books AND found them useful ON THE JOB
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.
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.
The most use I've gotten out of it was when I had it on my bookshelf in my Zoom background while TAing a class I think. One of the head TAs recognized it and asked if I had actually read it, and I told him I managed to read through volume 1 once and not solve many of the problems, which took about 3 months reading ~10 pgs/day. He was still impressed, and I think it helped me get the head TA role after he graduated, as he nominated me for it.
In terms of actual programming use, not much, but I still haven't read the other volumes yet.
Yeah stuff like that is handed out on competence, when it came to situation, there were a few other equally qualified candidates who had been TAing that class. It worked out so we all held head TA at one point. TAOCP in the background probably played a tiny role if anything, but it's the one distinguishing event I remember, which is strange and funny to think about.
Part 1 is the most "useless" - it's basically required reading to be able to read the rest of the book. There are a few sections in data structures that I read to actually apply (I can't remember the exact parts, but I remember pouring over the book), but mostly it's enjoyable if you like programming for programmings sake. If you think of programming as a practical means for achieving some end (job or creative pursuit) then these books aren't for you. There is absolutely practical stuff in here, but it's all shown from first principles.
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.
Part 1 has some cool material. The mathematical preliminaries, polynomial arithmetic to motivate linked lists, and symbolic differentiation to motivate trees. The MIX simulator written in MIX too!
Yes, to be more clear about my point: there is a lot of learning about MIX to set the groundwork for future stuff, which can feel arbitrary and disconnected from practice. It can be off putting to a new reader. It took longer to read than just about any other part of the book, since the rest of the book has a much higher density of interesting material. Also it’s the only section that is really “required reading” and I most enjoy this book by bouncing around. I just want to encourage new readers to stick with it, it’s not exactly representative of the whole book.
Vol 1 is just an intro to math and his language, you don't really need it, but it's kinda fun.
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 dunno, I found that chapter 2 was incredibly useful, as he covers all the fundamental data structures very very well. Mind you, I actually learned his assembly (MMIX) so maybe it was more useful for me.
IMO Volume 1 isn't that useful because it's mostly setting up the mathematical and architectural foundations. Knowing how to evaluate limits and recurrence relations isn't particularly valuable knowledge for the average programmer.
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 selected parts of it while in the University, studying Computer Science. I think that is the more appropriate time for you to read such a book, since it gives you the basics.
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.
TAOCP is the encyclopedia of algorithms. It is usually not something you read front to back.
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'm not sure if TAoCP is "workplace on the job" material.
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.
I bought them on a whim and they just lay around for years. I gave them away to someone who thought they were interesting. The assembly language he invented added very little to his work.
I dunno, I learned the newer one (MMIX) and it taught me so much about low level programming, honestly some of the best investments of time I ever made.
That being said, if you already know ASM/C then maybe it wouldn't be as useful.
This is one of those book series that I really, really want to purchase as a beautiful, matching, leather-bound set. And, yes, I would read it for pleasure, and I would treasure it.
The joke, for anyone else here who isn't a book nerd (my wife is), is that now whenever an old author dies with unfinished work, or hasn't finished their work (that's you, George!) people make a joke "Just let Brandon Sanderson finish it!" because Mr. Sanderson is an absolute writing beast, he's a "100x writer" if there ever was one and he is working on (or finished?) a book series[0] by a now-dead author and most people think he made it better.
I'm flattered, but have no idea where that came from. While I have implemented some interesting data structures and algorithms in my time, I don't consider myself a "Computer Scientist" or algorithms expert. However, I did work with Knuth in the 1980s, and am in a group photo in his "Digital Typography" book. I agree with all the nice things people have said about him.
I was thinking the same thing when I clicked on the comments. I somewhat expect this will be the last volume in the series, so one could now hope to buy a "complete" set. I would love to revisit and explore all of the material using modern programming languages.
One might hope that he can at least complete 4C such that volume 4 is complete. I am skeptical that volume 5 or later will see the light of day, But I also cannot predict the future.
This comment made me check the history of the official TAOCP page [1] through the Wayback Machine. Volume 5 was estimated to be ready in 2009 at the very first snapshot (1997), in 2010 by 2003, in 2015 by 2007, in 2020 by 2010, in 2025 by 2015 which is the latest estimate today. At the first glance this looks like an eternal "10 years later", but note that that estimate didn't change since 2015 and the 2025 estimate is now only 3 years away. Does this mean that Knuth does plan to publish anything related to Volume 5 by that time?
Same - it's just a joy dropping into some random section and reading through, but my copies are a little abused by that practice. I'd love to have a second set for aesthetics and display.
There's something beautiful about his work on the series. He's been working on it for years, built TeX (not sure if that was for this series or other books of his), and has such ambitious plans. He's a serious legend in the field of computer science and we're lucky to have someone like him to have provided our industry with so much incredible knowledge. I'm interested to see how the series progresses for the next 30 years.
He also seems like the kind of guy you'd want to have a cup of coffee or tea with. Always seemed like a fun and sweet guy in the interviews I've seen with him.
It reminds me of that Hokusai quote (japanese painter):
“From the age of 6 I had a mania for drawing the shapes of things. When I was 50 I had published a universe of designs. But all I have done before the the age of 70 is not worth bothering with. At 75 I'll have learned something of the pattern of nature, of animals, of plants, of trees, birds, fish and insects. When I am 80 you will see real progress. At 90 I shall have cut my way deeply into the mystery of life itself. At 100, I shall be a marvelous artist. At 110, everything I create; a dot, a line, will jump to life as never before. To all of you who are going to live as long as I do, I promise to keep my word. I am writing this in my old age. I used to call myself Hokusai, but today I sign my self 'The Old Man Mad About Drawing.’”
I didn't want to say it out right as it felt kind of morbid, but I'm wondering how it will carry on after he passes. Not sure if there's someone he's asked to continue it after his passing or not, but I hope so.
I was hoping that Fascicle 7 would come out, as that would be on Constraint Programming, and I think that's very similar to SAT-solvers (Fascicle 6) and the BDDs that he's already covered.
Then again: SAT-solvers are a big enough subject matter on their own that backtracking search + SAT-solvers is more than enough to fill a volume of its own. So choosing these two subjects as volume 4B makes sense.
-----------
As a fan of constraint programming, I'd love to see Knuth's take on the subject. I hope he doesn't skip over Fasicle 7.
I wasn't aware of this! Thanks for the info. I'll give it a lookthrough.
Its not exactly an easy subject, so I'll need some time to digest the material. Especially if its written in Knuth's famous "difficult, but terse" style.
I once had the pleasure of listening to Knuth speak at my university's computer science department. I joined the very large queue of other people, and expected the great man to totally revolutionise my understanding of – well, I didn't know what, but something. Computer programming to TeX, I don't mind. I was expecting enlightening solutions to famously difficult problems, a great study of algorithms, that kind of thing.
Well, what happened was that he spoke for nearly two hours on self-referential aptitude tests. The kind of "20 questions" game where the 20th question is "The maximum score obtainable on this test is (a) 18 (b) 19 (c) 20 (d) indeterminate (e) achievable only by getting this question wrong" and all of the others are inherently recursively linked. I had no idea these things existed, even less of an idea why anyone would want to study them, and came away later with both mind dripping down the side of my skull and a greater appreciation of SAT solvers and compiler design in functional programming languages. Highly recommended.
Many years ago I needed to understand hashing for an important work project. I sat down and read Knuth's chapter on hashing. It was very, very good and it helped to greatly accelerate my project work.
However.
What I also learned is how impossibly large a topic even just hashing is. A section of Knuth's encyclopedia isn't sufficient space to cover it thoroughly (for some definition of thoroughly) and further research showed how much progress had been made in the subject since Knuth published his work.
This isn't a complaint about Knuth, again, I'm grateful for how much his writing accelerated my understanding. But further research underlined how impossible a task he's undertaken.
Ironically once I studied a part of TAOCP dealing with parallel bit computation as I heard it would help with a Chip vendor I was applying to for a job. The end-of-day boss fight interview arrived with a puzzle I directly solved with my TAOCP knowledge. The result was they failed me on the interview. They said the job wouldn't stretch me. As the years have passed I wonder if what I should have said was "there's no way I could solve this but I know about it from TAOCP already so this is what you do ..."
From the (apparently still hand-coded html) web page:
The fourth volume of The Art of Computer Programming deals with Combinatorial Algorithms, the area of computer science where good techniques have the most dramatic effects. I love it the most, because one good idea can often make a program run a million times faster. It's a huge, fascinating subject, and I published Part 1 (Volume 4A, 883 pages, now in its twenty-first printing) in 2011.
50 years ago, he claimed he was going to write 10 volumes of TAOCP. The actuarial tables are not encouraging here.
He doesn't respond to emails, but his assistant does, and I sent a copy of my book about Xerox to his home address. No answer. But hey, it was worth a shot.
Speaking about Xerox PARC, about a month or so ago I was actually at the 50th anniversary of Smalltalk event at the Computer History Museum in Mountain View; Adele Goldberg participated in an in-person interview, and Dan Ingalls was also interviewed via live streaming. There were many luminaries in the audience, including David Ungar (one of the leading researchers behind the Self object-oriented programming language), but one standout moment was when a very tall elderly man walked up to me to read my nametag. It took me about 30 seconds to recognize that he was the author of Concrete Mathematics and The Art of Computer Programming: Donald Knuth!
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.
There's 6 and 7 planned too, might be a bit of a wait. It's a real shame he isn't likely to finish the series, I would really be interested in that final volume (compilers).
The website notes that 6 and 7 are "only if the things I want to say about those topics are still relevant and still haven't been said." This does make me think that he isn't particularly planning on working on these books at all, especially given that the timeline goes "volumes 4 & 5, revise volume 1-3, reader's digest 1-5, then maybe work on 6 & 7"
The show-runners would exercise some creative license, and we'd end up with things like o(n) being worse than o(n!) in the show, but not in the book. Even worse now that there's a video version of the classic - it's deviations from the text would start to be seen as "the better one" and the software bloat problem would dramatically intensify worldwide as everyone rearranged their algorithms.
Can someone write a volume 0 or volume -1 or some guide so noobs like me who want to enter this treasure chest can do so. I got lost just trying to start this so it might be over my head. I know Python, rusty on Java and cpp never touched assembly.
I can barely find time to read 3-4 pages of a novel before I pass out before bed. I look at volumes like this, Churchill's The Second World War, Summa Theologica, and wonder if I could ever get through these things in my lifetime.
With all the fascicles and updates to released volumes I'm a bit confused as to where one would start today with TAOCP.
If I wanted to give it an honest try, what do I buy?
Volume 1, 3rd edition + Volume 1, Fascicle 1?
If I get this right, fascicle 1 of Vol. 1 is used to replace/update the old MIX architecture used in TAoCP with the new MMIX. If so, what about volumes 2-4?
On a whim a few years ago I attended Knuth80[0], a symposium celebrating Knuth's 80th birthday in Piteå, northern Sweden. I traveled there by train from London and spent a few days listening to fascinating lectures and attending the inaugural performance of Fantasia Apocalyptica, performed by Jan Overduin on the wonderful new pipe organ in Piteå. I only had the opportunity to speak briefly with Knuth, but the whole thing (including the location in northern Sweden in winter!) was a wonderful experience, and should there be any further birthday symposiums I would heartily recommend them to anyone!
Since the pipe organ will be inevitably mentioned in the comments, I'm gonna plug the Youtube channel ‘Look Mum No Computer’, whose gear-crazy author in now apparently in the final stages of installing and patching up an organ in his seemingly interminable basement, after moving it from someone else's house: https://youtube.com/shorts/XGL3rskcQD0
Said organ was built by its late owner not just in the house, but pretty much into the walls of the house, and as a result the thing had to be ripped out of there rather grotesquely, and then rewired again at the new place: https://youtube.com/watch?v=8PwwRR8deHk
I suspect the printer could glue the last 90% of the pages together on each volume and many wouldn't notice. It's a very aspirational book to have, but not many have read much of it.
I am relatively unfamiliar with these books, but the fact that Knuth publishes them in “fascicles” is hilariously intriguing. I have a superficial understanding of Knuth’s character as a programmer but I get the impression that the work is portrayed in a folksy, arcane sort of way.
Yes, actually, you are correct! Hilarious in the sense that I am amused; it makes me laugh; it brings me joy. Intriguing in that makes me want to read them. The years-long effort reminds me of Robert Caro’s series on Lyndon B. Johnson. It’s as if he’s been blogging for decades, but in book form.
Knuth got annoyed at the state of mathematical publishing decades ago, and in a fit not seen since (maybe Linus and git counts) stopped what he was doing, learned enough about typesetting to become a domain expert, wrote TeX, and then resumed what he was doing.
So when he uses typesetting/printing terms, he's using them correctly.
As someone who perpetually abandons projects, I just admire that he has kept going with this for so long. It's a huge and daunting commitment to make, and the fact that he is 84 and has completed another book is impressive, even if he never finishes.
A math noobie here: I want to learn the TAOCP but the pre-req is Concrete Mathematics which I also find hard--it seems almost cryptic. Any ideas for a book before Concrete Mathematics? Thanks in advance.
Concrete Mathematics is not a prerequisite, but an expanded version of the "Mathematical Preliminaries" section of TAOCP. (More precisely, Knuth and later Graham used to teach a course at Stanford based on that section of TAOCP; the book Concrete Mathematics is based on the lecture notes of that course.)
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.
It makes me wonder though why previous published mathematics about computer programming has been allegedly faulty. Since I don't know enough math to objectively see whether Knuth has succeeded in his task or not...
TAOCP could have benefited a lot if someone had written a simpler on-ramping version, with examples in a powerful but newbie-friendly industrial-grade language, such as C#.
Knuth wrote that preface in the early 1960s, when it was indeed true that much of what little there was of published mathematical study related to programming was faulty. He succeeded incredibly well: he kickstarted the entire field of "analysis of algorithms", got all the details right and organized them extremely clearly, put it on a sound footing, and now mathematicians take it seriously, and published work in the area is of high quality.
Depending on your mathematical background, you might find working through the Art of Problem Solving books [0] good preparation as they would build an incredible mathematical foundation for you.
Honestly after working through those books, you could probably complete self-studying an undergraduate mathematics curriculum.
“Is that a copy of Knuth?” She homes in on the top
shelf. “Hang on — volume four? But he only finished the
first three volumes in that series! Volume four’s been overdue for the past twenty years!”
So who is the target audience for this type of work? I mean if I want to learn more about something such as combinatorial algorithms, this doesn't seem like it'd be the right place to begin. I want to learn more about the things that I don't know, but at the same time, learning absolutely everything about a single category is typically more depth than I require.
I started talking to him about some of the latest AI research and he mentioned the papers authors, he had already read them! Not only is he still very productive at 84, but he has not ossified into one particular subject but he continues to keep abreast of other related fields.
He also played his huge pipe organ for us, he was gracious, humble, down to earth, truly a treasure. I only wish he could live another hundred years, selfishly so I could see Volumes 5, 6, and 7 of Art of Computer Programming finished.
I should not with some sadness that COVID hit not long after and that year we lost a number of other luminaries in the field like Jon Conway.