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!
$7.68 USD
I Got a Knuth Check for 0x$3.00
11–20 of 149 posts
Re: I Got a Knuth Check for 0x$3.00
#12Slightly OT, but this whole article is about nitpicks so I don’t feel guilty... Shouldn’t the dollar sign be before the 0x?
That's apparently how Knuth writes it, so feel free to ask him. Maybe you'll get a reward too? ;-)
Re: I Got a Knuth Check for 0x$3.00
#13This 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.
Re: I Got a Knuth Check for 0x$3.00
#14Slightly OT, but this whole article is about nitpicks so I don’t feel guilty... Shouldn’t the dollar sign be before the 0x?
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
Re: I Got a Knuth Check for 0x$3.00
#15https://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.
Re: I Got a Knuth Check for 0x$3.00
#16Does 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.
Re: I Got a Knuth Check for 0x$3.00
#17> 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?
Re: I Got a Knuth Check for 0x$3.00
#18This 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
• 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 (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.)
Re: I Got a Knuth Check for 0x$3.00
#19Does 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. "…
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: ”Experienced computer programmers modify Algorithm A by placing a known elephant in Cairo to ensure that the algorithm will terminate.”)
Re: I Got a Knuth Check for 0x$3.00
#20> 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; ot…
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.