Package squidpony.squidmath

Class PermutedRNG

java.lang.Object
squidpony.squidmath.PermutedRNG
All Implemented Interfaces:
Serializable, RandomnessSource, SkippingRandomness, StatefulRandomness
public final class PermutedRNG
extends Object
implements RandomnessSource, StatefulRandomness, SkippingRandomness, Serializable
This is a RandomnessSource in the PCG-Random family. It performs pseudo- random modifications to the output based on the techniques from the Permuted Congruential Generators created by M.E. O'Neill. Specifically, this variant is: RXS M XS -- random xorshift, mcg multiply, fixed xorshift The most statistically powerful generator, but all those steps make it slower than some of the others.
Even though benchmarks on similar programs in C would lead you to believe this should be somewhat faster than LightRNG, benchmarking with JMH seems to show LightRNG being roughly 16% faster than PermutedRNG, and both drastically faster than java.util.Random . This generator was implemented incorrectly for a large part of its history, but it seems correct now, though it may be a little slower.
Author:
Melissa E. O'Neill (Go HMC!), Tommy Ettinger
See Also:
PintRNG is similar to this algorithm but uses only 32-bit math, where possible., Serialized Form

  • Field Summary

    Fields 
    Modifier and Type Field Description
    long state
    The state can be seeded with any value.

  • Constructor Summary

    Constructors 
    Constructor Description
    PermutedRNG()
    Creates a new generator seeded using Math.random.
    PermutedRNG​(long seed)
    Constructs a new PermutedRNG with the given seed as its state, exactly.

  • Method Summary

    Modifier and Type Method Description
    PermutedRNG 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)
    Given suitably-different inputs as state, this will permute that state to get a seemingly-unrelated number.
    static int determineBounded​(long state, int bound)
    Given suitably-different inputs as state, this will permute that state to get a seemingly-unrelated number as an int between 0 and bound.
    long getState()
    Gets the current state of this generator.
    int next​(int bits)
    Gets a random int with at most the specified number of bits.
    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) Calls nextLong() exactly once.
    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; the inner bound is 0.
    int nextInt​(int lower, int upper)
    Inclusive lower, exclusive upper.
    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 outer bound; the inner bound is 0.
    long nextLong​(long inner, long outer)
    Inclusive inner, exclusive outer; both inner and outer can be positive or negative.
    void setSeed​(long seed)
    Sets the seed of this generator (which is also the current state).
    void setState​(long seed)
    Sets the seed (also the current state) of this generator.
    long skip​(long advance)
    Advances or rolls back the PermutedRNG's state without actually generating each number.
    String toString()  

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

  • Field Details

    • state

      public long state
      The state can be seeded with any value.

  • Constructor Details

    • PermutedRNG

      public PermutedRNG()
      Creates a new generator seeded using Math.random.

    • PermutedRNG

      public PermutedRNG​(long seed)
      Constructs a new PermutedRNG with the given seed as its state, exactly.
      Parameters:
      seed - a long that will be used as-is for the state of a new PermutedRNG

  • Method Details

    • next

      public final int next​(int bits)
      Gets a random int with at most the specified number of bits. Equivalent in its effect on the state to calling nextLong() exactly one time.
      Specified by:
      next in interface RandomnessSource
      Parameters:
      bits - the number of bits to be returned, between 1 and 32
      Returns:
      a pseudo-random int with at most the specified bits

    • nextInt

      public int nextInt()
      Can return any int, positive or negative, of any size permissible in a 32-bit signed integer. Equivalent in its effect on the state to calling nextLong() exactly one time.
      Returns:
      any int, all 32 bits are random

    • 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 PermutedRNG 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 needs 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 int nextInt​(int bound)
      Exclusive on the outer bound; the inner bound is 0. Calls nextLong() exactly once.
      Parameters:
      bound - the upper bound; can be positive or negative
      Returns:
      a random int less than n and at least equal to 0

    • nextInt

      public int nextInt​(int lower, int upper)
      Inclusive lower, exclusive upper. The upper bound is really the outer bound, and the lower bound the inner bound, because upper is permitted to be less than lower, though upper is still exclusive there. Calls nextLong() exactly once.
      Parameters:
      lower - the lower bound, inclusive, can be positive or negative
      upper - the upper bound, exclusive, can be positive or negative
      Returns:
      a random int at least equal to lower and less than upper (if upper is less than lower, then the result will be less than or equal to lower and greater than upper)

    • nextLong

      public long nextLong​(long bound)
      Exclusive on the outer bound; the inner bound is 0. The bound may be negative, which will produce a non-positive result. Calls nextLong() exactly once.
      Parameters:
      bound - the outer exclusive bound; may be positive or negative
      Returns:
      a random long between 0 (inclusive) and bound (exclusive)

    • nextLong

      public long nextLong​(long inner, long outer)
      Inclusive inner, exclusive outer; both inner and outer can be positive or negative. Calls nextLong() exactly once.
      Parameters:
      inner - the inner bound, inclusive, can be positive or negative
      outer - the outer bound, exclusive, can be positive or negative and may be greater than or less than inner
      Returns:
      a random long that may be equal to inner and will otherwise be between inner and outer

    • nextDouble

      public double nextDouble()
      Gets a uniform random double in the range [0.0,1.0). Calls nextLong() exactly once.
      Returns:
      a random double at least equal to 0.0 and less than 1.0

    • nextDouble

      public 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. Calls nextLong() exactly once.
      Parameters:
      outer - the exclusive outer bound, can be negative
      Returns:
      a random double between 0.0 (inclusive) and outer (exclusive)

    • nextFloat

      public float nextFloat()
      Gets a uniform random float in the range [0.0,1.0) Calls nextLong() exactly once.
      Returns:
      a random float at least equal to 0.0f and less than 1.0f

    • nextBoolean

      public boolean nextBoolean()
      Gets a random value, true or false. Calls nextLong() exactly once.
      Returns:
      a random true or false value.

    • nextBytes

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

    • setSeed

      public void setSeed​(long seed)
      Sets the seed of this generator (which is also the current state).
      Parameters:
      seed - the seed to use for this PermutedRNG, as if it was constructed with this seed.

    • setState

      public 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 PermutedRNG, as if it was constructed with this seed.

    • getState

      public long getState()
      Gets the current state of this generator.
      Specified by:
      getState in interface StatefulRandomness
      Returns:
      the current seed of this PermutedRNG, changed once per call to nextLong()

    • skip

      public long skip​(long advance)
      Advances or rolls back the PermutedRNG'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()). Skipping ahead or behind takes more than constant time, unlike with LightRNG, but less time than calling nextLong() advance times. Skipping backwards by one step is the worst case for this technique.
      Specified by:
      skip in interface SkippingRandomness
      Parameters:
      advance - Number of future generations to skip past. Can be negative to backtrack.
      Returns:
      the number that would be generated after generating advance random numbers.

    • toString

      public String toString()
      Overrides:
      toString in class Object

    • determine

      public static long determine​(long state)
      Given suitably-different inputs as state, this will permute that state to get a seemingly-unrelated number. Unlike LightRNG.determine(long), this will not work with inputs that are sequential, and it is recommended that subsequent calls change state with a linear congruential generator like PermutedRNG.determine(state = state * 0x5851F42D4C957F2DL + 0x14057B7EF767814FL). It will be correct for any inputs, but if state is 0, then this will return 0.
      Parameters:
      state - a long that should be changed with state = state * 0x5851F42D4C957F2DL + 0x14057B7EF767814FL
      Returns:
      a pseudo-random long determined from state

    • determineBounded

      public static int determineBounded​(long state, int bound)
      Given suitably-different inputs as state, this will permute that state to get a seemingly-unrelated number as an int between 0 and bound. Unlike LightRNG.determine(long), this will not work with inputs that are sequential, and it is recommended that subsequent calls change state with a linear congruential generator like PermutedRNG.determine(state = state * 0x5851F42D4C957F2DL + 0x14057B7EF767814FL). It will be correct for any inputs, but if state is 0, then this will return 0.
      Parameters:
      state - a long that should be changed with state = state * 0x5851F42D4C957F2DL + 0x14057B7EF767814FL
      bound - the exclusive outer bound on the numbers this can produce, as an int
      Returns:
      a pseudo-random int between 0 (inclusive) and bound (exclusive) determined from state