Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

I Got a Knuth Check for 0x$3.00

nickdrozd.github.io

Post reply on HN
Print view View original

61–70 of 149 posts

Re: I Got a Knuth Check for 0x$3.00

#61

Post by mrob »

MRD85 wrote: post #60
mrob wrote: post #54

Earlier quoted context omitted.

>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. It's a small change to avoid the append. First check the final array item separately, and return success if it matches. If it doesn't match, overwrite the final array item with the desired item, and continue as before except this time checking if you're within array bound…

Do most array structures have a pointer to last element? Or similarly useful do they track length?

Not in C and similar languages, but you already need to know the length for the bounds check.

Re: I Got a Knuth Check for 0x$3.00

#62

Post by deathanatos »

edge17 wrote: post #38
hackermailman wrote: post #24

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 publis…

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.

I bought an international edition of a text in college because it was priced significantly cheaper. And indeed, it had all the same problems, but they had been re-arranged, so when the professor assigned problems "5-15", I needed to know the mapping from the US 5-15 to the international version's numbers. Which, by quickly thumbing through another student's copy, I could generate pretty rapidly, but boy was that annoying. (I might have reconsidered purchasing the international edition had this been disclosed at the time of sale…)

Re: I Got a Knuth Check for 0x$3.00

#63

Post by Someone »

mrob wrote: post #54
thaumasiotes wrote: post #25

Earlier quoted context omitted.

> 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…

>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. It's a small change to avoid the append. First check the final array item separately, and return success if it matches. If it doesn't match, overwrite the final array item with the desired item, and continue as before except this time checking if you're within array bound…

It probably is easier to reserve an array item for that sentinel marker.

In either case, it requires your array to be writable, and you’re giving up having multiple searches through the same array operating at the same time.

Also, on modern hardware, the ‘ran out of items’ check is essentially free.

Nowadays, the only realistic use for this would be a case where you have a fixed-size array that you search frequently, where the same end marker can be used all the time, so that you can add that sentinel marker once.

I’ve a hard time thinking of examples, but do not rule out cases inside OS kernels or search trees for computer chess or similar games.

A variant would be to use this in C, and, when the program allocates N+1 chars to hold a string of length strlen or strcpy calls don’t run on forever, even if a strncpy copies N+1 bytes. I don’t see how that ‘guarantee’ would add much, though.

Re: I Got a Knuth Check for 0x$3.00

#64

Post by veddox »

svat wrote: post #37
dmix wrote: post #15

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.

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 bu…

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

Re: I Got a Knuth Check for 0x$3.00

#65

Post by bredren »

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.

Re: I Got a Knuth Check for 0x$3.00

#66

Post by db48x »

thaumasiotes wrote: post #25
jaredsohn wrote: post #16

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. "…

> 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…

Yes, multi-threaded access to the array would invalidate the assumptions made when designing that algorithm, as so often happens.

And copying the array would cost more than you would save, so you would want to be sure that you don't have to do that. In general a growable array implementation will double the storage of the array (or multiply it by some other factor, such as the square root of 2) whenever it does grow it, so that it doesn't immediately have to grow it again. You could just arrange for your implementation to grow whenever there's only one storage location left, and then you could use this trick when searching it.

But recall that this algorithm was designed in a context where neither of those constraints apply.

Re: I Got a Knuth Check for 0x$3.00

#68

Post by sokoloff »

Tomte wrote: post #48
dmix wrote: post #15

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.

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)

With smartphone deposit-by-photo, you could cash the check [if it were real] and keep the check to display. (Totally agree that if you had to send it in that keeping the check is worth well more than the value of the check.)

PS: It took me way longer than it ought to have to figure out the Bank of San Serriffe joke...

Re: I Got a Knuth Check for 0x$3.00

#69

Post by neysofu »

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!

Re: I Got a Knuth Check for 0x$3.00

#70

Post by Sharlin »

krm01 wrote: post #59

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?

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.

Post reply on HN