Package squidpony.squidmath

Class ThrustAltRNG

java.lang.Object
squidpony.squidmath.ThrustAltRNG
All Implemented Interfaces:
Serializable, RandomnessSource, SkippingRandomness, StatefulRandomness
public final class ThrustAltRNG
extends Object
implements StatefulRandomness, SkippingRandomness, Serializable
A random number generator that is extremely fast but can't return all possible results. ThrustAltRNG passes TestU01's BigCrush, which is a difficult statistical quality test. On gjrand's "testunif" checks, this does very well on 100GB of tested data, with the "Overall summary one sided P-value P = 0.981", where 1 is perfect and 0.1 or less is a failure. On PractRand, this passes all 32TB of generated numbers without finding any failures (and very rarely finding anomalies). Like LightRNG, this changes its state with a steady fixed increment, and does hash-like adjustments to the current state to randomize it (the change is not a cipher because it is not reversible; this may be an advantage for some usage). The period on ThrustAltRNG is 2 to the 64. ThrustAltRNG is very strong on speed, outpacing the default generator for RNG, DiverRNG, by a small margin, and most other RandomnessSources in SquidLib by a larger margin (it is slower than MiniMover64RNG, but this has a better period). Similarly to other hash-like PRNGs such as LightRNG, ThrustAltRNG has a determine(long) method that takes a state as a long and returns a deterministic random number (each input has one output, though in this case the reverse isn't true and some outputs will be returned by multiple inputs). Like LightRNG, but unlike an LCG such as Random, changing the seed even slightly generally produces completely different results, which applies primarily to determine() but also the first number generated in a series of nextLong() calls. This generator is GWT-safe but will be much slower on GWT than generators designed for usage there, such as GWTRNG or Lathe32RNG.
Because this generator can't produce all longs (it is not equidistributed), that alone is enough to discount its use in some (mainly scientific) scenarios, although it passes all major testing suites (TestU01's BigCrush, PractRand over the full 32TB of tests, and gjrand to some degree, at least better than most). DiverRNG is the default generator after ThrustAltRNG was used extensively for some time, since DiverRNG passes the same tests, is almost as fast, and is known to produce all longs over the course of its period. One small change was required to pass a test added in PractRand version 0.94, going from a shift of 22 to a shift of 23 at the end of the generation. Without this change, ThrustAltRNG will eventually fail PractRand (failing "TMFn" tests, which check for patterns like those in a linear congruential generator such as Random), but only after 16TB of data has been analyzed. Even if using a version before the shift was changed on June 8, 2019, the quality is probably fine.
There was a ThrustRNG in SquidLib, but it failed statistical tests badly in roughly a minute of testing, so even though it was faster it probably wasn't a good idea to use it. ThrustAltRNG modifies ThrustRNG's algorithm very heavily, and isn't especially similar, but the name stuck, I guess. The idea behind the name is that the generator is acting like a thrust in fencing, pushing quickly but leaving a hole (not in the quality, but in the distribution).
Created by Tommy Ettinger on 10/18/2017.
See Also:
Serialized Form

  • Field Summary

    Fields 
    Modifier and Type Field Description
    long state
    Can be any long value.

  • Constructor Summary

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

  • Method Summary

    Modifier and Type Method Description
    ThrustAltRNG 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)
    Returns a random permutation of state; if state is the same on two calls to this, this will return the same number.
    static int determineBounded​(long state, int bound)
    Given a state that should usually change each time this is called, and a bound that limits the result to some (typically fairly small) int, produces a pseudo-random int between 0 and bound (exclusive).
    static int determineBoundedShort​(int state, int bound)
    Given an int state that should usually change each time this is called, and a bound that limits the result to some (typically fairly small) int, produces a pseudo-random int between 0 and bound (exclusive).
    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.
    static float determineFloatFromInt​(int state)
    Returns a random float that is deterministic based on an int state; if state is the same on two calls to this, this will return the same float.
    static int determineInt​(int state)
    Returns a random permutation of state; if state is the same on two calls to this, this will return the same number.
    boolean equals​(Object o)  
    long getState()
    Get the current internal state of the StatefulRandomness as a long.
    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.
    long nextLong()
    Using this method, any algorithm that needs to efficiently generate more than 32 bits of random data can interface with this randomness source.
    void setState​(long state)
    Set the current internal state of this StatefulRandomness with a long.
    long skip​(long advance)
    Advances or rolls back the ThrustAltRNG'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

    • state

      public long state
      Can be any long value.

  • Constructor Details

  • Method Details

    • getState

      public long getState()
      Get the current internal state of the StatefulRandomness as a long.
      Specified by:
      getState in interface StatefulRandomness
      Returns:
      the current internal state of this object.

    • setState

      public void setState​(long state)
      Set the current internal state of this StatefulRandomness with a long.
      Specified by:
      setState in interface StatefulRandomness
      Parameters:
      state - a 64-bit long

    • next

      public final int next​(int bits)
      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()
      Using this method, any algorithm that needs to efficiently generate more than 32 bits of random data can interface with this randomness source.

      Get a random long between Long.MIN_VALUE and Long.MAX_VALUE (both inclusive).

      Specified by:
      nextLong in interface RandomnessSource
      Returns:
      a random long between Long.MIN_VALUE and Long.MAX_VALUE (both inclusive)

    • skip

      public final long skip​(long advance)
      Advances or rolls back the ThrustAltRNG'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-recently-generated number
      Returns:
      the random long generated after skipping forward or backwards by advance numbers

    • copy

      public ThrustAltRNG 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

    • 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)
      Returns a random permutation of state; if state is the same on two calls to this, this will return the same number. This is expected to be called with some changing variable, e.g. determine(++state), where the increment for state should be odd but otherwise doesn't really matter. This multiplies state by 0x6C8E9CF570932BD5L 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.
      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 permutation of state

    • 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 0x6C8E9CF570932BD5L 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 0x6C8E9CF570932BD5L 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

    • determineBounded

      public static int determineBounded​(long state, int bound)
      Given a state that should usually change each time this is called, and a bound that limits the result to some (typically fairly small) int, produces a pseudo-random int between 0 and bound (exclusive). The bound can be negative, which will cause this to produce 0 or a negative int; otherwise this produces 0 or a positive int. The state should change each time this is called, generally by incrementing by an odd number (not an even number, especially not 0). It's fine to use determineBounded(++state, bound) to get a different int each time. The period is usually 2 to the 64 when you increment or decrement by 1, but some bounds may reduce the period (in the extreme case, a bound of 1 would force only 0 to be generated, so that would make the period 1).
      Parameters:
      state - a variable that should be different every time you want a different random result; using determineBounded(++state, bound) is recommended to go forwards or determineBounded(--state, bound) to generate numbers in reverse order
      bound - the outer exclusive bound for the int this produces; can be negative or positive
      Returns:
      a pseudo-random int between 0 (inclusive) and bound (exclusive)

    • determineInt

      public static int determineInt​(int state)
      Returns a random permutation of state; if state is the same on two calls to this, this will return the same number. This is expected to be called with some changing variable, e.g. determine(state = state + 1 | 0), where the increment for state should be odd but otherwise doesn't really matter (the | 0 is needed to force overflow to occur correctly on GWT; if you know you won't target GWT you can use determine(++state) instead). This multiplies state by 0x62BD5 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 32 if you increment or decrement by 1 (and perform any bitwise operation, such as | 0, if you might target GWT). If you use this on GWT and don't perform a bitwise operation on the new value for state, then the period will gradually shrink as precision is lost by the JavaScript double that GWT will use for state as a Java int. If you know that state will start at 0 and you call with determine(++state), then on GWT you may not have to worry at all until 2 to the 34 calls have been made, after which state may cease to have the precision to represent an increase by 1 when the math inside this method is considered. The period will have been exhausted by that point anyway (4 times), so it's more of a concern if state may start at a much higher int.
      This only uses int math, and should be fast on GWT.
      Parameters:
      state - a variable that should be different every time you want a different random result; using determine(state = state + 1 | 0) is recommended to go forwards or determine(state = state - 1 | 0) to generate numbers in reverse order
      Returns:
      a pseudo-random permutation of state

    • determineBoundedShort

      public static int determineBoundedShort​(int state, int bound)
      Given an int state that should usually change each time this is called, and a bound that limits the result to some (typically fairly small) int, produces a pseudo-random int between 0 and bound (exclusive). The bound should be between -65536 and 65535, that is, the range of a short. It can be negative, which will cause this to produce 0 or a negative int; otherwise this produces 0 or a positive int. The state should change each time this is called, generally by incrementing by an odd number (not an even number, especially not 0). It's fine to use determineBounded(++state, bound) to get a different int each time. The period is usually 2 to the 64 when you increment or decrement by 1, but some bounds may reduce the period (in the extreme case, a bound of 1 would force only 0 to be generated, so that would make the period 1).
      This only uses int math, unlike other bounded determine() methods, but this requires the bound to be small. It should be very fast on GWT.
      Parameters:
      state - an int variable that should be different every time you want a different random result; using determineBounded(++state, bound) is recommended to go forwards or determineBounded(--state, bound) to generate numbers in reverse order
      bound - the outer exclusive bound for the int this produces; should be between -65536 and 65535, inclusive
      Returns:
      a pseudo-random int between 0 (inclusive) and bound (exclusive)

    • determineFloatFromInt

      public static float determineFloatFromInt​(int state)
      Returns a random float that is deterministic based on an int 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 0x62BD5 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 32 if you increment or decrement by 1, but there are only 2 to the 30 possible floats between 0 and 1, and this can generate less than 2 to the 24 of them.
      Except for the final conversion to float, this only uses int math, and should be fast on GWT.
      Parameters:
      state - an int 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