Which PRNG is suited for a functional usage?

Question

This question is motivated by usage of a PRNG in Scala, but the answer can very well be language agnostic.

Problem

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

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

Here, S is the internal state of the PRNG (call it seed or whatever) and the method returns the desired random value plus the modified state.

What I need

Best would be an implementation. But I can do this easily by myself. A very simple implementation using Java's built-in PRNG would be:

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

or a bit more dangerous and less wasting

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

What I truly need is a PRNG algorithm with good quality, small state and quick calculation. Mersenne Twister has a state of 600+ bytes. Note, that the state has to be copied in every step. So, is there something smaller?

Is there some kind of comparison of PRNG algorithms?

Answer 1

You don't need a functional implementation to get a functional interface.

You could represent your function PRNG as just a Stream of numbers generated by the Java PRNG---or any other stateful PRNG. As you explore the stream, it automatically calls the Java PRNG and remembers the result.