Magic number generation taking 17 seconds or more

[matthewlai]

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::uniform_int_distribution<uint64_t> dist;

    public:
        Random() : rd(),mt(rd()),dist() {
        }

        uint64_t next() {
            return dist(mt);
        }
    };
// A KISS PRNG
    typedef uint64_t uint64;

    uint64 x = uint64(123456789123);
    uint64 y = uint64(987654321987);
    uint64 z1 = uint64(43219876);
    uint64 c1 = uint64(6543217);
    uint64 z2 = uint64(21987643);
    uint64 c2 = uint64(1732654);

    uint64 rand64();

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

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 (v >> s) | (v << (64-s));
	}
public:
	FastRandom() {
		Seed(0);
	}

	// generate next 64-bit random number
	inline ULong Next()
	{
		ULong tmp = keys[0];
		keys[0] += Rotate( keys[1] ^ 0xc5462216u ^ ((ULong)0xcf14f4ebu<<32), 1 );
		return keys[1] += Rotate( tmp ^ 0x75ecfc58u ^ ((ULong)0x9576080cu<<32), 9 );
	}

	void Seed( ULong val )
	{
		keys[0] = keys[1] = val;
		for ( Int i=0; i<64; i++ ) {
			Next();
		}
	}
private:
	ULong keys[2];
};

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

Mersenne Twister is relatively slow because it gives you very high quality random numbers. For most applications (like this one), you don't really need that high quality, and can get away with faster generators.

I personally always stick with MT unless profiling shows that it's a bottleneck. I haven't encountered one yet (not just in chess, but in everything I have programmed). I guess this is one such case, though, if you insist on not hard-coding.

I personally just hard code them.

[AlvaroBegue]

Hard coding isn't a good practice.

I wasn't indoctrinated into that faith. Hard coding things that might change in the future isn't a good practice, but there is no need to ever revisit your set of magics.

What I am advocating is called precomputation, and it's not something to be avoided. See https://en.wikipedia.org/wiki/Precomputation

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?

And what is the advantage of having a different set of magics in every run? Perhaps it would make it harder to reproduce bugs? I doubt it, but I can't think of a scenario --however improbable-- where it could be beneficial.

[krismchess]

I see your point. I will check this one again once I have engine code complete & make it to work first.

Hard coding isn't a good practice.

I wasn't indoctrinated into that faith. Hard coding things that might change in the future isn't a good practice, but there is no need to ever revisit your set of magics.

What I am advocating is called precomputation, and it's not something to be avoided. See https://en.wikipedia.org/wiki/Precomputation

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?

And what is the advantage of having a different set of magics in every run? Perhaps it would make it harder to reproduce bugs? I doubt it, but I can't think of a scenario --however improbable-- where it could be beneficial.

[mar]

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.

You're welcome.

Sure, it's based on a very scientific "trial and error" approach
I drew inspiration from Jenkins.
I wanted a very fast PRNG with small internal state that will still work even if it's all zeroes and with constant-time queries (=no hiccups).
I also wanted it to have very good statistical properties (thanks to dieharder which I used to test it http://www.phy.duke.edu/~rgb/General/dieharder.php).
Rotations/xor-shifts have some very neat properties.
So I used rotations and then mixed in other interesting ops.
The temporary load at the beginning is very important as it prevents pipeline stalls (otherwise performance would go to hell).
You could also fold the xor constants, I didn't want to use ull suffix because certain compiler give warnings in non-c++11 mode.

As for the period, I can't give you an exact number but I can assure you it's larger than 2^38 (I expect it to be around 2^60, perhaps more).

Like I said, it's public domain, feel free to use it, no need to give credit either.

PS: I find it shocking that even in 2015 Microsoft still uses LCG in their C stdlib as they have really poor statistical properties

[petero2]

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.

I spent a few hundred CPU hours computing my magic constants, because I wanted to optimize them to require as few cache lines as possible. In terms of increased playing strength it was not worth it, but I did it because I thought it was an interesting problem to work on.