org.aitools.programd.util
Class MersenneTwister

java.lang.Object
  extended by java.util.Random
      extended by org.aitools.programd.util.MersenneTwister
All Implemented Interfaces:
java.io.Serializable

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

Mersenne Twister and MersenneTwisterFast

Version 3 , based on version MT199937(99/10/29) of the Mersenne Twister algorithm found at The Mersenne Twister Home Page . By Sean Luke, June 2000.

MersenneTwister is a drop-in subclass replacement for java.util.Random. It is properly synchronized and can be used in a multithreaded environment.

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 over twice the speed of MersenneTwister.

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

This version of the code implements the MT19937 Mersenne Twister algorithm, with the 99/10/29 seeding mechanism. The original mechanism did not permit 0 as a seed, and odd numbers were not good seed choices. The new version permits any 32-bit signed integer. This algorithm is identical to the MT19937 integer algorithm; real values conform to Sun's float and double random number generator standards rather than attempting to implement the half-open or full-open MT19937-1 and MT199937-2 algorithms.

This 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 is Copyright (c) 1999 by Michael Lecuyer. The included license is as follows:

The basic algorithmic work of this library (appearing in nextInt() and setSeed()) is free software; you can redistribute it and or modify it under the terms of the GNU Library General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version.

This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Library General Public License for more details. You should have received a copy of the GNU Library General Public License along with this library; if not, write to the Free Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA

Bug Fixes

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.

Important Note on Seeds

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.

Timings On Different Java Versions

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. And why would you use 'em anyway? They're very slow, as you'll see. Here are some timings in milliseconds on a Sun Creator3D/Ultra 60 running SunOS 5.6.

Standard C Version (gcc -O2)
1070
Standard C Version (Solaris cc -O)
1210
JDK 1.2.2 w/Hotspot Compiler (-O)
MTF: 1785, MT: 3699, java.util.Random: 4849
JDK 1.2.1/1.2.2 (-O)
MTF: 1827, MT: 3868, java.util.Random: 4194
JDK 1.1.8 (-O)
MTF: 40509, MT: 45853, java.util.Random: 24604
Beats me why it's so slow...
JDK 1.1.5 (-O)
MTF: 4056, MT: 20478, java.util.Random: 19692
JDK 1.0.2 (-O)
MTF: 71640, MT: 66176, java.util.Random: 67269
Important note: Do not MersenneTwister.java or java.util.Random on a Java version this early! Random number generation in versions less than 1.1.5 has serious bugs.

See Also:
Serialized Form

Field Summary
private  boolean __haveNextNextGaussian
           
private  double __nextNextGaussian
           
private static long GOOD_SEED
           
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 int TEMPERING_MASK_B
           
private static int TEMPERING_MASK_C
           
private static int UPPER_MASK
           
 
Constructor Summary
MersenneTwister()
          Constructor using the default 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)
           
 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.
 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!
 char nextChar()
          For completeness' sake, though it's not in java.util.Random.
 short nextShort()
          For completeness' sake, though it's not in java.util.Random.
private  void readObject(java.io.ObjectInputStream in)
           
 void setSeed(int[] array)
          An alternative, more complete, method of seeding the pseudo random number generator. array must be an array of 624 ints, and they can be any value as long as they're not *all* zero.
 void setSeed(long seed)
          Initalize the pseudo random number generator.
 void setSeedOld(long seed)
          Initalize the pseudo random number generator.
private  void writeObject(java.io.ObjectOutputStream out)
           
 
Methods inherited from class java.util.Random
nextBoolean, nextDouble, nextFloat, nextInt, nextInt, nextLong
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

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

GOOD_SEED

private static final long GOOD_SEED
See Also:
Constant Field Values

__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.

Parameters:
seed - the seed to use
Method Detail

setSeedOld

public void setSeedOld(long seed)
Initalize the pseudo random number generator. This is the old seed-setting mechanism for the original Mersenne Twister algorithm. You must not use 0 as your seed, and don't pass in a long that's bigger than an int (Mersenne Twister only uses the first 32 bits for its seed). Also it's suggested that for you avoid even-numbered seeds in this older seed-generation procedure.

Parameters:
seed - the seed to use

setSeed

public void setSeed(int[] array)
An alternative, more complete, method of seeding the pseudo random number generator. array must be an array of 624 ints, and they can be any value as long as they're not *all* zero.

Parameters:
array - an array of 624 ints

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
Parameters:
seed - the seed to use

next

protected int next(int bits)
Overrides:
next in class java.util.Random
Parameters:
bits - the number of bits to use
Returns:
an integer with bits bits filled with a random number

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(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.

Parameters:
probability - the probability to use (between 0.0 and 1.0)
Returns:
the coin flip result

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.

Parameters:
probability - must be between 0.0 and 1.0
Returns:
the result of the coin flip

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
Parameters:
bytes - the bytes for which to get the next bytes (?)

nextChar

public char nextChar()
For completeness' sake, though it's not in java.util.Random.

Returns:
the next char

nextShort

public short nextShort()
For completeness' sake, though it's not in java.util.Random.

Returns:
the next short

nextByte

public byte nextByte()
For completeness' sake, though it's not in java.util.Random.

Returns:
the next byte

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
Returns:
the next Gaussian

main

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

Parameters:
args - not used