Paul Gilmartin writes:
<begin snippet>
For pure division-method, surely. Modulo 64 merely extracts the rightmost 6
bits of the original string. But you had suggested CKSUM, then modulo. And if
CKSUM is of high quality, I'd expect
any modulus to give good results.
<end snippet>
This response may well reflect Mr. Gilmartin's expectations. It does not
reflect much understanding of elementary number theory, of hashing operations,
or of arithmetic overflow in von Neumann machines.
My patience with his dicta in the past has apparently been misunderstood. In
the future I shall exhibit none.
Beginning with von Neumann, division-method hashing has been investigated
fully, so fully that it now has little more continuing intellectual interest
than Tartaglia's cubic formula. Hashing results are affected by width, for a
mainframe by whether successive byte, halfword, fullword, or [in principle]
doubleword substrings are summed and by whether FIXEDOVERFLOW is enabled or
disabled when this is done. (Reconsidered, my comparand was perhaps
ill-chosen: Tartaglia's formula may be of some intellectual interest if one
does not know it.)
About RKFAWTF: its standard expansion in some contexts is "Read Knuth First and
We'll Talk Further". I use it with students when I judge that they need to mug
up the rudiments of a topic before we can discuss it productively.
Mr. Postpischl has confused two problems. There is that of constructing a
balanced or, better, optimal static BST given hit and "between" frequencies.
This is now straightforward; it has been rendered so by Knuth's analysis.
(Before that analysis became available several non-clots, among them Ken
Iverson, notoriously got it wrong.) There is also the different problem of
keeping a dynamic BST, one in which insertions and deletions are ongoing,
balanced or compact using AVL rotations or the like. That is less
straightforward, although it too has been explicated by Knuth. I must concede
that it is not beyond the wit of man, but in my experience post-prelims Ph.D.
candidates in computer science often have trouble getting it right. These
things said, I have no wish to lump Mr. Postpischl together with Mr. Gilmartin;
he is not unseriösische;his posts are always to the point; and his comments
this time do not merit defenestration. (The archetypical one of Prague, which
was unsuccessful, anyway suggests that the operation is unreliable.).
For the archives I note that the five-character machine-instruction acronym
CKSUM is wrong; I should have written the four-character one CKSM instead.
John Gilmore Ashland, MA 01721-1817 USA
----------------------------------------------------------------------
For IBM-MAIN subscribe / signoff / archive access instructions,
send email to [email protected] with the message: GET IBM-MAIN INFO
Search the archives at http://bama.ua.edu/archives/ibm-main.html
