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.3 by jsr166, Thu Jul 11 03:31:26 2013 UTC vs.
Revision 1.7 by dl, Fri Jul 12 11:26:34 2013 UTC

#	Line 35 | Line 35 | import java.util.stream.IntStream;
35		import java.util.stream.LongStream;
36		import java.util.stream.DoubleStream;
37
38	–
38		/**
39		* A generator of uniform pseudorandom values applicable for use in
40		* (among other contexts) isolated parallel computations that may
#	Line 54 | Line 53 | import java.util.stream.DoubleStream;
53		*
54		* <li> Method {@link #split} constructs and returns a new
55		* SplittableRandom instance that shares no mutable state with the
56	<	* current instance. However, with very high probability, the set of
57	<	* values collectively generated by the two objects has the same
56	>	* current instance. However, with very high probability, the
57	>	* values collectively generated by the two objects have the same
58		* statistical properties as if the same quantity of values were
59		* generated by a single thread using a single {@code
60		* SplittableRandom} object.  </li>
#	Line 97 | Line 96 | public class SplittableRandom {
96		* Random-Number Generation for Dynamic-Multithreading Platforms",
97		* PPoPP 2012, but improves and extends it in several ways.
98		*
99	<	* The primary update step is simply to add a constant ("gamma")
100	<	* to the current seed, modulo a prime ("George"). However, the
101	<	* nextLong and nextInt methods do not return this value, but
102	<	* instead the results of bit-mixing transformations that produce
103	<	* more uniformly distributed sequences.
99	>	* The primary update step (see method nextSeed()) is simply to
100	>	* add a constant ("gamma") to the current seed, modulo a prime
101	>	* ("George"). However, the nextLong and nextInt methods do not
102	>	* return this value, but instead the results of bit-mixing
103	>	* transformations that produce more uniformly distributed
104	>	* sequences.
105		*
106		* "George" is the otherwise nameless (because it cannot be
107		* represented) prime number 2^64+13. Using a prime number larger
#	Line 178 | Line 178 | public class SplittableRandom {
178		private static final long DEFAULT_SEED_GAMMA = 0xBD24B73A95FB84D9L;
179
180		/**
181	+	* The least non-zero value returned by nextDouble(). This value
182	+	* is scaled by a random value of 53 bits to produce a result.
183	+	*/
184	+	private static final double DOUBLE_UNIT = 1.0 / (1L << 53);
185	+
186	+	/**
187		* The next seed for default constructors.
188		*/
189		private static final AtomicLong defaultSeedGenerator =
#	Line 200 | Line 206 | public class SplittableRandom {
206		private final long nextSplit;
207
208		/**
203	–	* Internal constructor used by all other constructors and by
204	–	* method split. Establishes the initial seed for this instance,
205	–	* and uses the given splitSeed to establish gamma, as well as the
206	–	* nextSplit to use by this instance.
207	–	*/
208	–	private SplittableRandom(long seed, long splitSeed) {
209	–	this.seed = seed;
210	–	long s = splitSeed, g;
211	–	do { // ensure gamma >= 13, considered as an unsigned integer
212	–	s = addGammaModGeorge(s, GAMMA_GAMMA);
213	–	g = mix64(s);
214	–	} while (Long.compareUnsigned(g, 13L) < 0);
215	–	this.gamma = g;
216	–	this.nextSplit = s;
217	–	}
218	–
219	–	/**
209		* Adds the given gamma value, g, to the given seed value s, mod
210		* George (2^64+13). We regard s and g as unsigned values
211		* (ranging from 0 to 2^64-1). We add g to s either once or twice
#	Line 238 | Line 227 | public class SplittableRandom {
227		}
228
229		/**
241	–	* Updates in-place and returns seed.
242	–	* See above for explanation.
243	–	*/
244	–	private long nextSeed() {
245	–	return seed = addGammaModGeorge(seed, gamma);
246	–	}
247	–
248	–	/**
230		* Returns a bit-mixed transformation of its argument.
231		* See above for explanation.
232		*/
#	Line 269 | Line 250 | public class SplittableRandom {
250		}
251
252		/**
253	<	* Atomically updates and returns next seed for default constructor
253	>	* Internal constructor used by all other constructors and by
254	>	* method split. Establishes the initial seed for this instance,
255	>	* and uses the given splitSeed to establish gamma, as well as the
256	>	* nextSplit to use by this instance. The loop to skip ineligible
257	>	* gammas very rarely iterates, and does so at most 13 times.
258	>	*/
259	>	private SplittableRandom(long seed, long splitSeed) {
260	>	this.seed = seed;
261	>	long s = splitSeed, g;
262	>	do { // ensure gamma >= 13, considered as an unsigned integer
263	>	s = addGammaModGeorge(s, GAMMA_GAMMA);
264	>	g = mix64(s);
265	>	} while (Long.compareUnsigned(g, 13L) < 0);
266	>	this.gamma = g;
267	>	this.nextSplit = s;
268	>	}
269	>
270	>	/**
271	>	* Updates in-place and returns seed.
272	>	* See above for explanation.
273	>	*/
274	>	private long nextSeed() {
275	>	return seed = addGammaModGeorge(seed, gamma);
276	>	}
277	>
278	>	/**
279	>	* Atomically updates and returns next seed for default constructor.
280		*/
281		private static long nextDefaultSeed() {
282		long oldSeed, newSeed;
#	Line 311 | Line 318 | public class SplittableRandom {
318		* evenly divisible by the range. The loop rejects candidates
319		* computed from otherwise over-represented values.  The
320		* expected number of iterations under an ideal generator
321	<	* varies from 1 to 2, depending on the bound.
321	>	* varies from 1 to 2, depending on the bound. The loop itself
322	>	* takes an unlovable form. Because the first candidate is
323	>	* already available, we need a break-in-the-middle
324	>	* construction, which is concisely but cryptically performed
325	>	* within the while-condition of a body-less for loop.
326		*
327		* 4. Otherwise, the range cannot be represented as a positive
328	<	* long.  Repeatedly generate unbounded longs until obtaining
329	<	* a candidate meeting constraints (with an expected number of
330	<	* iterations of less than two).
328	>	* long.  The loop repeatedly generates unbounded longs until
329	>	* obtaining a candidate meeting constraints (with an expected
330	>	* number of iterations of less than two).
331		*/
332
333		long r = mix64(nextSeed());
334		if (origin < bound) {
335		long n = bound - origin, m = n - 1;
336	<	if ((n & m) == 0L) // power of two
336	>	if ((n & m) == 0L)  // power of two
337		r = (r & m) + origin;
338	<	else if (n > 0) { // reject over-represented candidates
338	>	else if (n > 0L) {  // reject over-represented candidates
339		for (long u = r >>> 1;            // ensure nonnegative
340	<	u + m - (r = u % n) < 0L;    // reject
340	>	u + m - (r = u % n) < 0L;    // rejection check
341		u = mix64(nextSeed()) >>> 1) // retry
342		;
343		r += origin;
344		}
345	<	else {             // range not representable as long
345	>	else {              // range not representable as long
346		while (r < origin || r >= bound)
347		r = mix64(nextSeed());
348		}
#	Line 355 | Line 366 | public class SplittableRandom {
366		r = (r & m) + origin;
367		else if (n > 0) {
368		for (int u = r >>> 1;
369	<	u + m - (r = u % n) < 0L;
369	>	u + m - (r = u % n) < 0;
370		u = mix32(nextSeed()) >>> 1)
371		;
372		r += origin;
#	Line 376 | Line 387 | public class SplittableRandom {
387		* @return a pseudorandom value
388		*/
389		final double internalNextDouble(double origin, double bound) {
390	<	long bits = (1023L << 52) | (nextLong() >>> 12);
380	<	double r = Double.longBitsToDouble(bits) - 1.0;
390	>	double r = (nextLong() >>> 11) * DOUBLE_UNIT;
391		if (origin < bound) {
392		r = r * (bound - origin) + origin;
393	<	if (r == bound) // correct for rounding
393	>	if (r >= bound) // correct for rounding
394		r = Double.longBitsToDouble(Double.doubleToLongBits(bound) - 1);
395		}
396		return r;
#	Line 389 | Line 399 | public class SplittableRandom {
399		/* ---------------- public methods ---------------- */
400
401		/**
402	<	* Creates a new SplittableRandom instance using the given initial
403	<	* seed. Two SplittableRandom instances created with the same seed
404	<	* generate identical sequences of values.
402	>	* Creates a new SplittableRandom instance using the specified
403	>	* initial seed. SplittableRandom instances created with the same
404	>	* seed generate identical sequences of values.
405		*
406		* @param seed the initial seed
407		*/
#	Line 430 | Line 440 | public class SplittableRandom {
440		/**
441		* Returns a pseudorandom {@code int} value.
442		*
443	<	* @return a pseudorandom value
443	>	* @return a pseudorandom {@code int} value
444		*/
445		public int nextInt() {
446		return mix32(nextSeed());
447		}
448
449		/**
450	<	* Returns a pseudorandom {@code int} value between 0 (inclusive)
450	>	* Returns a pseudorandom {@code int} value between zero (inclusive)
451		* and the specified bound (exclusive).
452		*
453		* @param bound the bound on the random number to be returned.  Must be
454		*        positive.
455	<	* @return a pseudorandom {@code int} value between {@code 0}
455	>	* @return a pseudorandom {@code int} value between zero
456		*         (inclusive) and the bound (exclusive).
457	<	* @exception IllegalArgumentException if the bound is not positive
457	>	* @throws IllegalArgumentException if the bound is less than zero
458		*/
459		public int nextInt(int bound) {
460		if (bound <= 0)
#	Line 456 | Line 466 | public class SplittableRandom {
466		r &= m;
467		else { // reject over-represented candidates
468		for (int u = r >>> 1;
469	<	u + m - (r = u % bound) < 0L;
469	>	u + m - (r = u % bound) < 0;
470		u = mix32(nextSeed()) >>> 1)
471		;
472		}
#	Line 471 | Line 481 | public class SplittableRandom {
481		* @param bound the upper bound (exclusive)
482		* @return a pseudorandom {@code int} value between the origin
483		*         (inclusive) and the bound (exclusive).
484	<	* @exception IllegalArgumentException if {@code origin} is greater than
484	>	* @throws IllegalArgumentException if {@code origin} is greater than
485		*         or equal to {@code bound}
486		*/
487		public int nextInt(int origin, int bound) {
#	Line 483 | Line 493 | public class SplittableRandom {
493		/**
494		* Returns a pseudorandom {@code long} value.
495		*
496	<	* @return a pseudorandom value
496	>	* @return a pseudorandom {@code long} value
497		*/
498		public long nextLong() {
499		return mix64(nextSeed());
500		}
501
502		/**
503	<	* Returns a pseudorandom {@code long} value between 0 (inclusive)
503	>	* Returns a pseudorandom {@code long} value between zero (inclusive)
504		* and the specified bound (exclusive).
505		*
506		* @param bound the bound on the random number to be returned.  Must be
507		*        positive.
508	<	* @return a pseudorandom {@code long} value between {@code 0}
508	>	* @return a pseudorandom {@code long} value between zero
509		*         (inclusive) and the bound (exclusive).
510	<	* @exception IllegalArgumentException if the bound is not positive
510	>	* @throws IllegalArgumentException if {@code bound} is less than zero
511		*/
512		public long nextLong(long bound) {
513		if (bound <= 0)
#	Line 524 | Line 534 | public class SplittableRandom {
534		* @param bound the upper bound (exclusive)
535		* @return a pseudorandom {@code long} value between the origin
536		*         (inclusive) and the bound (exclusive).
537	<	* @exception IllegalArgumentException if {@code origin} is greater than
537	>	* @throws IllegalArgumentException if {@code origin} is greater than
538		*         or equal to {@code bound}
539		*/
540		public long nextLong(long origin, long bound) {
#	Line 534 | Line 544 | public class SplittableRandom {
544		}
545
546		/**
547	<	* Returns a pseudorandom {@code double} value between {@code 0.0}
548	<	* (inclusive) and {@code 1.0} (exclusive).
547	>	* Returns a pseudorandom {@code double} value between zero
548	>	* (inclusive) and one (exclusive).
549		*
550	<	* @return a pseudorandom value between {@code 0.0}
551	<	* (inclusive) and {@code 1.0} (exclusive)
550	>	* @return a pseudorandom {@code double} value between zero
551	>	* (inclusive) and one (exclusive)
552		*/
553		public double nextDouble() {
554	<	long bits = (1023L << 52) | (nextLong() >>> 12);
545	<	return Double.longBitsToDouble(bits) - 1.0;
554	>	return (nextLong() >>> 11) * DOUBLE_UNIT;
555		}
556
557		/**
#	Line 551 | Line 560 | public class SplittableRandom {
560		*
561		* @param bound the bound on the random number to be returned.  Must be
562		*        positive.
563	<	* @return a pseudorandom {@code double} value between {@code 0.0}
563	>	* @return a pseudorandom {@code double} value between zero
564		*         (inclusive) and the bound (exclusive).
565	<	* @throws IllegalArgumentException if {@code bound} is not positive
565	>	* @throws IllegalArgumentException if {@code bound} is less than zero
566		*/
567		public double nextDouble(double bound) {
568	<	if (bound <= 0.0)
568	>	if (!(bound > 0.0))
569		throw new IllegalArgumentException("bound must be positive");
570		double result = nextDouble() * bound;
571		return (result < bound) ?  result : // correct for rounding
#	Line 564 | Line 573 | public class SplittableRandom {
573		}
574
575		/**
576	<	* Returns a pseudorandom {@code double} value between the given
576	>	* Returns a pseudorandom {@code double} value between the specified
577		* origin (inclusive) and bound (exclusive).
578		*
579		* @param origin the least value returned
#	Line 575 | Line 584 | public class SplittableRandom {
584		*         or equal to {@code bound}
585		*/
586		public double nextDouble(double origin, double bound) {
587	<	if (origin >= bound)
587	>	if (!(origin < bound))
588		throw new IllegalArgumentException("bound must be greater than origin");
589		return internalNextDouble(origin, bound);
590		}
#	Line 584 | Line 593 | public class SplittableRandom {
593		// maintenance purposes the small differences across forms.
594
595		/**
596	<	* Returns a stream with the given {@code streamSize} number of
596	>	* Returns a stream producing the given {@code streamSize} number of
597		* pseudorandom {@code int} values.
598		*
599		* @param streamSize the number of values to generate
600		* @return a stream of pseudorandom {@code int} values
601		* @throws IllegalArgumentException if {@code streamSize} is
602	<	* less than zero
602	>	*         less than zero
603		*/
604		public IntStream ints(long streamSize) {
605		if (streamSize < 0L)
#	Line 618 | Line 627 | public class SplittableRandom {
627		}
628
629		/**
630	<	* Returns a stream with the given {@code streamSize} number of
630	>	* Returns a stream producing the given {@code streamSize} number of
631		* pseudorandom {@code int} values, each conforming to the given
632		* origin and bound.
633		*
#	Line 626 | Line 635 | public class SplittableRandom {
635		* @param randomNumberOrigin the origin of each random value
636		* @param randomNumberBound the bound of each random value
637		* @return a stream of pseudorandom {@code int} values,
638	<	* each with the given origin and bound.
638	>	*         each with the given origin and bound.
639		* @throws IllegalArgumentException if {@code streamSize} is
640	<	* less than zero.
632	<	* @throws IllegalArgumentException if {@code randomNumberOrigin}
640	>	*         less than zero, or {@code randomNumberOrigin}
641		*         is greater than or equal to {@code randomNumberBound}
642		*/
643		public IntStream ints(long streamSize, int randomNumberOrigin,
#	Line 654 | Line 662 | public class SplittableRandom {
662		* @param randomNumberOrigin the origin of each random value
663		* @param randomNumberBound the bound of each random value
664		* @return a stream of pseudorandom {@code int} values,
665	<	* each with the given origin and bound.
665	>	*         each with the given origin and bound.
666		* @throws IllegalArgumentException if {@code randomNumberOrigin}
667		*         is greater than or equal to {@code randomNumberBound}
668		*/
#	Line 668 | Line 676 | public class SplittableRandom {
676		}
677
678		/**
679	<	* Returns a stream with the given {@code streamSize} number of
679	>	* Returns a stream producing the given {@code streamSize} number of
680		* pseudorandom {@code long} values.
681		*
682		* @param streamSize the number of values to generate
683	<	* @return a stream of {@code long} values
683	>	* @return a stream of pseudorandom {@code long} values
684		* @throws IllegalArgumentException if {@code streamSize} is
685	<	* less than zero
685	>	*         less than zero
686		*/
687		public LongStream longs(long streamSize) {
688		if (streamSize < 0L)
#	Line 702 | Line 710 | public class SplittableRandom {
710		}
711
712		/**
713	<	* Returns a stream with the given {@code streamSize} number of
713	>	* Returns a stream producing the given {@code streamSize} number of
714		* pseudorandom {@code long} values, each conforming to the
715		* given origin and bound.
716		*
#	Line 710 | Line 718 | public class SplittableRandom {
718		* @param randomNumberOrigin the origin of each random value
719		* @param randomNumberBound the bound of each random value
720		* @return a stream of pseudorandom {@code long} values,
721	<	* each with the given origin and bound.
721	>	*         each with the given origin and bound.
722		* @throws IllegalArgumentException if {@code streamSize} is
723	<	* less than zero.
716	<	* @throws IllegalArgumentException if {@code randomNumberOrigin}
723	>	*         less than zero, or {@code randomNumberOrigin}
724		*         is greater than or equal to {@code randomNumberBound}
725		*/
726		public LongStream longs(long streamSize, long randomNumberOrigin,
#	Line 738 | Line 745 | public class SplittableRandom {
745		* @param randomNumberOrigin the origin of each random value
746		* @param randomNumberBound the bound of each random value
747		* @return a stream of pseudorandom {@code long} values,
748	<	* each with the given origin and bound.
748	>	*         each with the given origin and bound.
749		* @throws IllegalArgumentException if {@code randomNumberOrigin}
750		*         is greater than or equal to {@code randomNumberBound}
751		*/
#	Line 752 | Line 759 | public class SplittableRandom {
759		}
760
761		/**
762	<	* Returns a stream with the given {@code streamSize} number of
763	<	* pseudorandom {@code double} values, each between {@code 0.0}
764	<	* (inclusive) and {@code 1.0} (exclusive).
762	>	* Returns a stream producing the given {@code streamSize} number of
763	>	* pseudorandom {@code double} values, each between zero
764	>	* (inclusive) and one (exclusive).
765		*
766		* @param streamSize the number of values to generate
767		* @return a stream of {@code double} values
768		* @throws IllegalArgumentException if {@code streamSize} is
769	<	* less than zero
769	>	*         less than zero
770		*/
771		public DoubleStream doubles(long streamSize) {
772		if (streamSize < 0L)
#	Line 772 | Line 779 | public class SplittableRandom {
779
780		/**
781		* Returns an effectively unlimited stream of pseudorandom {@code
782	<	* double} values, each between {@code 0.0} (inclusive) and {@code
783	<	* 1.0} (exclusive).
782	>	* double} values, each between zero (inclusive) and one
783	>	* (exclusive).
784		*
785		* @implNote This method is implemented to be equivalent to {@code
786		* doubles(Long.MAX_VALUE)}.
#	Line 788 | Line 795 | public class SplittableRandom {
795		}
796
797		/**
798	<	* Returns a stream with the given {@code streamSize} number of
798	>	* Returns a stream producing the given {@code streamSize} number of
799		* pseudorandom {@code double} values, each conforming to the
800		* given origin and bound.
801		*
#	Line 806 | Line 813 | public class SplittableRandom {
813		double randomNumberBound) {
814		if (streamSize < 0L)
815		throw new IllegalArgumentException("negative Stream size");
816	<	if (randomNumberOrigin >= randomNumberBound)
816	>	if (!(randomNumberOrigin < randomNumberBound))
817		throw new IllegalArgumentException("bound must be greater than origin");
818		return StreamSupport.doubleStream
819		(new RandomDoublesSpliterator
#	Line 829 | Line 836 | public class SplittableRandom {
836		*         is greater than or equal to {@code randomNumberBound}
837		*/
838		public DoubleStream doubles(double randomNumberOrigin, double randomNumberBound) {
839	<	if (randomNumberOrigin >= randomNumberBound)
839	>	if (!(randomNumberOrigin < randomNumberBound))
840		throw new IllegalArgumentException("bound must be greater than origin");
841		return StreamSupport.doubleStream
842		(new RandomDoublesSpliterator
#	Line 839 | Line 846 | public class SplittableRandom {
846
847		/**
848		* Spliterator for int streams.  We multiplex the four int
849	<	* versions into one class by treating and bound < origin as
849	>	* versions into one class by treating a bound less than origin as
850		* unbounded, and also by treating "infinite" as equivalent to
851		* Long.MAX_VALUE. For splits, it uses the standard divide-by-two
852		* approach. The long and double versions of this class are
#	Line 869 | Line 876 | public class SplittableRandom {
876
877		public int characteristics() {
878		return (Spliterator.SIZED | Spliterator.SUBSIZED |
879	<	Spliterator.ORDERED | Spliterator.NONNULL |
873	<	Spliterator.IMMUTABLE);
879	>	Spliterator.NONNULL | Spliterator.IMMUTABLE);
880		}
881
882		public boolean tryAdvance(IntConsumer consumer) {
#	Line 924 | Line 930 | public class SplittableRandom {
930
931		public int characteristics() {
932		return (Spliterator.SIZED | Spliterator.SUBSIZED |
933	<	Spliterator.ORDERED | Spliterator.NONNULL |
928	<	Spliterator.IMMUTABLE);
933	>	Spliterator.NONNULL | Spliterator.IMMUTABLE);
934		}
935
936		public boolean tryAdvance(LongConsumer consumer) {
#	Line 980 | Line 985 | public class SplittableRandom {
985
986		public int characteristics() {
987		return (Spliterator.SIZED | Spliterator.SUBSIZED |
988	<	Spliterator.ORDERED | Spliterator.NONNULL |
984	<	Spliterator.IMMUTABLE);
988	>	Spliterator.NONNULL | Spliterator.IMMUTABLE);
989		}
990
991		public boolean tryAdvance(DoubleConsumer consumer) {

Diff Legend

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