ViewVC Help

View File | Revision Log | Show Annotations | Download File | Root Listing

root/jsr166/jsr166/src/main/java/util/SplittableRandom.java

Comparing jsr166/src/main/java/util/SplittableRandom.java (file contents):
Revision 1.7 by dl, Fri Jul 12 11:26:34 2013 UTC vs.
Revision 1.14 by dl, Mon Aug 5 13:58:02 2013 UTC

#	Line 25 | Line 25
25
26		package java.util;
27
28	+	import java.security.SecureRandom;
29		import java.util.concurrent.atomic.AtomicLong;
30		import java.util.Spliterator;
31		import java.util.function.IntConsumer;
#	Line 41 | Line 42 | import java.util.stream.DoubleStream;
42		* generate subtasks. Class SplittableRandom supports methods for
43		* producing pseudorandom numbers of type {@code int}, {@code long},
44		* and {@code double} with similar usages as for class
45	<	* {@link java.util.Random} but differs in the following ways: <ul>
45	>	* {@link java.util.Random} but differs in the following ways:
46	>	*
47	>	* <ul>
48		*
49		* <li>Series of generated values pass the DieHarder suite testing
50		* independence and uniformity properties of random number generators.
#	Line 49 | Line 52 | import java.util.stream.DoubleStream;
52		* href="http://www.phy.duke.edu/~rgb/General/dieharder.php"> version
53		* 3.31.1</a>.) These tests validate only the methods for certain
54		* types and ranges, but similar properties are expected to hold, at
55	<	* least approximately, for others as well.  </li>
55	>	* least approximately, for others as well. The <em>period</em>
56	>	* (length of any series of generated values before it repeats) is at
57	>	* least 2<sup>64</sup>. </li>
58		*
59		* <li> Method {@link #split} constructs and returns a new
60		* SplittableRandom instance that shares no mutable state with the
#	Line 110 | Line 115 | public class SplittableRandom {
115		* are encountered; see method addGammaModGeorge. For this to
116		* work, initial gamma values must be at least 13.
117		*
113	–	* The value of gamma differs for each instance across a series of
114	–	* splits, and is generated using a slightly stripped-down variant
115	–	* of the same algorithm, but operating across calls to split(),
116	–	* not calls to nextSeed(): Each instance carries the state of
117	–	* this generator as nextSplit, and uses mix64(nextSplit) as its
118	–	* own gamma value. Computations of gammas themselves use a fixed
119	–	* constant as the second argument to the addGammaModGeorge
120	–	* function, GAMMA_GAMMA, a "genuinely random" number from a
121	–	* radioactive decay reading (obtained from
122	–	* http://www.fourmilab.ch/hotbits/) meeting the above range
123	–	* constraint. Using a fixed constant maintains the invariant that
124	–	* the value of gamma is the same for every instance that is at
125	–	* the same split-distance from their common root. (Note: there is
126	–	* nothing especially magic about obtaining this constant from a
127	–	* "truly random" physical source rather than just choosing one
128	–	* arbitrarily; using "hotbits" was merely an aesthetically pleasing
129	–	* choice.  In either case, good statistical behavior of the
130	–	* algorithm should be, and was, verified by using the DieHarder
131	–	* test suite.)
132	–	*
118		* The mix64 bit-mixing function called by nextLong and other
119		* methods computes the same value as the "64-bit finalizer"
120		* function in Austin Appleby's MurmurHash3 algorithm.  See
121		* http://code.google.com/p/smhasher/wiki/MurmurHash3 , which
122		* comments: "The constants for the finalizers were generated by a
123		* simple simulated-annealing algorithm, and both avalanche all
124	<	* bits of 'h' to within 0.25% bias." It also appears to work to
125	<	* use instead any of the variants proposed by David Stafford at
126	<	* http://zimbry.blogspot.com/2011/09/better-bit-mixing-improving-on.html
127	<	* but these variants have not yet been tested as thoroughly
128	<	* in the context of the implementation of SplittableRandom.
124	>	* bits of 'h' to within 0.25% bias."
125	>	*
126	>	* The value of gamma differs for each instance across a series of
127	>	* splits, and is generated using an independent variant of the
128	>	* same algorithm, but operating across calls to split(), not
129	>	* calls to nextSeed(): Each instance carries the state of this
130	>	* generator as nextSplit. Gammas are treated as 57bit values,
131	>	* advancing by adding GAMMA_GAMMA mod GAMMA_PRIME, and bit-mixed
132	>	* with a 57-bit version of mix, using the "Mix13" multiplicative
133	>	* constants for MurmurHash3 described by David Stafford
134	>	* (http://zimbry.blogspot.com/2011/09/better-bit-mixing-improving-on.html).
135	>	* The value of GAMMA_GAMMA is arbitrary (except must be at least
136	>	* 13 and less than GAMMA_PRIME), but because it serves as the
137	>	* base of split sequences, should be subject to validation of
138	>	* consequent random number quality metrics.
139		*
140		* The mix32 function used for nextInt just consists of two of the
141	<	* five lines of mix64; avalanche testing shows that the 64-bit result
142	<	* has its top 32 bits avalanched well, though not the bottom 32 bits.
143	<	* DieHarder tests show that it is adequate for generating one
144	<	* random int from the 64-bit result of nextSeed.
141	>	* five lines of mix64; avalanche testing shows that the 64-bit
142	>	* result has its top 32 bits avalanched well, though not the
143	>	* bottom 32 bits.  DieHarder tests show that it is adequate for
144	>	* generating one random int from the 64-bit result of nextSeed.
145		*
146		* Support for the default (no-argument) constructor relies on an
147		* AtomicLong (defaultSeedGenerator) to help perform the
#	Line 154 | Line 149 | public class SplittableRandom {
149		* SplittableRandom. Unlike other cases, this split must be
150		* performed in a thread-safe manner. We use
151		* AtomicLong.compareAndSet as the (typically) most efficient
152	<	* mechanism. To bootstrap, we start off using System.nanotime(),
153	<	* and update using another "genuinely random" constant
152	>	* mechanism. To bootstrap, we start off using a SecureRandom
153	>	* initial default seed, and update using a fixed
154		* DEFAULT_SEED_GAMMA. The default constructor uses GAMMA_GAMMA,
155		* not 0, for its splitSeed argument (addGammaModGeorge(0,
156		* GAMMA_GAMMA) == GAMMA_GAMMA) to reflect that each is split from
#	Line 164 | Line 159 | public class SplittableRandom {
159		*/
160
161		/**
162	<	* The "genuinely random" value for producing new gamma values.
163	<	* The value is arbitrary, subject to the requirement that it be
164	<	* greater or equal to 13.
162	>	* The prime modulus for gamma values.
163	>	*/
164	>	private static final long GAMMA_PRIME = (1L << 57) - 13L;
165	>
166	>	/**
167	>	* The value for producing new gamma values. Must be greater or
168	>	* equal to 13 and less than GAMMA_PRIME. Otherwise, the value is
169	>	* arbitrary subject to validation of the resulting statistical
170	>	* quality of splits.
171		*/
172	<	private static final long GAMMA_GAMMA = 0xF2281E2DBA6606F3L;
172	>	private static final long GAMMA_GAMMA = 0x00aae38294f712aabL;
173
174		/**
175	<	* The "genuinely random" seed update value for default constructors.
176	<	* The value is arbitrary, subject to the requirement that it be
177	<	* greater or equal to 13.
175	>	* The seed update value for default constructors.  Must be
176	>	* greater or equal to 13. Otherwise, the value is arbitrary
177	>	* subject to quality checks.
178		*/
179	<	private static final long DEFAULT_SEED_GAMMA = 0xBD24B73A95FB84D9L;
179	>	private static final long DEFAULT_SEED_GAMMA = 0x9e3779b97f4a7c15L;
180	>
181	>	/**
182	>	* The value 13 with 64bit sign bit set. Used in the signed
183	>	* comparison in addGammaModGeorge.
184	>	*/
185	>	private static final long BOTTOM13 = 0x800000000000000DL;
186
187		/**
188		* The least non-zero value returned by nextDouble(). This value
#	Line 187 | Line 194 | public class SplittableRandom {
194		* The next seed for default constructors.
195		*/
196		private static final AtomicLong defaultSeedGenerator =
197	<	new AtomicLong(System.nanoTime());
197	>	new AtomicLong(getInitialDefaultSeed());
198
199		/**
200		* The seed, updated only via method nextSeed.
#	Line 215 | Line 222 | public class SplittableRandom {
222		* George < 2^64; thus we need only a conditional, not a loop,
223		* to be sure of getting a representable value.
224		*
225	<	* @param s a seed value
225	>	* Because Java comparison operators are signed, we implement this
226	>	* by conceptually offsetting seed values downwards by 2^63, so
227	>	* 0..13 is represented as Long.MIN_VALUE..BOTTOM13.
228	>	*
229	>	* @param s a seed value, viewed as a signed long
230		* @param g a gamma value, 13 <= g (as unsigned)
231		*/
232		private static long addGammaModGeorge(long s, long g) {
233		long p = s + g;
234	<	if (Long.compareUnsigned(p, g) >= 0)
224	<	return p;
225	<	long q = p - 13L;
226	<	return (Long.compareUnsigned(p, 13L) >= 0) ? q : (q + g);
234	>	return (p >= s) ? p : ((p >= BOTTOM13) ? p  : p + g) - 13L;
235		}
236
237		/**
#	Line 250 | Line 258 | public class SplittableRandom {
258		}
259
260		/**
261	+	* Returns a 57-bit mixed transformation of its argument.  See
262	+	* above for explanation.
263	+	*/
264	+	private static long mix57(long z) {
265	+	z = (z ^ (z >>> 30)) * 0xbf58476d1ce4e5b9L;
266	+	z &= 0x01FFFFFFFFFFFFFFL;
267	+	z = (z ^ (z >>> 27)) * 0x94d049bb133111ebL;
268	+	z &= 0x01FFFFFFFFFFFFFFL;
269	+	z ^= (z >>> 31);
270	+	return z;
271	+	}
272	+
273	+	/**
274		* Internal constructor used by all other constructors and by
275		* method split. Establishes the initial seed for this instance,
276		* and uses the given splitSeed to establish gamma, as well as the
#	Line 260 | Line 281 | public class SplittableRandom {
281		this.seed = seed;
282		long s = splitSeed, g;
283		do { // ensure gamma >= 13, considered as an unsigned integer
284	<	s = addGammaModGeorge(s, GAMMA_GAMMA);
285	<	g = mix64(s);
286	<	} while (Long.compareUnsigned(g, 13L) < 0);
284	>	s += GAMMA_GAMMA;
285	>	if (s >= GAMMA_PRIME)
286	>	s -= GAMMA_PRIME;
287	>	g = mix57(s);
288	>	} while (g < 13L);
289		this.gamma = g;
290		this.nextSplit = s;
291		}
#	Line 287 | Line 310 | public class SplittableRandom {
310		return mix64(newSeed);
311		}
312
313	+	/**
314	+	* Returns an initial default seed.
315	+	*/
316	+	private static long getInitialDefaultSeed() {
317	+	byte[] seedBytes = java.security.SecureRandom.getSeed(8);
318	+	long s = (long)(seedBytes[0]) & 0xffL;
319	+	for (int i = 1; i < 8; ++i)
320	+	s = (s << 8) | ((long)(seedBytes[i]) & 0xffL);
321	+	return s;
322	+	}
323	+
324		/*
325		* Internal versions of nextX methods used by streams, as well as
326		* the public nextX(origin, bound) methods.  These exist mainly to
#	Line 362 | Line 396 | public class SplittableRandom {
396		int r = mix32(nextSeed());
397		if (origin < bound) {
398		int n = bound - origin, m = n - 1;
399	<	if ((n & m) == 0L)
399	>	if ((n & m) == 0)
400		r = (r & m) + origin;
401		else if (n > 0) {
402		for (int u = r >>> 1;
#	Line 401 | Line 435 | public class SplittableRandom {
435		/**
436		* Creates a new SplittableRandom instance using the specified
437		* initial seed. SplittableRandom instances created with the same
438	<	* seed generate identical sequences of values.
438	>	* seed in the same program generate identical sequences of values.
439		*
440		* @param seed the initial seed
441		*/
442		public SplittableRandom(long seed) {
443	<	this(seed, 0);
443	>	this(seed, 0L);
444		}
445
446		/**
#	Line 453 | Line 487 | public class SplittableRandom {
487		* @param bound the bound on the random number to be returned.  Must be
488		*        positive.
489		* @return a pseudorandom {@code int} value between zero
490	<	*         (inclusive) and the bound (exclusive).
490	>	*         (inclusive) and the bound (exclusive)
491		* @throws IllegalArgumentException if the bound is less than zero
492		*/
493		public int nextInt(int bound) {
#	Line 462 | Line 496 | public class SplittableRandom {
496		// Specialize internalNextInt for origin 0
497		int r = mix32(nextSeed());
498		int m = bound - 1;
499	<	if ((bound & m) == 0L) // power of two
499	>	if ((bound & m) == 0) // power of two
500		r &= m;
501		else { // reject over-represented candidates
502		for (int u = r >>> 1;
#	Line 480 | Line 514 | public class SplittableRandom {
514		* @param origin the least value returned
515		* @param bound the upper bound (exclusive)
516		* @return a pseudorandom {@code int} value between the origin
517	<	*         (inclusive) and the bound (exclusive).
517	>	*         (inclusive) and the bound (exclusive)
518		* @throws IllegalArgumentException if {@code origin} is greater than
519		*         or equal to {@code bound}
520		*/
#	Line 506 | Line 540 | public class SplittableRandom {
540		* @param bound the bound on the random number to be returned.  Must be
541		*        positive.
542		* @return a pseudorandom {@code long} value between zero
543	<	*         (inclusive) and the bound (exclusive).
543	>	*         (inclusive) and the bound (exclusive)
544		* @throws IllegalArgumentException if {@code bound} is less than zero
545		*/
546		public long nextLong(long bound) {
#	Line 533 | Line 567 | public class SplittableRandom {
567		* @param origin the least value returned
568		* @param bound the upper bound (exclusive)
569		* @return a pseudorandom {@code long} value between the origin
570	<	*         (inclusive) and the bound (exclusive).
570	>	*         (inclusive) and the bound (exclusive)
571		* @throws IllegalArgumentException if {@code origin} is greater than
572		*         or equal to {@code bound}
573		*/
#	Line 551 | Line 585 | public class SplittableRandom {
585		* (inclusive) and one (exclusive)
586		*/
587		public double nextDouble() {
588	<	return (nextLong() >>> 11) * DOUBLE_UNIT;
588	>	return (mix64(nextSeed()) >>> 11) * DOUBLE_UNIT;
589		}
590
591		/**
#	Line 561 | Line 595 | public class SplittableRandom {
595		* @param bound the bound on the random number to be returned.  Must be
596		*        positive.
597		* @return a pseudorandom {@code double} value between zero
598	<	*         (inclusive) and the bound (exclusive).
598	>	*         (inclusive) and the bound (exclusive)
599		* @throws IllegalArgumentException if {@code bound} is less than zero
600		*/
601		public double nextDouble(double bound) {
602		if (!(bound > 0.0))
603		throw new IllegalArgumentException("bound must be positive");
604	<	double result = nextDouble() * bound;
604	>	double result = (mix64(nextSeed()) >>> 11) * DOUBLE_UNIT * bound;
605		return (result < bound) ?  result : // correct for rounding
606		Double.longBitsToDouble(Double.doubleToLongBits(bound) - 1);
607		}
#	Line 579 | Line 613 | public class SplittableRandom {
613		* @param origin the least value returned
614		* @param bound the upper bound
615		* @return a pseudorandom {@code double} value between the origin
616	<	*         (inclusive) and the bound (exclusive).
616	>	*         (inclusive) and the bound (exclusive)
617		* @throws IllegalArgumentException if {@code origin} is greater than
618		*         or equal to {@code bound}
619		*/
#	Line 589 | Line 623 | public class SplittableRandom {
623		return internalNextDouble(origin, bound);
624		}
625
626	+	/**
627	+	* Returns a pseudorandom {@code boolean} value.
628	+	*
629	+	* @return a pseudorandom {@code boolean} value
630	+	*/
631	+	public boolean nextBoolean() {
632	+	return mix32(nextSeed()) < 0;
633	+	}
634	+
635		// stream methods, coded in a way intended to better isolate for
636		// maintenance purposes the small differences across forms.
637
#	Line 612 | Line 655 | public class SplittableRandom {
655
656		/**
657		* Returns an effectively unlimited stream of pseudorandom {@code int}
658	<	* values
658	>	* values.
659		*
660		* @implNote This method is implemented to be equivalent to {@code
661		* ints(Long.MAX_VALUE)}.
#	Line 635 | Line 678 | public class SplittableRandom {
678		* @param randomNumberOrigin the origin of each random value
679		* @param randomNumberBound the bound of each random value
680		* @return a stream of pseudorandom {@code int} values,
681	<	*         each with the given origin and bound.
681	>	*         each with the given origin and bound
682		* @throws IllegalArgumentException if {@code streamSize} is
683		*         less than zero, or {@code randomNumberOrigin}
684		*         is greater than or equal to {@code randomNumberBound}
#	Line 662 | Line 705 | public class SplittableRandom {
705		* @param randomNumberOrigin the origin of each random value
706		* @param randomNumberBound the bound of each random value
707		* @return a stream of pseudorandom {@code int} values,
708	<	*         each with the given origin and bound.
708	>	*         each with the given origin and bound
709		* @throws IllegalArgumentException if {@code randomNumberOrigin}
710		*         is greater than or equal to {@code randomNumberBound}
711		*/
#	Line 718 | Line 761 | public class SplittableRandom {
761		* @param randomNumberOrigin the origin of each random value
762		* @param randomNumberBound the bound of each random value
763		* @return a stream of pseudorandom {@code long} values,
764	<	*         each with the given origin and bound.
764	>	*         each with the given origin and bound
765		* @throws IllegalArgumentException if {@code streamSize} is
766		*         less than zero, or {@code randomNumberOrigin}
767		*         is greater than or equal to {@code randomNumberBound}
#	Line 745 | Line 788 | public class SplittableRandom {
788		* @param randomNumberOrigin the origin of each random value
789		* @param randomNumberBound the bound of each random value
790		* @return a stream of pseudorandom {@code long} values,
791	<	*         each with the given origin and bound.
791	>	*         each with the given origin and bound
792		* @throws IllegalArgumentException if {@code randomNumberOrigin}
793		*         is greater than or equal to {@code randomNumberBound}
794		*/
#	Line 803 | Line 846 | public class SplittableRandom {
846		* @param randomNumberOrigin the origin of each random value
847		* @param randomNumberBound the bound of each random value
848		* @return a stream of pseudorandom {@code double} values,
849	<	* each with the given origin and bound.
849	>	* each with the given origin and bound
850		* @throws IllegalArgumentException if {@code streamSize} is
851	<	* less than zero.
851	>	* less than zero
852		* @throws IllegalArgumentException if {@code randomNumberOrigin}
853		*         is greater than or equal to {@code randomNumberBound}
854		*/
#	Line 831 | Line 874 | public class SplittableRandom {
874		* @param randomNumberOrigin the origin of each random value
875		* @param randomNumberBound the bound of each random value
876		* @return a stream of pseudorandom {@code double} values,
877	<	* each with the given origin and bound.
877	>	* each with the given origin and bound
878		* @throws IllegalArgumentException if {@code randomNumberOrigin}
879		*         is greater than or equal to {@code randomNumberBound}
880		*/
#	Line 852 | Line 895 | public class SplittableRandom {
895		* approach. The long and double versions of this class are
896		* identical except for types.
897		*/
898	<	static class RandomIntsSpliterator implements Spliterator.OfInt {
898	>	static final class RandomIntsSpliterator implements Spliterator.OfInt {
899		final SplittableRandom rng;
900		long index;
901		final long fence;
#	Line 906 | Line 949 | public class SplittableRandom {
949		/**
950		* Spliterator for long streams.
951		*/
952	<	static class RandomLongsSpliterator implements Spliterator.OfLong {
952	>	static final class RandomLongsSpliterator implements Spliterator.OfLong {
953		final SplittableRandom rng;
954		long index;
955		final long fence;
#	Line 961 | Line 1004 | public class SplittableRandom {
1004		/**
1005		* Spliterator for double streams.
1006		*/
1007	<	static class RandomDoublesSpliterator implements Spliterator.OfDouble {
1007	>	static final class RandomDoublesSpliterator implements Spliterator.OfDouble {
1008		final SplittableRandom rng;
1009		long index;
1010		final long fence;
#	Line 1013 | Line 1056 | public class SplittableRandom {
1056		}
1057
1058		}
1016	–

Diff Legend

–	Removed lines
+	Added lines
<	Changed lines
>	Changed lines