I have this random number generator, and have had it for quite some time, but despite how much I use it I don’t really understand it.
public static int Random(int x)
{
x = x + seed;
x = (x << 13) ^ x;
return (x * (x * x * 15731 + 789221) + 1376312589) & 0x7fffffff;
}
It works really well for my purposes – it takes an integer and just spits out another random integer. It doesn’t rely on a state, nor does it rely on its last output like so many linear congruential generators.
What type of generator is this? I’d like some terms that I can google to understand and learn more about it. What family of PRNG does it belong to? How/why does it work?
4
A bit of poking around on Google suggests that this is a Linear Feedback Shift Register or LFSR. It’s apparently commonly used to produce noise for shaders.
Further Reading
Noise and Pseudo Random Number Generator in GLSL
Linear-feedback shift register
13
To be clear, this doesn’t produce a random number. What it does (I expect) is produce wildly different numbers for integers that are close to each other. The way it does that is by overflowing the int by creating numbers that are bigger (absolute value) than the 32 bit range can support at least once. The shift and xor appear to expand the input over 32 bits and the multiplications and additions cause it to overflow and improve the distribution. I am not a mathematician but I believe this could be described as a chaotic function.
I ran some numbers through Java with seed of 13. Seems pretty well distributed:
Locally too:
12