Class MersenneTwister
MersenneTwister and MersenneTwisterFast
Version 22, based on version MT199937(99/10/29) of the Mersenne Twister algorithm found at The Mersenne Twister Home Page, with the initialization improved using the new 2002/1/26 initialization algorithm By Sean Luke, October 2004.
MersenneTwister is a drop-in subclass replacement for java.util.Random. It is properly synchronized and can be used in a multithreaded environment. On modern VMs such as HotSpot, it is approximately 1/3 slower than java.util.Random.
MersenneTwisterFast is not a subclass of java.util.Random. It has the same public methods as Random does, however, and it is algorithmically identical to MersenneTwister. MersenneTwisterFast has hard-code inlined all of its methods directly, and made all of them final (well, the ones of consequence anyway). Further, these methods are not synchronized, so the same MersenneTwisterFast instance cannot be shared by multiple threads. But all this helps MersenneTwisterFast achieve well over twice the speed of MersenneTwister. java.util.Random is about 1/3 slower than MersenneTwisterFast.
About the Mersenne Twister
This is a Java version of the C-program for MT19937: Integer version. The MT19937 algorithm was created by Makoto Matsumoto and Takuji Nishimura, who ask: "When you use this, send an email to: matumoto@math.keio.ac.jp with an appropriate reference to your work". Indicate that this is a translation of their algorithm into Java.
Reference. Makato Matsumoto and Takuji Nishimura, "Mersenne Twister: A 623-Dimensionally Equidistributed Uniform Pseudo-Random Number Generator", ACM Transactions on Modeling and. Computer Simulation, Vol. 8, No. 1, January 1998, pp 3--30.
About this Version
Changes since V21: Minor documentation HTML fixes.
Changes since V20: Added clearGuassian(). Modified stateEquals() to be synchronizd on both objects for MersenneTwister, and changed its documentation. Added synchronization to both setSeed() methods, to writeState(), and to readState() in MersenneTwister. Removed synchronization from readObject() in MersenneTwister.
Changes since V19: nextFloat(boolean, boolean) now returns float, not double.
Changes since V18: Removed old final declarations, which used to potentially speed up the code, but no longer.
Changes since V17: Removed vestigial references to &= 0xffffffff which stemmed from the original C code. The C code could not guarantee that ints were 32 bit, hence the masks. The vestigial references in the Java code were likely optimized out anyway.
Changes since V16: Added nextDouble(includeZero, includeOne) and nextFloat(includeZero, includeOne) to allow for half-open, fully-closed, and fully-open intervals.
Changes Since V15: Added serialVersionUID to quiet compiler warnings from Sun's overly verbose compilers as of JDK 1.5.
Changes Since V14: made strictfp, with StrictMath.log and StrictMath.sqrt in nextGaussian instead of Math.log and Math.sqrt. This is largely just to be safe, as it presently makes no difference in the speed, correctness, or results of the algorithm.
Changes Since V13: clone() method CloneNotSupportedException removed.
Changes Since V12: clone() method added.
Changes Since V11: stateEquals(...) method added. MersenneTwisterFast is equal to other MersenneTwisterFasts with identical state; likewise MersenneTwister is equal to other MersenneTwister with identical state. This isn't equals(...) because that requires a contract of immutability to compare by value.
Changes Since V10: A documentation error suggested that setSeed(int[]) required an int[] array 624 long. In fact, the array can be any non-zero length. The new version also checks for this fact.
Changes Since V9: readState(stream) and writeState(stream) provided.
Changes Since V8: setSeed(int) was only using the first 28 bits of the seed; it should have been 32 bits. For small-number seeds the behavior is identical.
Changes Since V7: A documentation error in MersenneTwisterFast (but not MersenneTwister) stated that nextDouble selects uniformly from the full-open interval [0,1]. It does not. nextDouble's contract is identical across MersenneTwisterFast, MersenneTwister, and java.util.Random, namely, selection in the half-open interval [0,1). That is, 1.0 should not be returned. A similar contract exists in nextFloat.
Changes Since V6: License has changed from LGPL to BSD. New timing information to compare against java.util.Random. Recent versions of HotSpot have helped Random increase in speed to the point where it is faster than MersenneTwister but slower than MersenneTwisterFast (which should be the case, as it's a less complex algorithm but is synchronized).
Changes Since V5: New empty constructor made to work the same as java.util.Random -- namely, it seeds based on the current time in milliseconds.
Changes Since V4: New initialization algorithms. See (see http://www.math.keio.ac.jp/matumoto/MT2002/emt19937ar.html)
The MersenneTwister code is based on standard MT19937 C/C++ code by Takuji Nishimura, with suggestions from Topher Cooper and Marc Rieffel, July 1997. The code was originally translated into Java by Michael Lecuyer, January 1999, and the original code is Copyright (c) 1999 by Michael Lecuyer.
Java notes
This implementation implements the bug fixes made in Java 1.2's version of Random, which means it can be used with earlier versions of Java. See the JDK 1.2 java.util.Random documentation for further documentation on the random-number generation contracts made. Additionally, there's an undocumented bug in the JDK java.util.Random.nextBytes() method, which this code fixes.
Just like java.util.Random, this generator accepts a long seed but doesn't use all of it. java.util.Random uses 48 bits. The Mersenne Twister instead uses 32 bits (int size). So it's best if your seed does not exceed the int range.
MersenneTwister can be used reliably on JDK version 1.1.5 or above. Earlier Java versions have serious bugs in java.util.Random; only MersenneTwisterFast (and not MersenneTwister nor java.util.Random) should be used with them.
License
Copyright (c) 2003 by Sean Luke.Portions copyright (c) 1993 by Michael Lecuyer.
All rights reserved.
Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:
- Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
- Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.
- Neither the name of the copyright owners, their employers, nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission.
THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
- Version:
- 22
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescriptionstatic interface
The minimalChronometer
interface is only used to hide differences for measuring execution time in JRE and GWT.(package private) static class
Minimal implementation of Chronometer. -
Field Summary
FieldsModifier and TypeFieldDescriptionprivate boolean
The flag to indicate that the next Gaussian has already been generated.private double
Gaussian random numbers are generated in pairs.private static final int
private static StringBuilder
ChH: for testing on GWT/JRE platforms logging needs to be rewrittenprivate static final double
Constant:1/(2^-31 - 1)
.private static final int
private static final int
private static final int
private int[]
The array for the state vectorprivate int
The current index for the state vector.private static final int
Period parametersprivate static final int
Tempering parametersprivate static final int
private static final double
Constant:2^27
.private static final float
Constant:2^31
.private static final double
Constant:2^31 - 1
.private static final double
Constant:2^32
.private static final double
Constant:2^53
.private static final double
Constant:2^-24
.private static final double
Constant:2^-25
.private static final double
Constant:2^-27
.private static final double
Constant:1/2^-31
.private static final float
Constant:2^-31
.private static final double
Constant:2^-52
.private static final double
Constant:2^-53
.private static final int
-
Constructor Summary
ConstructorsConstructorDescriptionConstructor using the default seed.MersenneTwister
(int[] array) Constructor using an array of integers as seed.MersenneTwister
(long seed) Constructor using a given seed. -
Method Summary
Modifier and TypeMethodDescriptionprivate static void
appendProgress
(String msg) Append message to buffer (no newline added).void
Clears the internal Gaussian variable from the RNG.clone()
Clone this MersenneTwister to ensure both objects return identical sequences of random numbers.Encode state of random number generator asplist
for saving.private static void
Append newline to buffer.private static void
logProgress
(String msg) Append message to buffer (adding newline).static void
Tests the code.boolean
Generates a random boolean.boolean
nextBoolean
(double probability) This generates a coin flip with a probabilityprobability
of returningtrue
, else returningfalse
.boolean
nextBoolean
(float probability) This generates a coin flip with a probabilityprobability
of returningtrue
, else returningfalse
.byte
nextByte()
Generates a randombyte
on[0, 0xff]
-interval.void
nextBytes
(byte[] bytes) Fill arraybytes
with random bytes.char
nextChar()
generates a randomchar
on[0, 0xffff]
-interval.double
Generate randomdouble
on half-open[0, 1)
-interval.double
Generate random double on closed[0, 1]
-intervaldouble
Generates a random high-precision double on half-open[0, 1)
-interval.double
Generate random double on open(0, 1)
-intervalfloat
Generates a randomfloat
on half-open[0, 1)
-interval.double
Generate random number from standard normal distribution (Gaussian distribution).int
nextInt()
Generate a 31bit (signed) randomint
in[0, Integer.MAX_VALUE)
.int
nextInt
(int n) Generate a randomint
in[0, n-1]
-interval.long
nextLong()
Generate a 63bit (signed) randomlong
integer in[0, Long.MAX_VALUE)
.long
nextLong
(long n) Generate a randomlong
integer in[0, n)
withn > 0
.short
Generates a random short integer on[0, 0xffff]
-interval.private int
nextUInt()
Generates a 32bit 'unsigned' randomint
in[0, 2^33-1]
.private long
Generate a 64bit unsigned random long in[0, 2^65-1]
.boolean
restoreState
(Plist plist) Restore state of random number generator fromplist
encoded string.void
setSeed
(int[] array) Sets the seed of the MersenneTwister using an array of integers.void
setSeed
(long seed) Initialize the pseudo random number generator.boolean
stateEquals
(MersenneTwister other) Returns true if the MersenneTwister's current internal state is equal to another MersenneTwister.static void
testCorrectness
(Logger logger) Tests if generated random numbers comply with referencemt19937ar.c
.static void
testSpeed
(Logger logger, MersenneTwister.Chronometer clock, int nSamples) Tests speed of MersenneTwister as compared toRandom
.private void
twist()
The twister: core mechanism for generating pseudo random numbers.
-
Field Details
-
N
private static final int NPeriod parameters- See Also:
-
M
private static final int M- See Also:
-
MATRIX_A
private static final int MATRIX_A- See Also:
-
BIT32_MASK
private static final int BIT32_MASK- See Also:
-
UPPER_MASK
private static final int UPPER_MASK- See Also:
-
LOWER_MASK
private static final int LOWER_MASK- See Also:
-
TEMPERING_MASK_B
private static final int TEMPERING_MASK_BTempering parameters- See Also:
-
TEMPERING_MASK_C
private static final int TEMPERING_MASK_C- See Also:
-
TWO_TO_27
private static final double TWO_TO_27Constant:2^27
.- See Also:
-
TWO_TO_31f
private static final float TWO_TO_31fConstant:2^31
.- See Also:
-
TWO_TO_31M1
private static final double TWO_TO_31M1Constant:2^31 - 1
.- See Also:
-
TWO_TO_32
private static final double TWO_TO_32Constant:2^32
.- See Also:
-
TWO_TO_53
private static final double TWO_TO_53Constant:2^53
.- See Also:
-
TWO_TO_NEG24
private static final double TWO_TO_NEG24Constant:2^-24
.- See Also:
-
TWO_TO_NEG25
private static final double TWO_TO_NEG25Constant:2^-25
.- See Also:
-
TWO_TO_NEG27
private static final double TWO_TO_NEG27Constant:2^-27
.- See Also:
-
TWO_TO_NEG31f
private static final float TWO_TO_NEG31fConstant:2^-31
.- See Also:
-
TWO_TO_NEG31
private static final double TWO_TO_NEG31Constant:1/2^-31
.- See Also:
-
INV_TWO_TO_31M1
private static final double INV_TWO_TO_31M1Constant:1/(2^-31 - 1)
.- See Also:
-
TWO_TO_NEG52
private static final double TWO_TO_NEG52Constant:2^-52
.- See Also:
-
TWO_TO_NEG53
private static final double TWO_TO_NEG53Constant:2^-53
.- See Also:
-
mt
private int[] mtThe array for the state vector -
mti
private int mtiThe current index for the state vector.mti == N+1
meansmt[N]
is not initialized. -
__nextNextGaussian
private double __nextNextGaussianGaussian random numbers are generated in pairs. This is the second of the two. -
__haveNextNextGaussian
private boolean __haveNextNextGaussianThe flag to indicate that the next Gaussian has already been generated.- See Also:
-
buffer
ChH: for testing on GWT/JRE platforms logging needs to be rewritten
-
-
Constructor Details
-
MersenneTwister
public MersenneTwister()Constructor using the default seed. -
MersenneTwister
public MersenneTwister(long seed) Constructor using a given seed. Though you pass this seed in as a long, it's best to make sure it's actually an integer.- Parameters:
seed
- for random number generator
-
MersenneTwister
public MersenneTwister(int[] array) Constructor using an array of integers as seed. Your array must have a non-zero length. Only the first 624 integers in the array are used; if the array is shorter than this then integers are repeatedly used in a wrap-around fashion.- Parameters:
array
- of integers for seeding the random number generator
-
-
Method Details
-
encodeState
Encode state of random number generator asplist
for saving.- Returns:
plist
string encoding state of random number generator
-
restoreState
Restore state of random number generator fromplist
encoded string.- Parameters:
plist
- encoded state of random number generator- Returns:
true
if state successfully restored
-
stateEquals
Returns true if the MersenneTwister's current internal state is equal to another MersenneTwister. This is roughly the same as equals(other), except that it compares based on value but does not guarantee the contract of immutability (obviously random number generators are immutable). Note that this does NOT check to see if the internal gaussian storage is the same for both. You can guarantee that the internal gaussian storage is the same (and so the nextGaussian() methods will return the same values) by calling clearGaussian() on both objects.- Parameters:
other
- anotherMersenneTwister
- Returns:
true
the twoMersenneTwister
's are identical.
-
setSeed
public void setSeed(long seed) Initialize the pseudo random number generator. Don't pass in a long that's bigger than an int (Mersenne Twister only uses the first 32 bits for its seed).Implementation Notes:
- Writing java code that GWT can translate into equivalent JavaScript turns out to be challenging. Stephan Brumme's JavaScript implementation supplied the essential tricks. For details see https://create.stephan-brumme.com/mersenne-twister/
- In order to avoid multiplication overflow split 32 bits into 2x 16 bits
and process them individually (see
mtmti1
in code). - See Knuth TAOCP Vol2. 3rd Ed. p.106 for multiplier
- Parameters:
seed
- the seed for the random number generator
-
setSeed
public void setSeed(int[] array) Sets the seed of the MersenneTwister using an array of integers. Your array must have a non-zero length. Only the first 624 integers in the array are used; if the array is shorter than this then integers are repeatedly used in a wrap-around fashion.- Parameters:
array
- of integers for seeding the random number generator
-
twist
private void twist()The twister: core mechanism for generating pseudo random numbers.Note: Adapted from
mersenne.js
, JavaScript version of MersenneTwister by Stephan Brumme.- See Also:
-
nextUInt
private int nextUInt()Generates a 32bit 'unsigned' randomint
in[0, 2^33-1]
. All 32bits represent random number - use with care! Allows to verify output with original mt19937ar.c output.From
mt19937ar.c
: generates a random number on[0, 0xffffffff]
-interval corresponds to:unsigned long genrand_int32
- Returns:
- random
int
in[0, 2^33-1]
-
nextInt
public int nextInt()Generate a 31bit (signed) randomint
in[0, Integer.MAX_VALUE)
.From
mt19937ar.c
: generates a random number on[0, 0x7fffffff]
-interval corresponds to:unsigned long genrand_int31
- Returns:
- random
int
in[0, 2^32-1]
-
nextInt
public int nextInt(int n) Generate a randomint
in[0, n-1]
-interval.- Parameters:
n
- integer upper bound (exclusive)- Returns:
- random integer in
[0, n)
- Throws:
IllegalArgumentException
- ifn ≤ 0
-
nextULong
private long nextULong()Generate a 64bit unsigned random long in[0, 2^65-1]
.- Returns:
- random
long
integer in[0, 2^65-1]
-
nextLong
public long nextLong()Generate a 63bit (signed) randomlong
integer in[0, Long.MAX_VALUE)
.Note:
- Twice as expensive as nextInt().
- Do not use in GWT applications (
long
integers are CPU hogs).
- Returns:
- random
long
integer in[0, 2^63-1]
-
nextLong
public long nextLong(long n) Generate a randomlong
integer in[0, n)
withn > 0
.Note:
- Twice as expensive as
nextInt(int)
. - Do not use in GWT applications (
long
integers are CPU hogs).
- Parameters:
n
- integer upper bound (exclusive)- Returns:
- random
long
integer in[0, n]
- Throws:
IllegalArgumentException
- ifn ≤ 0
- Twice as expensive as
-
nextShort
public short nextShort()Generates a random short integer on[0, 0xffff]
-interval.Note:
- same as nextChar() but different return type.
- Do not use in GWT applications (
short
integers are not supported).
- Returns:
- random
short
integer in[0, 65536)
-
nextChar
public char nextChar()generates a randomchar
on[0, 0xffff]
-interval.Note: same as nextShort() but different return type.
- Returns:
- random
short
integer in[0, 65536)
-
nextByte
public byte nextByte()Generates a randombyte
on[0, 0xff]
-interval.- Returns:
- random
short
integer in[0, 16)
-
nextBytes
public void nextBytes(byte[] bytes) Fill arraybytes
with random bytes.- Parameters:
bytes
- random bytes stored here- See Also:
-
nextBoolean
public boolean nextBoolean()Generates a random boolean.- Returns:
true
with 50% chance
-
nextBoolean
public boolean nextBoolean(float probability) This generates a coin flip with a probabilityprobability
of returningtrue
, else returningfalse
.probability
must be in[0, 1]
. Not as precise asnextBoolean(double)
, but twice as fast. To explicitly use this, remember you may need to cast tofloat
first.Note: Do not use in GWT applications (
float
's create overhead).- Parameters:
probability
- for returningtrue
- Returns:
true
withprobability
- Throws:
IllegalArgumentException
- ifprobability<0
orprobability>1
-
nextBoolean
public boolean nextBoolean(double probability) This generates a coin flip with a probabilityprobability
of returningtrue
, else returningfalse
.probability
must be in[0, 1]
.Note: More accurate than
nextBoolean(float)
, but twice as expensive- Parameters:
probability
- for returning true- Returns:
true
withprobability
- Throws:
IllegalArgumentException
- ifprobability<0
orprobability>1
-
nextDoubleHigh
public double nextDoubleHigh()Generates a random high-precision double on half-open[0, 1)
-interval.From
mt19937ar.c
: generates a random number on[0,1)
with 53-bit resolution corresponds to:double genrand_res53(void)
.Note: Twice as expensive as
nextDouble()
or the equivalentnextFloat()
.- Returns:
- random high-precision
double
in[0, 1)
-
nextDouble
public double nextDouble()Generate randomdouble
on half-open[0, 1)
-interval.From
mt19937ar.c
: generates a random number on[0,1)
-real-interval corresponds to:double genrand_real2(void)
.Note:
- Twice as fast as
nextDoubleHigh()
- Equivalent to
nextFloat()
- One bit lost compared to original due to signed
int
- Returns:
- random
double
in[0, 1)
- Twice as fast as
-
nextDoubleClosed
public double nextDoubleClosed()Generate random double on closed[0, 1]
-intervalFrom
mt19937ar.c
: generates a random number on[0,1]
-real-interval corresponds to:double genrand_real1(void)
.Note: one bit lost compared to original due to signed
int
.- Returns:
- random double in
[0, 1]
-
nextDoubleOpen
public double nextDoubleOpen()Generate random double on open(0, 1)
-intervalFrom
mt19937ar.c
: generates a random number on(0,1)
-real-interval corresponds to:double genrand_real3(void)
.Note: one bit lost compared to original due to signed
int
.- Returns:
- random
double
in(0, 1)
-
nextFloat
public float nextFloat()Generates a randomfloat
on half-open[0, 1)
-interval.Note:
- Twice as fast as
nextDouble()
. - Do not use in GWT applications (
float
's create overhead).
- Returns:
- random
float
in[0, 1)
- Twice as fast as
-
clearGaussian
public void clearGaussian()Clears the internal Gaussian variable from the RNG. You only need to do this in the rare case that you need to guarantee that two RNGs have identical internal state. Otherwise, disregard this method.- See Also:
-
nextGaussian
public double nextGaussian()Generate random number from standard normal distribution (Gaussian distribution).- Returns:
- random number
-
clone
Clone this MersenneTwister to ensure both objects return identical sequences of random numbers.IMPORTANT:
-
appendProgress
Append message to buffer (no newline added).- Parameters:
msg
- message to append
-
logProgress
private static void logProgress()Append newline to buffer. -
logProgress
Append message to buffer (adding newline).- Parameters:
msg
- message to append
-
testCorrectness
Tests if generated random numbers comply with referencemt19937ar.c
.- Parameters:
logger
- for reporting progress and results
-
testSpeed
Tests speed of MersenneTwister as compared toRandom
.- Parameters:
logger
- for reporting progress and resultsclock
- device for measuring elapsed timenSamples
- number of samples for testing speed
-
main
Tests the code.- Parameters:
args
- command line arguments - ignored
-