Random Access Stable PRNGs

NOTE: This article deals specifically with JavaScript, but the techniques described in it are trivially portable to other languages.

When writing programs that have pseudo-random behavior -- games being the obvious but by no means only case -- it is helpful to be able to reproduce a sequence of pseudo-random numbers while testing and debugging so that the same behaviors can be repeated. For exactly this reason, there is a seed function in most languages that can be used to provide the pseudo-random number generator (PRNG) with a repeatable starting point.

And then there is Brendan Eich's weekend project, JavaScript. In its standard library, there is the Math.random() method to generate random floating point numbers in the 0.0-1.0 interval, but there is no way to set the seed.

Even if there were, the seeding technique only works when testing a fixed linear execution path and provides no way to skip ahead, e.g., if the bug or feature you're interested in testing kicks in around the billionth iteration of the PRNG, you have to go through a billion iterations every time. For all practical purposes, most PRNGs behave like sequential access tapes instead of random access memory.

Fortunately, there is a simple and relatively efficient way to sample elements from an effectively infinite multidimensional array of pseudo-random numbers by using a simple checksum algorithm like CRC-32. In its simplest form -- and assuming we already have a CRC-32 implementation handy (see below) -- it looks like this:

function stableRandom(salt, coord) { return crc32(salt.toString() + coord.toString()) / Math.pow(2, 32); }

The salt argument is a string that consistently identifies the random number array you will be addressing. For most purposes, this can be fairly brief, and for efficiency's sake, it should be as short as possible. The coord argument is a string representation of the coordinate system in use. For a simple series of pseudo-random numbers, that is, a one-dimensional array, this can be an integer:

var x = stableRandom("aardvark", 100);

In the example above, as long as salt is aardvark, setting coord to 100 will always yield 0.6918889253865927. Likewise,

for(var i = 0; i < 10; i++) console.log(stableRandom("aardvark", i));

always produces

0.35716383648104966 0.1734641946386546 0.708518503466621 0.7593731542583555 0.35941808205097914 0.16805853554978967 0.695506326854229 0.769706932362169 0.3347873033490032 0.13555422076024115

This can be trivially extended to higher dimensions by passing a multidimensional coordinate, either as a string "100,6.35,-7" or, because stableRandom() explicitly calls toString() on its arguments, you can also use an Array [100, 6.35, -7] or Object {x: 100, y: 6.35, z: -7 }, though this runs the risk of encountering differing toString() implementations in different Javascript engines.

It should be noted that while CRC-32 yields a good first approximation of a uniform distribution, it is by no means a secure cryptographic hash and should not be used as such.

The CRC-32 implementation used here follows: