--- a/src/java.base/share/classes/java/util/random/L128X256MixRandom.java Thu Aug 29 11:33:26 2019 -0300
+++ b/src/java.base/share/classes/java/util/random/L128X256MixRandom.java Thu Nov 14 08:54:56 2019 -0400
@@ -28,7 +28,7 @@
import java.math.BigInteger;
import java.util.concurrent.atomic.AtomicLong;
import java.util.random.RandomGenerator.SplittableGenerator;
-import java.util.random.RandomSupport.AbstractSplittableGenerator;
+import java.util.random.RandomSupport.AbstractSplittableWithBrineGenerator;
/**
@@ -55,9 +55,10 @@
* {@link L128X256MixRandom} is a specific member of the LXM family of algorithms
* for pseudorandom number generators. Every LXM generator consists of two
* subgenerators; one is an LCG (Linear Congruential Generator) and the other is
- * an Xorshift generator. Each output of an LXM generator is the sum of one
- * output from each subgenerator, possibly processed by a final mixing function
- * (and {@link L128X256MixRandom} does use a mixing function).
+ * an Xorshift generator. Each output of an LXM generator is the result of
+ * combining state from the LCG with state from the Xorshift generator by
+ * using a Mixing function (and then the state of the LCG and the state of the
+ * Xorshift generator are advanced).
* <p>
* The LCG subgenerator for {@link L128X256MixRandom} has an update step of the
* form {@code s = m * s + a}, where {@code s}, {@code m}, and {@code a} are all
@@ -74,7 +75,8 @@
* and {@code x3}, which can take on any values provided that they are not all zero.
* The period of this subgenerator is 2<sup>256</sup>-1.
* <p>
- * The mixing function for {@link L128X256MixRandom} is the 64-bit MurmurHash3 finalizer.
+ * The mixing function for {@link L128X256MixRandom} is {@link RandomSupport.mixLea64}
+ * applied to the argument {@code (sh + x0)}, where {@code sh} is the high half of {@code s}.
* <p>
* Because the periods 2<sup>128</sup> and 2<sup>256</sup>-1 of the two subgenerators
* are relatively prime, the <em>period</em> of any single {@link L128X256MixRandom} object
@@ -86,34 +88,16 @@
* <p>
* The 64-bit values produced by the {@code nextLong()} method are exactly equidistributed.
* For any specific instance of {@link L128X256MixRandom}, over the course of its cycle each
- * of the 2<sup>64</sup> possible {@code long} values will be produced 2<sup>256</sup>-1 times.
- * The values produced by the {@code nextInt()}, {@code nextFloat()}, and {@code nextDouble()}
- * methods are likewise exactly equidistributed.
- * <p>
- * In fact, the 64-bit values produced by the {@code nextLong()} method are exactly
- * 2-equidistributed. For any specific instance of {@link L128X256MixRandom}, consider
- * the (overlapping) length-2 subsequences of the cycle of 64-bit values produced by
- * {@code nextLong()} (assuming no other methods are called that would affect the state).
- * There are 2<sup>128</sup>(2<sup>256</sup>-1) such subsequences, and each subsequence,
- * which consists of 2 64-bit values, can have one of 2<sup>128</sup> values, and each
- * such value occurs 2<sup>256</sup>-1 times. The values produced by the {@code nextInt()},
- * {@code nextFloat()}, and {@code nextDouble()} methods are likewise exactly 2-equidistributed.
+ * of the 2<sup>64</sup> possible {@code long} values will be produced
+ * 2<sup>64</sup>(2<sup>256</sup>-1) times. The values produced by the {@code nextInt()},
+ * {@code nextFloat()}, and {@code nextDouble()} methods are likewise exactly equidistributed.
* <p>
- * Moreover, the 64-bit values produced by the {@code nextLong()} method are 4-equidistributed.
- * To be precise: for any specific instance of {@link L128X256MixRandom}, consider
- * the (overlapping) length-4 subsequences of the cycle of 64-bit values produced by
- * {@code nextLong()} (assuming no other methods are called that would affect the state).
- * There are <sup>128</sup>(2<sup>256</sup>-1) such subsequences, and each subsequence,
- * which consists of 4 64-bit values, can have one of 2<sup>256</sup> values. Of those
- * 2<sup>256</sup> subsequence values, nearly all of them (2<sup>256</sup>-2<sup>128</sup>)
- * occur 2<sup>128</sup> times over the course of the entire cycle, and the other
- * 2<sup>128</sup> subsequence values occur only 2<sup>128</sup>-1 times. So the ratio
- * of the probability of getting one of the less common subsequence values and the
- * probability of getting one of the more common subsequence values is 1-2<sup>-128</sup>.
- * (Note that the set of 2<sup>128</sup> less-common subsequence values will differ from
- * one instance of {@link L128X256MixRandom} to another, as a function of the additive
- * parameter of the LCG.) The values produced by the {@code nextInt()}, {@code nextFloat()},
- * and {@code nextDouble()} methods are likewise 4-equidistributed.
+ * Moreover, 64-bit values produced by the {@code nextLong()} method are conjectured to be
+ * "very nearly" 4-equidistributed: all possible quadruples of 64-bit values are generated,
+ * and some pairs occur more often than others, but only very slightly more often.
+ * However, this conjecture has not yet been proven mathematically.
+ * If this conjecture is true, then the values produced by the {@code nextInt()}, {@code nextFloat()},
+ * and {@code nextDouble()} methods are likewise approximately 4-equidistributed.
* <p>
* Method {@link #split} constructs and returns a new {@link L128X256MixRandom}
* instance that shares no mutable state with the current instance. However, with
@@ -146,7 +130,7 @@
*
* @since 14
*/
-public final class L128X256MixRandom extends AbstractSplittableGenerator {
+public final class L128X256MixRandom extends AbstractSplittableWithBrineGenerator {
/*
* Implementation Overview.
@@ -193,28 +177,20 @@
BigInteger.ONE.shiftLeft(256).subtract(BigInteger.ONE).shiftLeft(128);
/*
- * The multiplier used in the LCG portion of the algorithm is 2**64 + m;
- * where m is taken from
- * Pierre L'Ecuyer, Tables of linear congruential generators of
- * different sizes and good lattice structure, <em>Mathematics of
- * Computation</em> 68, 225 (January 1999), pages 249-260,
- * Table 4 (first multiplier for size 2<sup>64</sup>).
- *
- * This is almost certainly not the best possible 128-bit multiplier
- * for an LCG, but it is sufficient for our purposes here; because
- * is is larger than 2**64, the 64-bit values produced by nextLong()
- * are exactly 2-equidistributed, and the fact that it is of the
- * form (2**64 + m) simplifies the code, given that we have only
- * 64-bit arithmetic to work with.
+ * Low half of multiplier used in the LCG portion of the algorithm;
+ * the overall multiplier is (2**64 + ML).
+ * Chosen based on research by Sebastiano Vigna and Guy Steele (2019).
+ * The spectral scores for dimensions 2 through 8 for the multiplier 0x1d605bbb58c8abbfdLL
+ * are [0.991889, 0.907938, 0.830964, 0.837980, 0.780378, 0.797464, 0.761493].
*/
- private static final long M = 2862933555777941757L;
+ private static final long ML = 0xd605bbb58c8abbfdL;
/* ---------------- instance fields ---------------- */
/**
* The parameter that is used as an additive constant for the LCG.
- * Must be odd.
+ * Must be odd (therefore al must be odd).
*/
private final long ah, al;
@@ -252,11 +228,12 @@
this.x3 = x3;
// If x0, x1, x2, and x3 are all zero, we must choose nonzero values.
if ((x0 | x1 | x2 | x3) == 0) {
+ long v = sh;
// At least three of the four values generated here will be nonzero.
- this.x0 = RandomSupport.mixStafford13(sh += RandomSupport.GOLDEN_RATIO_64);
- this.x1 = RandomSupport.mixStafford13(sh += RandomSupport.GOLDEN_RATIO_64);
- this.x2 = RandomSupport.mixStafford13(sh += RandomSupport.GOLDEN_RATIO_64);
- this.x3 = RandomSupport.mixStafford13(sh + RandomSupport.GOLDEN_RATIO_64);
+ this.x0 = RandomSupport.mixStafford13(v += RandomSupport.GOLDEN_RATIO_64);
+ this.x1 = RandomSupport.mixStafford13(v += RandomSupport.GOLDEN_RATIO_64);
+ this.x2 = RandomSupport.mixStafford13(v += RandomSupport.GOLDEN_RATIO_64);
+ this.x3 = RandomSupport.mixStafford13(v + RandomSupport.GOLDEN_RATIO_64);
}
}
@@ -277,7 +254,7 @@
// The seed is hashed by mixStafford13 to produce the initial `x0`,
// which will then be used to produce the first generated value.
// The other x values are filled in as if by a SplitMix PRNG with
- // GOLDEN_RATIO_64 as the gamma value and Stafford13 as the mixer.
+ // GOLDEN_RATIO_64 as the gamma value and mixStafford13 as the mixer.
this(RandomSupport.mixMurmur64(seed ^= RandomSupport.SILVER_RATIO_64),
RandomSupport.mixMurmur64(seed += RandomSupport.GOLDEN_RATIO_64),
0,
@@ -323,29 +300,31 @@
}
/* ---------------- public methods ---------------- */
-
+
/**
- * Constructs and returns a new instance of {@link L128X256MixRandom}
- * that shares no mutable state with this instance.
+ * Given 63 bits of "brine", constructs and returns a new instance of
+ * {@code L128X256MixRandom} that shares no mutable state with this instance.
* However, with very high probability, the set of values collectively
* generated by the two objects has the same statistical properties as if
* same the quantity of values were generated by a single thread using
- * a single {@link L128X256MixRandom} object. Either or both of the two
+ * a single {@code L128X256MixRandom} object. Either or both of the two
* objects may be further split using the {@code split} method,
* and the same expected statistical properties apply to the
* entire set of generators constructed by such recursive splitting.
*
- * @param source a {@link SplittableGenerator} instance to be used instead
+ * @param source a {@code SplittableGenerator} instance to be used instead
* of this one as a source of pseudorandom bits used to
* initialize the state of the new ones.
- * @return a new instance of {@link L128X256MixRandom}
+ * @param brine a long value, of which the low 63 bits are used to choose
+ * the {@code a} parameter for the new instance.
+ * @return a new instance of {@code L128X256MixRandom}
*/
- public L128X256MixRandom split(SplittableGenerator source) {
- // Literally pick a new instance "at random".
- return new L128X256MixRandom(source.nextLong(), source.nextLong(),
- source.nextLong(), source.nextLong(),
- source.nextLong(), source.nextLong(),
- source.nextLong(), source.nextLong());
+ public SplittableGenerator split(SplittableGenerator source, long brine) {
+ // Pick a new instance "at random", but use the brine for (the low half of) `a`.
+ return new L128X256MixRandom(source.nextLong(), brine << 1,
+ source.nextLong(), source.nextLong(),
+ source.nextLong(), source.nextLong(),
+ source.nextLong(), source.nextLong());
}
/**
@@ -354,12 +333,27 @@
* @return a pseudorandom {@code long} value
*/
public long nextLong() {
- final long z = sh + x0;
- // The LCG: in effect, s = ((1LL << 64) + M) * s + a, if only we had 128-bit arithmetic.
- final long u = M * sl;
- sh = (M * sh) + Math.multiplyHigh(M, sl) + sl + ah;
+ // Compute the result based on current state information
+ // (this allows the computation to be overlapped with state update).
+ final long result = RandomSupport.mixLea64(sh + x0);
+
+ // Update the LCG subgenerator
+ // The LCG is, in effect, s = ((1LL << 64) + ML) * s + a, if only we had 128-bit arithmetic.
+ final long u = ML * sl;
+ // Note that Math.multiplyHigh computes the high half of the product of signed values,
+ // but what we need is the high half of the product of unsigned values; for this we use the
+ // formula "unsignedMultiplyHigh(a, b) = multiplyHigh(a, b) + ((a >> 63) & b) + ((b >> 63) & a)";
+ // in effect, each operand is added to the result iff the sign bit of the other operand is 1.
+ // (See Henry S. Warren, Jr., _Hacker's Delight_ (Second Edition), Addison-Wesley (2013),
+ // Section 8-3, p. 175; or see the First Edition, Addison-Wesley (2003), Section 8-3, p. 133.)
+ // If Math.unsignedMultiplyHigh(long, long) is ever implemented, the following line can become:
+ // sh = (ML * sh) + Math.unsignedMultiplyHigh(ML, sl) + sl + ah;
+ // and this entire comment can be deleted.
+ sh = (ML * sh) + (Math.multiplyHigh(ML, sl) + ((ML >> 63) & sl) + ((sl >> 63) & ML)) + sl + ah;
sl = u + al;
if (Long.compareUnsigned(sl, u) < 0) ++sh; // Handle the carry propagation from low half to high half.
+
+ // Update the Xorshift subgenerator
long q0 = x0, q1 = x1, q2 = x2, q3 = x3;
{ // xoshiro256 1.0
long t = q1 << 17;
@@ -371,9 +365,15 @@
q3 = Long.rotateLeft(q3, 45);
}
x0 = q0; x1 = q1; x2 = q2; x3 = q3;
- return RandomSupport.mixLea64(z); // mixing function
+ return result;
}
+ /**
+ * Returns the period of this random generator.
+ *
+ * @return a {@link BigInteger} whose value is the number of distinct possible states of this
+ * {@link RandomGenerator} object (2<sup>128</sup>(2<sup>256</sup>-1)).
+ */
public BigInteger period() {
return PERIOD;
}
--- a/src/java.base/share/classes/java/util/random/L32X64MixRandom.java Thu Aug 29 11:33:26 2019 -0300
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,335 +0,0 @@
-/*
- * Copyright (c) 2013, 2019, Oracle and/or its affiliates. All rights reserved.
- * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
- *
- * This code is free software; you can redistribute it and/or modify it
- * under the terms of the GNU General Public License version 2 only, as
- * published by the Free Software Foundation. Oracle designates this
- * particular file as subject to the "Classpath" exception as provided
- * by Oracle in the LICENSE file that accompanied this code.
- *
- * This code is distributed in the hope that it will be useful, but WITHOUT
- * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
- * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
- * version 2 for more details (a copy is included in the LICENSE file that
- * accompanied this code).
- *
- * You should have received a copy of the GNU General Public License version
- * 2 along with this work; if not, write to the Free Software Foundation,
- * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
- *
- * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
- * or visit www.oracle.com if you need additional information or have any
- * questions.
- */
-
-package java.util.random;
-
-import java.math.BigInteger;
-import java.util.concurrent.atomic.AtomicLong;
-import java.util.random.RandomGenerator.SplittableGenerator;
-import java.util.random.RandomSupport.AbstractSplittableGenerator;
-
-/**
- * A generator of uniform pseudorandom values applicable for use in
- * (among other contexts) isolated parallel computations that may
- * generate subtasks. Class {@link L32X64MixRandom} implements
- * interfaces {@link RandomGenerator} and {@link SplittableGenerator},
- * and therefore supports methods for producing pseudorandomly chosen
- * numbers of type {@code int}, {@code long}, {@code float}, and {@code double}
- * as well as creating new split-off {@link L32X64MixRandom} objects,
- * with similar usages as for class {@link java.util.SplittableRandom}.
- * <p>
- * Series of generated values pass the TestU01 BigCrush and PractRand test suites
- * that measure independence and uniformity properties of random number generators.
- * (Most recently validated with
- * <a href="http://simul.iro.umontreal.ca/testu01/tu01.html">version 1.2.3 of TestU01</a>
- * and <a href="http://pracrand.sourceforge.net">version 0.90 of PractRand</a>.
- * Note that TestU01 BigCrush was used to test not only values produced by the {@code nextLong()}
- * method but also the result of bit-reversing each value produced by {@code nextLong()}.)
- * These tests validate only the methods for certain
- * types and ranges, but similar properties are expected to hold, at
- * least approximately, for others as well.
- * <p>
- * {@link L32X64MixRandom} is a specific member of the LXM family of algorithms
- * for pseudorandom number generators. Every LXM generator consists of two
- * subgenerators; one is an LCG (Linear Congruential Generator) and the other is
- * an Xorshift generator. Each output of an LXM generator is the sum of one
- * output from each subgenerator, possibly processed by a final mixing function
- * (and {@link L32X64MixRandom} does use a mixing function).
- * <p>
- * The LCG subgenerator for {@link L32X64MixRandom} has an update step of the
- * form {@code s = m * s + a}, where {@code s}, {@code m}, and {@code a} are all
- * of type {@code int}; {@code s} is the mutable state, the multiplier {@code m}
- * is fixed (the same for all instances of {@link L32X64MixRandom}) and the addend
- * {@code a} is a parameter (a final field of the instance). The parameter
- * {@code a} is required to be odd (this allows the LCG to have the maximal
- * period, namely 2<sup>32</sup>); therefore there are 2<sup>31</sup> distinct choices
- * of parameter.
- * <p>
- * The Xorshift subgenerator for {@link L32X64MixRandom} is the {@code xoroshiro64} algorithm,
- * version 1.0 (parameters 26, 9, 13), without any final scrambler such as "+" or "**".
- * Its state consists of two {@code int} fields {@code x0} and {@code x1},
- * which can take on any values provided that they are not both zero.
- * The period of this subgenerator is 2<sup>64</sup>-1.
- * <p>
- * The mixing function for {@link L32X64MixRandom} is the "starstar" mixing function.
- * <p>
- * Because the periods 2<sup>32</sup> and 2<sup>64</sup>-1 of the two subgenerators
- * are relatively prime, the <em>period</em> of any single {@link L32X64MixRandom} object
- * (the length of the series of generated 32-bit values before it repeats) is the product
- * of the periods of the subgenerators, that is, 2<sup>32</sup>(2<sup>64</sup>-1),
- * which is just slightly smaller than 2<sup>96</sup>. Moreover, if two distinct
- * {@link L32X64MixRandom} objects have different {@code a} parameters, then their
- * cycles of produced values will be different.
- * <p>
- * The 32-bit values produced by the {@code nextInt()} method are exactly equidistributed.
- * For any specific instance of {@link L32X64MixRandom}, over the course of its cycle each
- * of the 2<sup>32</sup> possible {@code int} values will be produced 2<sup>64</sup>-1 times.
- * The values produced by the {@code nextFloat()} method are likewise exactly equidistributed.
- * <p>
- * In fact, the 32-bit values produced by the {@code nextInt()} method are 2-equidistributed.
- * To be precise: for any specific instance of {@link L32X64MixRandom}, consider
- * the (overlapping) length-2 subsequences of the cycle of 64-bit values produced by
- * {@code nextInt()} (assuming no other methods are called that would affect the state).
- * There are 2<sup>32</sup>(2<sup>64</sup>-1) such subsequences, and each subsequence,
- * which consists of 2 32-bit values, can have one of 2<sup>64</sup> values. Of those
- * 2<sup>64</sup> subsequence values, nearly all of them (2<sup>64</sup>-2<sup>32</sup>)
- * occur 2<sup>32</sup> times over the course of the entire cycle, and the other
- * 2<sup>32</sup> subsequence values occur only 2<sup>32</sup>-1 times. So the ratio
- * of the probability of getting one of the less common subsequence values and the
- * probability of getting one of the more common subsequence values is 1-2<sup>-32</sup>.
- * (Note that the set of 2<sup>32</sup> less-common subsequence values will differ from
- * one instance of {@link L32X64MixRandom} to another, as a function of the additive
- * parameter of the LCG.) As a consequence, the values produced by the {@code nextFloat()}
- * method are likewise 2-equidistributed, and the values produced by the {@code nextLong()}
- * and {@code nextDouble()} methods are equidistributed (but not 2-equidistributed).
- * <p>
- * Method {@link #split} constructs and returns a new {@link L32X64MixRandom}
- * instance that shares no mutable state with the current instance. However, with
- * very high probability, the values collectively generated by the two objects
- * have the same statistical properties as if the same quantity of values were
- * generated by a single thread using a single {@link L32X64MixRandom} object.
- * This is because, with high probability, distinct {@link L32X64MixRandom} objects
- * have distinct {@code a} parameters and therefore use distinct members of the
- * algorithmic family; and even if their {@code a} parameters are the same, with
- * very high probability they will traverse different parts of their common state
- * cycle.
- * <p>
- * As with {@link java.util.SplittableRandom}, instances of
- * {@link L32X64MixRandom} are <em>not</em> thread-safe.
- * They are designed to be split, not shared, across threads. For
- * example, a {@link java.util.concurrent.ForkJoinTask} fork/join-style
- * computation using random numbers might include a construction
- * of the form {@code new Subtask(someL32X64MixRandom.split()).fork()}.
- * <p>
- * This class provides additional methods for generating random
- * streams, that employ the above techniques when used in
- * {@code stream.parallel()} mode.
- * <p>
- * Instances of {@link L32X64MixRandom} are not cryptographically
- * secure. Consider instead using {@link java.security.SecureRandom}
- * in security-sensitive applications. Additionally,
- * default-constructed instances do not use a cryptographically random
- * seed unless the {@linkplain System#getProperty system property}
- * {@code java.util.secureRandomSeed} is set to {@code true}.
- *
- * @since 14
- */
-public final class L32X64MixRandom extends AbstractSplittableGenerator {
-
- /*
- * Implementation Overview.
- *
- * The split operation uses the current generator to choose four new 64-bit
- * int values that are then used to initialize the parameter `a` and the
- * state variables `s`, `x0`, and `x1` for a newly constructed generator.
- *
- * With high probability, no two generators so chosen
- * will have the same `a` parameter, and testing has indicated
- * that the values generated by two instances of {@link L32X64MixRandom}
- * will be (approximately) independent if have different values for `a`.
- *
- * The default (no-argument) constructor, in essence, uses
- * "defaultGen" to generate four new 32-bit values for the same
- * purpose. Multiple generators created in this way will certainly
- * differ in their `a` parameters. The defaultGen state must be accessed
- * in a thread-safe manner, so we use an AtomicLong to represent
- * this state. To bootstrap the defaultGen, we start off using a
- * seed based on current time unless the
- * java.util.secureRandomSeed property is set. This serves as a
- * slimmed-down (and insecure) variant of SecureRandom that also
- * avoids stalls that may occur when using /dev/random.
- *
- * File organization: First static fields, then instance
- * fields, then constructors, then instance methods.
- */
-
- /* ---------------- static fields ---------------- */
-
- /**
- * The seed generator for default constructors.
- */
- private static final AtomicLong defaultGen = new AtomicLong(RandomSupport.initialSeed());
-
- /*
- * The period of this generator, which is (2**64 - 1) * 2**32.
- */
- private static final BigInteger PERIOD =
- BigInteger.ONE.shiftLeft(64).subtract(BigInteger.ONE).shiftLeft(32);
-
- /*
- * Multiplier used in the LCG portion of the algorithm, taken from
- * Pierre L'Ecuyer, Tables of linear congruential generators of
- * different sizes and good lattice structure, <em>Mathematics of
- * Computation</em> 68, 225 (January 1999), pages 249-260,
- * Table 4 (third multiplier for size 2<sup>32</sup>).
- */
-
- private static final int M = 32310901;
-
- /* ---------------- instance fields ---------------- */
-
- /**
- * The parameter that is used as an additive constant for the LCG.
- * Must be odd.
- */
- private final int a;
-
- /**
- * The per-instance state: s for the LCG; x0 and x1 for the xorshift.
- * At least one of x0 and x1 must be nonzero.
- */
- private int s, x0, x1;
-
- /* ---------------- constructors ---------------- */
-
- /**
- * Basic constructor that initializes all fields from parameters.
- * It then adjusts the field values if necessary to ensure that
- * all constraints on the values of fields are met.
- *
- * @param a additive parameter for the LCG
- * @param s initial state for the LCG
- * @param x0 first word of the initial state for the xorshift generator
- * @param x1 second word of the initial state for the xorshift generator
- */
- public L32X64MixRandom(int a, int s, int x0, int x1) {
- // Force a to be odd.
- this.a = a | 1;
- this.s = s;
- // If x0 and x1 are both zero, we must choose nonzero values.
- if ((x0 | x1) == 0) {
- // At least one of the two values generated here will be nonzero.
- this.x0 = RandomSupport.mixMurmur32(s += RandomSupport.GOLDEN_RATIO_32);
- this.x1 = RandomSupport.mixMurmur32(s + RandomSupport.GOLDEN_RATIO_32);
- }
- }
-
- /**
- * Creates a new instance of {@link L32X64MixRandom} using the
- * specified {@code long} value as the initial seed. Instances of
- * {@link L32X64MixRandom} created with the same seed in the same
- * program generate identical sequences of values.
- *
- * @param seed the initial seed
- */
- public L32X64MixRandom(long seed) {
- // Using a value with irregularly spaced 1-bits to xor the seed
- // argument tends to improve "pedestrian" seeds such as 0 or
- // other small integers. We may as well use SILVER_RATIO_64.
- //
- // The high half of the seed is hashed by mixMurmur32 to produce the `a` parameter.
- // The low half of the seed is hashed by mixMurmur32 to produce the initial `x0`,
- // which will then be used to produce the first generated value.
- // Then x1 is filled in as if by a SplitMix PRNG with
- // GOLDEN_RATIO_32 as the gamma value and Murmur32 as the mixer.
- this(RandomSupport.mixMurmur32((int)((seed ^= RandomSupport.SILVER_RATIO_64) >>> 32)),
- 1,
- RandomSupport.mixLea32((int)(seed)),
- RandomSupport.mixLea32((int)(seed) + RandomSupport.GOLDEN_RATIO_32));
- }
-
- /**
- * Creates a new instance of {@link L32X64MixRandom} that is likely to
- * generate sequences of values that are statistically independent
- * of those of any other instances in the current program execution,
- * but may, and typically does, vary across program invocations.
- */
- public L32X64MixRandom() {
- // Using GOLDEN_RATIO_64 here gives us a good Weyl sequence of values.
- this(defaultGen.getAndAdd(RandomSupport.GOLDEN_RATIO_64));
- }
-
- /**
- * Creates a new instance of {@link L32X64MixRandom} using the specified array of
- * initial seed bytes. Instances of {@link L32X64MixRandom} created with the same
- * seed array in the same program execution generate identical sequences of values.
- *
- * @param seed the initial seed
- */
- public L32X64MixRandom(byte[] seed) {
- // Convert the seed to 4 int values, of which the last 2 are not all zero.
- int[] data = RandomSupport.convertSeedBytesToInts(seed, 4, 2);
- int a = data[0], s = data[1], x0 = data[2], x1 = data[3];
- // Force a to be odd.
- this.a = a | 1;
- this.s = s;
- this.x0 = x0;
- this.x1 = x1;
- }
-
- /* ---------------- public methods ---------------- */
-
- /**
- * Constructs and returns a new instance of {@link L32X64MixRandom} that shares no mutable state
- * with this instance. However, with very high probability, the set of values collectively
- * generated by the two objects has the same statistical properties as if same the quantity of
- * values were generated by a single thread using a single {@link L32X64MixRandom} object.
- * Either or both of the two objects may be further split using the {@code split} method, and
- * the same expected statistical properties apply to the entire set of generators constructed by
- * such recursive splitting.
- *
- * @param source a {@link SplittableGenerator} instance to be used instead of this one as
- * a source of pseudorandom bits used to initialize the state of the new ones.
- *
- * @return a new instance of {@link L32X64MixRandom}
- */
- public L32X64MixRandom split(SplittableGenerator source) {
- // Literally pick a new instance "at random".
- return new L32X64MixRandom(source.nextInt(), source.nextInt(),
- source.nextInt(), source.nextInt());
- }
-
- /**
- * Returns a pseudorandom {@code int} value.
- *
- * @return a pseudorandom {@code int} value
- */
- public int nextInt() {
- final int z = s + x0;
- s = M * s + a; // LCG
- int q0 = x0, q1 = x1;
- { // xoroshiro64
- q1 ^= q0;
- q0 = Integer.rotateLeft(q0, 26);
- q0 = q0 ^ q1 ^ (q1 << 9);
- q1 = Integer.rotateLeft(q1, 13);
- }
- x0 = q0; x1 = q1;
- return Integer.rotateLeft(z * 5, 7) * 9; // "starstar" mixing function
- }
-
- /**
- * Returns a pseudorandom {@code long} value.
- *
- * @return a pseudorandom {@code long} value
- */
- public long nextLong() {
- return ((long)(nextInt()) << 32) | nextInt();
- }
-
- public BigInteger period() {
- return PERIOD;
- }
-}
--- a/src/java.base/share/classes/java/util/random/L64X1024MixRandom.java Thu Aug 29 11:33:26 2019 -0300
+++ b/src/java.base/share/classes/java/util/random/L64X1024MixRandom.java Thu Nov 14 08:54:56 2019 -0400
@@ -28,7 +28,7 @@
import java.math.BigInteger;
import java.util.concurrent.atomic.AtomicLong;
import java.util.random.RandomGenerator.SplittableGenerator;
-import java.util.random.RandomSupport.AbstractSplittableGenerator;
+import java.util.random.RandomSupport.AbstractSplittableWithBrineGenerator;
/**
* A generator of uniform pseudorandom values applicable for use in
@@ -54,9 +54,10 @@
* {@link L64X1024MixRandom} is a specific member of the LXM family of algorithms
* for pseudorandom number generators. Every LXM generator consists of two
* subgenerators; one is an LCG (Linear Congruential Generator) and the other is
- * an Xorshift generator. Each output of an LXM generator is the sum of one
- * output from each subgenerator, possibly processed by a final mixing function
- * (and {@link L64X1024MixRandom} does use a mixing function).
+ * an Xorshift generator. Each output of an LXM generator is the result of
+ * combining state from the LCG with state from the Xorshift generator by
+ * using a Mixing function (and then the state of the LCG and the state of the
+ * Xorshift generator are advanced).
* <p>
* The LCG subgenerator for {@link L64X1024MixRandom} has an update step of the
* form {@code s = m * s + a}, where {@code s}, {@code m}, and {@code a} are all
@@ -73,7 +74,9 @@
* which can take on any values provided that they are not all zero.
* The period of this subgenerator is 2<sup>1024</sup>-1.
* <p>
- * The mixing function for {@link L64X256MixRandom} is the 64-bit MurmurHash3 finalizer.
+ * The mixing function for {@link L64X1024MixRandom} is {@link RandomSupport.mixLea64}
+ * applied to the argument {@code (s + s0)}, where {@code s0} is the most recently computed
+ * element of {@code x}.
* <p>
* Because the periods 2<sup>64</sup> and 2<sup>1024</sup>-1 of the two subgenerators
* are relatively prime, the <em>period</em> of any single {@link L64X1024MixRandom} object
@@ -98,8 +101,8 @@
* 2<sup>1024</sup> subsequence values, nearly all of them (2<sup>1024</sup>-2<sup>64</sup>)
* occur 2<sup>64</sup> times over the course of the entire cycle, and the other
* 2<sup>64</sup> subsequence values occur only 2<sup>64</sup>-1 times. So the ratio
- * of the probability of getting one of the less common subsequence values and the
- * probability of getting one of the more common subsequence values is 1-2<sup>-64</sup>.
+ * of the probability of getting any specific one of the less common subsequence values and the
+ * probability of getting any specific one of the more common subsequence values is 1-2<sup>-64</sup>.
* (Note that the set of 2<sup>64</sup> less-common subsequence values will differ from
* one instance of {@link L64X1024MixRandom} to another, as a function of the additive
* parameter of the LCG.) The values produced by the {@code nextInt()}, {@code nextFloat()},
@@ -136,7 +139,7 @@
*
* @since 14
*/
-public final class L64X1024MixRandom extends AbstractSplittableGenerator {
+public final class L64X1024MixRandom extends AbstractSplittableWithBrineGenerator {
/*
* Implementation Overview.
@@ -185,14 +188,13 @@
BigInteger.ONE.shiftLeft(N*64).subtract(BigInteger.ONE).shiftLeft(64);
/*
- * Multiplier used in the LCG portion of the algorithm, taken from
- * Pierre L'Ecuyer, Tables of linear congruential generators of
- * different sizes and good lattice structure, <em>Mathematics of
- * Computation</em> 68, 225 (January 1999), pages 249-260,
- * Table 4 (first multiplier for size 2<sup>64</sup>).
+ * Multiplier used in the LCG portion of the algorithm.
+ * Chosen based on research by Sebastiano Vigna and Guy Steele (2019).
+ * The spectral scores for dimensions 2 through 8 for the multiplier 0xd1342543de82ef95
+ * are [0.958602, 0.937479, 0.870757, 0.822326, 0.820405, 0.813065, 0.760215].
*/
- private static final long M = 2862933555777941757L;
+ private static final long M = 0xd1342543de82ef95L;
/* ---------------- instance fields ---------------- */
@@ -264,9 +266,10 @@
this.x[15] = x15;
// If x0, x1, ..., x15 are all zero (very unlikely), we must choose nonzero values.
if ((x0 | x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 | x12 | x13 | x14 | x15) == 0) {
+ long v = s;
// At least fifteen of the sixteen values generated here will be nonzero.
for (int j = 0; j < N; j++) {
- this.x[j] = RandomSupport.mixStafford13(s += RandomSupport.GOLDEN_RATIO_64);
+ this.x[j] = RandomSupport.mixStafford13(v += RandomSupport.GOLDEN_RATIO_64);
}
}
}
@@ -288,7 +291,7 @@
// The seed is hashed by mixStafford13 to produce the initial `x[0]`,
// which will then be used to produce the first generated value.
// The other x values are filled in as if by a SplitMix PRNG with
- // GOLDEN_RATIO_64 as the gamma value and Stafford13 as the mixer.
+ // GOLDEN_RATIO_64 as the gamma value and mixStafford13 as the mixer.
this(RandomSupport.mixMurmur64(seed ^= RandomSupport.SILVER_RATIO_64),
1,
RandomSupport.mixStafford13(seed),
@@ -341,27 +344,28 @@
}
/* ---------------- public methods ---------------- */
-
/**
- * Constructs and returns a new instance of {@link L64X1024MixRandom}
- * that shares no mutable state with this instance.
+ * Given 63 bits of "brine", constructs and returns a new instance of
+ * {@code L64X1024MixRandom} that shares no mutable state with this instance.
* However, with very high probability, the set of values collectively
* generated by the two objects has the same statistical properties as if
* same the quantity of values were generated by a single thread using
- * a single {@link L64X1024MixRandom} object. Either or both of the two
+ * a single {@code L64X1024MixRandom} object. Either or both of the two
* objects may be further split using the {@code split} method,
* and the same expected statistical properties apply to the
* entire set of generators constructed by such recursive splitting.
*
- * @param source a {@link SplittableGenerator} instance to be used instead
+ * @param source a {@code SplittableGenerator} instance to be used instead
* of this one as a source of pseudorandom bits used to
* initialize the state of the new ones.
- * @return a new instance of {@link L64X1024MixRandom}
+ * @param brine a long value, of which the low 63 bits are used to choose
+ * the {@code a} parameter for the new instance.
+ * @return a new instance of {@code L64X1024MixRandom}
*/
- public L64X1024MixRandom split(SplittableGenerator source) {
- // Literally pick a new instance "at random".
- return new L64X1024MixRandom(source.nextLong(), source.nextLong(),
- source.nextLong(), source.nextLong(),
+ public SplittableGenerator split(SplittableGenerator source, long brine) {
+ // Pick a new instance "at random", but use the brine for `a`.
+ return new L64X1024MixRandom(brine << 1, source.nextLong(),
+ source.nextLong(), source.nextLong(),
source.nextLong(), source.nextLong(),
source.nextLong(), source.nextLong(),
source.nextLong(), source.nextLong(),
@@ -382,7 +386,12 @@
final long s0 = x[p = (p + 1) & (N - 1)];
long s15 = x[q];
- final long z = s + s0;
+ // Compute the result based on current state information
+ // (this allows the computation to be overlapped with state update).
+
+ final long result = RandomSupport.mixLea64(s + s0);
+
+ // Update the LCG subgenerator
s = M * s + a; // LCG
// Second part of xoroshiro1024: update array data
@@ -390,9 +399,15 @@
x[q] = Long.rotateLeft(s0, 25) ^ s15 ^ (s15 << 27);
x[p] = Long.rotateLeft(s15, 36);
- return RandomSupport.mixLea64(z); // mixing function
+ return result;
}
+ /**
+ * Returns the period of this random generator.
+ *
+ * @return a {@link BigInteger} whose value is the number of distinct possible states of this
+ * {@link RandomGenerator} object (2<sup>64</sup>(2<sup>1024</sup>-1)).
+ */
public BigInteger period() {
return PERIOD;
}
--- a/src/java.base/share/classes/java/util/random/L64X1024Random.java Thu Aug 29 11:33:26 2019 -0300
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,396 +0,0 @@
-/*
- * Copyright (c) 2013, 2019, Oracle and/or its affiliates. All rights reserved.
- * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
- *
- * This code is free software; you can redistribute it and/or modify it
- * under the terms of the GNU General Public License version 2 only, as
- * published by the Free Software Foundation. Oracle designates this
- * particular file as subject to the "Classpath" exception as provided
- * by Oracle in the LICENSE file that accompanied this code.
- *
- * This code is distributed in the hope that it will be useful, but WITHOUT
- * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
- * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
- * version 2 for more details (a copy is included in the LICENSE file that
- * accompanied this code).
- *
- * You should have received a copy of the GNU General Public License version
- * 2 along with this work; if not, write to the Free Software Foundation,
- * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
- *
- * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
- * or visit www.oracle.com if you need additional information or have any
- * questions.
- */
-
-package java.util.random;
-
-import java.math.BigInteger;
-import java.util.concurrent.atomic.AtomicLong;
-import java.util.random.RandomGenerator.SplittableGenerator;
-import java.util.random.RandomSupport.AbstractSplittableGenerator;
-
-/**
- * A generator of uniform pseudorandom values applicable for use in
- * (among other contexts) isolated parallel computations that may
- * generate subtasks. Class {@link L64X1024Random} implements
- * interfaces {@link RandomGenerator} and {@link SplittableGenerator},
- * and therefore supports methods for producing pseudorandomly chosen
- * numbers of type {@code int}, {@code long}, {@code float}, and {@code double}
- * as well as creating new split-off {@link L64X1024Random} objects,
- * with similar usages as for class {@link java.util.SplittableRandom}.
- * <p>
- * Series of generated values pass the TestU01 BigCrush and PractRand test suites
- * that measure independence and uniformity properties of random number generators.
- * (Most recently validated with
- * <a href="http://simul.iro.umontreal.ca/testu01/tu01.html">version 1.2.3 of TestU01</a>
- * and <a href="http://pracrand.sourceforge.net">version 0.90 of PractRand</a>.
- * Note that TestU01 BigCrush was used to test not only values produced by the {@code nextLong()}
- * method but also the result of bit-reversing each value produced by {@code nextLong()}.)
- * These tests validate only the methods for certain
- * types and ranges, but similar properties are expected to hold, at
- * least approximately, for others as well.
- * <p>
- * {@link L64X1024Random} is a specific member of the LXM family of algorithms
- * for pseudorandom number generators. Every LXM generator consists of two
- * subgenerators; one is an LCG (Linear Congruential Generator) and the other is
- * an Xorshift generator. Each output of an LXM generator is the sum of one
- * output from each subgenerator, possibly processed by a final mixing function
- * (but {@link L64X1024Random} does not use a mixing function).
- * <p>
- * The LCG subgenerator for {@link L64X1024Random} has an update step of the
- * form {@code s = m * s + a}, where {@code s}, {@code m}, and {@code a} are all
- * of type {@code long}; {@code s} is the mutable state, the multiplier {@code m}
- * is fixed (the same for all instances of {@link L64X1024Random}) and the addend
- * {@code a} is a parameter (a final field of the instance). The parameter
- * {@code a} is required to be odd (this allows the LCG to have the maximal
- * period, namely 2<sup>64</sup>); therefore there are 2<sup>63</sup> distinct choices
- * of parameter.
- * <p>
- * The Xorshift subgenerator for {@link L64X1024Random} is the {@code xoroshiro1024}
- * algorithm (parameters 25, 27, and 36), without any final scrambler such as "+" or "**".
- * Its state consists of an array {@code x} of sixteen {@code long} values,
- * which can take on any values provided that they are not all zero.
- * The period of this subgenerator is 2<sup>1024</sup>-1.
- * <p>
- * Because the periods 2<sup>64</sup> and 2<sup>1024</sup>-1 of the two subgenerators
- * are relatively prime, the <em>period</em> of any single {@link L64X1024Random} object
- * (the length of the series of generated 64-bit values before it repeats) is the product
- * of the periods of the subgenerators, that is, 2<sup>64</sup>(2<sup>1024</sup>-1),
- * which is just slightly smaller than 2<sup>1088</sup>. Moreover, if two distinct
- * {@link L64X1024Random} objects have different {@code a} parameters, then their
- * cycles of produced values will be different.
- * <p>
- * The 64-bit values produced by the {@code nextLong()} method are exactly equidistributed.
- * For any specific instance of {@link L64X1024Random}, over the course of its cycle each
- * of the 2<sup>64</sup> possible {@code long} values will be produced 2<sup>1024</sup>-1 times.
- * The values produced by the {@code nextInt()}, {@code nextFloat()}, and {@code nextDouble()}
- * methods are likewise exactly equidistributed.
- * <p>
- * In fact, the 64-bit values produced by the {@code nextLong()} method are 16-equidistributed.
- * To be precise: for any specific instance of {@link L64X1024Random}, consider
- * the (overlapping) length-16 subsequences of the cycle of 64-bit values produced by
- * {@code nextLong()} (assuming no other methods are called that would affect the state).
- * There are 2<sup>64</sup>(2<sup>1024</sup>-1) such subsequences, and each subsequence,
- * which consists of 16 64-bit values, can have one of 2<sup>1024</sup> values. Of those
- * 2<sup>1024</sup> subsequence values, nearly all of them (2<sup>1024</sup>-2<sup>64</sup>)
- * occur 2<sup>64</sup> times over the course of the entire cycle, and the other
- * 2<sup>64</sup> subsequence values occur only 2<sup>64</sup>-1 times. So the ratio
- * of the probability of getting one of the less common subsequence values and the
- * probability of getting one of the more common subsequence values is 1-2<sup>-64</sup>.
- * (Note that the set of 2<sup>64</sup> less-common subsequence values will differ from
- * one instance of {@link L64X1024Random} to another, as a function of the additive
- * parameter of the LCG.) The values produced by the {@code nextInt()}, {@code nextFloat()},
- * and {@code nextDouble()} methods are likewise 16-equidistributed.
- * <p>
- * Method {@link #split} constructs and returns a new {@link L64X1024Random}
- * instance that shares no mutable state with the current instance. However, with
- * very high probability, the values collectively generated by the two objects
- * have the same statistical properties as if the same quantity of values were
- * generated by a single thread using a single {@link L64X1024Random} object.
- * This is because, with high probability, distinct {@link L64X1024Random} objects
- * have distinct {@code a} parameters and therefore use distinct members of the
- * algorithmic family; and even if their {@code a} parameters are the same, with
- * very high probability they will traverse different parts of their common state
- * cycle.
- * <p>
- * As with {@link java.util.SplittableRandom}, instances of
- * {@link L64X1024Random} are <em>not</em> thread-safe.
- * They are designed to be split, not shared, across threads. For
- * example, a {@link java.util.concurrent.ForkJoinTask} fork/join-style
- * computation using random numbers might include a construction
- * of the form {@code new Subtask(someL64X1024Random.split()).fork()}.
- * <p>
- * This class provides additional methods for generating random
- * streams, that employ the above techniques when used in
- * {@code stream.parallel()} mode.
- * <p>
- * Instances of {@link L64X1024Random} are not cryptographically
- * secure. Consider instead using {@link java.security.SecureRandom}
- * in security-sensitive applications. Additionally,
- * default-constructed instances do not use a cryptographically random
- * seed unless the {@linkplain System#getProperty system property}
- * {@code java.util.secureRandomSeed} is set to {@code true}.
- *
- * @since 14
- */
-public final class L64X1024Random extends AbstractSplittableGenerator {
-
- /*
- * Implementation Overview.
- *
- * The split() operation uses the current generator to choose 18 new 64-bit
- * long values that are then used to initialize the parameter `a`, the
- * state variable `s`, and the array `x` for a newly constructed generator.
- *
- * With extremely high probability, no two generators so chosen
- * will have the same `a` parameter, and testing has indicated
- * that the values generated by two instances of {@link L64X1024Random}
- * will be (approximately) independent if have different values for `a`.
- *
- * The default (no-argument) constructor, in essence, uses
- * "defaultGen" to generate 18 new 64-bit values for the same
- * purpose. Multiple generators created in this way will certainly
- * differ in their `a` parameters. The defaultGen state must be accessed
- * in a thread-safe manner, so we use an AtomicLong to represent
- * this state. To bootstrap the defaultGen, we start off using a
- * seed based on current time unless the
- * java.util.secureRandomSeed property is set. This serves as a
- * slimmed-down (and insecure) variant of SecureRandom that also
- * avoids stalls that may occur when using /dev/random.
- *
- * File organization: First static fields, then instance
- * fields, then constructors, then instance methods.
- */
-
- /* ---------------- static fields ---------------- */
-
- /*
- * The length of the array x.
- */
-
- private static final int N = 16;
-
- /**
- * The seed generator for default constructors.
- */
- private static final AtomicLong defaultGen = new AtomicLong(RandomSupport.initialSeed());
-
- /*
- * The period of this generator, which is (2**1024 - 1) * 2**64.
- */
- private static final BigInteger PERIOD =
- BigInteger.ONE.shiftLeft(N*64).subtract(BigInteger.ONE).shiftLeft(64);
-
- /*
- * Multiplier used in the LCG portion of the algorithm, taken from
- * Pierre L'Ecuyer, Tables of linear congruential generators of
- * different sizes and good lattice structure, <em>Mathematics of
- * Computation</em> 68, 225 (January 1999), pages 249-260,
- * Table 4 (first multiplier for size 2<sup>64</sup>).
- */
-
- private static final long M = 2862933555777941757L;
-
- /* ---------------- instance fields ---------------- */
-
- /**
- * The parameter that is used as an additive constant for the LCG.
- * Must be odd.
- */
- private final long a;
-
- /**
- * The per-instance state: s for the LCG; the array x for the xorshift;
- * p is the rotating pointer into the array x.
- * At least one of the 16 elements of the array x must be nonzero.
- */
- private long s;
- private final long[] x;
- private int p = N - 1;
-
- /* ---------------- constructors ---------------- */
-
- /**
- * Basic constructor that initializes all fields from parameters.
- * It then adjusts the field values if necessary to ensure that
- * all constraints on the values of fields are met.
- *
- * @param a additive parameter for the LCG
- * @param s initial state for the LCG
- * @param x0 first word of the initial state for the xorshift generator
- * @param x1 second word of the initial state for the xorshift generator
- * @param x2 third word of the initial state for the xorshift generator
- * @param x3 fourth word of the initial state for the xorshift generator
- * @param x4 fifth word of the initial state for the xorshift generator
- * @param x5 sixth word of the initial state for the xorshift generator
- * @param x6 seventh word of the initial state for the xorshift generator
- * @param x7 eight word of the initial state for the xorshift generator
- * @param x8 ninth word of the initial state for the xorshift generator
- * @param x9 tenth word of the initial state for the xorshift generator
- * @param x10 eleventh word of the initial state for the xorshift generator
- * @param x11 twelfth word of the initial state for the xorshift generator
- * @param x12 thirteenth word of the initial state for the xorshift generator
- * @param x13 fourteenth word of the initial state for the xorshift generator
- * @param x14 fifteenth word of the initial state for the xorshift generator
- * @param x15 sixteenth word of the initial state for the xorshift generator
- */
- public L64X1024Random(long a, long s,
- long x0, long x1, long x2, long x3,
- long x4, long x5, long x6, long x7,
- long x8, long x9, long x10, long x11,
- long x12, long x13, long x14, long x15) {
- // Force a to be odd.
- this.a = a | 1;
- this.s = s;
- this.x = new long[N];
- this.x[0] = x0;
- this.x[1] = x1;
- this.x[2] = x2;
- this.x[3] = x3;
- this.x[4] = x4;
- this.x[5] = x5;
- this.x[6] = x6;
- this.x[7] = x7;
- this.x[8] = x8;
- this.x[9] = x9;
- this.x[10] = x10;
- this.x[11] = x11;
- this.x[12] = x12;
- this.x[13] = x13;
- this.x[14] = x14;
- this.x[15] = x15;
- // If x0, x1, ..., x15 are all zero (very unlikely), we must choose nonzero values.
- if ((x0 | x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 | x12 | x13 | x14 | x15) == 0) {
- for (int j = 0; j < N; j++) {
- this.x[j] = RandomSupport.mixStafford13(s += RandomSupport.GOLDEN_RATIO_64);
- }
- }
- }
-
- /**
- * Creates a new instance of {@link L64X1024Random} using the
- * specified {@code long} value as the initial seed. Instances of
- * {@link L64X1024Random} created with the same seed in the same
- * program execution generate identical sequences of values.
- *
- * @param seed the initial seed
- */
- public L64X1024Random(long seed) {
- // Using a value with irregularly spaced 1-bits to xor the seed
- // argument tends to improve "pedestrian" seeds such as 0 or
- // other small integers. We may as well use SILVER_RATIO_64.
- //
- // The seed is hashed by mixMurmur64 to produce the `a` parameter.
- // The seed is hashed by mixStafford13 to produce the initial `x[0]`,
- // which will then be used to produce the first generated value.
- // The other x values are filled in as if by a SplitMix PRNG with
- // GOLDEN_RATIO_64 as the gamma value and Stafford13 as the mixer.
- this(RandomSupport.mixMurmur64(seed ^= RandomSupport.SILVER_RATIO_64),
- 1,
- RandomSupport.mixStafford13(seed),
- RandomSupport.mixStafford13(seed += RandomSupport.GOLDEN_RATIO_64),
- RandomSupport.mixStafford13(seed += RandomSupport.GOLDEN_RATIO_64),
- RandomSupport.mixStafford13(seed += RandomSupport.GOLDEN_RATIO_64),
- RandomSupport.mixStafford13(seed += RandomSupport.GOLDEN_RATIO_64),
- RandomSupport.mixStafford13(seed += RandomSupport.GOLDEN_RATIO_64),
- RandomSupport.mixStafford13(seed += RandomSupport.GOLDEN_RATIO_64),
- RandomSupport.mixStafford13(seed += RandomSupport.GOLDEN_RATIO_64),
- RandomSupport.mixStafford13(seed += RandomSupport.GOLDEN_RATIO_64),
- RandomSupport.mixStafford13(seed += RandomSupport.GOLDEN_RATIO_64),
- RandomSupport.mixStafford13(seed += RandomSupport.GOLDEN_RATIO_64),
- RandomSupport.mixStafford13(seed += RandomSupport.GOLDEN_RATIO_64),
- RandomSupport.mixStafford13(seed += RandomSupport.GOLDEN_RATIO_64),
- RandomSupport.mixStafford13(seed += RandomSupport.GOLDEN_RATIO_64),
- RandomSupport.mixStafford13(seed += RandomSupport.GOLDEN_RATIO_64),
- RandomSupport.mixStafford13(seed + RandomSupport.GOLDEN_RATIO_64));
- }
-
- /**
- * Creates a new instance of {@link L64X1024Random} that is likely to
- * generate sequences of values that are statistically independent
- * of those of any other instances in the current program execution,
- * but may, and typically does, vary across program invocations.
- */
- public L64X1024Random() {
- // Using GOLDEN_RATIO_64 here gives us a good Weyl sequence of values.
- this(defaultGen.getAndAdd(RandomSupport.GOLDEN_RATIO_64));
- }
-
- /**
- * Creates a new instance of {@link L64X1024Random} using the specified array of
- * initial seed bytes. Instances of {@link L64X1024Random} created with the same
- * seed array in the same program execution generate identical sequences of values.
- *
- * @param seed the initial seed
- */
- public L64X1024Random(byte[] seed) {
- // Convert the seed to 18 long values, of which the last 16 are not all zero.
- long[] data = RandomSupport.convertSeedBytesToLongs(seed, 18, 16);
- long a = data[0], s = data[1];
- // Force a to be odd.
- this.a = a | 1;
- this.s = s;
- this.x = new long[N];
- for (int j = 0; j < N; j++) {
- this.x[j] = data[2+j];
- }
- }
-
- /* ---------------- public methods ---------------- */
-
- /**
- * Constructs and returns a new instance of {@link L64X1024Random}
- * that shares no mutable state with this instance.
- * However, with very high probability, the set of values collectively
- * generated by the two objects has the same statistical properties as if
- * same the quantity of values were generated by a single thread using
- * a single {@link L64X1024Random} object. Either or both of the two
- * objects may be further split using the {@code split} method,
- * and the same expected statistical properties apply to the
- * entire set of generators constructed by such recursive splitting.
- *
- * @param source a {@link SplittableGenerator} instance to be used instead
- * of this one as a source of pseudorandom bits used to
- * initialize the state of the new ones.
- * @return a new instance of {@link L64X1024Random}
- */
- public L64X1024Random split(SplittableGenerator source) {
- // Literally pick a new instance "at random".
- return new L64X1024Random(source.nextLong(), source.nextLong(),
- source.nextLong(), source.nextLong(),
- source.nextLong(), source.nextLong(),
- source.nextLong(), source.nextLong(),
- source.nextLong(), source.nextLong(),
- source.nextLong(), source.nextLong(),
- source.nextLong(), source.nextLong(),
- source.nextLong(), source.nextLong(),
- source.nextLong(), source.nextLong());
- }
-
- /**
- * Returns a pseudorandom {@code long} value.
- *
- * @return a pseudorandom {@code long} value
- */
- public long nextLong() {
- // First part of xoroshiro1024: fetch array data
- final int q = p;
- final long s0 = x[p = (p + 1) & (N - 1)];
- long s15 = x[q];
-
- final long z = s + s0;
- s = M * s + a; // LCG
-
- // Second part of xoroshiro1024: update array data
- s15 ^= s0;
- x[q] = Long.rotateLeft(s0, 25) ^ s15 ^ (s15 << 27);
- x[p] = Long.rotateLeft(s15, 36);
-
- return z;
- }
-
- public BigInteger period() {
- return PERIOD;
- }
-}
--- a/src/java.base/share/classes/java/util/random/L64X128MixRandom.java Thu Aug 29 11:33:26 2019 -0300
+++ b/src/java.base/share/classes/java/util/random/L64X128MixRandom.java Thu Nov 14 08:54:56 2019 -0400
@@ -28,7 +28,7 @@
import java.math.BigInteger;
import java.util.concurrent.atomic.AtomicLong;
import java.util.random.RandomGenerator.SplittableGenerator;
-import java.util.random.RandomSupport.AbstractSplittableGenerator;
+import java.util.random.RandomSupport.AbstractSplittableWithBrineGenerator;
/**
* A generator of uniform pseudorandom values applicable for use in
@@ -54,9 +54,10 @@
* {@link L64X128MixRandom} is a specific member of the LXM family of algorithms
* for pseudorandom number generators. Every LXM generator consists of two
* subgenerators; one is an LCG (Linear Congruential Generator) and the other is
- * an Xorshift generator. Each output of an LXM generator is the sum of one
- * output from each subgenerator, possibly processed by a final mixing function
- * (and {@link L64X128MixRandom} does use a mixing function).
+ * an Xorshift generator. Each output of an LXM generator is the result of
+ * combining state from the LCG with state from the Xorshift generator by
+ * using a Mixing function (and then the state of the LCG and the state of the
+ * Xorshift generator are advanced).
* <p>
* The LCG subgenerator for {@link L64X128MixRandom} has an update step of the
* form {@code s = m * s + a}, where {@code s}, {@code m}, and {@code a} are all
@@ -73,7 +74,8 @@
* which can take on any values provided that they are not both zero.
* The period of this subgenerator is 2<sup>128</sup>-1.
* <p>
- * The mixing function for {@link L64X128MixRandom} is the 64-bit "starstar(5,7,9)" function.
+ * The mixing function for {@link L64X128MixRandom} is {@link RandomSupport.mixLea64}
+ * applied to the argument {@code (s + x0)}.
* <p>
* Because the periods 2<sup>64</sup> and 2<sup>128</sup>-1 of the two subgenerators
* are relatively prime, the <em>period</em> of any single {@link L64X128MixRandom} object
@@ -98,8 +100,8 @@
* 2<sup>128</sup> subsequence values, nearly all of them (2<sup>128</sup>-2<sup>64</sup>)
* occur 2<sup>64</sup> times over the course of the entire cycle, and the other
* 2<sup>64</sup> subsequence values occur only 2<sup>64</sup>-1 times. So the ratio
- * of the probability of getting one of the less common subsequence values and the
- * probability of getting one of the more common subsequence values is 1-2<sup>-64</sup>.
+ * of the probability of getting any specific one of the less common subsequence values and the
+ * probability of getting any specific one of the more common subsequence values is 1-2<sup>-64</sup>.
* (Note that the set of 2<sup>64</sup> less-common subsequence values will differ from
* one instance of {@link L64X128MixRandom} to another, as a function of the additive
* parameter of the LCG.) The values produced by the {@code nextInt()}, {@code nextFloat()},
@@ -136,7 +138,7 @@
*
* @since 14
*/
-public final class L64X128MixRandom extends AbstractSplittableGenerator {
+public final class L64X128MixRandom extends AbstractSplittableWithBrineGenerator {
/*
* Implementation Overview.
@@ -179,14 +181,13 @@
BigInteger.ONE.shiftLeft(128).subtract(BigInteger.ONE).shiftLeft(64);
/*
- * Multiplier used in the LCG portion of the algorithm, taken from
- * Pierre L'Ecuyer, Tables of linear congruential generators of
- * different sizes and good lattice structure, <em>Mathematics of
- * Computation</em> 68, 225 (January 1999), pages 249-260,
- * Table 4 (first multiplier for size 2<sup>64</sup>).
+ * Multiplier used in the LCG portion of the algorithm.
+ * Chosen based on research by Sebastiano Vigna and Guy Steele (2019).
+ * The spectral scores for dimensions 2 through 8 for the multiplier 0xd1342543de82ef95
+ * are [0.958602, 0.937479, 0.870757, 0.822326, 0.820405, 0.813065, 0.760215].
*/
- private static final long M = 2862933555777941757L;
+ private static final long M = 0xd1342543de82ef95L;
/* ---------------- instance fields ---------------- */
@@ -222,9 +223,10 @@
this.x1 = x1;
// If x0 and x1 are both zero, we must choose nonzero values.
if ((x0 | x1) == 0) {
+ long v = s;
// At least one of the two values generated here will be nonzero.
- this.x0 = RandomSupport.mixStafford13(s += RandomSupport.GOLDEN_RATIO_64);
- this.x1 = RandomSupport.mixStafford13(s + RandomSupport.GOLDEN_RATIO_64);
+ this.x0 = RandomSupport.mixStafford13(v += RandomSupport.GOLDEN_RATIO_64);
+ this.x1 = RandomSupport.mixStafford13(v + RandomSupport.GOLDEN_RATIO_64);
}
}
@@ -245,7 +247,7 @@
// The seed is hashed by mixStafford13 to produce the initial `x0`,
// which will then be used to produce the first generated value.
// Then x1 is filled in as if by a SplitMix PRNG with
- // GOLDEN_RATIO_64 as the gamma value and Stafford13 as the mixer.
+ // GOLDEN_RATIO_64 as the gamma value and mixStafford13 as the mixer.
this(RandomSupport.mixMurmur64(seed ^= RandomSupport.SILVER_RATIO_64),
1,
RandomSupport.mixStafford13(seed),
@@ -284,26 +286,27 @@
/* ---------------- public methods ---------------- */
/**
- * Constructs and returns a new instance of {@link L64X128MixRandom}
- * that shares no mutable state with this instance.
+ * Given 63 bits of "brine", constructs and returns a new instance of
+ * {@code L64X128MixRandom} that shares no mutable state with this instance.
* However, with very high probability, the set of values collectively
* generated by the two objects has the same statistical properties as if
* same the quantity of values were generated by a single thread using
- * a single {@link L64X128MixRandom} object. Either or both of the two
+ * a single {@code L64X128MixRandom} object. Either or both of the two
* objects may be further split using the {@code split} method,
* and the same expected statistical properties apply to the
* entire set of generators constructed by such recursive splitting.
*
- * @param source a {@link SplittableGenerator} instance to be used instead
+ * @param source a {@code SplittableGenerator} instance to be used instead
* of this one as a source of pseudorandom bits used to
* initialize the state of the new ones.
- *
- * @return a new instance of {@link L64X128MixRandom}
+ * @param brine a long value, of which the low 63 bits are used to choose
+ * the {@code a} parameter for the new instance.
+ * @return a new instance of {@code L64X128MixRandom}
*/
- public L64X128MixRandom split(SplittableGenerator source) {
- // Literally pick a new instance "at random".
- return new L64X128MixRandom(source.nextLong(), source.nextLong(),
- source.nextLong(), source.nextLong());
+ public SplittableGenerator split(SplittableGenerator source, long brine) {
+ // Pick a new instance "at random", but use the brine for `a`.
+ return new L64X128MixRandom(brine << 1, source.nextLong(),
+ source.nextLong(), source.nextLong());
}
/**
@@ -312,8 +315,12 @@
* @return a pseudorandom {@code long} value
*/
public long nextLong() {
- final long z = s + x0;
- s = M * s + a; // LCG
+ // Compute the result based on current state information
+ // (this allows the computation to be overlapped with state update).
+ final long result = RandomSupport.mixLea64(s + x0);
+ // Update the LCG subgenerator
+ s = M * s + a;
+ // Update the Xorshift subgenerator
long q0 = x0, q1 = x1;
{ // xoroshiro128v1_0
q1 ^= q0;
@@ -322,9 +329,15 @@
q1 = Long.rotateLeft(q1, 37);
}
x0 = q0; x1 = q1;
- return Long.rotateLeft(z * 5, 7) * 9; // "starstar" mixing function
+ return result;
}
+ /**
+ * Returns the period of this random generator.
+ *
+ * @return a {@link BigInteger} whose value is the number of distinct possible states of this
+ * {@link RandomGenerator} object (2<sup>64</sup>(2<sup>128</sup>-1)).
+ */
public BigInteger period() {
return PERIOD;
}
--- a/src/java.base/share/classes/java/util/random/L64X128Random.java Thu Aug 29 11:33:26 2019 -0300
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,327 +0,0 @@
-/*
- * Copyright (c) 2013, 2019, Oracle and/or its affiliates. All rights reserved.
- * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
- *
- * This code is free software; you can redistribute it and/or modify it
- * under the terms of the GNU General Public License version 2 only, as
- * published by the Free Software Foundation. Oracle designates this
- * particular file as subject to the "Classpath" exception as provided
- * by Oracle in the LICENSE file that accompanied this code.
- *
- * This code is distributed in the hope that it will be useful, but WITHOUT
- * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
- * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
- * version 2 for more details (a copy is included in the LICENSE file that
- * accompanied this code).
- *
- * You should have received a copy of the GNU General Public License version
- * 2 along with this work; if not, write to the Free Software Foundation,
- * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
- *
- * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
- * or visit www.oracle.com if you need additional information or have any
- * questions.
- */
-
-package java.util.random;
-
-import java.math.BigInteger;
-import java.util.concurrent.atomic.AtomicLong;
-import java.util.random.RandomGenerator.SplittableGenerator;
-import java.util.random.RandomSupport.AbstractSplittableGenerator;
-
-/**
- * A generator of uniform pseudorandom values applicable for use in
- * (among other contexts) isolated parallel computations that may
- * generate subtasks. Class {@link L64X128Random} implements
- * interfaces {@link RandomGenerator} and {@link SplittableGenerator},
- * and therefore supports methods for producing pseudorandomly chosen
- * numbers of type {@code int}, {@code long}, {@code float}, and {@code double}
- * as well as creating new split-off {@link L64X128Random} objects,
- * with similar usages as for class {@link java.util.SplittableRandom}.
- * <p>
- * Series of generated values pass the TestU01 BigCrush and PractRand test suites
- * that measure independence and uniformity properties of random number generators.
- * (Most recently validated with
- * <a href="http://simul.iro.umontreal.ca/testu01/tu01.html">version 1.2.3 of TestU01</a>
- * and <a href="http://pracrand.sourceforge.net">version 0.90 of PractRand</a>.
- * Note that TestU01 BigCrush was used to test not only values produced by the {@code nextLong()}
- * method but also the result of bit-reversing each value produced by {@code nextLong()}.)
- * These tests validate only the methods for certain
- * types and ranges, but similar properties are expected to hold, at
- * least approximately, for others as well.
- * <p>
- * {@link L64X128Random} is a specific member of the LXM family of algorithms
- * for pseudorandom number generators. Every LXM generator consists of two
- * subgenerators; one is an LCG (Linear Congruential Generator) and the other is
- * an Xorshift generator. Each output of an LXM generator is the sum of one
- * output from each subgenerator, possibly processed by a final mixing function
- * (but {@link L64X128Random} does not use a mixing function).
- * <p>
- * The LCG subgenerator for {@link L64X128Random} has an update step of the
- * form {@code s = m * s + a}, where {@code s}, {@code m}, and {@code a} are all
- * of type {@code long}; {@code s} is the mutable state, the multiplier {@code m}
- * is fixed (the same for all instances of {@link L64X128Random}) and the addend
- * {@code a} is a parameter (a final field of the instance). The parameter
- * {@code a} is required to be odd (this allows the LCG to have the maximal
- * period, namely 2<sup>64</sup>); therefore there are 2<sup>63</sup> distinct choices
- * of parameter.
- * <p>
- * The Xorshift subgenerator for {@link L64X128Random} is the {@code xoroshiro128} algorithm,
- * version 1.0 (parameters 24, 16, 37), without any final scrambler such as "+" or "**".
- * Its state consists of two {@code long} fields {@code x0} and {@code x1},
- * which can take on any values provided that they are not both zero.
- * The period of this subgenerator is 2<sup>128</sup>-1.
- * <p>
- * Because the periods 2<sup>64</sup> and 2<sup>128</sup>-1 of the two subgenerators
- * are relatively prime, the <em>period</em> of any single {@link L64X128Random} object
- * (the length of the series of generated 64-bit values before it repeats) is the product
- * of the periods of the subgenerators, that is, 2<sup>64</sup>(2<sup>128</sup>-1),
- * which is just slightly smaller than 2<sup>192</sup>. Moreover, if two distinct
- * {@link L64X128Random} objects have different {@code a} parameters, then their
- * cycles of produced values will be different.
- * <p>
- * The 64-bit values produced by the {@code nextLong()} method are exactly equidistributed.
- * For any specific instance of {@link L64X128Random}, over the course of its cycle each
- * of the 2<sup>64</sup> possible {@code long} values will be produced 2<sup>128</sup>-1 times.
- * The values produced by the {@code nextInt()}, {@code nextFloat()}, and {@code nextDouble()}
- * methods are likewise exactly equidistributed.
- * <p>
- * In fact, the 64-bit values produced by the {@code nextLong()} method are 2-equidistributed.
- * To be precise: for any specific instance of {@link L64X128Random}, consider
- * the (overlapping) length-2 subsequences of the cycle of 64-bit values produced by
- * {@code nextLong()} (assuming no other methods are called that would affect the state).
- * There are 2<sup>64</sup>(2<sup>128</sup>-1) such subsequences, and each subsequence,
- * which consists of 2 64-bit values, can have one of 2<sup>128</sup> values. Of those
- * 2<sup>128</sup> subsequence values, nearly all of them (2<sup>128</sup>-2<sup>64</sup>)
- * occur 2<sup>64</sup> times over the course of the entire cycle, and the other
- * 2<sup>64</sup> subsequence values occur only 2<sup>64</sup>-1 times. So the ratio
- * of the probability of getting one of the less common subsequence values and the
- * probability of getting one of the more common subsequence values is 1-2<sup>-64</sup>.
- * (Note that the set of 2<sup>64</sup> less-common subsequence values will differ from
- * one instance of {@link L64X128Random} to another, as a function of the additive
- * parameter of the LCG.) The values produced by the {@code nextInt()}, {@code nextFloat()},
- * and {@code nextDouble()} methods are likewise 2-equidistributed.
- * <p>
- * Method {@link #split} constructs and returns a new {@link L64X128Random}
- * instance that shares no mutable state with the current instance. However, with
- * very high probability, the values collectively generated by the two objects
- * have the same statistical properties as if the same quantity of values were
- * generated by a single thread using a single {@link L64X128Random} object.
- * This is because, with high probability, distinct {@link L64X128Random} objects
- * have distinct {@code a} parameters and therefore use distinct members of the
- * algorithmic family; and even if their {@code a} parameters are the same, with
- * very high probability they will traverse different parts of their common state
- * cycle.
- * <p>
- * As with {@link java.util.SplittableRandom}, instances of
- * {@link L64X128Random} are <em>not</em> thread-safe.
- * They are designed to be split, not shared, across threads. For
- * example, a {@link java.util.concurrent.ForkJoinTask} fork/join-style
- * computation using random numbers might include a construction
- * of the form {@code new Subtask(someL64X128Random.split()).fork()}.
- * <p>
- * This class provides additional methods for generating random
- * streams, that employ the above techniques when used in
- * {@code stream.parallel()} mode.
- * <p>
- * Instances of {@link L64X128Random} are not cryptographically
- * secure. Consider instead using {@link java.security.SecureRandom}
- * in security-sensitive applications. Additionally,
- * default-constructed instances do not use a cryptographically random
- * seed unless the {@linkplain System#getProperty system property}
- * {@code java.util.secureRandomSeed} is set to {@code true}.
- *
- * @since 14
- */
-public final class L64X128Random extends AbstractSplittableGenerator {
-
- /*
- * Implementation Overview.
- *
- * The split operation uses the current generator to choose four new 64-bit
- * long values that are then used to initialize the parameter `a` and the
- * state variables `s`, `x0`, and `x1` for a newly constructed generator.
- *
- * With extremely high probability, no two generators so chosen
- * will have the same `a` parameter, and testing has indicated
- * that the values generated by two instances of {@link L64X128Random}
- * will be (approximately) independent if have different values for `a`.
- *
- * The default (no-argument) constructor, in essence, uses
- * "defaultGen" to generate four new 64-bit values for the same
- * purpose. Multiple generators created in this way will certainly
- * differ in their `a` parameters. The defaultGen state must be accessed
- * in a thread-safe manner, so we use an AtomicLong to represent
- * this state. To bootstrap the defaultGen, we start off using a
- * seed based on current time unless the
- * java.util.secureRandomSeed property is set. This serves as a
- * slimmed-down (and insecure) variant of SecureRandom that also
- * avoids stalls that may occur when using /dev/random.
- *
- * File organization: First static fields, then instance
- * fields, then constructors, then instance methods.
- */
-
- /* ---------------- static fields ---------------- */
-
- /**
- * The seed generator for default constructors.
- */
- private static final AtomicLong defaultGen = new AtomicLong(RandomSupport.initialSeed());
-
- /*
- * The period of this generator, which is (2**128 - 1) * 2**64.
- */
- private static final BigInteger PERIOD =
- BigInteger.ONE.shiftLeft(128).subtract(BigInteger.ONE).shiftLeft(64);
-
- /*
- * Multiplier used in the LCG portion of the algorithm, taken from
- * Pierre L'Ecuyer, Tables of linear congruential generators of
- * different sizes and good lattice structure, <em>Mathematics of
- * Computation</em> 68, 225 (January 1999), pages 249-260,
- * Table 4 (first multiplier for size 2<sup>64</sup>).
- */
-
- private static final long M = 2862933555777941757L;
-
- /* ---------------- instance fields ---------------- */
-
- /**
- * The parameter that is used as an additive constant for the LCG.
- * Must be odd.
- */
- private final long a;
-
- /**
- * The per-instance state: s for the LCG; x0 and x1 for the xorshift.
- * At least one of x0 and x1 must be nonzero.
- */
- private long s, x0, x1;
-
- /* ---------------- constructors ---------------- */
-
- /**
- * Basic constructor that initializes all fields from parameters.
- * It then adjusts the field values if necessary to ensure that
- * all constraints on the values of fields are met.
- *
- * @param a additive parameter for the LCG
- * @param s initial state for the LCG
- * @param x0 first word of the initial state for the xorshift generator
- * @param x1 second word of the initial state for the xorshift generator
- */
- public L64X128Random(long a, long s, long x0, long x1) {
- // Force a to be odd.
- this.a = a | 1;
- this.s = s;
- // If x0 and x1 are both zero, we must choose nonzero values.
- if ((x0 | x1) == 0) {
- // At least one of the two values generated here will be nonzero.
- this.x0 = RandomSupport.mixStafford13(s += RandomSupport.GOLDEN_RATIO_64);
- this.x1 = RandomSupport.mixStafford13(s + RandomSupport.GOLDEN_RATIO_64);
- }
- }
-
- /**
- * Creates a new instance of {@link L64X128Random} using the
- * specified {@code long} value as the initial seed. Instances of
- * {@link L64X128Random} created with the same seed in the same
- * program generate identical sequences of values.
- *
- * @param seed the initial seed
- */
- public L64X128Random(long seed) {
- // Using a value with irregularly spaced 1-bits to xor the seed
- // argument tends to improve "pedestrian" seeds such as 0 or
- // other small integers. We may as well use SILVER_RATIO_64.
- //
- // The seed is hashed by mixMurmur64 to produce the `a` parameter.
- // The seed is hashed by mixStafford13 to produce the initial `x0`,
- // which will then be used to produce the first generated value.
- // Then x1 is filled in as if by a SplitMix PRNG with
- // GOLDEN_RATIO_64 as the gamma value and Stafford13 as the mixer.
- this(RandomSupport.mixMurmur64(seed ^= RandomSupport.SILVER_RATIO_64),
- 1,
- RandomSupport.mixStafford13(seed),
- RandomSupport.mixStafford13(seed + RandomSupport.GOLDEN_RATIO_64));
- }
-
- /**
- * Creates a new instance of {@link L64X128Random} that is likely to
- * generate sequences of values that are statistically independent
- * of those of any other instances in the current program execution,
- * but may, and typically does, vary across program invocations.
- */
- public L64X128Random() {
- // Using GOLDEN_RATIO_64 here gives us a good Weyl sequence of values.
- this(defaultGen.getAndAdd(RandomSupport.GOLDEN_RATIO_64));
- }
-
- /**
- * Creates a new instance of {@link L64X128MixRandom} using the specified array of
- * initial seed bytes. Instances of {@link L64X128MixRandom} created with the same
- * seed array in the same program execution generate identical sequences of values.
- *
- * @param seed the initial seed
- */
- public L64X128Random(byte[] seed) {
- // Convert the seed to 4 long values, of which the last 2 are not all zero.
- long[] data = RandomSupport.convertSeedBytesToLongs(seed, 4, 2);
- long a = data[0], s = data[1], x0 = data[2], x1 = data[3];
- // Force a to be odd.
- this.a = a | 1;
- this.s = s;
- this.x0 = x0;
- this.x1 = x1;
- }
-
- /* ---------------- public methods ---------------- */
-
- /**
- * Constructs and returns a new instance of {@link L64X128Random}
- * that shares no mutable state with this instance.
- * However, with very high probability, the set of values collectively
- * generated by the two objects has the same statistical properties as if
- * same the quantity of values were generated by a single thread using
- * a single {@link L64X128Random} object. Either or both of the two
- * objects may be further split using the {@code split} method,
- * and the same expected statistical properties apply to the
- * entire set of generators constructed by such recursive splitting.
- *
- * @param source a {@link SplittableGenerator} instance to be used instead
- * of this one as a source of pseudorandom bits used to
- * initialize the state of the new ones.
- *
- * @return a new instance of {@link L64X128Random}
- */
- public L64X128Random split(SplittableGenerator source) {
- // Literally pick a new instance "at random".
- return new L64X128Random(source.nextLong(), source.nextLong(),
- source.nextLong(), source.nextLong());
- }
-
- /**
- * Returns a pseudorandom {@code long} value.
- *
- * @return a pseudorandom {@code long} value
- */
- public long nextLong() {
- final long z = s + x0;
- s = M * s + a; // LCG
- long q0 = x0, q1 = x1;
- { // xoroshiro128v1_0
- q1 ^= q0;
- q0 = Long.rotateLeft(q0, 24);
- q0 = q0 ^ q1 ^ (q1 << 16);
- q1 = Long.rotateLeft(q1, 37);
- }
- x0 = q0; x1 = q1;
- return z;
- }
-
- public BigInteger period() {
- return PERIOD;
- }
-}
--- a/src/java.base/share/classes/java/util/random/L64X256MixRandom.java Thu Aug 29 11:33:26 2019 -0300
+++ b/src/java.base/share/classes/java/util/random/L64X256MixRandom.java Thu Nov 14 08:54:56 2019 -0400
@@ -28,7 +28,7 @@
import java.math.BigInteger;
import java.util.concurrent.atomic.AtomicLong;
import java.util.random.RandomGenerator.SplittableGenerator;
-import java.util.random.RandomSupport.AbstractSplittableGenerator;
+import java.util.random.RandomSupport.AbstractSplittableWithBrineGenerator;
/**
* A generator of uniform pseudorandom values applicable for use in
@@ -54,9 +54,10 @@
* {@link L64X256MixRandom} is a specific member of the LXM family of algorithms
* for pseudorandom number generators. Every LXM generator consists of two
* subgenerators; one is an LCG (Linear Congruential Generator) and the other is
- * an Xorshift generator. Each output of an LXM generator is the sum of one
- * output from each subgenerator, possibly processed by a final mixing function
- * (and {@link L64X256MixRandom} does use a mixing function).
+ * an Xorshift generator. Each output of an LXM generator is the result of
+ * combining state from the LCG with state from the Xorshift generator by
+ * using a Mixing function (and then the state of the LCG and the state of the
+ * Xorshift generator are advanced).
* <p>
* The LCG subgenerator for {@link L64X256MixRandom} has an update step of the
* form {@code s = m * s + a}, where {@code s}, {@code m}, and {@code a} are all
@@ -73,7 +74,8 @@
* and {@code x3}, which can take on any values provided that they are not all zero.
* The period of this subgenerator is 2<sup>256</sup>-1.
* <p>
- * The mixing function for {@link L64X256MixRandom} is the 64-bit MurmurHash3 finalizer.
+ * The mixing function for {@link L64X256MixRandom} is {@link RandomSupport.mixLea64}
+ * applied to the argument {@code (s + x0)}.
* <p>
* Because the periods 2<sup>64</sup> and 2<sup>256</sup>-1 of the two subgenerators
* are relatively prime, the <em>period</em> of any single {@link L64X256MixRandom} object
@@ -98,8 +100,8 @@
* 2<sup>256</sup> subsequence values, nearly all of them (2<sup>256</sup>-2<sup>64</sup>)
* occur 2<sup>64</sup> times over the course of the entire cycle, and the other
* 2<sup>64</sup> subsequence values occur only 2<sup>64</sup>-1 times. So the ratio
- * of the probability of getting one of the less common subsequence values and the
- * probability of getting one of the more common subsequence values is 1-2<sup>-64</sup>.
+ * of the probability of getting any specific one of the less common subsequence values and the
+ * probability of getting any specific one of the more common subsequence values is 1-2<sup>-64</sup>.
* (Note that the set of 2<sup>64</sup> less-common subsequence values will differ from
* one instance of {@link L64X256MixRandom} to another, as a function of the additive
* parameter of the LCG.) The values produced by the {@code nextInt()}, {@code nextFloat()},
@@ -136,7 +138,7 @@
*
* @since 14
*/
-public final class L64X256MixRandom extends AbstractSplittableGenerator {
+public final class L64X256MixRandom extends AbstractSplittableWithBrineGenerator {
/*
* Implementation Overview.
@@ -180,14 +182,13 @@
BigInteger.ONE.shiftLeft(256).subtract(BigInteger.ONE).shiftLeft(64);
/*
- * Multiplier used in the LCG portion of the algorithm, taken from
- * Pierre L'Ecuyer, Tables of linear congruential generators of
- * different sizes and good lattice structure, <em>Mathematics of
- * Computation</em> 68, 225 (January 1999), pages 249-260,
- * Table 4 (first multiplier for size 2<sup>64</sup>).
+ * Multiplier used in the LCG portion of the algorithm.
+ * Chosen based on research by Sebastiano Vigna and Guy Steele (2019).
+ * The spectral scores for dimensions 2 through 8 for the multiplier 0xd1342543de82ef95
+ * are [0.958602, 0.937479, 0.870757, 0.822326, 0.820405, 0.813065, 0.760215].
*/
- private static final long M = 2862933555777941757L;
+ private static final long M = 0xd1342543de82ef95L;
/* ---------------- instance fields ---------------- */
@@ -227,11 +228,12 @@
this.x3 = x3;
// If x0, x1, x2, and x3 are all zero, we must choose nonzero values.
if ((x0 | x1 | x2 | x3) == 0) {
+ long v = s;
// At least three of the four values generated here will be nonzero.
- this.x0 = RandomSupport.mixStafford13(s += RandomSupport.GOLDEN_RATIO_64);
- this.x1 = RandomSupport.mixStafford13(s += RandomSupport.GOLDEN_RATIO_64);
- this.x2 = RandomSupport.mixStafford13(s += RandomSupport.GOLDEN_RATIO_64);
- this.x3 = RandomSupport.mixStafford13(s + RandomSupport.GOLDEN_RATIO_64);
+ this.x0 = RandomSupport.mixStafford13(v += RandomSupport.GOLDEN_RATIO_64);
+ this.x1 = RandomSupport.mixStafford13(v += RandomSupport.GOLDEN_RATIO_64);
+ this.x2 = RandomSupport.mixStafford13(v += RandomSupport.GOLDEN_RATIO_64);
+ this.x3 = RandomSupport.mixStafford13(v + RandomSupport.GOLDEN_RATIO_64);
}
}
@@ -252,7 +254,7 @@
// The seed is hashed by mixStafford13 to produce the initial `x0`,
// which will then be used to produce the first generated value.
// The other x values are filled in as if by a SplitMix PRNG with
- // GOLDEN_RATIO_64 as the gamma value and Stafford13 as the mixer.
+ // GOLDEN_RATIO_64 as the gamma value and mixStafford13 as the mixer.
this(RandomSupport.mixMurmur64(seed ^= RandomSupport.SILVER_RATIO_64),
1,
RandomSupport.mixStafford13(seed),
@@ -295,27 +297,28 @@
/* ---------------- public methods ---------------- */
/**
- * Constructs and returns a new instance of {@link L64X256MixRandom}
- * that shares no mutable state with this instance.
+ * Given 63 bits of "brine", constructs and returns a new instance of
+ * {@code L64X256MixRandom} that shares no mutable state with this instance.
* However, with very high probability, the set of values collectively
* generated by the two objects has the same statistical properties as if
* same the quantity of values were generated by a single thread using
- * a single {@link L64X256MixRandom} object. Either or both of the two
+ * a single {@code L64X256MixRandom} object. Either or both of the two
* objects may be further split using the {@code split} method,
* and the same expected statistical properties apply to the
* entire set of generators constructed by such recursive splitting.
*
- * @param source a {@link SplittableGenerator} instance to be used instead
+ * @param source a {@code SplittableGenerator} instance to be used instead
* of this one as a source of pseudorandom bits used to
* initialize the state of the new ones.
- *
- * @return a new instance of {@link L64X256MixRandom}
+ * @param brine a long value, of which the low 63 bits are used to choose
+ * the {@code a} parameter for the new instance.
+ * @return a new instance of {@code L64X256MixRandom}
*/
- public L64X256MixRandom split(SplittableGenerator source) {
- // Literally pick a new instance "at random".
- return new L64X256MixRandom(source.nextLong(), source.nextLong(),
- source.nextLong(), source.nextLong(),
- source.nextLong(), source.nextLong());
+ public SplittableGenerator split(SplittableGenerator source, long brine) {
+ // Pick a new instance "at random", but use the brine for `a`.
+ return new L64X256MixRandom(brine << 1, source.nextLong(),
+ source.nextLong(), source.nextLong(),
+ source.nextLong(), source.nextLong());
}
/**
@@ -324,8 +327,12 @@
* @return a pseudorandom {@code long} value
*/
public long nextLong() {
- final long z = s + x0;
- s = M * s + a; // LCG
+ // Compute the result based on current state information
+ // (this allows the computation to be overlapped with state update).
+ final long result = RandomSupport.mixLea64(s + x0);
+ // Update the LCG subgenerator
+ s = M * s + a;
+ // Update the Xorshift subgenerator
long q0 = x0, q1 = x1, q2 = x2, q3 = x3;
{ // xoshiro256 1.0
long t = q1 << 17;
@@ -337,9 +344,15 @@
q3 = Long.rotateLeft(q3, 45);
}
x0 = q0; x1 = q1; x2 = q2; x3 = q3;
- return RandomSupport.mixLea64(z); // mixing function
+ return result;
}
+ /**
+ * Returns the period of this random generator.
+ *
+ * @return a {@link BigInteger} whose value is the number of distinct possible states of this
+ * {@link RandomGenerator} object (2<sup>64</sup>(2<sup>256</sup>-1)).
+ */
public BigInteger period() {
return PERIOD;
}
--- a/src/java.base/share/classes/java/util/random/L64X256Random.java Thu Aug 29 11:33:26 2019 -0300
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,344 +0,0 @@
-/*
- * Copyright (c) 2013, 2019, Oracle and/or its affiliates. All rights reserved.
- * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
- *
- * This code is free software; you can redistribute it and/or modify it
- * under the terms of the GNU General Public License version 2 only, as
- * published by the Free Software Foundation. Oracle designates this
- * particular file as subject to the "Classpath" exception as provided
- * by Oracle in the LICENSE file that accompanied this code.
- *
- * This code is distributed in the hope that it will be useful, but WITHOUT
- * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
- * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
- * version 2 for more details (a copy is included in the LICENSE file that
- * accompanied this code).
- *
- * You should have received a copy of the GNU General Public License version
- * 2 along with this work; if not, write to the Free Software Foundation,
- * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
- *
- * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
- * or visit www.oracle.com if you need additional information or have any
- * questions.
- */
-
-package java.util.random;
-
-import java.math.BigInteger;
-import java.util.concurrent.atomic.AtomicLong;
-import java.util.random.RandomGenerator.SplittableGenerator;
-import java.util.random.RandomSupport.AbstractSplittableGenerator;
-
-/**
- * A generator of uniform pseudorandom values applicable for use in
- * (among other contexts) isolated parallel computations that may
- * generate subtasks. Class {@link L64X256Random} implements
- * interfaces {@link RandomGenerator} and {@link SplittableGenerator},
- * and therefore supports methods for producing pseudorandomly chosen
- * numbers of type {@code int}, {@code long}, {@code float}, and {@code double}
- * as well as creating new split-off {@link L64X256Random} objects,
- * with similar usages as for class {@link java.util.SplittableRandom}.
- * <p>
- * Series of generated values pass the TestU01 BigCrush and PractRand test suites
- * that measure independence and uniformity properties of random number generators.
- * (Most recently validated with
- * <a href="http://simul.iro.umontreal.ca/testu01/tu01.html">version 1.2.3 of TestU01</a>
- * and <a href="http://pracrand.sourceforge.net">version 0.90 of PractRand</a>.
- * Note that TestU01 BigCrush was used to test not only values produced by the {@code nextLong()}
- * method but also the result of bit-reversing each value produced by {@code nextLong()}.)
- * These tests validate only the methods for certain
- * types and ranges, but similar properties are expected to hold, at
- * least approximately, for others as well.
- * <p>
- * {@link L64X256Random} is a specific member of the LXM family of algorithms
- * for pseudorandom number generators. Every LXM generator consists of two
- * subgenerators; one is an LCG (Linear Congruential Generator) and the other is
- * an Xorshift generator. Each output of an LXM generator is the sum of one
- * output from each subgenerator, possibly processed by a final mixing function
- * (but {@link L64X256Random} does not use a mixing function).
- * <p>
- * The LCG subgenerator for {@link L64X256Random} has an update step of the
- * form {@code s = m * s + a}, where {@code s}, {@code m}, and {@code a} are all
- * of type {@code long}; {@code s} is the mutable state, the multiplier {@code m}
- * is fixed (the same for all instances of {@link L64X256Random}) and the addend
- * {@code a} is a parameter (a final field of the instance). The parameter
- * {@code a} is required to be odd (this allows the LCG to have the maximal
- * period, namely 2<sup>64</sup>); therefore there are 2<sup>63</sup> distinct choices
- * of parameter.
- * <p>
- * The Xorshift subgenerator for {@link L64X256Random} is the {@code xoshiro256} algorithm,
- * version 1.0 (parameters 17, 45), without any final scrambler such as "+" or "**".
- * Its state consists of four {@code long} fields {@code x0}, {@code x1}, {@code x2},
- * and {@code x3}, which can take on any values provided that they are not all zero.
- * The period of this subgenerator is 2<sup>256</sup>-1.
- * <p>
- * Because the periods 2<sup>64</sup> and 2<sup>256</sup>-1 of the two subgenerators
- * are relatively prime, the <em>period</em> of any single {@link L64X256Random} object
- * (the length of the series of generated 64-bit values before it repeats) is the product
- * of the periods of the subgenerators, that is, 2<sup>64</sup>(2<sup>256</sup>-1),
- * which is just slightly smaller than 2<sup>320</sup>. Moreover, if two distinct
- * {@link L64X256Random} objects have different {@code a} parameters, then their
- * cycles of produced values will be different.
- * <p>
- * The 64-bit values produced by the {@code nextLong()} method are exactly equidistributed.
- * For any specific instance of {@link L64X256Random}, over the course of its cycle each
- * of the 2<sup>64</sup> possible {@code long} values will be produced 2<sup>256</sup>-1 times.
- * The values produced by the {@code nextInt()}, {@code nextFloat()}, and {@code nextDouble()}
- * methods are likewise exactly equidistributed.
- * <p>
- * In fact, the 64-bit values produced by the {@code nextLong()} method are 4-equidistributed.
- * To be precise: for any specific instance of {@link L64X256Random}, consider
- * the (overlapping) length-4 subsequences of the cycle of 64-bit values produced by
- * {@code nextLong()} (assuming no other methods are called that would affect the state).
- * There are 2<sup>64</sup>(2<sup>256</sup>-1) such subsequences, and each subsequence,
- * which consists of 4 64-bit values, can have one of 2<sup>256</sup> values. Of those
- * 2<sup>256</sup> subsequence values, nearly all of them (2<sup>256</sup>-2<sup>64</sup>)
- * occur 2<sup>64</sup> times over the course of the entire cycle, and the other
- * 2<sup>64</sup> subsequence values occur only 2<sup>64</sup>-1 times. So the ratio
- * of the probability of getting one of the less common subsequence values and the
- * probability of getting one of the more common subsequence values is 1-2<sup>-64</sup>.
- * (Note that the set of 2<sup>64</sup> less-common subsequence values will differ from
- * one instance of {@link L64X256Random} to another, as a function of the additive
- * parameter of the LCG.) The values produced by the {@code nextInt()}, {@code nextFloat()},
- * and {@code nextDouble()} methods are likewise 4-equidistributed.
- * <p>
- * Method {@link #split} constructs and returns a new {@link L64X256Random}
- * instance that shares no mutable state with the current instance. However, with
- * very high probability, the values collectively generated by the two objects
- * have the same statistical properties as if the same quantity of values were
- * generated by a single thread using a single {@link L64X256Random} object.
- * This is because, with high probability, distinct {@link L64X256Random} objects
- * have distinct {@code a} parameters and therefore use distinct members of the
- * algorithmic family; and even if their {@code a} parameters are the same, with
- * very high probability they will traverse different parts of their common state
- * cycle.
- * <p>
- * As with {@link java.util.SplittableRandom}, instances of
- * {@link L64X256Random} are <em>not</em> thread-safe.
- * They are designed to be split, not shared, across threads. For
- * example, a {@link java.util.concurrent.ForkJoinTask} fork/join-style
- * computation using random numbers might include a construction
- * of the form {@code new Subtask(someL64X256Random.split()).fork()}.
- * <p>
- * This class provides additional methods for generating random
- * streams, that employ the above techniques when used in
- * {@code stream.parallel()} mode.
- * <p>
- * Instances of {@link L64X256Random} are not cryptographically
- * secure. Consider instead using {@link java.security.SecureRandom}
- * in security-sensitive applications. Additionally,
- * default-constructed instances do not use a cryptographically random
- * seed unless the {@linkplain System#getProperty system property}
- * {@code java.util.secureRandomSeed} is set to {@code true}.
- *
- * @since 14
- */
-public final class L64X256Random extends AbstractSplittableGenerator {
-
- /*
- * Implementation Overview.
- *
- * The split() operation uses the current generator to choose six new 64-bit
- * long values that are then used to initialize the parameter `a` and the
- * state variables `s`, `x0`, `x1`, `x2`, and `x3` for a newly constructed
- * generator.
- *
- * With extremely high probability, no two generators so chosen
- * will have the same `a` parameter, and testing has indicated
- * that the values generated by two instances of {@link L64X256Random}
- * will be (approximately) independent if have different values for `a`.
- *
- * The default (no-argument) constructor, in essence, uses
- * "defaultGen" to generate six new 64-bit values for the same
- * purpose. Multiple generators created in this way will certainly
- * differ in their `a` parameters. The defaultGen state must be accessed
- * in a thread-safe manner, so we use an AtomicLong to represent
- * this state. To bootstrap the defaultGen, we start off using a
- * seed based on current time unless the
- * java.util.secureRandomSeed property is set. This serves as a
- * slimmed-down (and insecure) variant of SecureRandom that also
- * avoids stalls that may occur when using /dev/random.
- *
- * File organization: First static fields, then instance
- * fields, then constructors, then instance methods.
- */
-
- /* ---------------- static fields ---------------- */
-
- /**
- * The seed generator for default constructors.
- */
- private static final AtomicLong defaultGen = new AtomicLong(RandomSupport.initialSeed());
-
- /*
- * The period of this generator, which is (2**256 - 1) * 2**64.
- */
- private static final BigInteger PERIOD =
- BigInteger.ONE.shiftLeft(256).subtract(BigInteger.ONE).shiftLeft(64);
-
- /*
- * Multiplier used in the LCG portion of the algorithm, taken from
- * Pierre L'Ecuyer, Tables of linear congruential generators of
- * different sizes and good lattice structure, <em>Mathematics of
- * Computation</em> 68, 225 (January 1999), pages 249-260,
- * Table 4 (first multiplier for size 2<sup>64</sup>).
- */
-
- private static final long M = 2862933555777941757L;
-
- /* ---------------- instance fields ---------------- */
-
- /**
- * The parameter that is used as an additive constant for the LCG.
- * Must be odd.
- */
- private final long a;
-
- /**
- * The per-instance state: s for the LCG; x0, x1, x2, and x3 for the xorshift.
- * At least one of the four fields x0, x1, x2, and x3 must be nonzero.
- */
- private long s, x0, x1, x2, x3;
-
- /* ---------------- constructors ---------------- */
-
- /**
- * Basic constructor that initializes all fields from parameters.
- * It then adjusts the field values if necessary to ensure that
- * all constraints on the values of fields are met.
- *
- * @param a additive parameter for the LCG
- * @param s initial state for the LCG
- * @param x0 first word of the initial state for the xorshift generator
- * @param x1 second word of the initial state for the xorshift generator
- * @param x2 third word of the initial state for the xorshift generator
- * @param x3 fourth word of the initial state for the xorshift generator
- */
- public L64X256Random(long a, long s, long x0, long x1, long x2, long x3) {
- // Force a to be odd.
- this.a = a | 1;
- this.s = s;
- this.x0 = x0;
- this.x1 = x1;
- this.x2 = x2;
- this.x3 = x3;
- // If x0, x1, x2, and x3 are all zero, we must choose nonzero values.
- if ((x0 | x1 | x2 | x3) == 0) {
- // At least three of the four values generated here will be nonzero.
- this.x0 = RandomSupport.mixStafford13(s += RandomSupport.GOLDEN_RATIO_64);
- this.x1 = RandomSupport.mixStafford13(s += RandomSupport.GOLDEN_RATIO_64);
- this.x2 = RandomSupport.mixStafford13(s += RandomSupport.GOLDEN_RATIO_64);
- this.x3 = RandomSupport.mixStafford13(s + RandomSupport.GOLDEN_RATIO_64);
- }
- }
-
- /**
- * Creates a new instance of {@link L64X256Random} using the
- * specified {@code long} value as the initial seed. Instances of
- * {@link L64X256Random} created with the same seed in the same
- * program execution generate identical sequences of values.
- *
- * @param seed the initial seed
- */
- public L64X256Random(long seed) {
- // Using a value with irregularly spaced 1-bit to xor the seed
- // argument tends to improve "pedestrian" seeds such as 0 or
- // other small integers. We may as well use SILVER_RATIO_64.
- //
- // The seed is hashed by mixMurmur64 to produce the `a` parameter.
- // The seed is hashed by mixStafford13 to produce the initial `x0`,
- // which will then be used to produce the first generated value.
- // The other x values are filled in as if by a SplitMix PRNG with
- // GOLDEN_RATIO_64 as the gamma value and Stafford13 as the mixer.
- this(RandomSupport.mixMurmur64(seed ^= RandomSupport.SILVER_RATIO_64),
- 1,
- RandomSupport.mixStafford13(seed),
- RandomSupport.mixStafford13(seed += RandomSupport.GOLDEN_RATIO_64),
- RandomSupport.mixStafford13(seed += RandomSupport.GOLDEN_RATIO_64),
- RandomSupport.mixStafford13(seed + RandomSupport.GOLDEN_RATIO_64));
- }
-
- /**
- * Creates a new instance of {@link L64X256Random} that is likely to
- * generate sequences of values that are statistically independent
- * of those of any other instances in the current program execution,
- * but may, and typically does, vary across program invocations.
- */
- public L64X256Random() {
- // Using GOLDEN_RATIO_64 here gives us a good Weyl sequence of values.
- this(defaultGen.getAndAdd(RandomSupport.GOLDEN_RATIO_64));
- }
-
- /**
- * Creates a new instance of {@link L64X256Random} using the specified array of
- * initial seed bytes. Instances of {@link L64X256Random} created with the same
- * seed array in the same program execution generate identical sequences of values.
- *
- * @param seed the initial seed
- */
- public L64X256Random(byte[] seed) {
- // Convert the seed to 6 long values, of which the last 4 are not all zero.
- long[] data = RandomSupport.convertSeedBytesToLongs(seed, 6, 4);
- long a = data[0], s = data[1], x0 = data[2], x1 = data[3], x2 = data[4], x3 = data[5];
- // Force a to be odd.
- this.a = a | 1;
- this.s = s;
- this.x0 = x0;
- this.x1 = x1;
- this.x2 = x2;
- this.x3 = x3;
- }
-
- /* ---------------- public methods ---------------- */
-
- /**
- * Constructs and returns a new instance of {@link L64X256Random}
- * that shares no mutable state with this instance.
- * However, with very high probability, the set of values collectively
- * generated by the two objects has the same statistical properties as if
- * same the quantity of values were generated by a single thread using
- * a single {@link L64X256Random} object. Either or both of the two
- * objects may be further split using the {@code split} method,
- * and the same expected statistical properties apply to the
- * entire set of generators constructed by such recursive splitting.
- *
- * @param source a {@link SplittableGenerator} instance to be used instead
- * of this one as a source of pseudorandom bits used to
- * initialize the state of the new ones.
- *
- * @return a new instance of {@link L64X256Random}
- */
- public L64X256Random split(SplittableGenerator source) {
- // Literally pick a new instance "at random".
- return new L64X256Random(source.nextLong(), source.nextLong(),
- source.nextLong(), source.nextLong(),
- source.nextLong(), source.nextLong());
- }
-
- /**
- * Returns a pseudorandom {@code long} value.
- *
- * @return a pseudorandom {@code long} value
- */
- public long nextLong() {
- final long z = s + x0;
- s = M * s + a; // LCG
- long q0 = x0, q1 = x1, q2 = x2, q3 = x3;
- { // xoshiro256 1.0
- long t = q1 << 17;
- q2 ^= q0;
- q3 ^= q1;
- q1 ^= q2;
- q0 ^= q3;
- q2 ^= t;
- q3 = Long.rotateLeft(q3, 45);
- }
- x0 = q0; x1 = q1; x2 = q2; x3 = q3;
- return z;
- }
-
- public BigInteger period() {
- return PERIOD;
- }
-}
--- a/src/java.base/share/classes/java/util/random/RandomGenerator.java Thu Aug 29 11:33:26 2019 -0300
+++ b/src/java.base/share/classes/java/util/random/RandomGenerator.java Thu Nov 14 08:54:56 2019 -0400
@@ -34,8 +34,8 @@
/**
* The {@link RandomGenerator} interface is designed to provide a common protocol for objects that
- * generate random or (more typically) pseudorandom sequences of numbers (or Boolean values). Such a
- * sequence may be obtained by either repeatedly invoking a method that returns a single
+ * generate random or (more typically) pseudorandom sequences of numbers (or Boolean values).
+ * Such a sequence may be obtained by either repeatedly invoking a method that returns a single
* (pseudo)randomly chosen value, or by invoking a method that returns a stream of (pseudo)randomly
* chosen values.
* <p>
@@ -59,12 +59,14 @@
* guaranteed is that each value in the stream is chosen in a similar (pseudo)random manner from the
* same range.
* <p>
- * Every object that implements the {@link RandomGenerator} interface is assumed to contain a finite
- * amount of state. Using such an object to generate a pseudorandomly chosen value alters its
- * state. The number of distinct possible states of such an object is called its
- * <i>period</i>. (Some implementations of the {@link RandomGenerator} interface
- * may be truly random rather than pseudorandom, for example relying on the statistical behavior of
- * a physical object to derive chosen values. Such implementations do not have a fixed period.)
+ * Every object that implements the {@link RandomNumberGenerator} interface by using a
+ * pseudorandom algorithm is assumed to contain a finite amount of state. Using such an object to
+ * generate a pseudorandomly chosen value alters its state by computing a new state as a function
+ * of the current state, without reference to any information other than the current state.
+ * The number of distinct possible states of such an object is called its <i>period</i>.
+ * (Some implementations of the {@link RandomNumberGenerator} interface may be truly random
+ * rather than pseudorandom, for example relying on the statistical behavior of a physical
+ * object to derive chosen values. Such implementations do not have a fixed period.)
* <p>
* As a rule, objects that implement the {@link RandomGenerator} interface need not be thread-safe.
* It is recommended that multithreaded applications use either {@link ThreadLocalRandom} or
@@ -74,10 +76,10 @@
* To implement this interface, a class only needs to provide concrete definitions for the methods
* {@code nextLong()} and {@code period()}. Default implementations are provided for all other
* methods (but it may be desirable to override some of them, especially {@code nextInt()} if the
- * underlying algorithm is {@code int}-based). Moerover, it may be preferable instead to implement
- * another interface such as {@link JumpableGenerator} or {@link LeapableGenerator}, or to extend an
- * abstract class such as {@link AbstractSplittableGenerator} or {@link
- * AbstractArbitrarilyJumpableGenerator}.
+ * underlying algorithm is {@code int}-based). Moreover, it may be preferable instead to implement
+ * a more specialized interface such as {@link JumpableGenerator} or {@link LeapableGenerator},
+ * or to extend an abstract implementation-support class such as {@link AbstractSplittableGenerator}
+ * or {@link AbstractArbitrarilyJumpableGenerator}.
* <p>
* Objects that implement {@link RandomGenerator} are typically not cryptographically secure.
* Consider instead using {@link java.security.SecureRandom} to get a cryptographically secure
@@ -91,7 +93,7 @@
public interface RandomGenerator {
/**
- * Supported randpm number Algorithms.
+ * Supported random number Algorithms.
*/
public enum Algorithm {
/**
@@ -99,34 +101,46 @@
*/
L32X64MixRandom("L32X64MixRandom"),
/**
- * L64X1024MixRandom algorithm
- */
- L64X1024MixRandom("L64X1024MixRandom"),
- /**
- * L64X1024Random algorithm
- */
- L64X1024Random("L64X1024Random"),
- /**
* L64X128MixRandom algorithm
*/
L64X128MixRandom("L64X128MixRandom"),
/**
- * L64X128Random algorithm
+ * L64X128StarStarRandom algorithm
*/
- L64X128Random("L64X128Random"),
+ L64X128StarStarRandom("L64X128StarStarRandom"),
+ /**
+ * L64X128PlusPlusRandom algorithm
+ */
+ L64X128PlusPlusRandom("L64X128PlusPlusRandom"),
/**
* L64X256MixRandom algorithm
*/
L64X256MixRandom("L64X256MixRandom"),
/**
- * L64X256Random algorithm
+ * L64X1024MixRandom algorithm
+ */
+ L64X1024MixRandom("L64X1024MixRandom"),
+ /**
+ * L128X128MixRandom algorithm
*/
- L64X256Random("L64X256Random"),
+ L128X128MixRandom("L128X128MixRandom"),
+ /**
+ * L128X128StarStarRandom algorithm
+ */
+ L128X128StarStarRandom("L128X128StarStarRandom"),
+ /**
+ * L128X128PlusPlusRandom algorithm
+ */
+ L128X128PlusPlusRandom("L128X128PlusPlusRandom"),
/**
* L128X256MixRandom algorithm
*/
L128X256MixRandom("L128X256MixRandom"),
/**
+ * L128X1024MixRandom algorithm
+ */
+ L128X1024MixRandom("L128X1024MixRandom"),
+ /**
* MRG32k3a algorithm
*/
MRG32k3a("MRG32k3a"),
@@ -141,9 +155,9 @@
@Deprecated
SecureRandom("SecureRandom"),
/**
- * Xoroshiro128Plus algorithm
+ * Xoroshiro128PlusPlus algorithm
*/
- Xoroshiro128Plus("Xoroshiro128Plus"),
+ Xoroshiro128PlusPlus("Xoroshiro128PlusPlus"),
/**
* Xoroshiro128StarStar algorithm
*/
@@ -245,7 +259,7 @@
* equivalent to {@code doubles(Long.MAX_VALUE)}.
*
* @implNote The default implementation produces a sequential stream
- * that repeatedly calls {@code nextDouble()}.
+ * that repeatedly calls {@code nextDouble()}.
*/
default DoubleStream doubles() {
return DoubleStream.generate(this::nextDouble).sequential();
@@ -262,11 +276,11 @@
* @return a stream of pseudorandomly chosen {@code double} values, each between
* the specified origin (inclusive) and the specified bound (exclusive)
*
- * @throws IllegalArgumentException if {@code randomNumberOrigin}
+ * @throws IllegalArgumentException if {@code randomNumberOrigin} is not finite,
+ * or {@code randomNumberBound} is not finite, or {@code randomNumberOrigin}
* is greater than or equal to {@code randomNumberBound}
*
- * @implNote It is permitted to implement this method in a manner
- * equivalent to
+ * @implNote It is permitted to implement this method in a manner equivalent to
* {@code doubles(Long.MAX_VALUE, randomNumberOrigin, randomNumberBound)}.
* @implNote The default implementation produces a sequential stream that repeatedly
* calls {@code nextDouble(randomNumberOrigin, randomNumberBound)}.
@@ -307,15 +321,16 @@
* @return a stream of pseudorandomly chosen {@code double} values, each between
* the specified origin (inclusive) and the specified bound (exclusive)
*
- * @throws IllegalArgumentException if {@code streamSize} is
- * less than zero, or {@code randomNumberOrigin}
+ * @throws IllegalArgumentException if {@code streamSize} is less than zero,
+ * or {@code randomNumberOrigin} is not finite,
+ * or {@code randomNumberBound} is not finite, or {@code randomNumberOrigin}
* is greater than or equal to {@code randomNumberBound}
*
- * @implNote The default implementation produces a sequential stream
- * that repeatedly calls {@code nextDouble(randomNumberOrigin, randomNumberBound)}.
+ * @implNote The default implementation produces a sequential stream that repeatedly
+ * calls {@code nextDouble(randomNumberOrigin, randomNumberBound)}.
*/
default DoubleStream doubles(long streamSize, double randomNumberOrigin,
- double randomNumberBound) {
+ double randomNumberBound) {
RandomSupport.checkStreamSize(streamSize);
RandomSupport.checkRange(randomNumberOrigin, randomNumberBound);
return doubles(randomNumberOrigin, randomNumberBound).limit(streamSize);
@@ -328,9 +343,9 @@
* @return a stream of pseudorandomly chosen {@code int} values
*
* @implNote It is permitted to implement this method in a manner
- * equivalent to {@code ints(Long.MAX_VALUE)}.
+ * equivalent to {@code ints(Long.MAX_VALUE)}.
* @implNote The default implementation produces a sequential stream
- * that repeatedly calls {@code nextInt()}.
+ * that repeatedly calls {@code nextInt()}.
*/
default IntStream ints() {
return IntStream.generate(this::nextInt).sequential();
@@ -399,7 +414,7 @@
* calls {@code nextInt(randomNumberOrigin, randomNumberBound)}.
*/
default IntStream ints(long streamSize, int randomNumberOrigin,
- int randomNumberBound) {
+ int randomNumberBound) {
RandomSupport.checkStreamSize(streamSize);
RandomSupport.checkRange(randomNumberOrigin, randomNumberBound);
return ints(randomNumberOrigin, randomNumberBound).limit(streamSize);
@@ -434,8 +449,8 @@
* @throws IllegalArgumentException if {@code randomNumberOrigin}
* is greater than or equal to {@code randomNumberBound}
*
- * @implNote It is permitted to implement this method in a manner
- * equivalent to {@code longs(Long.MAX_VALUE, randomNumberOrigin, randomNumberBound)}.
+ * @implNote It is permitted to implement this method in a manner equivalent to
+ * {@code longs(Long.MAX_VALUE, randomNumberOrigin, randomNumberBound)}.
* @implNote The default implementation produces a sequential stream that repeatedly
* calls {@code nextLong(randomNumberOrigin, randomNumberBound)}.
*/
@@ -483,7 +498,7 @@
* calls {@code nextLong(randomNumberOrigin, randomNumberBound)}.
*/
default LongStream longs(long streamSize, long randomNumberOrigin,
- long randomNumberBound) {
+ long randomNumberBound) {
RandomSupport.checkStreamSize(streamSize);
RandomSupport.checkRange(randomNumberOrigin, randomNumberBound);
return longs(randomNumberOrigin, randomNumberBound).limit(streamSize);
@@ -492,9 +507,9 @@
/**
* Returns a pseudorandomly chosen {@code boolean} value.
* <p>
- * The default implementation tests the high-order bit (sign bit) of a value produced by {@code
- * nextInt()}, on the grounds that some algorithms for pseudorandom number generation produce
- * values whose high-order bits have better statistical quality than the low-order bits.
+ * The default implementation tests the high-order bit (sign bit) of a value produced by
+ * {@code nextInt()}, on the grounds that some algorithms for pseudorandom number generation
+ * produce values whose high-order bits have better statistical quality than the low-order bits.
*
* @return a pseudorandomly chosen {@code boolean} value
*/
@@ -524,11 +539,11 @@
* zero (inclusive) and the bound (exclusive)
*
* @throws IllegalArgumentException if {@code bound} is not
- * positive and finite
+ * both positive and finite
*
* @implNote The default implementation simply calls
- * {@code RandomSupport.checkBound(bound)} and then
- * {@code RandomSupport.boundedNextFloat(this, bound)}.
+ * {@code RandomSupport.checkBound(bound)} and then
+ * {@code RandomSupport.boundedNextFloat(this, bound)}.
*/
default float nextFloat(float bound) {
RandomSupport.checkBound(bound);
@@ -545,13 +560,13 @@
* @return a pseudorandomly chosen {@code float} value between the
* origin (inclusive) and the bound (exclusive)
*
- * @throws IllegalArgumentException unless {@code origin} is finite,
- * {@code bound} is finite, and {@code origin} is less than
- * {@code bound}
+ * @throws IllegalArgumentException if {@code origin} is not finite,
+ * or {@code bound} is not finite, or {@code origin}
+ * is greater than or equal to {@code bound}
*
* @implNote The default implementation simply calls
* {@code RandomSupport.checkRange(origin, bound)} and then
- * {@code RandomSupport.boundedNextFloat(this, origin, bound)}.
+ * {@code RandomSupport.boundedNextFloat(this, origin, bound)}.
*/
default float nextFloat(float origin, float bound) {
RandomSupport.checkRange(origin, bound);
@@ -580,7 +595,7 @@
* zero (inclusive) and the bound (exclusive)
*
* @throws IllegalArgumentException if {@code bound} is not
- * positive and finite
+ * both positive and finite
*
* @implNote The default implementation simply calls
* {@code RandomSupport.checkBound(bound)} and then
@@ -601,9 +616,9 @@
* @return a pseudorandomly chosen {@code double} value between the
* origin (inclusive) and the bound (exclusive)
*
- * @throws IllegalArgumentException unless {@code origin} is finite,
- * {@code bound} is finite, and {@code origin} is less than
- * {@code bound}
+ * @throws IllegalArgumentException if {@code origin} is not finite,
+ * or {@code bound} is not finite, or {@code origin}
+ * is greater than or equal to {@code bound}
*
* @implNote The default implementation simply calls
* {@code RandomSupport.checkRange(origin, bound)} and then
--- a/src/java.base/share/classes/java/util/random/RandomSupport.java Thu Aug 29 11:33:26 2019 -0300
+++ b/src/java.base/share/classes/java/util/random/RandomSupport.java Thu Nov 14 08:54:56 2019 -0400
@@ -51,7 +51,7 @@
* Implementation Overview.
*
* This class provides utility methods and constants frequently
- * useful in the implentation of pseudorandom number generators
+ * useful in the implementation of pseudorandom number generators
* that satisfy the interface {@link RandomGenerator}.
*
* File organization: First some message strings, then the main
@@ -84,7 +84,7 @@
*
* @param distance the proposed jump distance
*
- * @throws IllegalArgumentException if {@code size} not positive, finite, and an exact integer
+ * @throws IllegalArgumentException if {@code size} fails to be positive, finite, and an exact integer
*/
public static void checkJumpDistance(double distance) {
if (!(distance > 0.0 && distance < Float.POSITIVE_INFINITY
@@ -98,7 +98,7 @@
*
* @param bound the upper bound (exclusive)
*
- * @throws IllegalArgumentException if {@code bound} is not positive and finite
+ * @throws IllegalArgumentException if {@code bound} fails to be positive and finite
*/
public static void checkBound(float bound) {
if (!(bound > 0.0 && bound < Float.POSITIVE_INFINITY)) {
@@ -111,7 +111,7 @@
*
* @param bound the upper bound (exclusive)
*
- * @throws IllegalArgumentException if {@code bound} is not positive and finite
+ * @throws IllegalArgumentException if {@code bound} fails to be positive and finite
*/
public static void checkBound(double bound) {
if (!(bound > 0.0 && bound < Double.POSITIVE_INFINITY)) {
@@ -151,8 +151,8 @@
* @param origin the least value (inclusive) in the range
* @param bound the upper bound (exclusive) of the range
*
- * @throws IllegalArgumentException unless {@code origin} is finite, {@code bound} is finite,
- * and {@code bound - origin} is finite
+ * @throws IllegalArgumentException if {@code origin} is not finite, {@code bound} is not finite,
+ * or {@code bound - origin} is not finite
*/
public static void checkRange(float origin, float bound) {
if (!(origin < bound && (bound - origin) < Float.POSITIVE_INFINITY)) {
@@ -166,8 +166,8 @@
* @param origin the least value (inclusive) in the range
* @param bound the upper bound (exclusive) of the range
*
- * @throws IllegalArgumentException unless {@code origin} is finite, {@code bound} is finite,
- * and {@code bound - origin} is finite
+ * @throws IllegalArgumentException if {@code origin} is not finite, {@code bound} is not finite,
+ * or {@code bound - origin} is not finite
*/
public static void checkRange(double origin, double bound) {
if (!(origin < bound && (bound - origin) < Double.POSITIVE_INFINITY)) {
@@ -1141,35 +1141,44 @@
*/
/**
- * Needs comment (was made public to be overridden out of package.)
+ * Create an instance of {@link Spliterator.OfInt} that for each traversal position
+ * between the specified index (inclusive) and the specified fence (exclusive) generates
+ * a pseudorandomly chosen {@code int} value between the specified origin (inclusive) and
+ * the specified bound (exclusive).
*
- * @param index low
- * @param fence high
- * @param origin low
- * @param bound high
- * @return result
+ * @param index the (inclusive) lower bound on traversal positions
+ * @param fence the (exclusive) upper bound on traversal positions
+ * @param origin the (inclusive) lower bound on the pseudorandom values to be generated
+ * @param bound the (exclusive) upper bound on the pseudorandom values to be generated
+ * @return an instance of {@link Spliterator.OfInt}
*/
public abstract Spliterator.OfInt makeIntsSpliterator(long index, long fence, int origin, int bound);
/**
- * Needs comment (was made public to be overridden out of package.)
+ * Create an instance of {@link Spliterator.OfLong} that for each traversal position
+ * between the specified index (inclusive) and the specified fence (exclusive) generates
+ * a pseudorandomly chosen {@code long} value between the specified origin (inclusive) and
+ * the specified bound (exclusive).
*
- * @param index low
- * @param fence high
- * @param origin low
- * @param bound high
- * @return result
+ * @param index the (inclusive) lower bound on traversal positions
+ * @param fence the (exclusive) upper bound on traversal positions
+ * @param origin the (inclusive) lower bound on the pseudorandom values to be generated
+ * @param bound the (exclusive) upper bound on the pseudorandom values to be generated
+ * @return an instance of {@link Spliterator.OfLong}
*/
public abstract Spliterator.OfLong makeLongsSpliterator(long index, long fence, long origin, long bound);
/**
- * Needs comment (was made public to be overridden out of package.)
+ * Create an instance of {@link Spliterator.OfDouble} that for each traversal position
+ * between the specified index (inclusive) and the specified fence (exclusive) generates
+ * a pseudorandomly chosen {@code double} value between the specified origin (inclusive) and
+ * the specified bound (exclusive).
*
- * @param index low
- * @param fence high
- * @param origin low
- * @param bound high
- * @return result
+ * @param index the (inclusive) lower bound on traversal positions
+ * @param fence the (exclusive) upper bound on traversal positions
+ * @param origin the (inclusive) lower bound on the pseudorandom values to be generated
+ * @param bound the (exclusive) upper bound on the pseudorandom values to be generated
+ * @return an instance of {@link Spliterator.OfDouble}
*/
public abstract Spliterator.OfDouble makeDoublesSpliterator(long index, long fence, double origin, double bound);
@@ -1922,11 +1931,10 @@
* provide implementations for the methods {@code nextInt()}, {@code nextLong()}, {@code period()},
* and {@code split(SplittableGenerator)}.
* <p>
- * (If the pseudorandom number generator also has the ability to jump, then the programmer may wish
- * to consider instead extending the class {@link ArbitrarilyJumpableGenerator}. But if the pseudorandom
- * number generator furthermore has the ability to jump an arbitrary specified distance, then the
- * programmer may wish to consider instead extending the class {@link
- * AbstractArbitrarilyJumpableGenerator}.)
+ * (If the pseudorandom number generator also has the ability to jump an arbitrary
+ * specified distance, then the programmer may wish to consider instead extending the
+ * class {@link AbstractArbitrarilyJumpableGenerator}. See also the class
+ * {@link AbstractSplittableWithBrineGenerator}.)
* <p>
* The programmer should generally provide at least three constructors: one that takes no arguments,
* one that accepts a {@code long} seed value, and one that accepts an array of seed {@code byte}
@@ -1934,8 +1942,8 @@
* initializing some static state from which to derive defaults seeds for use by the no-argument
* constructor.
* <p>
- * For the stream methods (such as {@code ints()} and {@code splits()}), this class provides {@link
- * Spliterator} based implementations that allow parallel execution when appropriate.
+ * For the stream methods (such as {@code ints()} and {@code splits()}), this class provides
+ * {@link Spliterator}-based implementations that allow parallel execution when appropriate.
* <p>
* The documentation for each non-abstract method in this class describes its implementation in
* detail. Each of these methods may be overridden if the pseudorandom number generator being
@@ -1949,15 +1957,12 @@
* Implementation Overview.
*
* This class provides most of the "user API" methods needed to
- * satisfy the interface JumpableGenerator. Most of these methods
+ * satisfy the interface SplittableGenerator. Most of these methods
* are in turn inherited from AbstractGenerator and the non-public class
- * AbstractSpliteratorGenerator; this file implements two versions of the
+ * AbstractSpliteratorGenerator; this class provides two versions of the
* splits method and defines the spliterators necessary to support
* them.
*
- * The abstract split() method from interface SplittableGenerator is redeclared
- * here so as to narrow the return type to AbstractSplittableGenerator.
- *
* File organization: First the non-public methods needed by the class
* AbstractSpliteratorGenerator, then the main public methods, followed by some
* custom spliterator classes.
@@ -1982,9 +1987,9 @@
/* ---------------- public methods ---------------- */
/**
- * Implements the @code{split()} method as {@code this.split(this) }.
+ * Implements the @code{split()} method as {@code this.split(this)}.
*
- * @return the new {@link AbstractSplittableGenerator} instance
+ * @return the new {@link SplittableGenerator} instance
*/
public SplittableGenerator split() {
return this.split(this);
@@ -2200,11 +2205,13 @@
* versions into one class by treating "infinite" as equivalent to Long.MAX_VALUE.
* For splits, it uses the standard divide-by-two approach.
*/
- static class RandomSplitsSpliterator extends RandomSupport.RandomSpliterator implements Spliterator<SplittableGenerator> {
+ static class RandomSplitsSpliterator extends RandomSpliterator implements Spliterator<SplittableGenerator> {
final SplittableGenerator generatingGenerator;
final SplittableGenerator constructingGenerator;
- RandomSplitsSpliterator(SplittableGenerator generatingGenerator, long index, long fence, SplittableGenerator constructingGenerator) {
+ RandomSplitsSpliterator(SplittableGenerator generatingGenerator,
+ long index, long fence,
+ SplittableGenerator constructingGenerator) {
super(index, fence);
this.generatingGenerator = generatingGenerator;
this.constructingGenerator = constructingGenerator;
@@ -2244,5 +2251,232 @@
}
+ /**
+ * This class provides much of the implementation of the {@link SplittableGenerator} interface, to
+ * minimize the effort required to implement this interface. It is similar to the class
+ * {@link AbstractSplittableGenerator} but makes use of the brine technique for ensuring that
+ * distinct generators created by a single call to a {@code splits} method have distinct state cycles.
+ * <p>
+ * To implement a pseudorandom number generator, the programmer needs only to extend this class and
+ * provide implementations for the methods {@code nextInt()}, {@code nextLong()}, {@code period()},
+ * and {@code split(SplittableGenerator, long)}.
+ * <p>
+ * The programmer should generally provide at least three constructors: one that takes no arguments,
+ * one that accepts a {@code long} seed value, and one that accepts an array of seed {@code byte}
+ * values. This class provides a public {@code initialSeed()} method that may be useful in
+ * initializing some static state from which to derive defaults seeds for use by the no-argument
+ * constructor.
+ * <p>
+ * For the stream methods (such as {@code ints()} and {@code splits()}), this class provides
+ * {@link Spliterator}-based implementations that allow parallel execution when appropriate.
+ * <p>
+ * The documentation for each non-abstract method in this class describes its implementation in
+ * detail. Each of these methods may be overridden if the pseudorandom number generator being
+ * implemented admits a more efficient implementation.
+ *
+ * @since 14
+ */
+ public abstract static class AbstractSplittableWithBrineGenerator
+ extends AbstractSplittableGenerator {
+
+ /*
+ * Implementation Overview.
+ *
+ * This class provides most of the "user API" methods needed to
+ * satisfy the interface SplittableGenerator. Most of these methods
+ * are in turn inherited from AbstractSplittableGenerator and the non-public class
+ * AbstractSpliteratorGenerator; this class provides four versions of the
+ * splits method and defines the spliterators necessary to support
+ * them.
+ *
+ * File organization: First the non-public methods needed by the class
+ * AbstractSplittableWithBrineGenerator, then the main public methods,
+ * followed by some custom spliterator classes needed for stream methods.
+ */
+
+ // The salt consists groups of bits each SALT_SHIFT in size, starting from
+ // the left-hand (high-order) end of the word. We can regard them as
+ // digits base (1 << SALT_SHIFT). If SALT_SHIFT does not divide 64
+ // evenly, then any leftover bits at the low end of the word are zero.
+ // The lowest digit of the salt is set to the largest possible digit
+ // (all 1-bits, or ((1 << SALT_SHIFT) - 1)); all other digits are set
+ // to a randomly chosen value less than that largest possible digit.
+ // The salt may be shifted left by SALT_SHIFT any number of times.
+ // If any salt remains in the word, its right-hand end can be identified
+ // by searching from left to right for an occurrence of a digit that is
+ // all 1-bits (not that we ever do that; this is simply a proof that one
+ // can identify the boundary between the salt and the index if any salt
+ // remains in the word). The idea is that before computing the bitwise OR
+ // of an index and the salt, one can first check to see whether the
+ // bitwise AND is nonzero; if so, one can shift the salt left by
+ // SALT_SHIFT and try again. In this way, when the bitwise OR is
+ // computed, if the salt is nonzero then its rightmost 1-bit is to the
+ // left of the leftmost 1-bit of the index.
+
+ // We need 2 <= SALT_SHIFT <= 63 (3 through 8 are good values; 4 is probably best)
+ static final int SALT_SHIFT = 4;
+
+ // Methods required by class AbstractSpliteratorGenerator (override)
+ Spliterator<SplittableGenerator> makeSplitsSpliterator(long index, long fence, SplittableGenerator source) {
+ // This little algorithm to generate a new salt value is carefully
+ // designed to work even if SALT_SHIFT does not evenly divide 64
+ // (the number of bits in a long value).
+ long bits = nextLong();
+ long multiplier = (1 << SALT_SHIFT) - 1;
+ long salt = multiplier << (64 - SALT_SHIFT);
+ while ((salt & multiplier) != 0) {
+ long digit = Math.multiplyHigh(bits, multiplier);
+ salt = (salt >>> SALT_SHIFT) | (digit << (64 - SALT_SHIFT));
+ bits *= multiplier;
+ }
+ // This is the point at which newly generated salt gets injected into
+ // the root of a newly created brine-generating splits-spliterator.
+ return new RandomSplitsSpliteratorWithSalt(source, index, fence, this, salt);
+ }
+
+ /* ---------------- public methods ---------------- */
+
+ // Stream methods for splitting
+
+ /**
+ * Constructs and returns a new instance of {@code AbstractSplittableWithBrineGenerator}
+ * that shares no mutable state with this instance. However, with very high
+ * probability, the set of values collectively generated by the two objects
+ * should have the same statistical properties as if the same quantity of
+ * values were generated by a single thread using a single may be
+ * {@code AbstractSplittableWithBrineGenerator} object. Either or both of the two objects
+ * further split using the {@code split()} method, and the same expected
+ * statistical properties apply to the entire set of generators constructed
+ * by such recursive splitting.
+ *
+ * @param brine a long value, of which the low 63 bits provide a unique id
+ * among calls to this method for constructing a single series of Generator objects.
+ *
+ * @return the new {@code AbstractSplittableWithBrineGenerator} instance
+ */
+ public SplittableGenerator split(long brine) {
+ return this.split(this, brine);
+ }
+
+ /**
+ * Constructs and returns a new instance of {@code L64X128MixRandom}
+ * that shares no mutable state with this instance.
+ * However, with very high probability, the set of values collectively
+ * generated by the two objects has the same statistical properties as if
+ * same the quantity of values were generated by a single thread using
+ * a single {@code L64X128MixRandom} object. Either or both of the two
+ * objects may be further split using the {@code split} method,
+ * and the same expected statistical properties apply to the
+ * entire set of generators constructed by such recursive splitting.
+ *
+ * @param source a {@code SplittableGenerator} instance to be used instead
+ * of this one as a source of pseudorandom bits used to
+ * initialize the state of the new ones.
+ * @return a new instance of {@code L64X128MixRandom}
+ */
+ public SplittableGenerator split(SplittableGenerator source) {
+ // It's a one-off: supply randomly chosen brine
+ return this.split(source, source.nextLong());
+ }
+
+ /**
+ * Constructs and returns a new instance of {@code AbstractSplittableWithBrineGenerator}
+ * that shares no mutable state with this instance. However, with very high
+ * probability, the set of values collectively generated by the two objects
+ * should have the same statistical properties as if the same quantity of
+ * values were generated by a single thread using a single may be
+ * {@code AbstractSplittableWithBrineGenerator} object. Either or both of the two objects
+ * further split using the {@code split()} method, and the same expected
+ * statistical properties apply to the entire set of generators constructed
+ * by such recursive splitting.
+ *
+ * @param source a {@code SplittableGenerator} instance to be used instead
+ * of this one as a source of pseudorandom bits used to
+ * initialize the state of the new ones.
+ * @param brine a long value, of which the low 63 bits provide a unique id
+ * among calls to this method for constructing a single series of
+ * {@code RandomGenerator} objects.
+ *
+ * @return the new {@code AbstractSplittableWithBrineGenerator} instance
+ */
+ public abstract SplittableGenerator split(SplittableGenerator source, long brine);
+
+
+ /* ---------------- spliterator ---------------- */
+ /**
+ * Alternate spliterator for stream of generators of type SplittableGenerator. We multiplex
+ * the two versions into one class by treating "infinite" as equivalent to Long.MAX_VALUE.
+ * For splits, it uses the standard divide-by-two approach.
+ *
+ * This differs from {@code SplittableGenerator.RandomSplitsSpliterator} in that it provides
+ * a brine argument (a mixture of salt and an index) when calling the {@code split} method.
+ */
+ static class RandomSplitsSpliteratorWithSalt
+ extends RandomSpliterator implements Spliterator<SplittableGenerator> {
+
+ final SplittableGenerator generatingGenerator;
+ final AbstractSplittableWithBrineGenerator constructingGenerator;
+ long salt;
+
+ // Important invariant: 0 <= index <= fence
+
+ // Important invariant: if salt and index are both nonzero,
+ // the rightmost 1-bit of salt is to the left of the leftmost 1-bit of index.
+ // If necessary, the salt can be leftshifted by SALT_SHIFT as many times as
+ // necessary to maintain the invariant.
+
+ RandomSplitsSpliteratorWithSalt(SplittableGenerator generatingGenerator, long index, long fence,
+ AbstractSplittableWithBrineGenerator constructingGenerator, long salt) {
+ super(index, fence);
+ this.generatingGenerator = generatingGenerator;
+ this.constructingGenerator = constructingGenerator;
+ while ((salt != 0) && (Long.compareUnsigned(salt & -salt, index) <= 0)) {
+ salt = salt << SALT_SHIFT;
+ }
+ this.salt = salt;
+ }
+
+ public Spliterator<SplittableGenerator> trySplit() {
+ long i = index, m = (i + fence) >>> 1;
+ if (m <= i) return null;
+ RandomSplitsSpliteratorWithSalt result =
+ new RandomSplitsSpliteratorWithSalt(generatingGenerator.split(), i, m, constructingGenerator, salt);
+ index = m;
+ while ((salt != 0) && (Long.compareUnsigned(salt & -salt, index) <= 0)) {
+ salt = salt << SALT_SHIFT;
+ }
+ return result;
+ }
+
+ public boolean tryAdvance(Consumer<? super SplittableGenerator> consumer) {
+ if (consumer == null) throw new NullPointerException();
+ long i = index, f = fence;
+ if (i < f) {
+ consumer.accept(constructingGenerator.split(generatingGenerator, salt | i));
+ ++i;
+ index = i;
+ if ((i & salt) != 0) salt <<= SALT_SHIFT;
+ return true;
+ }
+ return false;
+ }
+
+ public void forEachRemaining(Consumer<? super SplittableGenerator> consumer) {
+ if (consumer == null) throw new NullPointerException();
+ long i = index, f = fence;
+ if (i < f) {
+ index = f;
+ AbstractSplittableWithBrineGenerator c = constructingGenerator;
+ SplittableGenerator r = generatingGenerator;
+ do {
+ consumer.accept(c.split(r, salt | i));
+ ++i;
+ if ((i & salt) != 0) salt <<= SALT_SHIFT;
+ } while (i < f);
+ }
+ }
+ }
+
+ }
+
}
-
--- a/src/java.base/share/classes/java/util/random/Xoroshiro128Plus.java Thu Aug 29 11:33:26 2019 -0300
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,300 +0,0 @@
-/*
- * Copyright (c) 2013, 2019, Oracle and/or its affiliates. All rights reserved.
- * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
- *
- * This code is free software; you can redistribute it and/or modify it
- * under the terms of the GNU General Public License version 2 only, as
- * published by the Free Software Foundation. Oracle designates this
- * particular file as subject to the "Classpath" exception as provided
- * by Oracle in the LICENSE file that accompanied this code.
- *
- * This code is distributed in the hope that it will be useful, but WITHOUT
- * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
- * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
- * version 2 for more details (a copy is included in the LICENSE file that
- * accompanied this code).
- *
- * You should have received a copy of the GNU General Public License version
- * 2 along with this work; if not, write to the Free Software Foundation,
- * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
- *
- * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
- * or visit www.oracle.com if you need additional information or have any
- * questions.
- */
-
-package java.util.random;
-
-import java.math.BigInteger;
-import java.util.concurrent.atomic.AtomicLong;
-import java.util.random.RandomGenerator.LeapableGenerator;
-
-/**
- * A generator of uniform pseudorandom values applicable for use in
- * (among other contexts) isolated parallel computations that may
- * generate subtasks. Class {@link Xoroshiro128Plus} implements
- * interfaces {@link RandomGenerator} and {@link LeapableGenerator},
- * and therefore supports methods for producing pseudorandomly chosen
- * numbers of type {@code int}, {@code long}, {@code float}, and {@code double}
- * as well as creating new {@link Xoroshiro128Plus} objects
- * by "jumping" or "leaping".
- * <p>
- * Series of generated values pass the TestU01 BigCrush and PractRand test suites
- * that measure independence and uniformity properties of random number generators,
- * <em>except</em> that it does not pass the binary rank tests of PractRand,
- * which fail due to the lowest bit being an LFSR; all other bits pass all tests.
- * For this reason may be best for some purposes to use this generator to generate
- * pseudorandom {@code int}, {@code float}, and {@code double} values but not
- * {@code long} values. For the same reason, it may be best not to use the
- * method {@code nextGaussian} or {@code nextExponential} with this generator.
- * <p>
- * The class {@link Xoroshiro128Plus} uses the {@code xoroshiro128} algorithm,
- * version 1.0 (parameters 24, 16, 37), with the "+" scrambler
- * (the returned value is the sum of the two state variables {@code x0} and {@code x1}).
- * Its state consists of two {@code long} fields {@code x0} and {@code x1},
- * which can take on any values provided that they are not both zero.
- * The period of this generator is 2<sup>128</sup>-1.
- * <p>
- * The 64-bit values produced by the {@code nextLong()} method are equidistributed.
- * To be precise, over the course of the cycle of length 2<sup>128</sup>-1,
- * each nonzero {@code long} value is generated 2<sup>64</sup> times,
- * but the value 0 is generated only 2<sup>64</sup>-1 times.
- * The values produced by the {@code nextInt()}, {@code nextFloat()}, and {@code nextDouble()}
- * methods are likewise equidistributed.
- * <p>
- * Instances {@link Xoroshiro128Plus} are <em>not</em> thread-safe.
- * They are designed to be used so that each thread as its own instance.
- * The methods {@link #jump} and {@link #leap} and {@link #jumps} and {@link #leaps}
- * can be used to construct new instances of {@link Xoroshiro128Plus} that traverse
- * other parts of the state cycle.
- * <p>
- * Instances of {@link Xoroshiro128Plus} are not cryptographically
- * secure. Consider instead using {@link java.security.SecureRandom}
- * in security-sensitive applications. Additionally,
- * default-constructed instances do not use a cryptographically random
- * seed unless the {@linkplain System#getProperty system property}
- * {@code java.util.secureRandomSeed} is set to {@code true}.
- *
- * @since 14
- */
-public final class Xoroshiro128Plus implements LeapableGenerator {
-
- /*
- * Implementation Overview.
- *
- * This is an implementation of the xoroshiro128+ algorithm written
- * in 2016 by David Blackman and Sebastiano Vigna (vigna@acm.org),
- * and updated with improved parameters in 2018.
- * See http://xoshiro.di.unimi.it and these two papers:
- *
- * Sebastiano Vigna. 2016. An Experimental Exploration of Marsaglia's
- * xorshift Generators, Scrambled. ACM Transactions on Mathematical
- * Software 42, 4, Article 30 (June 2016), 23 pages.
- * https://doi.org/10.1145/2845077
- *
- * David Blackman and Sebastiano Vigna. 2018. Scrambled Linear
- * Pseudorandom Number Generators. Computing Research Repository (CoRR).
- * http://arxiv.org/abs/1805.01407
- *
- * The jump operation moves the current generator forward by 2*64
- * steps; this has the same effect as calling nextLong() 2**64
- * times, but is much faster. Similarly, the leap operation moves
- * the current generator forward by 2*96 steps; this has the same
- * effect as calling nextLong() 2**96 times, but is much faster.
- * The copy method may be used to make a copy of the current
- * generator. Thus one may repeatedly and cumulatively copy and
- * jump to produce a sequence of generators whose states are well
- * spaced apart along the overall state cycle (indeed, the jumps()
- * and leaps() methods each produce a stream of such generators).
- * The generators can then be parceled out to other threads.
- *
- * File organization: First the non-public methods that constitute the
- * main algorithm, then the public methods. Note that many methods are
- * defined by classes {@link AbstractJumpableGenerator} and {@link AbstractGenerator}.
- */
-
- /* ---------------- static fields ---------------- */
-
- /**
- * The seed generator for default constructors.
- */
- private static final AtomicLong defaultGen = new AtomicLong(RandomSupport.initialSeed());
-
- /*
- * The period of this generator, which is 2**128 - 1.
- */
- private static final BigInteger PERIOD =
- BigInteger.ONE.shiftLeft(128).subtract(BigInteger.ONE);
-
- /* ---------------- instance fields ---------------- */
-
- /**
- * The per-instance state.
- * At least one of the two fields x0 and x1 must be nonzero.
- */
- private long x0, x1;
-
- /* ---------------- constructors ---------------- */
-
- /**
- * Basic constructor that initializes all fields from parameters.
- * It then adjusts the field values if necessary to ensure that
- * all constraints on the values of fields are met.
- *
- * @param x0 first word of the initial state
- * @param x1 second word of the initial state
- */
- public Xoroshiro128Plus(long x0, long x1) {
- this.x0 = x0;
- this.x1 = x1;
- // If x0 and x1 are both zero, we must choose nonzero values.
- if ((x0 | x1) == 0) {
- // At least one of the two values generated here will be nonzero.
- this.x0 = RandomSupport.mixStafford13(x0 += RandomSupport.GOLDEN_RATIO_64);
- this.x1 = (x0 += RandomSupport.GOLDEN_RATIO_64);
- }
- }
-
- /**
- * Creates a new instance of {@link Xoroshiro128Plus} using the
- * specified {@code long} value as the initial seed. Instances of
- * {@link Xoroshiro128Plus} created with the same seed in the same
- * program generate identical sequences of values.
- *
- * @param seed the initial seed
- */
- public Xoroshiro128Plus(long seed) {
- // Using a value with irregularly spaced 1-bits to xor the seed
- // argument tends to improve "pedestrian" seeds such as 0 or
- // other small integers. We may as well use SILVER_RATIO_64.
- //
- // The x values are then filled in as if by a SplitMix PRNG with
- // GOLDEN_RATIO_64 as the gamma value and Stafford13 as the mixer.
- this(RandomSupport.mixStafford13(seed ^= RandomSupport.SILVER_RATIO_64),
- RandomSupport.mixStafford13(seed + RandomSupport.GOLDEN_RATIO_64));
- }
-
- /**
- * Creates a new instance of {@link Xoroshiro128Plus} that is likely to
- * generate sequences of values that are statistically independent
- * of those of any other instances in the current program execution,
- * but may, and typically does, vary across program invocations.
- */
- public Xoroshiro128Plus() {
- // Using GOLDEN_RATIO_64 here gives us a good Weyl sequence of values.
- this(defaultGen.getAndAdd(RandomSupport.GOLDEN_RATIO_64));
- }
-
- /**
- * Creates a new instance of {@link Xoroshiro128Plus} using the specified array of
- * initial seed bytes. Instances of {@link Xoroshiro128Plus} created with the same
- * seed array in the same program execution generate identical sequences of values.
- *
- * @param seed the initial seed
- */
- public Xoroshiro128Plus(byte[] seed) {
- // Convert the seed to 2 long values, which are not both zero.
- long[] data = RandomSupport.convertSeedBytesToLongs(seed, 2, 2);
- long x0 = data[0], x1 = data[1];
- this.x0 = x0;
- this.x1 = x1;
- }
-
- /* ---------------- public methods ---------------- */
-
- public Xoroshiro128Plus copy() { return new Xoroshiro128Plus(x0, x1); }
-
-
- /*
- * To the extent possible under law, the author has dedicated all copyright and related and
- * neighboring rights to this software to the public domain worldwide. This software is distributed
- * without any warranty.
- * <p>
- * See <http://creativecommons.org/publicdomain/zero/1.0/>.
- */
-
- /*
- * This is the successor to xorshift128+. It is the fastest full-period generator passing
- * BigCrush without systematic failures, but due to the relatively short period it is acceptable
- * only for applications with a mild amount of parallelism; otherwise, use a xorshift1024*
- * generator.
- * <p>
- * Beside passing BigCrush, this generator passes the PractRand test suite up to (and included)
- * 16TB, with the exception of binary rank tests, which fail due to the lowest bit being an
- * LFSR; all other bits pass all tests. We suggest to use a sign test to extract a random
- * Boolean value.
- * <p>
- * Note that the generator uses a simulated rotate operation, which most C compilers will turn
- * into a single instruction. In Java, you can use Long.rotateLeft(). In languages that do not
- * make low-level rotation instructions accessible xorshift128+ could be faster.
- * <p>
- * The state must be seeded so that it is not everywhere zero. If you have a 64-bit seed, we
- * suggest to seed a splitmix64 generator and use its output to fill s.
- */
-
- /**
- * Returns a pseudorandom {@code long} value.
- *
- * @return a pseudorandom {@code long} value
- */
- public long nextLong() {
- final long s0 = x0;
- long s1 = x1;
- final long z = s0 + s1;
-
- s1 ^= s0;
- x0 = Long.rotateLeft(s0, 24) ^ s1 ^ (s1 << 16); // a, b
- x1 = Long.rotateLeft(s1, 37); // c
-
- return z;
- }
-
- public BigInteger period() {
- return PERIOD;
- }
-
- public double defaultJumpDistance() {
- return 0x1.0p64;
- }
-
- public double defaultLeapDistance() {
- return 0x1.0p96;
- }
-
- private static final long[] JUMP_TABLE = { 0xdf900294d8f554a5L, 0x170865df4b3201fcL };
-
- private static final long[] LEAP_TABLE = { 0xd2a98b26625eee7bL, 0xdddf9b1090aa7ac1L };
-
- /*
- * This is the jump function for the generator. It is equivalent
- * to 2**64 calls to nextLong(); it can be used to generate 2**64
- * non-overlapping subsequences for parallel computations.
- */
- public void jump() {
- jumpAlgorithm(JUMP_TABLE);
- }
-
- /**
- * This is the long-jump function for the generator. It is equivalent to 2**96 calls to next();
- * it can be used to generate 2**32 starting points, from each of which jump() will generate
- * 2**32 non-overlapping subsequences for parallel distributed computations.
- */
- public void leap() {
- jumpAlgorithm(LEAP_TABLE);
- }
-
- private void jumpAlgorithm(long[] table) {
- long s0 = 0, s1 = 0;
- for (int i = 0; i < table.length; i++) {
- for (int b = 0; b < 64; b++) {
- if ((table[i] & (1L << b)) != 0) {
- s0 ^= x0;
- s1 ^= x1;
- }
- nextLong();
- }
- x0 = s0;
- x1 = s1;
- }
- }
-}
--- a/src/java.base/share/classes/java/util/random/Xoroshiro128StarStar.java Thu Aug 29 11:33:26 2019 -0300
+++ b/src/java.base/share/classes/java/util/random/Xoroshiro128StarStar.java Thu Nov 14 08:54:56 2019 -0400
@@ -154,9 +154,8 @@
this.x1 = x1;
// If x0 and x1 are both zero, we must choose nonzero values.
if ((x0 | x1) == 0) {
- // At least one of the two values generated here will be nonzero.
- this.x0 = RandomSupport.mixStafford13(x0 += RandomSupport.GOLDEN_RATIO_64);
- this.x1 = (x0 += RandomSupport.GOLDEN_RATIO_64);
+ this.x0 = RandomSupport.GOLDEN_RATIO_64;
+ this.x1 = RandomSupport.SILVER_RATIO_64;
}
}
@@ -244,13 +243,15 @@
public long nextLong() {
final long s0 = x0;
long s1 = x1;
- final long z = s0;
+ // Compute the result based on current state information
+ // (this allows the computation to be overlapped with state update).
+ final long result = Long.rotateLeft(s0 * 5, 7) * 9; // "starstar" mixing function
s1 ^= s0;
x0 = Long.rotateLeft(s0, 24) ^ s1 ^ (s1 << 16); // a, b
x1 = Long.rotateLeft(s1, 37); // c
- return Long.rotateLeft(z * 5, 7) * 9; // "starstar" mixing function
+ return result;
}
public BigInteger period() {
--- a/src/java.base/share/classes/java/util/random/Xoshiro256StarStar.java Thu Aug 29 11:33:26 2019 -0300
+++ b/src/java.base/share/classes/java/util/random/Xoshiro256StarStar.java Thu Nov 14 08:54:56 2019 -0400
@@ -233,8 +233,11 @@
* @return a pseudorandom {@code long} value
*/
public long nextLong() {
- final long z = x0;
- long q0 = x0, q1 = x1, q2 = x2, q3 = x3;
+ // Compute the result based on current state information
+ // (this allows the computation to be overlapped with state update).
+ final long result = Long.rotateLeft(x0 * 5, 7) * 9; // "starstar" mixing function
+
+ long q0 = x0, q1 = x1, q2 = x2, q3 = x3;
{ // xoshiro256 1.0
long t = q1 << 17;
q2 ^= q0;
@@ -245,7 +248,7 @@
q3 = Long.rotateLeft(q3, 45);
}
x0 = q0; x1 = q1; x2 = q2; x3 = q3;
- return Long.rotateLeft(z * 5, 7) * 9; // "starstar" mixing function
+ return result;
}
public BigInteger period() {
--- a/src/java.base/share/classes/java/util/random/package-info.java Thu Aug 29 11:33:26 2019 -0300
+++ b/src/java.base/share/classes/java/util/random/package-info.java Thu Nov 14 08:54:56 2019 -0400
@@ -24,7 +24,77 @@
*/
/**
- * Package info goes here.
+ * Classes and interfaces that support the definition and use of "random generators", a term that
+ * is meant to cover what have traditionally been called "random number generators" as well as
+ * generators of other sorts of randomly chosen values, and also to cover not only deterministic
+ * (pseudorandom) algorithms but also generators of values that use some "truly random" physical
+ * source (perhaps making use of thermal noise, for example, or quantum-mechanical effects).
+ *
+ * The principal interface is {@link java.util.random.RandomGenerator}, which provides methods
+ * for requesting individual values of type {@code int}, {@code long}, {@code float}, {@code double}, or {@code boolean}
+ * chosen (pseudo)randomly from a uniform distribution; methods for requesting values of type {@code double}
+ * chosen (pseudo)randomly from a normal distribution or from an exponential distribution;
+ * and methods for creating streams of (pseudo)randomly chosen values of type {@code int}, {@code long}, or {@code double}.
+ * These streams are spliterator-based, allowing for parallel processing of their elements.
+ *
+ * An important subsidiary interface is {@link java.util.random.RandomGenerator.StreamableGenerator},
+ * which provides methods for creating spliterator-based streams of {@code RandomGenerator} objects,
+ * allowing for allowing for parallel processing of these objects using multiple threads.
+ * Unlike {@link java.util.Random}, most implementations of {@code java.util.random.RandomGenerator}
+ * are <i>not</i> thread-safe. The intent is that instances should not be shared among threads;
+ * rather, each thread should have its own random generator(s) to use. The various pseudorandom algorithms
+ * provided by this package are designed so that multiple instances will (with very high probability) behave as
+ * if statistically independent.
+ *
+ * Historically, most pseudorandom generator algorithms have been based on some sort of
+ * finite-state machine with a single, large cycle of states; when it is necessary to have
+ * multiple threads use the same algorithm simultaneously, the usual technique is to arrange for
+ * each thread to traverse a different region of the state cycle. These regions may be doled out
+ * to threads by starting with a single initial state and then using a "jump function" that
+ * travels a long distance around the cycle (perhaps 2<sup>64</sup> steps or more); the jump function is applied repeatedly
+ * and sequentially, to identify widely spaced initial states for each thread's generator. This strategy is
+ * supported by the interface {@link java.util.random.RandomGenerator.JumpableGenerator}.
+ * Sometimes it is desirable to support two levels of jumping (by long distances and
+ * by <i>really</i> long distances); this strategy is supported by the interface
+ * {@link java.util.random.RandomGenerator.LeapableGenerator}. There is also an interface
+ * {@link java.util.random.RandomGenerator.ArbitrarilyJumpableGenerator} for algorithms that
+ * allow jumping along the state cycle by any user-specified distance.
+ * In this package, implementations of these interfaces include
+ * {@link java.util.random.Xoroshiro128PlusPlus},
+ * {@link java.util.random.Xoroshiro128StarStar},
+ * {@link java.util.random.Xoshiro256StarStar},
+ * and {@link java.util.random.MRG32K3A}.
+ *
+ * A more recent category of "splittable" pseudorandom generator algorithms uses a large family
+ * of state cycles and makes some attempt to ensure that distinct instances use different state
+ * cycles; but even if two instances "accidentally" use the same state cycle, they are highly
+ * likely to traverse different regions parts of that shared state cycle. This strategy is
+ * supported by the interface {@link java.util.random.RandomGenerator.SplittableGenerator}.
+ * In this package, implementations of this interface include
+ * {@link java.util.random.L32X64MixRandom},
+ * {@link java.util.random.L64X128MixRandom},
+ * {@link java.util.random.L64X128PlusPlusRandom},
+ * {@link java.util.random.L64X128StarStarMixRandom},
+ * {@link java.util.random.L64X256MixRandom},
+ * {@link java.util.random.L64X1024MixRandom},
+ * {@link java.util.random.L128X128MixRandom},
+ * {@link java.util.random.L128X128PlusPlusRandom},
+ * {@link java.util.random.L128X128StarStarMixRandom},
+ * {@link java.util.random.L128X256MixRandom},
+ * {@link java.util.random.L128X1024MixRandom},
+ * and {@link java.util.SplittableRandom}.
+ * Generally speaking, among the "{@code LmmmXnnn}" generators, the state size of the generator is
+ * {@code (mmm - 1 + nnn)} bits and the memory required for an instance is {@code (2 * mmm + nnn)} bits;
+ * larger values of "{@code mmm}" imply a lower probability that two instances will traverse the
+ * same state cycle; and larger values of "{@code nnn}" imply that the generator is equidistributed
+ * in a larger number of dimensions. A class with "{@code Mix}" in its name uses a strong mixing
+ * function with excellent avalanche characteristics; a class with "{@code StarStar}" or "{@code PlusPlus}"
+ * in its name uses a weaker but faster mixing function. See the documentation for individual classes
+ * for details about their specific characteristics.
+ *
+ * The class {@link java.util.random.RandomSupport} provides utility methods, constants, and
+ * abstract classes frequently useful in the implementation of pseudorandom number generators
+ * that satisfy the interface {@link RandomGenerator}.
*
* @since 14
*/
--- a/src/java.base/share/classes/module-info.java Thu Aug 29 11:33:26 2019 -0300
+++ b/src/java.base/share/classes/module-info.java Thu Nov 14 08:54:56 2019 -0400
@@ -378,16 +378,19 @@
provides java.util.random.RandomGenerator with
java.security.SecureRandom,
java.util.Random,
- java.util.random.L128X256MixRandom,
- java.util.random.L32X64MixRandom,
- java.util.random.L64X1024MixRandom,
- java.util.random.L64X1024Random,
+ java.util.random.L32X64StarStarRandom,
java.util.random.L64X128MixRandom,
- java.util.random.L64X128Random,
+ java.util.random.L64X128PlusPlusRandom,
+ java.util.random.L64X128StarStarRandom,
java.util.random.L64X256MixRandom,
- java.util.random.L64X256Random,
+ java.util.random.L64X1024MixRandom,
+ java.util.random.L128X128MixRandom,
+ java.util.random.L128X128PlusPlusRandom,
+ java.util.random.L128X128StarStarRandom,
+ java.util.random.L128X256MixRandom,
+ java.util.random.L128X1024MixRandom,
java.util.random.MRG32k3a,
- java.util.random.Xoroshiro128Plus,
+ java.util.random.Xoroshiro128PlusPlus,
java.util.random.Xoroshiro128StarStar,
java.util.random.Xoshiro256StarStar;