Multiple stream Mersenne Twister PRNG


Program (Link to Latest)[mt_stream_f90.tar.gz] [2011/03/31]

This program module splits single long period random number series from Mersenne Twister (MT) into multiple (almost) independent streams. This enables us the use of parallel Mersenne Twister in a large scale parallel simulation with MPI or OpenMP. This module provides several routines to manipulate multiple stream state and to generate random numbers.

The main part of the program is written in Fortran90/95. A part of the program uses some external libraries written in C/C++ language.
ISO C binding feature of Fortran 2003 is used to link with NTL/GF2X C++ libraries (version 1.10). The list of the compilers which support the feature, to my knowledge, is;

The parameter included in this program is taken from the original code (MT19937) by Makoto Matsumoto and Takuji Nishimura []. The stream length picked out from the long period is fixed to 2^256.

The method to divide the main stream into several streams is based on the manipulation on the polynomial representation of transition matrix with Cayley-Hamilton theorem for the characteristic polynomial of MT. I only use Horner's method to jump long ahead from the initial state to the next stream initial state. For the details on this method see the following original paper:
[Ref.: H. Haramoto, M. Matsumoto, T. Nishimura, F. Panneton, and P. L'Ecuyer, ``Efficient Jump Ahead for F_2-Linear Random Number Generators'', GERAD Report G-2006-62. INFORMS Journal on Computing, 20, 3 (2008), 385-390.]

In the paper they also describe more efficient method to realize the long jump: the sliding window method. I, however, coded simple/less efficient Horner's method only.

In order to obtain the polynomial coefficients to make the MT state to jump by 2^256 steps, we employ the following external libraries in default setting:

Install these libraries before compiling MT Stream. These libraries use C/C++.
If C/C++/NTL/GF2X are not available, I included a slow GF2X library written in Fortran90. To use the fully Fortran version, define `NTL_USE=no' in Makefile (`NTL_USE=yes' is default)(2010/03/08).

The MT state initialization routine used in this program is the same as that of the original MT19931 with improved initialization by Matusmoto-Nishimura (see also their original web page). I have checked that my generator produces the same first 1000 integer numbers as those of the original MT19931.

To check whether the state jump ahead routine works correctly or not, I have tested the following points. By setting the stream length to 2^15, make a branch form the master stream with the jump ahead routine. I have checked that the branch stream produces the same numbers as those from the master stream, where the master stream simply drops 2^15 random numbers to catch up the branch stream. I also checked this simple test for 1024 multiple streams separated by 2^15 steps each.

Note that I have not completely checked/understood the autocorrelation among multiple disjoint streams picked out from the long period stream.

This MT stream module library can yield the following types of random numbers:

This program is NO WARRANTY. License follows the New BSD License.

Compile: This program has been developed on Linux with gcc/g++/gfortran and Intel compilers.

  1. If C/C++/NTL/GF2X are available, compile and Install the following external libraries:
    If C/C++/NTL/GF2X are not available skip step 1 go next.

  2. Untar program tarball (Latest) [mt_stream_f90.tar.gz].
    Check and Edit the compiler settings in the Makefile.
    Set the include and library paths to the above external libraries in the Makefile.
    If C/C++/NTL/NG2X are not available, edit Makefile to define USE_NTL = no.

  3. Type make. You will see some auto consistency checks during compilation.

  4. mt_stream.o and mt_stream.mod are the main product of this MT Stream library.
    If you choose to use NTL/GF2X libraries, the following object file is generated. If you do not use NTL/GF2X libraries, the following object files are generated. You can write programs using the routines from the MT Stream library. To compile your program you need to put 'use mt_stream' statement and to link to mt_stream.o and the above jump ahead object files. Compiler will require mt_stream.mod in the include search path.

The subroutine/function list contained in this MT Stream module.

I would like to greatly thank to The Mersenne Twister web page by Makoto Matsumoto, at which I could find the original papers and related documents on MT/RNG and very useful links to samples and related programs. Without this page I could not develop this program and understand the philosophy on MT and better PRNG.
I also express my gratitude to the authors of various implementations in C/C++/Fortran etc. on his web page.
I thank Michael Briggs for his kind comments and contributions on the code.
I thank Tridib Sadhu for his bug report.

Comments, Improvements, Contact:
Ken-Ichi Ishikawa