Remove MSB

[bob]

Oops, you are right. I ignored that N bits are done in parallel. And without that it would of course just be O(N), as you would simply scan.

In fact, the log base 2 is equal to the msb

Yes I used:

Code: Select all

    public class BitBoardBackwardIterator: IBitBoardIterator
    {
        UInt64 bits;


        public void Reset(UInt64 bits)
        {
            this.bits = bits;
        }

        public UInt64 Next()
        {
            while (bits != 0)
            {
                int index = (int)Math.Log(bits, 2);
                UInt64 bit = ((UInt64)1 << index);

                bits &= ~bit;
                return bit;
            }
            return 0;
       }
    }

You REALLY want to use a math library function when it is called that many times? This is trivial and is FAR faster:

bits &= ~(1 << MSB(bits));

Or even better

bits ^= 1 << MSB(bits);

MSB is one instruction, shift is 1 instruction, complement is one instruction, and AND is one instruction. You will blow more than that just doing the procedure call and return.

There are fast ways to do these things. There are slow ways to do 'em. And then there are UNTHINKABLE ways of doing 'em. Little point in moving to bit boards if you are going to make everything 100x slower than it needs to be. BSF/BSR have been around since the original Intel pentium processor.

[mar]

You REALLY want to use a math library function when it is called that many times? This is trivial and is FAR faster:

bits &= ~(1 << MSB(bits));

Or even better

bits ^= 1 << MSB(bits);

MSB is one instruction, shift is 1 instruction, complement is one instruction, and AND is one instruction. You will blow more than that just doing the procedure call and return.

There are fast ways to do these things. There are slow ways to do 'em. And then there are UNTHINKABLE ways of doing 'em. Little point in moving to bit boards if you are going to make everything 100x slower than it needs to be. BSF/BSR have been around since the original Intel pentium processor.

And how would you do BSR in C#?
Actually the idea is clever, even though 64-bit integer doesn't fit in double, since it only extracts msb => potential loss of precision at lsbits is fine.

[bob]

You REALLY want to use a math library function when it is called that many times? This is trivial and is FAR faster:

bits &= ~(1 << MSB(bits));

Or even better

bits ^= 1 << MSB(bits);

MSB is one instruction, shift is 1 instruction, complement is one instruction, and AND is one instruction. You will blow more than that just doing the procedure call and return.

There are fast ways to do these things. There are slow ways to do 'em. And then there are UNTHINKABLE ways of doing 'em. Little point in moving to bit boards if you are going to make everything 100x slower than it needs to be. BSF/BSR have been around since the original Intel pentium processor.

And how would you do BSR in C#?
Actually the idea is clever, even though 64-bit integer doesn't fit in double, since it only extracts msb => potential loss of precision at lsbits is fine.

A. I would not write a chess program in C#.

B. I'm not a C# programmer, but do they not have either intrinsics or a way to get to external ASM? I certainly would not be using a math library Log2 function.

[kbhearn]

c# indeed does not have intrinsics. it's built as a high level language that is supposed to be agnostic to the hardware, not to compete with C and C++

the main alternative would be a binary search to narrow it down to a 1-2 byte region and then a lookup table. How that would compare to conversion to a floating point value and taking a log i have no idea - it might even be comparable.

[mar]

A. I would not write a chess program in C#.

B. I'm not a C# programmer, but do they not have either intrinsics or a way to get to external ASM? I certainly would not be using a math library Log2 function.

A. Agreed.
B. I'm not sure there's such thing

Actually I've investigated a bit further and Math.Log doesn't work as expected:

Code: Select all

(int)Math.Log(~(ulong)0, 2)

gives 64, not 63
Similarly for ((ulong)1 << 63)-1 you get 63, not 62.
So I should correct my statement and loss of precision is not fine; this approach is broken.
Whether it's practical for chess where bitboards are usually sparse is another question... Still I would probably look for something else.

[Dann Corbit]

Bit shift operators:
https://msdn.microsoft.com/en-us/librar ... 71%29.aspx

[Sven]

c# indeed does not have intrinsics. it's built as a high level language that is supposed to be agnostic to the hardware, not to compete with C and C++

the main alternative would be a binary search to narrow it down to a 1-2 byte region and then a lookup table. How that would compare to conversion to a floating point value and taking a log i have no idea - it might even be comparable.

At least it should be possible to put intrinsic wrapper functions into a C++/CLI library, compile them with "#pragma unmanaged", and call the real intrinsics from there. The overhead is certainly the function call overhead plus switching between managed and unmanaged code but that should still be better than all handmade C# software solutions, including those that do not work ...

[mar]

this approach is broken.

I think I found a remedy It makes it even slower and I've no idea why assuming 53 mantissa bits didn't work, but seems to work with 48: (the idea is to mask out least significant bits if we'd suffer a precision loss if input is too large)

Code: Select all

const int mbits = 48;
int bit = (int)(Math.Log(l & ~((((ulong)1 << (64 - mbits)) - 1) * Convert.ToUInt32(l >= (ulong)1 << mbits)), 2.0));

Very nice and readable One more reason to look for a different approach.
Also love the fact that you can't cast bool to integral types in C#

[petero2]

You REALLY want to use a math library function when it is called that many times? This is trivial and is FAR faster:

bits &= ~(1 << MSB(bits));

Or even better

bits ^= 1 << MSB(bits);

MSB is one instruction, shift is 1 instruction, complement is one instruction, and AND is one instruction. You will blow more than that just doing the procedure call and return.

There are fast ways to do these things. There are slow ways to do 'em. And then there are UNTHINKABLE ways of doing 'em. Little point in moving to bit boards if you are going to make everything 100x slower than it needs to be. BSF/BSR have been around since the original Intel pentium processor.

And how would you do BSR in C#?

Using De Bruijn multiplication is not that bad actually. On my computer the C# version is about 6 times slower than the C++ version that is using BSR (borrowed from crafty). This could be considered acceptable for a managed language that only supports the most basic bit manipulation instructions. It is at least a lot faster than using Math.log().

Code: Select all

class Test {
    private static int[] firstBitTable = new int[]{
        63,  0, 47,  1, 56, 48, 27,  2,
        60, 57, 49, 41, 37, 28, 16,  3,
        61, 54, 58, 35, 52, 50, 42, 21,
        44, 38, 32, 29, 23, 17, 11,  4,
        62, 46, 55, 26, 59, 40, 36, 15,
        53, 34, 51, 20, 43, 31, 22, 10,
        45, 25, 39, 14, 33, 19, 30,  9,
        24, 13, 18,  8, 12,  7,  6,  5
    };

    private static int log2(ulong x) {
        x |= x >> 1;
        x |= x >> 2;
        x |= x >> 4;
        x |= x >> 8;
        x |= x >> 16;
        x |= x >> 32;
        x += 1;
        ulong debruijn64 = 0x03f79d71b4cb0a89ul;
        return firstBitTable[(x * debruijn64) >> 58];
    }

    public static void Main(string[] args) {
        int max = System.Convert.ToInt32(args[0]);
        long sum = 0;
        for (uint i = 1; i <= max; i++) {
            sum += log2(i);
        }
        System.Console.WriteLine("sum:" + sum);
    }
}

Code: Select all

#include <iostream>
#include <cstdint>

static __inline__ int log2(uint64_t word) {
  uint64_t dummy, dummy2;
  asm(" 	 bsrq	 %1, %0     " "\n\t"
      :   "=&r"(dummy), "=&r" (dummy2)
      :   "1"((uint64_t) (word))
      :   "cc");
  return (dummy);
}

int main(int argc, const char* argv[]) {
    int max = atoi(argv[1]);
    uint64_t sum = 0;
    for (int i = 1; i <= max; i++)
        sum += log2(i);
    std::cout << "sum:" << sum << std::endl;
}

[hgm]

Conversion to double, and extracting the exponent still seems the way to go to me.