Magic number generation taking 17 seconds or more

[mar]

I meant using uniform_int_distribution on top of the RNG vs RNG directly.

Right, I was talking about something else. Yes it's negligible, only 16% slower with uniform dist (that's pointless anyway in this case).

[krismchess]

Where can I get a KISS PRNG examples?
And how should I find the seed numbers to them?

[krismchess]

Hi Gerd,

That's what I was exactly looking for.

Thanks!

The precondition for a good "sparse random" magic factor seems that the upper byte of the 64-bit product with the relevant occupancy mask has at least 6 bits set, so that the index distribution for all subset masks promises a good collision property. I guess the trick largely depends on properties of the used PRNG and seed. I'll suggest to profile how long it takes for every rook and bishop square, how often it loops per square in the first do while popcount loop, and how many trials are used at all per square and piece to find a destructive collision free magic.

[mar]

Where can I get a KISS PRNG examples?
And how should I find the seed numbers to them?

Bob Jenkins' pages: http://burtleburtle.net/bob/rand/smallprng.html
Alternatively you could use mine (public domain):

Code: Select all

class FastRandom
{
	inline ULong Rotate( ULong v, Byte s ) {
		return &#40;v >> s&#41; | &#40;v << &#40;64-s&#41;);
	&#125;
public&#58;
	FastRandom&#40;) &#123;
		Seed&#40;0&#41;;
	&#125;

	// generate next 64-bit random number
	inline ULong Next&#40;)
	&#123;
		ULong tmp = keys&#91;0&#93;;
		keys&#91;0&#93; += Rotate&#40; keys&#91;1&#93; ^ 0xc5462216u ^ (&#40;ULong&#41;0xcf14f4ebu<<32&#41;, 1 );
		return keys&#91;1&#93; += Rotate&#40; tmp ^ 0x75ecfc58u ^ (&#40;ULong&#41;0x9576080cu<<32&#41;, 9 );
	&#125;

	void Seed&#40; ULong val )
	&#123;
		keys&#91;0&#93; = keys&#91;1&#93; = val;
		for ( Int i=0; i<64; i++ ) &#123;
			Next&#40;);
		&#125;
	&#125;
private&#58;
	ULong keys&#91;2&#93;;
&#125;;

ULong = uint64_t, Byte = uint8_t
Passes dieharder tests, used by a couple of people for various things (a friend used it as part of a fast mesh simplification algorithm to choose edge collapses)
keys is IV and you can simply seed the internal state with std:: random generators/whatever and choose the one which works best for you.
Performance depends on the ability of your compiler to fold the rotations; IIRC clang had some problems, but I don't remember exactly.

[AlvaroBegue]

What's the problem with it taking 17 seconds? I think mine took several minutes, but I don't even have the code anymore. I took the output, hard-coded it into my program and I never need to run that code again.

[krismchess]

If there is a room for improvement why shouldn't I improve it?

What's the problem with it taking 17 seconds? I think mine took several minutes, but I don't even have the code anymore. I took the output, hard-coded it into my program and I never need to run that code again.

[krismchess]

I will try this one from Bob Jenkins' pages & your FastRandom.

Meanwhile I tried to use a KISS PRNG & the C++ <random> lib using random_device, uniform_int_distribution & mt19937_64 and found the <random> lib is consistent with 3 seconds while KISS PRNG is taking a bit longer. Full code below:

Code: Select all

   class Random {
    private:
        std::random_device rd;
        std::mt19937_64 mt;
        std&#58;&#58;uniform_int_distribution<uint64_t> dist;

    public&#58;
        Random&#40;) &#58; rd&#40;),mt&#40;rd&#40;)),dist&#40;) &#123;
        &#125;

        uint64_t next&#40;) &#123;
            return dist&#40;mt&#41;;
        &#125;
    &#125;;
// A KISS PRNG
    typedef uint64_t uint64;

    uint64 x = uint64&#40;123456789123&#41;;
    uint64 y = uint64&#40;987654321987&#41;;
    uint64 z1 = uint64&#40;43219876&#41;;
    uint64 c1 = uint64&#40;6543217&#41;;
    uint64 z2 = uint64&#40;21987643&#41;;
    uint64 c2 = uint64&#40;1732654&#41;;

    uint64 rand64&#40;);

    uint64 rand64&#40;)
    &#123;
        uint64 t;
        x = uint64&#40;1490024343005336237&#41; * x + 123456789;
        y ^= y << 21; y ^= y >> 17; y ^= y << 30; /* Do not set y=0! */
        t = uint64&#40;4294584393&#41; * z1 + c1; c1 = t >> 32; z1 = t;
        t = uint64&#40;4246477509&#41; * z2 + c2; c2 = t >> 32; z2 = t;
        return x + y + z1 + (&#40;uint64&#41;z2 << 32&#41;; /* Return 64-bit result */
    &#125;

Where can I get a KISS PRNG examples?
And how should I find the seed numbers to them?

Bob Jenkins' pages: http://burtleburtle.net/bob/rand/smallprng.html
Alternatively you could use mine (public domain):

Code: Select all

class FastRandom
{
	inline ULong Rotate( ULong v, Byte s ) {
		return &#40;v >> s&#41; | &#40;v << &#40;64-s&#41;);
	&#125;
public&#58;
	FastRandom&#40;) &#123;
		Seed&#40;0&#41;;
	&#125;

	// generate next 64-bit random number
	inline ULong Next&#40;)
	&#123;
		ULong tmp = keys&#91;0&#93;;
		keys&#91;0&#93; += Rotate&#40; keys&#91;1&#93; ^ 0xc5462216u ^ (&#40;ULong&#41;0xcf14f4ebu<<32&#41;, 1 );
		return keys&#91;1&#93; += Rotate&#40; tmp ^ 0x75ecfc58u ^ (&#40;ULong&#41;0x9576080cu<<32&#41;, 9 );
	&#125;

	void Seed&#40; ULong val )
	&#123;
		keys&#91;0&#93; = keys&#91;1&#93; = val;
		for ( Int i=0; i<64; i++ ) &#123;
			Next&#40;);
		&#125;
	&#125;
private&#58;
	ULong keys&#91;2&#93;;
&#125;;

ULong = uint64_t, Byte = uint8_t
Passes dieharder tests, used by a couple of people for various things (a friend used it as part of a fast mesh simplification algorithm to choose edge collapses)
keys is IV and you can simply seed the internal state with std:: random generators/whatever and choose the one which works best for you.
Performance depends on the ability of your compiler to fold the rotations; IIRC clang had some problems, but I don't remember exactly.

Code: Select all

[AlvaroBegue]

If there is a room for improvement why shouldn't I improve it?

I still don't understand. Are you running this search every time the engine is started? Why? Having a hard-coded table with all the magic multipliers takes exactly 3,072 bytes in my executable, and I can skip having and running the generating code.

[krismchess]

Hard coding isn't a good practice. If I can compute it in a negligible amount of time (that too one time) during startup why should I ignore it? Every time I run my engine I will have a unique set of magic's isn't it?

If there is a room for improvement why shouldn't I improve it?

I still don't understand. Are you running this search every time the engine is started? Why? Having a hard-coded table with all the magic multipliers takes exactly 3,072 bytes in my executable, and I can skip having and running the generating code.

[krismchess]

Hi Mar,

FastRandom - is really *FAST*. It goes through in 2 seconds time (consistent when I ran it for a dozen of times). Can you post some theory behind this - how it works etc.?

Also Do you allow me to use your FastRandom code in my chess engine & I'll provide this forum reference & your name in the code comments & README notes.

Many thanks.

I will try this one from Bob Jenkins' pages & your FastRandom.

Meanwhile I tried to use a KISS PRNG & the C++ <random> lib using random_device, uniform_int_distribution & mt19937_64 and found the <random> lib is consistent with 3 seconds while KISS PRNG is taking a bit longer. Full code below:

Code: Select all

   class Random {
    private:
        std::random_device rd;
        std::mt19937_64 mt;
        std&#58;&#58;uniform_int_distribution<uint64_t> dist;

    public&#58;
        Random&#40;) &#58; rd&#40;),mt&#40;rd&#40;)),dist&#40;) &#123;
        &#125;

        uint64_t next&#40;) &#123;
            return dist&#40;mt&#41;;
        &#125;
    &#125;;
// A KISS PRNG
    typedef uint64_t uint64;

    uint64 x = uint64&#40;123456789123&#41;;
    uint64 y = uint64&#40;987654321987&#41;;
    uint64 z1 = uint64&#40;43219876&#41;;
    uint64 c1 = uint64&#40;6543217&#41;;
    uint64 z2 = uint64&#40;21987643&#41;;
    uint64 c2 = uint64&#40;1732654&#41;;

    uint64 rand64&#40;);

    uint64 rand64&#40;)
    &#123;
        uint64 t;
        x = uint64&#40;1490024343005336237&#41; * x + 123456789;
        y ^= y << 21; y ^= y >> 17; y ^= y << 30; /* Do not set y=0! */
        t = uint64&#40;4294584393&#41; * z1 + c1; c1 = t >> 32; z1 = t;
        t = uint64&#40;4246477509&#41; * z2 + c2; c2 = t >> 32; z2 = t;
        return x + y + z1 + (&#40;uint64&#41;z2 << 32&#41;; /* Return 64-bit result */
    &#125;

Where can I get a KISS PRNG examples?
And how should I find the seed numbers to them?

Bob Jenkins' pages: http://burtleburtle.net/bob/rand/smallprng.html
Alternatively you could use mine (public domain):

Code: Select all

class FastRandom
{
	inline ULong Rotate( ULong v, Byte s ) {
		return &#40;v >> s&#41; | &#40;v << &#40;64-s&#41;);
	&#125;
public&#58;
	FastRandom&#40;) &#123;
		Seed&#40;0&#41;;
	&#125;

	// generate next 64-bit random number
	inline ULong Next&#40;)
	&#123;
		ULong tmp = keys&#91;0&#93;;
		keys&#91;0&#93; += Rotate&#40; keys&#91;1&#93; ^ 0xc5462216u ^ (&#40;ULong&#41;0xcf14f4ebu<<32&#41;, 1 );
		return keys&#91;1&#93; += Rotate&#40; tmp ^ 0x75ecfc58u ^ (&#40;ULong&#41;0x9576080cu<<32&#41;, 9 );
	&#125;

	void Seed&#40; ULong val )
	&#123;
		keys&#91;0&#93; = keys&#91;1&#93; = val;
		for ( Int i=0; i<64; i++ ) &#123;
			Next&#40;);
		&#125;
	&#125;
private&#58;
	ULong keys&#91;2&#93;;
&#125;;

ULong = uint64_t, Byte = uint8_t
Passes dieharder tests, used by a couple of people for various things (a friend used it as part of a fast mesh simplification algorithm to choose edge collapses)
keys is IV and you can simply seed the internal state with std:: random generators/whatever and choose the one which works best for you.
Performance depends on the ability of your compiler to fold the rotations; IIRC clang had some problems, but I don't remember exactly.

Code: Select all