Author: Sune Fischer
Date: 01:39:05 12/04/02
Go up one level in this thread
On December 03, 2002 at 23:30:50, Russell Reagan wrote:
>On December 03, 2002 at 15:50:15, Russell Reagan wrote:
>
>>bsf: 4.265 seconds
>>LSB_64: 42.968 seconds
>>LastOne(): 39.906 seconds
>>FirstOne(): 55.125 seconds
>
>I was just fooling around and wrote this one. It finished in 41.250 seconds.
>
>const int high_one_8bit[256] = {
> -1,0,1,1,2,2,2,2,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,5,5,5,5,5,
> 5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,6,6,6,6,6,6,6,6,6,
> 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
> 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
> 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
> 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
> 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7
>};
>
>int high_one_c (boardmap_t _bits)
>{
> int offset;
> int result;
>
> result = (_bits > 0xffffffff) * 32;
> unsigned int bits = _bits >> result;
>
> offset = (bits > 0xffff) * 16;
> bits >>= offset;
> result += offset;
>
> offset = (bits > 0xff) * 8;
> bits >>= offset;
> result += offset;
>
> return result + high_one_8bit[bits];
>}
>
>Perhaps there is some additional optimization that can be done here. I just
>thought this up real quick. The idea is to get rid of the 64-bit value as soon
>as possible so the rest will run faster on a 32-bit machine. No match for bsf on
>the pentium though.
>
>Maybe we could start a collection of these, with times and everything for
>different processors. I think it would be some interesting data to see all of
>these different algorithms and their results on various processors (athlon, p3,
>p4, hammer, itanium, etc.). Maybe I'll start collecting, although Gerd probably
>has a great collection going so far :)
>
>Russell
Nice :)
I also got thinking, most of the time we don't really need the least significant
bit, we just need one bit - any bit!
Should give a larger class of solutions for the problem, but whether it is
possible to make a faster algorithm I don't know.
-S.
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.