Package squidpony.squidmath

Class DiverRNG

java.lang.Object
squidpony.squidmath.DiverRNG
All Implemented Interfaces:
Serializable, RandomnessSource, StatefulRandomness
public final class DiverRNG
extends Object
implements StatefulRandomness, Serializable
A very-high-quality StatefulRandomness that is the fastest 64-bit generator in this library that passes statistical tests and is one-dimensionally equidistributed across all 64-bit outputs. Has 64 bits of state and natively outputs 64 bits at a time, changing the state with an "XLCG" or xor linear congruential generator (XLCGs are very similar to normal LCGs but have slightly better random qualities on the high bits; the code for this XLCG is state = (state ^ 7822362180758744021) * -4126379630918251389, and the only requirements for an XLCG are that the constant used with XOR, when treated as unsigned and modulo 8, equals 5, while the multiplier, again treated as unsigned and modulo 8, equals 3). Starting with that XLCG's output, it bitwise-left-rotates by 27, multiplies by a very large negative long (see next), then returns a right-xorshift by 25. The large negative long is -2643881736870682267, which when treated as unsigned is 2 to the 64 divided by an irrational number that generalizes the golden ratio. This specific irrational number is the solution to x5= x + 1. Other multipliers also seem to work well as long as they have enough set bits (fairly-small multipliers fail tests). For whatever reason, the output of this simple function passes all 32TB of PractRand with one anomaly ("unusual" at 256GB), meaning its statistical quality is excellent. ThrustAltRNG is slightly faster, but isn't equidistributed; unlike ThrustAltRNG, this can produce all long values as output. ThrustAltRNG bunches some outputs and makes producing them more likely, while others can't be produced at all. Notably, this generator is faster than LinnormRNG, which it is based on, while improving its quality, is faster than LightRNG while keeping the same or higher quality, and is also faster than XoRoRNG while passing tests that XoRoRNG always or frequently fails, such as binary matrix rank tests.
This generator is a StatefulRandomness but not a SkippingRandomness, so it can't (efficiently) have the skip() method that LightRNG has. A method could be written to run the generator's state backwards, though, as well as to get the state from an output of nextLong().
The static determine() methods in this class are a completely different algorithm from the nextLong() and similar instance methods here; they're a little faster than LinnormRNG.determine(long) and its family while actually having much better stability in case an increment is a poor fit for the internals of the generator. Like nextLong(), determine(long) can produce all possible long outputs and can take any long input; among determine() methods in this library that satisfy that constraint on input and output, this class' appears to be the fastest.
The name comes in a roundabout way from Xmulzencab, Maya mythology's bee god who is also called the Diving God, because the state transition is built around Xor and MUL. I was also listening to a Dio song, Holy Diver, at the time, and Diver is much more reasonable to pronounce than Xmulzencab.
Written December 14, 2018 by Tommy Ettinger. Thanks to M.E. O'Neill for her insights into the family of generators both this and her PCG-Random fall into, and to the team that worked on SplitMix64 for SplittableRandom in JDK 8. Chris Doty-Humphrey's work on PractRand has been invaluable, and I wouldn't know about XLCGs without his findings. Martin Roberts showed the technique for generalizing the golden ratio that produced the high-quality multiplier this uses in one place. Other constants were found empirically or via searching for probable primes with desirable values for use in an XLCG.
Author:
Tommy Ettinger
See Also:
Serialized Form

  • Constructor Summary

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

  • Method Summary

    Modifier and Type Method Description
    DiverRNG 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​(long state)
    Fast static randomizing method that takes its state as a parameter; state is expected to change between calls to this.
    static int determineBounded​(long state, int bound)
    Fast static randomizing method that takes its state as a parameter and limits output to an int between 0 (inclusive) and bound (exclusive); state is expected to change between calls to this.
    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)
    Using this method, any algorithm that might use the built-in Java Random can interface with this randomness source.
    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)
    Exclusive on the outer bound.
    int nextInt​(int inner, int outer)
    Inclusive inner, exclusive outer.
    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 bound (which may be positive or negative), with an inner bound of 0.
    long nextLong​(long lower, long upper)
    Inclusive inner, exclusive outer; lower and upper can be positive or negative and there's no requirement for one to be greater than or less than the other.
    static long randomize​(long state)
    High-quality static randomizing method that takes its state as a parameter; state is expected to change between calls to this.
    static int randomizeBounded​(long state, int bound)
    High-quality static randomizing method that takes its state as a parameter and limits output to an int between 0 (inclusive) and bound (exclusive); state is expected to change between calls to this.
    static double randomizeDouble​(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 randomizeFloat​(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.
    void setState​(long seed)
    Sets the seed (also the current state) of this generator.
    String toString()  

    Methods inherited from class java.lang.Object

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

  • Constructor Details

  • Method Details

    • next

      public final int next​(int bits)
      Description copied from interface: RandomnessSource
      Using this method, any algorithm that might use the built-in Java Random can interface with this randomness source.
      Specified by:
      next in interface RandomnessSource
      Parameters:
      bits - the number of bits to be returned
      Returns:
      the integer containing the appropriate number 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 DiverRNG 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 need 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 final 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 final int nextInt​(int bound)
      Exclusive on the outer bound. The inner bound is 0. The bound can be negative, which makes this produce either a negative int or 0.
      Parameters:
      bound - the upper bound; should be positive
      Returns:
      a random int between 0 (inclusive) and bound (exclusive)

    • nextInt

      public final int nextInt​(int inner, int outer)
      Inclusive inner, exclusive outer.
      Parameters:
      inner - the inner bound, inclusive, can be positive or negative
      outer - the outer bound, exclusive, can be positive or negative, usually greater than inner
      Returns:
      a random int between inner (inclusive) and outer (exclusive)

    • nextLong

      public long nextLong​(long bound)
      Exclusive on bound (which may be positive or negative), with an inner bound of 0. If bound is negative this returns a negative long; if bound is positive this returns a positive long. The bound can even be 0, which will cause this to return 0L every time.
      Credit for this method goes to Rafael Baptista's blog for the original idea, and the JDK10 Math class' usage of Hacker's Delight code for the current algorithm. This method is drastically faster than the previous implementation when the bound varies often (roughly 4x faster, possibly more). It also always gets exactly one random long, so by default it advances the state as much as nextLong().
      Parameters:
      bound - the outer exclusive bound; can be positive or negative
      Returns:
      a random long between 0 (inclusive) and bound (exclusive)

    • nextLong

      public final long nextLong​(long lower, long upper)
      Inclusive inner, exclusive outer; lower and upper can be positive or negative and there's no requirement for one to be greater than or less than the other.
      Parameters:
      lower - the lower bound, inclusive, can be positive or negative
      upper - the upper bound, exclusive, can be positive or negative
      Returns:
      a random long that may be equal to lower and will otherwise be between lower and upper

    • nextDouble

      public final 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 final 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 final 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 final boolean nextBoolean()
      Gets a random value, true or false. Calls nextLong() once.
      Returns:
      a random true or false value.

    • nextBytes

      public final 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.

    • setState

      public final 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 final 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()

    • 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)
      Fast static randomizing method that takes its state as a parameter; state is expected to change between calls to this. It is recommended that you use DiverRNG.determine(++state) or DiverRNG.determine(--state) to produce a sequence of different numbers, and you may have slightly worse quality with increments or decrements other than 1. All longs are accepted by this method, and all longs can be produced; unlike several other classes' determine() methods, passing 0 here does not return 0.
      You have a choice between determine() and randomize() in this class. determine() is the same as LinnormRNG.determine(long) and will behave well when the inputs are sequential, while randomize() is a completely different algorithm based on Pelle Evensen's rrxmrrxmsx_0 and evaluated with the same testing requirements Evensen used for rrxmrrxmsx_0; it will have excellent quality regardless of patterns in input but will be about 30% slower than determine(). Each method will produce all long outputs if given all possible longs as input.
      Parameters:
      state - any long; subsequent calls should change by an odd number, such as with ++state
      Returns:
      any long

    • randomize

      public static long randomize​(long state)
      High-quality static randomizing method that takes its state as a parameter; state is expected to change between calls to this. It is suggested that you use DiverRNG.randomize(++state) or DiverRNG.randomize(--state) to produce a sequence of different numbers, but any increments are allowed (even-number increments won't be able to produce all outputs, but their quality will be fine for the numbers they can produce). All longs are accepted by this method, and all longs can be produced; unlike several other classes' determine() methods, passing 0 here does not return 0.
      You have a choice between determine() and randomize() in this class. determine() is the same as LinnormRNG.determine(long) and will behave well when the inputs are sequential, while randomize() is a completely different algorithm based on Pelle Evensen's rrxmrrxmsx_0 and evaluated with the same testing requirements Evensen used for rrxmrrxmsx_0; it will have excellent quality regardless of patterns in input but will be about 30% slower than determine(). Each method will produce all long outputs if given all possible longs as input.
      Parameters:
      state - any long; subsequent calls should change by an odd number, such as with ++state
      Returns:
      any long

    • determineBounded

      public static int determineBounded​(long state, int bound)
      Fast static randomizing method that takes its state as a parameter and limits output to an int between 0 (inclusive) and bound (exclusive); state is expected to change between calls to this. It is recommended that you use DiverRNG.determineBounded(++state, bound) or DiverRNG.determineBounded(--state, bound) to produce a sequence of different numbers. All longs are accepted by this method, but not all ints between 0 and bound are guaranteed to be produced with equal likelihood (for any odd-number values for bound, this isn't possible for most generators). The bound can be negative.
      You have a choice between determine() and randomize() in this class. determine() is the same as LinnormRNG.determine(long) and will behave well when the inputs are sequential, while randomize() is a completely different algorithm based on Pelle Evensen's rrxmrrxmsx_0 and evaluated with the same testing requirements Evensen used for rrxmrrxmsx_0; it will have excellent quality regardless of patterns in input but will be about 30% slower than determine(). Each method will produce all long outputs if given all possible longs as input.
      Parameters:
      state - any long; subsequent calls should change by an odd number, such as with ++state
      bound - the outer exclusive bound, as an int
      Returns:
      an int between 0 (inclusive) and bound (exclusive)

    • randomizeBounded

      public static int randomizeBounded​(long state, int bound)
      High-quality static randomizing method that takes its state as a parameter and limits output to an int between 0 (inclusive) and bound (exclusive); state is expected to change between calls to this. It is suggested that you use DiverRNG.randomizeBounded(++state) or DiverRNG.randomize(--state) to produce a sequence of different numbers, but any increments are allowed (even-number increments won't be able to produce all outputs, but their quality will be fine for the numbers they can produce). All longs are accepted by this method, but not all ints between 0 and bound are guaranteed to be produced with equal likelihood (for any odd-number values for bound, this isn't possible for most generators). The bound can be negative.
      You have a choice between determine() and randomize() in this class. determine() is the same as LinnormRNG.determine(long) and will behave well when the inputs are sequential, while randomize() is a completely different algorithm based on Pelle Evensen's rrxmrrxmsx_0 and evaluated with the same testing requirements Evensen used for rrxmrrxmsx_0; it will have excellent quality regardless of patterns in input but will be about 30% slower than determine(). Each method will produce all long outputs if given all possible longs as input.
      Parameters:
      state - any long; subsequent calls should change by an odd number, such as with ++state
      bound - the outer exclusive bound, as an int
      Returns:
      an int between 0 (inclusive) and bound (exclusive)

    • 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. determineFloat(++state), where the increment for state should generally be 1. 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.
      You have a choice between determine() and randomize() in this class. determine() is the same as LinnormRNG.determine(long) and will behave well when the inputs are sequential, while randomize() is a completely different algorithm based on Pelle Evensen's rrxmrrxmsx_0 and evaluated with the same testing requirements Evensen used for rrxmrrxmsx_0; it will have excellent quality regardless of patterns in input but will be about 30% slower than determine(). Each method will produce all long outputs if given all possible longs as input.
      Parameters:
      state - a variable that should be different every time you want a different random result; using determineFloat(++state) is recommended to go forwards or determineFloat(--state) to generate numbers in reverse order
      Returns:
      a pseudo-random float between 0f (inclusive) and 1f (exclusive), determined by state

    • randomizeFloat

      public static float randomizeFloat​(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. randomizeFloat(++state), where the increment for state can be any value and should usually be odd (even-number increments reduce the period). The period is 2 to the 64 if you increment or decrement by any odd number, but there are only 2 to the 30 possible floats between 0 and 1.
      You have a choice between determine() and randomize() in this class. determine() is the same as LinnormRNG.determine(long) and will behave well when the inputs are sequential, while randomize() is a completely different algorithm based on Pelle Evensen's rrxmrrxmsx_0 and evaluated with the same testing requirements Evensen used for rrxmrrxmsx_0; it will have excellent quality regardless of patterns in input but will be about 30% slower than determine(). Each method will produce all long outputs if given all possible longs as input.
      Parameters:
      state - a variable that should be different every time you want a different random result; using randomizeFloat(++state) is recommended to go forwards or randomizeFloat(--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. determineDouble(++state), where the increment for state should generally be 1. 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.
      You have a choice between determine() and randomize() in this class. determine() is the same as LinnormRNG.determine(long) and will behave well when the inputs are sequential, while randomize() is a completely different algorithm based on Pelle Evensen's rrxmrrxmsx_0 and evaluated with the same testing requirements Evensen used for rrxmrrxmsx_0; it will have excellent quality regardless of patterns in input but will be about 30% slower than determine(). Each method will produce all long outputs if given all possible longs as input.
      Parameters:
      state - a variable that should be different every time you want a different random result; using determineDouble(++state) is recommended to go forwards or determineDouble(--state) to generate numbers in reverse order
      Returns:
      a pseudo-random double between 0.0 (inclusive) and 1.0 (exclusive), determined by state

    • randomizeDouble

      public static double randomizeDouble​(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. randomizeDouble(++state), where the increment for state can be any number but should usually be odd (even-number increments reduce the period). 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.
      You have a choice between determine() and randomize() in this class. determine() is the same as LinnormRNG.determine(long) and will behave well when the inputs are sequential, while randomize() is a completely different algorithm based on Pelle Evensen's rrxmrrxmsx_0 and evaluated with the same testing requirements Evensen used for rrxmrrxmsx_0; it will have excellent quality regardless of patterns in input but will be about 30% slower than determine(). Each method will produce all long outputs if given all possible longs as input.
      Parameters:
      state - a variable that should be different every time you want a different random result; using randomizeDouble(++state) is recommended to go forwards or randomizeDouble(--state) to generate numbers in reverse order
      Returns:
      a pseudo-random double between 0.0 (inclusive) and 1.0 (exclusive), determined by state