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. >> >>bruce > > > >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 fca 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.