--- jsr166/src/main/java/util/SplittableRandom.java 2013/07/21 14:02:23 1.12 +++ jsr166/src/main/java/util/SplittableRandom.java 2013/07/25 13:19:09 1.13 @@ -115,35 +115,33 @@ public class SplittableRandom { * are encountered; see method addGammaModGeorge. For this to * work, initial gamma values must be at least 13. * - * 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. - * * The mix64 bit-mixing function called by nextLong and other * methods computes the same value as the "64-bit finalizer" * function in Austin Appleby's MurmurHash3 algorithm. See * http://code.google.com/p/smhasher/wiki/MurmurHash3 , which * comments: "The constants for the finalizers were generated by a * simple simulated-annealing algorithm, and both avalanche all - * bits of 'h' to within 0.25% bias." It also appears to work to - * use instead any of the variants proposed by David Stafford at - * http://zimbry.blogspot.com/2011/09/better-bit-mixing-improving-on.html - * but these variants have not yet been tested as thoroughly - * in the context of the implementation of SplittableRandom. + * bits of 'h' to within 0.25% bias." + * + * The value of gamma differs for each instance across a series of + * splits, and is generated using an independent 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. Gammas are treated as 57bit values, + * advancing by adding GAMMA_GAMMA mod GAMMA_PRIME, and bit-mixed + * with a 57-bit version of mix, using the "Mix01" multiplicative + * constants for MurmurHash3 described by David Stafford + * (http://zimbry.blogspot.com/2011/09/better-bit-mixing-improving-on.html). + * The value of GAMMA_GAMMA is arbitrary (except must be at least + * 13 and less than GAMMA_PRIME), but because it serves as the + * base of split sequences, should be subject to validation of + * consequent random number quality metrics. * * The mix32 function used for nextInt just consists of two of the - * five lines of mix64; avalanche testing shows that the 64-bit result - * has its top 32 bits avalanched well, though not the bottom 32 bits. - * DieHarder tests show that it is adequate for generating one - * random int from the 64-bit result of nextSeed. + * five lines of mix64; avalanche testing shows that the 64-bit + * result has its top 32 bits avalanched well, though not the + * bottom 32 bits. DieHarder tests show that it is adequate for + * generating one random int from the 64-bit result of nextSeed. * * Support for the default (no-argument) constructor relies on an * AtomicLong (defaultSeedGenerator) to help perform the @@ -161,17 +159,24 @@ public class SplittableRandom { */ /** + * The prime modulus for gamma values. + */ + private static final long GAMMA_PRIME = (1L << 57) - 13L; + + /** * The value for producing new gamma values. Must be greater or - * equal to 13. Otherwise, the value is arbitrary subject to - * validation of the resulting statistical quality of splits. + * equal to 13 and less than GAMMA_PRIME. Otherwise, the value is + * arbitrary subject to validation of the resulting statistical + * quality of splits. */ - private static final long GAMMA_GAMMA = 0xF2281E2DBA6606F3L; + private static final long GAMMA_GAMMA = 0x00aae38294f712aabL; /** * The seed update value for default constructors. Must be - * greater or equal to 13. Otherwise, the value is arbitrary. + * greater or equal to 13. Otherwise, the value is arbitrary + * subject to quality checks. */ - private static final long DEFAULT_SEED_GAMMA = 0xBD24B73A95FB84D9L; + private static final long DEFAULT_SEED_GAMMA = 0x9e3779b97f4a7c15L; /** * The value 13 with 64bit sign bit set. Used in the signed @@ -253,6 +258,21 @@ public class SplittableRandom { } /** + * Returns a 57-bit mixed transformation of its argument. See + * above for explanation. + */ + private static long mix57(long z) { + z ^= (z >>> 33); + z *= 0x7fb5d329728ea185L; + z &= 0x01FFFFFFFFFFFFFFL; + z ^= (z >>> 33); + z *= 0x81dadef4bc2dd44dL; + z &= 0x01FFFFFFFFFFFFFFL; + z ^= (z >>> 33); + return z; + } + + /** * 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 @@ -263,9 +283,11 @@ public class SplittableRandom { 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); + s += GAMMA_GAMMA; + if (s >= GAMMA_PRIME) + s -= GAMMA_PRIME; + g = mix57(s); + } while (g < 13L); this.gamma = g; this.nextSplit = s; } @@ -376,7 +398,7 @@ public class SplittableRandom { int r = mix32(nextSeed()); if (origin < bound) { int n = bound - origin, m = n - 1; - if ((n & m) == 0L) + if ((n & m) == 0) r = (r & m) + origin; else if (n > 0) { for (int u = r >>> 1; @@ -420,7 +442,7 @@ public class SplittableRandom { * @param seed the initial seed */ public SplittableRandom(long seed) { - this(seed, 0); + this(seed, 0L); } /** @@ -476,7 +498,7 @@ public class SplittableRandom { // Specialize internalNextInt for origin 0 int r = mix32(nextSeed()); int m = bound - 1; - if ((bound & m) == 0L) // power of two + if ((bound & m) == 0) // power of two r &= m; else { // reject over-represented candidates for (int u = r >>> 1;