Package io.github.olyutorskii.aletojio.rng.fibo

Class LfShiftReg

java.lang.Object
io.github.olyutorskii.aletojio.rng.fibo.LfShiftReg
All Implemented Interfaces:
RndInt32
public class LfShiftReg extends Object implements RndInt32
Fibonacci Linear-feedback shift register (LFSR) Pseudo Random Generator.

A 32-bit length shift register is provided. Any number of taps can be specified.

The shift operation is performed 32 times to obtain a 32-bit random integer from MSB to LSB.

For LFSR to have a period of maximum length, at least the conditions "number of taps is even" and "Set of taps is setwise co-prime" must be satisfied. (but not sufficient)

If polynomial: [x**(tapN) + x**(tapN-1) + ... + x**(tap1) + 1] is primitive over GF(2), LFSR has maximum long period.

See Also:

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    static final int
    DEF_SEED
    Default seed value.

  • Constructor Summary

    Constructors
    Constructor
    Description
    LfShiftReg()
    Constructor.
    LfShiftReg(int... taps)
    Constructor.

  • Method Summary

    Modifier and Type
    Method
    Description
    int
    nextInt32()
    Return next random number as 32bit int with random sign-bit.
    void
    setSeed(int newSeed)
    Set seed.
    protected static int
    taps2Mask(int... taps)
    Convert from LFSR-taps notation to bitMask.
    String
    toString()
    static int
    xorBitSeq(int iVal)
    XOR whole bit sequence.

    Methods inherited from class java.lang.Object

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

  • Field Details

  • Constructor Details

    • LfShiftReg

      public LfShiftReg(int... taps) throws NullPointerException, IllegalArgumentException
      Constructor.

      Tap position numbers starts from 1 to 32. Value (1) points LSB of LFSR register. Value (32) points MSB of LFSR register.

      For LFSR to have a period of maximum length, at least the conditions "number of taps is even" and "Set of taps is setwise co-prime" must be satisfied. (but not sufficient)

      If polynomial: [x**(tapN) + x**(tapN-1) + ... + x**(tap1) + 1] is primitive over GF(2), LFSR has maximum long period.

      Taps example : (32, 31, 30, 10), (32, 31, 29, 1), (32, 25, 17, 7), etc.

      Parameters:
      taps - taps in register
      Throws:
      NullPointerException - taps is null.
      IllegalArgumentException - illegal tap position
      See Also:

    • LfShiftReg

      public LfShiftReg()
      Constructor.

      Default taps are { 32, 31, 30, 10 }

  • Method Details

    • taps2Mask

      protected static int taps2Mask(int... taps) throws IllegalArgumentException, NullPointerException
      Convert from LFSR-taps notation to bitMask.

      Tap position numbers starts from 1 to 32. Value (1) points LSB of LFSR register. Value (32) points MSB of LFSR register.

      Parameters:
      taps - Tap numbers array. Order is ignored. Duplications are ignored.
      Returns:
      Bit mask in which tapped bits are set.
      Throws:
      IllegalArgumentException - illegal tap position
      NullPointerException - taps is null.

    • xorBitSeq

      public static int xorBitSeq(int iVal)
      XOR whole bit sequence.

      result = b0 xor b1 xor ... xor b31

      Equivalent to [ Integer.bitCount(i) & 1 ] or ODD Parity.

      Yes, this is part of linear map function in boolean algebra.

      Parameters:
      iVal - bit pattern
      Returns:
      XOR result (1 or 0)

    • nextInt32

      public int nextInt32()
      Return next random number as 32bit int with random sign-bit.

      The 32bits obtained by repeating the register-shift 32times are returned, packed sequentially starting from MSB.

      Specified by:
      nextInt32 in interface RndInt32
      Returns:
      random number

    • setSeed

      public void setSeed(int newSeed) throws IllegalArgumentException
      Set seed.

      Seed value must not be 0.

      It will take some time before the extreme bias in seed value pop-counts is corrected.

      Parameters:
      newSeed - seed value
      Throws:
      IllegalArgumentException - Seed must be non-zero

    • toString

      public String toString()
      Overrides:
      toString in class Object
      Returns: