next »

[dr.crow]

Most pseudo-random number generators I've seen has an api similar to this.

Code:

seed(long);
int nextInt();

From what I understand most random generators store a 64-bit or higher state inside, that's changed each time you query for the next random number. Now, I'm wondering, is there some kind of implementation of random number generation where the state transformation is reversible and you could also ask for the previous random number?

Code:

seed(long);
int nextInt();
int prevInt();

[eigenbom]

I'm sure there are some very specific RNG's that are reversible (but who know's if they are any good). Instead, you could cache every N'th generated number, e.g., every 10th:
N(0) = seed
N(10) = blah
N(20) = foo
then when you need to go backwards you can just reseed from the nearest  cached value and step through until you hit the one you're after.

Alternatively, if you only ever need the last 50 values (say), then you could just store a circular buffer with all the last values in.

[Evan Balster]

I'm going to say the general techniques for designing pseudorandom numbers make this unlikely...  But I'm not an expert and unqualified to make such a judgment.  The better question is what possible use you have for this sort of behavior.

[gimymblert]

Reversible time generation, generate forward, generate backward, ie infinite world in time and space, imagine minecraft with time travel

[eigenbom]

It would be a stateless way to reverse any system that uses them. But memory is cheap so caching every N'th number would work better.

[Evan Balster]

Hmmm...  I'm gonna say a good hashing algorithm applied to an arbitrary number is better.  As a means of generating a random deterministic value for coordinate P, its complexity is O(1) rather than O(|P|).  A random number generator can be turned into a crude hashing algorithm by reseeding it with each query, but that's a little wasteful for something like a Mersenne Twister which uses a lot of state data.

Still, I'd rather have my question answered by the OP, as there could be more interesting applications I'm not aware of.

[eigenbom]

Yeah that's a good idea. You could hash the sequence 1, 2, ..., N, to get a sequence of N decisions.

[surt]

Code:

unsigned int rand_current = time(NULL);

unsigned int rand_index(const unsigned int i)
{
   srand(i);
   return rand();
}

unsigned int rand_prev(void)
{
   return rand_index(--rand_current);
}

unsigned int rand_next(void)
{
   return rand_index(++rand_current);
}

[JakobProgsch]

Its typically a really bad idea to seed a rng for each random number. It destroys all the nice properties of the expertly designed rngs (and might be expensive). Admittedly the builtin rng from stdlib.h is usually crap already so it might not make much of a difference .

[surt]

Yes, just a simple example. Given most uses of PRNGs in games don't need terribly good quality you could probably get by with an linear congruential generator (or a couple stacked/composited) in which case the seeding is free.

[Crimsontide]

Hmmm...  I'm gonna say a good hashing algorithm applied to an arbitrary number is better.  As a means of generating a random deterministic value for coordinate P, its complexity is O(1) rather than O(|P|).  A random number generator can be turned into a crude hashing algorithm by reseeding it with each query, but that's a little wasteful for something like a Mersenne Twister which uses a lot of state data.

Still, I'd rather have my question answered by the OP, as there could be more interesting applications I'm not aware of.

That's probably the best option.  You can tailor the hash function to be as complex or as simple as possible (depending on your needs) and still be sure its 100% reversible, no errors, ect...

[JakobProgsch]

Yes, just a simple example. Given most uses of PRNGs in games don't need terribly good quality you could probably get by with an linear congruential generator (or a couple stacked/composited) in which case the seeding is free.

Yeah it is cheap, but in the lcg case seeding with subsequent values is extra evil since you will get "equidistant random numbers" (example).
Luckily you can actually "invert" an lcg (a*x+c mod m) if gdc(a,m)==1 (no guarantee for my implementation begin completely bugfree though) proof that it works:

Code:

template<class T>
T mod(T a, T b)
{
    a %= b;
    return a>0?a:a+b;
}
 
void ext_euclid(int64_t a, int64_t b, int64_t *lastx, int64_t *lasty)
{
    int64_t x = 0;
    int64_t y = 1;
    *lastx = 1;
    *lasty = 0;
    int64_t q, r;
    int64_t tmp;
    
    while (b != 0)
    {
        q = a / b;
        r = a % b;
        tmp = x; x = *lastx - q * x; *lastx = tmp;
        tmp = y; y = *lasty - q * y; *lasty = tmp;
        a = b; b = r;
    }
}

class ReversibleLCG {
    int64_t x;
    int64_t a;
    int64_t m;
    int64_t c;
    int64_t ainverse;
public:
    ReversibleLCG(int seed) : x(seed), a(1103515245), m(1u<<31u), c(12345)
    {
        int64_t x, q;
        ext_euclid(a, m, &x, &q);
        ainverse =  mod(x, int64_t(m));
    }
    unsigned int next()
    {
        return x = (a*x + c) % m;
    }    
    unsigned int prev()
    {
        return x= (ainverse*mod(x - c, m)) % m;
    } 
};

[Fallsburg]

If you don't need a strong pseudorandom number generator, a lot of hashing functions should supply enough randomness.

[BleakProspects]

If you want, you could use 1-D perlin or simplex noise with a very high frequency, as it has this property. However, you will quickly run into problems with repeated values, and of course neither of these is uniformly random.

[JakobProgsch]

If you want, you could use 1-D perlin or simplex noise with a very high frequency, as it has this property. However, you will quickly run into problems with repeated values, and of course neither of these is uniformly random.

Also considering those depend on a hash function to get their "random values" to interpolate you might as well just use that hash function to begin with :D.

[Evan Balster]

What I was getting at in my last post is that for any given random generator this function:

Code:

int deterministicRand(int i)
{
   srand(i);
   return rand(i);
}

Is really nothing but a slow, potentially poor-quality hashing algorithm.  There's no need to involve a sequential, state-based pseudorandom number algorithm here.

[JakobProgsch]

potentially poor-quality hashing algorithm.

If rand is a linear congruential generator (which default rand functions often are) its not only poor, its catastrophically bad. Its pretty much equivalent to:

Code:

unsigned deterministicRand(unsigned i)
{
   return i*SOME_LARGE_INTEGER;
}

[dr.crow]

The reason I asked was because I was playing with landscape fractals a while ago, and I remember thinking that something like this would have been very handy, and that I could probably make it myself.

My understanding is that most rngs are designed for use in cryptography where the requirements for randomness are kind of overkill compared to how you would usually use the numbers in games.

JakobProgsch, your reversible lcg seems very interesting, though I don't understand everything.
I'm a little rusty with my discrete mathematics, could you help me out?

This is my attempt at reversing lcg:

Code:

x' : next int
x  : current int
a and m is relatively prime

from next int:
x' ≡ a * x + c  (mod m)

trying to reorder:
x' - c ≡ a * x (mod m)
ainverse * (x' - c) ≡ ainverse * a * x ≡ x (mod m)

which should mean
prevx = mod(ainverse * (x - c), m);

while you have:
prevx = (ainverse * mod(x - c, m)) % m;

is this the same? Or could you help me point out what's wrong with my derivation?

Also according to wikipedia it is recommended to discard some of the least significant bits from x before using it as a random number. Just thought somebody might be interested in case they use your implementation.

Kind of as a side question, has anyone had issues with lcg not being random enough when using it in games?

[Columbo]

"Kind of as a side question, has anyone had issues with lcg not being random enough when using it in games?"

I've had situations where the lack of randomness in the lower order bits has caused problems. But I've pretty much always been able to live with crappy RNGs as long as I've got functions that can automatically give me higher order bits when I ask for small ranges.

I do usually use Mersenne twister though, but that's more for peace of mind rather than in reaction to any specific problem with simpler solutions.

[JakobProgsch]

is this the same? Or could you help me point out what's wrong with my derivation?

I think it is the same. At the moment i was just to lazy to think about the consequences of x-c potentially being negative so i added in a "safety mod".