Package squidpony.squidmath

Class LightRNG

java.lang.Object
squidpony.squidmath.LightRNG
All Implemented Interfaces:
Serializable, RandomnessSource, SkippingRandomness, StatefulRandomness
public final class LightRNG
extends Object
implements RandomnessSource, StatefulRandomness, SkippingRandomness, Serializable
This is a SplittableRandom-style generator, meant to have a tiny state that permits storing many different generators with low overhead. It should be rather fast, though no guarantees can be made on all hardware. It should be faster than using SplittableRandom from Java 8 because it has a single "gamma" value that prevents it from being split but also makes runtime a bit quicker. It is based on using a unary hash on a large-increment counter, which makes even the first item obtained from similarly-seeded LightRNGs very likely to be very different. This is an advantage over non-hash-based RNGs.
This generator is especially fast on OpenJ9, version 0.17.0 or later (from late 2019), and can be several times faster there than on HotSpot.
Written in 2015 by Sebastiano Vigna (vigna@acm.org)
Author:
Sebastiano Vigna, Tommy Ettinger
See Also:
Serialized Form

  • Field Summary

    Fields 
    Modifier and Type Field Description
    long state  

  • Constructor Summary

    Constructors 
    Constructor Description
    LightRNG()
    Creates a new generator seeded using Math.random.
    LightRNG​(long seed)  

  • Method Summary

    Modifier and Type Method Description
    int compatibleNext​(int bits)
    Gets a pseudo-random int with at most the specified count of bits; for example, if bits is 3 this can return any int between 0 and 2 to the 3 (that is, 8), exclusive on the upper end.
    int compatibleNextInt​(int bound)
    Like compatibleNext(int), but for compatibility with nextInt(int).
    int compatibleNextInt​(int lower, int upper)
    Inclusive lower, exclusive upper.
    long compatibleNextLong​(long bound)
    Exclusive on the upper bound.
    long compatibleNextLong​(long lower, long upper)
    Inclusive lower, exclusive upper.
    LightRNG copy()
    Produces a copy of this RandomnessSource that, if next() and/or nextLong() are called on this object and the copy, both will generate the same sequence of random numbers from the point copy() was called.
    static long determine​(int a, int b)  
    static long determine​(long state)  
    static int determineBounded​(long state, int bound)  
    static double determineDouble​(long state)
    Returns a random double that is deterministic based on state; if state is the same on two calls to this, this will return the same float.
    static float determineFloat​(long state)
    Returns a random float that is deterministic based on state; if state is the same on two calls to this, this will return the same float.
    boolean equals​(Object o)  
    long getState()
    Gets the current state of this generator.
    int hashCode()  
    int next​(int bits)
    Gets a pseudo-random int with at most the specified count of bits; for example, if bits is 3 this can return any int between 0 and 2 to the 3 (that is, 8), exclusive on the upper end.
    boolean nextBoolean()
    Gets a random value, true or false.
    void nextBytes​(byte[] bytes)
    Given a byte array as a parameter, this will fill the array with random bytes (modifying it in-place).
    double nextDouble()
    Gets a uniform random double in the range [0.0,1.0)
    double nextDouble​(double outer)
    Gets a uniform random double in the range [0.0,outer) given a positive parameter outer.
    float nextFloat()
    Gets a uniform random float in the range [0.0,1.0)
    int nextInt()
    Can return any int, positive or negative, of any size permissible in a 32-bit signed integer.
    int nextInt​(int bound)
    Returns a random non-negative integer between 0 (inclusive) and the given bound (exclusive), or 0 if the bound is 0.
    int nextInt​(int lower, int upper)
    Inclusive lower, exclusive upper.
    long nextLong()
    Can return any long, positive or negative, of any size permissible in a 64-bit signed integer.
    long nextLong​(long bound)
    Exclusive on the outer bound; the inner bound is 0.
    long nextLong​(long inner, long outer)
    Inclusive inner, exclusive outer; both inner and outer can be positive or negative.
    void setSeed​(long seed)
    Sets the seed of this generator (which is also the current state).
    void setState​(long seed)
    Sets the seed (also the current state) of this generator.
    long skip​(long advance)
    Advances or rolls back the LightRNG's state without actually generating each number.
    String toString()  

    Methods inherited from class java.lang.Object

    clone, finalize, getClass, notify, notifyAll, wait, wait, wait

  • Field Details

  • Constructor Details

  • Method Details

    • next

      public final int next​(int bits)
      Gets a pseudo-random int with at most the specified count of bits; for example, if bits is 3 this can return any int between 0 and 2 to the 3 (that is, 8), exclusive on the upper end. That would mean 7 could be returned, but no higher ints, and 0 could be returned, but no lower ints. The algorithm used here changed on March 8, 2018 when LightRNG was remade the default generator in SquidLib. The older method is available as compatibleNext(int), but its use is discouraged; it's slightly slower for no good reason.
      Specified by:
      next in interface RandomnessSource
      Parameters:
      bits - the number of bits to be returned; if 0 or less, or if 32 or greater, can return any 32-bit int
      Returns:
      a pseudo-random int that uses at most the specified amount of bits

    • compatibleNext

      public final int compatibleNext​(int bits)
      Gets a pseudo-random int with at most the specified count of bits; for example, if bits is 3 this can return any int between 0 and 2 to the 3 (that is, 8), exclusive on the upper end. That would mean 7 could be returned, but no higher ints, and 0 could be returned, but no lower ints. The algorithm used here is the older version of next(int) before some things changed on March 8 2018. Using this method is discouraged unless you need to reproduce values exactly; it's slightly slower for no good reason. Calling next(32) and compatibleNext(32) should have identical results, but other values for bits will probably be different.
      Parameters:
      bits - the number of bits to be returned; if 0 or less, or if 32 or greater, can return any 32-bit int
      Returns:
      a pseudo-random int that uses at most the specified amount of bits

    • nextLong

      public final long nextLong()
      Can return any long, positive or negative, of any size permissible in a 64-bit signed integer.
      Specified by:
      nextLong in interface RandomnessSource
      Returns:
      any long, all 64 bits are random

    • copy

      public LightRNG copy()
      Produces a copy of this RandomnessSource that, if next() and/or nextLong() are called on this object and the copy, both will generate the same sequence of random numbers from the point copy() was called. This just needs to copy the state so it isn't shared, usually, and produce a new value with the same exact state.
      Specified by:
      copy in interface RandomnessSource
      Specified by:
      copy in interface StatefulRandomness
      Returns:
      a copy of this RandomnessSource

    • nextInt

      public int nextInt()
      Can return any int, positive or negative, of any size permissible in a 32-bit signed integer.
      Returns:
      any int, all 32 bits are random

    • nextInt

      public int nextInt​(int bound)
      Returns a random non-negative integer between 0 (inclusive) and the given bound (exclusive), or 0 if the bound is 0. The bound can be negative, which will produce 0 or a negative result. Uses an aggressively optimized technique that has some bias, but mostly for values of bound over 1 billion. This method uses the same technique as RNG.nextIntHasty(int), and like that method will always advance state exactly once (equivalent to one call to nextLong()).
      Credit goes to Daniel Lemire, http://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/
      Parameters:
      bound - the outer bound (exclusive), can be negative or positive
      Returns:
      the found number

    • compatibleNextInt

      public int compatibleNextInt​(int bound)
      Like compatibleNext(int), but for compatibility with nextInt(int). Exclusive on the upper bound. The lower bound is 0.
      Parameters:
      bound - the upper bound; should be positive
      Returns:
      a random int less than n and at least equal to 0

    • nextInt

      public int nextInt​(int lower, int upper)
      Inclusive lower, exclusive upper. Although you should usually use a higher value for upper than for lower, you can use a lower "upper" than "lower" and this will still work, producing an int between the two bounds.
      Parameters:
      lower - the lower bound, inclusive, can be positive or negative
      upper - the upper bound, exclusive, can be positive or negative, usually should be greater than lower
      Returns:
      a random int between lower (inclusive) and upper (exclusive)

    • compatibleNextInt

      public int compatibleNextInt​(int lower, int upper)
      Inclusive lower, exclusive upper.
      Parameters:
      lower - the lower bound, inclusive, can be positive or negative
      upper - the upper bound, exclusive, should be positive, must be greater than lower
      Returns:
      a random int between lower (inclusive) and upper (exclusive)

    • nextLong

      public long nextLong​(long bound)
      Exclusive on the outer bound; the inner bound is 0. The bound may be negative, which will produce a non-positive result.
      Parameters:
      bound - the outer exclusive bound; may be positive or negative
      Returns:
      a random long between 0 (inclusive) and bound (exclusive)

    • nextLong

      public long nextLong​(long inner, long outer)
      Inclusive inner, exclusive outer; both inner and outer can be positive or negative.
      Parameters:
      inner - the inner bound, inclusive, can be positive or negative
      outer - the outer bound, exclusive, can be positive or negative and may be greater than or less than inner
      Returns:
      a random long that may be equal to inner and will otherwise be between inner and outer

    • compatibleNextLong

      public long compatibleNextLong​(long bound)
      Exclusive on the upper bound. The lower bound is 0. Unlike nextInt(int) or nextLong(long), this may sometimes advance the state more than once, depending on what numbers are produced internally and the bound. nextLong(long) is preferred because it is much faster and reliably advances the state only once. Because this method uses rejection sampling, getting multiple random longs to "smooth the odds" when the bound is such that it can't fairly distribute one random long across all possible outcomes, it may be more "fair" than nextLong(long), though it could potentially consume more of the period faster if pathologically bad bounds were used very often, and if enough of the period is gone then statistical flaws may become detectable.
      Parameters:
      bound - the upper bound; if this isn't positive, this method always returns 0
      Returns:
      a random long less than n and at least equal to 0

    • compatibleNextLong

      public long compatibleNextLong​(long lower, long upper)
      Inclusive lower, exclusive upper.
      Parameters:
      lower - the lower bound, inclusive, can be positive or negative
      upper - the upper bound, exclusive, should be positive, must be greater than lower
      Returns:
      a random long at least equal to lower and less than upper

    • nextDouble

      public double nextDouble()
      Gets a uniform random double in the range [0.0,1.0)
      Returns:
      a random double at least equal to 0.0 and less than 1.0

    • nextDouble

      public double nextDouble​(double outer)
      Gets a uniform random double in the range [0.0,outer) given a positive parameter outer. If outer is negative, it will be the (exclusive) lower bound and 0.0 will be the (inclusive) upper bound.
      Parameters:
      outer - the exclusive outer bound, can be negative
      Returns:
      a random double between 0.0 (inclusive) and outer (exclusive)

    • nextFloat

      public float nextFloat()
      Gets a uniform random float in the range [0.0,1.0)
      Returns:
      a random float at least equal to 0.0 and less than 1.0

    • nextBoolean

      public boolean nextBoolean()
      Gets a random value, true or false. Calls nextLong() once.
      Returns:
      a random true or false value.

    • nextBytes

      public void nextBytes​(byte[] bytes)
      Given a byte array as a parameter, this will fill the array with random bytes (modifying it in-place). Calls nextLong() Math.ceil(bytes.length / 8.0) times.
      Parameters:
      bytes - a byte array that will have its contents overwritten with random bytes.

    • setSeed

      public void setSeed​(long seed)
      Sets the seed of this generator (which is also the current state).
      Parameters:
      seed - the seed to use for this LightRNG, as if it was constructed with this seed.

    • setState

      public void setState​(long seed)
      Sets the seed (also the current state) of this generator.
      Specified by:
      setState in interface StatefulRandomness
      Parameters:
      seed - the seed to use for this LightRNG, as if it was constructed with this seed.

    • getState

      public long getState()
      Gets the current state of this generator.
      Specified by:
      getState in interface StatefulRandomness
      Returns:
      the current seed of this LightRNG, changed once per call to nextLong()

    • skip

      public long skip​(long advance)
      Advances or rolls back the LightRNG's state without actually generating each number. Skips forward or backward a number of steps specified by advance, where a step is equal to one call to nextLong(), and returns the random number produced at that step (you can get the state with getState()).
      Specified by:
      skip in interface SkippingRandomness
      Parameters:
      advance - Number of future generations to skip over; can be negative to backtrack, 0 gets the most recent generated number
      Returns:
      the random long generated after skipping advance numbers

    • toString

      public String toString()
      Overrides:
      toString in class Object

    • equals

      public boolean equals​(Object o)
      Overrides:
      equals in class Object

    • hashCode

      public int hashCode()
      Overrides:
      hashCode in class Object

    • determine

      public static long determine​(long state)

    • determine

      public static long determine​(int a, int b)

    • determineBounded

      public static int determineBounded​(long state, int bound)

    • determineFloat

      public static float determineFloat​(long state)
      Returns a random float that is deterministic based on state; if state is the same on two calls to this, this will return the same float. This is expected to be called with a changing variable, e.g. determine(++state), where the increment for state should be odd but otherwise doesn't really matter. This multiplies state by 0x9E3779B97F4A7C15L within this method, so using a small increment won't be much different from using a very large one, as long as it is odd. The period is 2 to the 64 if you increment or decrement by 1, but there are only 2 to the 30 possible floats between 0 and 1.
      Parameters:
      state - a variable that should be different every time you want a different random result; using determine(++state) is recommended to go forwards or determine(--state) to generate numbers in reverse order
      Returns:
      a pseudo-random float between 0f (inclusive) and 1f (exclusive), determined by state

    • determineDouble

      public static double determineDouble​(long state)
      Returns a random double that is deterministic based on state; if state is the same on two calls to this, this will return the same float. This is expected to be called with a changing variable, e.g. determine(++state), where the increment for state should be odd but otherwise doesn't really matter. This multiplies state by 0x9E3779B97F4A7C15L within this method, so using a small increment won't be much different from using a very large one, as long as it is odd. The period is 2 to the 64 if you increment or decrement by 1, but there are only 2 to the 62 possible doubles between 0 and 1.
      Parameters:
      state - a variable that should be different every time you want a different random result; using determine(++state) is recommended to go forwards or determine(--state) to generate numbers in reverse order
      Returns:
      a pseudo-random double between 0.0 (inclusive) and 1.0 (exclusive), determined by state