1 /*

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

     3  * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.

     4  *

     5  *

     6  *

     7  *

     8  *

     9  *

    10  *

    11  *

    12  *

    13  *

    14  *

    15  *

    16  *

    17  *

    18  *

    19  *

    20  *

    21  *

    22  *

    23  *

    24  */

    25 

    26 // package java.util;

    27 

    28 import java.math.BigInteger;

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

    30 

    31 /**

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

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

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

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

    36  * and therefore supports methods for producing pseudorandomly chosen

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

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

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

    40  *

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

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

    43  * (Most recently validated with

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

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

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

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

    48  * These tests validate only the methods for certain

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

    50  * least approximately, for others as well.

    51  *

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

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

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

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

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

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

    58  *

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

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

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

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

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

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

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

    66  * of parameter.

    67  *

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

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

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

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

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

    73  * 

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

    75  *

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

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

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

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

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

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

    82  * cycles of produced values will be different.

    83  *

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

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

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

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

    88  * methods are likewise exactly equidistributed.

    89  *

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   105  *

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

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

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

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

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

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

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

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

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

   115  * cycle.

   116  *

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

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

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

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

   121  * computation using random numbers might include a construction

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

   123  *

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

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

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

   127  *

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

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

   130  * in security-sensitive applications. Additionally,

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

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

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

   134  *

   135  * @author  Guy Steele

   136  * @since   1.9

   137  */

   138 public final class L64X1024MixRandom extends AbstractSplittableRng {

   139 

   140     /*

   141      * Implementation Overview.

   142      *

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

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

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

   146      *

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

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

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

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

   151      *

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

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

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

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

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

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

   158      * seed based on current time unless the

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

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

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

   162      *

   163      * File organization: First static fields, then instance

   164      * fields, then constructors, then instance methods.

   165      */

   166 

   167     /* ---------------- static fields ---------------- */

   168 

   169     /*

   170      * The length of the array x.

   171      */

   172 

   173     private static final int N = 16;

   174 

   175     /**

   176      * The seed generator for default constructors.

   177      */

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

   179 

   180     /*

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

   182      */

   183     private static final BigInteger thePeriod =

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

   185 

   186     /*

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

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

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

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

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

   192      */

   193 

   194     private static final long m = 2862933555777941757L;

   195     

   196     /* ---------------- instance fields ---------------- */

   197 

   198     /**

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

   200      * Must be odd.

   201      */

   202     private final long a;

   203 

   204     /**

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

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

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

   208      */

   209     private long s;

   210     private final long[] x;

   211     private int p = N - 1;

   212 

   213     /* ---------------- constructors ---------------- */

   214 

   215     /**

   216      * Basic constructor that initializes all fields from parameters.

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

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

   219      */

   220     public L64X1024MixRandom(long a, long s,

   221 			     long x0, long x1, long x2, long x3,

   222 			     long x4, long x5, long x6, long x7,

   223 			     long x8, long x9, long x10, long x11,

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

   225 	// Force a to be odd.

   226         this.a = a | 1;

   227         this.s = s;

   228 	this.x = new long[N];

   229 	this.x[0] = x0;

   230 	this.x[1] = x1;

   231         this.x[2] = x2;

   232         this.x[3] = x3;

   233         this.x[4] = x4;

   234         this.x[5] = x5;

   235         this.x[6] = x6;

   236         this.x[7] = x7;

   237         this.x[8] = x8;

   238         this.x[9] = x9;

   239         this.x[10] = x10;

   240         this.x[11] = x11;

   241         this.x[12] = x12;

   242         this.x[13] = x13;

   243         this.x[14] = x14;

   244         this.x[15] = x15;

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

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

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

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

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

   250 	    }

   251 	}

   252     }

   253 

   254     /**

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

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

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

   258      * program execution generate identical sequences of values.

   259      *

   260      * @param seed the initial seed

   261      */

   262     public L64X1024MixRandom(long seed) {

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

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

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

   266 	//

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

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

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

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

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

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

   273 	     1,

   274 	     RngSupport.mixStafford13(seed),

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   290     }

   291 

   292     /**

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

   294      * generate sequences of values that are statistically independent

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

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

   297      */

   298     public L64X1024MixRandom() {

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

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

   301     }

   302 

   303     /**

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

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

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

   307      *

   308      * @param seed the initial seed

   309      */

   310     public L64X1024MixRandom(byte[] seed) {

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

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

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

   314 	// Force a to be odd.

   315         this.a = a | 1;

   316         this.s = s;

   317 	this.x = new long[N];

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

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

   320 	}

   321     }

   322 

   323     /* ---------------- public methods ---------------- */

   324 

   325     /**

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

   327      * that shares no mutable state with this instance.

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

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

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

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

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

   333      * and the same expected statistical properties apply to the

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

   335      *

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

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

   338      *               initialize the state of the new ones.

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

   340      */

   341     public L64X1024MixRandom split(SplittableRng source) {

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

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

   344 				     source.nextLong(), source.nextLong(),

   345 				     source.nextLong(), source.nextLong(),

   346 				     source.nextLong(), source.nextLong(),

   347 				     source.nextLong(), source.nextLong(),

   348 				     source.nextLong(), source.nextLong(),

   349 				     source.nextLong(), source.nextLong(),

   350 				     source.nextLong(), source.nextLong(),

   351 				     source.nextLong(), source.nextLong());

   352     }

   353 

   354     /**

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

   356      *

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

   358      */

   359 

   360     public long nextLong() {

   361 	// First part of xoroshiro1024: fetch array data

   362 	final int q = p;

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

   364 	long s15 = x[q];

   365 

   366 	final long z = s + s0;

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

   368 

   369 	// Second part of xoroshiro1024: update array data

   370 	s15 ^= s0;

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

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

   373 	

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

   375     }

   376 

   377     public BigInteger period() { return thePeriod; }

   378 }