Package squidpony.squidmath

Class MizuchiRNG

java.lang.Object
squidpony.squidmath.MizuchiRNG
All Implemented Interfaces:
Serializable, RandomnessSource, StatefulRandomness
public final class MizuchiRNG
extends Object
implements StatefulRandomness, Serializable
A high-quality StatefulRandomness based on LinnormRNG but modified to allow any odd number as a stream, instead of LinnormRNG's hardcoded stream of 1. Although some streams may have quality issues, the structure is based on a linear congruential generator where the stream is the additive component, and in that context all odd numbers are usually considered equally effective. Has 64 bits of state, 64 bits used to store a stream (which cannot be changed after construction) and natively outputs 64 bits at a time. Changes its state with a basic linear congruential generator (it is simply state = state * 3935559000370003845L + stream). Starting with that LCG's output, it xorshifts that output twice, multiplies by a very large negative long, then returns another xorshift. Like LinnormRNG, the output of this simple function passes all 32TB of PractRand (for one stream, it had 3 anomalies, but another had none, and none were ever significant or persistent), meaning its statistical quality is excellent. The speed of this particular class isn't fully clear yet, but benchmarks performed under the heavy load of PractRand testing happening at the same time appeared to show no significant difference between LinnormRNG and MizuchiRNG in speed (which means it's tied for second place in its category, behind DiverRNG).
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(). LinnormRNG uses the same algorithm except for the number added in the LCG state update; there this number is always 1, but here it can be any odd long. This means that any given MizuchiRNG object has two long values stored in it instead of the one in a LinnormRNG, 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 combining the concept of a linnorm, which is a dragon and the namesake of LinnormRNG, with streams, since Mizuchi allows many possible streams, to get the concept of a river-or-stream-dwelling dragon. The mizuchi is a (by some versions of the story) river dragon from Japanese mythology.
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
    MizuchiRNG()
    Creates a new generator seeded using Math.random.
    MizuchiRNG​(long seed)  
    MizuchiRNG​(long seed, long stream)  
    MizuchiRNG​(String seed)  

  • Method Summary

    Modifier and Type Method Description
    MizuchiRNG 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.
    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 the upper bound.
    long nextLong​(long lower, long upper)
    Inclusive lower, exclusive upper.
    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 MizuchiRNG 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 final long nextLong​(long bound)
      Exclusive on the upper bound. The lower bound is 0.
      Parameters:
      bound - the upper bound; should be positive (if negative, this returns 0)
      Returns:
      a random long less than n

    • nextLong

      public final long nextLong​(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 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