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.bloe...@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 <folk...@vanheusden.com>
To: computer-go@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@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go
_______________________________________________
Computer-go mailing list
Computer-go@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@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go
_______________________________________________
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go