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

71–80 of 149 posts

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

#71

Post by hackermailman »

userbinator wrote: post #57
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…

That book seems quite highly recommended but I remember glancing through it and even the US edition had lots of seemingly random but consistent capitalisation errors in the code examples, like someone had autocorrect/autoformat turned on throughout, which IMHO is enough to make me not recommend it --- it's already hard enough for a beginner to use correct code, nevermind code with such errors.

It worked well for my goal of satisfying the prereqs of Knuth that the reader is expected to have written a few programs already, which I presume means writing in an assembly language. Another book that could be used instead is 'Computer Organization and Design: The Hardware Software Interface (RISC-V Edition)' and MIT has lectures for it on youtube https://6004.mit.edu/web/spring19/resources/lectures should anybody else want to learn.

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

#72

Post by lisper »

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

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

#73

Post by Arnavion »

lisper wrote: post #72

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

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.

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

#74

Post by blitmap »

lisper wrote: post #72

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

I wish I could find a good text that talks about how removed from 'directly executing on hardware' you are. Modern [x86] processors are (as described) executing very much out of order or calculating things in parallel. I wish I could find something that spoke to the whole field of tricks at play. I'm sure there's a great depth of indirection I'll never understand.

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

#75

Post by Sharlin »

sokoloff wrote: post #68
Tomte wrote: post #48

Earlier quoted context omitted.

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

Unless that German guy actually lives in the US, I'm surprised he was actually able to a) cash an American cheque somewhere and b) not have to pay an exorbitant service fee for cashing it. Cheques are approximately as common as unicorns in Europe.

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

#76

Post by Arnavion »

Someone wrote: post #63
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…

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

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

The sentinel needs to be identical to the value you're searching for, otherwise you're trading "compare a pointer" for "compare a value with an arbitrary equality implementation" which is no better (and probably worse).

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

#77

Post by vidarh »

jaredsohn wrote: post #28
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…

Thanks everyone; I actually heard of this algorithm before but wasn't thinking of it today and missed this when I wrote the above post. >It's not clear to me how you're supposed to "tack the item on to the end of the array", though The algorithm mentions pointers so I think it means temporarily change a value in memory that is after the array with the array value. I'd be worried about how this would work if there are…

It'd be problematic for some operations, but if your access is dominated by reads, then setting aside an extra entry for a sentinel value 'only' requires serialising operations that needs the sentinel value and mutations. You'll need to protect against mutations during the search anyway, so then it boils down to if its better to wait or fall back to a bounds-checking version.

Though I'd question if it's worthwhile vs. some unrolling (you might even have a use for Duffs device...) to just do whatever number of iterations you want per bounds check.

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

#78

Post by chx »

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…

Editing is incredibly hard -- your brain tends to see what should be there and not what's there. Good copyeditors read syllable by syllable to break this up. (I am a tech editor, not a copy editor.)

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

#79

Post by lukasm »

dchest wrote: post #40
Someone wrote: post #9

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

> Were Soviet universities at the time closed over Christmas No, Christmas was not an official holiday. Also, it's on the 7th of January.

25th of Dec is 7th of January in the common Gregorian calendar.
Post reply on HN