2011-11-16
There's no discussion, Knuth's ``The Art of Computer Program-
ming'' is great. I've read Volume 1, some years ago (when I
haven't understood most of if). Some day I'd love to have all
volumes read and standing on my book shelf. Well, that wish
seems to be common.
However, today I delt with ``Reservoir Sampling'' (aka. ``Algo-
rithm R''), described by Knuth in Volume 2. It is a fine approach
to get evenly distributed random entries from a set of unknown
size in linear time. Knuth describes the Algorithm in prose. In
the Wikipedia, [0] you find implementations in pseudo-code and in
Python. Of those three, the one in Python revealed the logic
easiest. In Knuth's prose the logic was hidden most. This remind-
ed me of mathematical notation, which distills the logic of
several pages of prose into a few lines of formulas. Nobody
wants to have mathematical topics ever again to be described in
prose, now that we have this wonderful notation. Similar for
Torniello's geometrical descriptions of his letters. They're
just too awkward to read. The many words hide the true informa-
tion.
And now Knuth. Why didn't he just write in programming code, the
most plain notation for algorithms? But no, he wrote difficult to
decifer prose.
Michi provided a reasonable answer: Knuth would like to see his
books still be read in two hundret years. As programming code be-
comes obsolete more quickly than prose, the chose prose.
[0] http://en.wikipedia.org/wiki/Reservoir_sampling
http://marmaro.de/lue/ markus schnalke