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.12 by dl, Sun Jul 21 14:02:23 2013 UTC vs.
Revision 1.13 by dl, Thu Jul 25 13:19:09 2013 UTC

# Line 115 | Line 115 | public class SplittableRandom {
115       * are encountered; see method addGammaModGeorge. For this to
116       * work, initial gamma values must be at least 13.
117       *
118 –     * The value of gamma differs for each instance across a series of
119 –     * splits, and is generated using a slightly stripped-down variant
120 –     * of the same algorithm, but operating across calls to split(),
121 –     * not calls to nextSeed(): Each instance carries the state of
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. 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 –     *
118       * The mix64 bit-mixing function called by nextLong and other
119       * methods computes the same value as the "64-bit finalizer"
120       * function in Austin Appleby's MurmurHash3 algorithm.  See
121       * http://code.google.com/p/smhasher/wiki/MurmurHash3 , which
122       * comments: "The constants for the finalizers were generated by a
123       * simple simulated-annealing algorithm, and both avalanche all
124 <     * bits of 'h' to within 0.25% bias." It also appears to work to
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
127 <     * but these variants have not yet been tested as thoroughly
128 <     * in the context of the implementation of SplittableRandom.
124 >     * bits of 'h' to within 0.25% bias."
125 >     *
126 >     * The value of gamma differs for each instance across a series of
127 >     * splits, and is generated using an independent variant of the
128 >     * 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
141 <     * five lines of mix64; avalanche testing shows that the 64-bit result
142 <     * has its top 32 bits avalanched well, though not the bottom 32 bits.
143 <     * DieHarder tests show that it is adequate for generating one
144 <     * random int from the 64-bit result of nextSeed.
141 >     * five lines of mix64; avalanche testing shows that the 64-bit
142 >     * result has its top 32 bits avalanched well, though not the
143 >     * bottom 32 bits.  DieHarder tests show that it is adequate for
144 >     * generating one random int from the 64-bit result of nextSeed.
145       *
146       * Support for the default (no-argument) constructor relies on an
147       * AtomicLong (defaultSeedGenerator) to help perform the
# Line 161 | Line 159 | public class SplittableRandom {
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
168 <     * equal to 13. Otherwise, the value is arbitrary subject to
169 <     * validation of the resulting statistical quality of splits.
168 >     * equal to 13 and less than GAMMA_PRIME. Otherwise, the value is
169 >     * arbitrary subject to validation of the resulting statistical
170 >     * quality of splits.
171       */
172 <    private static final long GAMMA_GAMMA = 0xF2281E2DBA6606F3L;
172 >    private static final long GAMMA_GAMMA = 0x00aae38294f712aabL;
173  
174      /**
175       * The seed update value for default constructors.  Must be
176 <     * greater or equal to 13. Otherwise, the value is arbitrary.
176 >     * 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;
179 >    private static final long DEFAULT_SEED_GAMMA = 0x9e3779b97f4a7c15L;
180  
181      /**
182       * The value 13 with 64bit sign bit set. Used in the signed
# Line 253 | Line 258 | public class SplittableRandom {
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
277       * method split. Establishes the initial seed for this instance,
278       * and uses the given splitSeed to establish gamma, as well as the
# Line 263 | Line 283 | public class SplittableRandom {
283          this.seed = seed;
284          long s = splitSeed, g;
285          do { // ensure gamma >= 13, considered as an unsigned integer
286 <            s = addGammaModGeorge(s, GAMMA_GAMMA);
287 <            g = mix64(s);
288 <        } while (g >= 0L && g < 13L);
286 >            s += GAMMA_GAMMA;
287 >            if (s >= GAMMA_PRIME)
288 >                s -= GAMMA_PRIME;
289 >            g = mix57(s);
290 >        } while (g < 13L);
291          this.gamma = g;
292          this.nextSplit = s;
293      }
# Line 376 | Line 398 | public class SplittableRandom {
398          int r = mix32(nextSeed());
399          if (origin < bound) {
400              int n = bound - origin, m = n - 1;
401 <            if ((n & m) == 0L)
401 >            if ((n & m) == 0)
402                  r = (r & m) + origin;
403              else if (n > 0) {
404                  for (int u = r >>> 1;
# Line 420 | Line 442 | public class SplittableRandom {
442       * @param seed the initial seed
443       */
444      public SplittableRandom(long seed) {
445 <        this(seed, 0);
445 >        this(seed, 0L);
446      }
447  
448      /**
# Line 476 | Line 498 | public class SplittableRandom {
498          // Specialize internalNextInt for origin 0
499          int r = mix32(nextSeed());
500          int m = bound - 1;
501 <        if ((bound & m) == 0L) // power of two
501 >        if ((bound & m) == 0) // power of two
502              r &= m;
503          else { // reject over-represented candidates
504              for (int u = r >>> 1;

Diff Legend

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