Author: Russell Reagan
Date: 11:21:07 06/12/04
Go up one level in this thread
On June 12, 2004 at 13:09:30, Gian-Carlo Pascutto wrote:
>On June 12, 2004 at 13:05:14, Sergei S. Markoff wrote:
>
>>But the result isn't impressive. This works slower than previous version. I have
>>Athlon-1700XP+ and Intel C/C++ v6 compiler (v7 produces slower code).
>>
>>What was wrong?
>
>bsf and consorts are slow on Athlons.
>
>The best thing seems to be one of the "Magic bitscans".
>
>const BITBOARD magic = 0x03f08c5392f756cdULL;
>
>const unsigned int magictable[64] = {
>0, 1, 12, 2, 13, 22, 17, 3,
>14, 33, 23, 36, 18, 58, 28, 4,
>62, 15, 34, 26, 24, 48, 50, 37,
>19, 55, 59, 52, 29, 44, 39, 5,
>63, 11, 21, 16, 32, 35, 57, 27,
>61, 25, 47, 49, 54, 51, 43, 38,
>10, 20, 31, 56, 60, 46, 53, 42,
>9, 30, 45, 41, 8, 40, 7, 6,
>};
>
>unsigned int FindFirst (const BITBOARD b) {
> const BITBOARD lsb = b & -b;
> return magictable[(lsb * magic) >> 58];
>}
>
>--
>GCP
I found this one, by Eugene Nalimov, to be the fastest on my 32-bit Athlon.
int FirstOne (Bitboard arg) {
int result = 0;
if (arg > 0xFFFFFFFF) {
arg >>= 32;
result = 32;
}
if (arg > 0xFFFF) {
arg >>= 16;
result += 16;
}
if (arg > 0xFF) {
arg >>= 8;
result += 8;
}
return result + table8[arg];
}
table8[] is an 8-bit lookup table (256 elements) that returns the 'first one'
for an 8-bit value. You can also try using a 16-bit lookup table and get rid of
the last if-statement.
This page took 0.01 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.