Class LXMSupport
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:
-
Field Summary
FieldsModifier and TypeFieldDescription(package private) static final long
High half of the jump constant for an advance of the 128-bit LCG by 2^64.(package private) static final long
Jump constant precursor forc'
for an advance of the 64-bit LCG by 2^32.(package private) static final long
The fractional part of the golden ratio, phi, scaled to 64-bits and rounded to odd.private static final long
A mask to convert anint
to an unsigned integer stored as along
.(package private) static final long
Low half of 128-bit LCG multiplier.(package private) static final long
High half of the jump constantm'
for an advance of the 128-bit LCG by 2^64.(package private) static final long
64-bit LCG multiplier.(package private) static final long
Jump constantm'
for an advance of the 64-bit LCG by 2^32. -
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescription(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.
-
Field Details
-
M64
static final long M6464-bit LCG multiplier. Note: (M % 8) = 5.- See Also:
-
M64P
static final long M64PJump constantm'
for an advance of the 64-bit LCG by 2^32. Computed as:m' = m^(2^32) (mod 2^64)
.- See Also:
-
C64P
static final long C64PJump constant precursor forc'
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:
-
M128L
static final long M128LLow half of 128-bit LCG multiplier. The upper half is1L
.- See Also:
-
M128PH
static final long M128PHHigh half of the jump constantm'
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:
-
C128PH
static final long C128PHHigh 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:
-
GOLDEN_RATIO_64
static final long GOLDEN_RATIO_64The fractional part of the golden ratio, phi, scaled to 64-bits and rounded to odd.phi = (sqrt(5) - 1) / 2) * 2^64
- See Also:
-
INT_TO_UNSIGNED_BYTE_MASK
private static final long INT_TO_UNSIGNED_BYTE_MASKA mask to convert anint
to an unsigned integer stored as along
.- See Also:
-
-
Constructor Details
-
LXMSupport
private LXMSupport()No instances.
-
-
Method Details
-
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 valuevalue2
- 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 argumentright
- the right argument (assumed to have the lowest bit set to 1)- Returns:
- the carry (either 0 or 1)
-