On Tue, Aug 16, 2011 at 17:07, James Cook wrote:

On Aug 16, 2011, at 4:04 PM, Evan Laforge wrote:

...

I've noticed there's a convention to put modules having to deal with randomness into System.Random. I thought System was for OS interaction? Granted getting a random seed usually means going to the OS, but isn't the rest of it, like generating random sequences, distributions, selecting based on probability, shuffling, etc. all non-OS related algorithms?

System definitely does seem like an odd choice. In most cases the only interaction any PRNG, even when accessed via the FFI, has with the "system" is - as you say - to get an initial seed value for a global instance.

I'd be tempted to guess that the whole reason it's under System is the IO component. -- brandon s allbery allbery.b@gmail.com wandering unix systems administrator (available) (412) 475-9364 vm/sms

I don't like the idea of Data.Random because random numbers use ordinary number types, and the generator itself is not the object of interest, the numbers are. I'd much prefer Math.Random. As the Math prefix isn't used in the core libraries maybe Control.Random is the least unpalatable alternative. Regards, Niklas

Hi all, I'm the maintainer of random. If people could decide on what the alternative name would be we could put it through the library proposal process. It seems that one problem at this moment is the lack of a single, clear "right" answer. Replacing one debatable not-quite-right choice with another may not be satisfying ;-). Also, what Thomas says is right. The current implementation is SLOW and WEAK, which would not seem to make a good default implementation. The goal is to replace it with something better so that the default random package is strong in at least one dimension. I think this is important because I imagine many people use the default package, for example because they don't want to scour hackage and try all the alternatives. My proposal for this has been to use AES based crypto-prng. I think that is fast enough (i.e. faster than what's currently there), very strong, and splittable. New Intel and AMD hardware has hardware support for AES which makes it even faster. The intel-aes package provides this functionality, with and without hardware support. But there's work left to do in terms of testing, making sure its cross platform, etc. Anyone who's interested in helping (especially with Windows support) would be warmly welcomed! Cheers, -Ryan On Wed, Aug 17, 2011 at 4:46 AM, Ertugrul Soeylemez wrote:

Brandon Allbery wrote:

...

...

...

I've noticed there's a convention to put modules having to deal with randomness into System.Random. I thought System was for OS interaction? Granted getting a random seed usually means going to the OS, but isn't the rest of it, like generating random sequences, distributions, selecting based on probability, shuffling, etc. all non-OS related algorithms?

System definitely does seem like an odd choice. In most cases the only interaction any PRNG, even when accessed via the FFI, has with the "system" is - as you say - to get an initial seed value for a global instance.

I'd be tempted to guess that the whole reason it's under System is the IO component.

That's not really valid, is it? After all the new 'time' package is also stationed under the Data tree, and it has a similarly large IO component. I have to say, it seems very intuitive to me to look for it under Data, even though I'm not sure why. Probably I'm just used to it. Time has a strong connection to the operating system and the hardware, so it could just as well go into the System tree. For (non-cryptographic) randomness however we are dealing with numerical data, for which the connection to the system is mere convenience, so I wouldn't mind finding it under Data at all.

Greets, Ertugrul

-- nightmare = unsafePerformIO (getWrongWife >>= sex) http://ertes.de/

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

The problem with Mersenne twister is that it doesn't split well. The main reason for crypto prng in this package would not be to advertise to people that "System.Random can be used for security-related apps" *but to make splitting reasonably safe*. It's not good enough to have a known-bad generator under splitting provided as the default. And I think we need splitting, especially as more Haskell programs become parallel. Would it address your concerns to not mention the crypto nature of the standard implementation in the System.Random documentation? I think there's also a reasonable argument to lean towards *correctness* over performance in Haskell's defaults. For example, unconstrained Num bindings default to Integer and likewise random numbers could be as strong as possible by default, and those looking for raw rands/sec throughput could make other informed choices. 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: http://hackage.haskell.org/package/mersenne-random-pure64-0.2.0.3 Please also see Burton Smith's comments below in response to my proposal to offer a MT + AES combination. Best, -Ryan ---------- Forwarded message ---------- From: Burton Smith Date: Tue, Jun 28, 2011 at 1:28 PM Subject: RE: AESNI-based splittable random number generation for Haskell To: "Newton, Ryan R" 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 On Wed, Aug 17, 2011 at 12:26 PM, Ertugrul Soeylemez wrote:

Ryan Newton wrote:

Using a cryptographically strong random number generator here is probably a very bad idea. Two reasons:

Firstly while being faster than the current implementation an AES-based implementation will still be considerably slower than the Mersenne Twister algorithm. This may or may not be true, if hardware AES support is there, but don't just assume that everybody has AES instructions now. For example I don't have them.

Secondly there is no standard requiring that the default random number generator is cryptographically safe. Changing this particular implementation, which is the one most people use, to a CSPRNG will make people take for granted that System.Random is safe to use in security-related products, because it would be very convenient. This will render strong security products trivially weak, when compiled with the wrong Haskell distribution, and you will find packages with statements like: "We assume that you use Ryan Newton's distribution of the random package."

I would rather propose the Mersenne Twister as the default random number generator. You could add AES as a secondary generator for people requiring cryptographic strength, but then do it properly, i.e. impure, because most people, when reading about a PRNG with "AES" anywhere in its name, will just assume that it's a CSPRNG.

Greets, Ertugrul

-- nightmare = unsafePerformIO (getWrongWife >>= sex) http://ertes.de/

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

The more fundamental problem is that splitting is neither well understood nor generally safe, and as such it should not be in the basic Random class.

Would you mind elaborating? Splitting was not well-understood by the original authors of System.Random; that much is in the comments. Nor is it well understood by me. But I am under the impression that it is well understood by Burton Smith and others who have worked on the topic, and that they assure us that using AES, RNG's under any series of splits are as strong as those generated in a linear sequence. (And if you show otherwise, you have a crypto paper and quite a name for yourself.)

And I think we need splitting, especially as more Haskell programs become

...

parallel.

I do not agree here, I'm afraid.

Could you expound on this also? The people I know in the parallelism community seem to care a lot about deterministic PRNG in parallel programs. For example, the Cilk folks at MIT and Intel who I work with are *modifying their runtime system *just to get deterministic parallel PRNG. For example our in our "Monad Par" package splittable RNG will allow us to add a variant of the monad that provides randomness and transparently routes the state through the "forks" in the parallel computation, retaining the model's determinism. -Ryan

Yep, but don't conflate determinism with splitting. In the imperative world, you normally know how many CPUs you have, so you initialize one PRNG per CPU, and simply go from there; there's no need for splitting. In the parallel community, people are going out of their way to *avoid* splitting.

I'm having trouble thinking of scenarios where per-CPU does the trick. Do you mean one per pthread rather than one per CPU? In the Cilk case, you've got to deal with work stealing of course. So you want rand() to generate a result that is determined by the current stack-frame's position in the binary-tree of spawns. In the work I was referring to: http://groups.csail.mit.edu/sct/wiki/index.php?title=Other_Projects#Determin... ... they try a bunch of different methods and I can't remember if any of them split the RNG "eagerly" as they go down the spawn tree or if they just record the tree-index on the way down and then read it out when they generated randoms. (I think the latter.) Cheers, -Ryan