next »

[Evan Balster]

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.

[dr.crow]

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

[rivon]

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.

[dr.crow]

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.

[doihaveto]

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