[HN Gopher] Discovering errors in Donald Knuth's TAOCP
___________________________________________________________________
Discovering errors in Donald Knuth's TAOCP
Author : glth
Score : 192 points
Date : 2025-03-08 16:27 UTC (1 days ago)
(HTM) web link (glthr.com)
(TXT) w3m dump (glthr.com)
| WillAdams wrote:
| Nice! When I reported an error and a point of improvement in
| _Digital Typography_ the address was printed and glued on, not
| hand-written, which somewhat detracts from the display of the
| check/envelope.
|
| Need to find another error so I can get an account....
| dmoy wrote:
| This makes me feel less bad about also not being able to figure
| out my printer's address printing function.
|
| Like I know it is capable. I know how to set up the hand feed
| for it (and I successfully do that for thicker paper). And
| ostensibly I know the right dimensions and how to line it up in
| a PDF. But then it's just failure after failure, and I go back
| to cut and paste or handwrite.
| WillAdams wrote:
| Really miss poste.app on my NeXT Cube, which was a small
| app/service which did nothing but print a selected address
| onto a hand-fed envelope.
| nwellnhof wrote:
| The inventor of the bug bounty.
| jgrahamc wrote:
| I have a Knuth cheque from back when he sent out real cheques. Or
| at least I did; for some reason I decided that cashing it was a
| good idea and so I have his note back to me and a photocopy of
| the actual cheque.
| belter wrote:
| What error did you find?
| secondcoming wrote:
| Aren't the cheques for $2.56?
| hinkley wrote:
| Why am I just now having this thought?
|
| He should make them $5.12 so it's a check for 1,000,000,000
| cents, instead of 100,000,000.
| rdlw wrote:
| They're hexadecimal; 100 cents in a dollar.
| cinntaile wrote:
| lol I'm a bit curious about the thought process that led you to
| decide you wanted to cash it.
| tkhattra wrote:
| I have one for $7.68 ($2.56*3). Alas, it was for some minor
| typos and grammatical errors in SPOCS [1], not "real" math
| errors in TAOCP. Never plan on cashing it in though. And I
| can't remember where I stashed it, so there's that too... :)
|
| [1] https://www-cs-faculty.stanford.edu/~knuth/cs.html
| zabzonk wrote:
| A long while back I wrote an answer on Stack Overflow to a
| question that asked "How to read TAOCP?" my answer looked
| something like this:
|
| - don't read them
|
| - get all the books, put them in a bin bag and shake vigorously
| with some lumps of coal, to give them that "used" look
|
| - go through the books, underline things at random and make notes
| (also at random) in the margin such as "how true", or even better
| "wrong!"
|
| - put books on shelf in office - never look at them again
|
| This has worked for me, though I must admit that Searching &
| Sorting and stuff about random numbers are pretty good.
|
| I got my copies free from Addison Wesley for doing some book
| reviews for them - not reviewing Knuth, needless to say!
| WillAdams wrote:
| I have worked with two programmers who had well-thumbed copies
| of TAoCP on their shelves which each had actually read (one was
| the only other person I've met outside of a TeX conference who
| had a reward check) --- to this day, I've not worked with
| better devs.
| dhosek wrote:
| Ah nothing like a DEK post to pull out the old TeX folks on
| HN.
| wglb wrote:
| When I bought the first volume in about 1969, I vowed to read
| that one, and then each one that followed.
|
| However, that is yet to come to pass.
|
| However, when we at Mark Williams Company writing the floating
| point routines for the C compiler
| (https://winworldpc.com/product/mark-williams-letsc/3x), we
| were heavily reading Chapter 4, particularly on long division.
|
| Also did spend some time in the Random Number generation
| chapter.
|
| An interesting difference between my 1965 version and the ones
| published today is that long multi-page foldout in Sorting and
| Searching showing tape-based merge sort is no longer part of
| the book.
| kragen wrote:
| Hey, I have a question about the Mark Williams Company. I
| understand it was founded by Aaron Swartz's father. Did he
| work on the programming? Did Aaron spend time around the
| office? I'm curious how Aaron first got involved in
| programming, which I think was probably long after the
| company.
| wglb wrote:
| Aaron was very young during the Mark Williams years. I
| worked there for six years. I don't think he visited the
| office during its heyday. So yes long after MWC.
| nyrikki wrote:
| I was gifted the new set this last Christmas after losing my
| old versions in a fire, the fold out pages are there in the
| latest release.
|
| Edited to add: Amazon often has fake or at least printed with
| lower quality/cost versions. It was hard to find a real copy
| of his concrete math book when I was searching. The 'i18n'
| edition is printed on the cheapest of cheap paper for that
| book. I suspect that is related. But the fan-out pages are in
| the sorting volume.
|
| #2 Vol 3 is on the second edition, with the tape merge fanout
| between pages 338 and 339. So it would be a particular
| printing that didn't have it.
| polytely wrote:
| I just bought the whole set and just did chapter one, will
| probably not keep up with doing all the assignments but I
| indend to at least skim them and get a rough feel to where I
| can find stuff if I ever need it.
| nickdrozd wrote:
| Great post. Some general takeaways for people who want Knuth
| checks:
|
| 1. You are unlikely to find errors in the algorithms themselves,
| especially if they've been officially published. You might find
| some infelicities, but these are not counted as full errors. For
| example, the author here found some confusing-but-not-wrong
| comments about local variables and unused registers. These are
| counted as "suggestions" (worth 0x20C/) rather than "errors"
| (worth 0x$1.00).
|
| 2. Knuth is pretty generous with credit -- if your suggestion
| leads him to find an error, you get credit for the error. The
| author here said that some defined variables went unused. Knuth
| pointed out that those variables were in fact used in an
| exercise. However, in looking this up he noticed a variable-
| related error in that exercise. Author is credited with 0x$1.00!
|
| 3. Exercises are more likely to contain errors and infelicities
| than the main text. And there are an awful lot of exercises.
|
| 4. Knuth includes a whole bunch of stuff in his books that is not
| related to CS. Lots of weird trivia and references. This stuff is
| more likely to be wrong than the main text. For example, Knuth
| mentions "icosahedral objects inscribed with Greek letters" and
| includes a reference to an article in the _Bulletin de l'Institut
| francais du Caire_. But the author points out that the article is
| actually in the _Bulletin de l'Institut francais d'archeologie
| orientale_. Whoops! 0x$1.00 for you!
| Tomte wrote:
| Don't make assumptions about what parts must have been combed
| through so much that there is no chance of finding annerror.
|
| I found one and got my cheque on page Arabic one in one of his
| books. Paragraph one. First sentence. The very first word.
| eigenvalue wrote:
| Was it the word "the" instead of "a"? Trying to think what
| else it could even be.
| svat wrote:
| https://news.ycombinator.com/item?id=33083384
| fc417fc802 wrote:
| It's amusing that the same two commenters have
| essentially the same two comments side-by-side in both
| threads, years apart.
| ccppurcell wrote:
| For the lazy, the word is: "infinitely"
| dalke wrote:
| I found an error in a published version of TAOCP, 2nd edition I
| think, with improvements on Sieve of Eratosthenes. I was so
| excited, then found it was already listed in the errata.
|
| I later got a check for identifying a minor issue with the
| early history of superimposed coding. I happen to have copies
| of the relevant patent case containing examples predating
| Mooers' _randomized_ superimposed coding.
|
| ("Happened to" because I had visited the Mooers archive at the
| Charles Babbage Institute in Minnesota to research some of the
| early history of chemical information management. Mooers is one
| of the "fathers" of information retrieval, and in fact coined
| the term "information retrieval" at a chemistry conference.)
| hinkley wrote:
| Knuth has the Pablo Picasso's Dinner Bill "Problem" and so can
| afford to be generous.
|
| Picasso used to dine and dash as it were by drawing a doodle on
| the back of his check when the bill came due, and often enough
| the owner would choose to frame the check instead of cash it.
|
| For a long time most of the cost of writing checks to Knuth is
| the writing of the checks, not the cashing of them. He's paying
| for X00 checks at a time and the energy to fill them out. And
| anyone who had gotten their first check from him would not cash
| it.
|
| Though these days I can cash a check via a phone app and so I
| don't need to forfeit the check to get the money.
| fastasucan wrote:
| >Though these days I can cash a check via a phone app and so
| I don't need to forfeit the check to get the money.
|
| Its incredible that both of these technologies is in active
| use at the same time.
| bombcar wrote:
| They're not "real" checks anymore (unless you insist) because
| of check fraud issues. Bank of San Serif isn't a real bank.
| hinkley wrote:
| My bank knows where I live and if I start cashing fake
| checks they know where to send the FBI.
|
| Even in the old paper days banks where a little hesitant to
| let me come into your bank with a check from you and cash
| it without me also being a customer of that same bank. In
| theory you could do it, but sometimes if you tried you got
| the runaround.
| bombcar wrote:
| You can still wreak havoc with the account and routing
| numbers if you want to - it gets reversed when noticed
| which is why people still do it - sometimes it's not
| noticed.
| zozbot234 wrote:
| > ... includes a reference to an article in the _Bulletin de
| l'Institut francais du Caire_. But the author points out that
| the article is actually in the _Bulletin de l'Institut francais
| d'archeologie orientale_. Whoops! 0x$1.00 for you!
|
| I do wonder whether this is more likely to be a case where the
| journal actually changed its name over time (perhaps because
| the _Institut_ itself did) and then made the older papers
| available under the new name - which would mean both references
| are ultimately correct.
| skissane wrote:
| I don't think so. The article links to an image of the 1930
| journal article -
| https://gallica.bnf.fr/ark:/12148/btv1b53180372w - it doesn't
| look like it has been republished, it looks like something
| close to the original publication
|
| I don't completely know what is going on here, but I guess it
| is something like this: the institute has since 1898
| officially been called _Institut francais d 'archeologie
| orientale_, and its journal has always officially been called
| _Bulletin de l 'Institut francais d'archeologie orientale_.
| However, historically, people would sometimes add _du Caire_
| ( _in Cairo_ ) to the institute's name (to specify its
| location) - this habit was supported by the history that,
| prior to 1898, the institute (or its predecessor) was called
| _Ecole francaise du Caire_ (French School of Cairo) - and
| then unofficially abbreviate it from _Institut francais d
| 'archeologie orientale du Caire_ to _Institut francais d
| 'archeologie du Caire_ or even _Institut francais du Caire_.
| And since the journal is named for the institution, once
| people got in the habit of unofficially abbreviating the name
| of the institution, they applied the same habit to the
| journal.
|
| So _Bulletin de l'Institut francais d'archeologie orientale_
| has always been the official name of the journal, but
| _Bulletin de l'Institut francais du Caire_ is a historical
| unofficial alternative name.
|
| As I said, I'm just speculating, I don't really know. But
| this seems more plausible to me than the journal or institute
| changing its name, because I can't find any evidence of any
| name change since 1898, which was long before the publication
| of the 1930 article.
| gblargg wrote:
| Does the bank really read the amounts as hexadecimal?
| jks wrote:
| He used to send out real cheques for $2.56 but apparently they
| contained codes that could be used to transfer money out of his
| account in excess of the sum of the cheque. Now he uses the
| made-up Bank of San Serriffe, which naturally understands
| hexadecimal.
|
| https://www-cs-faculty.stanford.edu/~knuth/news08.html
| pests wrote:
| Routing and account numbers at the bottom of a check are
| semi-private and nefarious actors can abuse them. See the
| movie/book Catch Me If You Can about Frank Abigail.
| ozzmotik wrote:
| that's Abagnale, I believe.
| jll29 wrote:
| I've emailed DEK to point out that the first person to break
| Enigma was not actually Alan M. Turing (as stated in one of the
| recent pre-fascicles) but the Polish mathematician Marian
| Rejewski (Turing's contribution was to automate the task, which
| was important because the rotors/settings were reconfigured by
| the German Wehrmacht every morning).
|
| Bletchley Park now has a prominent bust of Rejewski that credits
| his accomplishment. The Polish wisely passed on their knowledge
| to the British to keep the intel safe, because they expected a
| German invasion.
|
| On another note, I hope Professor Knuth has a continuity plan in
| place that ensures that his book series gets completed despite
| his advanced age (I'm worried about that, but tact prohibited me
| from asking, of course).
| WillAdams wrote:
| Given his quite healthy lifestyle, I believe that we should be
| okay on that latter front --- I certainly hope so.
| irrational wrote:
| It's not his lifestyle I'm worried about. There was a healthy
| youtuber who made videos about wilderness survival who was
| killed when he was rear ended by a drunk driver while stopped
| at a red light (the drunk driver, of course, survived). It's
| all the morons around Knuth I'm worried about.
| ks2048 wrote:
| I hate to be morbid and I wish him a long life, but at age
| 87, I don't think drunk drivers are his biggest risk.
| rgmerk wrote:
| The book series will never be completed, and wouldn't be if
| Knuth lives to 120.
|
| And that's perfectly fine.
| mmooss wrote:
| OT: Will Knuth's lifetime of work be used for learning input in
| AI systems, and does he control that?
|
| An AI application might make a good search interface for Knuth's
| opus.
| lysace wrote:
| The key players have likely all ingested Anna's Archive.
| mmooss wrote:
| Based on what you say, I presume that Anna's Archive includes
| Knuth. For certain purposes, would you want AI software
| trained only on Knuth or have it 'diluted' with everything
| else?
| ForOldHack wrote:
| TOACP The Art of Computer Programming, Volumes 1~4c
|
| https://en.wikipedia.org/wiki/The_Art_of_Computer_Programmin...
|
| Kudos to everyone who found bugs, and got the bounty. Congrats to
| everyone who used these to get their PhD-CS
| geophile wrote:
| I first read parts of vol 1 in 1975, in my undergrad data
| structure and algorithm class. And then again in 1980 for my
| PhD comprehensive exams. That book is highly used. I found a
| pristine copy a few years in a pile of books on the sidewalk,
| thanks to someone moving.
|
| They put out a Unicomp clicky keyboard a few days later, picked
| up that too.
| svat wrote:
| My Knuth checks amount to a total account balance of 0x$b.40 at
| his "Bank of San Seriffe" (the equivalent of eleven "errors" and
| two "suggestions") -- mostly accumulated over a short period
| several years ago.
|
| Previously, I had the impression that Knuth was some magical
| figure of perfection. What I realized was that the truth was more
| surprising: he makes the same kinds and the same frequency of
| errors as anyone else (in fact likely more, because every page is
| packed with a lot of detail); what sets him apart is that he
| cares so deeply about getting everything right -- he has
| basically invited a DDoS on his time and attention, where every
| person in the world is strongly encouraged to write to him with
| errors on every page that he has ever written over several
| decades -- and he does go back and look at all of them carefully
| (example:
| https://retrocomputing.stackexchange.com/questions/18117/whi...);
| and despite all this he somehow continues to function, producing
| new pages at a nonzero rate. After some experience with his
| responses (handwritten with pencil on a printout of the emails
| sent to him), I came away even more impressed.
| zoky wrote:
| > _he makes the same kinds and the same frequency of errors as
| anyone else_
|
| Putting this here because I don't know where else to tell this
| story and I simply have to share:
|
| I flew into Munich a few months ago, and since I have an EU
| passport I was able to use the shorter self-scan line for EU
| citizens at passport control. In front of me was an older
| couple who was having trouble with getting their passports to
| scan. I noticed they had US passports, so I politely informed
| the gentleman that he was in the wrong line. He turned around
| and thanked me, and that's when I noticed the guy looked
| exactly like Donald Knuth! Before I could compose myself enough
| to say anything though, he and his wife had left to find the
| correct line. Obviously I couldn't be sure it was him, but I
| checked Knuth's public schedule and he was apparently speaking
| at some conference in Venice about two weeks later, so I'm
| guessing he decided to come a bit early and enjoy a vacation
| before the conference.
|
| So yeah, I'm like 99% sure I technically corrected an error by
| Donald Knuth, but unfortunately I missed out on my reward
| check. Didn't even get a selfie with him.
| abhgh wrote:
| I have mentioned this elsewhere online but I was once
| attending a talk in the computer history museum for which I
| had turned up early. An elderly gentleman took his seat right
| before me - it took me a while to process that it was Knuth
| (in reality, it was less to do with processing and more with
| accepting!).
|
| Somewhat recently we spotted him at a Hitchcock movie
| festival at Palo Alto, which my wife and I were attending.
|
| Random run-ins are surreal :-)
| oefrha wrote:
| Back when I was at Stanford a decade ago, I spotted him
| biking to/from Green Library quite a few times. You can
| probably run into him with some regularity if you make a
| habit of going to said library, assuming his routine hasn't
| changed much ;)
| rnewme wrote:
| At risk of sounding negative, I'm glad you didn't get to
| pester old man with a selfie.
| weinzierl wrote:
| I attended one of his MMIX lectures in Munich two decades ago
| and he mentioned that he was going to visit a friend later,
| so I guess he might have contacts in Munich.
|
| Speaking of errors, in the lecture he once forgot to save a
| file in Emacs and was confused about the compilation result
| briefly. Made him very relatable.
| ks2048 wrote:
| Another top story on HN right now is how LLMs are finding errors
| in research papers.
|
| Maybe an LLM winning a Knuth bug bounty is a milestone on the
| path towards "AGI"?
| vacuity wrote:
| AGI will be achieved when Knuth + LLMs work to finish TAOCP
| with no errors.
| rgovostes wrote:
| I haven't read TAOCP myself, but if I recall a lecture that Knuth
| gave, his algorithm analyses sometimes include cycle counts for
| his virtual MMIX architecture. He mentioned that these are
| counted by hand. If I were seeking a reward check, I would write
| a verifier to look for errors there.
| potus_kushner wrote:
| would like to read, but the site uses some clownflare
| alternative, that just like clownflare tries to verify my browser
| (palemoon), and then comes to the conclusion that my browser
| isn't a browser.
| vzaliva wrote:
| "he decided against breaking up Algorithm X between different
| pages"
|
| He should have used TeX ;) I've heard handles such layout
| problems automatically.
___________________________________________________________________
(page generated 2025-03-09 22:01 UTC)