Turning Random Number Into Deterministic White Noise

Question

I need to be able to generate a single random number and then use that number to seed a theoretically infinitely large 2d plane on the fly with boolean values. I need a function I can call that is deterministic with three inputs (x, y, and the random seed) and returns a pseudo-random result back:

int r = random()
//...
var value_for_point = f(x,y,r);

If I were to use this function to fill a 10x10 array with ones and zeros, it would ideally look the same as/similar to if I had asked for a random value for each cell as I went along, i.e. white noise. It doesn't have to be perfect - its not for statistical analysis. I just need to be able to recreate the array given the same random number.

I can't simply seed the random number generator for two reasons. First, I need this function to be based on x and y. I may call this function to fill the array between (0,0) and (10, 10), then later ask for the values between (-10,-5) and (3,4). Second, the language I'm using doesn't have a seed function.

I'm sure there's either a trivial way to do this that I'm not seeing or there's something int he domain of fractals that might help me. Anyone know how to do this?

Answer 1

I think you want Perlin noise?

Answer 2

Might help if we knew the language.

C#...

static bool GetPixel(int seed, ushort x, ushort y)
{
    int randomSeed = (x << 16 | y) ^ seed;
    Random rnd = new Random(randomSeed); 
    /* if you just want a constant result you can seed the function 
       on app start and never touch the random generator again */
    return rnd.NextDouble() >= .5;
}

Answer 3

Just use something simple like

private static uint GetUint()
{
    m_z = 36969 * (m_z & 65535) + (m_z >> 16);
    m_w = 18000 * (m_w & 65535) + (m_w >> 16);
    return (m_z << 16) + m_w;
}

and seed the initial values m_z and m_w. Do that for each, x and y.

Answer 4

It's not 100% perfect, but how about using a canned algorithm like SHA1 or MD5? SHA1 puts out a string of 160 bits from any character string and it's more-or-less random. To populate your 10x10 boolean array you'd only need the least significant 100 bits which should be pretty close to random. Because you're starting with a known base string (of any length) as your seed, your values are reproducible.

I don't know what language you're using, but implementations of SHA1 and MD5 are available for just about every operating system.

Answer 5

You can't simulate an infinitely large plane. Ultimately, you're stuck with a random number generator of some sort, and there's always a limit on the number of bits of state your generator can store.

That said, the limitation is mostly theoretical. For most practical purposes, you can limit the size of plane based on the size the user can specify. For example, if x and y are two 32 bit integers, then you only need to be able simulate a plane that's 2^32-1x2^32-1 -- which is a long ways short of infinite.

Given what you've said about your system's random number generator, chances are that you'll need (or at least very much want) to write a generator of your own, or else use an existing on on the web that has a sufficiently long period. If you're going to use 32 bits for your X and Y coordinates, then you need a generator with at least a 64-bit period.

From there, things are pretty easy: you combine the bits of the x,y coordinates about like producing a linear address into any other 2D array, then use the result as a seed to the PRNG, and get out the result.

Answer 6

Very simple mathematical algorithms can produce very complex deterministic output. Take a look at wolfram's book.

You could for example use rule 30 to generate this.