Class LXMSupport


  • final class LXMSupport
    extends java.lang.Object
    Utility support for the LXM family of generators. The LXM family is described in further detail in:
    Steele and Vigna (2021) LXM: better splittable pseudorandom number generators (and almost as fast). Proceedings of the ACM on Programming Languages, Volume 5, Article 148, pp 1–31.

    Contains methods to compute unsigned multiplication of 64-bit and 128-bit values to create 128-bit results for use in a 128-bit linear congruential generator (LCG). Constants are provided to advance the state of an LCG by a power of 2 in a single multiply operation to support jump operations.

    Since:
    1.5
    See Also:
    Steele & Vigna (2021) Proc. ACM Programming Languages 5, 1-31
    • Field Summary

      Fields 
      Modifier and Type Field Description
      (package private) static long C128PH
      High half of the jump constant for an advance of the 128-bit LCG by 2^64.
      (package private) static long C64P
      Jump constant precursor for c' for an advance of the 64-bit LCG by 2^32.
      (package private) static long GOLDEN_RATIO_64
      The fractional part of the golden ratio, phi, scaled to 64-bits and rounded to odd.
      private static long INT_TO_UNSIGNED_BYTE_MASK
      A mask to convert an int to an unsigned integer stored as a long.
      (package private) static long M128L
      Low half of 128-bit LCG multiplier.
      (package private) static long M128PH
      High half of the jump constant m' for an advance of the 128-bit LCG by 2^64.
      (package private) static long M64
      64-bit LCG multiplier.
      (package private) static long M64P
      Jump constant m' for an advance of the 64-bit LCG by 2^32.
    • Constructor Summary

      Constructors 
      Modifier Constructor Description
      private LXMSupport()
      No instances.
    • Method Summary

      All Methods Static Methods Concrete Methods 
      Modifier and Type Method Description
      (package private) static long lea64​(long x)
      Perform a 64-bit mixing function using Doug Lea's 64-bit mix constants and shifts.
      (package private) static long unsignedAddHigh​(long left, long right)
      Add the two values as if unsigned 64-bit longs to produce the high 64-bits of the 128-bit unsigned result.
      (package private) static long unsignedMultiplyHigh​(long value1, long value2)
      Multiply the two values as if unsigned 64-bit longs to produce the high 64-bits of the 128-bit unsigned result.
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Field Detail

      • M64P

        static final long M64P
        Jump constant m' for an advance of the 64-bit LCG by 2^32. Computed as: m' = m^(2^32) (mod 2^64).
        See Also:
        Constant Field Values
      • C64P

        static final long C64P
        Jump constant precursor for c' for an advance of the 64-bit LCG by 2^32. Computed as:
         product_{i=0}^{31} { M^(2^i) + 1 } (mod 2^64)
         

        The jump is computed for the LCG with an update step of s = m * s + c as:

         s = m' * s + c' * c
         
        See Also:
        Constant Field Values
      • M128L

        static final long M128L
        Low half of 128-bit LCG multiplier. The upper half is 1L.
        See Also:
        Constant Field Values
      • M128PH

        static final long M128PH
        High half of the jump constant m' for an advance of the 128-bit LCG by 2^64. The low half is 1. Computed as: m' = m^(2^64) (mod 2^128).
        See Also:
        Constant Field Values
      • C128PH

        static final long C128PH
        High half of the jump constant for an advance of the 128-bit LCG by 2^64. The low half is zero. Computed as:
         product_{i=0}^{63} { M^(2^i) + 1 } (mod 2^128)
         

        The jump is computed for the LCG with an update step of s = m * s + c as:

         s = m' * s + c' * c
         
        See Also:
        Constant Field Values
      • GOLDEN_RATIO_64

        static final long GOLDEN_RATIO_64
        The fractional part of the golden ratio, phi, scaled to 64-bits and rounded to odd.
         phi = (sqrt(5) - 1) / 2) * 2^64
         
        See Also:
        Golden ratio, Constant Field Values
      • INT_TO_UNSIGNED_BYTE_MASK

        private static final long INT_TO_UNSIGNED_BYTE_MASK
        A mask to convert an int to an unsigned integer stored as a long.
        See Also:
        Constant Field Values
    • Constructor Detail

      • LXMSupport

        private LXMSupport()
        No instances.
    • Method Detail

      • lea64

        static long lea64​(long x)
        Perform a 64-bit mixing function using Doug Lea's 64-bit mix constants and shifts.

        This is based on the original 64-bit mix function of Austin Appleby's MurmurHash3 modified to use a single mix constant and 32-bit shifts, which may have a performance advantage on some processors. The code is provided in Steele and Vigna's paper.

        Parameters:
        x - the input value
        Returns:
        the output value
      • unsignedMultiplyHigh

        static long unsignedMultiplyHigh​(long value1,
                                         long value2)
        Multiply the two values as if unsigned 64-bit longs to produce the high 64-bits of the 128-bit unsigned result.

        This method computes the equivalent of:

        
         Math.multiplyHigh(a, b) + ((a >> 63) & b) + ((b >> 63) & a)
         

        Note: The method Math.multiplyHigh was added in JDK 9 and should be used as above when the source code targets Java 11 to exploit the intrinsic method.

        Note: The method Math.unsignedMultiplyHigh was added in JDK 18 and should be used when the source code target allows.

        Parameters:
        value1 - the first value
        value2 - the second value
        Returns:
        the high 64-bits of the 128-bit result
      • unsignedAddHigh

        static long unsignedAddHigh​(long left,
                                    long right)
        Add the two values as if unsigned 64-bit longs to produce the high 64-bits of the 128-bit unsigned result.

        Warning

        This method is computing a carry bit for a 128-bit linear congruential generator (LCG). The method is not applicable to all arguments. Some computations can be dropped if the right argument is assumed to be the LCG addition, which should be odd to ensure a full period LCG.

        Parameters:
        left - the left argument
        right - the right argument (assumed to have the lowest bit set to 1)
        Returns:
        the carry (either 0 or 1)