1 /*

     2  * Copyright (c) 2013, 2019, Oracle and/or its affiliates. All rights reserved.

     3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

     4  *

     5  * This code is free software; you can redistribute it and/or modify it

     6  * under the terms of the GNU General Public License version 2 only, as

     7  * published by the Free Software Foundation.  Oracle designates this

     8  * particular file as subject to the "Classpath" exception as provided

     9  * by Oracle in the LICENSE file that accompanied this code.

    10  *

    11  * This code is distributed in the hope that it will be useful, but WITHOUT

    12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

    13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

    14  * version 2 for more details (a copy is included in the LICENSE file that

    15  * accompanied this code).

    16  *

    17  * You should have received a copy of the GNU General Public License version

    18  * 2 along with this work; if not, write to the Free Software Foundation,

    19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

    20  *

    21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

    22  * or visit www.oracle.com if you need additional information or have any

    23  * questions.

    24  */

    25 package java.util;

    26 

    27 import java.math.BigInteger;

    28 import java.util.concurrent.atomic.AtomicLong;

    29 

    30 /**

    31  * A generator of uniform pseudorandom values applicable for use in

    32  * (among other contexts) isolated parallel computations that may

    33  * generate subtasks.  Class {@code L64X1024MixRandom} implements

    34  * interfaces {@link java.util.Rng} and {@link java.util.SplittableRng},

    35  * and therefore supports methods for producing pseudorandomly chosen

    36  * numbers of type {@code int}, {@code long}, {@code float}, and {@code double}

    37  * as well as creating new split-off {@code L64X1024MixRandom} objects,

    38  * with similar usages as for class {@link java.util.SplittableRandom}.

    39  *

    40  * <p>Series of generated values pass the TestU01 BigCrush and PractRand test suites

    41  * that measure independence and uniformity properties of random number generators.

    42  * (Most recently validated with

    43  * <a href="http://simul.iro.umontreal.ca/testu01/tu01.html">version 1.2.3 of TestU01</a>

    44  * and <a href="http://pracrand.sourceforge.net">version 0.90 of PractRand</a>.

    45  * Note that TestU01 BigCrush was used to test not only values produced by the {@code nextLong()}

    46  * method but also the result of bit-reversing each value produced by {@code nextLong()}.)

    47  * These tests validate only the methods for certain

    48  * types and ranges, but similar properties are expected to hold, at

    49  * least approximately, for others as well.

    50  *

    51  * <p>{@code L64X1024MixRandom} is a specific member of the LXM family of algorithms

    52  * for pseudorandom number generators.  Every LXM generator consists of two

    53  * subgenerators; one is an LCG (Linear Congruential Generator) and the other is

    54  * an Xorshift generator.  Each output of an LXM generator is the sum of one

    55  * output from each subgenerator, possibly processed by a final mixing function

    56  * (and {@code L64X1024MixRandom} does use a mixing function).

    57  *

    58  * <p>The LCG subgenerator for {@code L64X1024MixRandom} has an update step of the

    59  * form {@code s = m * s + a}, where {@code s}, {@code m}, and {@code a} are all

    60  * of type {@code long}; {@code s} is the mutable state, the multiplier {@code m}

    61  * is fixed (the same for all instances of {@code L64X1024MixRandom}}) and the addend

    62  * {@code a} is a parameter (a final field of the instance).  The parameter

    63  * {@code a} is required to be odd (this allows the LCG to have the maximal

    64  * period, namely 2<sup>64</sup>); therefore there are 2<sup>63</sup> distinct choices

    65  * of parameter.

    66  *

    67  * <p>The Xorshift subgenerator for {@code L64X1024MixRandom} is the {@code xoroshiro1024}

    68  * algorithm (parameters 25, 27, and 36), without any final scrambler such as "+" or "**".

    69  * Its state consists of an array {@code x} of sixteen {@code long} values,

    70  * which can take on any values provided that they are not all zero.

    71  * The period of this subgenerator is 2<sup>1024</sup>-1.

    72  * 

    73  * <p> The mixing function for {@code L64X256MixRandom} is the 64-bit MurmurHash3 finalizer.

    74  *

    75  * <p> Because the periods 2<sup>64</sup> and 2<sup>1024</sup>-1 of the two subgenerators

    76  * are relatively prime, the <em>period</em> of any single {@code L64X1024MixRandom} object 

    77  * (the length of the series of generated 64-bit values before it repeats) is the product

    78  * of the periods of the subgenerators, that is, 2<sup>64</sup>(2<sup>1024</sup>-1),

    79  * which is just slightly smaller than 2<sup>1088</sup>.  Moreover, if two distinct

    80  * {@code L64X1024MixRandom} objects have different {@code a} parameters, then their

    81  * cycles of produced values will be different.

    82  *

    83  * <p>The 64-bit values produced by the {@code nextLong()} method are exactly equidistributed.

    84  * For any specific instance of {@code L64X1024MixRandom}, over the course of its cycle each

    85  * of the 2<sup>64</sup> possible {@code long} values will be produced 2<sup>1024</sup>-1 times.

    86  * The values produced by the {@code nextInt()}, {@code nextFloat()}, and {@code nextDouble()}

    87  * methods are likewise exactly equidistributed.

    88  *

    89  * <p>In fact, the 64-bit values produced by the {@code nextLong()} method are 16-equidistributed.

    90  * To be precise: for any specific instance of {@code L64X1024MixRandom}, consider

    91  * the (overlapping) length-16 subsequences of the cycle of 64-bit values produced by

    92  * {@code nextLong()} (assuming no other methods are called that would affect the state).

    93  * There are 2<sup>64</sup>(2<sup>1024</sup>-1) such subsequences, and each subsequence,

    94  * which consists of 16 64-bit values, can have one of 2<sup>1024</sup> values. Of those

    95  * 2<sup>1024</sup> subsequence values, nearly all of them (2<sup>1024</sup>-2<sup>64</sup>)

    96  * occur 2<sup>64</sup> times over the course of the entire cycle, and the other

    97  * 2<sup>64</sup> subsequence values occur only 2<sup>64</sup>-1 times.  So the ratio

    98  * of the probability of getting one of the less common subsequence values and the

    99  * probability of getting one of the more common subsequence values is 1-2<sup>-64</sup>.

   100  * (Note that the set of 2<sup>64</sup> less-common subsequence values will differ from

   101  * one instance of {@code L64X1024MixRandom} to another, as a function of the additive

   102  * parameter of the LCG.)  The values produced by the {@code nextInt()}, {@code nextFloat()},

   103  * and {@code nextDouble()} methods are likewise 16-equidistributed.

   104  *

   105  * <p>Method {@link #split} constructs and returns a new {@code L64X1024MixRandom}

   106  * instance that shares no mutable state with the current instance. However, with

   107  * very high probability, the values collectively generated by the two objects

   108  * have the same statistical properties as if the same quantity of values were

   109  * generated by a single thread using a single {@code L64X1024MixRandom} object.

   110  * This is because, with high probability, distinct {@code L64X1024MixRandom} objects

   111  * have distinct {@code a} parameters and therefore use distinct members of the

   112  * algorithmic family; and even if their {@code a} parameters are the same, with

   113  * very high probability they will traverse different parts of their common state

   114  * cycle.

   115  *

   116  * <p>As with {@link java.util.SplittableRandom}, instances of

   117  * {@code L64X1024MixRandom} are <em>not</em> thread-safe.

   118  * They are designed to be split, not shared, across threads. For

   119  * example, a {@link java.util.concurrent.ForkJoinTask} fork/join-style

   120  * computation using random numbers might include a construction

   121  * of the form {@code new Subtask(someL64X1024MixRandom.split()).fork()}.

   122  *

   123  * <p>This class provides additional methods for generating random

   124  * streams, that employ the above techniques when used in

   125  * {@code stream.parallel()} mode.

   126  *

   127  * <p>Instances of {@code L64X1024MixRandom} are not cryptographically

   128  * secure.  Consider instead using {@link java.security.SecureRandom}

   129  * in security-sensitive applications. Additionally,

   130  * default-constructed instances do not use a cryptographically random

   131  * seed unless the {@linkplain System#getProperty system property}

   132  * {@code java.util.secureRandomSeed} is set to {@code true}.

   133  *

   134  * @author  Guy Steele

   135  * @since   1.9

   136  */

   137 public final class L64X1024MixRandom extends AbstractSplittableRng {

   138 

   139     /*

   140      * Implementation Overview.

   141      *

   142      * The split() operation uses the current generator to choose 18 new 64-bit

   143      * long values that are then used to initialize the parameter `a`, the

   144      * state variable `s`, and the array `x` for a newly constructed generator.

   145      *

   146      * With extremely high probability, no two generators so chosen

   147      * will have the same `a` parameter, and testing has indicated

   148      * that the values generated by two instances of {@code L64X1024MixRandom}

   149      * will be (approximately) independent if have different values for `a`.

   150      *

   151      * The default (no-argument) constructor, in essence, uses

   152      * "defaultGen" to generate 18 new 64-bit values for the same

   153      * purpose.  Multiple generators created in this way will certainly

   154      * differ in their `a` parameters.  The defaultGen state must be accessed

   155      * in a thread-safe manner, so we use an AtomicLong to represent

   156      * this state.  To bootstrap the defaultGen, we start off using a

   157      * seed based on current time unless the

   158      * java.util.secureRandomSeed property is set. This serves as a

   159      * slimmed-down (and insecure) variant of SecureRandom that also

   160      * avoids stalls that may occur when using /dev/random.

   161      *

   162      * File organization: First static fields, then instance

   163      * fields, then constructors, then instance methods.

   164      */

   165 

   166     /* ---------------- static fields ---------------- */

   167 

   168     /*

   169      * The length of the array x.

   170      */

   171 

   172     private static final int N = 16;

   173 

   174     /**

   175      * The seed generator for default constructors.

   176      */

   177     private static final AtomicLong defaultGen = new AtomicLong(RngSupport.initialSeed());

   178 

   179     /*

   180      * The period of this generator, which is (2**1024 - 1) * 2**64.

   181      */

   182     private static final BigInteger thePeriod =

   183 	BigInteger.ONE.shiftLeft(N*64).subtract(BigInteger.ONE).shiftLeft(64);

   184 

   185     /*

   186      * Multiplier used in the LCG portion of the algorithm, taken from

   187      * Pierre L'Ecuyer, Tables of linear congruential generators of

   188      * different sizes and good lattice structure, <em>Mathematics of

   189      * Computation</em> 68, 225 (January 1999), pages 249-260,

   190      * Table 4 (first multiplier for size 2<sup>64</sup>).

   191      */

   192 

   193     private static final long m = 2862933555777941757L;

   194     

   195     /* ---------------- instance fields ---------------- */

   196 

   197     /**

   198      * The parameter that is used as an additive constant for the LCG.

   199      * Must be odd.

   200      */

   201     private final long a;

   202 

   203     /**

   204      * The per-instance state: s for the LCG; the array x for the xorshift;

   205      * p is the rotating pointer into the array x.

   206      * At least one of the 16 elements of the array x must be nonzero.

   207      */

   208     private long s;

   209     private final long[] x;

   210     private int p = N - 1;

   211 

   212     /* ---------------- constructors ---------------- */

   213 

   214     /**

   215      * Basic constructor that initializes all fields from parameters.

   216      * It then adjusts the field values if necessary to ensure that

   217      * all constraints on the values of fields are met.

   218      *

   219      * @param a additive parameter for the LCG

   220      * @param s initial state for the LCG

   221      * @param x0 first word of the initial state for the xorshift generator

   222      * @param x1 second word of the initial state for the xorshift generator

   223      * @param x2 third word of the initial state for the xorshift generator

   224      * @param x3 fourth word of the initial state for the xorshift generator

   225      * @param x4 fifth word of the initial state for the xorshift generator

   226      * @param x5 sixth word of the initial state for the xorshift generator

   227      * @param x6 seventh word of the initial state for the xorshift generator

   228      * @param x7 eight word of the initial state for the xorshift generator

   229      * @param x8 ninth word of the initial state for the xorshift generator

   230      * @param x9 tenth word of the initial state for the xorshift generator

   231      * @param x10 eleventh word of the initial state for the xorshift generator

   232      * @param x11 twelfth word of the initial state for the xorshift generator

   233      * @param x12 thirteenth word of the initial state for the xorshift generator

   234      * @param x13 fourteenth word of the initial state for the xorshift generator

   235      * @param x14 fifteenth word of the initial state for the xorshift generator

   236      * @param x15 sixteenth word of the initial state for the xorshift generator

   237      */

   238     public L64X1024MixRandom(long a, long s,

   239 			     long x0, long x1, long x2, long x3,

   240 			     long x4, long x5, long x6, long x7,

   241 			     long x8, long x9, long x10, long x11,

   242 			     long x12, long x13, long x14, long x15) {

   243 	// Force a to be odd.

   244         this.a = a | 1;

   245         this.s = s;

   246 	this.x = new long[N];

   247 	this.x[0] = x0;

   248 	this.x[1] = x1;

   249         this.x[2] = x2;

   250         this.x[3] = x3;

   251         this.x[4] = x4;

   252         this.x[5] = x5;

   253         this.x[6] = x6;

   254         this.x[7] = x7;

   255         this.x[8] = x8;

   256         this.x[9] = x9;

   257         this.x[10] = x10;

   258         this.x[11] = x11;

   259         this.x[12] = x12;

   260         this.x[13] = x13;

   261         this.x[14] = x14;

   262         this.x[15] = x15;

   263 	// If x0, x1, ..., x15 are all zero (very unlikely), we must choose nonzero values.

   264         if ((x0 | x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 | x12 | x13 | x14 | x15) == 0) {

   265 	    // At least fifteen of the sixteen values generated here will be nonzero.

   266 	    for (int j = 0; j < N; j++) {

   267 		this.x[j] = RngSupport.mixStafford13(s += RngSupport.GOLDEN_RATIO_64);

   268 	    }

   269 	}

   270     }

   271 

   272     /**

   273      * Creates a new instance of {@code L64X1024MixRandom} using the

   274      * specified {@code long} value as the initial seed. Instances of

   275      * {@code L64X1024MixRandom} created with the same seed in the same

   276      * program execution generate identical sequences of values.

   277      *

   278      * @param seed the initial seed

   279      */

   280     public L64X1024MixRandom(long seed) {

   281 	// Using a value with irregularly spaced 1-bits to xor the seed

   282 	// argument tends to improve "pedestrian" seeds such as 0 or

   283 	// other small integers.  We may as well use SILVER_RATIO_64.

   284 	//

   285 	// The seed is hashed by mixMurmur64 to produce the `a` parameter.

   286 	// The seed is hashed by mixStafford13 to produce the initial `x[0]`,

   287 	// which will then be used to produce the first generated value.

   288 	// The other x values are filled in as if by a SplitMix PRNG with

   289 	// GOLDEN_RATIO_64 as the gamma value and Stafford13 as the mixer.

   290         this(RngSupport.mixMurmur64(seed ^= RngSupport.SILVER_RATIO_64),

   291 	     1,

   292 	     RngSupport.mixStafford13(seed),

   293 	     RngSupport.mixStafford13(seed += RngSupport.GOLDEN_RATIO_64),

   294 	     RngSupport.mixStafford13(seed += RngSupport.GOLDEN_RATIO_64),

   295 	     RngSupport.mixStafford13(seed += RngSupport.GOLDEN_RATIO_64),

   296 	     RngSupport.mixStafford13(seed += RngSupport.GOLDEN_RATIO_64),

   297 	     RngSupport.mixStafford13(seed += RngSupport.GOLDEN_RATIO_64),

   298 	     RngSupport.mixStafford13(seed += RngSupport.GOLDEN_RATIO_64),

   299 	     RngSupport.mixStafford13(seed += RngSupport.GOLDEN_RATIO_64),

   300 	     RngSupport.mixStafford13(seed += RngSupport.GOLDEN_RATIO_64),

   301 	     RngSupport.mixStafford13(seed += RngSupport.GOLDEN_RATIO_64),

   302 	     RngSupport.mixStafford13(seed += RngSupport.GOLDEN_RATIO_64),

   303 	     RngSupport.mixStafford13(seed += RngSupport.GOLDEN_RATIO_64),

   304 	     RngSupport.mixStafford13(seed += RngSupport.GOLDEN_RATIO_64),

   305 	     RngSupport.mixStafford13(seed += RngSupport.GOLDEN_RATIO_64),

   306 	     RngSupport.mixStafford13(seed += RngSupport.GOLDEN_RATIO_64),

   307 	     RngSupport.mixStafford13(seed + RngSupport.GOLDEN_RATIO_64));

   308     }

   309 

   310     /**

   311      * Creates a new instance of {@code L64X1024MixRandom} that is likely to

   312      * generate sequences of values that are statistically independent

   313      * of those of any other instances in the current program execution,

   314      * but may, and typically does, vary across program invocations.

   315      */

   316     public L64X1024MixRandom() {

   317 	// Using GOLDEN_RATIO_64 here gives us a good Weyl sequence of values.

   318         this(defaultGen.getAndAdd(RngSupport.GOLDEN_RATIO_64));

   319     }

   320 

   321     /**

   322      * Creates a new instance of {@code L64X1024MixRandom} using the specified array of

   323      * initial seed bytes. Instances of {@code L64X1024MixRandom} created with the same

   324      * seed array in the same program execution generate identical sequences of values.

   325      *

   326      * @param seed the initial seed

   327      */

   328     public L64X1024MixRandom(byte[] seed) {

   329 	// Convert the seed to 18 long values, of which the last 16 are not all zero.

   330 	long[] data = RngSupport.convertSeedBytesToLongs(seed, 18, 16);

   331 	long a = data[0], s = data[1];

   332 	// Force a to be odd.

   333         this.a = a | 1;

   334         this.s = s;

   335 	this.x = new long[N];

   336 	for (int j = 0; j < N; j++) {

   337 	    this.x[j] = data[2+j];

   338 	}

   339     }

   340 

   341     /* ---------------- public methods ---------------- */

   342 

   343     /**

   344      * Constructs and returns a new instance of {@code L64X1024MixRandom}

   345      * that shares no mutable state with this instance.

   346      * However, with very high probability, the set of values collectively

   347      * generated by the two objects has the same statistical properties as if

   348      * same the quantity of values were generated by a single thread using

   349      * a single {@code L64X1024MixRandom} object.  Either or both of the two

   350      * objects may be further split using the {@code split} method,

   351      * and the same expected statistical properties apply to the

   352      * entire set of generators constructed by such recursive splitting.

   353      *

   354      * @param source a {@code SplittableRng} instance to be used instead

   355      *               of this one as a source of pseudorandom bits used to

   356      *               initialize the state of the new ones.

   357      * @return a new instance of {@code L64X1024MixRandom}

   358      */

   359     public L64X1024MixRandom split(SplittableRng source) {

   360 	// Literally pick a new instance "at random".

   361         return new L64X1024MixRandom(source.nextLong(), source.nextLong(), 

   362 				     source.nextLong(), source.nextLong(),

   363 				     source.nextLong(), source.nextLong(),

   364 				     source.nextLong(), source.nextLong(),

   365 				     source.nextLong(), source.nextLong(),

   366 				     source.nextLong(), source.nextLong(),

   367 				     source.nextLong(), source.nextLong(),

   368 				     source.nextLong(), source.nextLong(),

   369 				     source.nextLong(), source.nextLong());

   370     }

   371 

   372     /**

   373      * Returns a pseudorandom {@code long} value.

   374      *

   375      * @return a pseudorandom {@code long} value

   376      */

   377 

   378     public long nextLong() {

   379 	// First part of xoroshiro1024: fetch array data

   380 	final int q = p;

   381 	final long s0 = x[p = (p + 1) & (N - 1)];

   382 	long s15 = x[q];

   383 

   384 	final long z = s + s0;

   385 	s = m * s + a;  // LCG

   386 

   387 	// Second part of xoroshiro1024: update array data

   388 	s15 ^= s0;

   389 	x[q] = Long.rotateLeft(s0, 25) ^ s15 ^ (s15 << 27);

   390 	x[p] = Long.rotateLeft(s15, 36);

   391 	

   392 	return RngSupport.mixLea64(z);  // mixing function

   393     }

   394 

   395     public BigInteger period() { return thePeriod; }

   396 }