Welcome, Guest. Please login or register.
Did you miss your activation email?

Login with username, password and session length

 
Advanced search

1066793 Posts in 43544 Topics- by 35593 Members - Latest Member: Seencent

November 26, 2014, 09:16:43 AM
TIGSource ForumsDeveloperTechnical (Moderators: Glaiel-Gamer, ThemsAllTook)Two-way pseudo-random number generation?
Pages: [1] 2
Print
Author Topic: Two-way pseudo-random number generation?  (Read 2226 times)
dr.crow
Level 0
***



View Profile
« on: May 16, 2013, 05:23:01 PM »

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();
Logged
eigenbom
Level 10
*****



View Profile WWW
« Reply #1 on: May 16, 2013, 06:45:28 PM »

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.

Logged

Evan Balster
Level 10
*****


I live in this head.


View Profile WWW Email
« Reply #2 on: May 16, 2013, 07:21:07 PM »

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

Creativity births expression.  Curiosity births exploration.
Our work is as soil to these seeds; our art is what grows from them...


Wreath, SoundSelf, Infinite Blank, Cave Story+, <plaid/audio>
Gimym JIMBERT
Level 10
*****


NOTGAMER ludophile


View Profile Email
« Reply #3 on: May 16, 2013, 08:21:42 PM »

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


ILLOGICAL, random guy on internet, do not trust (lelebĉcülo dum borobürükiss)
eigenbom
Level 10
*****



View Profile WWW
« Reply #4 on: May 16, 2013, 08:34:49 PM »

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

Evan Balster
Level 10
*****


I live in this head.


View Profile WWW Email
« Reply #5 on: May 16, 2013, 09:34:39 PM »

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

Creativity births expression.  Curiosity births exploration.
Our work is as soil to these seeds; our art is what grows from them...


Wreath, SoundSelf, Infinite Blank, Cave Story+, <plaid/audio>
eigenbom
Level 10
*****



View Profile WWW
« Reply #6 on: May 16, 2013, 10:13:02 PM »

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

surt
Level 5
*****


Meat by-product.


View Profile Email
« Reply #7 on: May 16, 2013, 11:54:33 PM »

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);
}
Logged

Real life would be so much better with permadeath.
PJ Gallery - OGA Gallery - CC0 Scraps
JakobProgsch
Level 1
*



View Profile Email
« Reply #8 on: May 17, 2013, 12:23:21 AM »

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 Smiley.
Logged

surt
Level 5
*****


Meat by-product.


View Profile Email
« Reply #9 on: May 17, 2013, 12:52:13 AM »

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.
« Last Edit: May 17, 2013, 12:57:47 AM by surt » Logged

Real life would be so much better with permadeath.
PJ Gallery - OGA Gallery - CC0 Scraps
Crimsontide
Level 3
***


View Profile
« Reply #10 on: May 17, 2013, 01:56:42 AM »

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...
Logged
JakobProgsch
Level 1
*



View Profile Email
« Reply #11 on: May 17, 2013, 02:43:28 AM »

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;
    }
};
Logged

Fallsburg
Level 10
*****


Fear the CircleCat


View Profile
« Reply #12 on: May 17, 2013, 03:25:37 AM »

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



View Profile WWW Email
« Reply #13 on: May 17, 2013, 07:08:19 AM »

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

JakobProgsch
Level 1
*



View Profile Email
« Reply #14 on: May 17, 2013, 07:10:31 AM »

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

Evan Balster
Level 10
*****


I live in this head.


View Profile WWW Email
« Reply #15 on: May 17, 2013, 09:56:36 AM »

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

Creativity births expression.  Curiosity births exploration.
Our work is as soil to these seeds; our art is what grows from them...


Wreath, SoundSelf, Infinite Blank, Cave Story+, <plaid/audio>
JakobProgsch
Level 1
*



View Profile Email
« Reply #16 on: May 17, 2013, 11:08:24 AM »

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;
}
Logged

dr.crow
Level 0
***



View Profile
« Reply #17 on: May 17, 2013, 09:50:02 PM »

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?
Logged
Columbo
Level 0
***


View Profile
« Reply #18 on: May 17, 2013, 10:14:43 PM »

"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.
Logged

JakobProgsch
Level 1
*



View Profile Email
« Reply #19 on: May 18, 2013, 01:06:53 AM »

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".
Logged

Pages: [1] 2
Print
Jump to:  

Theme orange-lt created by panic