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.

Answer 2

Using a really simple symmetric encryption algorithm is one of the easiest ways to do this. Each random number is formed by just encrypt the previous one with some fixed key and to go backwards you just decrypt.

You might look at the RC4 - Code at http://en.wikipedia.org/wiki/RC4. You could use a much smaller key schedule to get it to all fit on an arduino.

Answer 3

Encrypt the sequence 1, 2, 3, ... with any cipher and any key.

AES is available on just about every recent system out there, and is lightning fast.

Answer 4

Just reverse the order of the bits in an increasing sequence of integers. For example (with 8 bit resolution):

• 0 <=> 0
• 1 <=> 128
• 2 <=> 64
• 3 <=> 192
• 4 <=> 32
• etc

It's very easy to move forward and backward in the sequence, and is much much faster than invoking encryption or hash functions. It also has the benefit of generating the longest-possible sequence.

It's definitely not cryptographically-secure. Here's a scatter plot of the generated values (again with 8 bit resolution):

You can readily see patterns, although it might be "random" enough for you.

Answer 5

If a linear congruential generator is good enough use it. They are easily reversible. The point is that the reverse generator is also an LCG. LCGs can also skip in any direction (forward and backwards) very fast.

The details can be found in The Art of Computer Programming - Volume 2

In particular section 3.2.1 Page 10 Equations 6-8 of TAOCP and also exercise 5 give the desired results. In case you can not solve the exercise you can find solutions to it easily, e.g. here

Answer 6

Although I agree with @BlueRaja that you should just use AES in "Counter mode", with a random or time-based start for your sequence, AES might not be available or feasible in your embedded situation.

I did find this interesting paper that discusses how to build a reversible PRNG; it's only 10 pages and has plenty of code samples. Give that at try if AES doesn't work for ya.

Answer 7

You can also go backwards with an LCG, it is just another LCG using the inverse of the multiplier modulo the modulus, together with a suitable increment.

For your small numbers you can just use brute force to search for the inverse, in general it can be computed with an extended GCD algorithm.

Unless your game is strictly for fun, with no stakes of whatever kind involved, I would choose something cryptographically secure, such as the AES approach suggested by others. LCGs and other linear random number generators cannot withstand an intelligent adversary.