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 L64X1024Random} 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 L64X1024Random} 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 L64X1024Random} 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  * (but {@code L64X1024Random} does not use a mixing function).

    58  *

    59  * <p>The LCG subgenerator for {@code L64X1024Random} 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 L64X1024Random}}) 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 L64X1024Random} 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> Because the periods 2<sup>64</sup> and 2<sup>1024</sup>-1 of the two subgenerators

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

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

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

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

    79  * {@code L64X1024Random} objects have different {@code a} parameters, then their

    80  * cycles of produced values will be different.

    81  *

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

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

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

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

    86  * methods are likewise exactly equidistributed.

    87  *

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   103  *

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

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

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

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

   108  * generated by a single thread using a single {@code L64X1024Random} object.

   109  * This is because, with high probability, distinct {@code L64X1024Random} objects

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

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

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

   113  * cycle.

   114  *

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

   116  * {@code L64X1024Random} are <em>not</em> thread-safe.

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

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

   119  * computation using random numbers might include a construction

   120  * of the form {@code new Subtask(someL64X1024Random.split()).fork()}.

   121  *

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

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

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

   125  *

   126  * <p>Instances of {@code L64X1024Random} are not cryptographically

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

   128  * in security-sensitive applications. Additionally,

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

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

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

   132  *

   133  * @author  Guy Steele

   134  * @since   1.9

   135  */

   136 public final class L64X1024Random extends AbstractSplittableRng {

   137 

   138     /*

   139      * Implementation Overview.

   140      *

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

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

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

   144      *

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

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

   147      * that the values generated by two instances of {@code L64X1024Random}

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

   149      *

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

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

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

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

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

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

   156      * seed based on current time unless the

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

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

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

   160      *

   161      * File organization: First static fields, then instance

   162      * fields, then constructors, then instance methods.

   163      */

   164 

   165     /* ---------------- static fields ---------------- */

   166 

   167     /*

   168      * The length of the array x.

   169      */

   170 

   171     private static final int N = 16;

   172 

   173     /**

   174      * The seed generator for default constructors.

   175      */

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

   177 

   178     /*

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

   180      */

   181     private static final BigInteger thePeriod =

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

   183 

   184     /*

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

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

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

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

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

   190      */

   191 

   192     private static final long m = 2862933555777941757L;

   193     

   194     /* ---------------- instance fields ---------------- */

   195 

   196     /**

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

   198      * Must be odd.

   199      */

   200     private final long a;

   201 

   202     /**

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

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

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

   206      */

   207     private long s;

   208     private final long[] x;

   209     private int p = N - 1;

   210 

   211     /* ---------------- constructors ---------------- */

   212 

   213     /**

   214      * Basic constructor that initializes all fields from parameters.

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

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

   217      */

   218     public L64X1024Random(long a, long s,

   219 			  long x0, long x1, long x2, long x3,

   220 			  long x4, long x5, long x6, long x7,

   221 			  long x8, long x9, long x10, long x11,

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

   223 	// Force a to be odd.

   224         this.a = a | 1;

   225         this.s = s;

   226 	this.x = new long[N];

   227 	this.x[0] = x0;

   228 	this.x[1] = x1;

   229         this.x[2] = x2;

   230         this.x[3] = x3;

   231         this.x[4] = x4;

   232         this.x[5] = x5;

   233         this.x[6] = x6;

   234         this.x[7] = x7;

   235         this.x[8] = x8;

   236         this.x[9] = x9;

   237         this.x[10] = x10;

   238         this.x[11] = x11;

   239         this.x[12] = x12;

   240         this.x[13] = x13;

   241         this.x[14] = x14;

   242         this.x[15] = x15;

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

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

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

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

   247 	    }

   248 	}

   249     }

   250 

   251     /**

   252      * Creates a new instance of {@code L64X1024Random} using the

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

   254      * {@code L64X1024Random} created with the same seed in the same

   255      * program execution generate identical sequences of values.

   256      *

   257      * @param seed the initial seed

   258      */

   259     public L64X1024Random(long seed) {

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

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

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

   263 	//

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

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

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

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

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

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

   270 	     1,

   271 	     RngSupport.mixStafford13(seed),

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

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

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

   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     }

   288 

   289     /**

   290      * Creates a new instance of {@code L64X1024Random} that is likely to

   291      * generate sequences of values that are statistically independent

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

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

   294      */

   295     public L64X1024Random() {

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

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

   298     }

   299 

   300     /**

   301      * Creates a new instance of {@code L64X1024Random} using the specified array of

   302      * initial seed bytes. Instances of {@code L64X1024Random} created with the same

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

   304      *

   305      * @param seed the initial seed

   306      */

   307     public L64X1024Random(byte[] seed) {

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

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

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

   311 	// Force a to be odd.

   312         this.a = a | 1;

   313         this.s = s;

   314 	this.x = new long[N];

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

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

   317 	}

   318     }

   319 

   320     /* ---------------- public methods ---------------- */

   321 

   322     /**

   323      * Constructs and returns a new instance of {@code L64X1024Random}

   324      * that shares no mutable state with this instance.

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

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

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

   328      * a single {@code L64X1024Random} object.  Either or both of the two

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

   330      * and the same expected statistical properties apply to the

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

   332      *

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

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

   335      *               initialize the state of the new ones.

   336      * @return a new instance of {@code L64X1024Random}

   337      */

   338     public L64X1024Random split(SplittableRng source) {

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

   340         return new L64X1024Random(source.nextLong(), source.nextLong(), 

   341 				  source.nextLong(), source.nextLong(),

   342 				  source.nextLong(), source.nextLong(),

   343 				  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     }

   350 

   351     /**

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

   353      *

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

   355      */

   356 

   357     public long nextLong() {

   358 	// First part of xoroshiro1024: fetch array data

   359 	final int q = p;

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

   361 	long s15 = x[q];

   362 

   363 	final long z = s + s0;

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

   365 

   366 	// Second part of xoroshiro1024: update array data

   367 	s15 ^= s0;

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

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

   370 	

   371 	return z;

   372     }

   373 

   374     public BigInteger period() { return thePeriod; }

   375 }