Author: Gerd Isenberg
Date: 10:25:31 07/17/03
Go up one level in this thread
On July 16, 2003 at 22:44:43, Matt Taylor wrote:
>On July 10, 2003 at 21:05:09, Russell Reagan wrote:
>
>>Thanks Gerd. This method seems approximately equal to the bsf assembler method
>>in speed on my Athlon (maybe a hair slower). Maybe this will be the fastest on a
>>64-bit cpu?
>
>Full time to compute is 10 cycles assuming cache hits. Time to bsf is 8 cycles +
>setup. On an Opteron, it is possible that this is faster than the built-in
>64-bit bsf instruction. Multiplication is faster and bsf should be 1 cycle
>slower, but I don't have access to all the details. I have a friend from AMD who
>happens to have one, and he's promised me that (eventually, time permitting) I
>can go play around with it. We'll see...
>
>I'm glad that someone was able to identify the algorithm. I knew I had seen it
>somewhere before. It is beyond my math background.
>
>Note that to do a 64-bit bitscan I am using 32-bit multiplication. There are
>multiple reasons for this. The foremost is that a 32-bit multiply is fast on our
>32-bit CPUs and even faster on an Opteron.
>
>Here's some code:
>
>int tbl[64] =
>{ 0, 31, 4, 33, 60, 15, 12, 34, 61, 25, 51, 10, 56, 20, 22, 35,
> 62, 30, 3, 54, 52, 24, 42, 19, 57, 29, 2, 44, 47, 28, 1, 36,
> 63, 32, 59, 5, 6, 50, 55, 7, 16, 53, 13, 41, 8, 43, 46, 17,
> 26, 58, 49, 14, 11, 40, 9, 45, 21, 48, 39, 23, 18, 38, 37, 27};
>
>int lsb(uint64 *bb)
>{
> uint64 bit = *bb;
> uint32 lo, high;
>
> bit = bit & -bit;
> *bb ^= bit;
>
> bit--;
>
> lo = (uint32)(bit >> 32);
> high = (uint32)(bit >> 0);
>
> return tbl[((lo ^ high) * 0x78291ACF) >> 26];
>}
>
>Happy computing!
>
>-Matt
Hi Matt,
congrats to your great work. Not only reinventing "Using de Bruijn Sequences to
Index a 1 in a Computer Word", but finding a way to do a 32-bit mul with folded
bitboard and a "super" de Bruijn! You will find the paper (ps) by Leiserson,
Prokop and Randall, 1998:
"Using de Bruijn Sequences to Index a 1 in a Computer Word"
with google in the net.
http://www.talkchess.com/forums/1/message.html?305965
looks similar to your code.
Regards,
Gerd
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.