Package squidpony.squidmath

Class LFSR

java.lang.Object
squidpony.squidmath.LFSR
All Implemented Interfaces:
Serializable, RandomnessSource, StatefulRandomness
public class LFSR
extends Object
implements StatefulRandomness, Serializable
A Linear Feedback Shift Register that may be used like a StatefulRandomness but is not truly random. This has a period of (2 to the 64) minus 1, and is based on Wikipedia's code for a Galois LFSR but uses data from http://web.archive.org/web/20161007061934/http://courses.cse.tamu.edu/csce680/walker/lfsr_table.pdf . It is important to note that an LFSR will produce each number from 1 until its maximum exactly once before repeating, so this may be useful as a way of generating test data in an unpredictable order.
Author:
Tommy Ettinger
See Also:
Serialized Form

  • Field Summary

    Fields 
    Modifier and Type Field Description
    long state  

  • Constructor Summary

    Constructors 
    Constructor Description
    LFSR()
    Creates a new generator seeded using Math.random.
    LFSR​(long seed)  
    LFSR​(CharSequence seed)  

  • Method Summary

    Modifier and Type Method Description
    LFSR 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)
    Gets the next number that an LFSR would produce using nextLong() if its state was state.
    static int determineBounded​(int state, int bound)
    Gets an int using determineInt(int) and bounds it to fit between 0 (inclusive) and bound (exclusive).
    static int determineBounded​(long state, int bound)
    Gets the next number that an LFSR would produce using nextInt(int) if its state was state and bound was passed to nextInt().
    static int determineByte​(byte state)
    Gets the next number from 1 to 255 that a different kind of LFSR would produce if its state was state.
    static int determineInt​(int state)
    Gets the next number that a different kind of 32-bit LFSR would produce if its state was state.
    static int determineIntSymmetrical​(int state)
    Gets the next int that a different kind of LFSR would produce if its state was state.
    static int determinePositiveInt​(int state)
    Gets the next positive int that a different kind of 31-bit LFSR would produce if its state was state.
    static long determinePositiveLong​(long state)
    Gets the next positive long that a different kind of 63-bit LFSR would produce if its state was state.
    boolean equals​(Object o)  
    long getState()
    Get the current internal state of the StatefulRandomness as a long.
    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.
    boolean nextBoolean()  
    void nextBytes​(byte[] bytes)  
    double nextDouble()  
    float nextFloat()  
    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 inner, int outer)
    Inclusive lower, exclusive upper.
    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 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 setState​(long seed)
    Sets the seed of this generator using one long, running that through LightRNG's algorithm twice to get the state.
    String toString()  

    Methods inherited from class java.lang.Object

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

  • Field Details

  • Constructor Details

  • Method Details

    • 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 LFSR 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()
      Can return any int, positive or negative, of any size permissible in a 32-bit signed integer.
      Returns:
      any int, all 32 bits are random

    • nextInt

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

    • nextInt

      public int nextInt​(int inner, int outer)
      Inclusive lower, exclusive upper.
      Parameters:
      inner - the inner bound, inclusive, can be positive or negative
      outer - the outer bound, exclusive, should be positive, should usually be greater than inner
      Returns:
      a random int that may be equal to inner and will otherwise be between inner and outer

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

    • nextFloat

      public float nextFloat()

    • nextBoolean

      public boolean nextBoolean()

    • nextBytes

      public void nextBytes​(byte[] bytes)

    • getState

      public long getState()
      Get the current internal state of the StatefulRandomness as a long.
      Specified by:
      getState in interface StatefulRandomness
      Returns:
      the current internal state of this object.

    • setState

      public void setState​(long seed)
      Sets the seed of this generator using one long, running that through LightRNG's algorithm twice to get the state.
      Specified by:
      setState in interface StatefulRandomness
      Parameters:
      seed - the number to use as the seed

    • 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

    • determine

      public static long determine​(long state)
      Gets the next number that an LFSR would produce using nextLong() if its state was state. Does not allow state to be 0. Strongly consider using the result of this and assigning it to state if you expect to call this again, such as with (state = LFSR.determine(state)), which will ensure the long-term properties of an LFSR hold up (such as having a period of ((2 to the 64) minus 1), or the guarantee that every number from 1 to ((2 to the 64) minus 1), inclusive on both, will be generated once per period).
      Parameters:
      state - any long other than 0
      Returns:
      the next long that a 64-bit LFSR would produce with the given state

    • determineByte

      public static int determineByte​(byte state)
      Gets the next number from 1 to 255 that a different kind of LFSR would produce if its state was state. Does not allow state to be 0. If given all byte values except 0 as arguments, will produce all ints 1-255. Strongly consider using the result of this and assigning it to state if you expect to call this again, such as with (state = LFSR.determineByte(state)), which will ensure the long-term properties of an LFSR hold up (such as having a period of 255, or the guarantee that every number from 1 to 255, inclusive on both, will be generated once per period).
      Parameters:
      state - any byte other than 0
      Returns:
      the next int between 1 and 255 that an 8-bit LFSR would produce with the given state

    • determineInt

      public static int determineInt​(int state)
      Gets the next number that a different kind of 32-bit LFSR would produce if its state was state. Does not allow state to be 0. If given all int values except 0 as arguments, will produce all ints except 0. Strongly consider using the result of this and assigning it to state if you expect to call this again, such as with (state = LFSR.determineInt(state)), which will ensure the long-term properties of an LFSR hold up (such as having a period of ((2 to the 32) minus 1), or the guarantee that every number from 1 to ((2 to the 32) minus 1), inclusive on both, will be generated once per period).
      Parameters:
      state - any long other than 0
      Returns:
      the next int that a 32-bit LFSR would produce with the given state

    • determinePositiveLong

      public static long determinePositiveLong​(long state)
      Gets the next positive long that a different kind of 63-bit LFSR would produce if its state was state. Does not allow state to be 0 or negative. If given all positive long values (not including 0) as arguments, will produce all longs greater than 0. Strongly consider using the result of this and assigning it to state if you expect to call this again, such as with (state = LFSR.determinePositiveLong(state)), which will ensure the long-term properties of an LFSR hold up (such as having a period of ((2 to the 63) minus 1), or the guarantee that every number from 1 to ((2 to the 63) minus 1), inclusive on both, will be generated once per period).
      Parameters:
      state - any positive long, not including 0
      Returns:
      the next int that a 63-bit LFSR would produce with the given state

    • determinePositiveInt

      public static int determinePositiveInt​(int state)
      Gets the next positive int that a different kind of 31-bit LFSR would produce if its state was state. Does not allow state to be 0 or negative. If given all positive int values (not including 0) as arguments, will produce all ints greater than 0. Strongly consider using the result of this and assigning it to state if you expect to call this again, such as with (state = LFSR.determinePositiveInt(state)), which will ensure the long-term properties of an LFSR hold up (such as having a period of ((2 to the 31) minus 1), or the guarantee that every number from 1 to ((2 to the 31) minus 1), inclusive on both, will be generated once per period).
      A potential benefit of using this particular LFSR type is that the period is a prime number, 2147483647; this can sometimes be relevant if you simultaneously get pseudo-random numbers from sources of randomness with different periods that are "relatively co-prime" (that is, they share no common factors other than 1). This case lengthens the total period of the combined generators significantly, generally multiplying the periods together to get the combined period, as opposed to other cases that may simply add them together.
      Parameters:
      state - any positive int, not including 0
      Returns:
      the next int that a 31-bit LFSR would produce with the given state

    • determineIntSymmetrical

      public static int determineIntSymmetrical​(int state)
      Gets the next int that a different kind of LFSR would produce if its state was state. Does not allow state to be Integer.MIN_VALUE, nor will this produce a result of Integer.MIN_VALUE (as long as Integer.MIN_VALUE was not the input). If given all int values except Integer.MIN_VALUE as arguments, will produce all ints in the range [-2147483647,2147483647], including 0 but not -2147483648 (the minimum int). Strongly consider using the result of this and assigning it to state if you expect to call this again, such as with (state = LFSR.determineIntSymmetrical(state)), which will ensure the long-term properties of an LFSR hold up (such as having a period of ((2 to the 32) minus 1), or the guarantee that every int except Integer.MIN_VALUE will be generated once per period).
      This is called Symmetrical because it produces the same amount of positive and negative numbers, instead of the normal generation of more negative ones (due to how ints are represented, the min value is always further from 0 than the max value for any signed integer type).
      Parameters:
      state - any int other than -2147483648 (0x80000000), which is Integer.MIN_VALUE; can produce 0
      Returns:
      the next int other than -2147483648 that an LFSR would produce with the given state

    • determineBounded

      public static int determineBounded​(long state, int bound)
      Gets the next number that an LFSR would produce using nextInt(int) if its state was state and bound was passed to nextInt(). Does not allow state to be 0, but bound can be negative, which causes this not to produce positive numbers. This method is very predictable and its use is not encouraged; prefer using determineBounded(int, int).
      Parameters:
      state - any long other than 0
      bound - the exclusive bound on the result as an int; does better if the bound is not too high (below 10000?)
      Returns:
      the next value that determine(long) would produce with the given state, but limited to bound; can return 0

    • determineBounded

      public static int determineBounded​(int state, int bound)
      Gets an int using determineInt(int) and bounds it to fit between 0 (inclusive) and bound (exclusive). Does not allow state to be 0, but bound can be negative, which causes this not to produce positive numbers.
      Parameters:
      state - any int other than 0
      bound - the exclusive bound on the result as an int; does better if the bound is not too high (below 10000?)
      Returns:
      the next int that determineInt(int) would produce with the given state, but limited to bound; can return 0