[Computer-go] fast + good RNG

[Kahn Jonas]

Why not xorshift+128 ?

*****
include <stdint.h>

/* The state must be seeded so that it is not everywhere zero. */
uint64_t s[2];

uint64_t xorshift128plus(void) {
     uint64_t x = s[0];
     uint64_t const y = s[1];
     s[0] = y;
     x ^= x << 23; // a
     x ^= x >> 17; // b
     x ^= y ^ (y >> 26); // c
     s[1] = x;
     return x + y;
}
******

It passes even more tests of randomness than Mersenne, according to Wikipedia (easily checkable, that's BigCrush, a standard test suite, the hardest usual one), 
and is 2.5x times faster, according to a PRNG shootout, though I don't think the author is neutral on the matter.

Period is $2^128 - 1$, more than sufficient for go. (If you need longer periods, use longer keys, I guess). And the code is easy.


Jonas

> Hmm, I use just a super-naive LCG
>
>        unsigned long hi, lo;
>        lo = 16807 * (pmseed & 0xffff);
>        hi = 16807 * (pmseed >> 16);
>        lo += (hi & 0x7fff) << 16;
>        lo += hi >> 15;
>        pmseed = (lo & 0x7fffffff) + (lo >> 31);
>        return ((pmseed & 0xffff) * max) >> 16;
>
> in Pachi.  Frankly, I think I could get away with just
> 	pmseed = pmseed * 16807 + 12345;
> 	return pmseed % max;
>
> Do you really need high quality RNG in your program?  I'd be interested
> if someone using a sophisticated RNG would compare it with using just
> the above wrt. Elo strength and performance.
>
> (BTW, for floats, there's this neat trick to take advantage of the
> internal representation
>
>        union { unsigned long ul; floating_t f; } p;
>        p.ul = (((pmseed *= 16807) & 0x007fffff) - 1) | 0x3f800000;
>        return p.f - 1.0f;
>
> see also http://rgba.org/articles/sfrand/sfrand.htm)
>
> On Sun, Mar 29, 2015 at 05:58:56PM +0800, remco.bloemen at singularityu.org wrote:
>> I switched to SFMT [0].  But that was some years ago, there might be faster options now.
>>
>> I also generated it in megabyte batches and consume it from there, generating a new megabyte as needed.
>>
>> Lastly, I had some code to make sure I did not consume more bits of entropy than required.  Two uniform choices,  one bit.  Three choices: fractional bits.
>>
>> [0]
>>
>> http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/
>>
>> — Remco
>>
>> -----Original Message-----
>> From: folkert <folkert at vanheusden.com>
>> To: computer-go at computer-go.org
>> Sent: Sun, 29 Mar 2015 17:50
>> Subject: [Computer-go] fast + good RNG
>>
>> Hi,
>>
>> I measured that std::mt19937_64 (the mersenne twister from the standard
>> c++ libraries) uses about 40% cpu time during playouts.
>>
>> So I wonder: is there a faster prng while still generating good enough
>> random?
>>
>>
>> Folkert van Heusden
>>
>> --
>> Nagios user? Check out CoffeeSaint - the versatile Nagios status
>> viewer! http://www.vanheusden.com/java/CoffeeSaint/
>> ----------------------------------------------------------------------
>> Phone: +31-6-41278122, PGP-key: 1F28D8AE, www.vanheusden.com
>> _______________________________________________
>> Computer-go mailing list
>> Computer-go at computer-go.org
>> http://computer-go.org/mailman/listinfo/computer-go
>
>> _______________________________________________
>> Computer-go mailing list
>> Computer-go at computer-go.org
>> http://computer-go.org/mailman/listinfo/computer-go
>
>
> --
> 				Petr Baudis
> 	If you do not work on an important problem, it's unlikely
> 	you'll do important work.  -- R. Hamming
> 	http://www.cs.virginia.edu/~robins/YouAndYourResearch.html
> _______________________________________________
> Computer-go mailing list
> Computer-go at computer-go.org
> http://computer-go.org/mailman/listinfo/computer-go