is there a such thing as a randomly accessible pseudo-random number generator? (preferably open-source)

Question

first off, is there a such thing as a random access random number generator, where you could not only sequentially generate random numbers as we're all used to, assuming rand100() always generates a value from 0-100:

for (int i=0;i<5;i++)
   print rand100()

output: 
14
75
36
22
67

but also randomly access any random value like:

rand100(0) would output 14 as long as you didn't change the seed

rand100(3) would always output 22

rand100(4) would always output 67

and so on...

I've actually found an open-source generator algorithm that does this, but you cannot change the seed. I know that pseudorandomness is a complex field; I wouldn't know how to alter it to add that functionality.

Is there a seedable random access random number generator, preferably open source? or is there a better term for this I can google for more information?

if not, part 2 of my question would be, is there any reliably random open source conventional seedable pseudorandom number generator so I could port it to multiple platforms/languages while retaining a consistent sequence of values for each platform for any given seed?

Clinkerbuilt

What is the application? – Phraseology

a game where the player can traverse an endless randomly generated level, where he can backtrack indefinitely, and where it is desirable that the seed data for the random levels be transferable across multiple platforms. – Clinkerbuilt

Answer 1

The PCG family of psuedo-random number generators can jump forward and backward in logarithmic time (i.e. jumping forward 1000 numbers requires O(log(1000)) operations), which is probably good enough to be considered random access. The reference C and C++ implementations both support this feature.

The table on the front page of the PCG site indicates that a number of other generators can support jump-ahead, but I've not seen it in any implementations.

Valentijn

Answer 2

I've not heard of anything like that, but it seems to me you could take use a decent hash and write a wrapper function that takes a seed value and your 'index', and runs them through the hash function. I'm not sure of the randomness of the bits output by various cryptographic hash functions, but I imagine that someone has taken a look at that.

Nineteen

I agree -- use the built in randomness features of your language, and build a data structure around it, and use that like a wrapper. – Cymose

Answer 3

Blum Blum Shub is a pseudorandom number generator with a seed and random access to any value it generates.

Sandi

Answer 4

Once I read a really good blog post from a guy who used to work at Google, which answered a question very similar to yours.

In short, the answer was to use a block cipher with a random number as the encryption key, and the index of the number you want in the sequence as the data to be encrypted. He mentioned a cipher which can work on blocks of any size (in bits), which is convenient -- I'd have to search for the blog to find the name of the cipher.

For example: say you want a random shuffling of integers from 0 to (2^32)-1. You can achieve that using a block cipher which takes 4 bytes input, and returns 4 encrypted bytes. To iterate over the series, first "encrypt" a block of value 0, then 1, then 2, etc. If you only want the 1 millionth item in the shuffled sequence, you just encrypt the number 1,000,000.

The "random sequences" you will get using a cipher are different from what you would get using a hash function (as @MichaelBurr suggested). Using a cipher, you can get a random permutation of a range of integers, and sample any item in that permutation in constant time. In other words, the "random numbers" won't repeat. If you use a hash function, the numbers in the sequence may repeat.

Having said all this, @MichaelBurr's solution is more appropriate for your situation, and I would recommend you use it.

Side

Answer 5

Thanks for all the replies, and also, for anyone who might happen upon this asking a similar question, I found a solution that isn't exactly what I asked for, but fits the bill for my purposes.

It is a perlin noise class that can be found here. I'm not sure how computationally complex this is relative to a conventional random number generator, which is a concern, since one of the planned platforms is Android. Also, perlin noise isn't the same thing as pseudorandomness, but from what I can tell, a high octave and/or frequency value should provide suitable randomness for non-cryptographic purposes, where the statistical level of true randomness isn't as important as the mere appearance of randomness.

This solution allows seeding, and also allows sampling a random set from any point, in other words, random access randomness.

here's an example set of regular c++ randomness (rand%200) on the left column for comparison, and perlin noise (with the equivalent of %200) on the right:

91 , 100
48 , 97
5 , 90
93 , 76
197 , 100
97 , 114
132 , 46
190 , 67
118 , 103
78 , 96
143 , 110
187 , 108
139 , 79
69 , 58
156 , 81
123 , 128
84 , 98
15 , 105
178 , 117
10 , 82
13 , 110
182 , 56
10 , 96
144 , 64
133 , 105

both were seeded to 0

the parameters for the perlin noise were

octaves = 8
amplitude = 100 
frequency = 9999
width/height = 10000,100

the sequential sampling order for the perlin noise was simply

for (int i=0;i<24;i++)
    floor(Get(i,i)+100);
//amplitude 100 generates noise between -100 and 100, 
//so adding 100 generates between 0 and 200

Clinkerbuilt

I'm just looking for this,greatly appreciated – Jailbreak

Answer 6

One way of achieving this is to synthesize a larger amount of random data from a smaller set. One way of doing this is to have three arrays of pre-generated random data. Each array should have prime number of entires.

To produce our random numbers we imagine each of these one-time pads to be looped inifintely and sampled incrementally; we combine the data in each of them using xor.

#define PRIME1 7001
#define PRIME2 7013
#define PRIME3 7019

static int pad1[PRIME1];
static int pad2[PRIME2];
static int pad3[PRIME3];

static void random_no_init (void)
{
  static int initialized = 0;
  int i;
  if (initialized)
    return;
  for (i = 0; i < PRIME1; i++) pad1[i] = random ();
  for (i = 0; i < PRIME2; i++) pad2[i] = random ();
  for (i = 0; i < PRIME3; i++) pad3[i] = random ();

  initialized = 1;
}

int random_no (int no)
{
   random_no_init ();
   return pad1[no % PRIME1] ^ pad2[no % PRIME2] ^ pad3[no % PRIME3];
}

The code sample above shows a simple example that yields 344618953247 randomly accessible entires. To ensure reproducible results between runs, you should provide a random number generator with a seed. A more complex system built on the same principle with seed variation based on picking different primes can be found at http://git.gnome.org/browse/gegl/tree/gegl/gegl-random.c

Psychopath

The solution I presented can be considered a variation of perlin noise that is discrete and fully random rather than smoothly varying. Yet another way to possibly do this that might be more spot on wrt the original question is foound at this link cessu.blogspot.com.au/2008/11/… – Psychopath

Answer 7

All the generators I'm aware of are iterative. So, any 'random access' would involve calculating all the values from the first to the one you ask for.

The closest you could come is to take a fixed seed, hash it, and then hash the index value, using something that mixes really enthusiastically.

Or generate a long list of them and store it.

Cantatrice

Answer 8

take a look at this patent: Random-access psuedo random number generator https://patents.google.com/patent/US4791594

It uses a multi-stage bit scrambling scheme to generate a Pseudo Number sequence that is able to be accessed randomly.

The idea is to use the input address as control bits to scramble multiple seed numbers, and then XOR the results to produce an output, then a second pass of scrambling using the result generated from the previous pass.

Jana