I had thought that maybe we could bifurcate the "stdgen" concept into a fast and a strong version, which could be say Mersenne Twister and AES respectively. But, again, the problem comes if the fast version is expected to be splittable as well.
With "SplittableGen" factored out from "RandomGen" I suppose it would be possible for the fast version to NOT offer splitting. However, Mersenne Twister is best used with an imperative interface, you can see the tension in the pure version of the mersenne package on hackage:
Please also see Burton Smith's comments below in response to my proposal to offer a MT + AES combination.
---------- Forwarded message ----------
From:
Burton Smith <burtons@microsoft.com>
Date: Tue, Jun 28, 2011 at 1:28 PM
Subject: RE: AESNI-based splittable random number generation for Haskell
To: "Newton, Ryan R" <
ryan.r.newton@intel.com>
Mersenne Twister (MT)is a poor choice in my opinion. First, the generator state is large (2496 bytes) and it must be copied on each call to next. Split is worse; it will generate twice as many bytes per call as next will.
Second, I see no good way to guarantee independence of the two generators emanating from a split. MT is hard to initialize anyway, and giant-stepping it to define the newly split generator (as we did back in the 80's paper) is not only hard for an LFSR like MT but, worse yet, it doesn't work for Haskell or other fine-grain concurrent languages because split and next will commute. Other tree RNGs, e.g. SPRNG, have the same commutativity issue. Block ciphers address this issue head-on by reducing the split independence problem to a crypto problem.
A better choice might be some block cipher other than AES. Two possibilities are XTEA and RC4. Both are in Wikipedia. RC4 has 256 bytes of key "state", still bigger than I would like.
Another scheme is to make the number of rounds an option. With AESNI, this could scream.
Burton