Re: [Haskell-cafe] Splittable random numbers

On Sat, Jan 22, 2011 at 12:40:04AM -0500, Ryan Newton wrote:

On Wed, Nov 10, 2010 at 11:33 AM, Lauri Alanko wrote:

...

So a naive implementation of split would be:

split g = (mkGen seed, g') where (seed, g') = random g

Just to be clear, that is the same as Burton Smith's original proposal that Simon mentioned at the outset, right? Specifically, Smith's proposal is yours instantiated with a crypto based PRNG?

Yes, I realized this in hindsight. I hadn't read Smith's proposal fully and didn't expect it to be so simple. My own interest in this discussion actually came from an OCaml project, where I needed an operation to generate new RNGs: val split : Random.State.t -> Random.State.t The obvious idea was just to create a new RNG by using a randomly generated seed: let split s = Random.State.make (Array.init 55 (fun _ -> Random.State.bits s)) However, I remembered years ago reading in the source of the Haskell Random module that splitting RNGs robustly is supposed to be an open problem so I wondered what the issue is. Since random numbers came up on the Haskell mailing list at the same time, I decided to ask. But since Burton apparently came up with the same solution, using AES in counter mode as the RNG, maybe there is no issue after all. Except perhaps performance? Is this approach less robust with a faster, non-cryptographic RNG?

So, except for the silliness of generating 128 random bits to make an Int, the following would implement the strategy using the "crypto" package on Hackage, correct?

next128 (RNG k c) = (encrypt k c, RNG k (c+1))

To my understandind that's indeed using AES in counter mode, but I'm no crypto expert. Lauri