gokkog@yahoo.com said:

Hi there,
--
There's a classic hash function to hash strings, where MULT is defined
as "31":

<snip>

Why MULT defined as 31? ( How about 29? 24? or 26? )

Why not find out yourself? Generic hashing routines are intended to get you
a decent spread of hashes for arbitrary data. So cook up a few million
records of arbitrary data, and see what kind of spreads you get for various
multipliers.

If you call it research, maybe you can even fool someone into paying you.

gokkog@yahoo.com wrote:
Hi there,
--
There's a classic hash function to hash strings, where MULT is defined
as "31":

//from programming pearls
unsigned int hash(char *ptr)
{unsigned int h = 0;
unsigned char *p = ptr;
int n;
for (n = k; n 0; p++) {
h = MULT * h + *p;
if (*p == 0)
n--;
}
return h % NHASH;
}

It looks like this code was probably mis-transcribed.
There's this undefined quantity `k' floating around, and
the behavior at end-of-string can only be called broken.
But that doesn't seem central to your question:

Why MULT defined as 31? ( How about 29? 24? or 26? )

It's a mixture of superstition and good sense.

First, the superstition: People who write code having
to do with hash tables apparently recall that prime numbers
are particularly "good" for them. It seems they don't always
remember just what the "goodness" was or in what connection,
but they'll throw prime numbers into the mix whenever they
can. They'll throw in prime numbers even if they're not too
sure what a prime number is! A colleague of mine once ran
across this little coding gem:

#define HASHSIZE 51 /* a smallish prime */

Second, the good sense: Suppose MULT were 26, and consider
hashing a hundred-character string. How much influence does
the string's first character have on the final value of `h',
just before the mod operation? The first character's value
will have been multiplied by MULT 99 times, so if the arithmetic
were done in infinite precision the value would consist of some
jumble of bits followed by 99 low-order zero bits -- each time
you multiply by MULT you introduce another low-order zero, right?
The computer's finite arithmetic just chops away all the excess
high-order bits, so the first character's actual contribution to
`h' is precisely zero! The `h' value depends only on the
rightmost 32 string characters (assuming a 32-bit int), and even
then things are not wonderful: the first of those final 32 bytes
influences only the leftmost bit of `h' and has no effect on
the remaining 31. Clearly, an even-valued MULT is a poor idea.

Need MULT be prime? Not as far as I know (I don't know
everything); any odd value ought to suffice. 31 may be attractive
because it is close to a power of two, and it may be easier for
the compiler to replace a possibly slow multiply instruction with
a shift and subtract (31*x == (x << 5) - x) on machines where it
makes a difference. Setting MULT one greater than a power of two
(e.g., 33) would also be easy to optimize, but might produce too
"simple" an arrangement: mostly a juxtaposition of two copies
of the original set of bits, with a little mixing in the middle.
So you want an odd MULT that has plenty of one-bits.

You'd also like a MULT that "smears" its operand bits across
as much of `h' as you can manage, so MULT shouldn't be too small
(consider the degenerate case of MULT==1). Also, MULT shouldn't
be too large -- to put it differently, UINT_MAX-MULT shouldn't be
too small. How small is "too small" depends to some extent on
the expected lengths of the strings; I suspect 31 is "too small"
if the strings are short (the values won't have time to invade
the high-order part of `h'). I think it would be wiser to choose
MULT somewhere between sqrt(UINT_MAX) and UINT_MAX-sqrt(UINT_MAX),
making sure it's odd and has lots of one-bits. Primality doesn't
seem important here -- but perhaps someone else may offer a good
reason to choose a prime. Sometimes superstition has valid roots.

Eric Sosman said:
A colleague of mine once ran
across this little coding gem:
#define HASHSIZE 51 /* a smallish prime */
<snorfl>
1 is prime, 3 is prime, 5 is prime, 7 is prime, 9 is prime, 11 is prime

Richard Heathfield wrote:

gokkog@yahoo.com said:

Hi there,
--
There's a classic hash function to hash strings, where MULT is defined
as "31":

<snip>
--
Why MULT defined as 31? ( How about 29? 24? or 26? )

Why not find out yourself? Generic hashing routines are intended to get you
a decent spread of hashes for arbitrary data. So cook up a few million
records of arbitrary data, and see what kind of spreads you get for various
multipliers.

If you call it research, maybe you can even fool someone into paying you.

Hey, Richard, you are the one who said:

"Give me a couple of years and a large research grant,
and I'll give you a receipt."

;-)

"Ancient_Hacker" <grg2@comcast.netwrites:

When picking a prime for a middling-size table, I just recall that
Knuth's MIX language (a horribly ancient IBM 650 emu-alike) also
denotes a prime in roman numerals.

I just use a decent hash algorithm. Then I can use a
power-of-two size table, saving an expensive remaindering
operation on every table search.

Ancient_Hacker wrote:

Richard Heathfield wrote:
Eric Sosman said:

A colleague of mine once ran
across this little coding gem:

#define HASHSIZE 51 /* a smallish prime */

<snorfl>

1 is prime, 3 is prime, 5 is prime, 7 is prime, 9 is prime, 11 is prime

When picking a prime for a middling-size table, I just recall that
Knuth's MIX language (a horribly ancient IBM 650 emu-alike) also
denotes a prime in roman numerals. If that's not big enough, the
International Motherhood of Multiple Marine Mammal Machinists is also a
prime.

"If 91 were prime, it would be a counterexample to your conjecture."
-- Bruce Wheeler

Chris Uppal wrote:
I wrote:
>
>
>>I have had some success using the multiplier from some "approved"
>>linear-conguential PRNG before -- even with "difficult" input data
>>such as words which are all 3-5 letters and all capitals.
>
>
I forgot to add that by "some success" I meant that I measured the
distributions of final values for a range of table sizes and found (a)
no apparent significant divergence from randomness and (b) no apparent
tendency to "resonate" with any particular sizes. That was using
real-world sized samples of real-world data.

So I used power-of-two sized hashtables, which I'm sure that Eric, as a
founder member and leading light of the Campaign To Stamp Primes,
would find pleasing -- were it not that he is also active their sister
organisation: the Campaign To Stamp Powers Two. ;-)

Superstition! Fight it everywhere! Join the Society to
Suppress Multiples of Unity!

Richard Heathfield wrote:
1 is prime, 3 is prime, 5 is prime, 7 is prime, 9 is prime, 11 is prime
<T>1 is not prime, the first prime number is 2, the only even prime. The
definition of a prime number is: "has excatly 2 distinct divisors, 1 and
itself".</T>

gokkog@yahoo.com wrote:

Eric Sosman wrote:
>
>
>It looks like this code was probably mis-transcribed.
>>There's this undefined quantity `k' floating around, and
>>the behavior at end-of-string can only be called broken.
>>But that doesn't seem central to your question:
>>
>
int k =2; /*defined before the function, from the book: programming
pearl*/

I still think it's mis-transcribed. Either that, or it's
not intended as a hash function for strings, but for groups of
k strings stored consecutively (first character of second string
right after the '\0' of the first, and so on).

Next time you post a code snippet, consider including a
brief description of what it's supposed to do. If you don't,
people will have to guess about the intent of the code and
may guess wrong. "//from programming pearls" does not qualify
as a specification

In article <NJydnaSG_LkNQ5LYnZ2dnUVZZ2d@comcast.com>, Eric Sosman <esosman@acm-dot-org.invalidwrites:
A colleague of mine once ran
across this little coding gem:

#define HASHSIZE 51 /* a smallish prime */

Well, at least it's smallish, for suitable definitions of "ish".

How small is "too small" depends to some extent on
the expected lengths of the strings; I suspect 31 is "too small"
if the strings are short (the values won't have time to invade
the high-order part of `h').

Depends on the size of the hash value, of course. If this is used
to calculate a 16-bit hash, then any string of at least two printable
ASCII characters affects both bytes of the value, any string of
at least three printable ASCII characters affects at least the lower
15 bits, and any string of at least three ASCII non-whitespace
printable characters affects all 16 bits.

If it's used to calculate a 32-bit hash, then even relatively short
strings like "abcdef" (in ASCII) affect all 32 bits.

I think it would be wiser to choose
MULT somewhere between sqrt(UINT_MAX) and UINT_MAX-sqrt(UINT_MAX),
making sure it's odd and has lots of one-bits. Primality doesn't
seem important here -- but perhaps someone else may offer a good
reason to choose a prime.

Well, if you're not using the whole range of hash values - if you're
taking the value modulo hash table size - then you want MULT to be
relatively prime to the modulus. For example, say MULT is 6 and your
table size is 15; you'll tend to get clumping around every third
bucket, because 3 is a common factor.

Sometimes the hash table size is fixed, but if it's variable, then
you'll want to choose MULT so that it's unlikely to share factors
with the modulus. Making MULT a prime that's not too small will do
the trick; for most applications, it seems unlikely that the hash
table size will be a multiple of 31.

That's my guess, anyway.

That said, I suspect you're right, and using a prime in this sort
of application may often owe as much to cargo-cult programming as
to real analysis. I note that this construct is basically a
linear-congruential PRNG with a variable increment, and primality
isn't a requirement for the multiplier in a good LCPRNG. Most of
the multipliers listed in the table of "good" LCPRNG parameters
in Schneier's _Applied Cryptography_ are composite.

Logan Shaw <lshaw-usenet@austin.rr.comwrites:
To put it another way, is there any modern processor (even an
embedded processor) where "mod" is actually more expensive than
"and"?
Please name a processor on which "mod" and "and" have the same
cost.

Ancient_Hacker wrote:
Logan Shaw wrote:
To put it another way, is there any modern processor (even an
embedded processor) where "mod" is actually more expensive than
"and"?

I would suggest that there is basically no processor anywhere where
that isn't true. From Cray vector processors to digital watches -- its
the same deal.

[] I agree the former takes more silicon, but it seems
like most chips have gone ahead and devoted the silicon to it
to make it fast.

- Logan

most CPU's nowdays have at least two integer and fp divide units,

Excuse me? The Alpha processor had a single multi-staged integer
divide unit (i.e., it could compute about 4 bits of integer result per
clock), because those guys were macho. I'm not sure if there are any
others that you could classify as a high performance CPU.

In general CPUs reuse many of their other functional units
(specifically their multipliers and adders) to simulate a divide over
multiple clocks. In fact, most CPUs only provide a floating point
division state machine and use it to generate the integer divide. Its
just a matter of making the most use out of your transisters. The
moment you try to make a divider in your CPU microarchitecture, it
becomes a better idea to turn those transistors into extra multipliers
and adders (on average there will just be a bigger performance impact
for doing so). I.e., it never has been, and never will be a
particularly good idea to make a custom divider, and as a consequence
it will never come down to a single clock (or 2); which I don't think
is possible anyways.

In the Itanium, for example, rather than making a division unit, they
decided to make two parallel multiply and add units instead. Its
clearly better to do things that way.

[] and
can do a divide in two clock cycles, and overlapped with other
operations as well.

CPU manufacturers have, at various times, done clever things with their
divide mechanisms -- but escaping their inevitable slowness is not one
of them. About the fastest dividers in existence are the SIMD
reciprocal dividers in the latest x86 processors that can compute 4
parallel 32-bit floating point approximate results in about 12 clocks.
But you can't shrink the 12 clocks, you can't get fully IEEE accurate
results, and you can't get fewer than 4 of them done at a time (except
by ignoring the extra ones you compute.) It certainly isn't going to
help you compute an isolated integer modulo.

The AMD Athlon did a neat thing where they would allow other FP
instructions to use the few dead slots in the FPU while it executed the
microcode for its division. But this does nothing for serial
calculations such as computing the offset into a hash (the software
just has to wait for the result before it can proceed.)

[] So divide and mod are not the 48-cycle monsters
they were just a few silicon generations ago.

Well good ones are about 20 clocks (the Grahm-Smidt formula is an
ingeneous way of reducing a divide to a critical path of about 5 serial
floating point operations). But its *really* hard (and not worth the
effort) to get them to go any faster.

Richard Heathfield wrote:
Eric Sosman said:
>
>A colleague of mine once ran
>across this little coding gem:
>>
>#define HASHSIZE 51 /* a smallish prime */
>
<snorfl>

1 is prime, 3 is prime, 5 is prime, 7 is prime, 9 is prime, 11 is prime

No. A prime is evenly divisible only by itself or unity (1). 2 is prime.
9 isn't prime. Did I miss something?

Joe Wright <joewwright@comcast.netwrites:

Richard Heathfield wrote:
>Eric Sosman said:
>>
A colleague of mine once ran
across this little coding gem:

#define HASHSIZE 51 /* a smallish prime */
><snorfl>
>1 is prime, 3 is prime, 5 is prime, 7 is prime, 9 is prime, 11 is
>prime
>>
No. A prime is evenly divisible only by itself or unity (1). 2 is prime.
9 isn't prime. Did I miss something?

The joke.

Joe Wright said:

Richard Heathfield wrote:
>Eric Sosman said:
>>
A colleague of mine once ran
across this little coding gem:

#define HASHSIZE 51 /* a smallish prime */
>>
><snorfl>
>>
>1 is prime, 3 is prime, 5 is prime, 7 is prime, 9 is prime, 11 is
>prime
>>
No.

Really?

A prime is evenly divisible only by itself or unity (1).

That definition is inadequate, since it fails to exclude negative numbers
and fractions from the universe of discourse. (3 is divisible by -1 and -3,
so by your definition it is not prime. If you then say "well, not
negatives, obviously", you still have to face 3/2, which fits your
definition nicely, and yet is not prime.)

Also, your definition is insufficient to the necessary task of excluding 1
from primality.

2 is prime. 9 isn't prime. Did I miss something?

Yes.