20 * |
20 * |
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
22 * or visit www.oracle.com if you need additional information or have any |
22 * or visit www.oracle.com if you need additional information or have any |
23 * questions. |
23 * questions. |
24 */ |
24 */ |
25 package java.util; |
25 |
|
26 package java.util.random; |
26 |
27 |
27 import java.math.BigInteger; |
28 import java.math.BigInteger; |
28 import java.util.concurrent.atomic.AtomicLong; |
29 import java.util.concurrent.atomic.AtomicLong; |
29 |
30 |
30 /** |
31 /** |
31 * A generator of uniform pseudorandom values applicable for use in |
32 * A generator of uniform pseudorandom values applicable for use in |
32 * (among other contexts) isolated parallel computations that may |
33 * (among other contexts) isolated parallel computations that may |
33 * generate subtasks. Class {@code Xoroshiro128StarStar} implements |
34 * generate subtasks. Class {@link Xoroshiro128StarStar} implements |
34 * interfaces {@link java.util.Rng} and {@link java.util.LeapableRng}, |
35 * interfaces {@link RandomNumberGenerator} and {@link LeapableRNG}, |
35 * and therefore supports methods for producing pseudorandomly chosen |
36 * and therefore supports methods for producing pseudorandomly chosen |
36 * numbers of type {@code int}, {@code long}, {@code float}, and {@code double} |
37 * numbers of type {@code int}, {@code long}, {@code float}, and {@code double} |
37 * as well as creating new {@code Xoroshiro128StarStar} objects |
38 * as well as creating new {@link Xoroshiro128StarStar} objects |
38 * by "jumping" or "leaping". |
39 * by "jumping" or "leaping". |
39 * |
40 * <p> |
40 * <p>Series of generated values pass the TestU01 BigCrush and PractRand test suites |
41 * Series of generated values pass the TestU01 BigCrush and PractRand test suites |
41 * that measure independence and uniformity properties of random number generators. |
42 * that measure independence and uniformity properties of random number generators. |
42 * |
43 * <p> |
43 * <p>The class {@code Xoroshiro128StarStar} uses the {@code xoroshiro128} algorithm, |
44 * The class {@link Xoroshiro128StarStar} uses the {@code xoroshiro128} algorithm, |
44 * version 1.0 (parameters 24, 16, 37), with the "**" scrambler (a mixing function). |
45 * version 1.0 (parameters 24, 16, 37), with the "**" scrambler (a mixing function). |
45 * Its state consists of two {@code long} fields {@code x0} and {@code x1}, |
46 * Its state consists of two {@code long} fields {@code x0} and {@code x1}, |
46 * which can take on any values provided that they are not both zero. |
47 * which can take on any values provided that they are not both zero. |
47 * The period of this generator is 2<sup>128</sup>-1. |
48 * The period of this generator is 2<sup>128</sup>-1. |
48 * |
49 * <p> |
49 * <p>The 64-bit values produced by the {@code nextLong()} method are equidistributed. |
50 * The 64-bit values produced by the {@code nextLong()} method are equidistributed. |
50 * To be precise, over the course of the cycle of length 2<sup>128</sup>-1, |
51 * To be precise, over the course of the cycle of length 2<sup>128</sup>-1, |
51 * each nonzero {@code long} value is generated 2<sup>64</sup> times, |
52 * each nonzero {@code long} value is generated 2<sup>64</sup> times, |
52 * but the value 0 is generated only 2<sup>64</sup>-1 times. |
53 * but the value 0 is generated only 2<sup>64</sup>-1 times. |
53 * The values produced by the {@code nextInt()}, {@code nextFloat()}, and {@code nextDouble()} |
54 * The values produced by the {@code nextInt()}, {@code nextFloat()}, and {@code nextDouble()} |
54 * methods are likewise equidistributed. |
55 * methods are likewise equidistributed. |
55 * |
56 * <p> |
56 * <p>In fact, the 64-bit values produced by the {@code nextLong()} method are 2-equidistributed. |
57 * In fact, the 64-bit values produced by the {@code nextLong()} method are 2-equidistributed. |
57 * To be precise: consider the (overlapping) length-2 subsequences of the cycle of 64-bit |
58 * To be precise: consider the (overlapping) length-2 subsequences of the cycle of 64-bit |
58 * values produced by {@code nextLong()} (assuming no other methods are called that would |
59 * values produced by {@code nextLong()} (assuming no other methods are called that would |
59 * affect the state). There are 2<sup>128</sup>-1 such subsequences, and each subsequence, |
60 * affect the state). There are 2<sup>128</sup>-1 such subsequences, and each subsequence, |
60 * which consists of 2 64-bit values, can have one of 2<sup>128</sup> values. Of those |
61 * which consists of 2 64-bit values, can have one of 2<sup>128</sup> values. Of those |
61 * 2<sup>128</sup> subsequence values, each one is generated exactly once over the course |
62 * 2<sup>128</sup> subsequence values, each one is generated exactly once over the course |
62 * of the entire cycle, except that the subsequence (0, 0) never appears. |
63 * of the entire cycle, except that the subsequence (0, 0) never appears. |
63 * The values produced by the {@code nextInt()}, {@code nextFloat()}, and {@code nextDouble()} |
64 * The values produced by the {@code nextInt()}, {@code nextFloat()}, and {@code nextDouble()} |
64 * methods are likewise 2-equidistributed, but note that that the subsequence (0, 0) |
65 * methods are likewise 2-equidistributed, but note that that the subsequence (0, 0) |
65 * can also appear (but occurring somewhat less frequently than all other subsequences), |
66 * can also appear (but occurring somewhat less frequently than all other subsequences), |
66 * because the values produced by those methods have fewer than 64 randomly chosen bits. |
67 * because the values produced by those methods have fewer than 64 randomly chosen bits. |
67 * |
68 * <p> |
68 * <p>Instances {@code Xoroshiro128StarStar} are <em>not</em> thread-safe. |
69 * Instances {@link Xoroshiro128StarStar} are <em>not</em> thread-safe. |
69 * They are designed to be used so that each thread as its own instance. |
70 * They are designed to be used so that each thread as its own instance. |
70 * The methods {@link #jump} and {@link #leap} and {@link #jumps} and {@link #leaps} |
71 * The methods {@link #jump} and {@link #leap} and {@link #jumps} and {@link #leaps} |
71 * can be used to construct new instances of {@code Xoroshiro128StarStar} that traverse |
72 * can be used to construct new instances of {@link Xoroshiro128StarStar} that traverse |
72 * other parts of the state cycle. |
73 * other parts of the state cycle. |
73 * |
74 * <p> |
74 * <p>Instances of {@code Xoroshiro128StarStar} are not cryptographically |
75 * Instances of {@link Xoroshiro128StarStar} are not cryptographically |
75 * secure. Consider instead using {@link java.security.SecureRandom} |
76 * secure. Consider instead using {@link java.security.SecureRandom} |
76 * in security-sensitive applications. Additionally, |
77 * in security-sensitive applications. Additionally, |
77 * default-constructed instances do not use a cryptographically random |
78 * default-constructed instances do not use a cryptographically random |
78 * seed unless the {@linkplain System#getProperty system property} |
79 * seed unless the {@linkplain System#getProperty system property} |
79 * {@code java.util.secureRandomSeed} is set to {@code true}. |
80 * {@code java.util.secureRandomSeed} is set to {@code true}. |
80 * |
81 * |
81 * @author Guy Steele |
82 * @since 14 |
82 * @author Doug Lea |
|
83 * @since 1.8 |
|
84 */ |
83 */ |
85 public final class Xoroshiro128StarStar implements LeapableRng { |
84 public final class Xoroshiro128StarStar implements LeapableRNG { |
86 |
85 |
87 /* |
86 /* |
88 * Implementation Overview. |
87 * Implementation Overview. |
89 * |
88 * |
90 * This is an implementation of the xoroshiro128** algorithm written |
89 * This is an implementation of the xoroshiro128** algorithm written |
148 * |
147 * |
149 * @param x0 first word of the initial state |
148 * @param x0 first word of the initial state |
150 * @param x1 second word of the initial state |
149 * @param x1 second word of the initial state |
151 */ |
150 */ |
152 public Xoroshiro128StarStar(long x0, long x1) { |
151 public Xoroshiro128StarStar(long x0, long x1) { |
153 this.x0 = x0; |
152 this.x0 = x0; |
154 this.x1 = x1; |
153 this.x1 = x1; |
155 // If x0 and x1 are both zero, we must choose nonzero values. |
154 // If x0 and x1 are both zero, we must choose nonzero values. |
156 if ((x0 | x1) == 0) { |
155 if ((x0 | x1) == 0) { |
157 // At least one of the two values generated here will be nonzero. |
156 // At least one of the two values generated here will be nonzero. |
158 this.x0 = RngSupport.mixStafford13(x0 += RngSupport.GOLDEN_RATIO_64); |
157 this.x0 = RNGSupport.mixStafford13(x0 += RNGSupport.GOLDEN_RATIO_64); |
159 this.x1 = (x0 += RngSupport.GOLDEN_RATIO_64); |
158 this.x1 = (x0 += RNGSupport.GOLDEN_RATIO_64); |
160 } |
159 } |
161 } |
160 } |
162 |
161 |
163 /** |
162 /** |
164 * Creates a new instance of {@code Xoroshiro128StarStar} using the |
163 * Creates a new instance of {@link Xoroshiro128StarStar} using the |
165 * specified {@code long} value as the initial seed. Instances of |
164 * specified {@code long} value as the initial seed. Instances of |
166 * {@code Xoroshiro128StarStar} created with the same seed in the same |
165 * {@link Xoroshiro128StarStar} created with the same seed in the same |
167 * program generate identical sequences of values. |
166 * program generate identical sequences of values. |
168 * |
167 * |
169 * @param seed the initial seed |
168 * @param seed the initial seed |
170 */ |
169 */ |
171 public Xoroshiro128StarStar(long seed) { |
170 public Xoroshiro128StarStar(long seed) { |
172 // Using a value with irregularly spaced 1-bits to xor the seed |
171 // Using a value with irregularly spaced 1-bits to xor the seed |
173 // argument tends to improve "pedestrian" seeds such as 0 or |
172 // argument tends to improve "pedestrian" seeds such as 0 or |
174 // other small integers. We may as well use SILVER_RATIO_64. |
173 // other small integers. We may as well use SILVER_RATIO_64. |
175 // |
174 // |
176 // The x values are then filled in as if by a SplitMix PRNG with |
175 // The x values are then filled in as if by a SplitMix PRNG with |
177 // GOLDEN_RATIO_64 as the gamma value and Stafford13 as the mixer. |
176 // GOLDEN_RATIO_64 as the gamma value and Stafford13 as the mixer. |
178 this(RngSupport.mixStafford13(seed ^= RngSupport.SILVER_RATIO_64), |
177 this(RNGSupport.mixStafford13(seed ^= RNGSupport.SILVER_RATIO_64), |
179 RngSupport.mixStafford13(seed + RngSupport.GOLDEN_RATIO_64)); |
178 RNGSupport.mixStafford13(seed + RNGSupport.GOLDEN_RATIO_64)); |
180 } |
179 } |
181 |
180 |
182 /** |
181 /** |
183 * Creates a new instance of {@code Xoroshiro128StarStar} that is likely to |
182 * Creates a new instance of {@link Xoroshiro128StarStar} that is likely to |
184 * generate sequences of values that are statistically independent |
183 * generate sequences of values that are statistically independent |
185 * of those of any other instances in the current program execution, |
184 * of those of any other instances in the current program execution, |
186 * but may, and typically does, vary across program invocations. |
185 * but may, and typically does, vary across program invocations. |
187 */ |
186 */ |
188 public Xoroshiro128StarStar() { |
187 public Xoroshiro128StarStar() { |
189 // Using GOLDEN_RATIO_64 here gives us a good Weyl sequence of values. |
188 // Using GOLDEN_RATIO_64 here gives us a good Weyl sequence of values. |
190 this(defaultGen.getAndAdd(RngSupport.GOLDEN_RATIO_64)); |
189 this(DEFAULT_GEN.getAndAdd(RNGSupport.GOLDEN_RATIO_64)); |
191 } |
190 } |
192 |
191 |
193 /** |
192 /** |
194 * Creates a new instance of {@code Xoroshiro128StarStar} using the specified array of |
193 * Creates a new instance of {@link Xoroshiro128StarStar} using the specified array of |
195 * initial seed bytes. Instances of {@code Xoroshiro128StarStar} created with the same |
194 * initial seed bytes. Instances of {@link Xoroshiro128StarStar} created with the same |
196 * seed array in the same program execution generate identical sequences of values. |
195 * seed array in the same program execution generate identical sequences of values. |
197 * |
196 * |
198 * @param seed the initial seed |
197 * @param seed the initial seed |
199 */ |
198 */ |
200 public Xoroshiro128StarStar(byte[] seed) { |
199 public Xoroshiro128StarStar(byte[] seed) { |
201 // Convert the seed to 2 long values, which are not both zero. |
200 // Convert the seed to 2 long values, which are not both zero. |
202 long[] data = RngSupport.convertSeedBytesToLongs(seed, 2, 2); |
201 long[] data = RNGSupport.convertSeedBytesToLongs(seed, 2, 2); |
203 long x0 = data[0], x1 = data[1]; |
202 long x0 = data[0], x1 = data[1]; |
204 this.x0 = x0; |
203 this.x0 = x0; |
205 this.x1 = x1; |
204 this.x1 = x1; |
206 } |
205 } |
207 |
206 |
208 /* ---------------- public methods ---------------- */ |
207 /* ---------------- public methods ---------------- */ |
209 |
208 |
210 public Xoroshiro128StarStar copy() { return new Xoroshiro128StarStar(x0, x1); } |
209 public Xoroshiro128StarStar copy() { return new Xoroshiro128StarStar(x0, x1); } |
211 |
210 |
212 /* |
211 /* |
213 |
212 * To the extent possible under law, the author has dedicated all copyright and related and |
214 To the extent possible under law, the author has dedicated all copyright |
213 * neighboring rights to this software to the public domain worldwide. This software is |
215 and related and neighboring rights to this software to the public domain |
214 * distributed without any warranty. |
216 worldwide. This software is distributed without any warranty. |
215 * <p> |
217 |
216 * See <http://creativecommons.org/publicdomain/zero/1.0/>. |
218 See <http://creativecommons.org/publicdomain/zero/1.0/>. */ |
217 */ |
219 |
218 |
220 /* This is the successor to xorshift128+. It is the fastest full-period |
219 /* |
221 generator passing BigCrush without systematic failures, but due to the |
220 * This is the successor to xorshift128+. It is the fastest full-period generator passing |
222 relatively short period it is acceptable only for applications with a |
221 * BigCrush without systematic failures, but due to the relatively short period it is acceptable |
223 mild amount of parallelism; otherwise, use a xorshift1024* generator. |
222 * only for applications with a mild amount of parallelism; otherwise, use a xorshift1024* |
224 |
223 * generator. |
225 Beside passing BigCrush, this generator passes the PractRand test suite |
224 * <p> |
226 up to (and included) 16TB, with the exception of binary rank tests, |
225 * Beside passing BigCrush, this generator passes the PractRand test suite up to (and included) |
227 which fail due to the lowest bit being an LFSR; all other bits pass all |
226 * 16TB, with the exception of binary rank tests, which fail due to the lowest bit being an |
228 tests. We suggest to use a sign test to extract a random Boolean value. |
227 * LFSR; all other bits pass all tests. We suggest to use a sign test to extract a random |
229 |
228 * Boolean value. |
230 Note that the generator uses a simulated rotate operation, which most C |
229 * <p> |
231 compilers will turn into a single instruction. In Java, you can use |
230 * Note that the generator uses a simulated rotate operation, which most C compilers will turn |
232 Long.rotateLeft(). In languages that do not make low-level rotation |
231 * into a single instruction. In Java, you can use Long.rotateLeft(). In languages that do not |
233 instructions accessible xorshift128+ could be faster. |
232 * make low-level rotation instructions accessible xorshift128+ could be faster. |
234 |
233 * <p> |
235 The state must be seeded so that it is not everywhere zero. If you have |
234 * The state must be seeded so that it is not everywhere zero. If you have a 64-bit seed, we |
236 a 64-bit seed, we suggest to seed a splitmix64 generator and use its |
235 * suggest to seed a splitmix64 generator and use its output to fill s. |
237 output to fill s. */ |
236 */ |
238 |
|
239 |
237 |
240 /** |
238 /** |
241 * Returns a pseudorandom {@code long} value. |
239 * Returns a pseudorandom {@code long} value. |
242 * |
240 * |
243 * @return a pseudorandom {@code long} value |
241 * @return a pseudorandom {@code long} value |
244 */ |
242 */ |
245 public long nextLong() { |
243 public long nextLong() { |
246 final long s0 = x0; |
244 final long s0 = x0; |
247 long s1 = x1; |
245 long s1 = x1; |
248 final long z = s0; |
246 final long z = s0; |
249 |
247 |
250 s1 ^= s0; |
248 s1 ^= s0; |
251 x0 = Long.rotateLeft(s0, 24) ^ s1 ^ (s1 << 16); // a, b |
249 x0 = Long.rotateLeft(s0, 24) ^ s1 ^ (s1 << 16); // a, b |
252 x1 = Long.rotateLeft(s1, 37); // c |
250 x1 = Long.rotateLeft(s1, 37); // c |
253 |
251 |
254 return Long.rotateLeft(z * 5, 7) * 9; // "starstar" mixing function |
252 return Long.rotateLeft(z * 5, 7) * 9; // "starstar" mixing function |
255 } |
253 } |
256 |
254 |
257 public BigInteger period() { return thePeriod; } |
255 public BigInteger period() { |
258 |
256 return PERIOD; |
259 public double defaultJumpDistance() { return 0x1.0p64; } |
257 } |
260 |
258 |
261 public double defaultLeapDistance() { return 0x1.0p96; } |
259 public double defaultJumpDistance() { |
|
260 return 0x1.0p64; |
|
261 } |
|
262 |
|
263 public double defaultLeapDistance() { |
|
264 return 0x1.0p96; |
|
265 } |
262 |
266 |
263 private static final long[] JUMP_TABLE = { 0xdf900294d8f554a5L, 0x170865df4b3201fcL }; |
267 private static final long[] JUMP_TABLE = { 0xdf900294d8f554a5L, 0x170865df4b3201fcL }; |
264 |
268 |
265 private static final long[] LEAP_TABLE = { 0xd2a98b26625eee7bL, 0xdddf9b1090aa7ac1L }; |
269 private static final long[] LEAP_TABLE = { 0xd2a98b26625eee7bL, 0xdddf9b1090aa7ac1L }; |
266 |
270 |
267 /* This is the jump function for the generator. It is equivalent |
271 /** |
268 to 2**64 calls to nextLong(); it can be used to generate 2**64 |
272 * This is the jump function for the generator. It is equivalent to 2**64 calls to nextLong(); |
269 non-overlapping subsequences for parallel computations. */ |
273 * it can be used to generate 2**64 non-overlapping subsequences for parallel computations. |
270 |
274 */ |
271 public void jump() { jumpAlgorithm(JUMP_TABLE); } |
275 public void jump() { |
272 |
276 jumpAlgorithm(JUMP_TABLE); |
273 /* This is the long-jump function for the generator. It is equivalent to |
277 } |
274 2**96 calls to next(); it can be used to generate 2**32 starting points, |
278 |
275 from each of which jump() will generate 2**32 non-overlapping |
279 /** |
276 subsequences for parallel distributed computations. */ |
280 * This is the long-jump function for the generator. It is equivalent to 2**96 calls to next(); |
277 |
281 * it can be used to generate 2**32 starting points, from each of which jump() will generate |
278 public void leap() { jumpAlgorithm(LEAP_TABLE); } |
282 * 2**32 non-overlapping subsequences for parallel distributed computations. |
|
283 */ |
|
284 public void leap() { |
|
285 jumpAlgorithm(LEAP_TABLE); |
|
286 } |
279 |
287 |
280 private void jumpAlgorithm(long[] table) { |
288 private void jumpAlgorithm(long[] table) { |
281 long s0 = 0, s1 = 0; |
289 long s0 = 0, s1 = 0; |
282 for (int i = 0; i < table.length; i++) { |
290 for (int i = 0; i < table.length; i++) { |
283 for (int b = 0; b < 64; b++) { |
291 for (int b = 0; b < 64; b++) { |
284 if ((table[i] & (1L << b)) != 0) { |
292 if ((table[i] & (1L << b)) != 0) { |
285 s0 ^= x0; |
293 s0 ^= x0; |
286 s1 ^= x1; |
294 s1 ^= x1; |
287 } |
295 } |
288 nextLong(); |
296 nextLong(); |
289 } |
297 } |
290 x0 = s0; |
298 x0 = s0; |
291 x1 = s1; |
299 x1 = s1; |
292 } |
300 } |
293 } |
301 } |
294 } |
302 } |