[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.12, Sun Jul 21 14:02:23 2013 UTC revision 1.13, Thu Jul 25 13:19:09 2013 UTC
# Line 115  Line 115 
115       * are encountered; see method addGammaModGeorge. For this to       * are encountered; see method addGammaModGeorge. For this to
116       * work, initial gamma values must be at least 13.       * work, initial gamma values must be at least 13.
117       *       *
      * The value of gamma differs for each instance across a series of  
      * splits, and is generated using a slightly stripped-down variant  
      * of the same algorithm, but operating across calls to split(),  
      * not calls to nextSeed(): Each instance carries the state of  
      * this generator as nextSplit, and uses mix64(nextSplit) as its  
      * own gamma value. Computations of gammas themselves use a fixed  
      * constant as the second argument to the addGammaModGeorge  
      * function, GAMMA_GAMMA. The value of GAMMA_GAMMA is arbitrary  
      * (except must be at least 13), but because it serves as the base  
      * of split sequences, should be subject to validation of  
      * consequent random number quality metrics.  
      *  
118       * The mix64 bit-mixing function called by nextLong and other       * The mix64 bit-mixing function called by nextLong and other
119       * methods computes the same value as the "64-bit finalizer"       * methods computes the same value as the "64-bit finalizer"
120       * function in Austin Appleby's MurmurHash3 algorithm.  See       * function in Austin Appleby's MurmurHash3 algorithm.  See
121       * http://code.google.com/p/smhasher/wiki/MurmurHash3 , which       * http://code.google.com/p/smhasher/wiki/MurmurHash3 , which
122       * comments: "The constants for the finalizers were generated by a       * comments: "The constants for the finalizers were generated by a
123       * simple simulated-annealing algorithm, and both avalanche all       * simple simulated-annealing algorithm, and both avalanche all
124       * bits of 'h' to within 0.25% bias." It also appears to work to       * bits of 'h' to within 0.25% bias."
125       * use instead any of the variants proposed by David Stafford at       *
126       * http://zimbry.blogspot.com/2011/09/better-bit-mixing-improving-on.html       * The value of gamma differs for each instance across a series of
127       * but these variants have not yet been tested as thoroughly       * splits, and is generated using an independent variant of the
128       * in the context of the implementation of SplittableRandom.       * same algorithm, but operating across calls to split(), not
129         * calls to nextSeed(): Each instance carries the state of this
130         * generator as nextSplit. Gammas are treated as 57bit values,
131         * advancing by adding GAMMA_GAMMA mod GAMMA_PRIME, and bit-mixed
132         * with a 57-bit version of mix, using the "Mix01" multiplicative
133         * constants for MurmurHash3 described by David Stafford
134         * (http://zimbry.blogspot.com/2011/09/better-bit-mixing-improving-on.html).
135         * The value of GAMMA_GAMMA is arbitrary (except must be at least
136         * 13 and less than GAMMA_PRIME), but because it serves as the
137         * base of split sequences, should be subject to validation of
138         * consequent random number quality metrics.
139       *       *
140       * The mix32 function used for nextInt just consists of two of the       * The mix32 function used for nextInt just consists of two of the
141       * five lines of mix64; avalanche testing shows that the 64-bit result       * five lines of mix64; avalanche testing shows that the 64-bit
142       * has its top 32 bits avalanched well, though not the bottom 32 bits.       * result has its top 32 bits avalanched well, though not the
143       * DieHarder tests show that it is adequate for generating one       * bottom 32 bits.  DieHarder tests show that it is adequate for
144       * random int from the 64-bit result of nextSeed.       * generating one random int from the 64-bit result of nextSeed.
145       *       *
146       * Support for the default (no-argument) constructor relies on an       * Support for the default (no-argument) constructor relies on an
147       * AtomicLong (defaultSeedGenerator) to help perform the       * AtomicLong (defaultSeedGenerator) to help perform the
# Line 161  Line 159 
159       */       */
160    
161      /**      /**
162         * The prime modulus for gamma values.
163         */
164        private static final long GAMMA_PRIME = (1L << 57) - 13L;
165    
166        /**
167       * The value for producing new gamma values. Must be greater or       * The value for producing new gamma values. Must be greater or
168       * equal to 13. Otherwise, the value is arbitrary subject to       * equal to 13 and less than GAMMA_PRIME. Otherwise, the value is
169       * validation of the resulting statistical quality of splits.       * arbitrary subject to validation of the resulting statistical
170         * quality of splits.
171       */       */
172      private static final long GAMMA_GAMMA = 0xF2281E2DBA6606F3L;      private static final long GAMMA_GAMMA = 0x00aae38294f712aabL;
173    
174      /**      /**
175       * The seed update value for default constructors.  Must be       * The seed update value for default constructors.  Must be
176       * greater or equal to 13. Otherwise, the value is arbitrary.       * greater or equal to 13. Otherwise, the value is arbitrary
177         * subject to quality checks.
178       */       */
179      private static final long DEFAULT_SEED_GAMMA = 0xBD24B73A95FB84D9L;      private static final long DEFAULT_SEED_GAMMA = 0x9e3779b97f4a7c15L;
180    
181      /**      /**
182       * The value 13 with 64bit sign bit set. Used in the signed       * The value 13 with 64bit sign bit set. Used in the signed
# Line 253  Line 258 
258      }      }
259    
260      /**      /**
261         * Returns a 57-bit mixed transformation of its argument.  See
262         * above for explanation.
263         */
264        private static long mix57(long z) {
265            z ^= (z >>> 33);
266            z *= 0x7fb5d329728ea185L;
267            z &= 0x01FFFFFFFFFFFFFFL;
268            z ^= (z >>> 33);
269            z *= 0x81dadef4bc2dd44dL;
270            z &= 0x01FFFFFFFFFFFFFFL;
271            z ^= (z >>> 33);
272            return z;
273        }
274    
275        /**
276       * Internal constructor used by all other constructors and by       * Internal constructor used by all other constructors and by
277       * method split. Establishes the initial seed for this instance,       * method split. Establishes the initial seed for this instance,
278       * and uses the given splitSeed to establish gamma, as well as the       * and uses the given splitSeed to establish gamma, as well as the
# Line 263  Line 283 
283          this.seed = seed;          this.seed = seed;
284          long s = splitSeed, g;          long s = splitSeed, g;
285          do { // ensure gamma >= 13, considered as an unsigned integer          do { // ensure gamma >= 13, considered as an unsigned integer
286              s = addGammaModGeorge(s, GAMMA_GAMMA);              s += GAMMA_GAMMA;
287              g = mix64(s);              if (s >= GAMMA_PRIME)
288          } while (g >= 0L && g < 13L);                  s -= GAMMA_PRIME;
289                g = mix57(s);
290            } while (g < 13L);
291          this.gamma = g;          this.gamma = g;
292          this.nextSplit = s;          this.nextSplit = s;
293      }      }
# Line 376  Line 398 
398          int r = mix32(nextSeed());          int r = mix32(nextSeed());
399          if (origin < bound) {          if (origin < bound) {
400              int n = bound - origin, m = n - 1;              int n = bound - origin, m = n - 1;
401              if ((n & m) == 0L)              if ((n & m) == 0)
402                  r = (r & m) + origin;                  r = (r & m) + origin;
403              else if (n > 0) {              else if (n > 0) {
404                  for (int u = r >>> 1;                  for (int u = r >>> 1;
# Line 420  Line 442 
442       * @param seed the initial seed       * @param seed the initial seed
443       */       */
444      public SplittableRandom(long seed) {      public SplittableRandom(long seed) {
445          this(seed, 0);          this(seed, 0L);
446      }      }
447    
448      /**      /**
# Line 476  Line 498 
498          // Specialize internalNextInt for origin 0          // Specialize internalNextInt for origin 0
499          int r = mix32(nextSeed());          int r = mix32(nextSeed());
500          int m = bound - 1;          int m = bound - 1;
501          if ((bound & m) == 0L) // power of two          if ((bound & m) == 0) // power of two
502              r &= m;              r &= m;
503          else { // reject over-represented candidates          else { // reject over-represented candidates
504              for (int u = r >>> 1;              for (int u = r >>> 1;

Legend:
Removed from v.1.12  
changed lines
  Added in v.1.13

Doug Lea
ViewVC Help
Powered by ViewVC 1.0.8