Package it.unimi.dsi.test

Class XorShift

  • public class XorShift
extends java.lang.Object

    • Nested Class Summary

      Nested Classes 
      Modifier and Type Class Description
      static class  XorShift.Compute  

    • Field Summary

      Fields 
      Modifier and Type Field Description
      static int BITS
      The number of bits of state of the generator.
      static java.math.BigInteger[] cofactor
      An array of cofactors.
      static java.math.BigInteger[] factor
      Factors of the Fermat “primes” up to the eleventh (22048 + 1).
      static long[][] left
      64x64 bit matrices of the form I + La.
      static int numCofactors
      The actual number of valid entries in cofactor.
      static long[][] right
      64x64 bit matrices of the form I + Ra.
      static java.math.BigInteger twoToBitsMinus1
      The period of the generator (2BITS − 1).

    • Method Summary

      All Methods Static Methods Concrete Methods 
      Modifier and Type Method Description
      static long[][] identity()
      Returns the identity matrix in compact representation.
      static boolean isFull​(long[][] m)
      Checks whether a specified matrix in compact representation has full period.
      static boolean isIdentity​(long[][] m)
      Checks whether a specified matrix in compact representation is the identity.
      static void main​(java.lang.String[] arg)  
      static long[][] makeABCMatrix​(int a, int b, int c, int bits)
      Creates a matrix in compact form representing a xorshift generator as suggested by Marsaglia in “Xorshift RNGs”, Journal of Statistical Software, 8:1−6, 2003.
      static long[][] mPow​(long[][][] q, java.math.BigInteger e)
      Computes the power of a matrix to a given exponent, given the quadratures of the matrix.
      static long[][] multiply​(long[][] x, long[][] y)
      Multiplies two matrices in compact representation.
      static long[] multiply​(long[] x, long[] y)
      Multiplies two 64x64 bit matrices represented as arrays of longs.
      static long[][] newMatrix​(int bits)
      Creates a bit matrix in compact representation: only the first and last 64 rows, and only the first 64 columns of the remaining rows are actually represented.
      static long[][][] quad​(long[][] x)
      Computes the quadratures of a matrix in compact represention.
      static long word​(long[][] matrix, int r, int cw, int bits)
      Returns a specified word from a matrix in compact representation.

      • Methods inherited from class java.lang.Object

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

    • Field Detail

      • BITS

        public static final int BITS
        The number of bits of state of the generator.
        See Also:
        Constant Field Values

      • twoToBitsMinus1

        public static final java.math.BigInteger twoToBitsMinus1
        The period of the generator (2BITS − 1).

      • factor

        public static final java.math.BigInteger[] factor
        Factors of the Fermat “primes” up to the eleventh (22048 + 1).

      • cofactor

        public static final java.math.BigInteger[] cofactor
        An array of cofactors. Entry 0 ≤ i < numCofactors contains twoToBitsMinus1 divided by factor[i]. Note that some entries can be null if BITS is less then 4096.

      • numCofactors

        public static final int numCofactors
        The actual number of valid entries in cofactor.

      • right

        public static long[][] right
        64x64 bit matrices of the form I + Ra.

      • left

        public static long[][] left
        64x64 bit matrices of the form I + La.

    • Method Detail

      • newMatrix

        public static long[][] newMatrix​(int bits)
        Creates a bit matrix in compact representation: only the first and last 64 rows, and only the first 64 columns of the remaining rows are actually represented. The remaining entries are returned by word(long[][], int, int, int) by extending the explicit values in a Toeplitz-like fashion. Each row is represented by an array of longs, each representing 64 bits. Bit in column i can be retrieved as row[i / 64] & 1L << i.
        Parameters:
        bits - the number of bits in a row.
        Returns:
        a new matrix as described above.

      • word

        public static long word​(long[][] matrix,
                        int r,
                        int cw,
                        int bits)
        Returns a specified word from a matrix in compact representation.
        Parameters:
        matrix - a matrix in compact form.
        r - the row, starting from 0.
        cw - the column index of a word, starting from 0.
        bits - the number of bits in a row.
        Returns:
        the specified word.
        See Also:
        newMatrix(int)

      • multiply

        public static long[] multiply​(long[] x,
                              long[] y)
        Multiplies two 64x64 bit matrices represented as arrays of longs.
        Parameters:
        x - a 64x64 bit matrix.
        y - a 64x64 bit matrix.
        Returns:
        the product of x and y.

      • multiply

        public static long[][] multiply​(long[][] x,
                                long[][] y)
        Multiplies two matrices in compact representation.
        Parameters:
        x - a matrix in compact representation.
        y - a matrix in compact representation.
        Returns:
        the product of x and y in compact representation.
        See Also:
        newMatrix(int)

      • quad

        public static long[][][] quad​(long[][] x)
        Computes the quadratures of a matrix in compact represention.
        Parameters:
        x - a matrix in compact representation.
        Returns:
        an array of matrices in compact representation; the i-th entry of the matrix is x2i (0 ≤ i ≤ BITS).
        See Also:
        newMatrix(int)

      • identity

        public static long[][] identity()
        Returns the identity matrix in compact representation.
        Returns:
        a compact representation of the identity.
        See Also:
        newMatrix(int)

      • isIdentity

        public static boolean isIdentity​(long[][] m)
        Checks whether a specified matrix in compact representation is the identity.
        Returns:
        true if m is the identity matrix.
        See Also:
        newMatrix(int)

      • mPow

        public static long[][] mPow​(long[][][] q,
                            java.math.BigInteger e)
        Computes the power of a matrix to a given exponent, given the quadratures of the matrix.
        Parameters:
        q - the quadratures of some matrix as returned by quad(long[][]).
        e - an exponent smaller than or equal to 2BITS.
        Returns:
        the matrix whose array of quadratures is q raised to exponent e.
        See Also:
        newMatrix(int)

      • isFull

        public static boolean isFull​(long[][] m)
        Checks whether a specified matrix in compact representation has full period.
        Parameters:
        m - a matrix in compact representation.
        Returns:
        true of m has full period (i.e., 2BITS − 1).
        See Also:
        newMatrix(int)

      • makeABCMatrix

        public static long[][] makeABCMatrix​(int a,
                                     int b,
                                     int c,
                                     int bits)
        Creates a matrix in compact form representing a xorshift generator as suggested by Marsaglia in “Xorshift RNGs”, Journal of Statistical Software, 8:1−6, 2003.
        Parameters:
        a - the first shift parameter.
        b - the second shift parameter.
        c - the third shift parameter.
        bits - the number of bits in a row.
        Returns:
        a matrix representing a xorshift generator with specified parameters and number of bits.
        See Also:
        newMatrix(int)

      • main

        public static void main​(java.lang.String[] arg)