[Computer-go] fast + good RNG

[remco.bloemen at singularityu.org]

Powers of two are easy, just take the minimum amount of bits out of your entropy.

For a generic number N

Approach 1: round up to the next highest power of two, then discard and try again if it is >= N.

This could potentially reject up to half the samples, so I have two improvements I used:

Approach 2: take 3 more bits than the next highest power of two. Reject if it is higher than  the highest multiple of N less than this larger power of two. On accept return modulo N.

Approach 3: An arithmetic decoder fed with entropy. When done with 64 bit integers it is as good as perfect in terms of bias and entropy consumption.

— Remco

-----Original Message-----
From: folkert <folkert at vanheusden.com>
To: computer-go at computer-go.org
Sent: Sun, 29 Mar 2015 18:05
Subject: Re: [Computer-go] fast + good RNG

Ah!
But how do you make sure the numbers are uniformly distributed?

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



Folkert van Heusden

-- 
MultiTail er et flexible tool for å kontrolere Logfiles og commandoer.
Med filtrer, farger, sammenføringer, forskeliger ansikter etc.
http://www.vanheusden.com/multitail/
----------------------------------------------------------------------
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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://computer-go.org/pipermail/computer-go/attachments/20150329/2b449f3b/attachment.html>