--- jsr166/src/main/java/util/SplittableRandom.java 2013/07/11 23:22:01 1.6 +++ jsr166/src/main/java/util/SplittableRandom.java 2013/07/12 11:26:34 1.7 @@ -35,7 +35,6 @@ import java.util.stream.IntStream; import java.util.stream.LongStream; import java.util.stream.DoubleStream; - /** * A generator of uniform pseudorandom values applicable for use in * (among other contexts) isolated parallel computations that may @@ -54,8 +53,8 @@ import java.util.stream.DoubleStream; * *
  • Method {@link #split} constructs and returns a new * SplittableRandom instance that shares no mutable state with the - * current instance. However, with very high probability, the set of - * values collectively generated by the two objects has the same + * current instance. However, with very high probability, the + * values collectively generated by the two objects have the same * statistical properties as if the same quantity of values were * generated by a single thread using a single {@code * SplittableRandom} object.
    • @@ -97,11 +96,12 @@ public class SplittableRandom { * Random-Number Generation for Dynamic-Multithreading Platforms", * PPoPP 2012, but improves and extends it in several ways. * - * The primary update step is simply to add a constant ("gamma") - * to the current seed, modulo a prime ("George"). However, the - * nextLong and nextInt methods do not return this value, but - * instead the results of bit-mixing transformations that produce - * more uniformly distributed sequences. + * The primary update step (see method nextSeed()) is simply to + * add a constant ("gamma") to the current seed, modulo a prime + * ("George"). However, the nextLong and nextInt methods do not + * return this value, but instead the results of bit-mixing + * transformations that produce more uniformly distributed + * sequences. * * "George" is the otherwise nameless (because it cannot be * represented) prime number 2^64+13. Using a prime number larger @@ -179,7 +179,7 @@ public class SplittableRandom { /** * The least non-zero value returned by nextDouble(). This value - * is scaled by a random value of 52 bits to produce a result. + * is scaled by a random value of 53 bits to produce a result. */ private static final double DOUBLE_UNIT = 1.0 / (1L << 53); @@ -206,23 +206,6 @@ public class SplittableRandom { private final long nextSplit; /** - * Internal constructor used by all other constructors and by - * method split. Establishes the initial seed for this instance, - * and uses the given splitSeed to establish gamma, as well as the - * nextSplit to use by this instance. - */ - private SplittableRandom(long seed, long splitSeed) { - this.seed = seed; - long s = splitSeed, g; - do { // ensure gamma >= 13, considered as an unsigned integer - s = addGammaModGeorge(s, GAMMA_GAMMA); - g = mix64(s); - } while (Long.compareUnsigned(g, 13L) < 0); - this.gamma = g; - this.nextSplit = s; - } - - /** * Adds the given gamma value, g, to the given seed value s, mod * George (2^64+13). We regard s and g as unsigned values * (ranging from 0 to 2^64-1). We add g to s either once or twice @@ -244,14 +227,6 @@ public class SplittableRandom { } /** - * Updates in-place and returns seed. - * See above for explanation. - */ - private long nextSeed() { - return seed = addGammaModGeorge(seed, gamma); - } - - /** * Returns a bit-mixed transformation of its argument. * See above for explanation. */ @@ -275,7 +250,33 @@ public class SplittableRandom { } /** - * Atomically updates and returns next seed for default constructor + * Internal constructor used by all other constructors and by + * method split. Establishes the initial seed for this instance, + * and uses the given splitSeed to establish gamma, as well as the + * nextSplit to use by this instance. The loop to skip ineligible + * gammas very rarely iterates, and does so at most 13 times. + */ + private SplittableRandom(long seed, long splitSeed) { + this.seed = seed; + long s = splitSeed, g; + do { // ensure gamma >= 13, considered as an unsigned integer + s = addGammaModGeorge(s, GAMMA_GAMMA); + g = mix64(s); + } while (Long.compareUnsigned(g, 13L) < 0); + this.gamma = g; + this.nextSplit = s; + } + + /** + * Updates in-place and returns seed. + * See above for explanation. + */ + private long nextSeed() { + return seed = addGammaModGeorge(seed, gamma); + } + + /** + * Atomically updates and returns next seed for default constructor. */ private static long nextDefaultSeed() { long oldSeed, newSeed; @@ -332,16 +333,16 @@ public class SplittableRandom { long r = mix64(nextSeed()); if (origin < bound) { long n = bound - origin, m = n - 1; - if ((n & m) == 0L) // power of two + if ((n & m) == 0L) // power of two r = (r & m) + origin; - else if (n > 0) { // reject over-represented candidates + else if (n > 0L) { // reject over-represented candidates for (long u = r >>> 1; // ensure nonnegative - u + m - (r = u % n) < 0L; // reject + u + m - (r = u % n) < 0L; // rejection check u = mix64(nextSeed()) >>> 1) // retry ; r += origin; } - else { // range not representable as long + else { // range not representable as long while (r < origin || r >= bound) r = mix64(nextSeed()); } @@ -365,7 +366,7 @@ public class SplittableRandom { r = (r & m) + origin; else if (n > 0) { for (int u = r >>> 1; - u + m - (r = u % n) < 0L; + u + m - (r = u % n) < 0; u = mix32(nextSeed()) >>> 1) ; r += origin; @@ -389,7 +390,7 @@ public class SplittableRandom { double r = (nextLong() >>> 11) * DOUBLE_UNIT; if (origin < bound) { r = r * (bound - origin) + origin; - if (r == bound) // correct for rounding + if (r >= bound) // correct for rounding r = Double.longBitsToDouble(Double.doubleToLongBits(bound) - 1); } return r; @@ -398,9 +399,9 @@ public class SplittableRandom { /* ---------------- public methods ---------------- */ /** - * Creates a new SplittableRandom instance using the given initial - * seed. Two SplittableRandom instances created with the same seed - * generate identical sequences of values. + * Creates a new SplittableRandom instance using the specified + * initial seed. SplittableRandom instances created with the same + * seed generate identical sequences of values. * * @param seed the initial seed */ @@ -439,21 +440,21 @@ public class SplittableRandom { /** * Returns a pseudorandom {@code int} value. * - * @return a pseudorandom value + * @return a pseudorandom {@code int} value */ public int nextInt() { return mix32(nextSeed()); } /** - * Returns a pseudorandom {@code int} value between 0 (inclusive) + * Returns a pseudorandom {@code int} value between zero (inclusive) * and the specified bound (exclusive). * * @param bound the bound on the random number to be returned. Must be * positive. - * @return a pseudorandom {@code int} value between {@code 0} + * @return a pseudorandom {@code int} value between zero * (inclusive) and the bound (exclusive). - * @exception IllegalArgumentException if the bound is not positive + * @throws IllegalArgumentException if the bound is less than zero */ public int nextInt(int bound) { if (bound <= 0) @@ -465,7 +466,7 @@ public class SplittableRandom { r &= m; else { // reject over-represented candidates for (int u = r >>> 1; - u + m - (r = u % bound) < 0L; + u + m - (r = u % bound) < 0; u = mix32(nextSeed()) >>> 1) ; } @@ -480,7 +481,7 @@ public class SplittableRandom { * @param bound the upper bound (exclusive) * @return a pseudorandom {@code int} value between the origin * (inclusive) and the bound (exclusive). - * @exception IllegalArgumentException if {@code origin} is greater than + * @throws IllegalArgumentException if {@code origin} is greater than * or equal to {@code bound} */ public int nextInt(int origin, int bound) { @@ -492,21 +493,21 @@ public class SplittableRandom { /** * Returns a pseudorandom {@code long} value. * - * @return a pseudorandom value + * @return a pseudorandom {@code long} value */ public long nextLong() { return mix64(nextSeed()); } /** - * Returns a pseudorandom {@code long} value between 0 (inclusive) + * Returns a pseudorandom {@code long} value between zero (inclusive) * and the specified bound (exclusive). * * @param bound the bound on the random number to be returned. Must be * positive. - * @return a pseudorandom {@code long} value between {@code 0} + * @return a pseudorandom {@code long} value between zero * (inclusive) and the bound (exclusive). - * @exception IllegalArgumentException if the bound is not positive + * @throws IllegalArgumentException if {@code bound} is less than zero */ public long nextLong(long bound) { if (bound <= 0) @@ -533,7 +534,7 @@ public class SplittableRandom { * @param bound the upper bound (exclusive) * @return a pseudorandom {@code long} value between the origin * (inclusive) and the bound (exclusive). - * @exception IllegalArgumentException if {@code origin} is greater than + * @throws IllegalArgumentException if {@code origin} is greater than * or equal to {@code bound} */ public long nextLong(long origin, long bound) { @@ -543,11 +544,11 @@ public class SplittableRandom { } /** - * Returns a pseudorandom {@code double} value between {@code 0.0} - * (inclusive) and {@code 1.0} (exclusive). + * Returns a pseudorandom {@code double} value between zero + * (inclusive) and one (exclusive). * - * @return a pseudorandom value between {@code 0.0} - * (inclusive) and {@code 1.0} (exclusive) + * @return a pseudorandom {@code double} value between zero + * (inclusive) and one (exclusive) */ public double nextDouble() { return (nextLong() >>> 11) * DOUBLE_UNIT; @@ -559,12 +560,12 @@ public class SplittableRandom { * * @param bound the bound on the random number to be returned. Must be * positive. - * @return a pseudorandom {@code double} value between {@code 0.0} + * @return a pseudorandom {@code double} value between zero * (inclusive) and the bound (exclusive). - * @throws IllegalArgumentException if {@code bound} is not positive + * @throws IllegalArgumentException if {@code bound} is less than zero */ public double nextDouble(double bound) { - if (bound <= 0.0) + if (!(bound > 0.0)) throw new IllegalArgumentException("bound must be positive"); double result = nextDouble() * bound; return (result < bound) ? result : // correct for rounding @@ -572,7 +573,7 @@ public class SplittableRandom { } /** - * Returns a pseudorandom {@code double} value between the given + * Returns a pseudorandom {@code double} value between the specified * origin (inclusive) and bound (exclusive). * * @param origin the least value returned @@ -583,7 +584,7 @@ public class SplittableRandom { * or equal to {@code bound} */ public double nextDouble(double origin, double bound) { - if (origin >= bound) + if (!(origin < bound)) throw new IllegalArgumentException("bound must be greater than origin"); return internalNextDouble(origin, bound); } @@ -592,13 +593,13 @@ public class SplittableRandom { // maintenance purposes the small differences across forms. /** - * Returns a stream with the given {@code streamSize} number of + * Returns a stream producing the given {@code streamSize} number of * pseudorandom {@code int} values. * * @param streamSize the number of values to generate * @return a stream of pseudorandom {@code int} values * @throws IllegalArgumentException if {@code streamSize} is - * less than zero + * less than zero */ public IntStream ints(long streamSize) { if (streamSize < 0L) @@ -626,7 +627,7 @@ public class SplittableRandom { } /** - * Returns a stream with the given {@code streamSize} number of + * Returns a stream producing the given {@code streamSize} number of * pseudorandom {@code int} values, each conforming to the given * origin and bound. * @@ -634,10 +635,9 @@ public class SplittableRandom { * @param randomNumberOrigin the origin of each random value * @param randomNumberBound the bound of each random value * @return a stream of pseudorandom {@code int} values, - * each with the given origin and bound. + * each with the given origin and bound. * @throws IllegalArgumentException if {@code streamSize} is - * less than zero. - * @throws IllegalArgumentException if {@code randomNumberOrigin} + * less than zero, or {@code randomNumberOrigin} * is greater than or equal to {@code randomNumberBound} */ public IntStream ints(long streamSize, int randomNumberOrigin, @@ -662,7 +662,7 @@ public class SplittableRandom { * @param randomNumberOrigin the origin of each random value * @param randomNumberBound the bound of each random value * @return a stream of pseudorandom {@code int} values, - * each with the given origin and bound. + * each with the given origin and bound. * @throws IllegalArgumentException if {@code randomNumberOrigin} * is greater than or equal to {@code randomNumberBound} */ @@ -676,13 +676,13 @@ public class SplittableRandom { } /** - * Returns a stream with the given {@code streamSize} number of + * Returns a stream producing the given {@code streamSize} number of * pseudorandom {@code long} values. * * @param streamSize the number of values to generate - * @return a stream of {@code long} values + * @return a stream of pseudorandom {@code long} values * @throws IllegalArgumentException if {@code streamSize} is - * less than zero + * less than zero */ public LongStream longs(long streamSize) { if (streamSize < 0L) @@ -710,7 +710,7 @@ public class SplittableRandom { } /** - * Returns a stream with the given {@code streamSize} number of + * Returns a stream producing the given {@code streamSize} number of * pseudorandom {@code long} values, each conforming to the * given origin and bound. * @@ -718,10 +718,9 @@ public class SplittableRandom { * @param randomNumberOrigin the origin of each random value * @param randomNumberBound the bound of each random value * @return a stream of pseudorandom {@code long} values, - * each with the given origin and bound. + * each with the given origin and bound. * @throws IllegalArgumentException if {@code streamSize} is - * less than zero. - * @throws IllegalArgumentException if {@code randomNumberOrigin} + * less than zero, or {@code randomNumberOrigin} * is greater than or equal to {@code randomNumberBound} */ public LongStream longs(long streamSize, long randomNumberOrigin, @@ -746,7 +745,7 @@ public class SplittableRandom { * @param randomNumberOrigin the origin of each random value * @param randomNumberBound the bound of each random value * @return a stream of pseudorandom {@code long} values, - * each with the given origin and bound. + * each with the given origin and bound. * @throws IllegalArgumentException if {@code randomNumberOrigin} * is greater than or equal to {@code randomNumberBound} */ @@ -760,14 +759,14 @@ public class SplittableRandom { } /** - * Returns a stream with the given {@code streamSize} number of - * pseudorandom {@code double} values, each between {@code 0.0} - * (inclusive) and {@code 1.0} (exclusive). + * Returns a stream producing the given {@code streamSize} number of + * pseudorandom {@code double} values, each between zero + * (inclusive) and one (exclusive). * * @param streamSize the number of values to generate * @return a stream of {@code double} values * @throws IllegalArgumentException if {@code streamSize} is - * less than zero + * less than zero */ public DoubleStream doubles(long streamSize) { if (streamSize < 0L) @@ -780,8 +779,8 @@ public class SplittableRandom { /** * Returns an effectively unlimited stream of pseudorandom {@code - * double} values, each between {@code 0.0} (inclusive) and {@code - * 1.0} (exclusive). + * double} values, each between zero (inclusive) and one + * (exclusive). * * @implNote This method is implemented to be equivalent to {@code * doubles(Long.MAX_VALUE)}. @@ -796,7 +795,7 @@ public class SplittableRandom { } /** - * Returns a stream with the given {@code streamSize} number of + * Returns a stream producing the given {@code streamSize} number of * pseudorandom {@code double} values, each conforming to the * given origin and bound. * @@ -814,7 +813,7 @@ public class SplittableRandom { double randomNumberBound) { if (streamSize < 0L) throw new IllegalArgumentException("negative Stream size"); - if (randomNumberOrigin >= randomNumberBound) + if (!(randomNumberOrigin < randomNumberBound)) throw new IllegalArgumentException("bound must be greater than origin"); return StreamSupport.doubleStream (new RandomDoublesSpliterator @@ -837,7 +836,7 @@ public class SplittableRandom { * is greater than or equal to {@code randomNumberBound} */ public DoubleStream doubles(double randomNumberOrigin, double randomNumberBound) { - if (randomNumberOrigin >= randomNumberBound) + if (!(randomNumberOrigin < randomNumberBound)) throw new IllegalArgumentException("bound must be greater than origin"); return StreamSupport.doubleStream (new RandomDoublesSpliterator @@ -847,7 +846,7 @@ public class SplittableRandom { /** * Spliterator for int streams. We multiplex the four int - * versions into one class by treating and bound < origin as + * versions into one class by treating a bound less than origin as * unbounded, and also by treating "infinite" as equivalent to * Long.MAX_VALUE. For splits, it uses the standard divide-by-two * approach. The long and double versions of this class are