Hacker Newsnew | past | comments | ask | show | jobs | submitlogin
Ask HN: Is Knuth's TAOCP worth the time and effort?
205 points by QuadrupleA on Jan 13, 2016 | hide | past | favorite | 132 comments
I recently purchased a boxed set of Donald Knuth's The Art of Computer Programming on Amazon ( http://www.amazon.com/gp/product/0321751043 ) based on its stellar reputation as one of the indispensible, foundational computer science books that every programmer should read.

I excitedly started delving into it last night but after an hour or two of reading and exercises I started getting the sinking feeling that I'd just wasted $178.08. It seems quite mired in 1960's-era academic minutiae and tedious mathematical formalism that doesn't seem very relevant to a modern practicing programmer.

For all its focus on algorithmic performance I found no mention of pipeline stalls, designing for cache performance, branch prediction, multithreading, etc. which are all very fundamental aspects of good performance on modern hardware.

So for those who are practical programmers and have gone down the Knuth TAOCP rabbit hole I ask - was it worth it? Did it give you knowledge and skills applicable to your programming work or was it mostly academic / intellectual entertainment?



> based on its stellar reputation as one of the indispensible, foundational computer science books that every programmer should read.

A while back, I was joking with some friends that TAoCP is to the programming world what Finnegans Wake is to English literature: you're not supposed to read it, nobody's ever actually read it. We all just say we've read it, talk about how brilliant it is, and place it prominently on our office bookshelves to silently humblebrag to anyone who drops by. Sorry you had to spend $178.08 on that lesson, mate.


And this shows a huge folly in our industry.

Short answer, is the book easy? Of course not. Is it dated in approach? Yes. Sorta. What would make it better? A modern language? Why?

Consider, just yesterday there was someone designing an elevator system using python. That is literally one of the first examples in TAoCP.

Not long ago, there was an article about how linear search with sentinel values is actually faster than binary search for many data sets. This is, again, one of the first treatments of searches in this text.

I'm waiting for someone to rediscover that you can make a tree for depth first traversal, such that you do not need to use a stack. Again, one of the early topics in these books. Curious about different characteristics of Tries/Trees/Lists/Hashes?...

Is it worth the time to read end to end? Almost certainly not. The math heavy sections are definitely going to scare off a lot of people. Myself included. This mainly means to skim the exercises.

But, there is a lot to offer in the industry of programming. Knuth picked an order to offer this information and is going in that order. The latest topics he is just now getting to are hugely relevant in many endeavors and I recommend people at least be aware of them.


> But, there is a lot to offer in the industry of programming. Knuth picked an order to offer this information and is going in that order.

Perhaps it's sacrilege, but I've always considered it kind of weird to take on a project like TAOCP in a field that's growing far faster than it can be documented by one person.


The fundamentals of computation remain the same.


Sometimes I believe it strongly, sometimes I don't. Do deep fundamental, mathematical analysis help in the accidental social complexity found on programming stacks sometimes ?


Last time realized that basic algebra (equivalence relation and classes) were helping me to solve a concrete programming problem I was having (having something to do with syntactic trees). It was a big surprise to me. Equivalence relations are a simple concept [0], and maybe my problem could have been solved without thinking of it, but still, some fundamental math helped me for my problem, and I was stunned by that.

[0] https://en.wikipedia.org/wiki/Equivalence_relation


I believe this kind of problems are already far away from most people's job and one foot in the math side of programming.


Also, I didn't want to diminish your point. When you understand the value of mathematical abstractions for any kind of tasks it's a bliss.


In fact those situations are pretty rare, it was the first time it happened to me that a mathematical concept helped me to understand how to write a certain algorithm that isn't specifically mathy (as opposite to implement something purely math related), so I would that, sadly, your previous comment is on the point.


Certainly, I realize he's not writing about the cool new library for Python or something, but even just looking at actual computer science stuff, the field is expanding rapidly.


> "but even just looking at actual computer science stuff, the field is expanding rapidly."

Is it though?

Hash tables - 1953, Red-Black trees 1972, Quicksort 1959, etc...


Look at Knuth's future book plans, and consider all the things he's not putting in them that are current. He's also revisited the books some, and plans to do so again in the future.

I don't mean to take away from the books - they're beautiful and full of a lot of timeless knowledge. There's just something that seems a bit ... I can't even find a word for it ... about the endeavor.


I believe the word you're looking for is sisyphean, and I actually don't agree.

You've yet to make the case that the fundamentals of computing science are changing so much that documenting them is not a worthy task.

Again, basic algorithms and data structures simply have not changed. Their performance characteristics, methods for optimal implementation, etc, certainly have as computer architectures have evolved (think reordering CPUs, multi-level caches, changes to data storage technology, etc). But the basic algorithms remain the same. Quicksort is still quicksort.

It's true that over the last decade some new concepts have reached a new prominence (e.g., lock-free data structures), but those are additions to the field. They certainly don't invalidate the basics.


you are very correct. I've spent the last 7 years in bioinformatics doing algorithm development and it's almost entirely specialized versions of existing and established algos from decades ago.


Yup, because the math (ironically, the part most people find most difficult about the series) doesn't change. Algorithmic complexity, number theory, set theory. These are things that show up again and again in "higher level" concepts.

These are computer science books, not software engineering books.


> documenting them is not a worthy task.

Woah there! No one ever said anything about 'not worthy'. I have tremendous admiration and respect for Knuth and his work, and like you say, a lot what he's written is timeless.


You totally have a point.

TAOCP is not only hyper-focused, obsessive, bloated, difficult, and outdated, but also genius and foundational and connected to everything.

Kind of like TeX and Metafont.


It would really help if you could list some specific ways that the theory of computation has changed since the writing of TAOCP, and some evidence for why you think that theoretical CS is changing faster than can be documented.


TAOCP has not been written, several volumes of it have. It remains to be seen whether Knuth will even be able to finish what he set out to do, let alone include new things.

> faster than can be documented.

By one person, I wrote.

Here's one that I think is interesting, difficult and evolving: distributed systems. This shows interesting work happening with version vectors, for instance, over the past 15 years: https://en.wikipedia.org/wiki/Version_vector


No need to worry about that one. Looking at Wikipedia's list of volume's, looks like distributed systems are not being covered. But I agree with you anyway. Let's quote the man himself (taken from his website): "As I continue to write Volumes 4 and 5, I'll need to refer to topics that belong logically in Volumes 1--3 but weren't invented yet when I wrote those books". He plans to complete Volume 5 by 2025. Tune in ten years from now to see how it goes.


Knuth is currently 78 years old. It would be interesting to see if he lives to 88, never mind still have the intellectual and or physical capacity to complete such a work.

I wish him the best of lucky and sincerely hope he pulls it off.


Yes, he will revisited the first three books after the fifth finish, cmiiw.


quixotic?


Knuth doesn't cover red black trees.


My suspicion is that the growth rate of computer science is partially due to Knuth's work. TAoCP has a fair amount of original research in it and Knuth developed tools like the Stanford Graph Base, original algorithms, and original numerical methods as part of his research for the book...and TeX and Metafont for it's publication.


Guts.

Also (you probably know): "The unreasonable man ..." - Shaw (GBS)

https://en.m.wikiquote.org/wiki/George_Bernard_Shaw


I read (and understood) volumes 1 to 3 (text, exercises and answers to the exercises, insofar they are present). It is not that hard to read, if you combine it with the right set of university courses in discrete math, combinatorics, and number theory, and some hacking on a 80's home computer (teaches one assembler)

Especially without those math courses, I imagine it will be a tougher read, certainly for those grown up with multi-mega or multi-gigabyte machines who expect it to be on programming, not computer science.

And it isn't 60's era formalism, it is low-level computer science.


It's OK. You may display that book prominently and proudly on your cubicle's bookshelf. You've earned it! ;)


> "It's a pleasure to meet you, Professor Knuth," Steve [Jobs] said. "I've read all of your books."

> "You're full of shit," Knuth responded.

(http://www.folklore.org/StoryView.py?story=Close_Encounters_...)

Yes, now we know that this never happened, but I like to think it did.


He could respond that way to everyone.

In every full set of TAOCP, there is a sentence that reads "If you have read this far, mail this string to the author to collect $25." The sentence is followed by a 10 character alphanumeric string. The string and placement of this sentence is randomized: different in every set.

To this day only 3 people have collected their checks. All three have them framed on their walls.


Too late to edit, so I'll reply to myself:

My parent post was a (badly executed) joke, riffing on a) the famous bug reward checks and b) the running joke (mentioned in other comments) that a lot more people own TAOCP than have actually read it. EDIT: and c) the urban legends of students putting such a "test" sentence in papers they hand in to inattentive professors.

There is no better way to kill a joke than explain it, but mine was DOA anyway...


Wow. This sounds like an urban legend (for values of "urban" that mean "university CS departmental"), but I would love to be convinced that it is true.


Hmm... I've only ever heard about the reward checks for finding errors in the books. https://en.wikipedia.org/wiki/Knuth_reward_check


I'm skeptical. I read the first 3 volumes nearly 20 years ago, skipping only a couple of the most laborious mathy sections and don't recall seeing this.


In truth, if you haven't actually read Finnegans Wake, you've missed a grand literary experience.


I've read Finnegans Wake and view it as almost entirely a waste of time. Maybe that marks me a philistine, but I put a whole lot of effort into the book - reading books about it, listening to two different versions on tape - and it did pretty much nothing for me.

And to the original question, I consider TAOCP probably not worth the time and effort to read in detail. It has a lot of interesting stuff if you have infinite time, but very little that I've found practical to me. I've read enough of TAOCP to get two Knuth reward checks but can't motivate myself to read more than a fraction of it.


You're right. It's gibberish.


In truth it is an extremely difficult book to read due to its experimental writing style. See for yourself:

https://ebooks.adelaide.edu.au/j/joyce/james/j8f/complete.ht...


It really appears tedious, at best.

The explanation is golden:

https://en.wikipedia.org/wiki/Finnegans_Wake

"Despite the obstacles, readers and commentators have reached a broad consensus about the book's central cast of characters and, to a lesser degree, its plot. However, a number of key details remain elusive.[6][7]"


I took a class on FW in college, and that definitely helps. Perhaps the book is "hard," but it is hilarious. I can't read a page of it without finding something laugh out loud funny. If that is hard, bring it on. The book really has no beginning or end so feel free to jump around at will. I don't think it is good comparison to taocp.


What did you find laugh out loud funny in Finnegans Wake? (A serious question, I'm not trying to be argumentative.) To me, there were lots of things that were clever or slightly amusing, but nothing near hilarious.

Some examples from the first chapter "oystrygods gaggin fishy-gods" - ok, that's clever turning Ostrogoths and Visigoths into seafood gods. The Willingdone Museyroom section was entertaining enough with "Willingdone" and "Lipoleum" for Wellington and Napoleon. "And a barrowload of guenesis hoer his head" - Guinness the beer and Genesis the book of the bible, clever enough.

I've read a few comments before saying that FW is hilarious. Maybe it's pointless to try to dissect humor, but I'm just not seeing it.


"Shem was a sham and a low sham and his lowness creeped out first via foodstuffs. So low was he that he preferred Gibsen's tea-time salmon tinned, as inexpensive as pleasing, to the plumpest roeheavy lax or the friskiest parr or smolt troutlet that ever was gaffed between Leixlip and Island Bridge and many was the time he repeated in his botulism that no junglegrown pineapple ever smacked like the whoppers you shook out of Ananias' cans, Findlater and Gladstone's, Corner House, Englend. None of your inchthick blueblooded Balaclava fried-at-belief-stakes or juicejelly legs of the Grex's molten mutton or greasilygristly grunters' goupons or slice upon slab of luscious goosebosom with lump after load of plumpudding stuffing all aswim in a swamp of bogoakgravy for that greekenhearted yude!"

I personally think this passage is one of the funniest things I've ever read. First of all, it rolls off the tongue in the most ridiculous way ever (you have to read it out loud) and second of all he manages to write entirely about food while making you think entirely about naughty things.


No accounting for taste but you have got a peculiar sense of humour if that makes you laugh. Give me Professor Stanley Unwin any day.


As you say, it is difficult to explain humor. The best I can do is try to give examples. And to be honest most of the things that immediately strike me as funny deal with sex.

In the passage cited below by jhedwards, I find the way Joyce suggests Shem's Greek-Jewish heritage explains his taste in cheap prostitutes very funny (as well as his skewering the sanctimoniousness of it all, "you like prostitutes but only the cheap ones"). Also, that he gives the address of the whore house, like it is an advertisement is also funny.

You mention the first chapter, so I started reading from the online link given earlier in the thread. In the second paragraph, I found it funny the way he says that topsawyer (Tom Sawyer?) had not exaggerated the size of his balls when they were "doublin their mumper all the time."

It's all about the wordplay and frankly being ridiculous. Obviously if you read these things in the context of a forum, you are probably not going to find it funny. Context is very important: http://www.cc.com/video-clips/0i0fy2/stand-up-hannibal-bures...

As jhedwards suggests, if you read it aloud you will hear the jokes.


The first chapter is deliberately impenetrable, using obscure words from many different languages. I've seen commentaries that explain what it's supposed to mean, but it strikes me more as a tall mountain that exists to be climbed. It's more like you're translating it than reading it.

That said, if you can convince people to house rule it as a word-source for a Scrabble game, you can terrify people who want to challenge.


There's a way to read it that many people miss out on and that is to focus on the sound of reading it out loud. If you scrutinize the meaning of the words, sure, you might learn or discover something, but there's a ton of humor and play and fun to be had just by reading it out loud that most people miss trying to "understand" it.


I highly doubt people making all these lists recommending SICP, Code Complete and the dragon book have read those either.


SICP and the dragon book were both part of my CS curriculum. I read Code Complete as a mid-level engineer and found it quite useful. It would not surprise me that many others have done so as well.


Code Complete is very easy to read and good for beginners. SICP on the other hand... I don't think many people actually read that book, it's extremely 'dry'.


James Joyce would probably not have taken kindly to being called "English"


There is this Hindu[1] tale[2] that goes like this:

A king once solicited a scholar to read an ancient hindu text, so that the king may better understand God. The scholar goes away, and after a period of time comes to the king. The king asks "Have you read the text?" to which the scholar replies "Yes I have." The king does not believe the scholar and sends the scholar to read the text.

Some time passes by, and the scholar returns. The king again questions the scholar, and again the scholar replies that he has read the text. The king sends the scholar away telling the scholar to read the text.

Some time passes by, and the scholar does not return. After some additional time, the king has grown impatient and sends some men to find the scholar. When they arrive at his home, the scholar is no where to be found, and has seemingly disappeared.

After studying the text so diligently, the scholar has ascended to heaven and joined God.

My assumption is that once you've truly read The Art of Computer Programming, you will transcend your human form and be one with the Cloud.

[1] Source: My dad, who is not the most reliable person when it comes to these sorts of things.

[2] I'm paraphrasing it, as I am also no the most reliable person when it comes to these sorts of things.


So in today's terms the tale can be translated to: read the book and once you have you won't be asking these questions anymore.


Disclaimer, I only read the first book.

Depends what you want from it. I used the first book to study for my Bachelor's degree final state examinations, and it served me well :-)

In other words, yes it is very academical, in the truest sense of the word.

From what you say, that you want it to "mention of pipeline stalls, designing for cache performance, branch prediction, multithreading, etc.", you might find better use of Andrew S. Tanenbaum books. I have only read his Computer Networks [1], but it has saved me at least 14 hours of boring lectures at uni, and helped me with some protocols work. He still does research in distributed OS-es, so would hope, that rest of his books would have same amount of readability and usefulness as the one I have read :)

Back to Knuth, if think you have no use in mathematical formalism, or college math in general, you will probably find it little more than intellectual entertainment.

There are of course areas where having formal theory of a thing is beneficial when programming, even if you yourself don't apply it (i.e. the chapter on random numbers seems like something everybody touching any code related to security should read, i.m.o)

But even then, if you suddenly need to learn more math theory, there are probably better sources than Knuth.

As somebody who finished my Msc already, I like it as my intellectual entertainment just fine :)

[1] http://www.mypearsonstore.com/bookstore/computer-networks-97...


It's not useful as a reference, but it is full of delight – though only if you actually do the problems. Many of them are chains of inquiry that build on each other and culminate in some result that gives you so much intuition about whatever it was they were dealing with.

If you're in the Toronto region, I actually run a reading group for these books: http://www.meetup.com/Knuth-Reading-Group-Art-of-Computer-Pr.... We get together about once a month and go through the problems together. Just last night we had a 2.5-hour session about only section 2.3.4.1. I doubt you'd be able to get this much content from a sub-sub-sub-section of CLRS.


> It's not useful as a reference,

I would argue the opposite... When I needed to read about the different approaches on how to shuffle a deck for a card game TAOCP was there for me. When I needed to investigate different approaches for string comparison algorithms, TAOCP was there for me. When I didn't understand what was the deal and why was so hard to implement a random number generator, TAOCP was there too.

Anytime that I needed a reference for a core CS algorithm or data structure, TAOCP worked very well as a reference for me. It feels like the Britannica Encyclopedia for CS.


I keep neglecting to come, mostly out of shame; frankly I find the texts troublingly dense and don't want to feel weak in public.


The term programming here is used with the same semantic definition as "dynamic programming" or "linear programming". Don't expect the book to touch on how to code fast algorithms, rather expect Knuth to teach you the inner workings of the algorithms regardless of their implementations.

Computer science and software development are usually thought to be the same by non computer scientists, but in reality computer science is basically applied mathematics. Expect a lot of it.


Umm, no. "Programming" in "TAOCP" actually refers to "making step by step recipes for a computer" to execute (and is prefixed by the word "Computer" to make this clear). In "linear programming" it refers to something completely different, namely the planning of the use of resources or optimization. "Dynamic programming" is yet something else: a narrow cluster of techniques having to do with memoization in order to help an algorithm identify overlapping subproblems and avoid re-computing them.


Ha.

My first thought was, there sure are different definitions of what "dynamic programming" is, as I've only seen it as related to the Bellman equation (motivation for the name being that it would sound appealing to Bellman's superiors at RAND who had a distaste for mathematical theory).

But then, solving the damn thing is all about identifying and avoiding re-computing overlapping sub-problems, so I guess that is exactly what you meant (even though I have no idea what "memoization" is) :)


Umm, no. You got half the concept right. Programming, especially in the 70s refers to a set of instructions to be followed in order to achieve a specific task.

When you prefix it with "computer" you're specifying the domain, namely all instructions that will allow a computer to do something. Like you correctly mentioned, when prefixed with "dynamic" you're specifying the set of instructions that have a common approach (to break problems into subproblems, etc etc). Similarly, when saying "linear" before "programming" you're specifying that the instructions involving this set use linear variable constrains.


"The term "linear programming" for certain optimization cases was due to George B. Dantzig, although much of the theory had been introduced by Leonid Kantorovich in 1939. (Programming in this context does not refer to computer programming, but from the use of program by the United States military to refer to proposed training and logistics schedules, which were the problems Dantzig studied at that time.)"

Source: https://en.wikipedia.org/wiki/Mathematical_optimization#Hist...


I read all three volumnes and think it's great.

In a sense it's all irrelevant today. How many of your colleagues mentioned O() in any of the past five standups? Add a load balancer and scale up by adding instances, that's today. Don't even profile, much less understand.

However, if you're the kind of person who thinks hard about abstract matters and would like to encourage that side of yourself, then you might want to read that. You'll probably find it hard, particularly if you're a "ruby programmer" or "java programmer" rather than a "programmer", because Knuth is rather the opposite.

Interestingly, I have found that some parts of the book offer much more useful information than others. All offer the same thorough, intellectual approach, but while much of what volumes 1/3 say is useful for a modern programmer (but not for a modern <language> programmer), what I learned in volume 2 hasn't been of much use to me. Today's languages and libraries offer both math and data structures. But in practice, for whatever reasons, they seem to have liberated me effectively from caring about seminumerical algorithms, while I still think about data structures every week.

Knuth writes about making things fast with drum memory. I don't have drum memory, but making my data structures fast within the real-world constraints remains a topic, and somehow it's the same topic. Knuth also writes forty pages about floating point, but when I use floating point I don't worry about that part in the same way. The libraries do what I need and their internal problems rarely or never leak up to me. (Well, at work we do occasionally share "14.000000000002%" of revenue... but it's not a problem. Insignificant.)


pipeline stalls, designing for cache performance, branch prediction, multithreading, etc.

Those are issues for a subset of computer hardware. Embedded computing is still huge and has drastically different performance requirements. TAOCP is designed to stand the test of time, not focus on micro-optimizations that generally have limited performance impact and are a waste of time 99% of the time.


> TAOCP is designed to stand the test of time, not focus on micro-optimizations . . .

Hmmm. My edition of "Sorting and Searching" has a section devoted to tape-sorting.


The idea is that if you fully understand the analysis as it applies to tape-sorting, you'll be able to perform a similar analysis as sorting applies to different problem domains yourself.

The point isn't learning the answer; it's learning how to get to the answer.


He plans to remove that section in the next edition of the book :( I'd argue the section is very relevant since today's RAM works fastest when accessed sequentially.


Same strategies apply to NUMA.


and the cache/memory hierarchy.


> Embedded computing is still huge and has drastically different performance requirements

Even chips as small Cortex-M4 has a write buffer, 3-stage pipeline and branch speculation. And real embedded computing is more and more utilizing hardware similar to desktop/mobile/server. You can't run self-driving car / neural networks / image processing on a single threaded CPU with no cache or branch prediction.


Cache is part of TAOCP

As to the rest of it. It's much cheaper to use a GPU style massive array of dumb cores vs. a few faster cores. Don't forget car companies are spending billions on these chips so spending a little more on software to save a lot on hardware is a good tradeoff.


You can't run the car on it, but many subsystems in any car, automatic or not, can and will run on that sort of machine.


There would be better ways to spend your time than TAOCP.

If you want to scratch that itch, a better way would be Cormen, Leiserson, Rivest, and Stein's Intro to Algorithms (https://mitpress.mit.edu/books/introduction-algorithms).

I'm not aware of such a universal reference for the interaction between algorithms and architecture ("...pipeline stalls, cache performance, ...").

Until that day comes...TAOCP sure looks nice on the bookshelf.


I have read much of it. It's a project I started in my late teens, and have revisited many times over the subsequent twenty years. I have done many of the (simpler) exercises, and I have even sent in a letter detailing a small error in the text, yielding me a minor check (not to be confused with the major check) from the Bank of San Serriffe. I also got a response from Don Knuth, who corrected my letter inline in pencil. Both an awe-inspiring and humbling experience.

Should you read the series? Well, that's largely up to you. There are other books that cover subsets of the material, and many books that cover algorithms not in Knuth's text. However, there are such amazing gems of knowledge in this work that it would be a shame to miss out. I'm sure that many people keep this set on their shelves for some sort of bragging rights, but I often leaf through sections for both inspiration and for entertainment.

You don't _need_ to read TAoCP, but it is a refreshing read. To get the most out of the text, you will need to have a pretty good understanding of mathematics, and you will need to be willing to work out the things he describes on your own. It's not a passive reading experience, like reading most fluffy books found in the "computers" section of the average bookstore or library. It is an active experience, like reading a mathematics textbook. There will be parts that challenge your conceptions, and there will be parts that will take several attempts to fully understand. Then come the exercises, some of which are still open problems in Computer Science.

It is a worthy endeavor. I recommend it.


TAOCP is not to learn programming or to cover everything modern. It is for the intellectual exercise, for widening the mind. And that is where its beauty lies.


> So for those who are practical programmers and have gone down the Knuth TAOCP rabbit hole

There's the rub. TAOCP is Computer Science. "Practical programmers" aren't even engineers. So yes. The books for your intended purpose aren't worth anything.

It will have worth when you are writing something 'serious' like compilers, kernels, or complicated games. CRUD apps, nah.


I don't know if it's intended, but I picked up a whiff of condescension from this comment.

I think it's worthy of celebration that the field has come so far that we can have such a thing as "practical programmers" who achieve very significant things in their respective business fields, without having to know much if any theoretical computer science at all.

Slight hyperbole: the CRUD app is basically the indoor sanitation of this century.

This is facilitated by lots of brilliant people who DID read and understand TAoCP (or equivalent), and it's a credit to their brilliance that so many get so much done without reading it.


Donald Knuth is actually a great writer and teacher. Try Concrete Mathematics instead of TAOCP, it is a shorter and easier introduction: http://amzn.com/0201558025.

It is humorous and it includes notes from past students in the margin. I really enjoyed it.

Shameless plug: I wrote an illustrated book on algorithms that aims to be an easier read than TAOCP, CLRS and others: http://amzn.com/1617292230.


Not available yet.


The first chapter is here: https://manning-content.s3.amazonaws.com/download/4/b78a5a1-...

(not the final formatting)


I prefer the Sedgewick illustrations. Yours are targetting kids and is too verbose.


It is more a reference work than anything else.

> For all its focus on algorithmic performance I found no mention of pipeline stalls, designing for cache performance, branch prediction, multithreading, etc. which are all very fundamental aspects of good performance on modern hardware

Yes, but pure computer science is not worried about that (maybe about multithreading)

But yeah, for a more practical/specific work there are better options (but it's going to be specific to an area)


> Yes, but pure computer science is not worried about that

He writes in that made up assembly language specifically to consider efficiency and implementation concerns:

"Expressing basic methods like algorithms for sorting and searching in machine language makes it possible to carry out meaningful studies of the effects of cache and RAM size and other hardware characteristics (memory speed, pipelining, multiple issue, lookaside buffers, the size of cache blocks, etc.) when comparing different schemes."

Whether he achieves that is another matter.


Indeed, it's a reference work. I've read through the first volume cover to cover, but that's probably not the best way to use TAOCP. When you're interested in a particular algorithm or topic, go find it and read that section.

If you're interested in modern architecture details, I'd recommend Agner Fog's marvelous reference books (http://www.agner.org/optimize/).


TAOCP is very much worth reading, but it does emphasize the "science" part of "computer science". That's not 1960s minutiae, either, that's just academic rigor.

TAOCP creates challenges for many readers, because it does address most problems with an enormous amount of depth and breadth (but at the same time, offers a pretty exhaustive treatment of many topics) and requires a level of mathematics that may be daunting for beginners.

If you want a more accessible text in the same vein, you may want to give Mehlhorn's and Sanders' "Algorithms and Data Structures: The Basic Toolbox" a whirl, as it is freely available online [1]. It is a text aimed specifically at undergraduates and isn't as ambitious as TAOCP, but it still is something that may require a fair amount of effort to follow.

[1] https://people.mpi-inf.mpg.de/~mehlhorn/ftp/Mehlhorn-Sanders...


The older editions of "Sorting and Searching" contained a lot of information on efficiently reading and writing to sequential storage devices [tape]. Don't know about the current edition. [1] That said, "Combinatorial Algorithms" is all about efficiency that is relevant today. Combinatorial problems are the sort of thing where good algorithms stomp caching, branch prediction etc. because the fundamental problems are in NP and NP/32 is still NP.

Knuth has spent 50 years creating computer science that we can take for granted. But in the end TAoCP is a "little book on compilers" and if that's not relevant to one's vocation and the topic isn't intellectually interesting in and of itself then it's probably not the right book for a person.

Knuth always reminds me how hard this stuff really is.

Good luck.

[1]: edit. The First Edition has a centerfold showing the sequences of different society's executions across multiple tape drives.


I use TAOCP on a regular basis where I work, I started writing DSLs for industrial systems then learned from TAOCP how to optimize memory of these embedded systems. We leaf through the pages whenever we can and always find something relevant to what we're working on. We also used just a few LOC for hand rolled Knuth in a customer app field engineers use to quickly find documentation that is so fast and accurate we get offers to buy it. As a result these corps all keep their ancient embedded systems that would cost multi millions to replace as we keep making them faster and more reliable.

Knuth is also a fan of abstracted programming languages like Literate programming which he claims without it he wouldn't have been able to create a lot of the exercises in recent TAOCP volumes so anybody declaring that if you're "just" a Java programmer you won't get any use out of the books are likely incorrect.


Many years ago, I purchased TA0CP because I was stuck. I simply could not get a tiny 8-bit microcontroller to linearly search a lengthy data array in real time. I found the solution in the preface of the work! Simply put the value that you are looking for at the end. That way, you can eliminate checking for the end of the array in the search loop. So, at least for me, I got mymoney's worth after a couple of pages.


There's always been a divide between algorithm design and analysis (covered in TAOCP and most algorithm books), and hardware implementation details like pipeline stalls, cache performance, and branch prediction.

That doesn't mean the algorithm books are useless, it means they give you a bunch of options, and you have to decide which algorithms and data structures will perform best on the specific hardware you're using.

But, at the same time, TAOCP is terrible as a practical algorithms book. It's perfect for graduate level algorithms classes deep diving into mathematical proofs and analyses, but for practical, "real life" coverage I prefer Skiena's "Algorithm Design Manual."


It's a good reference, but I could never read it straight thru. I tried and failed a few times.

There is a note from Bill Gates in the back that says if you can read it all and understand it, contact him for a job.

Edit: read the comment by @geff82 in this thread. This is perfect.


Some people read it cover to cover, and the few I know also happen to be the best computer scientists I know of. It is hard to come by a comparable compilation of best algorithms in one place, so I occasionally have to refer to it. I wouldn't think of reading all of it, because I don't think I have the time, but it is a page turner if you are into algorithms.


I am an academic, so slightly offtopic from the original post, but still may be relevant. I think TAOCP is probably not worth reading cover to cover for even academics let alone practical programmers, but definitely having it by your side for reference.

The important thing that distinguishes the book is this: the attention to detail. Knuth is one who famously shuns email to "get to the bottom of things", rather than stay "on top of things".

I am trying to get into an area called pseudorandomness, and Knuth vol 2. 3rd edition has an excellent treatment of the subject in all its incarnations. The details that are in the book beat even the original research articles where the results first came in. So I refer to Knuth first to see if it is there, and then go to the research articles!

Bottom Line: To get the details correct, trust Knuth, rather than a random blog article on the web on the same topic.


TAOCP is a fundamental work teaching fundamental techniques. If you can master it, pipeline stalls, designing for cache performance, branch prediction, multi-threading, etc., are easily understood problems and you have the tools to then attack most any other computational problems that are likely to come along.

Sounds like what you want is a prescriptive tutorial addressing a set of specific computing problems. That's not what TAOCP is.


When I'm bored I pick a random section and read it. I was really fascinated by the section on sorting networks for example.

The real gems are the exercises and answers to them; there's at least as much useful/applicable stuff as in the main text. I tried to solve them, but found myself unable to proceed with them if difficulty was > 20, even if I understood the concepts. I have no idea on how to attack them. (Even non-mathematical ones.)

IMHO, TAOCP needs "Volume 0" which would teach you problem solving in this particular domain. (No, "Concrete mathematics" is not it. That book is, IMHO, awful: many problems depend on having tricks up your sleeve.)

Any tips on how to approach exercises which seemingly don't have a lot to do with the preceding text?


I liked it a lot. I read all three books but only did a small fraction of the exercises. I had read quite a few easier algorithms books, but had never seen a good treatment of less trendy things like external sorting algorithms or random number generators. I really like Knuth's writing. Of course the drawbacks are that the books don't have recent algorithms, and you have to deal with MIX assembly rather than your favorite language.

They are not easy books. At the time I read them, I had a 45-minute bus commute each way, which gave me a nice forced reading window. I don't know if I'd make it through them today, without public transportation. Too many more entertaining things to read or do at home.


No offense, but you really should have done some research before you plunked down the cash... its exactly what you say it it is a foundation computer science book. literally.


Apocryphal story: http://www.folklore.org/StoryView.py?story=Close_Encounters_...


Knuth's books are a baseline for "how things are done" for many, many areas, so having read them lets you hit par on most holes. Optimizing code for an architecture is very interesting, but it comes after 1) figuring out which ways the math can be stated correctly and 2) calculating the order of computation. Then architecture gives numbers to put into the order of computation. Knuth focuses on the first two, but maybe a few books' worth of focusing on those is understanding them well and not such a waste.


A theme that runs through some of the comments here is that TAOCP is not worth reading straight throught, but it makes a good reference work. In the last 10 years, I've used it as a reference exactly once, when I peeked into Vol 1 on semi-numerical algos. I found it as well-written as I remembered, but requiring heavy slogging to find out one detail. Ultimately, I found what I needed online. I would argue that great as TAOCP is, it's rarely going to serve many needs even as a reference.


So long as you don't spill coffee on it, you can always resell it.

I got a set when a coworker jumped ship with no forwarding address and left all his books. It seems useful for people implementing languages and standard libraries, less useful for people using them.


>TAOCP worth the time and effort?

Early in my career, I got the first three volumes.

The volume on sorting and searching was the most useful, and there the most useful was AVL trees. Next, heap sort and the Gleason bound. Sort-merge? I'd known that already, but if don't then can learn it there. Radix sort? That's what the old punched card machines did; in some cases it's faster than heap sort (doesn't contradict the Gleason bound because that bound assumes that the sorting is from comparing pars, and radix sort doesn't do that). Radix sort could be still be useful in special cases. Lists, queues? Obvious.

The fast Fourier transform remains important, and some of what Knuth writes about it is good and tough to find elsewhere.

Somewhere in those first three volumes are some really good summaries of combinatorial formulas, with some results not easy to find elsewhere.

The volumes give some good examples of how to do the math to evaluate the performance of an algorithm -- might need to do that sometime, e.g., for some guaranteed performance in some embedded system -- and if need to do that then it's far easier to read at least the start on how from Knuth than reinvent it yourself and likely easier than from other sources.

The level of clarity, precision, and quality in Knuth is about as high as those go and a great example for others.

That's most of what I got from those three volumes.

For the later volumes, right, I didn't bother. But, if I have a question that might have an answer in one of those volumes, then, sure, I will eagerly look.


I wouldn't necessarily read it cover to cover. I did that with volume 1 and found it interesting, but I could have done without the assembly implementations. Assembly is highly dependent on the hardware capabilities. It feels to me like C or some other close to the metal language would have been more useful.

I keep volumes 1 and 2 on my desk in case I ever need to refer to them for information about a specific topic, but I have yet to actually open them.


I sometimes think of Computer Science (in the classical theoretical sense---and Knuth is a towering figure in that domain) as having a similar relationship with programming as that of Mathematics to Engineering. A basic foundation in the theoretical background is very helpful, possibly essential, to professional work, but a deep understanding of theory is unnecessary. That said, those engineers that have a deeper mathematical foundation can realize important benefits to the quality of their work. Similarly, a rich immersion in abstract computer science is not necessary to programming, but its presence can be of great value. Being aware that a given programming problem maps to a well-understood class of algorithms with known performance and correctness enables elegant solutions.


I should note that, while TAOCP is absurdly important in CompSci, it's probably not a good starting point. I'd recommend Corman's book on algorithms first, and maybe getting your feet wet with Knuth's Concrete Mathematics ( if only as a more gentle introduction to his style).


I've read the first volume. I do not have a math-heavy background. Knuth's dry humor is great. The scope and effort put into the books are astounding.

I did not learn much of practical use for my day-to-day programming. Sadly, I will probably never read the other two volumes in my boxed set. They look great on the shelf.

The MIX assembly language was my least favorite aspect of the book - and I ENJOY creating and tinkering with toy virtual machines.

MMIX (MIX's modern RISC successor) will probably be a lot nicer.

Perhaps assembly languages are essential to demonstrate the concepts properly. And I understand the arguments against using a popular low-level language such as C. But it sure would have been nice to have a simple and readable pseudo-language for the examples rather than MIX!


TAOCP is like a math book, and you were hoping it will make you a better experimental physicists. :)


>>was it worth it?

You are not supposed to read about any algorithm. There is nothing special about knowing how some sorting algorithm works, or any algorithm for that matter. That knowledge is no better than knowing how some war in history happened. Or remembering arcane trivial about things. Knowing how to sort a list a dozen ways, no big deal. Unless you discovered the algorithms yourself, there is nothing special about just knowing how these things work.

You are supposed to learn how to discover your own algorithms, reasoning from the first principles, learning the axioms that govern the area of the problem, learn the rules, then work out step by the step, deriving new results from the results discovered a step back.

You are supposed to learn how to reason about the problem. You are supposed to learn to understand the problem, state it in simple terms, learn to draw diagrams to represent it, solve sub problems. Build theories, hypothesis, question them, prove them etc.

We don't do algorithm studies the right way.

Even software interviews are not testing algorithm skills, they are testing algorithm memorization skills. Nothing different than those teachers who used to confuse memorizing multiplication tables with genius.


"You are not supposed to..." in general I agree that we should take first principles based approach always as an option - from point of view of taking intellectual pride in ones work.

However, a large category of real world problems is solvable only through a combination of solutions to hard problems.

If I have to solve three hard problems before I can have a complete solution is at hand - and by hard I mean months of work - my memory is so poor that the current value of a solved problem does not depend on whether I or someone elso solved it. I've forgotten the details anyway - and the only thing I have are the implementation and documentation.

I have a limited lifespan but the number of interesting problems is infinite.

I can't really find a calculus that says it's far more valuable to solve the known problems several times rather than new interesting problems.

Because that's what you are implying (with my memory) - if never using existing solutions is preferable I would never get anything done.

The same applies for most of civilizations activities.

Don't confuse practicality as the opposite of love of knowledge.


It virtually all programming, even in stuff with tight performance constraints and high performance demands you are utilizing known and studied algorithms.


My company bought the books for me. Everyone was able to order books for the value of around 100 euros, and I ordered TAOCP because it is almost timeless and it will be valid for long time. I never buy programming books (books like "learn XYZ in XYZ days") in paper because they get outdated so fast, but getting TAOCP practically for free, I did not give it a second thought..


Is OED worth the time and effort?


I got a used set for $6 and I felt that was a good investment.


I've got a mixed edition used set. More hours of entertainment than I'll ever get to.


Not really. There are a few gems here and there in the text, but overall it is a slog. CLRS is a better text book for getting up to speed in algorithms. If you are going to read it though, the volume on searching and sorting is probably the best. I didn't much like volume 1.


I haven't read TAOCP, but for those things you mentioned, Computer Systems a Programmer's Perspective is great, especially if you're thinking the way you seem to be about how you can exploit these things rather than how they work in depth.


it's worth reading just for one of the best book in-jokes ever - see the introductory part "Notes on the Exercises" of Volume 2 "Seminumerical Algorithms"

3. [M50] Prove that when n is an integer, n > 2, the equation xn + yn = zn has no solution in positive integers x, y, z.

Knuth's book was published in 1973. The initial solution to this exercise was solved by a then Princeton professor in 1993 and was finalized by same professor and his former student by 1995.


If I recall correctly, newer editions of the book has lowered the difficulty of this (M49?) as it has been solved.


It's kinda important to note here that the "M50" designation indicates that the excercise is an "unsolved research problem". It's not an in-joke; Knuth is presenting unsolved problems with the intention that the student would consider trying solving them.


btw, if you didn't find an in-joke [1] funny [2][3][4][5] then it's probably because of a very good reason :)

Knuth himself found it funny [6]

[1] https://en.wikipedia.org/wiki/In-joke

[2] https://groups.google.com/forum/#!topic/alt.folklore.compute...

[3] https://www.reddit.com/r/ProgrammerHumor/comments/38gt65/was...

[4] http://texthook.com/blog/2013/07/01/reading-knuth/

[5] http://tal.forum2.org/story_45

[6] http://www.tug.org/TUGboat/Articles/tb17-1/tb50knut.pdf (page 10)


An hour or two of reading is too short to draw any conclusions here. Choose something in the books that looks interesting to you (not necessarily in the earlier chapters) then spend a week or two working through it, and _then_ decide if it is worth it or not.

I suspect that for most of us TAOCP is a rich red wine that we would sip from occasionally to get that feeling of "aha, so that's what red wine should taste like!"


A good portion of my undergrad CS program used excerpts from TAOCP. So yeah - there's good stuff in there, but maybe it wasn't what you personally wanted. If you've been in industry for a long time, then sure - you've probably developed expertise in areas that TAOCP doesn't cover. But if you are looking for a rigorous, broad, academic base then it is pretty solid.


Appreciate all the feedback and discussion, been sneaking peeks at the comments throughout the day - I'm still within the time window to return the boxed set thankfully, and haven't spilled coffee on them yet, so I'll probably go that route. Some of the other resources people have suggested sound like they'd be a better use of my study time.


Really the book series should be called the Art of Computer Science. It is basically my entire degree wrapped up in 3 books, it will not teach you how to program, just as a computer science degree will not teach you how to program, but it is an intensely interesting series of books if Computer Science is what you're into.


Try out the Competitive Programming book - http://cpbook.net

In a lot of ways, it is a faster and much more practical way to learn how to think about algorithms and data structures quickly and code them fast.


It was worth the 25 euro's my dad spent on them i guess (bday gift it was on sale). just to look at it sometimes and i even read some stuff. but its hard. if you want to learn something for real pick any other book.


I have TAOCP in my bookshelf. It's actually my second set of books since the first set was stolen from my work-place. I also have other books I haven't read.


There is an argument that it hasn't aged well and that with the advances of programming language design, libraries and hardware it is more of a historical look at the early days of programming. I disagree though as it gives the budding programmer a good foundation. I would also suggest SICP books/lectures. Also learn to program Visual Basic in 5 hours :-p


Do you need to people to tell you what to do?

Asking other's advice is as stupid as judging a book by its cover.

If you have studied a tad, or read books in the past, there are ways to efficiently evaluate a book:

Read some pages randomly. Think 30s if you liked it. TAOCP is indigest for sure.

Then take a topic for which its relevant. Read it. Did you learnt something?

A) no, either you or him is an idiot. Go to B)

B) Was it luck? Reproduce nth time (n being left to your choice and whatever)

C) after nth iterations : - is something interesting worth learning? - can you understand the book (don't lie to yourself)? - do you like reading it?

Then look at the tag price. You look at your internal evaluation and buy or not the book according to your needs.

I liked reading part of this book, and i grasped the underlying context fast enough to be so bored (trying to build a consistent mapping between algebrae and code) that I never opened it again.

In microelectronic you learn to draw your logic on Silicium and wire the logic... It is much more powerful and is one of the key concept of parallelism. Geometric approach.

But, this is my subjective opinion of the book. Talent comes with strong balance between opinions and curiosity.

If you want to understand better computers I would suggest to take a look at VHDL rather than TAOCP ... if it SUITS you.

You should be the master in your choices.


> Do you need to people to tell you what to do?

No but if I want advice on building a wall and I'm not a builder I might ask one.

If I want advice on how to make bread I'd ask a baker.

There is nothing wrong with asking more knowledgeable people for advice, in fact the inverse, I've learnt skills in my life the brute force way by trial and error where just been able to ask someone who'd done it for advice would have saved me a whole bunch of time.


The two easiest ways to learn how to solve a problem: looking at a system that does exactly what you want and copying it shamelessly, and asking someone who has already done what you're trying to do how they did it.


Funny how you tell him he doesn't need other people to tell him what to do, and then you tell him what to do :)


I give him a methodology that seems to have been lacking in his education. Not the conclusion he should reach.

Maybe because I have a lutherian culture based on the belief that critical reading is the only way to improve the world and avoid the ravage of superstition? (Yes, the first act of faith of a lutherian is read the bible with a critical eye and refusing the interpretation of experts (called authority), but to accept discussion of other critical open readers on an equal foot based on experience).

Maybe I come from a family that knows better than none the effect of people the importance of books as long as they are read critically. Maybe, because my family is on the run since 4 centuries from various places/religions/situations around the world.

Monoculture is bad. Consensus is dangerous.

Basically I resent bigots from all schools of thinking.


Not really. The books are terribly outdated. There are far better books in each subject area. Pick up a book on a specific topic you want to learn about instead.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: