Path: utzoo!utgpu!attcan!uunet!husc6!ukma!uflorida!novavax!proxftl!twwells!bill
From: bill@twwells.uucp (T. William Wells)
Newsgroups: comp.lang.c
Subject: Re: Efficient coding considered harmful?
Message-ID: <143@twwells.uucp>
Date: 3 Nov 88 16:30:35 GMT
References: <3105@hubcap.UUCP> <34112@XAIT.XEROX.COM> <1700@dataio.Data-IO.COM> <8630@smoke.ARPA> <1704@dataio.Data-IO.COM> <119@twwells.uucp> <7700@bloom-beacon.MIT.EDU> <137@twwells.uucp> <8819@smoke.BRL.MIL>
Reply-To: bill@twwells.UUCP (T. William Wells)
Organization: None, Ft. Lauderdale
Lines: 37

In article <8819@smoke.BRL.MIL> gwyn@brl.arpa (Doug Gwyn (VLD/VMB) <gwyn>) writes:
: In article <137@twwells.uucp> bill@twwells.UUCP (T. William Wells) writes:
: >#define HASHSIZE 4              /* A power of two, or else! */
:
: To continue my complaint against using bitwise operators where arithmetic
: is called for, let me point out that most reasonable hashing schemes work
: best of the hash table size is NOT a power of two.

But there are also some that don't.

:                                                     Now, if you had used
: arithmetic instead of bit-diddling throughout your hashing code, most
: likely a programmer could change HASHSIZE to some useful number like 113
: and that would be all it would take to improve the hashing scheme.

But on quite a few of the hashing schemes that use a power of two,
you *can't* change the number to anything other than a power of two.
It breaks the algorithm.

Actually, I almost agree with you here: if the hash method were not
one where the size had to be a power of two, it would be incorrect to
use bitwise operators. However, the mistake would have been in making
the requirement that a tunable parameter which is not naturally
restricted to a power of two be restricted to be a power of two.  That
mistake would then be compounded by taking advantage of the bogus
restriction. (Ack, I *hate* subjunctives!)

Formulated as a general principle: if an operand in a multiply or the
divisor in a divide or mod (with the other operand being known to be a
positive number) is one which in the problem being solved is
naturally a power of two, it is reasonable to use bitwise operators to
implement the operation, provided that a #define is used to define
the number and (when needed) its log base 2.

---
Bill
{uunet|novavax}!proxftl!twwells!bill