Package squidpony.squidmath

Class LinnormRNG

java.lang.Object
squidpony.squidmath.LinnormRNG
All Implemented Interfaces:
Serializable, RandomnessSource, StatefulRandomness
public final class LinnormRNG
extends Object
implements RandomnessSource, StatefulRandomness, Serializable
A mid-high-quality StatefulRandomness that is the second-fastest 64-bit generator in this library that is 1-dimensionally equidistributed across its 64-bit outputs. Has a period of 2 to the 64, and permits all states. Passes all statistical tests in PractRand up to 32TB of data. DiverRNG is a variant that is a little faster, while keeping the same other qualities, so it is currently recommended over LinnormRNG (however, the same structure is shared between LinnormRNG and MizuchiRNG, and Mizuchi has some extra features that Diver lacks). Has 64 bits of state and natively outputs 64 bits at a time, changing the state with a basic linear congruential generator (it is simply state = state * 3935559000370003845L + 1L, with the large multiplier found by L'Ecuyer in a 1999 paper). Starting with that LCG's output, it xorshifts that output twice (using z ^= (z >>> 23) ^ (z >>> 47);), multiplies by a very large negative long, then returns another xorshift. Considering that some seeds don't have any anomalies in 8TB with Linnorm, the quality is probably fine except for the known potential issue that it can't return duplicate outputs until its period has cycled. ThrustAltRNG and MiniMover64RNG are faster (tied for first place), but unlike those, Linnorm 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, while MiniMover64RNG cycles at some point before 2 to the 64 but after 2 to the 42 (it doesn't produce any duplicates until then, but it also can't produce all values). Notably, this generator is faster than LightRNG with similar quality, and also faster than XoRoRNG while passing tests that XoRoRNG always or frequently fails (and fails early), such as binary matrix rank tests. It is slower than DiverRNG, which is a variant on the structure of LinnormRNG.
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(). MizuchiRNG uses the same algorithm except for the number added in the LCG state update; here this number is always 1, but in MizuchiRNG it can be any odd long. This means that any given MizuchiRNG object has two long values stored in it instead of the one here, but it allows two MizuchiRNG objects with different streams to produce different, probably-not-correlated sequences of results, even with the same seed. This property may be useful for cases where an adversary is trying to predict results in some way, though using different streams for this purpose isn't enough and should be coupled with truncation of a large part of output (see PCG-Random's techniques for this).
The name comes from LINear congruential generator this uses to change it state, while the rest is a NORMal SplitMix64-like generator. "Linnorm" is a Norwegian name for a kind of dragon, as well.
Written June 29, 2019 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. The LCG state multiplier is listed in a paper by L'Ecuyer from 1999, Tables of Linear Congruential Generators of Different Sizes and Good Lattice Structure. The other multiplier is from PCG-Random, and that's both the nothing-up-my-sleeve numbers used here. Thanks also to Sebastiano Vigna and David Blackwell for creating the incredibly fast xoroshiro128+ generator and also very fast HWD tool; the former inspired me to make my code even faster and the latter tool seems useful so far in proving the quality of the generator (LinnormRNG passes over 100TB of HWD, and probably would pass much more if I gave it more days to run).
Author:
Tommy Ettinger
See Also:
Serialized Form

  • Constructor Summary

    Constructors 
    Constructor Description
    LinnormRNG()
    Constructor that seeds the generator with two calls to Math.random.
    LinnormRNG​(long seed)
    Constructor that uses the given seed as the state without changes; all long seeds are acceptable.
    LinnormRNG​(CharSequence seed)
    Constructor that hashes seed with CrossHash.hash64(CharSequence) and uses the result as the state.

  • Method Summary

    Modifier and Type Method Description
    LinnormRNG copy()
    Produces a copy of this LinnormRNG 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()  
    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.
    String toString()  

    Methods inherited from class java.lang.Object

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

  • Constructor Details

    • LinnormRNG

      public LinnormRNG()
      Constructor that seeds the generator with two calls to Math.random.

    • LinnormRNG

      public LinnormRNG​(long seed)
      Constructor that uses the given seed as the state without changes; all long seeds are acceptable.
      Parameters:
      seed - any long, will be used exactly

    • LinnormRNG

      public LinnormRNG​(CharSequence seed)
      Constructor that hashes seed with CrossHash.hash64(CharSequence) and uses the result as the state.
      Parameters:
      seed - any CharSequence, such as a String or StringBuilder; should probably not be null (it might work?)

  • 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 LinnormRNG copy()
      Produces a copy of this LinnormRNG 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 LinnormRNG

    • 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. This uses a biased technique to get numbers from large ranges, but the amount of bias is incredibly small (expected to be under 1/1000 if enough random ranged numbers are requested, which is about the same as an unbiased method that was also considered). It may have noticeable bias if the LinnormRNG's period is exhausted by only calls to this method, which would take months on 2018-era consumer hardware. Unlike all unbiased methods, this advances the state by an equivalent to exactly one call to nextLong(), where rejection sampling would sometimes advance by one call, but other times by arbitrarily many more.
      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 LinnormRNG, 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 LinnormRNG, 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)
      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 LinnormRNG.determine(++state) or LinnormRNG.determine(--state) to produce a sequence of different numbers, but you can also use LinnormRNG.determine(state += 12345L) or any odd-number increment. 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.
      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 LinnormRNG.determineBounded(++state, bound) or LinnormRNG.determineBounded(--state, bound) to produce a sequence of different numbers, but you can also use LinnormRNG.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 multiplies state by 0x632BE59BD9B4E019L 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 less than 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 0x632BE59BD9B4E019L 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 less than 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