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?

Improve this question
4
  • 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, 2016 at 14:24
  • If you can afford the lower performance, I'd consider using a proper PRF (pseudo-random-function) instead.
    – CodesInChaos
    Jun 23, 2016 at 14:51
  • Can anyone suggest how I could modify this function to accommodate 2 and 3 input integers?
    – user234599
    Jun 23, 2016 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, 2016 at 20:57

2 Answers 2

Reset to default
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

Improve this answer
13
  • @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, 2016 at 14:45
  • @CodesInChaos So what happens when it gets the same seed?
    – 8bittree
    Jun 23, 2016 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, 2016 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, 2016 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, 2016 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

Improve this answer
12
  • PRNG = Pseudo Random Number Generator. The "pseudo" implies it's not truly random.
    – 8bittree
    Jun 23, 2016 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, 2016 at 14:47
  • @jimmyjames "random" was just lazy short-hand - i know it's only pseudorandom
    – user234599
    Jun 23, 2016 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, 2016 at 15:27
  • Bloody hell - thanks for the graphics and stuff - that's incredible.
    – user234599
    Jun 23, 2016 at 15:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.