## 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

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

1. change directory to src/migration-tools.
2. edit Makefile and uncomment some lines.
3. type make all.
4. 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 < 232.
  - 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 2p-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.