Computer Chess Club Archives




Subject: Can Someone Rename This Thread? (was: is the

Author: fca

Date: 10:27:23 08/06/98

Go up one level in this thread

On August 04, 1998 at 15:57:37, Robert Hyatt wrote:

>On August 04, 1998 at 12:15:45, Bruce Moreland wrote:
>>On August 04, 1998 at 11:34:15, Robert Hyatt wrote:
>>>The most direct way of probing a table of N words, where N is not an
>>>exact power of to is this:
>>>address=key % N;
>>>where % is the "modulo" operator in C.  if N is an exact power of 2,
>>>you can replace this by
>>>address=key>>(log2 N);
>>The compiler should know what to do if you use a constant value of N.  If you
>>don't, you can subtract one and complement it someplace ( N = ~(N-1) ), and then
>>just say
>>address = key & N
>>This is splitting hairs though.
>I do the latter, because my hash size is dynamic.  But key&mask only works
>if this is a power of two, of course, which is why the % operator is needed
>for oddball hash sizes.

Trying to split the split hair, would it be faster still (however minutely) to
have different bits of probing code to cover the (0) 2^n and the (1) oddball
case, as determining the 0/1 "typing" of the max. hash size need only be done
when it changes?

Or have I missed something, which is more likely?

Also, is it implicit that the drawback of slightly slower probing is outweighed
by the advantage of excess hash over a 2^n threshhold?  Or is there a region
(0,k) above a 2^n threshhold where it is better to leave the hash at 2^n rather
than at k+2^n?

Or have I missed something here too, which is more likely?

Kind regards


PS: apologies as my terminology is doubtless non-std.

This page took 0 seconds to execute

Last modified: Thu, 15 Apr 21 08:11:13 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.