Hi Eric,
> multiplying by the inverse of the golden ratio, and then taking the
> high bits of the result with a shift, narrowing of a 32- or 64-bit
> hash value down to the power-of-two number of buckets can be done more
> efficiently than computing the remainder of a division by a prime
> number.
This was true until ca. 1990. Since then, the CPUs have fast multiplication
and division instructions for integers. A remainder operation is fast
nowadays.
> In hash.c, there is nothing guaranteeing that candidate is odd on
> entry:
>
> > static size_t _GL_ATTRIBUTE_PURE
> > compute_bucket_size (size_t candidate, const Hash_tuning *tuning)
> > {
> > if (!tuning->is_n_buckets)
> > {
> > float new_candidate = candidate / tuning->growth_threshold;
> > if ((float) SIZE_MAX <= new_candidate)
> > goto nomem;
> > candidate = new_candidate;
> > }
> > candidate = next_prime (candidate);
>
> But in next-prime.c, there is this contract:
>
> > /* Return true if CANDIDATE is a prime number or 1.
> > CANDIDATE should be an odd number >= 1. */
> > static bool _GL_ATTRIBUTE_CONST
> > is_prime (size_t candidate)
> > {
> > size_t divisor = 3;
> > size_t square = divisor * divisor;
> >
> > for (;;)
> > {
> > if (square > candidate)
> > return true;
> > if ((candidate % divisor) == 0)
> > return false;
> > /* Increment divisor by 2. */
> > divisor++;
> > square += 4 * divisor;
> > divisor++;
> > }
> > }
>
> which looks like it will mis-behave when handed an even number.
You are confusing the next_prime() function with the is_prime() function.
The next_prime() function has its specification in lib/next-prime.h,
and it does *not* require that the argument be an odd number.
Bruno
