Package squidpony.squidmath

Class PulleyRNG

java.lang.Object
squidpony.squidmath.PulleyRNG
All Implemented Interfaces:
Serializable, RandomnessSource, SkippingRandomness, StatefulRandomness
public final class PulleyRNG
extends Object
implements StatefulRandomness, SkippingRandomness, Serializable
A very-high-quality StatefulRandomness that is meant to be reasonably fast, but also to be robust against frequent state changes, and is built around a strong determine() method. It passes 32TB of PractRand with no anomalies, and calling determine(long) on two different sequences of inputs (one that added 3 each time, and one that added 5 each time) showed no failures on 32TB of data produced by XORing calls to determine() on both sequences. PulleyRNG is one-dimensionally equidistributed across all 64-bit outputs, has 64 bits of state, natively outputs 64 bits at a time, can have its state set and skipped over as a StatefulRandomness and SkippingRandomness. It has a 1-to-1 correspondence between inputs and outputs for determine(long), and you can get the input to determine() that produced a particular long output by passing that output to inverseNextLong(long). It is largely the work of Pelle Evensen, who discovered that where a unary hash (called a determine() method here) can start with the XOR of the input and two rotations of that input, and that sometimes acts as a better randomization procedure than multiplying by a large constant (which is what LightRNG.determine(long), LinnormRNG.determine(long), and even ThrustAltRNG.determine(long) do). Evensen also crunched the numbers to figure out that n ^ n >>> A ^ n >>> B is a bijection for all distinct non-zero values for A and B, though this wasn't used in his unary hash rrxmrrxmsx_0.
The algorithm for determine(long) looks like this (nextLong() just calls determine() on a counter):
  1. XOR the input with two different bitwise rotations: n ^ (n << 41 | n >>> 23) ^ (n << 17 | n >>> 47)
  2. Multiply by a large constant, 0x369DEA0F31A53F85L, and store it in n
  3. XOR n with two different unsigned bitwise right shifts: n ^ n >>> 25 ^ n >>> 37
  4. Multiply by a large constant, 0xDB4F0B9175AE2165L, and store it in n
  5. XOR n with n right-shifted by 28, and return
This is the result of some simplifications on PelicanRNG (present here as DiverRNG.randomize(long)), which is ridiculously strong (passing the full battery of tests that rrxmrrxmsx_0 only narrowly failed) but not especially fast. PulleyRNG is an effort to speed up PelicanRNG just a little, but without doing the extensive testing that ensure virtually any bit pattern given to PelicanRNG will produce pseudo-random outputs. PulleyRNG does well in tough tests. Other than the input stream correlation test mentioned earlier, this also passes tests if the inputs are incremented by what is normally one of the worst-case scenarios for other generators -- using an increment that is the multiplicative inverse (mod 2 to the 64 in this case) of one of the fixed constants in the generator. The first multiplication performed here is by 0x369DEA0F31A53F85L, and 0xBE21F44C6018E14DL * 0x369DEA0F31A53F85L == 1L, so testing determine() with inputs that change by 0xBE21F44C6018E14DL should stress the generator, but instead it does fine through 32TB, with only one "unusual" anomaly rather early on.
Author:
Pelle Evensen, Tommy Ettinger
See Also:
Serialized Form

  • Constructor Summary

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

  • Method Summary

    Modifier and Type Method Description
    PulleyRNG 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)
    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)
    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()  
    static long inverseNextLong​(long out)
    Given the output of a call to nextLong() as out, this finds the state of the PulleyRNG that produce that output.
    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.
    void setState​(long seed)
    Sets the seed (also the current state) of this generator.
    long skip​(long advance)
    Advances or rolls back the SkippingRandomness' state without actually generating each number.
    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 PulleyRNG 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

    • skip

      public final long skip​(long advance)
      Description copied from interface: SkippingRandomness
      Advances or rolls back the SkippingRandomness' 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 RandomnessSource.nextLong(), and returns the random number produced at that step. Negative numbers can be used to step backward, or 0 can be given to get the most-recently-generated long from RandomnessSource.nextLong().
      Specified by:
      skip in interface SkippingRandomness
      Parameters:
      advance - Number of future generations to skip over; can be negative to backtrack, 0 gets the most-recently-generated number
      Returns:
      the random long generated after skipping forward or backwards by advance numbers

    • 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 PulleyRNG, 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 PulleyRNG, changed once per call to nextLong()

    • inverseNextLong

      public static long inverseNextLong​(long out)
      Given the output of a call to nextLong() as out, this finds the state of the PulleyRNG that produce that output. If you set the state of a PulleyRNG with setState(long) to the result of this method and then call nextLong() on it, you should get back out. This can also reverse determine(long); it uses the same algorithm as nextLong().
      This isn't as fast as nextLong(), but both run in constant time.
      This will not necessarily work if out was produced by a generator other than a PulleyRNG, or if it was produced with the bounded nextLong(long) method by any generator.
      Parameters:
      out - a long as produced by nextLong(), without changes
      Returns:
      the state of the RNG that will produce the given long

    • 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)
      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 PulleyRNG.determine(++state) or PulleyRNG.determine(--state) to produce a sequence of different numbers, but you can also use PulleyRNG.determine(state += 12345L) or any odd-number increment. All longs are accepted by this method, and all longs can be produced; passing 0 here will return 0.
      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)
      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 PulleyRNG.determineBounded(++state, bound) or PulleyRNG.determineBounded(--state, bound) to produce a sequence of different numbers, but you can also use PulleyRNG.determineBounded(state += 12345L, bound) or any odd-number increment. 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.
      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. determine(++state), where the increment for state should be odd but otherwise doesn't really matter. This should tolerate just about any increment 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 should tolerate just about any increment, 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