Package squidpony.squidmath

Class LongPeriodRNG

java.lang.Object
squidpony.squidmath.LongPeriodRNG
All Implemented Interfaces:
Serializable, RandomnessSource
public final class LongPeriodRNG
extends Object
implements RandomnessSource, Serializable
An RNG that has a drastically longer period than the other generators in SquidLib, other than IsaacRNG, without sacrificing speed or GWT support. If you don't already know what the period of an RNG is, this probably isn't needed for your purposes, or many purposes in games at all. It is primarily meant for applications that need to generate massive amounts of random numbers, more than pow(2, 64) (18,446,744,073,709,551,616), without repeating the sequence of generated numbers. An RNG's period refers to the number of numbers it generates given a single seed before the sequence repeats from the beginning. The period of this class is pow(2, 1024) minus 1 (179,769,313,486,231,590,772,930,519,078,902,473,361,797,697,894,230,657,273,430,081,157,732,675,805,500,963,132,708, 477,322,407,536,021,120,113,879,871,393,357,658,789,768,814,416,622,492,847,430,639,474,124,377,767,893,424,865,485, 276,302,219,601,246,094,119,453,082,952,085,005,768,838,150,682,342,462,881,473,913,110,540,827,237,163,350,510,684, 586,298,239,947,245,938,479,716,304,835,356,329,624,224,137,215). While that number is preposterously large, there's always some application that seems to need more; if you really need more than that, look into CMWC generators, which can have even larger state and also even larger periods. There isn't one of those in SquidLib currently, though there is a possibility of one being added in the future. There is a 64-bit MersenneTwister, which has an even larger period than this one, but it might not have optimal quality for some applications (notably, the game Dungeon Crawl Stone Soup used Mersenne Twister and found that some players in a competition could predict impending random events, despite the generator seeming bulletproof).
This class may be particularly useful in conjunction with the shuffle method of RNG; the period of an RNG determines how many possible "shuffles", a.k.a orderings or permutations, can be produced over all calls to a permuting method like shuffle. A LightRNG-backed RNG with a period of pow(2, 64) will only be able to produce all possible "shuffles" for lists or arrays of 20 items or less. If a LongPeriodRNG is given to the constructor of an RNG and a large enough state has been given to the LongPeriodRNG (the String or long[] constructors can allow this), then lists or arrays of up to 170 elements can have all possible orderings produced by shuffle(), though it will take near-impossibly-many calls. This class has 128 bytes of state plus more in overhead (compare to the 16-byte-with-overhead LightRNG), but due to its massive period and createMany() static method, you can create a large number of subsequences with rather long periods themselves from a single seed. This uses the xorshift-1024*phi algorithm, and has competitive speed.
This generator was updated to the "phi" variant of XorShift1024* instead of the "M_8" variant when the phi variant became recommended over the version this originally used. The multiplier, and thus the sequence of numbers this generates for a given seed, changed on October 19, 2017.
Created by Tommy Ettinger on 3/21/2016. Ported from CC0-licensed C code by Sebastiano Vigna, at http://xorshift.di.unimi.it/xorshift1024star.c
Author:
Tommy Ettinger
See Also:
Serialized Form

  • Field Summary

    Fields 
    Modifier and Type Field Description
    int choice  
    long[] state  

  • Constructor Summary

    Constructors 
    Constructor Description
    LongPeriodRNG()
    Builds a LongPeriodRNG and initializes this class' 1024 bits of state with a random seed passed into SplitMix64, the algorithm also used by LightRNG.
    LongPeriodRNG​(long seed)
    Builds a LongPeriodRNG and initializes this class' 1024 bits of state with many calls to a SplitMix64-based RNG using a variant on seed produced by running it through PCG-Random's output step (PermutedRNG here).
    LongPeriodRNG​(long[] seed)
    Builds a LongPeriodRNG and initializes this class' 1024 bits of state with the given seed as a long array, which may or may not have 16 elements (though it is less wasteful to run this with 16 longs since that is exactly 1024 bits).
    LongPeriodRNG​(CharSequence seed)
    Builds a LongPeriodRNG and initializes this class' 1024 bits of state with the given seed, using a different strategy depending on the seed.
    LongPeriodRNG​(LongPeriodRNG other)  

  • Method Summary

    Modifier and Type Method Description
    LongPeriodRNG 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 LongPeriodRNG[] createMany​(int count)
    Creates many LongPeriodRNG objects in an array, where each will generate a sequence of pow(2, 512) numbers that will not overlap with other sequences in the array.
    static LongPeriodRNG[] createMany​(int count, long seed)
    Creates many LongPeriodRNG objects in an array, where each will generate a sequence of pow(2, 512) numbers that will not overlap with other sequences in the array.
    static LongPeriodRNG[] createMany​(int count, long[] seed)
    Creates many LongPeriodRNG objects in an array, where each will generate a sequence of pow(2, 512) numbers that will not overlap with other sequences in the array.
    static LongPeriodRNG[] createMany​(int count, String seed)
    Creates many LongPeriodRNG objects in an array, where each will generate a sequence of pow(2, 512) numbers that will not overlap with other sequences in the array.
    boolean equals​(Object o)  
    int hashCode()  
    void jump()
    This is the jump function for the generator.
    int next​(int bits)
    Using this method, any algorithm that might use the built-in Java Random can interface with this randomness source.
    long nextLong()
    Can return any long, positive or negative, of any size permissible in a 64-bit signed integer.
    void reseed()  
    void reseed​(long seed)
    Reinitializes this class' 1024 bits of state with the given seed passed into SplitMix64, the algorithm also used by LightRNG.
    void reseed​(long[] seed)
    Reinitializes this class' 1024 bits of state with the given seed as a long array, which may or may not have 16 elements (though it is less wasteful to run this with 16 longs since that is exactly 1024 bits).
    void reseed​(CharSequence seed)
    Reinitializes this class' 1024 bits of state with the given seed, using a different strategy depending on the seed.
    String toString()  

    Methods inherited from class java.lang.Object

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

  • Field Details

  • Constructor Details

    • LongPeriodRNG

      public LongPeriodRNG()
      Builds a LongPeriodRNG and initializes this class' 1024 bits of state with a random seed passed into SplitMix64, the algorithm also used by LightRNG. A different algorithm is used in non-constructor code to generate random numbers, which is a recommended technique to generate seeds.

    • LongPeriodRNG

      public LongPeriodRNG​(long seed)
      Builds a LongPeriodRNG and initializes this class' 1024 bits of state with many calls to a SplitMix64-based RNG using a variant on seed produced by running it through PCG-Random's output step (PermutedRNG here).
      Parameters:
      seed - a 64-bit seed; can be any value.

    • LongPeriodRNG

      public LongPeriodRNG​(CharSequence seed)
      Builds a LongPeriodRNG and initializes this class' 1024 bits of state with the given seed, using a different strategy depending on the seed. If seed is null, this uses the same state as any other null seed. If seed is a String with length 15 or less, this generates a 64-bit hash of the seed and uses it in the same way the constructor that takes a long creates 1024 bits of state from a 64-bit seed. If seed is a String with length 16 or more, this splits the string up and generates 16 hashes from progressively smaller substrings of seed. The highest quality states will result from passing this a very long String (a StringBuilder would also be a good choice).
      Parameters:
      seed - a String (or other CharSequence) seed; can be any value, but produces the best results if it at least 16 characters long

    • LongPeriodRNG

      public LongPeriodRNG​(long[] seed)
      Builds a LongPeriodRNG and initializes this class' 1024 bits of state with the given seed as a long array, which may or may not have 16 elements (though it is less wasteful to run this with 16 longs since that is exactly 1024 bits). If seed is null, this produces the same state as the String constructor does when given a null seed. If seed has fewer than 16 elements, this repeats earlier elements once it runs out of unused longs. If seed has 16 or more elements, this exclusive-ors elements after the sixteenth with longs it has already placed into the state, causing all elements of the seed to have an effect on the state, and making the 16-element case copy all longs exactly.
      Parameters:
      seed - a long array seed; can have any number of elements, though 16 is ideal

    • LongPeriodRNG

      public LongPeriodRNG​(LongPeriodRNG other)

  • Method Details

    • reseed

      public void reseed()

    • reseed

      public void reseed​(long seed)
      Reinitializes this class' 1024 bits of state with the given seed passed into SplitMix64, the algorithm also used by LightRNG. A different algorithm is used in actual number generating code, which is a recommended technique to generate seeds.
      Parameters:
      seed - a 64-bit seed; can be any value.

    • reseed

      public void reseed​(CharSequence seed)
      Reinitializes this class' 1024 bits of state with the given seed, using a different strategy depending on the seed. If seed is null, this uses the same state as any other null seed. If seed is a String with length 15 or less, this generates a 64-bit hash of the seed and uses it in the same way the constructor that takes a long creates 1024 bits of state from a 64-bit seed. If seed is a String with length 16 or more, this splits the string up and generates 16 hashes from progressively smaller substrings of seed. The highest quality states will result from passing this a very long String (a StringBuilder would also be a good choice).
      Parameters:
      seed - a String (or other CharSequence) seed; can be any value, but produces the best results if it at least 16 characters long

    • reseed

      public void reseed​(long[] seed)
      Reinitializes this class' 1024 bits of state with the given seed as a long array, which may or may not have 16 elements (though it is less wasteful to run this with 16 longs since that is exactly 1024 bits). If seed is null, this produces the same state as the String constructor does when given a null seed. If seed has fewer than 16 elements, this repeats earlier elements once it runs out of unused longs. If seed has 16 or more elements, this exclusive-ors elements after the sixteenth with longs it has already placed into the state, causing all elements of the seed to have an effect on the state, and making the 16-element case copy all longs exactly.
      Parameters:
      seed - a long array seed; can have any number of elements, though 16 is ideal

    • next

      public 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 long nextLong()
      Can return any long, positive or negative, of any size permissible in a 64-bit signed integer.
      Written by Sebastiano Vigna, from http://xorshift.di.unimi.it/xorshift1024star.c
      Specified by:
      nextLong in interface RandomnessSource
      Returns:
      any long, all 64 bits are random

    • copy

      public LongPeriodRNG 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
      Returns:
      a copy of this RandomnessSource

    • jump

      public void jump()
      This is the jump function for the generator. It is equivalent to 2^512 calls to nextLong(); it can be used to generate 2^512 non-overlapping subsequences for parallel computations. Alters the state of this object.
      Written by Sebastiano Vigna, from http://xorshift.di.unimi.it/xorshift1024star.c , don't ask how it works.

    • createMany

      public static LongPeriodRNG[] createMany​(int count)
      Creates many LongPeriodRNG objects in an array, where each will generate a sequence of pow(2, 512) numbers that will not overlap with other sequences in the array. The number of items in the array is specified by count.
      Parameters:
      count - the number of LongPeriodRNG objects to generate in the array.
      Returns:
      an array of LongPeriodRNG where none of the RNGs will generate overlapping sequences.

    • createMany

      public static LongPeriodRNG[] createMany​(int count, long seed)
      Creates many LongPeriodRNG objects in an array, where each will generate a sequence of pow(2, 512) numbers that will not overlap with other sequences in the array. The number of items in the array is specified by count. A seed can be given that will affect all items in the array, but with each item using a different section of the massive period this class supports. Essentially, each LongPeriodRNG in the array will generate a different random sequence relative to any other element of the array, but the sequences are reproducible if the same seed is given to this method a different time (useful for testing).
      Parameters:
      count - the number of LongPeriodRNG objects to generate in the array.
      seed - the RNG seed that will determine the different sequences the returned LongPeriodRNG objects produce
      Returns:
      an array of LongPeriodRNG where none of the RNGs will generate overlapping sequences.

    • createMany

      public static LongPeriodRNG[] createMany​(int count, String seed)
      Creates many LongPeriodRNG objects in an array, where each will generate a sequence of pow(2, 512) numbers that will not overlap with other sequences in the array. The number of items in the array is specified by count. A seed can be given that will affect all items in the array, but with each item using a different section of the massive period this class supports. Essentially, each LongPeriodRNG in the array will generate a different random sequence relative to any other element of the array, but the sequences are reproducible if the same seed is given to this method a different time (useful for testing).
      Parameters:
      count - the number of LongPeriodRNG objects to generate in the array.
      seed - the RNG seed that will determine the different sequences the returned LongPeriodRNG objects produce
      Returns:
      an array of LongPeriodRNG where none of the RNGs will generate overlapping sequences.

    • createMany

      public static LongPeriodRNG[] createMany​(int count, long[] seed)
      Creates many LongPeriodRNG objects in an array, where each will generate a sequence of pow(2, 512) numbers that will not overlap with other sequences in the array. The number of items in the array is specified by count. A seed can be given that will affect all items in the array, but with each item using a different section of the massive period this class supports. Essentially, each LongPeriodRNG in the array will generate a different random sequence relative to any other element of the array, but the sequences are reproducible if the same seed is given to this method a different time (useful for testing).
      Parameters:
      count - the number of LongPeriodRNG objects to generate in the array.
      seed - the RNG seed that will determine the different sequences the returned LongPeriodRNG objects produce
      Returns:
      an array of LongPeriodRNG where none of the RNGs will generate overlapping sequences.

    • 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