## Reversible Random Number Generator

### November 24, 2015

Since we have a modular inverse function from a previous exercise, this is easy:

(define next #f) (define prev #f)

(let ((a 69069) (c 1234567) (m (expt 2 32))) (set! next (lambda (x) (modulo (+ (* a x) c) m))) (set! prev (lambda (x) (modulo (* (inverse a m) (- x c)) m))))

The two `define`

s that are re-bound inside a `let`

are the standard Scheme idiom for keeping two variables private to a cooperating set of function. Here are some examples:

`> (next 2718281828)`

3103402651

> (next 3103402651)

4281062310

> (next 4281062310)

1670430837

> (prev 1670430837)

4281062310

> (prev 4281062310)

3103402651

> (prev 3103402651)

2718281828

You can run the program at http://ideone.com/mRuFZS, where you will also see the function that performs the modular inverse. If you don’t want to use a linear congruential generator, an alternate method of solving the problem is to encrypt the numbers 1, 2, 3, … using your favorite encryption method to convert the sequential index to a random number.

Pages: 1 2

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).