ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/jsr166/jsr166/src/main/java/util/SplittableRandom.java
(Generate patch)

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.12 by dl, Sun Jul 21 14:02:23 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 117 | Line 122 | public class SplittableRandom {
122       * this generator as nextSplit, and uses mix64(nextSplit) as its
123       * own gamma value. Computations of gammas themselves use a fixed
124       * constant as the second argument to the addGammaModGeorge
125 <     * function, GAMMA_GAMMA, a "genuinely random" number from a
126 <     * radioactive decay reading (obtained from
127 <     * http://www.fourmilab.ch/hotbits/) meeting the above range
128 <     * 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.)
125 >     * function, GAMMA_GAMMA. The value of GAMMA_GAMMA is arbitrary
126 >     * (except must be at least 13), but because it serves as the base
127 >     * of split sequences, should be subject to validation of
128 >     * consequent random number quality metrics.
129       *
130       * The mix64 bit-mixing function called by nextLong and other
131       * methods computes the same value as the "64-bit finalizer"
# Line 154 | Line 151 | public class SplittableRandom {
151       * SplittableRandom. Unlike other cases, this split must be
152       * performed in a thread-safe manner. We use
153       * AtomicLong.compareAndSet as the (typically) most efficient
154 <     * mechanism. To bootstrap, we start off using System.nanotime(),
155 <     * and update using another "genuinely random" constant
154 >     * mechanism. To bootstrap, we start off using a SecureRandom
155 >     * initial default seed, and update using a fixed
156       * DEFAULT_SEED_GAMMA. The default constructor uses GAMMA_GAMMA,
157       * not 0, for its splitSeed argument (addGammaModGeorge(0,
158       * GAMMA_GAMMA) == GAMMA_GAMMA) to reflect that each is split from
# Line 164 | Line 161 | public class SplittableRandom {
161       */
162  
163      /**
164 <     * The "genuinely random" value for producing new gamma values.
165 <     * The value is arbitrary, subject to the requirement that it be
166 <     * greater or equal to 13.
164 >     * The value for producing new gamma values. Must be greater or
165 >     * equal to 13. Otherwise, the value is arbitrary subject to
166 >     * validation of the resulting statistical quality of splits.
167       */
168      private static final long GAMMA_GAMMA = 0xF2281E2DBA6606F3L;
169  
170      /**
171 <     * The "genuinely random" seed update value for default constructors.
172 <     * The value is arbitrary, subject to the requirement that it be
176 <     * greater or equal to 13.
171 >     * The seed update value for default constructors.  Must be
172 >     * greater or equal to 13. Otherwise, the value is arbitrary.
173       */
174      private static final long DEFAULT_SEED_GAMMA = 0xBD24B73A95FB84D9L;
175  
176      /**
177 +     * The value 13 with 64bit sign bit set. Used in the signed
178 +     * comparison in addGammaModGeorge.
179 +     */
180 +    private static final long BOTTOM13 = 0x800000000000000DL;
181 +
182 +    /**
183       * The least non-zero value returned by nextDouble(). This value
184       * is scaled by a random value of 53 bits to produce a result.
185       */
# Line 187 | Line 189 | public class SplittableRandom {
189       * The next seed for default constructors.
190       */
191      private static final AtomicLong defaultSeedGenerator =
192 <        new AtomicLong(System.nanoTime());
192 >        new AtomicLong(getInitialDefaultSeed());
193  
194      /**
195       * The seed, updated only via method nextSeed.
# Line 215 | Line 217 | public class SplittableRandom {
217       * George < 2^64; thus we need only a conditional, not a loop,
218       * to be sure of getting a representable value.
219       *
220 <     * @param s a seed value
220 >     * Because Java comparison operators are signed, we implement this
221 >     * by conceptually offsetting seed values downwards by 2^63, so
222 >     * 0..13 is represented as Long.MIN_VALUE..BOTTOM13.
223 >     *
224 >     * @param s a seed value, viewed as a signed long
225       * @param g a gamma value, 13 <= g (as unsigned)
226       */
227      private static long addGammaModGeorge(long s, long g) {
228          long p = s + g;
229 <        if (Long.compareUnsigned(p, g) >= 0)
224 <            return p;
225 <        long q = p - 13L;
226 <        return (Long.compareUnsigned(p, 13L) >= 0) ? q : (q + g);
229 >        return (p >= s) ? p : ((p >= BOTTOM13) ? p  : p + g) - 13L;
230      }
231  
232      /**
# Line 262 | Line 265 | public class SplittableRandom {
265          do { // ensure gamma >= 13, considered as an unsigned integer
266              s = addGammaModGeorge(s, GAMMA_GAMMA);
267              g = mix64(s);
268 <        } while (Long.compareUnsigned(g, 13L) < 0);
268 >        } while (g >= 0L && g < 13L);
269          this.gamma = g;
270          this.nextSplit = s;
271      }
# Line 287 | Line 290 | public class SplittableRandom {
290          return mix64(newSeed);
291      }
292  
293 +    /**
294 +     * Returns an initial default seed.
295 +     */
296 +    private static long getInitialDefaultSeed() {
297 +        byte[] seedBytes = java.security.SecureRandom.getSeed(8);
298 +        long s = (long)(seedBytes[0]) & 0xffL;
299 +        for (int i = 1; i < 8; ++i)
300 +            s = (s << 8) | ((long)(seedBytes[i]) & 0xffL);
301 +        return s;
302 +    }
303 +
304      /*
305       * Internal versions of nextX methods used by streams, as well as
306       * the public nextX(origin, bound) methods.  These exist mainly to
# Line 401 | Line 415 | public class SplittableRandom {
415      /**
416       * Creates a new SplittableRandom instance using the specified
417       * initial seed. SplittableRandom instances created with the same
418 <     * seed generate identical sequences of values.
418 >     * seed in the same program generate identical sequences of values.
419       *
420       * @param seed the initial seed
421       */
# Line 453 | Line 467 | public class SplittableRandom {
467       * @param bound the bound on the random number to be returned.  Must be
468       *        positive.
469       * @return a pseudorandom {@code int} value between zero
470 <     *         (inclusive) and the bound (exclusive).
470 >     *         (inclusive) and the bound (exclusive)
471       * @throws IllegalArgumentException if the bound is less than zero
472       */
473      public int nextInt(int bound) {
# Line 480 | Line 494 | public class SplittableRandom {
494       * @param origin the least value returned
495       * @param bound the upper bound (exclusive)
496       * @return a pseudorandom {@code int} value between the origin
497 <     *         (inclusive) and the bound (exclusive).
497 >     *         (inclusive) and the bound (exclusive)
498       * @throws IllegalArgumentException if {@code origin} is greater than
499       *         or equal to {@code bound}
500       */
# Line 506 | Line 520 | public class SplittableRandom {
520       * @param bound the bound on the random number to be returned.  Must be
521       *        positive.
522       * @return a pseudorandom {@code long} value between zero
523 <     *         (inclusive) and the bound (exclusive).
523 >     *         (inclusive) and the bound (exclusive)
524       * @throws IllegalArgumentException if {@code bound} is less than zero
525       */
526      public long nextLong(long bound) {
# Line 533 | Line 547 | public class SplittableRandom {
547       * @param origin the least value returned
548       * @param bound the upper bound (exclusive)
549       * @return a pseudorandom {@code long} value between the origin
550 <     *         (inclusive) and the bound (exclusive).
550 >     *         (inclusive) and the bound (exclusive)
551       * @throws IllegalArgumentException if {@code origin} is greater than
552       *         or equal to {@code bound}
553       */
# Line 551 | Line 565 | public class SplittableRandom {
565       * (inclusive) and one (exclusive)
566       */
567      public double nextDouble() {
568 <        return (nextLong() >>> 11) * DOUBLE_UNIT;
568 >        return (mix64(nextSeed()) >>> 11) * DOUBLE_UNIT;
569      }
570  
571      /**
# Line 561 | Line 575 | public class SplittableRandom {
575       * @param bound the bound on the random number to be returned.  Must be
576       *        positive.
577       * @return a pseudorandom {@code double} value between zero
578 <     *         (inclusive) and the bound (exclusive).
578 >     *         (inclusive) and the bound (exclusive)
579       * @throws IllegalArgumentException if {@code bound} is less than zero
580       */
581      public double nextDouble(double bound) {
582          if (!(bound > 0.0))
583              throw new IllegalArgumentException("bound must be positive");
584 <        double result = nextDouble() * bound;
584 >        double result = (mix64(nextSeed()) >>> 11) * DOUBLE_UNIT * bound;
585          return (result < bound) ?  result : // correct for rounding
586              Double.longBitsToDouble(Double.doubleToLongBits(bound) - 1);
587      }
# Line 579 | Line 593 | public class SplittableRandom {
593       * @param origin the least value returned
594       * @param bound the upper bound
595       * @return a pseudorandom {@code double} value between the origin
596 <     *         (inclusive) and the bound (exclusive).
596 >     *         (inclusive) and the bound (exclusive)
597       * @throws IllegalArgumentException if {@code origin} is greater than
598       *         or equal to {@code bound}
599       */
# Line 589 | Line 603 | public class SplittableRandom {
603          return internalNextDouble(origin, bound);
604      }
605  
606 +    /**
607 +     * Returns a pseudorandom {@code boolean} value.
608 +     *
609 +     * @return a pseudorandom {@code boolean} value
610 +     */
611 +    public boolean nextBoolean() {
612 +        return mix32(nextSeed()) < 0;
613 +    }
614 +
615      // stream methods, coded in a way intended to better isolate for
616      // maintenance purposes the small differences across forms.
617  
# Line 612 | Line 635 | public class SplittableRandom {
635  
636      /**
637       * Returns an effectively unlimited stream of pseudorandom {@code int}
638 <     * values
638 >     * values.
639       *
640       * @implNote This method is implemented to be equivalent to {@code
641       * ints(Long.MAX_VALUE)}.
# Line 635 | Line 658 | public class SplittableRandom {
658       * @param randomNumberOrigin the origin of each random value
659       * @param randomNumberBound the bound of each random value
660       * @return a stream of pseudorandom {@code int} values,
661 <     *         each with the given origin and bound.
661 >     *         each with the given origin and bound
662       * @throws IllegalArgumentException if {@code streamSize} is
663       *         less than zero, or {@code randomNumberOrigin}
664       *         is greater than or equal to {@code randomNumberBound}
# Line 662 | Line 685 | public class SplittableRandom {
685       * @param randomNumberOrigin the origin of each random value
686       * @param randomNumberBound the bound of each random value
687       * @return a stream of pseudorandom {@code int} values,
688 <     *         each with the given origin and bound.
688 >     *         each with the given origin and bound
689       * @throws IllegalArgumentException if {@code randomNumberOrigin}
690       *         is greater than or equal to {@code randomNumberBound}
691       */
# Line 718 | Line 741 | public class SplittableRandom {
741       * @param randomNumberOrigin the origin of each random value
742       * @param randomNumberBound the bound of each random value
743       * @return a stream of pseudorandom {@code long} values,
744 <     *         each with the given origin and bound.
744 >     *         each with the given origin and bound
745       * @throws IllegalArgumentException if {@code streamSize} is
746       *         less than zero, or {@code randomNumberOrigin}
747       *         is greater than or equal to {@code randomNumberBound}
# Line 745 | Line 768 | public class SplittableRandom {
768       * @param randomNumberOrigin the origin of each random value
769       * @param randomNumberBound the bound of each random value
770       * @return a stream of pseudorandom {@code long} values,
771 <     *         each with the given origin and bound.
771 >     *         each with the given origin and bound
772       * @throws IllegalArgumentException if {@code randomNumberOrigin}
773       *         is greater than or equal to {@code randomNumberBound}
774       */
# Line 803 | Line 826 | public class SplittableRandom {
826       * @param randomNumberOrigin the origin of each random value
827       * @param randomNumberBound the bound of each random value
828       * @return a stream of pseudorandom {@code double} values,
829 <     * each with the given origin and bound.
829 >     * each with the given origin and bound
830       * @throws IllegalArgumentException if {@code streamSize} is
831 <     * less than zero.
831 >     * less than zero
832       * @throws IllegalArgumentException if {@code randomNumberOrigin}
833       *         is greater than or equal to {@code randomNumberBound}
834       */
# Line 831 | Line 854 | public class SplittableRandom {
854       * @param randomNumberOrigin the origin of each random value
855       * @param randomNumberBound the bound of each random value
856       * @return a stream of pseudorandom {@code double} values,
857 <     * each with the given origin and bound.
857 >     * each with the given origin and bound
858       * @throws IllegalArgumentException if {@code randomNumberOrigin}
859       *         is greater than or equal to {@code randomNumberBound}
860       */
# Line 852 | Line 875 | public class SplittableRandom {
875       * approach. The long and double versions of this class are
876       * identical except for types.
877       */
878 <    static class RandomIntsSpliterator implements Spliterator.OfInt {
878 >    static final class RandomIntsSpliterator implements Spliterator.OfInt {
879          final SplittableRandom rng;
880          long index;
881          final long fence;
# Line 906 | Line 929 | public class SplittableRandom {
929      /**
930       * Spliterator for long streams.
931       */
932 <    static class RandomLongsSpliterator implements Spliterator.OfLong {
932 >    static final class RandomLongsSpliterator implements Spliterator.OfLong {
933          final SplittableRandom rng;
934          long index;
935          final long fence;
# Line 961 | Line 984 | public class SplittableRandom {
984      /**
985       * Spliterator for double streams.
986       */
987 <    static class RandomDoublesSpliterator implements Spliterator.OfDouble {
987 >    static final class RandomDoublesSpliterator implements Spliterator.OfDouble {
988          final SplittableRandom rng;
989          long index;
990          final long fence;
# Line 1013 | Line 1036 | public class SplittableRandom {
1036      }
1037  
1038   }
1016 –

Diff Legend

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