1 /* 2 * Copyright (c) 2021, 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 26 // Android-changed: removed service loader API sentence. 27 28 /** 29 * This package contains classes and interfaces that support a generic API 30 * for random number generation. 31 * 32 * <p>These classes and interfaces support the definition and use of "random 33 * generators", a term covering what have traditionally been called "random 34 * number generators" as well as generators of other sorts of randomly chosen 35 * values (eg. booleans). These classes and interfaces cover not only 36 * deterministic (pseudorandom) algorithms but also generators of values that 37 * use some "truly random" physical source (stochastic algorithms perhaps making 38 * use of thermal noise, for example, or quantum-mechanical effects). 39 * 40 * <p> The principal interface is {@link RandomGenerator}, which provides 41 * methods for requesting individual values of type {@code int}, {@code long}, 42 * {@code float}, {@code double}, or {@code boolean} chosen pseudorandomly 43 * from a uniform distribution; methods for requesting values of type 44 * {@code double} chosen pseudorandomly from a normal distribution or from an 45 * exponential distribution; and methods for creating streams of values of type 46 * {@code int}, {@code long}, or {@code double} chosen pseudorandomly from a 47 * uniform distribution (such streams are spliterator-based, allowing for 48 * parallel processing of their elements). There are also static factory methods 49 * for creating an instance of a specific random number generator algorithm 50 * given its name. 51 * 52 * <p> The principal supporting class is {@link RandomGeneratorFactory}. This 53 * can be used to generate multiple random number generators for a specific 54 * algorithm. {@link RandomGeneratorFactory} also provides methods for 55 * selecting random number generator algorithms. 56 * 57 * <p> An important subsidiary interface is 58 * {@link RandomGenerator.StreamableGenerator}, which provides methods for 59 * creating spliterator-based streams of {@link RandomGenerator} objects, 60 * allowing for parallel processing of these objects using multiple threads. 61 * Unlike {@link java.util.Random}, most implementations of 62 * {@link RandomGenerator} are <i>not</i> thread-safe. The intent is that 63 * instances should not be shared among threads; rather, each thread should have 64 * its own random generator(s) to use. The various pseudorandom algorithms 65 * provided by this package are designed so that multiple instances will (with 66 * very high probability) behave as if statistically independent. 67 * 68 * <p> For many purposes, these are the only two interfaces that a consumer of 69 * pseudorandom values will need. There are also some more specialized 70 * interfaces that describe more specialized categories of random number 71 * generators {@link RandomGenerator.SplittableGenerator SplittableGenerator}, 72 * {@link RandomGenerator.JumpableGenerator JumpableGenerator}, 73 * {@link RandomGenerator.LeapableGenerator LeapableGenerator}, and 74 * {@link RandomGenerator.ArbitrarilyJumpableGenerator ArbitrarilyJumpableGenerator} 75 * that have specific strategies for creating statistically independent instances. 76 * 77 * <h2>Using the Random Number Generator Interfaces</h2> 78 * 79 * To get started, an application should first create one instance of a 80 * generator class. Assume that the contents of the package 81 * {@link java.util.random} has been imported: 82 * 83 * <blockquote>{@code import java.util.random.*;}</blockquote> 84 * 85 * Then one can choose a specific implementation by giving the name of a generator 86 * algorithm to the static method {@link RandomGenerator#of}, in which case the 87 * no-arguments constructor for that implementation is used: 88 * 89 * <blockquote>{@code RandomGenerator g = RandomGenerator.of("L64X128MixRandom");}</blockquote> 90 * 91 * For a single-threaded application, this is all that is needed. One can then 92 * invoke methods of {@code g} such as 93 * {@link RandomGenerator#nextLong nextLong()}, 94 * {@link RandomGenerator#nextInt nextInt()}, 95 * {@link RandomGenerator#nextFloat nextFloat()}, 96 * {@link RandomGenerator#nextDouble nextDouble()} and 97 * {@link RandomGenerator#nextBoolean nextBoolean()} to generate individual 98 * randomly chosen values. One can also use the methods 99 * {@link RandomGenerator#ints ints()}, {@link RandomGenerator#longs longs()} 100 * and {@link RandomGenerator#doubles doubles()} to create streams of randomly 101 * chosen values. The methods 102 * {@link RandomGenerator#nextGaussian nextGaussian()} and 103 * {@link RandomGenerator#nextExponential nextExponential()} draw floating-point 104 * values from nonuniform distributions. 105 * 106 * <p> For a multi-threaded application, one can repeat the preceding steps 107 * to create additional {@linkplain RandomGenerator RandomGenerators}, but 108 * often it is preferable to use methods of the one single initially 109 * created generator to create others like it. (One reason is that some 110 * generator algorithms, if asked to create a new set of generators all at 111 * once, can make a special effort to ensure that the new generators are 112 * statistically independent.) If the initial generator implements the 113 * interface {@link RandomGenerator.StreamableGenerator}, then the method 114 * {@link RandomGenerator.StreamableGenerator#rngs rngs()} can be used to 115 * create a stream of generators. If this is a parallel stream, then it is 116 * easy to get parallel execution by using the 117 * {@link java.util.stream.Stream#map map()} method on the stream. 118 * <p> For a multi-threaded application that forks new threads dynamically, 119 * another approach is to use an initial generator that implements the interface 120 * {@link RandomGenerator.SplittableGenerator}, which is then considered to 121 * "belong" to the initial thread for its exclusive use; then whenever any 122 * thread needs to fork a new thread, it first uses the 123 * {@link RandomGenerator.SplittableGenerator#split split()} method of its own 124 * generator to create a new generator, which is then passed to the newly 125 * created thread for exclusive use by that new thread. 126 * 127 * 128 * <h2>Choosing a Random Number Generator Algorithm</h2> 129 * 130 * <p> There are three groups of random number generator algorithm provided 131 * in Java: the Legacy group, the LXM group, and the Xoroshiro/Xoshiro group. 132 * 133 * <p> The legacy group includes random number generators that existed 134 * before JDK 17: Random, ThreadLocalRandom, SplittableRandom, and 135 * SecureRandom. Random (LCG) is the weakest of the available algorithms, and it 136 * is recommended that users migrate to newer algorithms. If an application 137 * requires a random number generator algorithm that is cryptographically 138 * secure, then it should continue to use an instance of the class {@link 139 * java.security.SecureRandom}. 140 * 141 * <p> The algorithms in the LXM group are similar to each other. The parameters 142 * of each algorithm can be found in the algorithm name. The number after "L" indicates the 143 * number of state bits for the LCG subgenerator, and the number after "X" indicates the 144 * number of state bits for the XBG subgenerator. "Mix" indicates that 145 * the algorithm uses an 8-operation bit-mixing function; "StarStar" indicates use 146 * of a 3-operation bit-scrambler. 147 * 148 * <p> The algorithms in the Xoroshiro/Xoshiro group are more traditional algorithms 149 * (see David Blackman and Sebastiano Vigna, "Scrambled Linear Pseudorandom 150 * Number Generators," ACM Transactions on Mathematical Software, 2021); 151 * the number in the name indicates the number of state bits. 152 * 153 * <p> For applications (such as physical simulation, machine learning, and 154 * games) that do not require a cryptographically secure algorithm, this package 155 * provides multiple implementations of interface {@link RandomGenerator} that 156 * provide trade-offs among speed, space, period, accidental correlation, and 157 * equidistribution properties. 158 * 159 * <p> For applications with no special requirements, 160 * {@code L64X128MixRandom} has a good balance among speed, space, 161 * and period, and is suitable for both single-threaded and multi-threaded 162 * applications when used properly (a separate instance for each thread). 163 * 164 * <p> If the application uses only a single thread, then 165 * {@code Xoroshiro128PlusPlus} is even smaller and faster, and 166 * certainly has a sufficiently long period. 167 * 168 * <p> For an application running in a 32-bit hardware environment and using 169 * only one thread or a small number of threads, {@code L32X64MixRandom} may be a good 170 * choice. 171 * 172 * <p> For an application that uses many threads that are allocated in one batch 173 * at the start of the computation, either a "jumpable" generator such as 174 * {@code Xoroshiro128PlusPlus} or 175 * {@code Xoshiro256PlusPlus} may be used, or a "splittable" 176 * generator such as {@code L64X128MixRandom} or 177 * {@code L64X256MixRandom} may be used. 178 * 179 * <p> For an application that creates many threads dynamically, perhaps through 180 * the use of spliterators, a "splittable" generator such as 181 * {@code L64X128MixRandom} or {@code L64X256MixRandom} is 182 * recommended. If the number of generators created dynamically may 183 * be very large (millions or more), then using generators such as 184 * {@code L128X128MixRandom} or {@code L128X256MixRandom}, 185 * which use a 128-bit parameter rather than a 64-bit parameter for their LCG 186 * subgenerator, will make it much less likely that two instances use the same 187 * state cycle. 188 * 189 * <p> For an application that uses tuples of consecutively generated values, it 190 * may be desirable to use a generator that is <i>k</i>-equidistributed such 191 * that <i>k</i> is at least as large as the length of the tuples being 192 * generated. The generator {@code L64X256MixRandom} is provably 193 * 4-equidistributed, and {@code L64X1024MixRandom} is provably 194 * 16-equidistributed. 195 * 196 * <p> For applications that generate large permutations, it may be best to use 197 * a generator whose period is much larger than the total number of possible 198 * permutations; otherwise it will be impossible to generate some of the 199 * intended permutations. For example, if the goal is to shuffle a deck of 52 200 * cards, the number of possible permutations is 52! (52 factorial), which is 201 * larger than 2<sup>225</sup> (but smaller than 2<sup>226</sup>), so it may be 202 * best to use a generator whose period at least 2<sup>256</sup>, such as 203 * {@code L64X256MixRandom} or {@code L64X1024MixRandom} 204 * or {@code L128X256MixRandom} or 205 * {@code L128X1024MixRandom}. (It is of course also necessary to 206 * provide sufficiently many seed bits when the generator is initialized, or 207 * else it will still be impossible to generate some of the intended 208 * permutations.) 209 * 210 * 211 * <h2><a id="algorithms">Random Number Generator Algorithms Available</a></h2> 212 * 213 * These algorithms [in the table below] must be found with the current version 214 * of Java SE. A particular JDK implementation may recognize additional 215 * algorithms; check the JDK's documentation for details. The set of algorithms 216 * required by Java SE may be updated by changes to the Java SE specification. 217 * Over time, new algorithms may be added and old algorithms may be removed. 218 * <p>In addition, as another life-cycle phase, an algorithm may be {@linkplain 219 * RandomGeneratorFactory#isDeprecated() deprecated}. A deprecated algorithm is 220 * not recommended for use. If a required algorithm is deprecated, it may be 221 * removed in a future release. Due to advances in random number generator 222 * algorithm development and analysis, an algorithm may be deprecated during the 223 * lifetime of a particular Java SE release. Changing the deprecation status of 224 * an algorithm is <em>not</em> a specification change. 225 * 226 * <table style="padding:0px 20px 0px 0px"> 227 * <caption>Available Algorithms</caption> 228 * <thead> 229 * <tr> 230 * <th style="text-align:left">Algorithm</th> 231 * <th style="text-align:left">Group</th> 232 * <th style="text-align:left">Period</th> 233 * <th style="text-align:right">StateBits</th> 234 * <th style="text-align:right">Equidistribution</th> 235 * </tr> 236 * </thead> 237 * <tbody> 238 * <tr> 239 * <td style="text-align:left">L128X1024MixRandom</td> 240 * <td style="text-align:left">LXM</td> 241 * <td style="text-align:left">BigInteger.ONE.shiftLeft(1024).subtract(BigInteger.ONE).shiftLeft(128)</td> 242 * <td style="text-align:right">1152</td> 243 * <td style="text-align:right">1</td> 244 * </tr> 245 * <tr> 246 * <td style="text-align:left">L128X128MixRandom</td> 247 * <td style="text-align:left">LXM</td> 248 * <td style="text-align:left">BigInteger.ONE.shiftLeft(128).subtract(BigInteger.ONE).shiftLeft(128)</td> 249 * <td style="text-align:right">256</td> 250 * <td style="text-align:right">1</td> 251 * </tr> 252 * <tr> 253 * <td style="text-align:left">L128X256MixRandom</td> 254 * <td style="text-align:left">LXM</td> 255 * <td style="text-align:left">BigInteger.ONE.shiftLeft(256).subtract(BigInteger.ONE).shiftLeft(128)</td> 256 * <td style="text-align:right">384</td> 257 * <td style="text-align:right">1</td> 258 * </tr> 259 * <tr> 260 * <td style="text-align:left">L32X64MixRandom</td> 261 * <td style="text-align:left">LXM</td> 262 * <td style="text-align:left">BigInteger.ONE.shiftLeft(64).subtract(BigInteger.ONE).shiftLeft(32)</td> 263 * <td style="text-align:right">96</td> 264 * <td style="text-align:right">1</td> 265 * </tr> 266 * <tr> 267 * <td style="text-align:left">L64X1024MixRandom</td> 268 * <td style="text-align:left">LXM</td> 269 * <td style="text-align:left">BigInteger.ONE.shiftLeft(1024).subtract(BigInteger.ONE).shiftLeft(64)</td> 270 * <td style="text-align:right">1088</td> 271 * <td style="text-align:right">16</td> 272 * </tr> 273 * <tr> 274 * <td style="text-align:left">L64X128MixRandom</td> 275 * <td style="text-align:left">LXM</td> 276 * <td style="text-align:left">BigInteger.ONE.shiftLeft(128).subtract(BigInteger.ONE).shiftLeft(64)</td> 277 * <td style="text-align:right">192</td> 278 * <td style="text-align:right">2</td> 279 * </tr> 280 * <tr> 281 * <td style="text-align:left">L64X128StarStarRandom</td> 282 * <td style="text-align:left">LXM</td> 283 * <td style="text-align:left">BigInteger.ONE.shiftLeft(128).subtract(BigInteger.ONE).shiftLeft(64)</td> 284 * <td style="text-align:right">192</td> 285 * <td style="text-align:right">2</td> 286 * </tr> 287 * <tr> 288 * <td style="text-align:left">L64X256MixRandom</td> 289 * <td style="text-align:left">LXM</td> 290 * <td style="text-align:left">BigInteger.ONE.shiftLeft(256).subtract(BigInteger.ONE).shiftLeft(64)</td> 291 * <td style="text-align:right">320</td> 292 * <td style="text-align:right">4</td> 293 * </tr> 294 * <tr> 295 * <td style="text-align:left">Random</td> 296 * <td style="text-align:left">Legacy</td> 297 * <td style="text-align:left">BigInteger.ONE.shiftLeft(48)</td> 298 * <td style="text-align:right">48</td> 299 * <td style="text-align:right">0</td> 300 * </tr> 301 * <tr> 302 * <td style="text-align:left">SplittableRandom</td> 303 * <td style="text-align:left">Legacy</td> 304 * <td style="text-align:left">BigInteger.ONE.shiftLeft(64)</td> 305 * <td style="text-align:right">64</td> 306 * <td style="text-align:right">1</td> 307 * </tr> 308 * <tr> 309 * <td style="text-align:left">ThreadLocalRandom <sup>*</sup></td> 310 * <td style="text-align:left">Legacy</td> 311 * <td style="text-align:left">BigInteger.ONE.shiftLeft(64)</td> 312 * <td style="text-align:right">64</td> 313 * <td style="text-align:right">1</td> 314 * </tr> 315 * <tr> 316 * <td style="text-align:left">Xoroshiro128PlusPlus</td> 317 * <td style="text-align:left">Xoroshiro</td> 318 * <td style="text-align:left">BigInteger.ONE.shiftLeft(128).subtract(BigInteger.ONE)</td> 319 * <td style="text-align:right">128</td> 320 * <td style="text-align:right">1</td> 321 * </tr> 322 * <tr> 323 * <td style="text-align:left">Xoshiro256PlusPlus</td> 324 * <td style="text-align:left">Xoshiro</td> 325 * <td style="text-align:left">BigInteger.ONE.shiftLeft(256).subtract(BigInteger.ONE)</td> 326 * <td style="text-align:right">256</td> 327 * <td style="text-align:right">3</td> 328 * </tr> 329 * </tbody> 330 * </table> 331 * 332 * <p><sup>*</sup> ThreadLocalRandom can only be accessed via 333 * {@link java.util.concurrent.ThreadLocalRandom#current()}. 334 * 335 * <h2>Categories of Random Number Generator Algorithms</h2> 336 * 337 * Historically, most pseudorandom generator algorithms have been based on some 338 * sort of finite-state machine with a single, large cycle of states; when it is 339 * necessary to have multiple threads use the same algorithm simultaneously, the 340 * usual technique is to arrange for each thread to traverse a different region 341 * of the state cycle. These regions may be doled out to threads by starting 342 * with a single initial state and then using a "jump function" that travels a 343 * long distance around the cycle (perhaps 2<sup>64</sup> steps or more); the 344 * jump function is applied repeatedly and sequentially, to identify widely 345 * spaced states that are then doled out, one to each thread, to serve as the 346 * initial state for the generator to be used by that thread. This strategy is 347 * supported by the interface {@link RandomGenerator.JumpableGenerator}. 348 * Sometimes it is desirable to support two levels of jumping (by long distances 349 * and by <i>really</i> long distances); this strategy is supported by the 350 * interface {@link RandomGenerator.LeapableGenerator}. There is also an interface 351 * {@link RandomGenerator.ArbitrarilyJumpableGenerator} for algorithms that allow 352 * jumping along the state cycle by any user-specified distance. In this package, 353 * implementations of these interfaces include 354 * "Xoroshiro128PlusPlus", and 355 * "Xoshiro256PlusPlus". 356 * 357 * <p> A more recent category of "splittable" pseudorandom generator algorithms 358 * uses a large family of state cycles and makes some attempt to ensure that 359 * distinct instances use different state cycles; but even if two instances 360 * "accidentally" use the same state cycle, they are highly likely to traverse 361 * different regions parts of that shared state cycle. This strategy is 362 * supported by the interface {@link RandomGenerator.SplittableGenerator}. 363 * In this package, implementations of this interface include 364 * "L32X64MixRandom", 365 * "L64X128StarStarRandom", 366 * "L64X128MixRandom", 367 * "L64X256MixRandom", 368 * "L64X1024MixRandom", 369 * "L128X128MixRandom", 370 * "L128X256MixRandom", and 371 * "L128X1024MixRandom"; note that the class 372 * {@link java.util.SplittableRandom} also implements this interface. 373 * 374 * 375 * <h2>The LXM Family of Random Number Generator Algorithms</h2> 376 * 377 * The structure of the central nextLong (or nextInt) method of an LXM 378 * algorithm follows a suggestion in December 2017 by Sebastiano Vigna 379 * that using one Linear Congruential Generator (LCG) as a first subgenerator 380 * and one Xor-Based Generator (XBG) as a second subgenerator (rather 381 * than using two LCG subgenerators) would provide a longer period, superior 382 * equidistribution, scalability, and better quality. Each of the 383 * specific implementations here combines one of the best currently known 384 * XBG algorithms (xoroshiro128 or xoshiro256, described by Blackman and 385 * Vigna in "Scrambled Linear Pseudorandom Number Generators", ACM Transactions 386 * on Mathematical Software, 2021) with an LCG that uses one of the best 387 * currently known multipliers (found by a search for better multipliers 388 * in 2019 by Steele and Vigna), and then applies either a mixing function 389 * identified by Doug Lea or a simple scrambler proposed by Blackman and Vigna. 390 * Testing has confirmed that the LXM algorithm is far superior in quality to 391 * the SplitMix algorithm (2014) used by {@code SplittableRandom}. 392 * 393 * Each class with a name of the form 394 * {@code L}<i>p</i>{@code X}<i>q</i>{@code SomethingRandom} 395 * uses some specific member of the LXM family of random number 396 * algorithms; "LXM" is short for "LCG, XBG, Mixer". Every LXM 397 * generator has two subgenerators; one is an LCG (Linear Congruential 398 * Generator) and the other is an XBG (Xor-Based Generator). Each output of an LXM 399 * generator is the result of combining state from the LCG with state from the 400 * XBG using a Mixing function (and then the state of the LCG 401 * and the state of the XBG are advanced). 402 * 403 * <p> The LCG subgenerator has an update step of the form {@code s = m*s + a}, 404 * where {@code s}, {@code m}, and {@code a} are all binary integers of the same 405 * size, each having <i>p</i> bits; {@code s} is the mutable state, the 406 * multiplier {@code m} is fixed (the same for all instances of a class) and the 407 * addend {@code a} is a parameter (a final field of the instance). The 408 * parameter {@code a} is required to be odd (this allows the LCG to have the 409 * maximal period, namely 2<sup><i>p</i></sup>); therefore there are 410 * 2<sup><i>p</i>−1</sup> distinct choices of parameter. (When the size of 411 * {@code s} is 128 bits, then we use the name "{@code sh}" below to refer to 412 * the high half of {@code s}, that is, the high-order 64 bits of {@code s}.) 413 * 414 * <p> The XBG subgenerator can in principle be any one of a wide variety 415 * of XBG algorithms; in this package it is always either 416 * {@code xoroshiro128}, {@code xoshiro256}, or {@code xoroshiro1024}, in each 417 * case without any final scrambler (such as "+" or "**") because LXM uses 418 * a separate Mixer later in the process. The XBG state consists of 419 * some fixed number of {@code int} or {@code long} fields, generally named 420 * {@code x0}, {@code x1}, and so on, which can take on any values provided that 421 * they are not all zero. The collective total size of these fields is <i>q</i> 422 * bits; therefore the period of this subgenerator is 423 * 2<sup><i>q</i></sup>−1. 424 * 425 * <p> Because the periods 2<sup><i>p</i></sup> and 2<sup><i>q</i></sup>−1 426 * of the two subgenerators are relatively prime, the <em>period</em> of any 427 * single instance of an LXM algorithm (the length of the series of generated 428 * values before it repeats) is the product of the periods of the subgenerators, 429 * that is, 2<sup><i>p</i></sup>(2<sup><i>q</i></sup>−1), which is just 430 * slightly smaller than 2<sup>(<i>p</i>+<i>q</i>)</sup>. Moreover, if two 431 * distinct instances of the same LXM algorithm have different {@code a} 432 * parameters, then their cycles of produced values will be different. 433 * 434 * <p> Generally speaking, among the "{@code L}<i>p</i>{@code X}<i>q</i>" 435 * generators, the memory required for an instance is 2<i>p</i>+<i>q</i> bits. 436 * (If <i>q</i> is 1024 or larger, the XBG state is represented as an 437 * array, so additional bits are needed for the array object header, and another 438 * 32 bits are used for an array index.) 439 * 440 * <p> Larger values of <i>p</i> imply a lower probability that two distinct 441 * instances will traverse the same state cycle, and larger values of <i>q</i> 442 * imply that the generator is equidistributed in a larger number of dimensions 443 * (this is provably true when <i>p</i> is 64, and conjectured to be 444 * approximately true when <i>p</i> is 128). A class with "{@code Mix}" in its 445 * name uses a fairly strong mixing function with excellent avalanche 446 * characteristics; a class with "{@code StarStar}" in its name uses a weaker 447 * but faster mixing function. 448 * 449 * <p> The specific LXM algorithms used in this package are all chosen so that 450 * the 64-bit values produced by the {@link RandomGenerator#nextLong nextLong()} 451 * method are exactly equidistributed (for example, for any specific instance of 452 * "L64X128MixRandom", over the course of its cycle each of the 453 * 2<sup>64</sup> possible {@code long} values will be produced 454 * 2<sup>128</sup>−1 times). The values produced by the 455 * {@link RandomGenerator#nextInt nextInt()}, 456 * {@link RandomGenerator#nextFloat nextFloat()}, and 457 * {@link RandomGenerator#nextDouble nextDouble()} methods are likewise exactly 458 * equidistributed. Some algorithms provide a further guarantee of 459 * <i>k</i>-equidistribution for some <i>k</i> greater than 1, meaning that successive 460 * non-overlapping <i>k</i>-tuples of 64-bit values produced by the 461 * {@link RandomGenerator#nextLong nextLong()} method are exactly 462 * equidistributed (equally likely to occur). 463 * 464 * <p> The following table gives the period, state size (in bits), parameter 465 * size (in bits, including the low-order bit that is required always to be a 466 * 1-bit), and equidistribution property for each of the specific LXM algorithms 467 * used in this package. 468 * 469 * <table style="padding:0px 20px 0px 0px"> 470 * <caption>Algorithm Properties</caption> 471 * <thead> 472 * <tr><th style="text-align:left">Implementation</th> 473 * <th style="text-align:right">Period</th> 474 * <th style="text-align:right">State size</th> 475 * <th style="text-align:right">Parameter size</th> 476 * <th style="text-align:left">{@link RandomGenerator#nextLong nextLong()} values are</th></tr> 477 * </thead> 478 * <tbody> 479 * <tr><td style="text-align:left">"L32X64MixRandom"</td> 480 * <td style="text-align:right">2<sup>32</sup>(2<sup>64</sup>−1)</td> 481 * <td style="text-align:right">96 bits</td> 482 * <td style="text-align:right">32 bits</td> 483 * <td style="text-align:left"></td></tr> 484 * <tr><td style="text-align:left">"L64X128StarStarRandom"</td> 485 * <td style="text-align:right">2<sup>64</sup>(2<sup>128</sup>−1)</td> 486 * <td style="text-align:right">192 bits</td> 487 * <td style="text-align:right">64 bits</td> 488 * <td style="text-align:left">2-equidistributed and exactly equidistributed</td></tr> 489 * <tr><td style="text-align:left">"L64X128MixRandom"</td> 490 * <td style="text-align:right">2<sup>64</sup>(2<sup>128</sup>−1)</td> 491 * <td style="text-align:right">192 bits</td> 492 * <td style="text-align:right">64 bits</td> 493 * <td style="text-align:left">2-equidistributed and exactly equidistributed</td></tr> 494 * <tr><td style="text-align:left">"L64X256MixRandom"</td> 495 * <td style="text-align:right">2<sup>64</sup>(2<sup>256</sup>−1)</td> 496 * <td style="text-align:right">320 bits</td> 497 * <td style="text-align:right">64 bits</td> 498 * <td style="text-align:left">4-equidistributed and exactly equidistributed</td></tr> 499 * <tr><td style="text-align:left">"L64X1024MixRandom"</td> 500 * <td style="text-align:right">2<sup>64</sup>(2<sup>1024</sup>−1)</td> 501 * <td style="text-align:right">1088 bits</td> 502 * <td style="text-align:right">64 bits</td> 503 * <td style="text-align:left">16-equidistributed and exactly equidistributed</td></tr> 504 * <tr><td style="text-align:left">"L128X128MixRandom"</td> 505 * <td style="text-align:right">2<sup>128</sup>(2<sup>128</sup>−1)</td> 506 * <td style="text-align:right">256 bits</td> 507 * <td style="text-align:right">128 bits</td> 508 * <td style="text-align:left">exactly equidistributed</td></tr> 509 * <tr><td style="text-align:left">"L128X256MixRandom"</td> 510 * <td style="text-align:right">2<sup>128</sup>(2<sup>256</sup>−1)</td> 511 * <td style="text-align:right">384 bits</td> 512 * <td style="text-align:right">128 bits</td> 513 * <td style="text-align:left">exactly equidistributed</td></tr> 514 * <tr><td style="text-align:left">"L128X1024MixRandom"</td> 515 * <td style="text-align:right">2<sup>128</sup>(2<sup>1024</sup>−1)</td> 516 * <td style="text-align:right">1152 bits</td> 517 * <td style="text-align:right">128 bits</td> 518 * <td style="text-align:left">exactly equidistributed</td></tr> 519 * </tbody> 520 * </table> 521 * 522 * For the algorithms listed above whose names begin with {@code L32}, the 523 * 32-bit values produced by the {@link RandomGenerator#nextInt nextInt()} 524 * method are exactly equidistributed, but the 64-bit values produced by the 525 * {@link RandomGenerator#nextLong nextLong()} method are not exactly 526 * equidistributed. 527 * 528 * <p> For the algorithms listed above whose names begin with {@code L64} or 529 * {@code L128}, the 64-bit values produced by the 530 * {@link RandomGenerator#nextLong nextLong()} method are <i>exactly 531 * equidistributed</i>: every instance, over the course of its cycle, will 532 * produce each of the 2<sup>64</sup> possible {@code long} values exactly the 533 * same number of times. For example, any specific instance of 534 * "L64X256MixRandom", over the course of its cycle each of the 535 * 2<sup>64</sup> possible {@code long} values will be produced 536 * 2<sup>256</sup>−1 times. The values produced by the 537 * {@link RandomGenerator#nextInt nextInt()}, 538 * {@link RandomGenerator#nextFloat nextFloat()}, and 539 * {@link RandomGenerator#nextDouble nextDouble()} methods are likewise exactly 540 * equidistributed. 541 * 542 * <p> In addition, for the algorithms listed above whose names begin with 543 * {@code L64}, the 64-bit values produced by the 544 * {@link RandomGenerator#nextLong nextLong()} method are 545 * <i>k</i>-equidistributed (but not exactly <i>k</i>-equidistributed). To be 546 * precise, and taking "L64X256MixRandom" as an example: for 547 * any specific instance of "L64X256MixRandom", consider the 548 * (overlapping) length-4 subsequences of the cycle of 64-bit values produced by 549 * {@link RandomGenerator#nextLong nextLong()} (assuming no other methods are 550 * called that would affect the state). There are 551 * 2<sup>64</sup>(2<sup>256</sup>−1) such subsequences, and each 552 * subsequence, which consists of 4 64-bit values, can have one of 553 * 2<sup>256</sup> values. Of those 2<sup>256</sup> subsequence values, nearly 554 * all of them (2<sup>256</sup>−2<sup>64</sup>) occur 2<sup>64</sup> times 555 * over the course of the entire cycle, and the other 2<sup>64</sup> subsequence 556 * values occur only 2<sup>64</sup>−1 times. So the ratio of the 557 * probability of getting any specific one of the less common subsequence values 558 * and the probability of getting any specific one of the more common 559 * subsequence values is 1−2<sup>-64</sup>. (Note that the set of 560 * 2<sup>64</sup> less-common subsequence values will differ from one instance 561 * of "L64X256MixRandom" to another, as a function of the 562 * additive parameter of the LCG.) The values produced by the 563 * {@link RandomGenerator#nextInt nextInt()}, 564 * {@link RandomGenerator#nextFloat nextFloat()}, and 565 * {@link RandomGenerator#nextDouble nextDouble()} methods are likewise 566 * 4-equidistributed (but not exactly 4-equidistributed). 567 * 568 * <p> The next table gives the LCG multiplier value, the name of the specific 569 * XBG algorithm used, the specific numeric parameters for that XBG 570 * algorithm, and the mixing function for each of the specific LXM algorithms 571 * used in this package. (Note that the multiplier used for the 128-bit LCG 572 * cases is 65 bits wide, so the constant {@code 0x1d605bbb58c8abbfdL} shown in 573 * the table cannot actually be used in code; instead, only the 64 low-order 574 * bits {@code 0xd605bbb58c8abbfdL} are represented in the source code, and the 575 * missing 1-bit is handled through special coding of the multiply-add algorithm 576 * used in the LCG.) 577 * 578 * <table style="padding:0px 20px 0px 0px"> 579 * <caption>LXM Multipliers</caption> 580 * <thead> 581 * <tr><th style="text-align:left">Implementation</th> 582 * <th style="text-align:right">LCG multiplier {@code m}</th> 583 * <th style="text-align:left">XBG algorithm</th> 584 * <th style="text-align:left">XBG parameters</th> 585 * <th style="text-align:left">Mixing function</th></tr> 586 * </thead> 587 * <tbody> 588 * <tr><td style="text-align:left">"L32X64MixRandom"</td> 589 * <td style="text-align:right">{@code 0xadb4a92d}</td> 590 * <td style="text-align:left">{@code xoroshiro64}, version 1.0</td> 591 * <td style="text-align:left">{@code (26, 9, 13)}</td> 592 * <td style="text-align:left">mixLea32{@code (s+x0)}</td></tr> 593 * <tr><td style="text-align:left">"L64X128StarStarRandom" </td> 594 * <td style="text-align:right">{@code 0xd1342543de82ef95L}</td> 595 * <td style="text-align:left">{@code xoroshiro128}, version 1.0</td> 596 * <td style="text-align:left">{@code (24, 16, 37)}</td> 597 * <td style="text-align:left">{@code Long.rotateLeft((s+x0)* 5, 7) * 9}</td></tr> 598 * <tr><td style="text-align:left">"L64X128MixRandom"</td> 599 * <td style="text-align:right">{@code 0xd1342543de82ef95L}</td> 600 * <td style="text-align:left">{@code xoroshiro128}, version 1.0</td> 601 * <td style="text-align:left">{@code (24, 16, 37)}</td> 602 * <td style="text-align:left">mixLea64{@code (s+x0)}</td></tr> 603 * <tr><td style="text-align:left">"L64X256MixRandom"</td> 604 * <td style="text-align:right">{@code 0xd1342543de82ef95L}</td> 605 * <td style="text-align:left">{@code xoshiro256}, version 1.0</td> 606 * <td style="text-align:left">{@code (17, 45)}</td> 607 * <td style="text-align:left">mixLea64{@code (s+x0)}</td></tr> 608 * <tr><td style="text-align:left">"L64X1024MixRandom"</td> 609 * <td style="text-align:right">{@code 0xd1342543de82ef95L}</td> 610 * <td style="text-align:left">{@code xoroshiro1024}, version 1.0</td> 611 * <td style="text-align:left">{@code (25, 27, 36)}</td> 612 * <td style="text-align:left">mixLea64{@code (s+x0)}</td></tr> 613 * <tr><td style="text-align:left">"L128X128MixRandom"</td> 614 * <td style="text-align:right">{@code 0x1d605bbb58c8abbfdL}</td> 615 * <td style="text-align:left">{@code xoroshiro128}, version 1.0</td> 616 * <td style="text-align:left">{@code (24, 16, 37)}</td> 617 * <td style="text-align:left">mixLea64{@code (sh+x0)}</td></tr> 618 * <tr><td style="text-align:left">"L128X256MixRandom"</td> 619 * <td style="text-align:right">{@code 0x1d605bbb58c8abbfdL}</td> 620 * <td style="text-align:left">{@code xoshiro256}, version 1.0</td> 621 * <td style="text-align:left">{@code (17, 45)}</td> 622 * <td style="text-align:left">mixLea64{@code (sh+x0)}</td></tr> 623 * <tr><td style="text-align:left">"L128X1024MixRandom"</td> 624 * <td style="text-align:right">{@code 0x1d605bbb58c8abbfdL}</td> 625 * <td style="text-align:left">{@code xoroshiro1024}, version 1.0</td> 626 * <td style="text-align:left">{@code (25, 27, 36)}</td> 627 * <td style="text-align:left">mixLea64{@code (sh+x0)}</td></tr> 628 * </tbody> 629 * </table> 630 * 631 * @since 17 632 */ 633 package java.util.random; 634 635