1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17 package org.apache.commons.rng.core.source32;
18
19 /**
20 * Utility support for the LXM family of generators. The LXM family is described
21 * in further detail in:
22 *
23 * <blockquote>Steele and Vigna (2021) LXM: better splittable pseudorandom number generators
24 * (and almost as fast). Proceedings of the ACM on Programming Languages, Volume 5,
25 * Article 148, pp 1–31.</blockquote>
26 *
27 * <p>Constants are provided to advance the state of an LCG by a power of 2 in a single
28 * multiply operation to support jump operations.
29 *
30 * @see <a href="https://doi.org/10.1145/3485525">Steele & Vigna (2021) Proc. ACM Programming
31 * Languages 5, 1-31</a>
32 * @since 1.5
33 */
34 final class LXMSupport {
35 /** 32-bit LCG multiplier. Note: (M % 8) = 5. */
36 static final int M32 = 0xadb4a92d;
37 /** Jump constant {@code m'} for an advance of the 32-bit LCG by 2^16.
38 * Computed as: {@code m' = m^(2^16) (mod 2^32)}. */
39 static final int M32P = 0x65640001;
40 /** Jump constant precursor for {@code c'} for an advance of the 32-bit LCG by 2^16.
41 * Computed as:
42 * <pre>
43 * product_{i=0}^{15} { M^(2^i) + 1 } (mod 2^32)
44 * </pre>
45 * <p>The jump is computed for the LCG with an update step of {@code s = m * s + c} as:
46 * <pre>
47 * s = m' * s + c' * c
48 * </pre>
49 */
50 static final int C32P = 0x046b0000;
51 /**
52 * The fractional part of the golden ratio, phi, scaled to 32-bits and rounded to odd.
53 * <pre>
54 * phi = (sqrt(5) - 1) / 2) * 2^32
55 * </pre>
56 * @see <a href="https://en.wikipedia.org/wiki/Golden_ratio">Golden ratio</a>
57 */
58 static final int GOLDEN_RATIO_32 = 0x9e3779b9;
59
60 /** No instances. */
61 private LXMSupport() {}
62
63 /**
64 * Perform a 32-bit mixing function using Doug Lea's 32-bit mix constants and shifts.
65 *
66 * <p>This is based on the original 32-bit mix function of Austin Appleby's
67 * MurmurHash3 modified to use a single mix constant and 16-bit shifts, which may have
68 * a performance advantage on some processors.
69 *
70 * <p>The code was kindly provided by Guy Steele as a printing constraint led to
71 * its omission from Steele and Vigna's paper.
72 *
73 * <p>Note from Guy Steele:
74 * <blockquote>
75 * The constant 0xd36d884b was chosen by Doug Lea by taking the (two’s-complement)
76 * negation of the decimal constant 747796405, which appears in Table 5 of L’Ecuyer’s
77 * classic paper “Tables of Linear Congruential Generators of Different Sizes and Good
78 * Lattice Structure” (January 1999); the constant in lea64 was chosen in a similar manner.
79 * These choices were based on his engineering intuition and then validated by testing.
80 * </blockquote>
81 *
82 * @param x the input value
83 * @return the output value
84 */
85 static int lea32(int x) {
86 x = (x ^ (x >>> 16)) * 0xd36d884b;
87 x = (x ^ (x >>> 16)) * 0xd36d884b;
88 return x ^ (x >>> 16);
89 }
90 }