Author: Dann Corbit
Date: 10:24:27 01/24/03
Go up one level in this thread
On January 24, 2003 at 01:54:34, Matt Taylor wrote:
>On January 21, 2003 at 17:16:46, Dann Corbit wrote:
>
>>On January 21, 2003 at 17:14:08, Dann Corbit wrote:
>>
>>>http://www.cs.ucsd.edu/users/carter/Papers/focspdf.pdf
>>
>>Kang Su Gatlin's implementation of the COBRA bit reversal algorithm:
>>http://www.cs.ucsd.edu/~kgatlin/cobra.tar.gz
>
>Ok, I did have a thorough look at COBRA, and it seems that it's really optimized
>for -huge- bit sequences. By huge, I'm talking about multiple KBs and upward.
>We're dealing with 8 bytes.
>
>COBRA's handling of a word-sized flip is the following function:
>int bitrev(int x, int lgn)
>{
> int i, t, value;
>
> value = 0;
>
>
> for(i = lgn-1; i >= 0; i--)
> {
> t = 1 & x;
> value = (value | (t << i));
> x = x >> 1;
> }
>
> return(value);
>}
>
>Worst-case runtime: has to iterate a number of times equal to the number of bits
>in int. The logarithmic time version is -much- better.
What about when the board becomes sparse? Or, suppose that we have separated
bitboards into components. So our bishop bitboard has 2 bishops or so most of
the time. Same for rooks and knights. One queen (maybe held as a rook + a
bishop entry...). It might be that many of our operations are performed on
extremely sparse boards.
At any rate, a sparse method certainly has value.
Another possibility that intrigues me is to use a convolution like an FFT. Not
sure that it is worth it for a small bit sequence, and I also don't know how to
do it without using floating point. But it makes a nice gedankenexperiment.
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.