Class LXMSupport

java.lang.Object

org.apache.commons.rng.core.source64.LXMSupport

final class LXMSupport
extends 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 final long	C128PH	High half of the jump constant for an advance of the 128-bit LCG by 2^64.
(package private) static final long	C64P	Jump constant precursor for c' for an advance of the 64-bit LCG by 2^32.
(package private) static final long	GOLDEN_RATIO_64	The fractional part of the golden ratio, phi, scaled to 64-bits and rounded to odd.
private static final long	INT_TO_UNSIGNED_BYTE_MASK	A mask to convert an int to an unsigned integer stored as a long.
(package private) static final long	M128L	Low half of 128-bit LCG multiplier.
(package private) static final long	M128PH	High half of the jump constant m' for an advance of the 128-bit LCG by 2^64.
(package private) static final long	M64	64-bit LCG multiplier.
(package private) static final 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

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 Object

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

Field Details

M64

static final long M64

64-bit LCG multiplier. Note: (M % 8) = 5.

See Also:

• Constant Field Values

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 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 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)