Reversible pseudo-random sequence generator

by

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.

More Related Contents:

  1. True random number generator [closed]
  2. Do stateless random number generators exist?
  3. SecureRandom with NativePRNG vs SHA1PRNG
  4. Looping for a random number of times java
  5. Python random.choice same output
  6. how to use if(math.random == 50)? [closed]
  7. How can I use the output of a rand function, simulating 2 die rolls?
  8. Randomly generate 4 or 5 digit Unique Codes in Subsequent Runs of the Script
  9. How do I generate random integers within a specific range in Java?
  10. Generating Unique Random Numbers in Java
  11. How to request a random row in SQL?
  12. Weighted random numbers
  13. Generate random numbers summing to a predefined value
  14. Generating random whole numbers in JavaScript in a specific range
  15. Why do I get the same sequence for every run with std::random_device with mingw gcc4.8.1?
  16. efficiently generate a random sample of times and dates between two dates
  17. Random weighted choice
  18. What’s an easy way to read random line from a file?
  19. How to generate a random number in a range (10…20) using Swift [duplicate]
  20. How to get a random line of a text file in Java?
  21. Weighted random sample in python
  22. Uniformity of random numbers taken modulo N
  23. Random number generator without dupes in Javascript?
  24. Weighted random sample without replacement in python
  25. Is there an easy way to randomize a list in VB.NET?
  26. How do I create a random String by sampling from alphanumeric characters?
  27. C++11 random numbers
  28. Vectorizing `numpy.random.choice` for given 2D array of probabilities along an axis
  29. Comparing Matlab and Numpy code that uses random number generation
  30. Maximal Length of List to Shuffle with Python random.shuffle?

Leave a Comment