Author: Dan Newman
Date: 12:58:49 02/12/02
Go up one level in this thread
On February 12, 2002 at 05:03:32, Ricardo Gibert wrote: >On February 11, 2002 at 20:23:08, Dann Corbit wrote: > >>On February 09, 2002 at 12:53:32, Ricardo Gibert wrote: >> >>>On February 08, 2002 at 17:17:26, Oliver Roese wrote: >>> >>>>Hi! >>>> >>>>http://citeseer.nj.nec.com/338945.html >>>>Hope you find it interesting. >>>> >>>>Oliver >>> >>>Yes, it is quite interesting. Thanks! >>> >>>For 32 bits, the perfect hash function x%37 instead of the minimal perfect hash >>>function (x*debruijn32)>>27 also works well. The difference is a slightly larger >>>lookup table will be needed and a division is performed instead of a >>>multiplication plus a shift. For 64 bits the modulus 67 works. >> >>Have you made a 64 bit version? I would be interested to know your benchmark >>results. > >I have and have confirmed that "division is evil". The only thing going for it >is, it handles zero without any complication, but this is not enough. I tried the x%37 trick about 6 yrs ago in my checkers program and found it made things a bit slower than the divide-and-conquer table lookup version. This was on a PPro 200 though... The BSF/BSR trick was a good deal faster than either of the two. Division is definitely evil...and table lookup too, when you can avoid it. -Dan.
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.