By PapaFreud


2010-05-26 08:55:31 8 Comments

I would like some sort of method to create a fairly long sequence of random numbers that I can flip through backwards and forwards. Like a machine with "next" and "previous" buttons, that will give you random numbers.

Something like 10-bit resolution (i.e. positive integers in a range from 0 to 1023) is enough, and a sequence of >100k numbers. It's for a simple game-type app, I don't need encryption-strength randomness or anything, but I want it to feel fairly random. I have a limited amount of memory available though, so I can't just generate a chunk of random data and go through it. I need to get the numbers in "interactive time" - I can easily spend a few ms thinking about the next number, but not comfortably much more than that. Eventually it will run on some sort of microcontroller, probably just an Arduino.

I could do it with a simple linear congruential generator (LCG). Going forwards is simple, to go backwards I'd have to cache the most recent numbers and store some points at intervals so I can recreate the sequence from there.

But maybe there IS some pseudo-random generator that allows you to go both forwards and forwards? It should be possible to hook up two linear feedback shift registers (LFSRs) to roll in different directions, no?

Or maybe I can just get by with garbling the index number using a hash function of some sort? I'm going to try that first.

Any other ideas?

7 comments

@Udo Klein 2017-05-02 13:02:40

If a linear congruential generator is good enough use it. They are easily reversible. The point is that the reverse generator is also an LCG. LCGs can also skip in any direction (forward and backwards) very fast.

The details can be found in The Art of Computer Programming - Volume 2

In particular section 3.2.1 Page 10 Equations 6-8 of TAOCP and also exercise 5 give the desired results. In case you can not solve the exercise you can find solutions to it easily, e.g. here

@Matt Thomas 2017-01-18 19:47:27

Just reverse the order of the bits in an increasing sequence of integers. For example (with 8 bit resolution):

  • 0 <=> 0
  • 1 <=> 128
  • 2 <=> 64
  • 3 <=> 192
  • 4 <=> 32
  • etc

It's very easy to move forward and backward in the sequence, and is much much faster than invoking encryption or hash functions. It also has the benefit of generating the longest-possible sequence.

It's definitely not cryptographically-secure. Here's a scatter plot of the generated values (again with 8 bit resolution):

Scatter plot of "randomly" generated values

You can readily see patterns, although it might be "random" enough for you.

@alfC 2017-12-08 06:59:34

I don't have mathematical proof, but the resulting sequence looks like it is "subrandom". en.wikipedia.org/wiki/Low-discrepancy_sequence . Still can be useful in many applications.

@Matt Thomas 2017-12-08 14:41:24

@alfC My picture certainly looks like the Hammersley set, and Wolfram says you can generate that set by reversing the order of bits--I think that's the proof that you're right. Thanks for the link!

@alfC 2017-12-08 19:03:49

Exactly, in fact even if it were random, it would be more than reversible/bi-directional, it would be random sequence with "random access". I always wondered if such thing exists. That is skip N random number (in any diretion) in O(1).

@Matt Thomas 2017-12-09 18:09:35

@alfC If all you want is O(1) generation of the i'th number in a pseudorandom sequence, and you care nothing about its reversibility, then r(i, seed) = hash(i + seed) would do the trick; just pick your favorite hash function

@alfC 2017-12-09 19:01:47

Yes, but it is going to be subrandom, not random. I don't question that subrandom are random-access (O(1) jumps). The question I have is if there are random sequences with random-access.

@Matt Thomas 2017-12-11 12:42:21

@alfC I'm not understanding how hash(i + seed) produces a low-discrepancy sequence (with an appropriate hash function e.g. SHA256)?

@alfC 2017-12-11 16:44:45

Me neither. It is intuition, if random number could be generated that way it would not require any memory and that would be odd. If it were not subrandom it would be a bad hash. My conclusion is that hashes produce subrandom sequences when applied to programmatic sequences.

@Matt Thomas 2017-12-11 18:53:17

@alfC Allow me to restate more assertively: A cryptographically secure hash of a counter might also act as a good CSPRNG in some cases (CSPRNG = cryptographically-secure pseudorandom number generator). Note that it seems more common to use an encryption function instead of a hash function, but the principle is the same.

@Matt Thomas 2017-12-11 19:13:15

@alfC Perhaps this will help intuition: it's usually easy to refactor a function's internal state into a parameter. In other words, there's no magic that comes from a function having internal state. In the case of using a hash/encryption function to accomplish PRNG, all the state that is necessary is encapsulated in those two parameters ("i" and "seed"). Similarly, you could refactor your favorite PRNG function so that all state comes in as parameters and all descriptions of side-effects are returned from it.

@Matt Thomas 2017-12-11 19:23:49

@alfC As a toy example for my previous comment, consider this Linear Congruential Generator (a PRNG): {int seed = 1337; int rand() { seed = (4321 * seed + 2345) % 53; return seed; }. This function does the exact same thing: int rand(int seed) { return (4321 * seed + 2345) % 53; }

@alfC 2017-12-11 20:12:08

they will do the same thing if the seed is stored. Which means that there is no easy jumps. In other words, for(int i = 0; i != 1000; ++i) print(rand()); and for(int i = 0; i != 1000; ++i) print(rand(i)); will not do the same thing. I would claim that the first is random (i.e. quasi-random) and the second is subrandom. Do you agree?

@Matt Thomas 2017-12-11 23:37:36

@alfC See my reply in chat.stackoverflow.com/transcript/160976 (you have edit access)

@bobbaluba 2013-05-19 01:11:17

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.

@Jonathan Basile 2015-04-13 00:35:58

thank you @bobbaluba - I found this information very helpful. I'm not very good at math, so i tried to create a little dummy's guide to inverting modular functions - in case someone like me comes across this in the future: stackoverflow.com/questions/29569927/…

@alfC 2017-12-08 21:32:54

I have the impression that hashing sequential integers will lead to subrandom sequences. See stackoverflow.com/a/41728178/225186

@starblue 2010-05-29 12:45:13

You can also go backwards with an LCG, it is just another LCG using the inverse of the multiplier modulo the modulus, together with a suitable increment.

For your small numbers you can just use brute force to search for the inverse, in general it can be computed with an extended GCD algorithm.

Unless your game is strictly for fun, with no stakes of whatever kind involved, I would choose something cryptographically secure, such as the AES approach suggested by others. LCGs and other linear random number generators cannot withstand an intelligent adversary.

@Randolpho 2010-05-28 14:14:20

Although I agree with @BlueRaja that you should just use AES in "Counter mode", with a random or time-based start for your sequence, AES might not be available or feasible in your embedded situation.

I did find this interesting paper that discusses how to build a reversible PRNG; it's only 10 pages and has plenty of code samples. Give that at try if AES doesn't work for ya.

@BlueRaja - Danny Pflughoeft 2010-05-28 14:00:47

Encrypt the sequence 1, 2, 3, ... with any cipher and any key.

AES is available on just about every recent system out there, and is lightning fast.

@Cullen Fluffy Jennings 2010-05-28 13:58:50

Using a really simple symmetric encryption algorithm is one of the easiest ways to do this. Each random number is formed by just encrypt the previous one with some fixed key and to go backwards you just decrypt.

You might look at the RC4 - Code at http://en.wikipedia.org/wiki/RC4. You could use a much smaller key schedule to get it to all fit on an arduino.

Related Questions

Sponsored Content

23 Answered Questions

[SOLVED] Generate random number between two numbers in JavaScript

  • 2011-02-10 16:41:22
  • Mirgorod
  • 1548288 View
  • 1894 Score
  • 23 Answer
  • Tags:   javascript random

67 Answered Questions

[SOLVED] How do I generate random integers within a specific range in Java?

  • 2008-12-12 18:20:57
  • user42155
  • 4185818 View
  • 3595 Score
  • 67 Answer
  • Tags:   java random integer

32 Answered Questions

[SOLVED] How do I generate a random int number?

  • 2010-04-24 23:09:11
  • Rella
  • 2396126 View
  • 2001 Score
  • 32 Answer
  • Tags:   c# random

34 Answered Questions

[SOLVED] Generating random whole numbers in JavaScript in a specific range?

31 Answered Questions

[SOLVED] Random string generation with upper case letters and digits

  • 2010-02-13 12:23:58
  • Hellnar
  • 918405 View
  • 1384 Score
  • 31 Answer
  • Tags:   python string random

42 Answered Questions

[SOLVED] How to generate a random alpha-numeric string?

19 Answered Questions

[SOLVED] Generate random integers between 0 and 9

  • 2010-10-22 12:48:29
  • aneuryzm
  • 1973110 View
  • 1397 Score
  • 19 Answer
  • Tags:   python random integer

77 Answered Questions

[SOLVED] Generate random string/characters in JavaScript

33 Answered Questions

[SOLVED] How can I generate random alphanumeric strings?

  • 2009-08-27 23:07:24
  • KingNestor
  • 770878 View
  • 1028 Score
  • 33 Answer
  • Tags:   c# .net random

15 Answered Questions

[SOLVED] Why does this code using random strings print "hello world"?

  • 2013-03-03 04:38:06
  • 0x56794E
  • 200247 View
  • 1791 Score
  • 15 Answer
  • Tags:   java string random

Sponsored Content