2

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?

  • 3
    You shouldn't put images of text in your posts. Always post the code itself so it's easier to copy/paste and to search. I edited your question, you can verify I didn't do any mistake. – Vincent Savard Jun 23 '16 at 14:24
  • If you can afford the lower performance, I'd consider using a proper PRF (pseudo-random-function) instead. – CodesInChaos Jun 23 '16 at 14:51
  • Can anyone suggest how I could modify this function to accommodate 2 and 3 input integers? – user234599 Jun 23 '16 at 15:48
  • Combine the integers into one according to your requirements (xor? add? multiply?), then call this function with the result. – jpaugh Jun 23 '16 at 20:57
5

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

  • @MasonWheeler Depends on the definition you're using. For example one could consider /dev/urandom a PRNG because it's not truly random, but it's not deterministic because it implicitly seeds (and frequently reseeds) itself from various true RNGs. – CodesInChaos Jun 23 '16 at 14:45
  • @CodesInChaos So what happens when it gets the same seed? – 8bittree Jun 23 '16 at 14:46
  • 1
    For perlin noise, you essentially need a hash function, not a stateful PRNG. Since this is cheap hash, it's suitable for that purpose. – CodesInChaos Jun 23 '16 at 14:47
  • Good links. I think it's important to note that you can imply from the second link that these are not recommended for crypto purposes unless you really know what you are doing. – JimmyJames Jun 23 '16 at 14:50
  • 1
    LFSRs are used any time you need a data source that's mostly random at face value, but is still deterministic. If you were developing a wireless transmission protocol for example, an LSFR output is random enough to simulate arbitrary data, but deterministic so that you can debug transmission errors because you know what you should be receiving. – whatsisname Jun 23 '16 at 14:54
4

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:

distribution of results for inputs 0 -> 10000

Locally too:

zoomed in

  • PRNG = Pseudo Random Number Generator. The "pseudo" implies it's not truly random. – 8bittree Jun 23 '16 at 14:45
  • @8bittree Of that, I am well aware but the comment "takes an integer and just spits out another random integer" suggests to me it's worth pointing out explicitly. – JimmyJames Jun 23 '16 at 14:47
  • @jimmyjames "random" was just lazy short-hand - i know it's only pseudorandom – user234599 Jun 23 '16 at 15:12
  • 1
    @user2312610 I figured you did but this often poorly understood and other people could read that and be confused. – JimmyJames Jun 23 '16 at 15:27
  • Bloody hell - thanks for the graphics and stuff - that's incredible. – user234599 Jun 23 '16 at 15:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy