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

Login with username, password and session length

 
Advanced search

1038321 Posts in 41959 Topics- by 33585 Members - Latest Member: ASavary

September 02, 2014, 01:23:25 PM
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 1976 times)
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

Evan Balster
Level 10
*****


I live in this head.


View Profile WWW Email
« Reply #20 on: May 18, 2013, 08:35:26 AM »

I believe it's generally impossible to reverse a linear congruential generator.  The reason for this is that for any desirable values of a, c and m, it will be possible for multiple x to change to the same x'.  For this not to be the case, you would need to find values for these variables which result in a cycle of values of size m.  Unless you're content with c=1, that's a difficult or impossible problem...

Seriously, just try any of these hash algorithms on integer (X, Y) values.  You won't be disappointed, and it will likely outperform your proposed solution.


EDIT: found an article on full cycles in PRNGs.  Don't take that to mean this is a practical approach, though...  The presented approach is to set c to 1 and have coprime values of a and m, which isn't very random at all.
« Last Edit: May 18, 2013, 08:40:39 AM by Evan Balster » 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>
dr.crow
Level 0
***



View Profile
« Reply #21 on: May 18, 2013, 09:57:31 AM »

According to wikipedia the period of an lcg is at most m anyway so I don't see why that should be a problem. You could also choose m to be something like 2^64 which should be more than enough for most uses I can think of.

And I don't see why c should have to be 1 either. For me JakobProgsch's implementation worked just fine (he used the same parameters for m, c and g as glibc does). I did a traversal of 100000 numbers in each direction and stored them and verified that they were the same on the way back. It seems to be working.

I wrapped his implementation as a header library and did some optimizations on it:

Code:
#ifndef RLCG_HPP
#define RLCG_HPP

#include <cstdint>

namespace rlcg {

namespace details {

template<class T>
constexpr bool isPowerOfTwo(T x){
    return (x & (x - 1)) == 0;
}

//template metaprogramming implementation of extended euclid's algorithm
//bsed on recursive definition from wikipedia:
template <int64_t A, int64_t B>
struct ExtendedEuclid {
    enum {
        x = ExtendedEuclid<B, A - B * (A / B)>::y,
        y = ExtendedEuclid<B, A - B * (A / B)>::x - (A / B) * ExtendedEuclid<B, A - B * (A / B)>::y
    };
};
template <int64_t T>
struct ExtendedEuclid<T, 0> {
    enum {x = 1, y = 0};
};

//modulus M, multiplicand A, increment C, least significant bits D to discard
template<int64_t M = 1u<<31u, int64_t A = 1103515245, int64_t C = 12345, int64_t D = 2>
class ReversibleLCG {
    static_assert(isPowerOfTwo(M), "M is not a power of two as it should be");
    int64_t x;
public:
    ReversibleLCG(int seed) : x(seed){}
    unsigned int next() {
        //nextx = (a * x + c) % m;
        x = (A * x + C) & (M - 1);
        return x >> D;
    }
    unsigned int prev() {
        const int64_t ainverse = ExtendedEuclid<A, M>::x;
        //prevx = (ainverse * (x - c)) mod m
        x = ainverse * (x - C) & (M - 1);
        return x >> D;
    }
    unsigned int max() const {
        return M >> D;
    }
};

} // end namespace details

using ReversibleLCG = details::ReversibleLCG<>;

} // end namespace rlcg


#endif // RLCG_HPP

And then to test:

Code:
#include <rlcg.hpp>

#include <iostream>
#include <cassert>
#include <vector>

int main() {
        rlcg::ReversibleLCG rng(42);
        const unsigned int numtests = 10000;

        std::vector<unsigned int> forward;
        std::cout << "\nForward:\n";
        for(int i = 0; i<numtests; ++i){
                forward.push_back(rng.next());
                std::cout << forward.back() << std::endl;
        }
        std::cout << "\nBackwards:\n";
        for(int i = numtests - 2; i>=0; --i){
                unsigned int val = rng.prev();
                std::cout << val << std::endl;
                assert(val == forward[i]);
        }

        std::vector<unsigned int> backward;
        std::cout << "\nBackwards:\n";
        for(int i = 0; i<numtests; ++i){
                backward.push_back(rng.prev());
                std::cout << backward.back() << std::endl;
        }
        std::cout << "\nForwards:\n";
        for(int i = numtests - 2; i>=0; --i){
                unsigned int val = rng.next();
                std::cout << val << std::endl;
                assert(val == backward[i]);
        }
        return 0;
}
Logged
rivon
Level 10
*****



View Profile
« Reply #22 on: May 18, 2013, 11:22:23 AM »

Seriously, just try any of these hash algorithms on integer (X, Y) values.  You won't be disappointed, and it will likely outperform your proposed solution.
Murmur2 looks nice. Fast and the randomness seems quite ok when hashing numbers from 0-216k. Should work fine for the OP's problem.
Logged
dr.crow
Level 0
***



View Profile
« Reply #23 on: May 18, 2013, 11:39:15 AM »

Yup, I guess you're right. A hashing function would probably be easier in most cases. Thanks for the link, evan, looks like a good summary.
Logged
doihaveto
Level 1
*



View Profile
« Reply #24 on: May 18, 2013, 12:25:07 PM »

If we had a PRNG that only did operations that don't lose information - like bitwise-swizzles, and rotations with wrap-around - then we could reverse them easily to get a backward random number stream. Unfortunately most PRNGs are not like that, virtually all of them do irreversible operations, like mods, or multiplies that drop overflows, or bitwise shift that lose the bits that got shifted out.

I guess one could try rolling their own, using just reversible operations, and see if it has a good enough probability distribution and period...?

OTOH, someone on StackOverflow had a clever idea: you could take a cheap symmetric encryption algorithm, and use that as a reversible PRNG: to get the next value, encrypt the previous one; to get the previous value, decrypt the one in front...
http://stackoverflow.com/questions/2911432/reversible-pseudo-random-sequence-generator
Logged

Pages: 1 [2]
Print
Jump to:  

Theme orange-lt created by panic