|
1 *************** |
|
2 *** 28,34 **** |
|
3 import java.math.BigInteger; |
|
4 import java.util.concurrent.atomic.AtomicLong; |
|
5 import java.util.random.RandomGenerator.SplittableGenerator; |
|
6 - import java.util.random.RandomSupport.AbstractSplittableGenerator; |
|
7 |
|
8 |
|
9 /** |
|
10 --- 28,34 ---- |
|
11 import java.math.BigInteger; |
|
12 import java.util.concurrent.atomic.AtomicLong; |
|
13 import java.util.random.RandomGenerator.SplittableGenerator; |
|
14 + import java.util.random.RandomSupport.AbstractSplittableWithBrineGenerator; |
|
15 |
|
16 |
|
17 /** |
|
18 *************** |
|
19 *** 55,63 **** |
|
20 * {@link L128X256MixRandom} is a specific member of the LXM family of algorithms |
|
21 * for pseudorandom number generators. Every LXM generator consists of two |
|
22 * subgenerators; one is an LCG (Linear Congruential Generator) and the other is |
|
23 - * an Xorshift generator. Each output of an LXM generator is the sum of one |
|
24 - * output from each subgenerator, possibly processed by a final mixing function |
|
25 - * (and {@link L128X256MixRandom} does use a mixing function). |
|
26 * <p> |
|
27 * The LCG subgenerator for {@link L128X256MixRandom} has an update step of the |
|
28 * form {@code s = m * s + a}, where {@code s}, {@code m}, and {@code a} are all |
|
29 --- 55,64 ---- |
|
30 * {@link L128X256MixRandom} is a specific member of the LXM family of algorithms |
|
31 * for pseudorandom number generators. Every LXM generator consists of two |
|
32 * subgenerators; one is an LCG (Linear Congruential Generator) and the other is |
|
33 + * an Xorshift generator. Each output of an LXM generator is the result of |
|
34 + * combining state from the LCG with state from the Xorshift generator by |
|
35 + * using a Mixing function (and then the state of the LCG and the state of the |
|
36 + * Xorshift generator are advanced). |
|
37 * <p> |
|
38 * The LCG subgenerator for {@link L128X256MixRandom} has an update step of the |
|
39 * form {@code s = m * s + a}, where {@code s}, {@code m}, and {@code a} are all |
|
40 *************** |
|
41 *** 74,80 **** |
|
42 * and {@code x3}, which can take on any values provided that they are not all zero. |
|
43 * The period of this subgenerator is 2<sup>256</sup>-1. |
|
44 * <p> |
|
45 - * The mixing function for {@link L128X256MixRandom} is the 64-bit MurmurHash3 finalizer. |
|
46 * <p> |
|
47 * Because the periods 2<sup>128</sup> and 2<sup>256</sup>-1 of the two subgenerators |
|
48 * are relatively prime, the <em>period</em> of any single {@link L128X256MixRandom} object |
|
49 --- 75,82 ---- |
|
50 * and {@code x3}, which can take on any values provided that they are not all zero. |
|
51 * The period of this subgenerator is 2<sup>256</sup>-1. |
|
52 * <p> |
|
53 + * The mixing function for {@link L128X256MixRandom} is {@link RandomSupport.mixLea64} |
|
54 + * applied to the argument {@code (sh + x0)}, where {@code sh} is the high half of {@code s}. |
|
55 * <p> |
|
56 * Because the periods 2<sup>128</sup> and 2<sup>256</sup>-1 of the two subgenerators |
|
57 * are relatively prime, the <em>period</em> of any single {@link L128X256MixRandom} object |
|
58 *************** |
|
59 *** 86,119 **** |
|
60 * <p> |
|
61 * The 64-bit values produced by the {@code nextLong()} method are exactly equidistributed. |
|
62 * For any specific instance of {@link L128X256MixRandom}, over the course of its cycle each |
|
63 - * of the 2<sup>64</sup> possible {@code long} values will be produced 2<sup>256</sup>-1 times. |
|
64 - * The values produced by the {@code nextInt()}, {@code nextFloat()}, and {@code nextDouble()} |
|
65 - * methods are likewise exactly equidistributed. |
|
66 - * <p> |
|
67 - * In fact, the 64-bit values produced by the {@code nextLong()} method are exactly |
|
68 - * 2-equidistributed. For any specific instance of {@link L128X256MixRandom}, consider |
|
69 - * the (overlapping) length-2 subsequences of the cycle of 64-bit values produced by |
|
70 - * {@code nextLong()} (assuming no other methods are called that would affect the state). |
|
71 - * There are 2<sup>128</sup>(2<sup>256</sup>-1) such subsequences, and each subsequence, |
|
72 - * which consists of 2 64-bit values, can have one of 2<sup>128</sup> values, and each |
|
73 - * such value occurs 2<sup>256</sup>-1 times. The values produced by the {@code nextInt()}, |
|
74 - * {@code nextFloat()}, and {@code nextDouble()} methods are likewise exactly 2-equidistributed. |
|
75 * <p> |
|
76 - * Moreover, the 64-bit values produced by the {@code nextLong()} method are 4-equidistributed. |
|
77 - * To be precise: for any specific instance of {@link L128X256MixRandom}, consider |
|
78 - * the (overlapping) length-4 subsequences of the cycle of 64-bit values produced by |
|
79 - * {@code nextLong()} (assuming no other methods are called that would affect the state). |
|
80 - * There are <sup>128</sup>(2<sup>256</sup>-1) such subsequences, and each subsequence, |
|
81 - * which consists of 4 64-bit values, can have one of 2<sup>256</sup> values. Of those |
|
82 - * 2<sup>256</sup> subsequence values, nearly all of them (2<sup>256</sup>-2<sup>128</sup>) |
|
83 - * occur 2<sup>128</sup> times over the course of the entire cycle, and the other |
|
84 - * 2<sup>128</sup> subsequence values occur only 2<sup>128</sup>-1 times. So the ratio |
|
85 - * of the probability of getting one of the less common subsequence values and the |
|
86 - * probability of getting one of the more common subsequence values is 1-2<sup>-128</sup>. |
|
87 - * (Note that the set of 2<sup>128</sup> less-common subsequence values will differ from |
|
88 - * one instance of {@link L128X256MixRandom} to another, as a function of the additive |
|
89 - * parameter of the LCG.) The values produced by the {@code nextInt()}, {@code nextFloat()}, |
|
90 - * and {@code nextDouble()} methods are likewise 4-equidistributed. |
|
91 * <p> |
|
92 * Method {@link #split} constructs and returns a new {@link L128X256MixRandom} |
|
93 * instance that shares no mutable state with the current instance. However, with |
|
94 --- 88,103 ---- |
|
95 * <p> |
|
96 * The 64-bit values produced by the {@code nextLong()} method are exactly equidistributed. |
|
97 * For any specific instance of {@link L128X256MixRandom}, over the course of its cycle each |
|
98 + * of the 2<sup>64</sup> possible {@code long} values will be produced |
|
99 + * 2<sup>64</sup>(2<sup>256</sup>-1) times. The values produced by the {@code nextInt()}, |
|
100 + * {@code nextFloat()}, and {@code nextDouble()} methods are likewise exactly equidistributed. |
|
101 * <p> |
|
102 + * Moreover, 64-bit values produced by the {@code nextLong()} method are conjectured to be |
|
103 + * "very nearly" 4-equidistributed: all possible quadruples of 64-bit values are generated, |
|
104 + * and some pairs occur more often than others, but only very slightly more often. |
|
105 + * However, this conjecture has not yet been proven mathematically. |
|
106 + * If this conjecture is true, then the values produced by the {@code nextInt()}, {@code nextFloat()}, |
|
107 + * and {@code nextDouble()} methods are likewise approximately 4-equidistributed. |
|
108 * <p> |
|
109 * Method {@link #split} constructs and returns a new {@link L128X256MixRandom} |
|
110 * instance that shares no mutable state with the current instance. However, with |
|
111 *************** |
|
112 *** 146,152 **** |
|
113 * |
|
114 * @since 14 |
|
115 */ |
|
116 - public final class L128X256MixRandom extends AbstractSplittableGenerator { |
|
117 |
|
118 /* |
|
119 * Implementation Overview. |
|
120 --- 130,136 ---- |
|
121 * |
|
122 * @since 14 |
|
123 */ |
|
124 + public final class L128X256MixRandom extends AbstractSplittableWithBrineGenerator { |
|
125 |
|
126 /* |
|
127 * Implementation Overview. |
|
128 *************** |
|
129 *** 193,220 **** |
|
130 BigInteger.ONE.shiftLeft(256).subtract(BigInteger.ONE).shiftLeft(128); |
|
131 |
|
132 /* |
|
133 - * The multiplier used in the LCG portion of the algorithm is 2**64 + m; |
|
134 - * where m is taken from |
|
135 - * Pierre L'Ecuyer, Tables of linear congruential generators of |
|
136 - * different sizes and good lattice structure, <em>Mathematics of |
|
137 - * Computation</em> 68, 225 (January 1999), pages 249-260, |
|
138 - * Table 4 (first multiplier for size 2<sup>64</sup>). |
|
139 - * |
|
140 - * This is almost certainly not the best possible 128-bit multiplier |
|
141 - * for an LCG, but it is sufficient for our purposes here; because |
|
142 - * is is larger than 2**64, the 64-bit values produced by nextLong() |
|
143 - * are exactly 2-equidistributed, and the fact that it is of the |
|
144 - * form (2**64 + m) simplifies the code, given that we have only |
|
145 - * 64-bit arithmetic to work with. |
|
146 */ |
|
147 |
|
148 - private static final long M = 2862933555777941757L; |
|
149 |
|
150 /* ---------------- instance fields ---------------- */ |
|
151 |
|
152 /** |
|
153 * The parameter that is used as an additive constant for the LCG. |
|
154 - * Must be odd. |
|
155 */ |
|
156 private final long ah, al; |
|
157 |
|
158 --- 177,196 ---- |
|
159 BigInteger.ONE.shiftLeft(256).subtract(BigInteger.ONE).shiftLeft(128); |
|
160 |
|
161 /* |
|
162 + * Low half of multiplier used in the LCG portion of the algorithm; |
|
163 + * the overall multiplier is (2**64 + ML). |
|
164 + * Chosen based on research by Sebastiano Vigna and Guy Steele (2019). |
|
165 + * The spectral scores for dimensions 2 through 8 for the multiplier 0x1d605bbb58c8abbfdLL |
|
166 + * are [0.991889, 0.907938, 0.830964, 0.837980, 0.780378, 0.797464, 0.761493]. |
|
167 */ |
|
168 |
|
169 + private static final long ML = 0xd605bbb58c8abbfdL; |
|
170 |
|
171 /* ---------------- instance fields ---------------- */ |
|
172 |
|
173 /** |
|
174 * The parameter that is used as an additive constant for the LCG. |
|
175 + * Must be odd (therefore al must be odd). |
|
176 */ |
|
177 private final long ah, al; |
|
178 |
|
179 *************** |
|
180 *** 252,262 **** |
|
181 this.x3 = x3; |
|
182 // If x0, x1, x2, and x3 are all zero, we must choose nonzero values. |
|
183 if ((x0 | x1 | x2 | x3) == 0) { |
|
184 // At least three of the four values generated here will be nonzero. |
|
185 - this.x0 = RandomSupport.mixStafford13(sh += RandomSupport.GOLDEN_RATIO_64); |
|
186 - this.x1 = RandomSupport.mixStafford13(sh += RandomSupport.GOLDEN_RATIO_64); |
|
187 - this.x2 = RandomSupport.mixStafford13(sh += RandomSupport.GOLDEN_RATIO_64); |
|
188 - this.x3 = RandomSupport.mixStafford13(sh + RandomSupport.GOLDEN_RATIO_64); |
|
189 } |
|
190 } |
|
191 |
|
192 --- 228,239 ---- |
|
193 this.x3 = x3; |
|
194 // If x0, x1, x2, and x3 are all zero, we must choose nonzero values. |
|
195 if ((x0 | x1 | x2 | x3) == 0) { |
|
196 + long v = sh; |
|
197 // At least three of the four values generated here will be nonzero. |
|
198 + this.x0 = RandomSupport.mixStafford13(v += RandomSupport.GOLDEN_RATIO_64); |
|
199 + this.x1 = RandomSupport.mixStafford13(v += RandomSupport.GOLDEN_RATIO_64); |
|
200 + this.x2 = RandomSupport.mixStafford13(v += RandomSupport.GOLDEN_RATIO_64); |
|
201 + this.x3 = RandomSupport.mixStafford13(v + RandomSupport.GOLDEN_RATIO_64); |
|
202 } |
|
203 } |
|
204 |
|
205 *************** |
|
206 *** 277,283 **** |
|
207 // The seed is hashed by mixStafford13 to produce the initial `x0`, |
|
208 // which will then be used to produce the first generated value. |
|
209 // The other x values are filled in as if by a SplitMix PRNG with |
|
210 - // GOLDEN_RATIO_64 as the gamma value and Stafford13 as the mixer. |
|
211 this(RandomSupport.mixMurmur64(seed ^= RandomSupport.SILVER_RATIO_64), |
|
212 RandomSupport.mixMurmur64(seed += RandomSupport.GOLDEN_RATIO_64), |
|
213 0, |
|
214 --- 254,260 ---- |
|
215 // The seed is hashed by mixStafford13 to produce the initial `x0`, |
|
216 // which will then be used to produce the first generated value. |
|
217 // The other x values are filled in as if by a SplitMix PRNG with |
|
218 + // GOLDEN_RATIO_64 as the gamma value and mixStafford13 as the mixer. |
|
219 this(RandomSupport.mixMurmur64(seed ^= RandomSupport.SILVER_RATIO_64), |
|
220 RandomSupport.mixMurmur64(seed += RandomSupport.GOLDEN_RATIO_64), |
|
221 0, |
|
222 *************** |
|
223 *** 323,351 **** |
|
224 } |
|
225 |
|
226 /* ---------------- public methods ---------------- */ |
|
227 - |
|
228 /** |
|
229 - * Constructs and returns a new instance of {@link L128X256MixRandom} |
|
230 - * that shares no mutable state with this instance. |
|
231 * However, with very high probability, the set of values collectively |
|
232 * generated by the two objects has the same statistical properties as if |
|
233 * same the quantity of values were generated by a single thread using |
|
234 - * a single {@link L128X256MixRandom} object. Either or both of the two |
|
235 * objects may be further split using the {@code split} method, |
|
236 * and the same expected statistical properties apply to the |
|
237 * entire set of generators constructed by such recursive splitting. |
|
238 * |
|
239 - * @param source a {@link SplittableGenerator} instance to be used instead |
|
240 * of this one as a source of pseudorandom bits used to |
|
241 * initialize the state of the new ones. |
|
242 - * @return a new instance of {@link L128X256MixRandom} |
|
243 */ |
|
244 - public L128X256MixRandom split(SplittableGenerator source) { |
|
245 - // Literally pick a new instance "at random". |
|
246 - return new L128X256MixRandom(source.nextLong(), source.nextLong(), |
|
247 - source.nextLong(), source.nextLong(), |
|
248 - source.nextLong(), source.nextLong(), |
|
249 - source.nextLong(), source.nextLong()); |
|
250 } |
|
251 |
|
252 /** |
|
253 --- 300,330 ---- |
|
254 } |
|
255 |
|
256 /* ---------------- public methods ---------------- */ |
|
257 + |
|
258 /** |
|
259 + * Given 63 bits of "brine", constructs and returns a new instance of |
|
260 + * {@code L128X256MixRandom} that shares no mutable state with this instance. |
|
261 * However, with very high probability, the set of values collectively |
|
262 * generated by the two objects has the same statistical properties as if |
|
263 * same the quantity of values were generated by a single thread using |
|
264 + * a single {@code L128X256MixRandom} object. Either or both of the two |
|
265 * objects may be further split using the {@code split} method, |
|
266 * and the same expected statistical properties apply to the |
|
267 * entire set of generators constructed by such recursive splitting. |
|
268 * |
|
269 + * @param source a {@code SplittableGenerator} instance to be used instead |
|
270 * of this one as a source of pseudorandom bits used to |
|
271 * initialize the state of the new ones. |
|
272 + * @param brine a long value, of which the low 63 bits are used to choose |
|
273 + * the {@code a} parameter for the new instance. |
|
274 + * @return a new instance of {@code L128X256MixRandom} |
|
275 */ |
|
276 + public SplittableGenerator split(SplittableGenerator source, long brine) { |
|
277 + // Pick a new instance "at random", but use the brine for (the low half of) `a`. |
|
278 + return new L128X256MixRandom(source.nextLong(), brine << 1, |
|
279 + source.nextLong(), source.nextLong(), |
|
280 + source.nextLong(), source.nextLong(), |
|
281 + source.nextLong(), source.nextLong()); |
|
282 } |
|
283 |
|
284 /** |
|
285 *************** |
|
286 *** 354,365 **** |
|
287 * @return a pseudorandom {@code long} value |
|
288 */ |
|
289 public long nextLong() { |
|
290 - final long z = sh + x0; |
|
291 - // The LCG: in effect, s = ((1LL << 64) + M) * s + a, if only we had 128-bit arithmetic. |
|
292 - final long u = M * sl; |
|
293 - sh = (M * sh) + Math.multiplyHigh(M, sl) + sl + ah; |
|
294 sl = u + al; |
|
295 if (Long.compareUnsigned(sl, u) < 0) ++sh; // Handle the carry propagation from low half to high half. |
|
296 long q0 = x0, q1 = x1, q2 = x2, q3 = x3; |
|
297 { // xoshiro256 1.0 |
|
298 long t = q1 << 17; |
|
299 --- 333,359 ---- |
|
300 * @return a pseudorandom {@code long} value |
|
301 */ |
|
302 public long nextLong() { |
|
303 + // Compute the result based on current state information |
|
304 + // (this allows the computation to be overlapped with state update). |
|
305 + final long result = RandomSupport.mixLea64(sh + x0); |
|
306 + |
|
307 + // Update the LCG subgenerator |
|
308 + // The LCG is, in effect, s = ((1LL << 64) + ML) * s + a, if only we had 128-bit arithmetic. |
|
309 + final long u = ML * sl; |
|
310 + // Note that Math.multiplyHigh computes the high half of the product of signed values, |
|
311 + // but what we need is the high half of the product of unsigned values; for this we use the |
|
312 + // formula "unsignedMultiplyHigh(a, b) = multiplyHigh(a, b) + ((a >> 63) & b) + ((b >> 63) & a)"; |
|
313 + // in effect, each operand is added to the result iff the sign bit of the other operand is 1. |
|
314 + // (See Henry S. Warren, Jr., _Hacker's Delight_ (Second Edition), Addison-Wesley (2013), |
|
315 + // Section 8-3, p. 175; or see the First Edition, Addison-Wesley (2003), Section 8-3, p. 133.) |
|
316 + // If Math.unsignedMultiplyHigh(long, long) is ever implemented, the following line can become: |
|
317 + // sh = (ML * sh) + Math.unsignedMultiplyHigh(ML, sl) + sl + ah; |
|
318 + // and this entire comment can be deleted. |
|
319 + sh = (ML * sh) + (Math.multiplyHigh(ML, sl) + ((ML >> 63) & sl) + ((sl >> 63) & ML)) + sl + ah; |
|
320 sl = u + al; |
|
321 if (Long.compareUnsigned(sl, u) < 0) ++sh; // Handle the carry propagation from low half to high half. |
|
322 + |
|
323 + // Update the Xorshift subgenerator |
|
324 long q0 = x0, q1 = x1, q2 = x2, q3 = x3; |
|
325 { // xoshiro256 1.0 |
|
326 long t = q1 << 17; |
|
327 *************** |
|
328 *** 371,379 **** |
|
329 q3 = Long.rotateLeft(q3, 45); |
|
330 } |
|
331 x0 = q0; x1 = q1; x2 = q2; x3 = q3; |
|
332 - return RandomSupport.mixLea64(z); // mixing function |
|
333 } |
|
334 |
|
335 public BigInteger period() { |
|
336 return PERIOD; |
|
337 } |
|
338 --- 365,379 ---- |
|
339 q3 = Long.rotateLeft(q3, 45); |
|
340 } |
|
341 x0 = q0; x1 = q1; x2 = q2; x3 = q3; |
|
342 + return result; |
|
343 } |
|
344 |
|
345 + /** |
|
346 + * Returns the period of this random generator. |
|
347 + * |
|
348 + * @return a {@link BigInteger} whose value is the number of distinct possible states of this |
|
349 + * {@link RandomGenerator} object (2<sup>128</sup>(2<sup>256</sup>-1)). |
|
350 + */ |
|
351 public BigInteger period() { |
|
352 return PERIOD; |
|
353 } |