## Reversible Random Number Generator

### November 24, 2015

Some applications of random number generators. games, for instance, require that the random sequence be available to run in reverse.

This is easy to do with a simple linear congruential random number generator, which is characterized by the formula `next = a * prev + c (mod m)`

. With a little bit of algebra, that formula can be written `prev = a`

, where a^{−1} * (next - c) (mod m)^{−1} is the inverse of `a (mod m)`

; that modular inverse always exists because the linear congruential generator requires that *a* and *m* are coprime.

Your task is to write a reversible random number generator. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

A Haskell solution.

This implements the Julia (v0.4.1) iterator protocol (methods for start, done, next). I believe each version of the generator (Gen, ForwardIter, ReverseIter) is actually stored as a single 64-bit value as long as the compiler can infer its type. So the whole thing could even be held in a register. A call to next returns both the generated value and the next state. There are no stateful objects in this implementation.

Julia for-loops use the iterator protocol implicitly, but then one gets access only to the values. To reverse the process in the middle requires access to the state, hence the explicit calls to start and next (but never done).