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.6 by dl, Thu Jul 11 23:22:01 2013 UTC vs.
Revision 1.9 by jsr166, Sun Jul 14 03:47:31 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
41		* generate subtasks. Class SplittableRandom supports methods for
42		* producing pseudorandom numbers of type {@code int}, {@code long},
43		* and {@code double} with similar usages as for class
44	<	* {@link java.util.Random} but differs in the following ways: <ul>
44	>	* {@link java.util.Random} but differs in the following ways:
45	>	*
46	>	* <ul>
47		*
48		* <li>Series of generated values pass the DieHarder suite testing
49		* independence and uniformity properties of random number generators.
#	Line 54 | Line 55 | import java.util.stream.DoubleStream;
55		*
56		* <li> Method {@link #split} constructs and returns a new
57		* SplittableRandom instance that shares no mutable state with the
58	<	* current instance. However, with very high probability, the set of
59	<	* values collectively generated by the two objects has the same
58	>	* current instance. However, with very high probability, the
59	>	* values collectively generated by the two objects have the same
60		* statistical properties as if the same quantity of values were
61		* generated by a single thread using a single {@code
62		* SplittableRandom} object.  </li>
#	Line 97 | Line 98 | public class SplittableRandom {
98		* Random-Number Generation for Dynamic-Multithreading Platforms",
99		* PPoPP 2012, but improves and extends it in several ways.
100		*
101	<	* The primary update step is simply to add a constant ("gamma")
102	<	* to the current seed, modulo a prime ("George"). However, the
103	<	* nextLong and nextInt methods do not return this value, but
104	<	* instead the results of bit-mixing transformations that produce
105	<	* more uniformly distributed sequences.
101	>	* The primary update step (see method nextSeed()) is simply to
102	>	* add a constant ("gamma") to the current seed, modulo a prime
103	>	* ("George"). However, the nextLong and nextInt methods do not
104	>	* return this value, but instead the results of bit-mixing
105	>	* transformations that produce more uniformly distributed
106	>	* sequences.
107		*
108		* "George" is the otherwise nameless (because it cannot be
109		* represented) prime number 2^64+13. Using a prime number larger
#	Line 179 | Line 181 | public class SplittableRandom {
181
182		/**
183		* The least non-zero value returned by nextDouble(). This value
184	<	* is scaled by a random value of 52 bits to produce a result.
184	>	* is scaled by a random value of 53 bits to produce a result.
185		*/
186		private static final double DOUBLE_UNIT = 1.0 / (1L << 53);
187
#	Line 206 | Line 208 | public class SplittableRandom {
208		private final long nextSplit;
209
210		/**
209	–	* Internal constructor used by all other constructors and by
210	–	* method split. Establishes the initial seed for this instance,
211	–	* and uses the given splitSeed to establish gamma, as well as the
212	–	* nextSplit to use by this instance.
213	–	*/
214	–	private SplittableRandom(long seed, long splitSeed) {
215	–	this.seed = seed;
216	–	long s = splitSeed, g;
217	–	do { // ensure gamma >= 13, considered as an unsigned integer
218	–	s = addGammaModGeorge(s, GAMMA_GAMMA);
219	–	g = mix64(s);
220	–	} while (Long.compareUnsigned(g, 13L) < 0);
221	–	this.gamma = g;
222	–	this.nextSplit = s;
223	–	}
224	–
225	–	/**
211		* Adds the given gamma value, g, to the given seed value s, mod
212		* George (2^64+13). We regard s and g as unsigned values
213		* (ranging from 0 to 2^64-1). We add g to s either once or twice
#	Line 244 | Line 229 | public class SplittableRandom {
229		}
230
231		/**
247	–	* Updates in-place and returns seed.
248	–	* See above for explanation.
249	–	*/
250	–	private long nextSeed() {
251	–	return seed = addGammaModGeorge(seed, gamma);
252	–	}
253	–
254	–	/**
232		* Returns a bit-mixed transformation of its argument.
233		* See above for explanation.
234		*/
#	Line 275 | Line 252 | public class SplittableRandom {
252		}
253
254		/**
255	<	* Atomically updates and returns next seed for default constructor
255	>	* Internal constructor used by all other constructors and by
256	>	* method split. Establishes the initial seed for this instance,
257	>	* and uses the given splitSeed to establish gamma, as well as the
258	>	* nextSplit to use by this instance. The loop to skip ineligible
259	>	* gammas very rarely iterates, and does so at most 13 times.
260	>	*/
261	>	private SplittableRandom(long seed, long splitSeed) {
262	>	this.seed = seed;
263	>	long s = splitSeed, g;
264	>	do { // ensure gamma >= 13, considered as an unsigned integer
265	>	s = addGammaModGeorge(s, GAMMA_GAMMA);
266	>	g = mix64(s);
267	>	} while (Long.compareUnsigned(g, 13L) < 0);
268	>	this.gamma = g;
269	>	this.nextSplit = s;
270	>	}
271	>
272	>	/**
273	>	* Updates in-place and returns seed.
274	>	* See above for explanation.
275	>	*/
276	>	private long nextSeed() {
277	>	return seed = addGammaModGeorge(seed, gamma);
278	>	}
279	>
280	>	/**
281	>	* Atomically updates and returns next seed for default constructor.
282		*/
283		private static long nextDefaultSeed() {
284		long oldSeed, newSeed;
#	Line 332 | Line 335 | public class SplittableRandom {
335		long r = mix64(nextSeed());
336		if (origin < bound) {
337		long n = bound - origin, m = n - 1;
338	<	if ((n & m) == 0L) // power of two
338	>	if ((n & m) == 0L)  // power of two
339		r = (r & m) + origin;
340	<	else if (n > 0) { // reject over-represented candidates
340	>	else if (n > 0L) {  // reject over-represented candidates
341		for (long u = r >>> 1;            // ensure nonnegative
342	<	u + m - (r = u % n) < 0L;    // reject
342	>	u + m - (r = u % n) < 0L;    // rejection check
343		u = mix64(nextSeed()) >>> 1) // retry
344		;
345		r += origin;
346		}
347	<	else {             // range not representable as long
347	>	else {              // range not representable as long
348		while (r < origin || r >= bound)
349		r = mix64(nextSeed());
350		}
#	Line 365 | Line 368 | public class SplittableRandom {
368		r = (r & m) + origin;
369		else if (n > 0) {
370		for (int u = r >>> 1;
371	<	u + m - (r = u % n) < 0L;
371	>	u + m - (r = u % n) < 0;
372		u = mix32(nextSeed()) >>> 1)
373		;
374		r += origin;
#	Line 389 | Line 392 | public class SplittableRandom {
392		double r = (nextLong() >>> 11) * DOUBLE_UNIT;
393		if (origin < bound) {
394		r = r * (bound - origin) + origin;
395	<	if (r == bound) // correct for rounding
395	>	if (r >= bound) // correct for rounding
396		r = Double.longBitsToDouble(Double.doubleToLongBits(bound) - 1);
397		}
398		return r;
#	Line 398 | Line 401 | public class SplittableRandom {
401		/* ---------------- public methods ---------------- */
402
403		/**
404	<	* Creates a new SplittableRandom instance using the given initial
405	<	* seed. Two SplittableRandom instances created with the same seed
406	<	* generate identical sequences of values.
404	>	* Creates a new SplittableRandom instance using the specified
405	>	* initial seed. SplittableRandom instances created with the same
406	>	* seed generate identical sequences of values.
407		*
408		* @param seed the initial seed
409		*/
#	Line 439 | Line 442 | public class SplittableRandom {
442		/**
443		* Returns a pseudorandom {@code int} value.
444		*
445	<	* @return a pseudorandom value
445	>	* @return a pseudorandom {@code int} value
446		*/
447		public int nextInt() {
448		return mix32(nextSeed());
449		}
450
451		/**
452	<	* Returns a pseudorandom {@code int} value between 0 (inclusive)
452	>	* Returns a pseudorandom {@code int} value between zero (inclusive)
453		* and the specified bound (exclusive).
454		*
455		* @param bound the bound on the random number to be returned.  Must be
456		*        positive.
457	<	* @return a pseudorandom {@code int} value between {@code 0}
457	>	* @return a pseudorandom {@code int} value between zero
458		*         (inclusive) and the bound (exclusive).
459	<	* @exception IllegalArgumentException if the bound is not positive
459	>	* @throws IllegalArgumentException if the bound is less than zero
460		*/
461		public int nextInt(int bound) {
462		if (bound <= 0)
#	Line 465 | Line 468 | public class SplittableRandom {
468		r &= m;
469		else { // reject over-represented candidates
470		for (int u = r >>> 1;
471	<	u + m - (r = u % bound) < 0L;
471	>	u + m - (r = u % bound) < 0;
472		u = mix32(nextSeed()) >>> 1)
473		;
474		}
#	Line 480 | Line 483 | public class SplittableRandom {
483		* @param bound the upper bound (exclusive)
484		* @return a pseudorandom {@code int} value between the origin
485		*         (inclusive) and the bound (exclusive).
486	<	* @exception IllegalArgumentException if {@code origin} is greater than
486	>	* @throws IllegalArgumentException if {@code origin} is greater than
487		*         or equal to {@code bound}
488		*/
489		public int nextInt(int origin, int bound) {
#	Line 492 | Line 495 | public class SplittableRandom {
495		/**
496		* Returns a pseudorandom {@code long} value.
497		*
498	<	* @return a pseudorandom value
498	>	* @return a pseudorandom {@code long} value
499		*/
500		public long nextLong() {
501		return mix64(nextSeed());
502		}
503
504		/**
505	<	* Returns a pseudorandom {@code long} value between 0 (inclusive)
505	>	* Returns a pseudorandom {@code long} value between zero (inclusive)
506		* and the specified bound (exclusive).
507		*
508		* @param bound the bound on the random number to be returned.  Must be
509		*        positive.
510	<	* @return a pseudorandom {@code long} value between {@code 0}
510	>	* @return a pseudorandom {@code long} value between zero
511		*         (inclusive) and the bound (exclusive).
512	<	* @exception IllegalArgumentException if the bound is not positive
512	>	* @throws IllegalArgumentException if {@code bound} is less than zero
513		*/
514		public long nextLong(long bound) {
515		if (bound <= 0)
#	Line 533 | Line 536 | public class SplittableRandom {
536		* @param bound the upper bound (exclusive)
537		* @return a pseudorandom {@code long} value between the origin
538		*         (inclusive) and the bound (exclusive).
539	<	* @exception IllegalArgumentException if {@code origin} is greater than
539	>	* @throws IllegalArgumentException if {@code origin} is greater than
540		*         or equal to {@code bound}
541		*/
542		public long nextLong(long origin, long bound) {
#	Line 543 | Line 546 | public class SplittableRandom {
546		}
547
548		/**
549	<	* Returns a pseudorandom {@code double} value between {@code 0.0}
550	<	* (inclusive) and {@code 1.0} (exclusive).
549	>	* Returns a pseudorandom {@code double} value between zero
550	>	* (inclusive) and one (exclusive).
551		*
552	<	* @return a pseudorandom value between {@code 0.0}
553	<	* (inclusive) and {@code 1.0} (exclusive)
552	>	* @return a pseudorandom {@code double} value between zero
553	>	* (inclusive) and one (exclusive)
554		*/
555		public double nextDouble() {
556		return (nextLong() >>> 11) * DOUBLE_UNIT;
#	Line 559 | Line 562 | public class SplittableRandom {
562		*
563		* @param bound the bound on the random number to be returned.  Must be
564		*        positive.
565	<	* @return a pseudorandom {@code double} value between {@code 0.0}
565	>	* @return a pseudorandom {@code double} value between zero
566		*         (inclusive) and the bound (exclusive).
567	<	* @throws IllegalArgumentException if {@code bound} is not positive
567	>	* @throws IllegalArgumentException if {@code bound} is less than zero
568		*/
569		public double nextDouble(double bound) {
570	<	if (bound <= 0.0)
570	>	if (!(bound > 0.0))
571		throw new IllegalArgumentException("bound must be positive");
572		double result = nextDouble() * bound;
573		return (result < bound) ?  result : // correct for rounding
#	Line 572 | Line 575 | public class SplittableRandom {
575		}
576
577		/**
578	<	* Returns a pseudorandom {@code double} value between the given
578	>	* Returns a pseudorandom {@code double} value between the specified
579		* origin (inclusive) and bound (exclusive).
580		*
581		* @param origin the least value returned
#	Line 583 | Line 586 | public class SplittableRandom {
586		*         or equal to {@code bound}
587		*/
588		public double nextDouble(double origin, double bound) {
589	<	if (origin >= bound)
589	>	if (!(origin < bound))
590		throw new IllegalArgumentException("bound must be greater than origin");
591		return internalNextDouble(origin, bound);
592		}
#	Line 592 | Line 595 | public class SplittableRandom {
595		// maintenance purposes the small differences across forms.
596
597		/**
598	<	* Returns a stream with the given {@code streamSize} number of
598	>	* Returns a stream producing the given {@code streamSize} number of
599		* pseudorandom {@code int} values.
600		*
601		* @param streamSize the number of values to generate
602		* @return a stream of pseudorandom {@code int} values
603		* @throws IllegalArgumentException if {@code streamSize} is
604	<	* less than zero
604	>	*         less than zero
605		*/
606		public IntStream ints(long streamSize) {
607		if (streamSize < 0L)
#	Line 626 | Line 629 | public class SplittableRandom {
629		}
630
631		/**
632	<	* Returns a stream with the given {@code streamSize} number of
632	>	* Returns a stream producing the given {@code streamSize} number of
633		* pseudorandom {@code int} values, each conforming to the given
634		* origin and bound.
635		*
#	Line 634 | Line 637 | public class SplittableRandom {
637		* @param randomNumberOrigin the origin of each random value
638		* @param randomNumberBound the bound of each random value
639		* @return a stream of pseudorandom {@code int} values,
640	<	* each with the given origin and bound.
640	>	*         each with the given origin and bound.
641		* @throws IllegalArgumentException if {@code streamSize} is
642	<	* less than zero.
640	<	* @throws IllegalArgumentException if {@code randomNumberOrigin}
642	>	*         less than zero, or {@code randomNumberOrigin}
643		*         is greater than or equal to {@code randomNumberBound}
644		*/
645		public IntStream ints(long streamSize, int randomNumberOrigin,
#	Line 662 | Line 664 | public class SplittableRandom {
664		* @param randomNumberOrigin the origin of each random value
665		* @param randomNumberBound the bound of each random value
666		* @return a stream of pseudorandom {@code int} values,
667	<	* each with the given origin and bound.
667	>	*         each with the given origin and bound.
668		* @throws IllegalArgumentException if {@code randomNumberOrigin}
669		*         is greater than or equal to {@code randomNumberBound}
670		*/
#	Line 676 | Line 678 | public class SplittableRandom {
678		}
679
680		/**
681	<	* Returns a stream with the given {@code streamSize} number of
681	>	* Returns a stream producing the given {@code streamSize} number of
682		* pseudorandom {@code long} values.
683		*
684		* @param streamSize the number of values to generate
685	<	* @return a stream of {@code long} values
685	>	* @return a stream of pseudorandom {@code long} values
686		* @throws IllegalArgumentException if {@code streamSize} is
687	<	* less than zero
687	>	*         less than zero
688		*/
689		public LongStream longs(long streamSize) {
690		if (streamSize < 0L)
#	Line 710 | Line 712 | public class SplittableRandom {
712		}
713
714		/**
715	<	* Returns a stream with the given {@code streamSize} number of
715	>	* Returns a stream producing the given {@code streamSize} number of
716		* pseudorandom {@code long} values, each conforming to the
717		* given origin and bound.
718		*
#	Line 718 | Line 720 | public class SplittableRandom {
720		* @param randomNumberOrigin the origin of each random value
721		* @param randomNumberBound the bound of each random value
722		* @return a stream of pseudorandom {@code long} values,
723	<	* each with the given origin and bound.
723	>	*         each with the given origin and bound.
724		* @throws IllegalArgumentException if {@code streamSize} is
725	<	* less than zero.
724	<	* @throws IllegalArgumentException if {@code randomNumberOrigin}
725	>	*         less than zero, or {@code randomNumberOrigin}
726		*         is greater than or equal to {@code randomNumberBound}
727		*/
728		public LongStream longs(long streamSize, long randomNumberOrigin,
#	Line 746 | Line 747 | public class SplittableRandom {
747		* @param randomNumberOrigin the origin of each random value
748		* @param randomNumberBound the bound of each random value
749		* @return a stream of pseudorandom {@code long} values,
750	<	* each with the given origin and bound.
750	>	*         each with the given origin and bound.
751		* @throws IllegalArgumentException if {@code randomNumberOrigin}
752		*         is greater than or equal to {@code randomNumberBound}
753		*/
#	Line 760 | Line 761 | public class SplittableRandom {
761		}
762
763		/**
764	<	* Returns a stream with the given {@code streamSize} number of
765	<	* pseudorandom {@code double} values, each between {@code 0.0}
766	<	* (inclusive) and {@code 1.0} (exclusive).
764	>	* Returns a stream producing the given {@code streamSize} number of
765	>	* pseudorandom {@code double} values, each between zero
766	>	* (inclusive) and one (exclusive).
767		*
768		* @param streamSize the number of values to generate
769		* @return a stream of {@code double} values
770		* @throws IllegalArgumentException if {@code streamSize} is
771	<	* less than zero
771	>	*         less than zero
772		*/
773		public DoubleStream doubles(long streamSize) {
774		if (streamSize < 0L)
#	Line 780 | Line 781 | public class SplittableRandom {
781
782		/**
783		* Returns an effectively unlimited stream of pseudorandom {@code
784	<	* double} values, each between {@code 0.0} (inclusive) and {@code
785	<	* 1.0} (exclusive).
784	>	* double} values, each between zero (inclusive) and one
785	>	* (exclusive).
786		*
787		* @implNote This method is implemented to be equivalent to {@code
788		* doubles(Long.MAX_VALUE)}.
#	Line 796 | Line 797 | public class SplittableRandom {
797		}
798
799		/**
800	<	* Returns a stream with the given {@code streamSize} number of
800	>	* Returns a stream producing the given {@code streamSize} number of
801		* pseudorandom {@code double} values, each conforming to the
802		* given origin and bound.
803		*
#	Line 814 | Line 815 | public class SplittableRandom {
815		double randomNumberBound) {
816		if (streamSize < 0L)
817		throw new IllegalArgumentException("negative Stream size");
818	<	if (randomNumberOrigin >= randomNumberBound)
818	>	if (!(randomNumberOrigin < randomNumberBound))
819		throw new IllegalArgumentException("bound must be greater than origin");
820		return StreamSupport.doubleStream
821		(new RandomDoublesSpliterator
#	Line 837 | Line 838 | public class SplittableRandom {
838		*         is greater than or equal to {@code randomNumberBound}
839		*/
840		public DoubleStream doubles(double randomNumberOrigin, double randomNumberBound) {
841	<	if (randomNumberOrigin >= randomNumberBound)
841	>	if (!(randomNumberOrigin < randomNumberBound))
842		throw new IllegalArgumentException("bound must be greater than origin");
843		return StreamSupport.doubleStream
844		(new RandomDoublesSpliterator
#	Line 847 | Line 848 | public class SplittableRandom {
848
849		/**
850		* Spliterator for int streams.  We multiplex the four int
851	<	* versions into one class by treating and bound < origin as
851	>	* versions into one class by treating a bound less than origin as
852		* unbounded, and also by treating "infinite" as equivalent to
853		* Long.MAX_VALUE. For splits, it uses the standard divide-by-two
854		* approach. The long and double versions of this class are
#	Line 1014 | Line 1015 | public class SplittableRandom {
1015		}
1016
1017		}
1017	–

Diff Legend

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