[HN Gopher] Knuth's Art of Computer Programming, V 4B, has gone ...
___________________________________________________________________
Knuth's Art of Computer Programming, V 4B, has gone into print
Author : inetsee
Score : 551 points
Date : 2022-10-04 15:49 UTC (7 hours ago)
(HTM) web link (www-cs-faculty.stanford.edu)
(TXT) w3m dump (www-cs-faculty.stanford.edu)
| Pet_Ant wrote:
| Who will finish the book when he is gone? This is too important a
| work to not finish.
| AlbertCory wrote:
| 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.
| linguae wrote:
| 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.
| AlbertCory wrote:
| I was there, too. Didn't see Knuth, though.
| f1shy wrote:
| I learned about the TAOCP in 2008 or even earlier. At that time,
| I already thought, I will not be able to have the first 4 Volumes
| complete.
|
| Is there any hope that somebody will continue the work?
| varjag wrote:
| Seeing the photo of Knuth picking cotton in Uzbekistan, my ex-
| Soviet citizen's first thought was "now what they did pack him
| for".
| O__________O wrote:
| 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?
|
| ___________
|
| [1] https://news.ycombinator.com/item?id=33066313
|
| - specifically:
| https://youtube.com/watch?v=IoXiXlCNoXg&list=PL590L5WQmH8dsx...
|
| [2] https://wikipedia.org/wiki/Knuth_reward_check
| eesmith wrote:
| FWIW, here's a side-ways mention of Knuth's bounty, from
| http://ed-thelen.org/comp-hist/B5000-AlgolRWaychoff.html
|
| > 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.
| macintux wrote:
| Thanks, there are a lot of gems in that piece.
| IncRnd wrote:
| 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.
| PeterStuer wrote:
| Just picked up a near pristine vol.1 first edition in a uni
| library selloff. Wonder how they got a copy so unread after all
| these years.
| bombcar wrote:
| 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.
| sitzkrieg wrote:
| well it is simple, as the countless comments above attest to:
| very few people actually read the tomes.
|
| but hey maybe impressive no damage from being lugged around
| between check outs :)
| ColinWright wrote:
| A copy personally autographed by Knuth will be up for auction in
| the Gathering For Gardner fund raiser.
|
| * The Art of Computer Programming, Volume 4B: Combinatorial
| Algorithms, Part 2
|
| * https://www.amazon.com/Art-Computer-Programming-Combinatoria...
| the-printer wrote:
| 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.
|
| Am I far off?
| kragen wrote:
| What's hilarious or intriguing about it? Is it just that you're
| not familiar with the practice of publishing things in
| fascicles?
| the-printer wrote:
| 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.
|
| Tantalizing.
| bombcar wrote:
| 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.
| the-printer wrote:
| Thanks for this. It's fascinating, truly.
| f1shy wrote:
| Not only TeX, also Metafont, because we was not satisfied
| with available computer types.
| bonzini wrote:
| And designing the Computer Modern font, which is
| certainly not the most artistic or beautiful but still in
| use and more than decent.
| Bayko wrote:
| 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
| Labo333 wrote:
| 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.
| lupire wrote:
| Knuth's chapters are mostly decades old. I don't think they
| are near the boundaries of research. (except the starting
| boundaries.)
| kieckerjan wrote:
| 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.
| lupire wrote:
| 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.)
| bcwarner wrote:
| 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.
| lupire wrote:
| Shouldn't TA jobs be handed out based on you knowledge and
| teaching and management ability, not fashion prejudice?
| nottorp wrote:
| > found them useful ON TGE JOB?
|
| Algorithm training is useful on most jobs for preventing you
| from going accidentally quadratic.
| wollsmoth wrote:
| I bought volume 1, figuring if I actually worked up the
| gumption to finish it I'd continue from there. It looks very
| nice on my bookshelf.
| commandlinefan wrote:
| > 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.
| lifefeed wrote:
| 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.
| disgruntledphd2 wrote:
| 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.
| dragontamer wrote:
| 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.
|
| Even if you never, ever, ever will program F1.
| elcapitan wrote:
| 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.
| lupire wrote:
| Fun is fun, but if you want help with Leetcode, something
| like CLR(S) is more helpful.
| linschn wrote:
| 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.
| bombcar wrote:
| 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.
| lupire wrote:
| There is quite a lot of money waiting for you if you ever
| figure out how to factor composites quickly. (Any old bum can
| factor primes quickly.)
| linschn wrote:
| 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.
| hardwaregeek wrote:
| 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.
| daoist_shaman wrote:
| It's something nice to put on the shelf and fantasize about
| enjoying, one day, when there's time.
| dyingkneepad wrote:
| 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.
| lupire wrote:
| TAOCP is far far more than the basics.
| treffer wrote:
| 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.
| deltasepsilon wrote:
| 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.
| wing-_-nuts wrote:
| >It just means you're not doing anything interesting on your
| job.
|
| That man had a family...
| bombcar wrote:
| The vast, vast majority of us may be doing _difficult_
| work, maybe even _necessary_ work, but much of it is not
| really that _interesting_.
|
| It's good to remind myself that I'm basically a plumber for
| the internet tubes.
| dc-programmer wrote:
| 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
| lupire wrote:
| The book is a nice way to give you a hint about what exists
| and what stuff is called. From there you can search for
| more.
|
| Of course other resources exist, many of which cite TAOCP
| or are derived from it
| martincmartin wrote:
| I once used them at work. I had a monitor that was too low, so
| putting a volume or two of Knuth under it raised it to the
| right height.
|
| That's the only time I've ever used them though.
| giantg2 wrote:
| Quite expensive for that use.
| jahewson wrote:
| And yet significantly cheaper than Apple's Pro Stand.
| jonnycomputer wrote:
| funniest comment of the day.
| leoc wrote:
| And more prestigious to boot.
| randcraw wrote:
| 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...
| giantg2 wrote:
| 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.
| toast0 wrote:
| 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.
| kragen wrote:
| 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.
| openfuture wrote:
| The world changes through the collective effort of the people
| who inhabit it. Not because some demigod wrote a script.
| kragen wrote:
| 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.
| bo1024 wrote:
| The one can be a special case of the other...
| dyingkneepad wrote:
| 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.
| lupire wrote:
| Luckily, you are more than a few hours from death.
| klik99 wrote:
| 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.
| slavapestov wrote:
| 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!
| lupire wrote:
| A great book is to be pored over with a pour-over.
| thomasahle wrote:
| As an algorithms researcher, I have often been reading Knuth on
| the job.
|
| Most of the time, perspiring with worry that a 1960s article
| might have scooped me.
| kramarao wrote:
| 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.
| lupire wrote:
| This is also why MIT switched its intro to CS class from
| Scheme to Python ~15 years ago.
| [deleted]
| lupire wrote:
| Do you normally expect to read encyclopedias for your job?
| jseutter wrote:
| 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.
| kragen wrote:
| It may not be a coincidence that one of the author's other
| books is on Biblical studies: https://www-cs-
| faculty.stanford.edu/~knuth/316.html
|
| I didn't realize it had been blurbed by a professor emeritus
| at a seminary (as well as Martin Gardner).
| Tomte wrote:
| My take on it: https://www.2uo.de/Books/316-bible-texts-
| illuminated/
| kragen wrote:
| 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",
| "donAt" for "don't", "WHat" for "What", and
| "theologician" for "theologian".
| GuB-42 wrote:
| That's a $15.36 comment
| birdyrooster wrote:
| I lolled at theologician
| bombcar wrote:
| Theologician sounds like a perfectly cromulent word, we
| should establish a doctorate in it immediately.
| Tomte wrote:
| Thank you!
| irrational wrote:
| "redaing" for "reading"
| radicalbyte wrote:
| 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).
|
| Glad to know that the problem isn't totally me :)
| rented_mule wrote:
| TAOCP was invaluable for a couple of jobs I had.
|
| 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.
| todd8 wrote:
| 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.
| Tomis02 wrote:
| 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.
| secondcoming wrote:
| 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.
| bugfix-66 wrote:
| 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):
|
| https://bugfix-66.com/fdb8bb4fa84cf810aa25ff40c88a13c1874410...
|
| From Volume 3, here is by far the fastest method of sorting
| integers (Singleton's method), an algorithm I have used
| professionally several times (e.g., for beam search in a speech
| decoder):
|
| https://bugfix-66.com/834f0677c85b23c0bf1047d3654ab7c27ff054...
|
| Knuth's books are just packed with gems like that.
|
| The meticulous high quality of the books is also remarkable.
| However, if you look very carefully you can find rare mistakes.
| I received payment from Knuth and have an account at his bank:
|
| https://www-cs-faculty.stanford.edu/~knuth/boss.html
|
| Getting your name on the above list was once a Hacker rite of
| passage.
| Tomte wrote:
| > However, if you look very carefully you can find mistakes.
|
| Opened the book, thought "no, it can't be". Agonized for days
| and weeks if I'm making a fool of myself.
|
| Sent the bug report.
|
| First word in first sentence in first paragraph in first
| chapter was wrong. Got my cheque. ;-)
| mkehrt wrote:
| What was it?!
| Tomte wrote:
| "Infinitely many alphabets can be generated by the
| programs in this book".
|
| But the number of parameters is finite, and all
| parameters have a finite number of possible values.
|
| His errata changed the wording thus:
|
| Zillions of alphabets can be generated by the programs in
| this book. (https://ftp.rrze.uni-
| erlangen.de/ctan/systems/knuth/dist/err...)
| dalke wrote:
| 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.
|
| I have a check.
| desio wrote:
| Incredible.
| Brystephor wrote:
| 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.
| jjice wrote:
| 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.
| falcrist wrote:
| Decades.
|
| It looks like he started working on it in 1962.
|
| Just imagine being that intelligent and pouring 60 years of
| your life into something like this.
| rusk wrote:
| Sounds blissful
| melling wrote:
| The origins of TeX from Knuth himself:
|
| https://youtu.be/9IM_dqjBkIw
|
| His books were the reason he started TeX.
| carl_dr wrote:
| > I'm interested to see how the series progresses for the next
| 30 years.
|
| Donald is 84. And each time I'm reminded of that I get sad,
| it's very unlikely we'll get another 30 years of his work.
| javajosh wrote:
| He's already well over the avg life expectancy for American
| men. But hey, good genes exist and it's possible he's got
| another 20 lucid years.
| melling wrote:
| The average age is from birth. What's the expected age
| having lived to be 84?
|
| People can live well into their 90's. Hopefully he's got
| another book in him. These people are still alive, for
| example:
|
| Jimmy Carter: 98
|
| Henry Kissinger: 99
|
| Warren Buffet: 92
|
| Charlie Munger: 98
|
| Mel Brooks: 96
|
| Alan Greenspan: 96
|
| Noam Chomsky: 94 in December
| Tortoise wrote:
| Unfortunately, for an American man at age 84 he would only be
| expected to live (on average) another 6.44 years. See:
|
| https://www.ssa.gov/oact/STATS/table4c6.html
| [deleted]
| uptownfunk wrote:
| 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.
| uptownfunk wrote:
| And how to understand the programming language used?
| Jtsummers wrote:
| https://www-cs-faculty.stanford.edu/~knuth/mmixware.html -
| _MMIXware_ by Knuth introduces the updated assembly.
|
| https://www.mmix.cs.hm.edu/supplement/index.html - _The MMIX
| Supplement_ by Ruckert
|
| The first introduces the updated assembly language, the
| second updates all the MIX programs from Volumes 1-3 to MMIX.
| f1shy wrote:
| That would be "the hobbit" ? :)
| leoc wrote:
| _Concrete Mathematics_ is basically an expanded version of the
| mathematical content of Volume 1, apparently. Not that it's a
| doddle either.
| dboreham wrote:
| Possibly the last physical book I will buy.
| eddof13 wrote:
| I don't want Knuth to Robert Jordan/George RR Martin himself so
| I'm waiting for vol 5 to complete before purchasing the set
| llaolleh wrote:
| Imagine if we got an HBO adaptation of TAOCP.
| sophacles wrote:
| 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.
| jcl wrote:
| No doubt it would be filled with gratuitous union-finding
| that wasn't present in the original.
| gs17 wrote:
| 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).
| jcranmer wrote:
| 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"
| Decabytes wrote:
| 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.
| dragontamer wrote:
| 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.
| boonsuan wrote:
| have you read his current draft of fascicle 7a (7.2.2.3
| Constraint Satisfaction)? it is currently 145 pages and is
| available at https://cs.stanford.edu/~knuth/fasc7a.ps.gz
| dragontamer wrote:
| 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.
| g9yuayon wrote:
| 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.
| azalemeth wrote:
| 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.
|
| (And if anyone wants to do the quiz, it's here: [1] https://www-
| cs-faculty.stanford.edu/~knuth/paradox.pdf)
| aamargulies wrote:
| 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.
| boonsuan wrote:
| very amusingly, the entire 700+ page volume covers only Sections
| 7.2.2.1 and 7.2.2.2 of _The Art_.
|
| _The lyf so short, the craft so long to lerne_
| c1ccccc1 wrote:
| Reminds me of this story:
| https://slatestarcodex.com/2017/11/09/ars-longa-vita-brevis/
| [deleted]
| cromwellian wrote:
| 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.
| pksebben wrote:
| may we all age so gracefully. perhaps part of the secret is to
| work like Don.
| coreyp_1 wrote:
| 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.
| voakbasda wrote:
| 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.
| jsmith45 wrote:
| 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.
| lifthrasiir wrote:
| 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?
|
| [1] https://www-cs-faculty.stanford.edu/~knuth/taocp.html
| klik99 wrote:
| 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.
| helsinkiandrew wrote:
| Each volume is taking longer and longer (4A and 4B and work on
| 4C have taken over 20 years). Mr Knuth is 84 and if there are 3
| more volumes...
| irrational wrote:
| Maybe Brandon Sanderson can write the last three books.
| ok_dad wrote:
| 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_.
|
| [0]: https://en.wikipedia.org/wiki/The_Wheel_of_Time
| krull10 wrote:
| Well played
| openfuture wrote:
| tmtvl wrote:
| Never heard of him, is he another great computer scientist?
|
| I'd love it if someone like Chris Wellons or Per Bothner
| could work on them, but filling Knuth's shoes may be a big
| task for one man.
| thfuran wrote:
| No, he's a fantasy author who finished the last few
| volumes of a popular epic fantasy series after its
| original author died.
| imaltont wrote:
| Also convinced he writes in his sleep with the amount of
| books he releases.
| aaroninsf wrote:
| https://www.theverge.com/c/23194235/ai-fiction-writing-
| amazo...
| ars wrote:
| He got a little bored during COVID and accidentally wrote
| 5 books: https://youtu.be/6a-k6eaT-jQ this led to what I
| think is the most funded Kickstarter ever: https://www.ki
| ckstarter.com/projects/dragonsteel/surprise-fo...
| jrop wrote:
| Journey before destination
| noyesno wrote:
| Bookbinding is a great hobby. Or you can commission someone to
| create leather-bound covers for your book?
| bombcar wrote:
| Yes - you can find book rebinders who can take a paperback
| book and make a bound book out of it.
| WillAdams wrote:
| R.A. MacAvoy has the titular character do this in her wonderful
| novel _Tea with the Black Dragon_
| amelius wrote:
| Still hoping for a next edition of his "Searching and Sorting"
| volume, to include modern search engines.
| user3939382 wrote:
| 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.
| hguant wrote:
| Churchill's Second World War books are an incredibly easy read
| for how information dense they are, as is his "History Of the
| English Speaking People."
| [deleted]
| bombcar wrote:
| The Summa Theologica is actually relatively easy to read,
| especially if you have some background in it and a good
| translation.
|
| Since it's divided into sections, you can poke it before bed
| now and then. You don't even have to buy it: https://aquinas.cc
| WhitneyLand wrote:
| 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.
| rietta wrote:
| 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.
| moron4hire wrote:
| 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.
| lupire wrote:
| You read a math book slowly, so you don't need whitespace for
| help skimming. Extra whitespace would make the huge books
| even huger.
|
| Beautiful formatting here refers to the _text_ , not the
| whitespace.
| moron4hire wrote:
| 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.
|
| https://twitter.com/Sean_McBeth/status/1577388169418383363
|
| Adding whitespace doesn't have to make the book _longer_.
| It could just make the book _wider_. Besides, paper is
| cheap.
|
| https://twitter.com/Sean_McBeth/status/1577388234589478914
| andrepd wrote:
| Subjectively, I like TAoCP's typography much better. But
| hey, that's just me.
| fragmede wrote:
| Paper's having supply chain issues, same as everything
| else. https://www.npr.org/2021/10/04/1043145212/supply-
| chain-issue...
| commandlinefan wrote:
| > 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.
| svat wrote:
| 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).
| dirtsoc wrote:
| Acceptance is the first step on the road to recovery.
| krylon wrote:
| 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.
| WillAdams wrote:
| The story is related at:
|
| https://www.folklore.org/StoryView.py?project=Macintosh&stor.
| ..
|
| but probably didn't happen that way.
| davidrupp wrote:
| 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."
| radicalbyte wrote:
| 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 :-)
| leereeves wrote:
| I use it more like a dictionary. I don't read it from start
| to finish, but if I need an algorithm for something, I look
| it up in Knuth.
| jpgvm wrote:
| 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.
| Q6T46nT668w6i3m wrote:
| 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!
| lupire wrote:
| That's not really what Concrete Mathematics is about. It's
| not a prereq to TAOCP.
| Jtsummers wrote:
| 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.
| BeetleB wrote:
| Concrete Mathematics has some fairly advanced stuff (e.g.
| asymptotics) which I doubt Khan Academy covers.
| Jtsummers wrote:
| 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.
| Q6T46nT668w6i3m wrote:
| I have no idea! I just used it as an example of
| "educational video on YouTube!" :-)
| moron4hire wrote:
| 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.
| dragontamer wrote:
| 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.
| why-el wrote:
| 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.
| pasquinelli wrote:
| 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.
| jupp0r wrote:
| 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!
| jjice wrote:
| 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.
| synergy20 wrote:
| I too have the whole collection but never read it, they're so
| thick and life is so busy...
| pjmorris wrote:
| 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
| :))
| ChicagoBoy11 wrote:
| 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.
| lupire wrote:
| NKS isn't a new kind of science, but it's not nonsense. It's
| a poorly cited thorough monograph on cellular automata.
| kzrdude wrote:
| I wonder what the second-hand value of that brick is. It's
| the only hope I have for that one.
| svat wrote:
| Note that, to get an idea of the contents, you can see the
| previously published fascicles, and earlier drafts online (pre-
| fascicles):
|
| * Mathematical Preliminaries Redux:
| https://cs.stanford.edu/~knuth/fasc5a.ps.gz
|
| * 7.2.2 Introduction to Backtracking:
| https://cs.stanford.edu/~knuth/fasc5b.ps.gz
|
| * 7.2.2.1 Dancing Links:
| https://cs.stanford.edu/~knuth/fasc5c.ps.gz
|
| * 7.2.2.2 Satisfiability:
| https://cs.stanford.edu/~knuth/fasc6a.ps.gz
|
| 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._
| xwolfi wrote:
| Imagine being this guy at work, writing "thousands of computer
| programs" all unproductive, while being paid for the priviledge
| !
|
| It's probably as interesting as it is for a Christian to read
| the Bible or a Marxist to read The Capital: many dont feel the
| need.
| senko wrote:
| How's that unproductive?
|
| He writes these programs to research things, and then
| publishes an authoritative book on the subject.
| smitty1e wrote:
| For the Christian, reading the Bible is internally
| transformative.
| reidjs wrote:
| 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.
| gameman144 wrote:
| "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).
| aasasd wrote:
| 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
| magicloop wrote:
| 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 ..."
| goldenkey wrote:
| Overqualified or underqualified. Sigh...
___________________________________________________________________
(page generated 2022-10-04 23:00 UTC)