Which PRNG is suitable for functional use?

Question

This question is motivated by the use of PRNG in Scala, but the answer may well be a language agnostic.

Problem

I want to have a functional interface for my PRNG. Currently, the PRNG implementations that I know (Java stdlib, Scala stdlib, commons math) are OO, in the sense that PRNG is a stateful object. But I prefer a purely functional PRNG, which basically has the following method:

def nextInt(state: S): (Int,S) 

Here S is the internal state of the PRNG (call its seed or something else), and the method returns the desired random value plus the changed state.

What I need

Best will be implementation. But I can do it easily myself. A very simple implementation using the built-in Java PRNG:

 def nextInt(state: Int): (Int,Int) = { val rng = new Random(state) (rng.nextInt(),rng.next()) } 

or a little more dangerous and less spend

 def nextInt(state: Random): (Int, Random) = { val newRng = state.clone (newRng.nextInt(),newRng) } 

I really need a PRNG algorithm with good quality, small state and fast calculation. Mersenne Twister has a state of over 600 bytes. Please note that the status should be copied at every step. So is there anything less?

Is there any comparison of PRNG algorithms?

Answer 1

You do not need a functional implementation to get a functional interface.

You can imagine your PRNG function as just a stream of numbers generated by Java PRNG, or any other stateful PRNG. When you examine a stream, it automatically calls Java PRNG and remembers the result.

Answer 2

Your easiest bet is Mersern Twister. It is widely used in Monte Carlo Financial Analysis and Simulations, and I even saw it on several game servers. It is also the default PRNG for a large number of languages.

Here's a pretty clear / well-commented implementation of Mersenne Twister . This is in Java, but Scala translation should be fast, and even better not needed.

The following is an implementation of Scala.

Answer 3

A very good overview and implementation for PRNG published in Knuth, TAOCP , Vol. 2, C.3.