13 ms·

I Got a Knuth Check for 0x$3.00

469 points by UkiahSmith 7y ago

burtonator 7y ago
I do this with tipping. If the price is 22.95 I tip -22.95 and the total charge is only $0.00 ... save a ton of money!
- dbish 7y ago
  It's not 0 times the value, it's a hex number.
  - burtonator 7y ago
    Ah!! ha.. I just scanned the number.
  - userbinator 7y ago
    Perhaps it would be clear if it was $0x3.00 , but I see that 0x$ is the way Knuth writes it on his reward checks... I wonder if anyone pointing this out might get one too.
- 768 7y ago
  $7.68 USD
- mruts 7y ago
  I don’t understand?
- LukaD 7y ago
  If you don't want to tip, maybe just don't tip then?
simonebrunozzi 7y ago
Man, you ruined the life of two other people who could have found 2 out of the 3 bugs!!! Jokes apart, congratulations. Well done and well deserved.
raister 7y ago
I came here expecting to find some sort of problems on mathematical proofs, since he was quote saying "Beware of bugs in the above code; I have only proved it correct, not tried it." and I got out disapointed for two human mistakes and one minor historical hiccup.
- nickdrozd 7y ago
  Tuh, you and me both. Then again, it's been said that "technically correct" is "the best kind of correct". https://www.youtube.com/watch?v=hou0lU8WMgo https://www.youtube.com/watch?v=hou0lU8WMgo
mimixco 7y ago
Good story! Knuth's nickname of "Yoda" is well-deserved.
nsomaru 7y ago
Slightly OT, but this whole article is about nitpicks so I don’t feel guilty... Shouldn’t the dollar sign be before the 0x?
- userbinator 7y ago
  That's apparently how Knuth writes it, so feel free to ask him. Maybe you'll get a reward too? ;-)
- manningthegoose 7y ago
  Not really, since a “hexadecimal dollar” is really just a fictional measurement of money that Knuth has created (which he designates with symbol 0x$). I guess if it were $0x3.00, you could interpret the quantity to be regular dollars in hex form, which would just evaluate to 3, instead of the 7.68 Knuth is actually offering
- LodeOfCode 7y ago
  0x$ = 0x100¢ = 2.56$?
- so33 7y ago
  The check is issued by the “Bank of San Serriffe” (https://en.m.wikipedia.org/wiki/San_Serriffe https://en.m.wikipedia.org/wiki/San_Serriffe). Perhaps they have different typographical conventions...
Someone 7y ago
”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.” 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?
- dchest 7y ago
  > Were Soviet universities at the time closed over Christmas No, Christmas was not an official holiday. Also, it's on the 7th of January.
  - lukasm 7y ago
    25th of Dec is 7th of January in the common Gregorian calendar.
- nickdrozd 7y ago
  Apparently the seminar was held "in the autumn of 1960" [1], so "within a week" seems safely within 1960. That said, I will happily award 0x$0.50 to anyone who can come up with conclusive proof that the algorithm was discovered in 1961. Karatsuba himself is dead though, so such evidence will not be easy to find. [1] https://www.researchgate.net/publication/258001835_The_complexity_of_computations https://www.researchgate.net/publication/258001835_The_compl...
  - HumanHater 7y ago
    > The Karatsuba algorithm is a fast multiplication algorithm. It was discovered by Anatoly Karatsuba in 1960 and published in 1962. https://en.wikipedia.org/wiki/Karatsuba_algorithm https://en.wikipedia.org/wiki/Karatsuba_algorithm
taeric 7y ago
This is awesome! I'll second the advice to try out the book. I'll have to watch for small errors like this to point out, as well. :) I'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'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.
dmix 7y ago
https://www-cs-faculty.stanford.edu/~knuth/boss.html https://www-cs-faculty.stanford.edu/~knuth/boss.html 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.
- weinzierl 7y ago
  Maybe he just likes working through text books thoroughly? I personally find it quite valuable to compile a list of "outstanding questions" for the text books I read. Usually most of my questions are resolved before I finish the book. The ones that remain, often turn out to be simply errors. Finding the the errors is just a by-product of the learning process for me.
- svat 7y ago
  Knuth gives higher rewards for works he believes have fewer errors. For TeX and METAFONT, he started with 1 cent for every bug found, and doubled it each year until reaching the current value of 327.68 dollars (= 0x$80.00): for example Eberhard Mattes and Oleg Bulatov (joint 7th on the list) have all their amount from a single (and the latest so far) bug found in TeX and METAFONT each (if you're wondering what the bugs were: https://tex.stackexchange.com/questions/154873/ https://tex.stackexchange.com/questions/154873/ — the TeX bug was a missing space in the debug output for a macro with an empty name). Incidentally, he seems to have had this policy of giving out rewards for errors from the time he was a college student: http://ed-thelen.org/comp-hist/B5000-AlgolRWaychoff.html#7 http://ed-thelen.org/comp-hist/B5000-AlgolRWaychoff.html#7
  - veddox 7y ago
    Great story, thanks for sharing! "The first week of don's project he spent in writing his own assembler." And my respect for Knuth goes up even further :-O
- Tomte 7y ago
  Some German guy has actually been cashing a Knuth cheque every year. Cashing! A Knuth cheque! That's decadent. (Source: a Knuth interview that's probably easy to find, but I don't have the URL at hand)
jaredsohn 7y ago
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't see my concerns in the post. The algorithm I am referring to is: " 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. " 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't think there are guarantees of it being the case. 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.
- Someone 7y ago
  Read the sentence before it: ”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” (https://paws.kettering.edu/~jhuggins/humor/elephants.html https://paws.kettering.edu/~jhuggins/humor/elephants.html: ”Experienced computer programmers modify Algorithm A by placing a known elephant in Cairo to ensure that the algorithm will terminate.”)
- deleted 7y ago
  [deleted]
- thaumasiotes 7y ago
  > 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't see my concerns in the post. > I think it assumes that all values will be found in memory somewhere That assumption is not made; the post does cover this. You left out the beginning of the algorithm: > 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: It's not clear to me how you're supposed to "tack the item on to the end of the array", though. That's not an operation arrays naturally support. If you recopy the array so you can add your sentinel value, then you're replacing an average n/2 bounds checks with a guaranteed n copies.
PhasmaFelis 7y ago
> 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: > 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. > 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/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: > 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. > 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. It sounds like he's saying "feel free to overrun the buffer; eventually you'll find the value you want somewhere in the depths of memory, and then you can check and see that you've left the array behind long ago." Aside from the obvious problems, it's not at all guaranteed that the specific bit sequence you want will exist anywhere in memory. What am I missing?
- mruts 7y ago
  He’s saying that if you append the value you’re looking for at the end, you don’t need a bounds check since you are guaranteed to find it at the very end. Kind of like C strings terminated with NUL.
- mjw1007 7y ago
  « Tack the desired item on to the end of the array »
- tasty_freeze 7y ago
  OK, even if it isn't possible to cheaply extend the array by one, do this slight tweak for the same end result: store the last item in the array as a temporary, and replace it in the array by a sentinel value. (search the array). Once you find the value, if the index isn't that of the last entry, you've found it. If it is the last entry, check the temporary to see if it happened to be the value you were looking for. Finally, replace the last item in the array by the temporary value.
svat 7y ago
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! A few more comments: • A huge +100 for the paragraph pointing out that TAOCP is not a reference work; it's a very enjoyable work meant to be read: > 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! 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”. • Karatsuba multiplication was discussed recently on HN: https://news.ycombinator.com/item?id=19672835 https://news.ycombinator.com/item?id=19672835 • 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'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. • 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'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'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: https://cs.stanford.edu/~knuth/email.html https://cs.stanford.edu/~knuth/email.html (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.)
hackermailman 7y ago
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 'Thanks but we don't give a shit about that version, only the US edition'. 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's not trivial errata, about 20+ major mistakes per chapter I found. Edit: My version is "an authorized adaption, global edition" overseen by two Malaysian professors and printed in Malaysia by Pearson Global. I'm not sure what adaption means in the printing industry. Edit2: One of the author's acknowledges the terrible amount of errors on their personal page https://www.amazon.com/gp/customer-reviews/RK8QVG9TMSUIF/ref=cm_cr_dp_d_rvw_ttl?ie=UTF8&ASIN=013409266X https://www.amazon.com/gp/customer-reviews/RK8QVG9TMSUIF/ref... 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).
- wodenokoto 7y ago
  I’m sorry you got such a shitty reply to what must have been a lot of hard work. Did you try to contact the Malaysian professors? Regardless, thank you for the warning about international editions.
  - hackermailman 7y ago
    I probably should have contacted them. The completely untrustworthy answers/exercises turned out to be somewhat of a blessing in disguise as I ended up really learning the material being that I had to figure out everything myself and carefully step through exercises to find the error. However I had luxury of free time to do so and wasn't panicking under pressure of a class schedule and this text is used for a lot of undergrad courses.
- edge17 7y ago
  International Editions differ often in the problems at the ends of the chapters in order to protect US and other western markets. Differences in the problems means it discourages students from buying things that may lead to incorrect answers to assigned problem sets. As for things just being flat out wrong, I can only imagine this discourages US/western students from buying International Editions to save money.
anderspitman 7y ago
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.
- ehsankia 7y ago
  I'm curious, unlike the other two, wouldn't that typo be caught by any sort of automatic grammar checker? Couldn't anyone looking for a Knuth Check just load the text into a decent checker and go through the suggestions to find a valid one?
  - aasasd 7y ago
    It's probably difficult to deal with a type checker on a programming and math book.
- nickdrozd 7y ago
  I can't remember where I read this, but I think the first edition of Volume 3 was the last one to be published before the creation of TeX, and so the second edition had to substantially reworked. The typo was probably introduced at that time.
jacquesm 7y ago
This led me to Donald Knuth's organ pages, what an incredible instrument that must be to have on one's house: https://www-cs-faculty.stanford.edu/~knuth/organ.html https://www-cs-faculty.stanford.edu/~knuth/organ.html
heinrichf 7y ago
> This post alone is sure to contain several typos (no rewards for finding them though) [...] > It mostly applies to [techinical] errors,
- nickdrozd 7y ago
  Fixed! Unfortunately, somebody beat you to it, so you wouldn't receive a reward check even I were sending them out, which, to reiterate, I'm not :)
typon 7y ago
I love this blog post - it reminds me of an older internet and style of writing. Thanks for writing it!
Tomte 7y ago
I'm quite proud to have found an error on page arabic one. In the first sentence. The very first word. Not a typographical error. Nobody can claim he did not read that far. I still believe I should have gotten a cheque for my bug report that "the programs are in the public domain" 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 "I'm not a Stallman disciple". Even though "public domain" has a clear legal meaning. Oh well, whatever, I've got 0x$1.20, that's enough.
flensortow 7y ago
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. Cashed both checks.
krm01 7y ago
This is fantastic! All books should have a bug bounty reward. What if we'd extend that to news? Would that solve the fake news issue?
- Sharlin 7y ago
  News is not about facts. Fake news even less so. Why would someone with an agenda reward fact-checkers? On the other hand, reputable news outlets already accept and publish corrections. Of course, nobody reads them; the damage is already done. Unlike a book, there won’t be future readers who would benefit from the correction.
bredren 7y ago
I found and reported decent errata in a popular Django book this year and got no reply from the authors. 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.
gitpusher 7y ago
The article names Asuthosh Mehra as the leader with 0x$207.f0 -- but Knuth's site lists two even higher: including Udo Wermuth with a whopping 0x$772.58. https://www-cs-faculty.stanford.edu/~knuth/boss.html https://www-cs-faculty.stanford.edu/~knuth/boss.html
- snpriyanshu 7y ago
  The blog clearly mentions "Ashutosh Mehra is the third-richest person in San Serriffe".
neysofu 7y ago
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's legendary checks and going through whole chapters thinking how cool it would be if I ever found one. Good times!
lisper 7y ago
> 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: 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. > 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/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: 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. > 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. All this is true, but it overlooks one very important thing: on a modern processor architecture, this "optimization" 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. So this is not a very good example to refute the argument that TAOCP is irrelevant and outdated. [1] In fact, it will almost certainly be worse than useless because the extra setup and teardown steps required at the beginning and end will make the algorithm run more slowly than it otherwise would have.
- Arnavion 7y ago
  It's already questionable for a search algorithm to require the ability to write to the array it's searching in, but it's even worse if it wants to be able to extend and shrink the array to do so. Edit: I haven't read the book. Presumably it gives some context for the algorithm that you only bring it out in the specific situation where it makes sense to use it.
ape4 7y ago
I'm actually shocked that Knuth writes DD MMM, YYYY
- random42 7y ago
  Why? Its the most unambiguous one.
  - RandomGuyDTB 7y ago
    YYYYMMDD in my experiences is best for file sorting.
benchplz 7y ago
did you cash it?
chaostheory 7y ago
Even if it was a real check I wouldn’t cash it. I’m sure people did the same with Dali’s checks
Lowkeyloki 7y ago
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.
- deleted 7y ago
  [deleted]
- basitmakine 7y ago
  It's not a real check though. He stopped sending real once in 2008 according to the article.
  - Lowkeyloki 7y ago
    That's weak. Now he's just printing Monopoly money.
- zaarn 7y ago
  Now that's just mean for no good reason.
nathankunicki 7y ago
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. 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. Therefore I find great joy in seeing the words "Bank of San Seriffe". I giggled quite a lot at this. :) Ps. This description is probably entirely wrong. It's just how I always pictured him as a result of reading that article.
- svat 7y ago
  His first publication, as a high-school student, was in MAD magazine. His books are full of jokes, both highly technical ones and more trivial ones. :-) If you have some mathematical inclination and a couple of hours to spare, you may like watching his (1-hour) Christmas lecture from 2017: https://www.youtube.com/watch?v=BxQw4CdxLr8 https://www.youtube.com/watch?v=BxQw4CdxLr8 — you may need to listen carefully (he's over 80 after all), but some of his humour comes through at moments.
- kontorStol 7y ago
  I recommend this video to you: Oral History of Donald Knuth Part 1 and 2: https://www.youtube.com/watch?v=Wp7GAKLSGnI https://www.youtube.com/watch?v=Wp7GAKLSGnI on The Computer History Museum Youtube channel. It's a _really_ long interview, +7 hours. But it's also superb. He is interviewed by his friend and colleague Edward Feigenbaum who does a stellar job. He brings out the human Donald Knuth in a remarkable way. It gave me great respect and admiration for Donald Knuth life and achievements. For me I dare to say it was transformative in regards to human pursuit of knowledge, passion and what it means to be a intellectual human being. td;dr: Watched a Donald Knuth interview and got a nerd crush
jtlienwis 7y ago
I had a comp sci prof back in the early 1970'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't.
crypster 7y ago
Did you mean Knuth Cheque?
peter303 7y ago
Frame it. It will be a classic. Some banks allow you cash a check by cellphone photo instead of turning it in. Donald was one of the original crowdsourcers. He employed the public to improve his already high quality publications.
- jcl 7y ago
  In case it wasn't clear from the article, it's not a real check. (But certainly worthy of framing.) https://www-cs-faculty.stanford.edu/~knuth/news08.html https://www-cs-faculty.stanford.edu/~knuth/news08.html
warmfuzzykitten 7y ago
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. Um, shouldn't the check be done before accessing the current one?

469 points by UkiahSmith 7y ago

burtonator 7y ago

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

dbish 7y ago
It's not 0 times the value, it's a hex number.
- burtonator 7y ago
  Ah!! ha.. I just scanned the number.
- userbinator 7y ago
  Perhaps it would be clear if it was $0x3.00 , but I see that 0x$ is the way Knuth writes it on his reward checks... I wonder if anyone pointing this out might get one too.
768 7y ago
$7.68 USD
mruts 7y ago
I don’t understand?
LukaD 7y ago
If you don't want to tip, maybe just don't tip then?

simonebrunozzi 7y ago

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

raister 7y ago

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

nickdrozd 7y ago
Tuh, you and me both. Then again, it's been said that "technically correct" is "the best kind of correct". https://www.youtube.com/watch?v=hou0lU8WMgo https://www.youtube.com/watch?v=hou0lU8WMgo

mimixco 7y ago

Good story! Knuth's nickname of "Yoda" is well-deserved.

nsomaru 7y ago

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

userbinator 7y ago
That's apparently how Knuth writes it, so feel free to ask him. Maybe you'll get a reward too? ;-)
manningthegoose 7y ago
Not really, since a “hexadecimal dollar” is really just a fictional measurement of money that Knuth has created (which he designates with symbol 0x$). I guess if it were $0x3.00, you could interpret the quantity to be regular dollars in hex form, which would just evaluate to 3, instead of the 7.68 Knuth is actually offering
LodeOfCode 7y ago
0x$ = 0x100¢ = 2.56$?
so33 7y ago
The check is issued by the “Bank of San Serriffe” (https://en.m.wikipedia.org/wiki/San_Serriffe https://en.m.wikipedia.org/wiki/San_Serriffe). Perhaps they have different typographical conventions...

Someone 7y ago

”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.” 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?

dchest 7y ago
> Were Soviet universities at the time closed over Christmas No, Christmas was not an official holiday. Also, it's on the 7th of January.
- lukasm 7y ago
  25th of Dec is 7th of January in the common Gregorian calendar.
nickdrozd 7y ago
Apparently the seminar was held "in the autumn of 1960" [1], so "within a week" seems safely within 1960. That said, I will happily award 0x$0.50 to anyone who can come up with conclusive proof that the algorithm was discovered in 1961. Karatsuba himself is dead though, so such evidence will not be easy to find. [1] https://www.researchgate.net/publication/258001835_The_complexity_of_computations https://www.researchgate.net/publication/258001835_The_compl...
- HumanHater 7y ago
  > The Karatsuba algorithm is a fast multiplication algorithm. It was discovered by Anatoly Karatsuba in 1960 and published in 1962. https://en.wikipedia.org/wiki/Karatsuba_algorithm https://en.wikipedia.org/wiki/Karatsuba_algorithm

taeric 7y ago

This is awesome! I'll second the advice to try out the book. I'll have to watch for small errors like this to point out, as well. :) I'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'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.

dmix 7y ago

https://www-cs-faculty.stanford.edu/~knuth/boss.html https://www-cs-faculty.stanford.edu/~knuth/boss.html 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.

weinzierl 7y ago
Maybe he just likes working through text books thoroughly? I personally find it quite valuable to compile a list of "outstanding questions" for the text books I read. Usually most of my questions are resolved before I finish the book. The ones that remain, often turn out to be simply errors. Finding the the errors is just a by-product of the learning process for me.
svat 7y ago
Knuth gives higher rewards for works he believes have fewer errors. For TeX and METAFONT, he started with 1 cent for every bug found, and doubled it each year until reaching the current value of 327.68 dollars (= 0x$80.00): for example Eberhard Mattes and Oleg Bulatov (joint 7th on the list) have all their amount from a single (and the latest so far) bug found in TeX and METAFONT each (if you're wondering what the bugs were: https://tex.stackexchange.com/questions/154873/ https://tex.stackexchange.com/questions/154873/ — the TeX bug was a missing space in the debug output for a macro with an empty name). Incidentally, he seems to have had this policy of giving out rewards for errors from the time he was a college student: http://ed-thelen.org/comp-hist/B5000-AlgolRWaychoff.html#7 http://ed-thelen.org/comp-hist/B5000-AlgolRWaychoff.html#7
- veddox 7y ago
  Great story, thanks for sharing! "The first week of don's project he spent in writing his own assembler." And my respect for Knuth goes up even further :-O
Tomte 7y ago
Some German guy has actually been cashing a Knuth cheque every year. Cashing! A Knuth cheque! That's decadent. (Source: a Knuth interview that's probably easy to find, but I don't have the URL at hand)

jaredsohn 7y ago

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't see my concerns in the post. The algorithm I am referring to is: " 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. " 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't think there are guarantees of it being the case. 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.

Someone 7y ago
Read the sentence before it: ”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” (https://paws.kettering.edu/~jhuggins/humor/elephants.html https://paws.kettering.edu/~jhuggins/humor/elephants.html: ”Experienced computer programmers modify Algorithm A by placing a known elephant in Cairo to ensure that the algorithm will terminate.”)
deleted 7y ago
[deleted]
thaumasiotes 7y ago
> 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't see my concerns in the post. > I think it assumes that all values will be found in memory somewhere That assumption is not made; the post does cover this. You left out the beginning of the algorithm: > 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: It's not clear to me how you're supposed to "tack the item on to the end of the array", though. That's not an operation arrays naturally support. If you recopy the array so you can add your sentinel value, then you're replacing an average n/2 bounds checks with a guaranteed n copies.

PhasmaFelis 7y ago

> 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: > 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. > 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/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: > 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. > 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. It sounds like he's saying "feel free to overrun the buffer; eventually you'll find the value you want somewhere in the depths of memory, and then you can check and see that you've left the array behind long ago." Aside from the obvious problems, it's not at all guaranteed that the specific bit sequence you want will exist anywhere in memory. What am I missing?

mruts 7y ago
He’s saying that if you append the value you’re looking for at the end, you don’t need a bounds check since you are guaranteed to find it at the very end. Kind of like C strings terminated with NUL.
mjw1007 7y ago
« Tack the desired item on to the end of the array »
tasty_freeze 7y ago
OK, even if it isn't possible to cheaply extend the array by one, do this slight tweak for the same end result: store the last item in the array as a temporary, and replace it in the array by a sentinel value. (search the array). Once you find the value, if the index isn't that of the last entry, you've found it. If it is the last entry, check the temporary to see if it happened to be the value you were looking for. Finally, replace the last item in the array by the temporary value.

svat 7y ago

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! A few more comments: • A huge +100 for the paragraph pointing out that TAOCP is not a reference work; it's a very enjoyable work meant to be read: > 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! 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”. • Karatsuba multiplication was discussed recently on HN: https://news.ycombinator.com/item?id=19672835 https://news.ycombinator.com/item?id=19672835 • 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'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. • 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'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'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: https://cs.stanford.edu/~knuth/email.html https://cs.stanford.edu/~knuth/email.html (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.)

hackermailman 7y ago

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 'Thanks but we don't give a shit about that version, only the US edition'. 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's not trivial errata, about 20+ major mistakes per chapter I found. Edit: My version is "an authorized adaption, global edition" overseen by two Malaysian professors and printed in Malaysia by Pearson Global. I'm not sure what adaption means in the printing industry. Edit2: One of the author's acknowledges the terrible amount of errors on their personal page https://www.amazon.com/gp/customer-reviews/RK8QVG9TMSUIF/ref=cm_cr_dp_d_rvw_ttl?ie=UTF8&ASIN=013409266X https://www.amazon.com/gp/customer-reviews/RK8QVG9TMSUIF/ref... 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).

wodenokoto 7y ago
I’m sorry you got such a shitty reply to what must have been a lot of hard work. Did you try to contact the Malaysian professors? Regardless, thank you for the warning about international editions.
- hackermailman 7y ago
  I probably should have contacted them. The completely untrustworthy answers/exercises turned out to be somewhat of a blessing in disguise as I ended up really learning the material being that I had to figure out everything myself and carefully step through exercises to find the error. However I had luxury of free time to do so and wasn't panicking under pressure of a class schedule and this text is used for a lot of undergrad courses.
edge17 7y ago
International Editions differ often in the problems at the ends of the chapters in order to protect US and other western markets. Differences in the problems means it discourages students from buying things that may lead to incorrect answers to assigned problem sets. As for things just being flat out wrong, I can only imagine this discourages US/western students from buying International Editions to save money.

anderspitman 7y ago

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.

ehsankia 7y ago
I'm curious, unlike the other two, wouldn't that typo be caught by any sort of automatic grammar checker? Couldn't anyone looking for a Knuth Check just load the text into a decent checker and go through the suggestions to find a valid one?
- aasasd 7y ago
  It's probably difficult to deal with a type checker on a programming and math book.
nickdrozd 7y ago
I can't remember where I read this, but I think the first edition of Volume 3 was the last one to be published before the creation of TeX, and so the second edition had to substantially reworked. The typo was probably introduced at that time.

jacquesm 7y ago

This led me to Donald Knuth's organ pages, what an incredible instrument that must be to have on one's house: https://www-cs-faculty.stanford.edu/~knuth/organ.html https://www-cs-faculty.stanford.edu/~knuth/organ.html

heinrichf 7y ago

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

nickdrozd 7y ago
Fixed! Unfortunately, somebody beat you to it, so you wouldn't receive a reward check even I were sending them out, which, to reiterate, I'm not :)

typon 7y ago

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

Tomte 7y ago

I'm quite proud to have found an error on page arabic one. In the first sentence. The very first word. Not a typographical error. Nobody can claim he did not read that far. I still believe I should have gotten a cheque for my bug report that "the programs are in the public domain" 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 "I'm not a Stallman disciple". Even though "public domain" has a clear legal meaning. Oh well, whatever, I've got 0x$1.20, that's enough.

flensortow 7y ago

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. Cashed both checks.

krm01 7y ago

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

Sharlin 7y ago
News is not about facts. Fake news even less so. Why would someone with an agenda reward fact-checkers? On the other hand, reputable news outlets already accept and publish corrections. Of course, nobody reads them; the damage is already done. Unlike a book, there won’t be future readers who would benefit from the correction.

bredren 7y ago

I found and reported decent errata in a popular Django book this year and got no reply from the authors. 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.

gitpusher 7y ago

The article names Asuthosh Mehra as the leader with 0x$207.f0 -- but Knuth's site lists two even higher: including Udo Wermuth with a whopping 0x$772.58. https://www-cs-faculty.stanford.edu/~knuth/boss.html https://www-cs-faculty.stanford.edu/~knuth/boss.html

snpriyanshu 7y ago
The blog clearly mentions "Ashutosh Mehra is the third-richest person in San Serriffe".

neysofu 7y ago

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's legendary checks and going through whole chapters thinking how cool it would be if I ever found one. Good times!

lisper 7y ago

> 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: 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. > 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/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: 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. > 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. All this is true, but it overlooks one very important thing: on a modern processor architecture, this "optimization" 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. So this is not a very good example to refute the argument that TAOCP is irrelevant and outdated. [1] In fact, it will almost certainly be worse than useless because the extra setup and teardown steps required at the beginning and end will make the algorithm run more slowly than it otherwise would have.

Arnavion 7y ago
It's already questionable for a search algorithm to require the ability to write to the array it's searching in, but it's even worse if it wants to be able to extend and shrink the array to do so. Edit: I haven't read the book. Presumably it gives some context for the algorithm that you only bring it out in the specific situation where it makes sense to use it.

ape4 7y ago

I'm actually shocked that Knuth writes DD MMM, YYYY

random42 7y ago
Why? Its the most unambiguous one.
- RandomGuyDTB 7y ago
  YYYYMMDD in my experiences is best for file sorting.

benchplz 7y ago

did you cash it?

chaostheory 7y ago

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

Lowkeyloki 7y ago

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.

deleted 7y ago
[deleted]
basitmakine 7y ago
It's not a real check though. He stopped sending real once in 2008 according to the article.
- Lowkeyloki 7y ago
  That's weak. Now he's just printing Monopoly money.
zaarn 7y ago
Now that's just mean for no good reason.

nathankunicki 7y ago

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. 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. Therefore I find great joy in seeing the words "Bank of San Seriffe". I giggled quite a lot at this. :) Ps. This description is probably entirely wrong. It's just how I always pictured him as a result of reading that article.

svat 7y ago
His first publication, as a high-school student, was in MAD magazine. His books are full of jokes, both highly technical ones and more trivial ones. :-) If you have some mathematical inclination and a couple of hours to spare, you may like watching his (1-hour) Christmas lecture from 2017: https://www.youtube.com/watch?v=BxQw4CdxLr8 https://www.youtube.com/watch?v=BxQw4CdxLr8 — you may need to listen carefully (he's over 80 after all), but some of his humour comes through at moments.
kontorStol 7y ago
I recommend this video to you: Oral History of Donald Knuth Part 1 and 2: https://www.youtube.com/watch?v=Wp7GAKLSGnI https://www.youtube.com/watch?v=Wp7GAKLSGnI on The Computer History Museum Youtube channel. It's a _really_ long interview, +7 hours. But it's also superb. He is interviewed by his friend and colleague Edward Feigenbaum who does a stellar job. He brings out the human Donald Knuth in a remarkable way. It gave me great respect and admiration for Donald Knuth life and achievements. For me I dare to say it was transformative in regards to human pursuit of knowledge, passion and what it means to be a intellectual human being. td;dr: Watched a Donald Knuth interview and got a nerd crush

jtlienwis 7y ago

I had a comp sci prof back in the early 1970'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't.

crypster 7y ago

Did you mean Knuth Cheque?

peter303 7y ago

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

jcl 7y ago
In case it wasn't clear from the article, it's not a real check. (But certainly worthy of framing.) https://www-cs-faculty.stanford.edu/~knuth/news08.html https://www-cs-faculty.stanford.edu/~knuth/news08.html

warmfuzzykitten 7y ago

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. Um, shouldn't the check be done before accessing the current one?