"Random access" PRNG

[Nexuapex]

I've been poking around PRNGs, and am trying to find one that allows random access without a (relatively) time-consuming reseeding process. For example, the Mersenne twister algorithms I've seen regenerate a 624-word internal state every time the seed changes, which is not something you want to do every time you generate a number. The reason I don't want an internal state running around is, say, generating a random bitmap of extreme size. It would be convenient to store only the seed plus any changes the user makes to the bitmap, instead of the entire state of the picture (especially if many parts will never change), and it would be extremely useful in case the bitmap doesn't actually fit in memory (i.e. it is infinite). But you wouldn't want to reseed the PRNG constantly as the user scrolls around (as you'd need to reseed the generator one time for each visible row or column per frame, if the visible rect is moving around).

Basically, my question is if anyone knows about a PRNG that generates good random (preferably 64-bit) integers from an arbitrary and variable-sized seed (say an array of integers that might add or remove elements between calls) in O(n) relative to the number of elements changed in the array (instead of the total number of elements). For the above example, it would be a variable-sized array of integers as a seed, with the last two elements being the x and y coordinates of the pixel to be generated. Or something that can be used to help with the above example, if my thoughts are leading me in the wrong direction.

Any thoughts, or corrections as to my line of thinking for this?

[Puck]

I'm very confused as to why you want to reseed the random number generator at all. Unless I'm misreading your post, you should probably just use one seed and then keep asking the RNG for the next random number.

Can you explain in more detail why you think reseeding is needed?

[headprogrammingczar]

I would do a method similar to one-time pad encryption. Take a huge-normous file (i.e. your OS's hibernate file) and compress it, then encrypt it. Then make whatever algorithm you want to do random access lookup on the file. As for multi-variable parametrization, you can use matrix operations to flatten the arguments into an integer. It would be nice to know what it is for, and whatever it happens to be for, come up with a solution yourself before implementing any suggestions here.

[Xanthir]

I would do a method similar to one-time pad encryption. Take a huge-normous file (i.e. your OS's hibernate file) and compress it, then encrypt it. Then make whatever algorithm you want to do random access lookup on the file. As for multi-variable parametrization, you can use matrix operations to flatten the arguments into an integer. It would be nice to know what it is for, and whatever it happens to be for, come up with a solution yourself before implementing any suggestions here.

The method used to do random-access on the file will either be/contain a useful PRNG by itself (thus removing the need to carry around a huge file and do lookups on it), or will be/contain a poor PRNG (thus making it useless, as it won't do properly random lookups on the document).

All your suggestion does is remap one set of numbers to another set of predetermined random numbers. The target set is already random - there's no need to throw more randomness at it (and in fact, you're likely to reduce the randomness). It's exactly equivalent and much easier to just eat the random file you've generated from start to finish - it'll generate a sequence of similar or greater randomness.

[Nexuapex]

I can't use a machine-specific file, the seed must be machine-independent.

Some more detail: imagine the pseudocode that would draw a portion of this generated image:

Code: Select all

int stored_seed = get_stored_seed();
int x, y;
for (y = origin_y; y < viewport_height; y++) {
   srand(stored_seed ^ y);
   for (x = 0; x < origin_x; x++) {
      rand();
   }
   for (x = origin_x; x < viewport_width; x++) {
      plot(x - origin_x, y - origin_y, rand() % TONE_RANGE);
   }
}

To start my random number generation at any arbitrary (origin_x, origin_y) and get consistent results, I need to call srand() once per row and rand() constantly to shift to where my row begins. I could also do this:

Code: Select all

int stored_seed = get_stored_seed();
int x, y;
for (y = origin_y; y < viewport_height; y++) {
   for (x = origin_x; x < viewport_width; x++) {
      srand(stored_seed ^ x ^ y);
      plot(x - origin_x, y - origin_y, rand() % TONE_RANGE);
   }
}

That involves an srand() for every rand(). By that point I'm worried.

What I'm looking for, I guess, is basically a hash function for an array that is statistically random. I'd like to be able to do this, or something like it:

Code: Select all

size_t size;
int * stored_seeds = get_stored_seeds(&size);
rand_buf * state = new_rand(stored_seeds, size);
int coords[2];
for (coords[0] = origin_y; coords[0] < viewport_height; coords[0]++) {
   for (coords[1] = origin_x; coords[1] < viewport_width; coords[1]++) {
      plot(x - origin_x, y - origin_y, get_rand(state, coords, sizeof(coords)) % TONE_RANGE);
   }
}

[Berengal]

So to rephrase, you want to be able to find the n-th term of a prng without calculating all terms <n?

I think I remember reading something about this, but I can't remember exactly what it was about or where. I'll try looking for it again.

[segmentation fault]

poll the sound card. its always generating random white noise.

[Berengal]

poll the sound card. its always generating random white noise.

Good idea, though you might get problems if you want the same term twice. If that's the case then you'd have to store each retrieved value, or generate everything at once and store it in a file as previously suggested. Or use a prng where you can calculate an arbitrary term.

Edit: Come to think of it, could you use a hash? I'm not quite up to date on which hash would make the best random numbers, but you should get consistent return values from identical input.

[Nexuapex]

So to rephrase, you want to be able to find the n-th term of a prng without calculating all terms <n?

Yep.

I could use a hash, I'm betting most hashes would do statistical randomness pretty well.

...but finding a hash function for an array that didn't turn {1} into a hash of 1, and {2} into a hash of 2, etc. might be a problem. I wouldn't know where to start looking.

[Berengal]

What about md5 or sha-1? Being cryptographically secure, they should provide output indistinguishable from true randomness. In theory that is, and for your use as well.

[Nexuapex]

Well, MD5 and SHA-1 probably won't work straight off the bat, as they aren't really designed for this use (doesn't MD5 need to pad the input to a multiple of 256 bytes or something like that?). But I'll look into those, they're very close to what I want.

[Berengal]

Padding shouldn't be that huge an issue. Just repeat the pattern until you get above the closest multiple of 256 (or whatever it is) and cut the rest of. It might provide the same hash a couple of times too much at first (with 5, 55, 555 etc. all giving the same one), but if you don't need really random numbers, just ones that are random enough, it should work fine (or you could start counting at 1000).

[Unparallelogram]

Why not let your (i,j)-th pseudo-random number be hash(seed + i + j) or something, + being concatenation? Cryptographic hashes give very good pseudo-randomness, but of course simpler hashes are cheaper computationally if that matters to you.

[Nexuapex]

Why not let your (i,j)-th pseudo-random number be hash(seed + i + j) or something, + being concatenation? Cryptographic hashes give very good pseudo-randomness, but of course simpler hashes are cheaper computationally if that matters to you.

It does matter somewhat.

Is there a better site than Wikipedia to go for information about hashing methods, cryptographic and otherwise?

Edit: Actually, anyone know of a cryptographic-ish hash that I could do hash(hash(seed, i), j) with, instead of hash(seed + i + j)?

[Yakk]

Build "zones" of, say, ~1024 units (32x32). Your "world" becomes a bunch of patches of that size.

Hash the location of the zone into a seed for your random number generator.

Build each 32x32 patch by calling rand 1024 times in a particular order.

This requires 1 hashing and 1 seeding every ~1000 calls to rand. For a given pixel, it requires an average of 512 calls to rand -- however, odds are when examining an image is that you work on a reasonably contiguous region.

If you want a much much much larger region (ie, bigger than your hash function), you can do something like the above in a quad tree (or oct tree) hierarchy.

If this is for, example, a game, you could add an "extra dimension" for independent dimensions of the terrain.

(I believe SC2, among many other games, uses a technique somewhat like this to efficiently generate a rather large amount of data consistently.)

[petschge]

You can use the BBS generator. It is named after the inventors Blum, Blum and Shub. Please note that the algorithm return pseudorandom bits, not bytes. Now for a short description:

* Generate two primes p, q of sufficient size which satisfy p \equiv 3 \pmod{4} and q \equiv 3 \pmod{4}.
* Calculate n = p * q
* Pick a seed s which is smaller than n and coprime to n
* Calculate x_0 = s^2 \pmod{n}
* Iterate x_i = (x_{i-1})^2 \pmod{n} and use the least significant bit of x_i

Now if you want to get x_j directly compute x_j = x_0 ^{(2^j mod ((p - 1)*(q-1)))}

I hope this helps a little.

[Cosmologicon]

Now if you want to get x_j directly compute x_j = x_0 ^{(2^j mod ((p - 1)*(q-1)))}

But calculating 2^j mod whatever is an O(j) operation, isn't it?

[Yakk]

Calculating 2^j mod n takes about lg(j) time, using a naive algorithm.

You could probably do even better.

(Let x_0 = 1 and x_{i+1} = {x_i}^2 for i >= 0. Each squaring takes about O(1) time in a specific modulus.

Now, 2^j = Product(i from X)( x_i ) for some set X with |X| <= lg(j), simply by expressing j as a binary number, and multiplying together the appropriate x_i.

This requires you to calculate lg(j) x_i terms, then multiply together some subset of them. Overall: O(lg(j)) time.

As noted, I'm not convinced that this is the fastest algorithm to solve this problem.

[Cosmologicon]

Yep good call. I don't know what I was thinking, probably computing x^(2^j). But that's not needed here.

[Yakk]

Modular arithmetic is really fast. Even x^(2^j) mod k can be done in O(lg(j)) time if you can factor k (factoring k is sufficient, but not required).

Simply calculate 2^j mod phi(k), then calculate x^[ 2^j mod phi(k) ], which takes O(lg(k)) time.

At this level, I should be admitting that operations on numbers up to size k isn't constant time. Which slows things down.

(As an example, multiplying together two lg(k) digit numbers takes various amounts of time depending on how sophisticated you want to be. The more sophisticated, the worse the constant factor, until you eventually do the multiplication in the frequency domain.)

[godrik]

(sorry for the inconvienience, formulas are written in latex. I believe the explanation are still easy to read.)


I would suggest to consider the problem of generating a one dimensional array of $n$ element of a finite field $F$ of size $p$.
Let us consider $P_0$ and $P_1$ two PRNG that maps an element of $F$ to another one.
Let $k$ be the element of the array you want to generate, we define $A_i (k) = P_0$ if the $i$-th bit of $k$ is $0$ an $A_i (k) = P_1$ if the $i$-th bit of $k$ is $1$.
An array is identified by a single element of $F$, namely the seed $s$.
We generate $k$ in $\log_2 (n)$ step by applying iteratively $A_i$ on the seed.

For instance, for $k=00101$, the element is $P_0 (P_0 (P_1 (P_0 (P_1 (s)))))$.
Using such a technique you can generate any of the array in $O(log_2 (n))$ call to a PRNG storing only $1$ element of $F$.

I believe this is one of the most reasonable answer to the problem. However, i am not quite sure of the property of such a generator. One should take care on the choice of the functions $P_0$ and $P_1$, they should not respect the property $P_0 (P_1 (x)) = P_1 (P_0 (x))$ since this would mean that $k=011001$ and $k=110001$ have the same value.
Using two exponentiation such as in RSA would lead to this problem. I believe Linear Congruential Generators (LCG) does not respect such a property and could be a valid choice. Perhaps it would even be better to use a LCG and an exponentiation technique.

To speed up the computations of the value, one could cache the result of the inner call to $A_i$.