--- jsr166/src/main/java/util/SplittableRandom.java	2013/07/11 23:14:45	1.5
+++ jsr166/src/main/java/util/SplittableRandom.java	2013/07/16 12:32:05	1.11
@@ -35,14 +35,15 @@ 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
  * generate subtasks. Class SplittableRandom supports methods for
  * producing pseudorandom numbers of type {@code int}, {@code long},
  * and {@code double} with similar usages as for class
- * {@link java.util.Random} but differs in the following ways: <ul>
+ * {@link java.util.Random} but differs in the following ways:
+ *
+ * <ul>
  *
  * <li>Series of generated values pass the DieHarder suite testing
  * independence and uniformity properties of random number generators.
@@ -50,12 +51,14 @@ import java.util.stream.DoubleStream;
  * href="http://www.phy.duke.edu/~rgb/General/dieharder.php"> version
  * 3.31.1</a>.) These tests validate only the methods for certain
  * types and ranges, but similar properties are expected to hold, at
- * least approximately, for others as well.  </li>
+ * least approximately, for others as well. The <em>period</em>
+ * (length of any series of generated values before it repeats) is at
+ * least 2<sup>64</sup>. </li>
  *
  * <li> 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.  </li>
@@ -97,11 +100,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
@@ -154,13 +158,16 @@ public class SplittableRandom {
      * SplittableRandom. Unlike other cases, this split must be
      * performed in a thread-safe manner. We use
      * AtomicLong.compareAndSet as the (typically) most efficient
-     * mechanism. To bootstrap, we start off using System.nanotime(),
-     * and update using another "genuinely random" constant
-     * DEFAULT_SEED_GAMMA. The default constructor uses GAMMA_GAMMA,
-     * not 0, for its splitSeed argument (addGammaModGeorge(0,
-     * GAMMA_GAMMA) == GAMMA_GAMMA) to reflect that each is split from
-     * this root generator, even though the root is not explicitly
-     * represented as a SplittableRandom.
+     * mechanism. To bootstrap, we start off using a function of the
+     * current System time as seed, and update using another
+     * "genuinely random" constant DEFAULT_SEED_GAMMA. The default
+     * constructor uses GAMMA_GAMMA, not 0, for its splitSeed argument
+     * (addGammaModGeorge(0, GAMMA_GAMMA) == GAMMA_GAMMA) to reflect
+     * that each is split from this root generator, even though the
+     * root is not explicitly represented as a SplittableRandom.  When
+     * establishing the initial seed, we use both
+     * System.currentTimeMillis and System.nanoTime(), to avoid
+     * regularities that may occur if using either alone.
      */
 
     /**
@@ -178,6 +185,12 @@ public class SplittableRandom {
     private static final long DEFAULT_SEED_GAMMA = 0xBD24B73A95FB84D9L;
 
     /**
+     * The value 13 with 64bit sign bit set. Used in the signed
+     * comparison in addGammaModGeorge.
+     */
+    private static final long BOTTOM13 = 0x800000000000000DL;
+
+    /**
      * The least non-zero value returned by nextDouble(). This value
      * is scaled by a random value of 53 bits to produce a result.
      */
@@ -187,7 +200,8 @@ public class SplittableRandom {
      * The next seed for default constructors.
      */
     private static final AtomicLong defaultSeedGenerator =
-        new AtomicLong(System.nanoTime());
+        new AtomicLong(mix64(System.currentTimeMillis()) ^
+                       mix64(System.nanoTime()));
 
     /**
      * The seed, updated only via method nextSeed.
@@ -206,23 +220,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
@@ -232,23 +229,16 @@ public class SplittableRandom {
      * George < 2^64; thus we need only a conditional, not a loop,
      * to be sure of getting a representable value.
      *
-     * @param s a seed value
+     * Because Java comparison operators are signed, we implement this
+     * by conceptually offsetting seed values downwards by 2^63, so
+     * 0..13 is represented as Long.MIN_VALUE..BOTTOM13.
+     *
+     * @param s a seed value, viewed as a signed long
      * @param g a gamma value, 13 <= g (as unsigned)
      */
     private static long addGammaModGeorge(long s, long g) {
         long p = s + g;
-        if (Long.compareUnsigned(p, g) >= 0)
-            return p;
-        long q = p - 13L;
-        return (Long.compareUnsigned(p, 13L) >= 0) ? q : (q + g);
-    }
-
-    /**
-     * Updates in-place and returns seed.
-     * See above for explanation.
-     */
-    private long nextSeed() {
-        return seed = addGammaModGeorge(seed, gamma);
+        return (p >= s) ? p : ((p >= BOTTOM13) ? p  : p + g) - 13L;
     }
 
     /**
@@ -275,7 +265,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 (g >= 0L && g < 13L);
+        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 +348,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 +381,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 +405,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 +414,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 in the same program generate identical sequences of values.
      *
      * @param seed the initial seed
      */
@@ -439,21 +455,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}
-     *         (inclusive) and the bound (exclusive).
-     * @exception IllegalArgumentException if the bound is not positive
+     * @return a pseudorandom {@code int} value between zero
+     *         (inclusive) and the bound (exclusive)
+     * @throws IllegalArgumentException if the bound is less than zero
      */
     public int nextInt(int bound) {
         if (bound <= 0)
@@ -465,7 +481,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)
                 ;
         }
@@ -479,8 +495,8 @@ public class SplittableRandom {
      * @param origin the least value returned
      * @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
+     *         (inclusive) and the bound (exclusive)
+     * @throws IllegalArgumentException if {@code origin} is greater than
      *         or equal to {@code bound}
      */
     public int nextInt(int origin, int bound) {
@@ -492,21 +508,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}
-     *         (inclusive) and the bound (exclusive).
-     * @exception IllegalArgumentException if the bound is not positive
+     * @return a pseudorandom {@code long} value between zero
+     *         (inclusive) and the bound (exclusive)
+     * @throws IllegalArgumentException if {@code bound} is less than zero
      */
     public long nextLong(long bound) {
         if (bound <= 0)
@@ -532,8 +548,8 @@ public class SplittableRandom {
      * @param origin the least value returned
      * @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
+     *         (inclusive) and the bound (exclusive)
+     * @throws IllegalArgumentException if {@code origin} is greater than
      *         or equal to {@code bound}
      */
     public long nextLong(long origin, long bound) {
@@ -543,14 +559,14 @@ 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;
+        return (mix64(nextSeed()) >>> 11) * DOUBLE_UNIT;
     }
 
     /**
@@ -559,46 +575,55 @@ 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}
-     *         (inclusive) and the bound (exclusive).
-     * @throws IllegalArgumentException if {@code bound} is not positive
+     * @return a pseudorandom {@code double} value between zero
+     *         (inclusive) and the bound (exclusive)
+     * @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;
+        double result = (mix64(nextSeed()) >>> 11) * DOUBLE_UNIT * bound;
         return (result < bound) ?  result : // correct for rounding
             Double.longBitsToDouble(Double.doubleToLongBits(bound) - 1);
     }
 
     /**
-     * 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
      * @param bound the upper bound
      * @return a pseudorandom {@code double} value between the origin
-     *         (inclusive) and the bound (exclusive).
+     *         (inclusive) and the bound (exclusive)
      * @throws IllegalArgumentException if {@code origin} is greater than
      *         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);
     }
 
+    /**
+     * Returns a pseudorandom {@code boolean} value.
+     *
+     * @return a pseudorandom {@code boolean} value
+     */
+    public boolean nextBoolean() {
+        return mix32(nextSeed()) < 0;
+    }
+
     // stream methods, coded in a way intended to better isolate for
     // 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)
@@ -611,7 +636,7 @@ public class SplittableRandom {
 
     /**
      * Returns an effectively unlimited stream of pseudorandom {@code int}
-     * values
+     * values.
      *
      * @implNote This method is implemented to be equivalent to {@code
      * ints(Long.MAX_VALUE)}.
@@ -626,7 +651,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 +659,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 +686,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 +700,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 +734,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 +742,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 +769,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 +783,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 +803,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 +819,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.
      *
@@ -804,9 +827,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 double} values,
-     * each with the given origin and bound.
+     * each with the given origin and bound
      * @throws IllegalArgumentException if {@code streamSize} is
-     * less than zero.
+     * less than zero
      * @throws IllegalArgumentException if {@code randomNumberOrigin}
      *         is greater than or equal to {@code randomNumberBound}
      */
@@ -814,7 +837,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
@@ -832,12 +855,12 @@ 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 double} 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}
      */
     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,13 +870,13 @@ 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
      * identical except for types.
      */
-    static class RandomIntsSpliterator implements Spliterator.OfInt {
+    static final class RandomIntsSpliterator implements Spliterator.OfInt {
         final SplittableRandom rng;
         long index;
         final long fence;
@@ -907,7 +930,7 @@ public class SplittableRandom {
     /**
      * Spliterator for long streams.
      */
-    static class RandomLongsSpliterator implements Spliterator.OfLong {
+    static final class RandomLongsSpliterator implements Spliterator.OfLong {
         final SplittableRandom rng;
         long index;
         final long fence;
@@ -962,7 +985,7 @@ public class SplittableRandom {
     /**
      * Spliterator for double streams.
      */
-    static class RandomDoublesSpliterator implements Spliterator.OfDouble {
+    static final class RandomDoublesSpliterator implements Spliterator.OfDouble {
         final SplittableRandom rng;
         long index;
         final long fence;
@@ -1014,4 +1037,3 @@ public class SplittableRandom {
     }
 
 }
-