--- jsr166/src/main/java/util/SplittableRandom.java 2013/07/16 12:32:05 1.11 +++ jsr166/src/main/java/util/SplittableRandom.java 2013/08/05 13:58:02 1.14 @@ -25,6 +25,7 @@ package java.util; +import java.security.SecureRandom; import java.util.concurrent.atomic.AtomicLong; import java.util.Spliterator; import java.util.function.IntConsumer; @@ -114,43 +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, a "genuinely random" number from a - * radioactive decay reading (obtained from - * http://www.fourmilab.ch/hotbits/) meeting the above range - * constraint. Using a fixed constant maintains the invariant that - * the value of gamma is the same for every instance that is at - * the same split-distance from their common root. (Note: there is - * nothing especially magic about obtaining this constant from a - * "truly random" physical source rather than just choosing one - * arbitrarily; using "hotbits" was merely an aesthetically pleasing - * choice. In either case, good statistical behavior of the - * algorithm should be, and was, verified by using the DieHarder - * test suite.) - * * 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 "Mix13" 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 @@ -158,31 +149,34 @@ public class SplittableRandom { * SplittableRandom. Unlike other cases, this split must be * performed in a thread-safe manner. We use * AtomicLong.compareAndSet as the (typically) most efficient - * mechanism. To bootstrap, we start off using a function of the - * current System time as seed, and update using another - * "genuinely random" constant DEFAULT_SEED_GAMMA. The default - * constructor uses GAMMA_GAMMA, not 0, for its splitSeed argument - * (addGammaModGeorge(0, GAMMA_GAMMA) == GAMMA_GAMMA) to reflect - * that each is split from this root generator, even though the - * root is not explicitly represented as a SplittableRandom. When - * establishing the initial seed, we use both - * System.currentTimeMillis and System.nanoTime(), to avoid - * regularities that may occur if using either alone. + * mechanism. To bootstrap, we start off using a SecureRandom + * initial default seed, and update using a fixed + * DEFAULT_SEED_GAMMA. The default constructor uses GAMMA_GAMMA, + * not 0, for its splitSeed argument (addGammaModGeorge(0, + * GAMMA_GAMMA) == GAMMA_GAMMA) to reflect that each is split from + * this root generator, even though the root is not explicitly + * represented as a SplittableRandom. */ /** - * The "genuinely random" value for producing new gamma values. - * The value is arbitrary, subject to the requirement that it be - * greater or equal to 13. + * The prime modulus for gamma values. */ - private static final long GAMMA_GAMMA = 0xF2281E2DBA6606F3L; + private static final long GAMMA_PRIME = (1L << 57) - 13L; /** - * The "genuinely random" seed update value for default constructors. - * The value is arbitrary, subject to the requirement that it be - * greater or equal to 13. + * The value for producing new gamma values. Must be greater or + * 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 DEFAULT_SEED_GAMMA = 0xBD24B73A95FB84D9L; + 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 + * subject to quality checks. + */ + private static final long DEFAULT_SEED_GAMMA = 0x9e3779b97f4a7c15L; /** * The value 13 with 64bit sign bit set. Used in the signed @@ -200,8 +194,7 @@ public class SplittableRandom { * The next seed for default constructors. */ private static final AtomicLong defaultSeedGenerator = - new AtomicLong(mix64(System.currentTimeMillis()) ^ - mix64(System.nanoTime())); + new AtomicLong(getInitialDefaultSeed()); /** * The seed, updated only via method nextSeed. @@ -265,6 +258,19 @@ public class SplittableRandom { } /** + * Returns a 57-bit mixed transformation of its argument. See + * above for explanation. + */ + private static long mix57(long z) { + z = (z ^ (z >>> 30)) * 0xbf58476d1ce4e5b9L; + z &= 0x01FFFFFFFFFFFFFFL; + z = (z ^ (z >>> 27)) * 0x94d049bb133111ebL; + z &= 0x01FFFFFFFFFFFFFFL; + z ^= (z >>> 31); + 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 @@ -275,9 +281,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; } @@ -302,6 +310,17 @@ public class SplittableRandom { return mix64(newSeed); } + /** + * Returns an initial default seed. + */ + private static long getInitialDefaultSeed() { + byte[] seedBytes = java.security.SecureRandom.getSeed(8); + long s = (long)(seedBytes[0]) & 0xffL; + for (int i = 1; i < 8; ++i) + s = (s << 8) | ((long)(seedBytes[i]) & 0xffL); + return s; + } + /* * Internal versions of nextX methods used by streams, as well as * the public nextX(origin, bound) methods. These exist mainly to @@ -377,7 +396,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; @@ -421,7 +440,7 @@ public class SplittableRandom { * @param seed the initial seed */ public SplittableRandom(long seed) { - this(seed, 0); + this(seed, 0L); } /** @@ -477,7 +496,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;