Author: Eugene Nalimov
Date: 10:03:57 02/11/02
Go up one level in this thread
Actually, proposed algorithm does not work when there are no bits set in its
argument; that is clear from the paper, so Dann is wrong here.
Otherwise, paper looks like the typical student paper. They are making some
statements about their work, but did not bother to understand how alternative
ideas work, or what can be done to improve implementation of the alternative
ideas that was used in the comparison.
Several examples:
(1) They are using 'int' to store data in lookup tables, thus penalting LOOKUP
algorithms greatly; why not use 'char' instead?
(2) They presented results for LOOKUP16 (with *huge* lookup tables) and LOOKUP4
(with too much calculations before the lookup). I believe LOOKUP8 should be the
good compromise, but authors did not include it into the comparison.
(3) They did not try to remove poorly predicted branch from their implementation
of the LOOKUP algorithm. For example, on x86 there is no branches in the
following variant:
extern unsigned char tab[256];
unsigned Lookup8 (unsigned i)
{
unsigned b, n;
b = ((i & 0xFFFF0000) != 0);
n = b * 16;
i >>= b * 16;
b = ((i & 0x0000FF00) != 0);
n += b * 8;
i >>= b * 8;
return n + tab[i];
}
Eugene
On February 11, 2002 at 12:10:33, Dann Corbit wrote:
>On February 09, 2002 at 12:14:22, Ricardo Gibert wrote:
>
>>On February 09, 2002 at 03:07:47, Dann Corbit 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.
>>>
>>>Unless I've screwed it up a bit, it doesn't quite work right at the endpoints.
>>
>>If you take the trouble of understanding the *idea* of the algorithm, you would
>>realize that the idea is sound even if a particular incarnation in code may not
>>be.
>
>A perfect hash that maps to the right bit is obviously a commically simple idea.
> However, if the author of the original paper has not bother to make even the
>most rudimentary tests for correctness, I doubt the entire outcome of the paper.
> Is it really faster? Maybe not, if you have to model everthing correctly.
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.