Author: Russell Reagan
Date: 22:03:41 01/06/03
Go up one level in this thread
On January 06, 2003 at 23:25:57, Nathan Thom wrote:
>But im sure it could be much faster in assembler, i just dont know how.
You are headed down the wrong path here. Don't worry about writing it in
assembler. Worry about using a good algorithm. For example, the code you posted
will potentially do 64 iterations through the loop to count a single bit, and
that is very innefficient. Try something like this:
int count (bitboard b) {
int c = 0;
while (b) {
b &= b - 1;
c++;
}
return c;
}
That will do N iterations, where N is the number of bits set. So if there are 5
bits set in 'b', it will go through the loop 5 times. Your version might go
through the loop 50 or 60 times depending on which bits are set.
You are assuming that your function is inefficient, and it is. Then you are
assuming that writiing it in assemler is the solution, which is an incorrect
assumption.
If your bitboards are not densely populated, just use this function I gave. If
they are more densely populated most of the time, there are other more efficient
methods of getting a population count. I don't know any off hand, but surely
someone else can post something.
I use this function (above) in my program and my program is fairly fast (fast
enough, anyway). I believe Crafty also uses that function. Don't sweat this kind
of stuff. Just find an efficient algorithm (doesn't have to be the absolute most
efficient thing known to man) and move on to more important things. No program
ever won the world championship because it had a fast popcount.
Russell
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.