I Got a Knuth Check for 0x$3.00

Any published authors here? I once went through a cheaper international edition of a large computer science text, and built a massive errata of all the mistakes (primarily found in the exercises) then submitted it to the authors who basically told me &#x27;Thanks but we don&#x27;t give a shit about that version, only the US edition&#x27;. Any reason there would be that many mistakes in the international version? Does Pearson publishers just use incompetent printers for these sell at cost books? It&#x27;s not trivial errata, about 20+ major mistakes per chapter I found.<p>Edit: My version is &quot;an authorized adaption, global edition&quot; overseen by two Malaysian professors and printed in Malaysia by Pearson Global. I&#x27;m not sure what adaption means in the printing industry.<p>Edit2: One of the author&#x27;s acknowledges the terrible amount of errors on their personal page <a href="https:&#x2F;&#x2F;www.amazon.com&#x2F;gp&#x2F;customer-reviews&#x2F;RK8QVG9TMSUIF&#x2F;ref=cm_cr_dp_d_rvw_ttl?ie=UTF8&amp;ASIN=013409266X" rel="nofollow">https:&#x2F;&#x2F;www.amazon.com&#x2F;gp&#x2F;customer-reviews&#x2F;RK8QVG9TMSUIF&#x2F;ref...</a> which I just discovered and did not know at the time I read the book (I bought this so I could understand MIXAL in TAOCP, Vol 1).

&gt; People also say that TAOCP is irrelevant or outdated or otherwise inapplicable to “real programming”. This also wrong. For instance, the first section after the chapter intro deals with the basic problem of searching for an item in an unsorted array. The simplest algorithm should be familiar to all programmers. Start your pointer at the head of the array, then do the following in a loop:<p><pre><code> Check if the current item is the desired one. If it is, return success; otherwise Check if the pointer is past the array bound. If it is, return failure; otherwise Increment the pointer and continue. </code></pre> &gt; Now consider: how many bound checks does this algorithm require on average? In the worst case, when the array doesn’t contain the item, one bound check will be required for each item in the list, and on average it will be something like N&#x2F;2. A more clever search algorithm can do it with just one bound check in all cases. Tack the desired item on to the end of the array, then start your pointer at the head of the array and do the following in a loop:<p><pre><code> Check if the current item is the desired one. If it is, return success if the pointer is within the array bound and return failure if it isn’t; otherwise Increment the pointer and continue. </code></pre> &gt; With this algorithm, things are arranged such that the item is guaranteed to be found one way or another, and the bound check only needs to be executed once when the item is found. This is a deep idea, but it’s also simple enough even for a beginning programmer to understand.<p>All this is true, but it overlooks one very important thing: on a modern processor architecture, this &quot;optimization&quot; will almost certainly be completely useless [1]. Almost certainly, the bounds check will be pipelined in such a way that it is essentially free on every iteration. Almost certainly, for a problem of any size where efficiency actually matters, the run time will be dominated by memory access latency.<p>So this is not a very good example to refute the argument that TAOCP is irrelevant and outdated.<p>[1] In fact, it will almost certainly be <i>worse</i> than useless because the extra setup and teardown steps required at the beginning and end will make the algorithm run <i>more slowly</i> than it otherwise would have.

Interesting. I have a 1973 (1st edition?) copy of Sorting and Searching I picked up at a book sale a couple years ago. In that version chapter 6 starts on page 389, and the typo is not there. I guess it was introduced later.

This is awesome! I&#x27;ll second the advice to try out the book. I&#x27;ll have to watch for small errors like this to point out, as well. :)<p>I&#x27;m currently reading this with some folks at work that simply run circles around my ability in the mathematical sections. It is humbling, but also very fun. The best is seeing the process on how to get through these sections. If you are like me, you assume it is someone doing a straight forward walk through the steps. My colleagues don&#x27;t hesitate to just start with an idea and see where it can go. Often, it is not necessarily algebra or anything else that gets to the next part, but a simple question of pattern recognition on the series we have put on the board. But, as often as not, mistakes are made and have to be tried again. The folks that get things right the most are not necessarily those that make the fewest mistakes.

<a href="https:&#x2F;&#x2F;www-cs-faculty.stanford.edu&#x2F;~knuth&#x2F;boss.html" rel="nofollow">https:&#x2F;&#x2F;www-cs-faculty.stanford.edu&#x2F;~knuth&#x2F;boss.html</a><p>Someone found and submitted 700+ errors. I wonder where he finds the time to send all of these out! I guess it’s like an open source project getting PRs.

<i>”In 1960, Karatsuba attended a seminar wherein Kolmogorov pitched his n2 conjecture. 3) “Exactly within a week” Karatsuba devised his divide-and-conquer algorithm. […] Thus the error is that 1962 should be 1960.”</i><p>Based on the information given, the correct year _could_ be 1961, too. When, exactly, was that seminar? Were Soviet universities at the time closed over Christmas?

TAoCP will always have a special place in my heart. It was my very first Computer Science textbook and what ultimately made me fall in love with the field. I remember reading about Knuth&#x27;s legendary checks and going through whole chapters thinking how cool it would be if I ever found one. Good times!

Slightly OT, but this whole article is about nitpicks so I don’t feel guilty...<p>Shouldn’t the dollar sign be before the 0x?

I once read a short biography of Donald who put forth the image of a gentlemen who often eschewed most of lifes pleasantries and small enjoyments in pursuit of spending most of his life in his library, studying, with little brain capacity remaining for anything else.<p>Given this, I pictured a somewhat solitary gentleman - a slightly more dignified version of a modern nerdy basement dweller, disconnected from modern life and humour.<p>Therefore I find great joy in seeing the words &quot;Bank of San Seriffe&quot;. I giggled quite a lot at this. :)<p>Ps. This description is probably entirely wrong. It&#x27;s just how I always pictured him as a result of reading that article.

This is impressive; congratulations to the author! I too got a Knuth check for 0x$3.00 a year or two ago... but that was for errors in the unpublished (draft) pre-fascicles; finding some in the published volumes of TAOCP is surely a rare event!<p>A few more comments:<p>• A huge +100 for the paragraph pointing out that TAOCP is <i>not</i> a reference work; it&#x27;s a very enjoyable work meant to be read:<p>&gt; <i>By the way, if you’ve ever thought about reading TAOCP, give it a try. A lot of people will tell you that it’s a reference work, and it’s not meant to be read straight through, but that isn’t true. The author has a clear point of view and a narrative and an idiosyncratic style, and the only thing that inhibits readability is the difficulty of the math. There’s an easy solution to that though: read until you get to math you don’t understand, then skip it and find the next section you can understand. Reading this way, I skip at least 80% of the book, but the remaining 20% is great!</i><p>In addition, there are many jokes, beautifully employed quotes, etc. Basically what Knuth has done is to take all the published research literature on each of the topics of the respective chapters, digest it, pass it through his personal “interestingness” filter, and figure out what he feels is the best way to teach it. The result is highly personal, and not all what one may expect from “reference work”.<p>• Karatsuba multiplication was discussed recently on HN: <a href="https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=19672835" rel="nofollow">https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=19672835</a><p>• To be pedantic, 0x$3.00 (aka $7.68) only puts you in a 29-way tie for the 115th richest person in the Bank of San Seriffe — it&#x27;s the 69th largest amount but you need to count all the people with each higher amount :-) Also note that this BoSS only counts checks since 2006.<p>• I actually find my name on the list with another 0x$1.00 (and I think I know what it was for), but I never received a check for it: probably lost in the mail, in which case I&#x27;ll never forgive USPS for it. I have however received many replies from Knuth saying that the errors I tried to point out were not actually errors, or that they had already been pointed out by others, just not updated on the website yet (in the case of the draft pre-fascicles). You send him an email (only if it&#x27;s a bug; else the email never reaches him!), his secretary who comes in once a week prints it out for him, he gets to it at some point, scrawls his response in pencil, encloses a check if warranted, then his secretary sends it back to you by post. Exactly as described here: <a href="https:&#x2F;&#x2F;cs.stanford.edu&#x2F;~knuth&#x2F;email.html" rel="nofollow">https:&#x2F;&#x2F;cs.stanford.edu&#x2F;~knuth&#x2F;email.html</a> (I once snuck in my solution to one of his exercises (which asked to write a poem) and he wrote “Beautiful!” next to it, which I will value more than the check itself.)

Does the algorithm described for finding a number in an unsorted array using minimal checks really work? Probably is addressed more in the book but didn&#x27;t see my concerns in the post.<p>The algorithm I am referring to is: &quot; 1. Check if the current item is the desired one. If it is, return success if the pointer is within the array bound and return failure if it isn’t; otherwise 2. Increment the pointer and continue. &quot;<p>I think it assumes that all values will be found in memory somewhere (otherwise an exception will be raised for trying to read memory at an address that does not exist). This is probably the case in practice but I don&#x27;t think there are guarantees of it being the case.<p>Also, this algorithm can have lower worse-case performance than a more naive solution because its performance is based on the number of possible values (assuming random distribution) rather than the size of the array for cases where a value cannot be found.

I love this blog post - it reminds me of an older internet and style of writing. Thanks for writing it!

I&#x27;m actually shocked that Knuth writes DD MMM, YYYY

I had a comp sci prof back in the early 1970&#x27;s. Someone told me that he had gotten a check from Knuth for finding an error. I saw him off campus once and I had to check to see if his feet actually touched the ground. I swear that they didn&#x27;t.

I found and reported decent errata in a popular Django book this year and got no reply from the authors.<p>I heard the book has not been financially successful enough. That said, it feels like books should have some kind of GitHub style community errata by default.

This is fantastic! All books should have a bug bounty reward. What if we&#x27;d extend that to news? Would that solve the fake news issue?

Check if the current item is the desired one. If it is, return success; otherwise Check if the pointer is past the array bound. If it is, return failure; otherwise Increment the pointer and continue.<p>Um, shouldn&#x27;t the check be done before accessing the current one?

This led me to Donald Knuth&#x27;s organ pages, what an incredible instrument that must be to have on one&#x27;s house:<p><a href="https:&#x2F;&#x2F;www-cs-faculty.stanford.edu&#x2F;~knuth&#x2F;organ.html" rel="nofollow">https:&#x2F;&#x2F;www-cs-faculty.stanford.edu&#x2F;~knuth&#x2F;organ.html</a>

&gt; <i>the first section after the chapter intro deals with the basic problem of searching for an item in an unsorted array. The simplest algorithm should be familiar to all programmers. Start your pointer at the head of the array, then do the following in a loop:</i><p>&gt; <i>Check if the current item is the desired one. If it is, return success; otherwise</i><p>&gt; <i>Check if the pointer is past the array bound. If it is, return failure; otherwise</i><p>&gt; <i>Increment the pointer and continue.</i><p>&gt; <i>Now consider: how many bound checks does this algorithm require on average? In the worst case, when the array doesn’t contain the item, one bound check will be required for each item in the list, and on average it will be something like N&#x2F;2. A more clever search algorithm can do it with just one bound check in all cases. Tack the desired item on to the end of the array, then start your pointer at the head of the array and do the following in a loop:</i><p>&gt; <i>Check if the current item is the desired one. If it is, return success if the pointer is within the array bound and return failure if it isn’t; otherwise</i><p>&gt; <i>Increment the pointer and continue.</i><p>&gt; <i>With this algorithm, things are arranged such that the item is guaranteed to be found one way or another, and the bound check only needs to be executed once when the item is found.</i><p>It sounds like he&#x27;s saying &quot;feel free to overrun the buffer; eventually you&#x27;ll find the value you want somewhere in the depths of memory, and then you can check and see that you&#x27;ve left the array behind long ago.&quot; Aside from the obvious problems, it&#x27;s not at all guaranteed that the specific bit sequence you want will exist anywhere in memory.<p>What am I missing?

I got two (real) checks from him from the newly re-typeset first volume in the late 90s. Someone else did a bunch of the typesetting work and it was relatively sloppy so I managed to notice them from relatively casual reading.<p>Cashed both checks.

Frame it. It will be a classic. Some banks allow you cash a check by cellphone photo instead of turning it in.<p>Donald was one of the original crowdsourcers. He employed the public to improve his already high quality publications.

&gt; This post alone is sure to contain several typos (no rewards for finding them though)<p>[...]<p>&gt; It mostly applies to [techinical] errors,

Even if it was a real check I wouldn’t cash it. I’m sure people did the same with Dali’s checks

The article names Asuthosh Mehra as the leader with 0x$207.f0 -- but Knuth&#x27;s site lists two even higher: including Udo Wermuth with a whopping 0x$772.58. <a href="https:&#x2F;&#x2F;www-cs-faculty.stanford.edu&#x2F;~knuth&#x2F;boss.html" rel="nofollow">https:&#x2F;&#x2F;www-cs-faculty.stanford.edu&#x2F;~knuth&#x2F;boss.html</a>

I came here expecting to find some sort of problems on mathematical proofs, since he was quote saying &quot;Beware of bugs in the above code; I have only proved it correct, not tried it.&quot; and I got out disapointed for two human mistakes and one minor historical hiccup.

Good story! Knuth&#x27;s nickname of &quot;Yoda&quot; is well-deserved.

Man, you ruined the life of two other people who could have found 2 out of the 3 bugs!!!<p>Jokes apart, congratulations. Well done and well deserved.

Did you mean Knuth Cheque?

I wonder if anyone cashes these things? We should all gang up and cash these checks together and overdraw him. Or at least really screw up his check book balance.

I&#x27;m quite proud to have found an error on page arabic one. In the first sentence. The very first word. Not a typographical error.<p>Nobody can claim he did not read that far.<p>I still believe I should have gotten a cheque for my bug report that &quot;the programs are in the public domain&quot; or similar wording on the back cover of the MMIX book is clearly wrong, since the copyright notices assert copyright, but Knuth dismissed that along the lines of &quot;I&#x27;m not a Stallman disciple&quot;. Even though &quot;public domain&quot; has a clear legal meaning. Oh well, whatever, I&#x27;ve got 0x$1.20, that&#x27;s enough.

I do this with tipping.<p>If the price is 22.95 I tip -22.95 and the total charge is only $0.00 ... save a ton of money!