ec.util
Class MersenneTwister

java.lang.Object
  java.util.Random
      ec.util.MersenneTwister

All Implemented Interfaces:

java.io.Serializable

public class MersenneTwister
extends java.util.Random
implements java.io.Serializable

MersenneTwister and MersenneTwisterFast

Version 10, 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 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:

11

See Also:

Serialized Form

Field Summary

private boolean	__haveNextNextGaussian
private double	__nextNextGaussian
private static int	LOWER_MASK
private static int	M
private int[]	mag01
private static int	MATRIX_A
private int[]	mt
private int	mti
private static int	N
private static long	serialVersionUID
private static int	TEMPERING_MASK_B
private static int	TEMPERING_MASK_C
private static int	UPPER_MASK

Constructor Summary

MersenneTwister()
Constructor 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

static void	main(java.lang.String[] args) Tests the code.
protected int	next(int bits) Returns an integer with bits bits filled with a random number.
boolean	nextBoolean() This method is missing from jdk 1.0.x and below.
boolean	nextBoolean(double probability) This generates a coin flip with a probability probability of returning true, else returning false.
boolean	nextBoolean(float probability) This generates a coin flip with a probability probability of returning true, else returning false.
byte	nextByte() For completeness' sake, though it's not in java.util.Random.
void	nextBytes(byte[] bytes) A bug fix for all versions of the JDK.
char	nextChar() For completeness' sake, though it's not in java.util.Random.
double	nextDouble() A bug fix for versions of JDK 1.1 and below.
float	nextFloat() A bug fix for versions of JDK 1.1 and below.
double	nextGaussian() A bug fix for all JDK code including 1.2.
int	nextInt(int n) This method is missing from JDK 1.1 and below.
long	nextLong(long n) This method is for completness' sake.
short	nextShort() For completeness' sake, though it's not in java.util.Random.
private void	readObject(java.io.ObjectInputStream in)
void	readState(java.io.DataInputStream stream) Reads the entire state of the MersenneTwister RNG from the stream
void	setSeed(int[] array) Sets the seed of the MersenneTwister using an array of integers.
void	setSeed(long seed) Initalize the pseudo random number generator.
private void	writeObject(java.io.ObjectOutputStream out)
void	writeState(java.io.DataOutputStream stream) Writes the entire state of the MersenneTwister RNG to the stream

Methods inherited from class java.util.Random

nextInt, nextLong

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

serialVersionUID

private static final long serialVersionUID

See Also:

Constant Field Values

N

private static final int N

See Also:

Constant Field Values

M

private static final int M

See Also:

Constant Field Values

MATRIX_A

private static final int MATRIX_A

See Also:

Constant Field Values

UPPER_MASK

private static final int UPPER_MASK

See Also:

Constant Field Values

LOWER_MASK

private static final int LOWER_MASK

See Also:

Constant Field Values

TEMPERING_MASK_B

private static final int TEMPERING_MASK_B

See Also:

Constant Field Values

TEMPERING_MASK_C

private static final int TEMPERING_MASK_C

See Also:

Constant Field Values

mt

private int[] mt

mti

private int mti

mag01

private int[] mag01

__nextNextGaussian

private double __nextNextGaussian

__haveNextNextGaussian

private boolean __haveNextNextGaussian

Constructor Detail

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.

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.

Method Detail

readState

public void readState(java.io.DataInputStream stream)
               throws java.io.IOException

Reads the entire state of the MersenneTwister RNG from the stream

Throws:

java.io.IOException

writeState

public void writeState(java.io.DataOutputStream stream)
                throws java.io.IOException

Writes the entire state of the MersenneTwister RNG to the stream

Throws:

java.io.IOException

setSeed

public void setSeed(long seed)

Initalize 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).

Overrides:

setSeed in class java.util.Random

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.

next

protected int next(int bits)

Returns an integer with bits bits filled with a random number.

Overrides:

next in class java.util.Random

writeObject

private void writeObject(java.io.ObjectOutputStream out)
                  throws java.io.IOException

Throws:

java.io.IOException

readObject

private void readObject(java.io.ObjectInputStream in)
                 throws java.io.IOException,
                        java.lang.ClassNotFoundException

Throws:

java.io.IOException

java.lang.ClassNotFoundException

nextBoolean

public boolean nextBoolean()

This method is missing from jdk 1.0.x and below. JDK 1.1 includes this for us, but what the heck.

Overrides:

nextBoolean in class java.util.Random

nextBoolean

public boolean nextBoolean(float probability)

This generates a coin flip with a probability probability of returning true, else returning false. probability must be between 0.0 and 1.0, inclusive. Not as precise a random real event as nextBoolean(double), but twice as fast. To explicitly use this, remember you may need to cast to float first.

nextBoolean

public boolean nextBoolean(double probability)

This generates a coin flip with a probability probability of returning true, else returning false. probability must be between 0.0 and 1.0, inclusive.

nextInt

public int nextInt(int n)

This method is missing from JDK 1.1 and below. JDK 1.2 includes this for us, but what the heck.

Overrides:

nextInt in class java.util.Random

nextLong

public long nextLong(long n)

This method is for completness' sake. Returns a long drawn uniformly from 0 to n-1. Suffice it to say, n must be > 0, or an IllegalArgumentException is raised.

nextDouble

public double nextDouble()

A bug fix for versions of JDK 1.1 and below. JDK 1.2 fixes this for us, but what the heck.

Overrides:

nextDouble in class java.util.Random

nextFloat

public float nextFloat()

A bug fix for versions of JDK 1.1 and below. JDK 1.2 fixes this for us, but what the heck.

Overrides:

nextFloat in class java.util.Random

nextBytes

public void nextBytes(byte[] bytes)

A bug fix for all versions of the JDK. The JDK appears to use all four bytes in an integer as independent byte values! Totally wrong. I've submitted a bug report.

Overrides:

nextBytes in class java.util.Random

nextChar

public char nextChar()

For completeness' sake, though it's not in java.util.Random.

nextShort

public short nextShort()

For completeness' sake, though it's not in java.util.Random.

nextByte

public byte nextByte()

For completeness' sake, though it's not in java.util.Random.

nextGaussian

public double nextGaussian()

A bug fix for all JDK code including 1.2. nextGaussian can theoretically ask for the log of 0 and divide it by 0! See Java bug http://developer.java.sun.com/developer/bugParade/bugs/4254501.html

Overrides:

nextGaussian in class java.util.Random

main

public static void main(java.lang.String[] args)

Tests the code.