Reversible pseudo-random sequence generator

Question

I would like some sort of method to create a fairly long sequence of random numbers that I can flip through backwards and forwards. Like a machine with "next" and "previous" buttons, that will give you random numbers.

Something like 10-bit resolution (i.e. positive integers in a range from 0 to 1023) is enough, and a sequence of >100k numbers. It's for a simple game-type app, I don't need encryption-strength randomness or anything, but I want it to feel fairly random. I have a limited amount of memory available though, so I can't just generate a chunk of random data and go through it. I need to get the numbers in "interactive time" - I can easily spend a few ms thinking about the next number, but not comfortably much more than that. Eventually it will run on some sort of microcontroller, probably just an Arduino.

I could do it with a simple linear congruential generator (LCG). Going forwards is simple, to go backwards I'd have to cache the most recent numbers and store some points at intervals so I can recreate the sequence from there.

But maybe there IS some pseudo-random generator that allows you to go both forwards and forwards? It should be possible to hook up two linear feedback shift registers (LFSRs) to roll in different directions, no?

Or maybe I can just get by with garbling the index number using a hash function of some sort? I'm going to try that first.

Any other ideas?

Answer 1

I asked a very similar question at the tigsource forums.

Hashing

At least in games, a hash function could probably do what you want. You could do it like this

class ReversibleRNG {
    int x;
public:
    ReversibleRNG(int seed) : x(seed) {}
    int next(){return yourFavoriteHash(++x);}
    int prev(){return yourFavoriteHash(--x);}
};

Reversible linear congruential generator (lcg)

As multiple people have pointed out, an lcg is indeed reversible. In an lcg, the next state is computed like this:

x = (a * prevx + c) mod m

We can reorder this:

x ≡ a * prevx + c (mod m)
x - c ≡ a * prevx (mod m)

Since a and m are chosen to be relatively prime in an lcg, we can find the inverse by using the extended euclid's algorithm.

ainverse = extEuclid(a, m).x;
ainverse * (x - c) ≡ ainverse * a * prevx (mod m)
ainverse * (x - c) ≡ prevx (mod m)

Which means

prevx = ainverse * (x - c) mod m

If you choose m and a carefully, the algorithm can have a period of 2^64

Implementation

I did a header-only implementation of this algorithm in case anyone's interested.