Package squidpony.squidmath

Class Mover64RNG

java.lang.Object
squidpony.squidmath.Mover64RNG
All Implemented Interfaces:
Serializable, RandomnessSource
public final class Mover64RNG
extends Object
implements RandomnessSource
One of Mark Overton's subcycle generators from this article, specifically a cmr^cmr with two 64-bit states. It is extremely fast, faster than LinnormRNG and TangleRNG, but its period is unknown. The period is at the very least 2 to the 38, since each of its sub-generators has been checked up to that period length without running out of period, and the total period of a Mover64RNG should be greater than 2 to the 64 with a very high likelihood. The total period is also very unlikely to be a power of two or even a number close to a power of two; it could be odd or even. The guarantees of Linnorm and Tangle that they are certain to have a period of 2 to the 64 may be worthwhile reasons to use them; they also will be faster when setting the state often. LightRNG is a SkippingRandomness and a StatefulRandomness, but this is neither, so you may want to prefer LightRNG for that reason. This generator is not equidistributed, so it can return some long values more often than others and some not at all; you may want to use a generator with guarantees on distribution if you don't want to see some returned values (or pairs of values) more often than others. Starfish32RNG is 2-dimensionally equidistributed for ints, so it returns all pairs of ints with equal likelihood, and it may be a good RandomnessSource to use if distribution matters (though you should prefer GWTRNG, which is implemented using Starfish32RNG, because it is specialized to use a 32-bit generator).
This seems to do well in PractRand testing, passing a full 32TB with two ("unusual") anomalies, but this is not one of the exact generators Overton tested. "Chaotic" generators like this one tend to score well in PractRand, but it isn't clear if they will fail other tests (in particular, they probably can't generate all possible long values, and maybe can't generate some ints). This generator is not equidistributed.
The generator has two similar parts, each updated without needing to read from the other part. Each is a 64-bit CMR generator, which multiplies a state by a constant, rotates by another constant, and stores that as the next state. The multiplier constants used here were chosen arbitrarily, since almost all odd-number multipliers produce a period for a 64-bit CMR generator that is too long to iterate through and compare. One multiplier is close to the LCG multiplier used in PractRand (0x41C64E6B); the other is very close to the golden ratio times 2 to the 32 (0x9E3779B9). Better multipliers are almost guaranteed to exist, but finding them would be a challenge. The rotation constants, 28 and 37, were chosen so they were sufficiently different and so the sum of their (left or right) rotation amounts is close to 64, which seems to help quality. Oddly, substituting an addition for one of the two multiplications slows this generator down reliably, and does nothing to help quality. Even though addition should be faster, the two near-identical operations performed on two states may be able to be compiled into vector operations if the compiler is clever enough, but an addition on one state and a multiplication on the other would not make sense to see SIMD optimization.
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. It uses two generators with different cycle lengths, and skips at most 65536 times into each generator's cycle independently when seeding. It uses constants to store 128 known midpoints for each generator, which ensures it calculates an advance for each generator at most 511 times. There are 2 to the 32 possible starting states for this generator when using setState(int), but it is unknown if that method actually puts the generator in the longest possible cycle, or just a sufficiently long one.
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.
Created by Tommy Ettinger on 9/13/2018.
Author:
Mark Overton, Tommy Ettinger
See Also:
Serialized Form

  • Constructor Summary

    Constructors 
    Constructor Description
    Mover64RNG()  
    Mover64RNG​(int state)  
    Mover64RNG​(long stateA, long stateB)
    Not advised for external use; prefer Mover64RNG(int) because it guarantees a good subcycle.

  • Method Summary

    Modifier and Type Method Description
    Mover64RNG copy()
    Produces a copy of this Mover64RNG 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 getStateA()
    Gets the "A" part of the state; if this generator was set with Mover64RNG(), Mover64RNG(int), or setState(int), then this will be on the optimal subcycle, otherwise it may not be.
    long getStateB()
    Gets the "B" part of the state; if this generator was set with Mover64RNG(), Mover64RNG(int), or setState(int), then this will be on the optimal 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.
    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 setState​(int s)  
    void setStateA​(long stateA)
    Sets the "A" part of the state to any long, which may put the generator in a low-period subcycle.
    void setStateB​(long stateB)
    Sets the "B" part of 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

  • Method Details

    • setState

      public final void setState​(int s)

    • 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)

    • copy

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

    • getStateA

      public long getStateA()
      Gets the "A" part of the state; if this generator was set with Mover64RNG(), Mover64RNG(int), or setState(int), then this will be on the optimal subcycle, otherwise it may not be.
      Returns:
      the "A" part of the state, an int

    • getStateB

      public long getStateB()
      Gets the "B" part of the state; if this generator was set with Mover64RNG(), Mover64RNG(int), or setState(int), then this will be on the optimal subcycle, otherwise it may not be.
      Returns:
      the "B" part of the state, an int

    • setStateA

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

    • setStateB

      public void setStateB​(long stateB)
      Sets the "B" part of the state to any long, which may put the generator in a low-period subcycle. Use setState(int) to guarantee a good subcycle.
      Parameters:
      stateB - 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