On January 5, 2002 02:39 am, William Lee Irwin III wrote:
> 2 or 3 shift/adds is really not possible, the population counts of the
> primes in those ranges tends to be high, much to my chagrin.
It doesn't really have to be a prime, being relatively prime is also
good, i.e., not too many or too small factors. Surely there's a multiplier
in the right range with just two prime factors that can be computed with 3
shift-adds.
> I actually
> tried unrolling it by hand a few times, and it was slower than
> multiplication on i386 (and uncomfortably lengthy).
Right, it's not worth it unless you can get it down to a handful of
shift-adds. How does 2**17 - 1 (Mersenne prime #6) with right-shift by
(16 - bits) work?
> I believe to address architectures where multiplication is prohibitively
> expensive I should do some reading to determine a set of theoretically
> sound candidates for non-multiplicative hash functions and benchmark them.
> Knuth has some general rules about design but I would rather merely test
> some already verified by someone else and use the one that benches best
> than duplicate the various historical efforts to find good hash functions.
It would be nice if you could just look up good ones in a cookbook, but you
can't, that cookbook doesn't exist.
-- Daniel - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
This archive was generated by hypermail 2b29 : Mon Jan 07 2002 - 21:00:27 EST