Package squidpony.squidmath

Class MiniMover64RNG

java.lang.Object
squidpony.squidmath.MiniMover64RNG
All Implemented Interfaces:
Serializable, RandomnessSource
public final class MiniMover64RNG
extends Object
implements RandomnessSource, Serializable
The fastest generator in this library on desktop JVMs; one of Mark Overton's subcycle generators from this article, specifically a CMR with a 64-bit state, that has its result multiplied by a constant. Its period is unknown, and it has multiple subcycles with different period lengths, but one is at the very least 2 to the 42, since the generator passes PractRand after generating that many 64-bit integers (it passes 32TB with no anomalies), and all states that can be produced using seed(int) have a minimum period of 2 to the 20, or roughly one million. It also can pass TestU01's BigCrush suite in both forward and reversed bit order, though not for all seeds (as expected).
Notably, this generator's nextLong() method is extremely small (as are all of the methods that use it as a basis), which may help with inlining decisions for HotSpot. Generating the next step just needs a bitwise rotation of the current state, multiplying the result by a 32-bit constant, and assigning that to state. Generating a long after that only needs a multiplication by another constant, which doesn't have the issues with reversed-bits testing that some other generators do when they multiply as their only output step (xorshift128 notably has patterns in its low bits, so multiplying by a constant doesn't help those bits, but the CMR generator here has no such low-bit problems). This means only three math instructions need to be performed to get a new random number (bitwise rotate left, multiply, multiply), which is extremely low for a high-quality generator. While the CMR state change does not pipeline well, the ease of calculating a complete number seems to make up for it on desktop JVMs.
The choice of constants for the multipliers and for the rotation needs to be carefully verified; earlier choices came close to failing PractRand at 8TB (and were worsening, so were likely to fail at 16TB), but this set of constants has higher quality in testing. Other constants did well in PractRand but had failures in TestU01 (even down to SmallCrush when reversed). For transparency, the constants used in this version:
  • The state multiplier is 0xAC564B05L (or 2891336453L), which is one of the constants evaluated in Tables of Linear Congruential Generators of Different Sizes and Good Lattice Structure, by Pierre L'Ecuyer, to be optimal for an LCG with a modulus of 2 to the 32 and an odd addend (this doesn't have an addend, but it isn't an LCG either).
  • The post-processing multiplier is 0x818102004182A025L (or -9115001970698837979L), which is a probable prime with a low Hamming weight (14 bits of 64 are set), in the hope it will perform well speed-wise. This number doesn't seem as critical to the quality of the generator, and some other multipliers probably work just as well.
  • A left rotation constant of 29, which was chosen because it seems to allow the generator to pass certain TestU01 statistical tests, such as Birthday Spacings, where most other rotations do not.

This is a RandomnessSource but not a StatefulRandomness because it needs to take care and avoid seeds that would put it in a short-period subcycle. One long test brute-force checked all seeds from 1 to Math.pow(2, 25) and validated that each of their periods is at least Math.pow(2, 20) - 1. This means that as long as a period as low as 1 million is rarely allowed, a starting state can be quickly chosen from a 32-bit int by using the bottom 25 bits of the int (plus 1, to disallow the 0 state) and using the remaining 7 bits to step up to 127 times through the generator.
The name comes from M. Overton, who discovered this category of subcycle generators, and also how this generator can really move when it comes to speed. This generator has less state than Mover64RNG, has a shorter period than it, and is faster than it in all aspects.
Created by Tommy Ettinger on 11/26/2018.
Author:
Mark Overton, Tommy Ettinger
See Also:
Serialized Form

  • Constructor Summary

    Constructors 
    Constructor Description
    MiniMover64RNG()
    Calls seed(int) with a random int value (obtained using Math.random()).
    MiniMover64RNG​(int state)
    The recommended constructor, this guarantees the generator will have a period of at least 2 to the 20 (roughly one million, but most if not all initial states will have much longer periods).
    MiniMover64RNG​(long state)
    Not advised for external use; prefer MiniMover64RNG(int) because it guarantees a good subcycle.

  • Method Summary

    Modifier and Type Method Description
    MiniMover64RNG copy()
    Produces a copy of this MiniMover64RNG 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 state; if this generator was set with MiniMover64RNG(), MiniMover64RNG(int), or seed(int), then this will be on a good subcycle, otherwise it may not be.
    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.
    double nextDouble()
    Gets a pseudo-random double between 0.0 (inclusive) and 1.0 (exclusive).
    float nextFloat()
    Gets a pseudo-random float between 0.0f (inclusive) and 1.0f (exclusive).
    int nextInt()  
    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 seed​(int s)
    Seeds the state using all bits of the given int s.
    void setState​(long state)
    Sets the state to any long, which may put the generator in a low-period subcycle.
    String toString()  

    Methods inherited from class java.lang.Object

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

  • Constructor Details

    • MiniMover64RNG

      public MiniMover64RNG()
      Calls seed(int) with a random int value (obtained using Math.random()).

    • MiniMover64RNG

      public MiniMover64RNG​(int state)
      The recommended constructor, this guarantees the generator will have a period of at least 2 to the 20 (roughly one million, but most if not all initial states will have much longer periods). All ints are permissible values for state.
      Parameters:
      state - any int; will be used to get the actual state used in the generator (which is a long internally)

    • MiniMover64RNG

      public MiniMover64RNG​(long state)
      Not advised for external use; prefer MiniMover64RNG(int) because it guarantees a good subcycle. This constructor allows all subcycles to be produced, including ones with a shorter period.
      Parameters:
      state - the state to use, exactly unless it is 0 (then this uses 1)

  • Method Details

    • seed

      public final void seed​(int s)
      Seeds the state using all bits of the given int s. Between 33554432 and 4294967296 seeds are possible, with the actual count probably much closer to 4294967296. This treats the bottom 25 bits of s (plus 1, to avoid a seed of 0) as the starting point and then generates the next state at most 127 times, with each generated state taking less time than nextLong(). Some of the starting states are entirely possible to be within 127 steps of another starting state, so not all seeds are necessarily unique. This is not guaranteed to put the generator on an optimal subcycle, but it is guaranteed that any subcycle will have a period of at least 1048575.
      Parameters:
      s - all bits are used, none verbatim (0 is tolerated)

    • nextInt

      public final int nextInt()

    • 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()
      Description copied from interface: RandomnessSource
      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)

    • nextDouble

      public final double nextDouble()
      Gets a pseudo-random double between 0.0 (inclusive) and 1.0 (exclusive).
      Returns:
      a pseudo-random double between 0.0 (inclusive) and 1.0 (exclusive)

    • nextFloat

      public final float nextFloat()
      Gets a pseudo-random float between 0.0f (inclusive) and 1.0f (exclusive).
      Returns:
      a pseudo-random float between 0.0f (inclusive) and 1.0f (exclusive)

    • copy

      public MiniMover64RNG copy()
      Produces a copy of this MiniMover64RNG 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
      Returns:
      a copy of this MiniMover64RNG

    • getState

      public long getState()
      Gets the state; if this generator was set with MiniMover64RNG(), MiniMover64RNG(int), or seed(int), then this will be on a good subcycle, otherwise it may not be.
      Returns:
      the state, a long

    • setState

      public void setState​(long state)
      Sets the state to any long, which may put the generator in a low-period subcycle. Use seed(int) to guarantee a good subcycle.
      Parameters:
      state - any int

    • 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