Mersenne Twister for Graphic Processors (MTGP) Dynamic Creator (DC)

READ ME FIRST

The program in this archive is Mersenne Twister for Graphic Processors Dynamic Creator (MTGPDC).

MTGPDC is written in C++ language using templates.
MTGPDC outputs parameter sets for MTGP in Comma Separated Values format.
MTGPDC runs on CPUs not on GPUs.

Requirement

MTGP requires three libraries to be compiled.

Victor Shoup's NTL: A Library for doing Number Theory.
C++ TR1 Libraries. (g++ ver. 4.0 or later)
Boost C++ Libraries.
OpenSSL.

And MTGP requires UNIX like Operating System with GNU C++ compiler(g++).

Compile

change directory to src.
edit Makefile and uncomment some lines.
type make all.
mtgp32dc and mtgp64dc are created.

change directory to src/migration-tools.
edit Makefile and uncomment some lines.
type make all.
migration32 is created.

Programs and Usage

mtgp32dc [-v] [-c count] [-s seed_string] [-f outputfile] mexp ID mtgp64dc [-v] [-c count] [-s seed_string] [-f outputfile] mexp ID

The programs generate parameter sets for MTGP32 or MTGP64.

required

mexp

mexp is one of 3217, 4423, 11213, 23209 and 44497.

mexp 110503 and 216091 are allowed now, but it takes too many time to calculate these parameters. And these large mexps use large internal state which may not be kept in the shared memories of GPUs. And searching these large mexps is not tested. But someone may need these large mexps. Use these large mexps at your own risk.

ID

ID is a decimal integer such that 0 <= ID < 2³².
optional

-v

verbose mode. MTGP outputs parameters, calculation time, etc. The messages are sent to standard output.

-c count

count is a number of the parameter sets to output. If omitted, one is assumed. ID is automatically incremented.

-s seed_string

seed_string is a ASCII character string used to initialize the internal random number generator. If omitted, PID and clock are concatenated and used as seed_string.

-f filename

filename of output parameters. If omitted, the parameters are sent to standard output.

check-sha-uniq.sh file file ...

The program checks if SHA1 of each parameter sets is different. The program uses UNIX utilities grep, cut, sort and wc. It outputs the number of unique SHA1s in the files which is outputs of mtgp32dc or mtgp64dc.

required

file

outputs of mtgp32dc or mtgp64dc

fast-param.awk file file ...

The program converts the output of mtgp32dc or mtgp64dc to the constant table of C language.

migration32 file

The program gets the output file of mtgp32dc ver.0.2 and recalculates the tempering parameters using the algorithm of mtgp32dc ver.0.3. The output is printed to stdout.

Users may need to change check-sha-uniq.sh and fast-param.awk to fit to their operating systems.

Format of Outputs

MTGP outpus Comma Separated Values format. Here is the format of outpus.

Column or Row	Description
The first row	# sha1, mexp, type, id, pos, sh1, sh2, tbl_0, tbl_1, tbl_2, tbl_3,tmp_0, tmp_1, tmp_2, tmp_3, mask, weight, delta The first row is as above. It starts with '#', so it's easy to be skipped by the script programs such as fast-param.awk or check-sha-uniq.sh. The first row shows title of several columns, but not all columns.
1st column SHA1	1st column is SHA1 digest of the characteristic polynomial of the state transition function of the generator. This column start with " and end with ".
2nd column MEXP	2nd column is Mersenne Exponent which is exponent part of Mersenne Prime. MTGP of the Mersenne Exponent p has a period of 2^p-1.
3rd column type	3rd column shows typename of integers in C99. mtgp32dc always puts uint32_t here, and mtgp64dc always put uint64_t.
4th column ID	4th column shows ID which users specified directly or indirectly by command line of MTGP.
5th column pos	5th column shows the pick-up position of the generator.
6th and 7th columns sh1 and sh2	For mtgp32dc, sh1 and sh2 are fixed to 13 and 4 respectively. And for mtgp64dc, sh1 and sh2 are fixed to 11 and 4 respectively.
8th -- 11th columns tbl_1 to tbl_4	recursion parameters. hexadecimal format numbers.
12th -- 15th columns tmp_1 to tmp_4	tempering parameters. hexadecimal format numbers.
16th column mask	the bit mask pattern. Let r = ceil(mexp / bit_size) * bit_size - mexp. r LSBs of the mask is set to zero, and other bits are set to one.
17th column weight	Hamming weight of the characteristic polynomial. In other words, the number of non-zero term of the characteristic polynomial.
18th column delta	Total dimension defect of the generator.
19th to 34th columns	redundant data. the recursion parameters expanded to a look-up table.
35th to 50th columns	redundant data. The tempering parameters expanded to a look-up table.
51th to 66th columns	redundant data. A look-up table which has the tempering parameters shifted and or-ed with a constant for tempering and converting into float.

CPU Time (sec.) consumed for searching

CPU Time (sec.) consumed for searching 32bit MTGP parameter sets on OS X 10.6 MacPro Xeon 5500 2.26GHz.
MEXP		3217	4423	11213	23209	44497
samples		3000	3000	1500	1500	750
Recursion parameter set search	min	0	0	4	24	143
	max	90	191	3318	10146	49987
	average	11.2	25.0	338.1	1404.7	6529.4
Tempering parameter set search	min	10	15	76	379	946
	max	25	40	253	1040	3893
	average	21.7	34.1	213.7	910.0	3236.4

CPU Time (sec.) consumed for searching 64bit MTGP parameter sets on CentOS 5.3 Xeon 5570 2.93GHz.
MEXP		3217	4423	11213	23209	44497
samples		1500	1500	3000	1500	750
Recursion parameter set search	min	0	0	3	15	104
	max	42	128	1482	3187	22578
	average	5.5	12.9	147.3	410.7	3332.8
Tempering parameter set search	min	4	7	30	102	328
	max	10	16	85	255	864
	average	8.5	13.1	60.1	219.4	730.8

LICENSE

Copyright (c) 2010 Mutsuo Saito, Makoto Matsumoto and Hiroshima
University. All rights reserved.
Copyright (c) 2011 Mutsuo Saito, Makoto Matsumoto, Hiroshima
University and University of Tokyo. 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 Hiroshima University 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
OWNER 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.