[cvs] / jsr166 / src / main / java / util / SplittableRandom.java Repository:
ViewVC logotype

Diff of /jsr166/src/main/java/util/SplittableRandom.java

Parent Directory Parent Directory | Revision Log Revision Log | View Patch Patch

revision 1.6, Thu Jul 11 23:22:01 2013 UTC revision 1.7, Fri Jul 12 11:26:34 2013 UTC
# Line 35  Line 35 
35  import java.util.stream.LongStream;  import java.util.stream.LongStream;
36  import java.util.stream.DoubleStream;  import java.util.stream.DoubleStream;
37    
   
38  /**  /**
39   * A generator of uniform pseudorandom values applicable for use in   * A generator of uniform pseudorandom values applicable for use in
40   * (among other contexts) isolated parallel computations that may   * (among other contexts) isolated parallel computations that may
# Line 54  Line 53 
53   *   *
54   * <li> Method {@link #split} constructs and returns a new   * <li> Method {@link #split} constructs and returns a new
55   * SplittableRandom instance that shares no mutable state with the   * SplittableRandom instance that shares no mutable state with the
56   * current instance. However, with very high probability, the set of   * current instance. However, with very high probability, the
57   * values collectively generated by the two objects has the same   * values collectively generated by the two objects have the same
58   * statistical properties as if the same quantity of values were   * statistical properties as if the same quantity of values were
59   * generated by a single thread using a single {@code   * generated by a single thread using a single {@code
60   * SplittableRandom} object.  </li>   * SplittableRandom} object.  </li>
# Line 97  Line 96 
96       * Random-Number Generation for Dynamic-Multithreading Platforms",       * Random-Number Generation for Dynamic-Multithreading Platforms",
97       * PPoPP 2012, but improves and extends it in several ways.       * PPoPP 2012, but improves and extends it in several ways.
98       *       *
99       * The primary update step is simply to add a constant ("gamma")       * The primary update step (see method nextSeed()) is simply to
100       * to the current seed, modulo a prime ("George"). However, the       * add a constant ("gamma") to the current seed, modulo a prime
101       * nextLong and nextInt methods do not return this value, but       * ("George"). However, the nextLong and nextInt methods do not
102       * instead the results of bit-mixing transformations that produce       * return this value, but instead the results of bit-mixing
103       * more uniformly distributed sequences.       * transformations that produce more uniformly distributed
104         * sequences.
105       *       *
106       * "George" is the otherwise nameless (because it cannot be       * "George" is the otherwise nameless (because it cannot be
107       * represented) prime number 2^64+13. Using a prime number larger       * represented) prime number 2^64+13. Using a prime number larger
# Line 179  Line 179 
179    
180      /**      /**
181       * The least non-zero value returned by nextDouble(). This value       * The least non-zero value returned by nextDouble(). This value
182       * 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.
183       */       */
184      private static final double DOUBLE_UNIT = 1.0 / (1L << 53);      private static final double DOUBLE_UNIT = 1.0 / (1L << 53);
185    
# Line 206  Line 206 
206      private final long nextSplit;      private final long nextSplit;
207    
208      /**      /**
      * 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;  
     }  
   
     /**  
209       * Adds the given gamma value, g, to the given seed value s, mod       * 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       * 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       * (ranging from 0 to 2^64-1). We add g to s either once or twice
# Line 244  Line 227 
227      }      }
228    
229      /**      /**
      * Updates in-place and returns seed.  
      * See above for explanation.  
      */  
     private long nextSeed() {  
         return seed = addGammaModGeorge(seed, gamma);  
     }  
   
     /**  
230       * Returns a bit-mixed transformation of its argument.       * Returns a bit-mixed transformation of its argument.
231       * See above for explanation.       * See above for explanation.
232       */       */
# Line 275  Line 250 
250      }      }
251    
252      /**      /**
253       * Atomically updates and returns next seed for default constructor       * 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() {      private static long nextDefaultSeed() {
282          long oldSeed, newSeed;          long oldSeed, newSeed;
# Line 334  Line 335 
335              long n = bound - origin, m = n - 1;              long n = bound - origin, m = n - 1;
336              if ((n & m) == 0L) // power of two              if ((n & m) == 0L) // power of two
337                  r = (r & m) + origin;                  r = (r & m) + origin;
338              else if (n > 0) { // reject over-represented candidates              else if (n > 0L) {  // reject over-represented candidates
339                  for (long u = r >>> 1;            // ensure nonnegative                  for (long u = r >>> 1;            // ensure nonnegative
340                       u + m - (r = u % n) < 0L;    // reject                       u + m - (r = u % n) < 0L;    // rejection check
341                       u = mix64(nextSeed()) >>> 1) // retry                       u = mix64(nextSeed()) >>> 1) // retry
342                      ;                      ;
343                  r += origin;                  r += origin;
# Line 365  Line 366 
366                  r = (r & m) + origin;                  r = (r & m) + origin;
367              else if (n > 0) {              else if (n > 0) {
368                  for (int u = r >>> 1;                  for (int u = r >>> 1;
369                       u + m - (r = u % n) < 0L;                       u + m - (r = u % n) < 0;
370                       u = mix32(nextSeed()) >>> 1)                       u = mix32(nextSeed()) >>> 1)
371                      ;                      ;
372                  r += origin;                  r += origin;
# Line 389  Line 390 
390          double r = (nextLong() >>> 11) * DOUBLE_UNIT;          double r = (nextLong() >>> 11) * DOUBLE_UNIT;
391          if (origin < bound) {          if (origin < bound) {
392              r = r * (bound - origin) + origin;              r = r * (bound - origin) + origin;
393              if (r == bound) // correct for rounding              if (r >= bound) // correct for rounding
394                  r = Double.longBitsToDouble(Double.doubleToLongBits(bound) - 1);                  r = Double.longBitsToDouble(Double.doubleToLongBits(bound) - 1);
395          }          }
396          return r;          return r;
# Line 398  Line 399 
399      /* ---------------- public methods ---------------- */      /* ---------------- public methods ---------------- */
400    
401      /**      /**
402       * Creates a new SplittableRandom instance using the given initial       * Creates a new SplittableRandom instance using the specified
403       * seed. Two SplittableRandom instances created with the same seed       * initial seed. SplittableRandom instances created with the same
404       * generate identical sequences of values.       * seed generate identical sequences of values.
405       *       *
406       * @param seed the initial seed       * @param seed the initial seed
407       */       */
# Line 439  Line 440 
440      /**      /**
441       * Returns a pseudorandom {@code int} value.       * Returns a pseudorandom {@code int} value.
442       *       *
443       * @return a pseudorandom value       * @return a pseudorandom {@code int} value
444       */       */
445      public int nextInt() {      public int nextInt() {
446          return mix32(nextSeed());          return mix32(nextSeed());
447      }      }
448    
449      /**      /**
450       * Returns a pseudorandom {@code int} value between 0 (inclusive)       * Returns a pseudorandom {@code int} value between zero (inclusive)
451       * and the specified bound (exclusive).       * and the specified bound (exclusive).
452       *       *
453       * @param bound the bound on the random number to be returned.  Must be       * @param bound the bound on the random number to be returned.  Must be
454       *        positive.       *        positive.
455       * @return a pseudorandom {@code int} value between {@code 0}       * @return a pseudorandom {@code int} value between zero
456       *         (inclusive) and the bound (exclusive).       *         (inclusive) and the bound (exclusive).
457       * @exception IllegalArgumentException if the bound is not positive       * @throws IllegalArgumentException if the bound is less than zero
458       */       */
459      public int nextInt(int bound) {      public int nextInt(int bound) {
460          if (bound <= 0)          if (bound <= 0)
# Line 465  Line 466 
466              r &= m;              r &= m;
467          else { // reject over-represented candidates          else { // reject over-represented candidates
468              for (int u = r >>> 1;              for (int u = r >>> 1;
469                   u + m - (r = u % bound) < 0L;                   u + m - (r = u % bound) < 0;
470                   u = mix32(nextSeed()) >>> 1)                   u = mix32(nextSeed()) >>> 1)
471                  ;                  ;
472          }          }
# Line 480  Line 481 
481       * @param bound the upper bound (exclusive)       * @param bound the upper bound (exclusive)
482       * @return a pseudorandom {@code int} value between the origin       * @return a pseudorandom {@code int} value between the origin
483       *         (inclusive) and the bound (exclusive).       *         (inclusive) and the bound (exclusive).
484       * @exception IllegalArgumentException if {@code origin} is greater than       * @throws IllegalArgumentException if {@code origin} is greater than
485       *         or equal to {@code bound}       *         or equal to {@code bound}
486       */       */
487      public int nextInt(int origin, int bound) {      public int nextInt(int origin, int bound) {
# Line 492  Line 493 
493      /**      /**
494       * Returns a pseudorandom {@code long} value.       * Returns a pseudorandom {@code long} value.
495       *       *
496       * @return a pseudorandom value       * @return a pseudorandom {@code long} value
497       */       */
498      public long nextLong() {      public long nextLong() {
499          return mix64(nextSeed());          return mix64(nextSeed());
500      }      }
501    
502      /**      /**
503       * Returns a pseudorandom {@code long} value between 0 (inclusive)       * Returns a pseudorandom {@code long} value between zero (inclusive)
504       * and the specified bound (exclusive).       * and the specified bound (exclusive).
505       *       *
506       * @param bound the bound on the random number to be returned.  Must be       * @param bound the bound on the random number to be returned.  Must be
507       *        positive.       *        positive.
508       * @return a pseudorandom {@code long} value between {@code 0}       * @return a pseudorandom {@code long} value between zero
509       *         (inclusive) and the bound (exclusive).       *         (inclusive) and the bound (exclusive).
510       * @exception IllegalArgumentException if the bound is not positive       * @throws IllegalArgumentException if {@code bound} is less than zero
511       */       */
512      public long nextLong(long bound) {      public long nextLong(long bound) {
513          if (bound <= 0)          if (bound <= 0)
# Line 533  Line 534 
534       * @param bound the upper bound (exclusive)       * @param bound the upper bound (exclusive)
535       * @return a pseudorandom {@code long} value between the origin       * @return a pseudorandom {@code long} value between the origin
536       *         (inclusive) and the bound (exclusive).       *         (inclusive) and the bound (exclusive).
537       * @exception IllegalArgumentException if {@code origin} is greater than       * @throws IllegalArgumentException if {@code origin} is greater than
538       *         or equal to {@code bound}       *         or equal to {@code bound}
539       */       */
540      public long nextLong(long origin, long bound) {      public long nextLong(long origin, long bound) {
# Line 543  Line 544 
544      }      }
545    
546      /**      /**
547       * Returns a pseudorandom {@code double} value between {@code 0.0}       * Returns a pseudorandom {@code double} value between zero
548       * (inclusive) and {@code 1.0} (exclusive).       * (inclusive) and one (exclusive).
549       *       *
550       * @return a pseudorandom value between {@code 0.0}       * @return a pseudorandom {@code double} value between zero
551       * (inclusive) and {@code 1.0} (exclusive)       * (inclusive) and one (exclusive)
552       */       */
553      public double nextDouble() {      public double nextDouble() {
554          return (nextLong() >>> 11) * DOUBLE_UNIT;          return (nextLong() >>> 11) * DOUBLE_UNIT;
# Line 559  Line 560 
560       *       *
561       * @param bound the bound on the random number to be returned.  Must be       * @param bound the bound on the random number to be returned.  Must be
562       *        positive.       *        positive.
563       * @return a pseudorandom {@code double} value between {@code 0.0}       * @return a pseudorandom {@code double} value between zero
564       *         (inclusive) and the bound (exclusive).       *         (inclusive) and the bound (exclusive).
565       * @throws IllegalArgumentException if {@code bound} is not positive       * @throws IllegalArgumentException if {@code bound} is less than zero
566       */       */
567      public double nextDouble(double bound) {      public double nextDouble(double bound) {
568          if (bound <= 0.0)          if (!(bound > 0.0))
569              throw new IllegalArgumentException("bound must be positive");              throw new IllegalArgumentException("bound must be positive");
570          double result = nextDouble() * bound;          double result = nextDouble() * bound;
571          return (result < bound) ?  result : // correct for rounding          return (result < bound) ?  result : // correct for rounding
# Line 572  Line 573 
573      }      }
574    
575      /**      /**
576       * Returns a pseudorandom {@code double} value between the given       * Returns a pseudorandom {@code double} value between the specified
577       * origin (inclusive) and bound (exclusive).       * origin (inclusive) and bound (exclusive).
578       *       *
579       * @param origin the least value returned       * @param origin the least value returned
# Line 583  Line 584 
584       *         or equal to {@code bound}       *         or equal to {@code bound}
585       */       */
586      public double nextDouble(double origin, double bound) {      public double nextDouble(double origin, double bound) {
587          if (origin >= bound)          if (!(origin < bound))
588              throw new IllegalArgumentException("bound must be greater than origin");              throw new IllegalArgumentException("bound must be greater than origin");
589          return internalNextDouble(origin, bound);          return internalNextDouble(origin, bound);
590      }      }
# Line 592  Line 593 
593      // maintenance purposes the small differences across forms.      // maintenance purposes the small differences across forms.
594    
595      /**      /**
596       * Returns a stream with the given {@code streamSize} number of       * Returns a stream producing the given {@code streamSize} number of
597       * pseudorandom {@code int} values.       * pseudorandom {@code int} values.
598       *       *
599       * @param streamSize the number of values to generate       * @param streamSize the number of values to generate
# Line 626  Line 627 
627      }      }
628    
629      /**      /**
630       * Returns a stream with the given {@code streamSize} number of       * Returns a stream producing the given {@code streamSize} number of
631       * pseudorandom {@code int} values, each conforming to the given       * pseudorandom {@code int} values, each conforming to the given
632       * origin and bound.       * origin and bound.
633       *       *
# Line 636  Line 637 
637       * @return a stream of pseudorandom {@code int} values,       * @return a stream of pseudorandom {@code int} values,
638       * each with the given origin and bound.       * each with the given origin and bound.
639       * @throws IllegalArgumentException if {@code streamSize} is       * @throws IllegalArgumentException if {@code streamSize} is
640       * less than zero.       *         less than zero, or {@code randomNumberOrigin}
      * @throws IllegalArgumentException if {@code randomNumberOrigin}  
641       *         is greater than or equal to {@code randomNumberBound}       *         is greater than or equal to {@code randomNumberBound}
642       */       */
643      public IntStream ints(long streamSize, int randomNumberOrigin,      public IntStream ints(long streamSize, int randomNumberOrigin,
# Line 676  Line 676 
676      }      }
677    
678      /**      /**
679       * Returns a stream with the given {@code streamSize} number of       * Returns a stream producing the given {@code streamSize} number of
680       * pseudorandom {@code long} values.       * pseudorandom {@code long} values.
681       *       *
682       * @param streamSize the number of values to generate       * @param streamSize the number of values to generate
683       * @return a stream of {@code long} values       * @return a stream of pseudorandom {@code long} values
684       * @throws IllegalArgumentException if {@code streamSize} is       * @throws IllegalArgumentException if {@code streamSize} is
685       * less than zero       * less than zero
686       */       */
# Line 710  Line 710 
710      }      }
711    
712      /**      /**
713       * Returns a stream with the given {@code streamSize} number of       * Returns a stream producing the given {@code streamSize} number of
714       * pseudorandom {@code long} values, each conforming to the       * pseudorandom {@code long} values, each conforming to the
715       * given origin and bound.       * given origin and bound.
716       *       *
# Line 720  Line 720 
720       * @return a stream of pseudorandom {@code long} values,       * @return a stream of pseudorandom {@code long} values,
721       * each with the given origin and bound.       * each with the given origin and bound.
722       * @throws IllegalArgumentException if {@code streamSize} is       * @throws IllegalArgumentException if {@code streamSize} is
723       * less than zero.       *         less than zero, or {@code randomNumberOrigin}
      * @throws IllegalArgumentException if {@code randomNumberOrigin}  
724       *         is greater than or equal to {@code randomNumberBound}       *         is greater than or equal to {@code randomNumberBound}
725       */       */
726      public LongStream longs(long streamSize, long randomNumberOrigin,      public LongStream longs(long streamSize, long randomNumberOrigin,
# Line 760  Line 759 
759      }      }
760    
761      /**      /**
762       * Returns a stream with the given {@code streamSize} number of       * Returns a stream producing the given {@code streamSize} number of
763       * pseudorandom {@code double} values, each between {@code 0.0}       * pseudorandom {@code double} values, each between zero
764       * (inclusive) and {@code 1.0} (exclusive).       * (inclusive) and one (exclusive).
765       *       *
766       * @param streamSize the number of values to generate       * @param streamSize the number of values to generate
767       * @return a stream of {@code double} values       * @return a stream of {@code double} values
# Line 780  Line 779 
779    
780      /**      /**
781       * Returns an effectively unlimited stream of pseudorandom {@code       * Returns an effectively unlimited stream of pseudorandom {@code
782       * double} values, each between {@code 0.0} (inclusive) and {@code       * double} values, each between zero (inclusive) and one
783       * 1.0} (exclusive).       * (exclusive).
784       *       *
785       * @implNote This method is implemented to be equivalent to {@code       * @implNote This method is implemented to be equivalent to {@code
786       * doubles(Long.MAX_VALUE)}.       * doubles(Long.MAX_VALUE)}.
# Line 796  Line 795 
795      }      }
796    
797      /**      /**
798       * Returns a stream with the given {@code streamSize} number of       * Returns a stream producing the given {@code streamSize} number of
799       * pseudorandom {@code double} values, each conforming to the       * pseudorandom {@code double} values, each conforming to the
800       * given origin and bound.       * given origin and bound.
801       *       *
# Line 814  Line 813 
813                                  double randomNumberBound) {                                  double randomNumberBound) {
814          if (streamSize < 0L)          if (streamSize < 0L)
815              throw new IllegalArgumentException("negative Stream size");              throw new IllegalArgumentException("negative Stream size");
816          if (randomNumberOrigin >= randomNumberBound)          if (!(randomNumberOrigin < randomNumberBound))
817              throw new IllegalArgumentException("bound must be greater than origin");              throw new IllegalArgumentException("bound must be greater than origin");
818          return StreamSupport.doubleStream          return StreamSupport.doubleStream
819              (new RandomDoublesSpliterator              (new RandomDoublesSpliterator
# Line 837  Line 836 
836       *         is greater than or equal to {@code randomNumberBound}       *         is greater than or equal to {@code randomNumberBound}
837       */       */
838      public DoubleStream doubles(double randomNumberOrigin, double randomNumberBound) {      public DoubleStream doubles(double randomNumberOrigin, double randomNumberBound) {
839          if (randomNumberOrigin >= randomNumberBound)          if (!(randomNumberOrigin < randomNumberBound))
840              throw new IllegalArgumentException("bound must be greater than origin");              throw new IllegalArgumentException("bound must be greater than origin");
841          return StreamSupport.doubleStream          return StreamSupport.doubleStream
842              (new RandomDoublesSpliterator              (new RandomDoublesSpliterator
# Line 847  Line 846 
846    
847      /**      /**
848       * Spliterator for int streams.  We multiplex the four int       * Spliterator for int streams.  We multiplex the four int
849       * versions into one class by treating and bound < origin as       * versions into one class by treating a bound less than origin as
850       * unbounded, and also by treating "infinite" as equivalent to       * unbounded, and also by treating "infinite" as equivalent to
851       * Long.MAX_VALUE. For splits, it uses the standard divide-by-two       * Long.MAX_VALUE. For splits, it uses the standard divide-by-two
852       * approach. The long and double versions of this class are       * approach. The long and double versions of this class are

Legend:
Removed from v.1.6  
changed lines
  Added in v.1.7

Doug Lea
ViewVC Help
Powered by ViewVC 1.0.8