Author: Dieter Buerssner
Date: 14:42:38 10/06/02
Go up one level in this thread
On October 06, 2002 at 15:23:26, Russell Reagan wrote:
>On October 06, 2002 at 07:05:04, Dieter Buerssner wrote:
>
>>/* Untested code */
Well, one should never post totally untested code ...
>>int LowBit(unsigned long long a)
>>{
>> int res;
>> __asm__ volatile("
>> movl -33, %0
>> bsfl %2, %0
>> addl 32, %0
>> bsfl %1, %0"
>> : "=q&" (res)
>> : "g" ((unsigned long)a), "g" ((unsigned long)(a>>32))
>> : "cc" /* condition code (flags register) clobbered */);
>> return res;
>>}
>
>Thanks for the code. At least I know I was on the right track. I was trying
>something similar, but I was using eax explicitly. The problem is that I was
>getting a segmentation fault with my code, and I get the same with yours.
Oops. A stupid error twice. For constants, you need the "$" in front of it. So,
instead of movl -33, %0 it must be movl $-33, %0.
Now, with a small test driver (still not very careful testing). The first loop
in main should finish in reasonable time, the second will never finish (hit ^C).
BTW. With many PRNGs the second loop will not reach a big "max value", even when
you give it years ...
Regards,
Dieter
/* Please note, the following program will never exit -
you have to interrupt with Ctrl-C or similar */
int LowBit(unsigned long long a)
{
int res;
__asm__ volatile(
"movl $-33, %0
bsfl %2, %0
addl $32, %0
bsfl %1, %0"
: "=q&" (res)
: "g" ((unsigned long)a), "g" ((unsigned long)(a>>32))
: "cc" /* condition code (flags register) clobbered */);
return res;
}
/* Just for testing, much faster high language routines are possible */
int SlowLowBit(unsigned long long a)
{
int i = -1;
while (a)
{
++i;
if (a&1)
return i;
a >>= 1;
}
return i;
}
/* A cheap but reasonable pseudo random number generator */
static unsigned long ws = 0x12345678UL;
static unsigned long zs = 0x87654321UL;
static unsigned long marrnd(void)
{
zs= 30903UL *(zs&0xffff)+(zs>>16);
ws=18000*(ws&0xffff)+(ws>>16);
return (zs<<16) + (ws&0xffff);
}
#include <stdio.h>
int main(void)
{
unsigned long long x, tries=0;
unsigned long a, b;
int r1, r2, m = -1;
/* First test with all 32 low bits set to 0 */
while (m<63)
{
a = marrnd();
x = ((unsigned long long)a<<32);
++tries;
r1 = LowBit(x);
r2 = SlowLowBit(x);
if (r1 != r2)
{
printf("error: r1 =%d, r2 = %d\n", r1, r2);
break;
}
if (r1 > m)
{
m = r1;
printf("max = %2d x=0x%16llx tries = %20llu\n", m, x, tries);
}
}
/* Now "pure" 64 bit random numbers */
m = -1;
tries = 0;
while (m<63)
{
a = marrnd();
b = marrnd();
x = ((unsigned long long)a<<32)+b;
++tries;
r1 = LowBit(x);
r2 = SlowLowBit(x);
if (r1 != r2)
{
printf("error: r1 =%d, r2 = %d\n", r1, r2);
break;
}
if (r1 > m)
{
m = r1;
printf("max = %2d x=0x%16llx tries = %20llu\n", m, x, tries);
}
}
return 0;
}
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.