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
18 package org.apache.commons.rng.core.source32;
19
20 import java.util.stream.Stream;
21 import org.apache.commons.rng.JumpableUniformRandomProvider;
22 import org.apache.commons.rng.LongJumpableUniformRandomProvider;
23 import org.apache.commons.rng.SplittableUniformRandomProvider;
24 import org.apache.commons.rng.UniformRandomProvider;
25 import org.apache.commons.rng.core.util.NumberFactory;
26 import org.apache.commons.rng.core.util.RandomStreams;
27
28 /**
29 * A 32-bit all purpose generator.
30 *
31 * <p>This is a member of the LXM family of generators: L=Linear congruential generator;
32 * X=Xor based generator; and M=Mix. This member uses a 32-bit LCG and 64-bit Xor-based
33 * generator. It is named as {@code "L32X64MixRandom"} in the {@code java.util.random}
34 * package introduced in JDK 17; the LXM family is described in further detail in:
35 *
36 * <blockquote>Steele and Vigna (2021) LXM: better splittable pseudorandom number generators
37 * (and almost as fast). Proceedings of the ACM on Programming Languages, Volume 5,
38 * Article 148, pp 1–31.</blockquote>
39 *
40 * <p>Memory footprint is 128 bits and the period is 2<sup>32</sup> (2<sup>64</sup> - 1).
41 *
42 * <p>This generator implements {@link LongJumpableUniformRandomProvider}.
43 * In addition instances created with a different additive parameter for the LCG are robust
44 * against accidental correlation in a multi-threaded setting. The additive parameters must be
45 * different in the most significant 31-bits.
46 *
47 * <p>This generator implements
48 * {@link org.apache.commons.rng.SplittableUniformRandomProvider SplittableUniformRandomProvider}.
49 * The stream of generators created using the {@code splits} methods support parallelisation
50 * and are robust against accidental correlation by using unique values for the additive parameter
51 * for each instance in the same stream. The primitive streaming methods support parallelisation
52 * but with no assurances of accidental correlation; each thread uses a new instance with a
53 * randomly initialised state.
54 *
55 * @see <a href="https://doi.org/10.1145/3485525">Steele & Vigna (2021) Proc. ACM Programming
56 * Languages 5, 1-31</a>
57 * @see <a href="https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/random/package-summary.html">
58 * JDK 17 java.util.random javadoc</a>
59 * @since 1.5
60 */
61 public final class L32X64Mix extends IntProvider implements LongJumpableUniformRandomProvider,
62 SplittableUniformRandomProvider {
63 // Implementation note:
64 // This does not extend AbstractXoRoShiRo64 as the XBG function is re-implemented
65 // inline to allow parallel pipelining. Inheritance would provide only the XBG state.
66
67 /** LCG multiplier. */
68 private static final int M = LXMSupport.M32;
69 /** Size of the state vector. */
70 private static final int SEED_SIZE = 4;
71
72 /** Per-instance LCG additive parameter (must be odd).
73 * Cannot be final to support RestorableUniformRandomProvider. */
74 private int la;
75 /** State of the LCG generator. */
76 private int ls;
77 /** State 0 of the XBG generator. */
78 private int x0;
79 /** State 1 of the XBG generator. */
80 private int x1;
81
82 /**
83 * Creates a new instance.
84 *
85 * @param seed Initial seed.
86 * If the length is larger than 4, only the first 4 elements will
87 * be used; if smaller, the remaining elements will be automatically
88 * set. A seed containing all zeros in the last two elements
89 * will create a non-functional XBG sub-generator and a low
90 * quality output with a period of 2<sup>32</sup>.
91 *
92 * <p>The 1st element is used to set the LCG increment; the least significant bit
93 * is set to odd to ensure a full period LCG. The 2nd element is used
94 * to set the LCG state.</p>
95 */
96 public L32X64Mix(int[] seed) {
97 setState(extendSeed(seed, SEED_SIZE));
98 }
99
100 /**
101 * Creates a new instance using a 4 element seed.
102 * A seed containing all zeros in the last two elements
103 * will create a non-functional XBG sub-generator and a low
104 * quality output with a period of 2<sup>32</sup>.
105 *
106 * <p>The 1st element is used to set the LCG increment; the least significant bit
107 * is set to odd to ensure a full period LCG. The 2nd element is used
108 * to set the LCG state.</p>
109 *
110 * @param seed0 Initial seed element 0.
111 * @param seed1 Initial seed element 1.
112 * @param seed2 Initial seed element 2.
113 * @param seed3 Initial seed element 3.
114 */
115 public L32X64Mix(int seed0, int seed1, int seed2, int seed3) {
116 // Additive parameter must be odd
117 la = seed0 | 1;
118 ls = seed1;
119 x0 = seed2;
120 x1 = seed3;
121 }
122
123 /**
124 * Creates a copy instance.
125 *
126 * @param source Source to copy.
127 */
128 private L32X64Mix(L32X64Mix source) {
129 super(source);
130 la = source.la;
131 ls = source.ls;
132 x0 = source.x0;
133 x1 = source.x1;
134 }
135
136 /**
137 * Copies the state into the generator state.
138 *
139 * @param state the new state
140 */
141 private void setState(int[] state) {
142 // Additive parameter must be odd
143 la = state[0] | 1;
144 ls = state[1];
145 x0 = state[2];
146 x1 = state[3];
147 }
148
149 /** {@inheritDoc} */
150 @Override
151 protected byte[] getStateInternal() {
152 return composeStateInternal(NumberFactory.makeByteArray(new int[] {la, ls, x0, x1}),
153 super.getStateInternal());
154 }
155
156 /** {@inheritDoc} */
157 @Override
158 protected void setStateInternal(byte[] s) {
159 final byte[][] c = splitStateInternal(s, SEED_SIZE * Integer.BYTES);
160 setState(NumberFactory.makeIntArray(c[0]));
161 super.setStateInternal(c[1]);
162 }
163
164 /** {@inheritDoc} */
165 @Override
166 public int next() {
167 // LXM generate.
168 // Old state is used for the output allowing parallel pipelining
169 // on processors that support multiple concurrent instructions.
170
171 final int s0 = x0;
172 final int s = ls;
173
174 // Mix
175 final int z = LXMSupport.lea32(s + s0);
176
177 // LCG update
178 ls = M * s + la;
179
180 // XBG update
181 int s1 = x1;
182
183 s1 ^= s0;
184 x0 = Integer.rotateLeft(s0, 26) ^ s1 ^ (s1 << 9); // a, b
185 x1 = Integer.rotateLeft(s1, 13); // c
186
187 return z;
188 }
189
190 /**
191 * Creates a copy of the UniformRandomProvider and then <em>retreats</em> the state of the
192 * current instance. The copy is returned.
193 *
194 * <p>The jump is performed by advancing the state of the LCG sub-generator by 1 cycle.
195 * The XBG state is unchanged. The jump size is the equivalent of moving the state
196 * <em>backwards</em> by (2<sup>64</sup> - 1) positions. It can provide up to 2<sup>32</sup>
197 * non-overlapping subsequences.</p>
198 */
199 @Override
200 public UniformRandomProvider jump() {
201 final UniformRandomProvider copy = new L32X64Mix(this);
202 // Advance the LCG 1 step
203 ls = M * ls + la;
204 resetCachedState();
205 return copy;
206 }
207
208 /**
209 * Creates a copy of the UniformRandomProvider and then <em>retreats</em> the state of the
210 * current instance. The copy is returned.
211 *
212 * <p>The jump is performed by advancing the state of the LCG sub-generator by
213 * 2<sup>16</sup> cycles. The XBG state is unchanged. The jump size is the equivalent
214 * of moving the state <em>backwards</em> by 2<sup>16</sup> (2<sup>64</sup> - 1)
215 * positions. It can provide up to 2<sup>16</sup> non-overlapping subsequences of
216 * length 2<sup>16</sup> (2<sup>64</sup> - 1); each subsequence can provide up to
217 * 2<sup>16</sup> non-overlapping subsequences of length (2<sup>64</sup> - 1) using
218 * the {@link #jump()} method.</p>
219 */
220 @Override
221 public JumpableUniformRandomProvider longJump() {
222 final JumpableUniformRandomProvider copy = new L32X64Mix(this);
223 // Advance the LCG 2^16 steps
224 ls = LXMSupport.M32P * ls + LXMSupport.C32P * la;
225 resetCachedState();
226 return copy;
227 }
228
229 /** {@inheritDoc} */
230 @Override
231 public SplittableUniformRandomProvider split(UniformRandomProvider source) {
232 // The upper half of the long seed is discarded so use nextInt
233 return create(source.nextInt(), source);
234 }
235
236 /** {@inheritDoc} */
237 @Override
238 public Stream<SplittableUniformRandomProvider> splits(long streamSize, SplittableUniformRandomProvider source) {
239 return RandomStreams.generateWithSeed(streamSize, source, L32X64Mix::create);
240 }
241
242 /**
243 * Create a new instance using the given {@code seed} and {@code source} of randomness
244 * to initialise the instance.
245 *
246 * @param seed Seed used to initialise the instance.
247 * @param source Source of randomness used to initialise the instance.
248 * @return A new instance.
249 */
250 private static SplittableUniformRandomProvider create(long seed, UniformRandomProvider source) {
251 // LCG state. The addition uses the input seed.
252 // The LCG addition parameter is set to odd so left-shift the seed.
253 final int s0 = (int) seed << 1;
254 final int s1 = source.nextInt();
255 // XBG state must not be all zero
256 int x0 = source.nextInt();
257 int x1 = source.nextInt();
258 if ((x0 | x1) == 0) {
259 // SplitMix style seed ensures at least one non-zero value
260 x0 = LXMSupport.lea32(s1);
261 x1 = LXMSupport.lea32(s1 + LXMSupport.GOLDEN_RATIO_32);
262 }
263 return new L32X64Mix(s0, s1, x0, x1);
264 }
265 }