Author: Matt Taylor
Date: 12:22:12 01/24/03
Go up one level in this thread
On January 24, 2003 at 13:24:27, Dann Corbit wrote:
>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.
Hmm...perhaps apply LSB lookup stuff toward this? If there is one bit set, you
can get its index and use it to form a flipped mask with 1 << (32 - index).
Overhead with 2 bits might be too nasty, though. I'll try it out. Won't be
elegant for Athlon, but it could scream on older Intel chips.
An FFT would probably be too slow, but it's also worth working out at least for
curiousity's sake.
-Matt
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.