Package squidpony.squidmath

Class BasicRandom64

java.lang.Object
java.util.Random
squidpony.squidmath.BasicRandom64
All Implemented Interfaces:
Serializable, RandomnessSource
public class BasicRandom64
extends Random
implements RandomnessSource, Serializable
A high-quality and very fast RNG that has no apparent visual artifacts here; uses Mark Overton's CMR subcycle generator type, with a multiplication on the output. This is meant to be an answer to when people ask for a bare-minimum generator that's still "good enough" for games. It still passes at least 8TB of PractRand testing and passes TestU01 with both the bits in normal forward order and in reversed bit order, which is remarkable for a generator this small and simple. It has an unknown period that is fairly high; unless the seed used puts the generator in a worse cycle (some of which have a much lower period, like the seed 0), the period probably won't be exhausted without hours (possibly days) of pure random number generation. It cannot produce all possible longs in its longest cycle, and it can't produce even a fraction of all possible longs in its smallest cycle.
This implements RandomnessSource, but if you just want to copy this class with no dependencies, then the class declaration can easily be changed to public class BasicRandom64 extends Random implements Serializable without any other changes. Note, it does extend java.util.Random for additional ease of integration, but doesn't use the slow synchronized keyword that Random's implementations do.
This Dr. Dobb's article has more on this type of generator. A multiplication applied to the output of a CMR seems to be enough to pass stringent testing, which is amazing.
Author:
Mark Overton, Tommy Ettinger
See Also:
Serialized Form

  • Field Summary

    Fields 
    Modifier and Type Field Description
    long state  

  • Constructor Summary

    Constructors 
    Constructor Description
    BasicRandom64()
    Calls seed(int) with a random int value (obtained using Math.random()).
    BasicRandom64​(int seed)
    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).
    BasicRandom64​(long seed)
    Like BasicRandom64(int), this doesn't use the seed as-is, and instead uses it to get a valid state (which is a long internally).

  • Method Summary

    Modifier and Type Method Description
    BasicRandom64 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.
    long getState()  
    int next​(int bits)
    Gets an int with at most the specified amount of bits; don't confuse this with nextInt(int), which gets a number between 0 and its int argument, where this draws from a different (larger) range of random results.
    int nextInt()  
    int nextInt​(int bound)
    Returns a random non-negative integer between 0 (inclusive) and the given bound (exclusive), or 0 if the bound is 0.
    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.
    long nextLong​(long bound)
    Exclusive on bound (which must be positive), with an inner bound of 0.
    void seed​(int s)
    Seeds the state using all bits of the given int s.
    void setSeed​(long seed)
    Sets the seed using a long, passing its argument to setState(long).
    void setState​(long seed)  
    <T> T[] shuffle​(T[] elements)
    Shuffle an array using the Fisher-Yates algorithm and returns a shuffled copy, freshly-allocated, without modifying elements.
    <T> List<T> shuffleInPlace​(List<T> elements)
    Shuffles a Collection of T items in-place using the Fisher-Yates algorithm.
    <T> T[] shuffleInPlace​(T[] elements)
    Shuffles an array in-place using the Fisher-Yates algorithm.
    <T> T[] shuffleInPlace​(T[] elements, int length)
    Shuffles an array in-place using the Fisher-Yates algorithm, affecting indices from 0 (inclusive) to length (exclusive).
    protected static <T> void swap​(T[] arr, int pos1, int pos2)
    Mutates the array arr by switching the contents at pos1 and pos2.

    Methods inherited from class java.util.Random

    doubles, doubles, doubles, doubles, ints, ints, ints, ints, longs, longs, longs, longs, nextBoolean, nextBytes, nextDouble, nextFloat, nextGaussian

    Methods inherited from class java.lang.Object

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

  • Field Details

  • Constructor Details

    • BasicRandom64

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

    • BasicRandom64

      public BasicRandom64​(int seed)
      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 the seed parameter.
      Parameters:
      seed - any int; will be used to get the actual state used in the generator (which is a long internally)

    • BasicRandom64

      public BasicRandom64​(long seed)
      Like BasicRandom64(int), this doesn't use the seed as-is, and instead uses it to get a valid state (which is a long internally). If you want to duplicate the state of another BasicRandom64, get the existing state either with the field state or with getState() (you could store the state and load it later at this stage), then make some new BasicRandom64 (such as with new BasicRandom64(0);) and call setState(long) with the previous state. You can also use copy().
      Parameters:
      seed - any long; will be mixed around and given to seed(int) as an int, not used as-is

  • 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 top 25 bits of s (moved to the bottom, 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)

    • getState

      public long getState()

    • setState

      public void setState​(long seed)

    • 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
      Overrides:
      nextLong in class Random
      Returns:
      a random long between Long.MIN_VALUE and Long.MAX_VALUE (both inclusive)

    • next

      public final int next​(int bits)
      Gets an int with at most the specified amount of bits; don't confuse this with nextInt(int), which gets a number between 0 and its int argument, where this draws from a different (larger) range of random results. For example, next(2) can return any 2-bit int, which is limited to 0, 1, 2, or 3. Note that if you request 0 bits, this can give you any int (32 bits).
      Specified by:
      next in interface RandomnessSource
      Overrides:
      next in class Random
      Parameters:
      bits - the number of bits to get, from 1 to 32
      Returns:
      an int with at most the specified bits

    • nextInt

      public final int nextInt()
      Overrides:
      nextInt in class Random

    • nextInt

      public int nextInt​(int bound)
      Returns a random non-negative integer between 0 (inclusive) and the given bound (exclusive), or 0 if the bound is 0. The bound can be negative, which will produce 0 or a negative result.
      Credit goes to Daniel Lemire, http://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/
      Overrides:
      nextInt in class Random
      Parameters:
      bound - the outer bound (exclusive), can be negative or positive
      Returns:
      the found number

    • nextLong

      public long nextLong​(long bound)
      Exclusive on bound (which must be positive), with an inner bound of 0. If bound is negative or 0 this always returns 0.
      Credit for this method goes to Rafael Baptista's blog for the original idea, and the JDK10 Math class' usage of Karatsuba multiplication 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; should be positive, otherwise this always returns 0L
      Returns:
      a random long between 0 (inclusive) and bound (exclusive)

    • setSeed

      public void setSeed​(long seed)
      Sets the seed using a long, passing its argument to setState(long). That method just sets the public field state to its argument currently, but it may do more to ensure cycle length in the future.
      Overrides:
      setSeed in class Random
      Parameters:
      seed - the initial seed

    • swap

      protected static <T> void swap​(T[] arr, int pos1, int pos2)
      Mutates the array arr by switching the contents at pos1 and pos2.
      Parameters:
      arr - an array of T; must not be null
      pos1 - an index into arr; must be at least 0 and no greater than arr.length
      pos2 - an index into arr; must be at least 0 and no greater than arr.length

    • shuffle

      public <T> T[] shuffle​(T[] elements)
      Shuffle an array using the Fisher-Yates algorithm and returns a shuffled copy, freshly-allocated, without modifying elements.
      Wikipedia has more on this algorithm.
      Parameters:
      elements - an array of T; will not be modified
      Returns:
      a shuffled copy of elements

    • shuffleInPlace

      public <T> T[] shuffleInPlace​(T[] elements, int length)
      Shuffles an array in-place using the Fisher-Yates algorithm, affecting indices from 0 (inclusive) to length (exclusive). May be useful with libGDX Array instances, which can be shuffled with random.shuffleInPlace(arr.items, arr.size). If you don't want the array modified, use shuffle(Object[]).
      Wikipedia has more on this algorithm.
      Parameters:
      elements - an array of T; will be modified
      Returns:
      elements after shuffling it in-place

    • shuffleInPlace

      public <T> T[] shuffleInPlace​(T[] elements)
      Shuffles an array in-place using the Fisher-Yates algorithm. If you don't want the array modified, use shuffle(Object[]).
      Wikipedia has more on this algorithm.
      Parameters:
      elements - an array of T; will be modified
      Returns:
      elements after shuffling it in-place

    • shuffleInPlace

      public <T> List<T> shuffleInPlace​(List<T> elements)
      Shuffles a Collection of T items in-place using the Fisher-Yates algorithm. This only shuffles List data structures.
      Wikipedia has more on this algorithm.
      Type Parameters:
      T - can be any non-primitive type.
      Parameters:
      elements - a List of T; will be modified
      Returns:
      elements after shuffling it in-place

    • copy

      public BasicRandom64 copy()
      Description copied from interface: RandomnessSource
      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
      Returns:
      a copy of this RandomnessSource