forked from MersenneTwister-Lab/TinyMT
-
Notifications
You must be signed in to change notification settings - Fork 0
Tiny Mersenne Twister
License
Ben1524/TinyMT
Folders and files
| Name | Name | Last commit message | Last commit date | |
|---|---|---|---|---|
Repository files navigation
<?xml version="1.0" encoding="UTF-8" ?> <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> <html xmlns="http://www.w3.org/1999/xhtml"> <head> <meta http-equiv="Content-Type" content="text/html" /> <meta name="keywords" content="tiny mt" /> <title>Tiny Mersenne Twister (tinyMT)</title> <style type="text/css"> TABLE.numeric TD {text-align:right} DD.gray {color:gray} body {margin-right:10%;margin-left:10%} </style> </head> <body> <h2>Tiny Mersenne Twister</h2> <h2>READ ME FIRST</h2> <p> There are two kinds of programs in this archive file. One is <strong>tinymt</strong> and another is <strong>tinymtdc</strong>. Tinymt is pseudorandom number generator, tinymtdc is parameter generator for tinymt. </p> <h2>tinymt</h2> <p> tinymt is small-sized pseudorandom number generator, compared with Mersenne Twister or WELL RNG. tinymt32 uses 16 bytes for its internal state vector and 12 bytes for its parameters, and tinymt64 uses 16 bytes for its internal state vector and 16 bytes for its parameters. Pseudorandom number sequences generated by tinymt has a period of 2<sup>127</sup>-1. </p> <ul> <li>There are two types of tinymt, tinymt32 and tinymt64. tinymt32 outputs 32-bit unsigned integers and single precision floating point numbers. On the other hand, tinymt64 outputs 64-bit unsigned integers and double precision floating point numbers. </li> <li>tinymt is not designed for special hardware. It will run on many hardware because of its small size. </li> <li>tinymt generates pseudorandom numbers using two functions, state transition function and output function. The state transition function is an F<sub>2</sub>-linear function whose characteristic polynomial is irreducible and is degree 127. The output function is not F<sub>2</sub>-linear, but almost F<sub>2</sub>-linear. Almost all of operations in the output function is F<sub>2</sub>-linear, but one operation is not F<sub>2</sub>-linear, which is addition in mod 2<sup>32</sup> or mod 2<sup>64</sup> instead of F<sub>2</sub> vector addition. </li> <li> Tinymt passes Bigcrush test suite of TESTU01, which is one of the severest tests against pseudorandom number generators. To be precise, We used 10 parameter sets of tinymt32, and used 10 seeds for each parameters, so we tested total 100 sequences using Bigcrush test suite. Some sequences fails one or two tests in the test suite, but the test suite has 160 tests, even the true random sequence will possibly fail in some tests. We checked the test that tinymt failed, and we can say that tinymt passed Bigcrush test suite. </li> <li> However the dimension of equidistribution is defined only when the state transition function and the output function are both linear, theoretical upper bound is calculated from the size of internal state vector, the dimension of equidistribution of 32-bit outputs of tinymt32 will be smaller than 4. This is much smaller than 624 of Mersenne Twister 19937. </li> <li> Tinymt is not designed for the purpose that it will take place of Mersenne Twister. Instead, it is designed for the purpose that it can be used where Mersenne Twister or other generators are difficult to be used because of their large internal state size. Tinymt is pretty well generator as far as its small internal state allows. </li> </ul> <h3>Requirement</h3> <p>tinymt is written in C language, and it uses stdint.h and inttypes.h of c99. </p> <ul> <li>gcc supports c99, use std=c99 option.</li> <li>Visual Studio C/C++ does not support c99, but you can get stdint.h and inttypes.h for Visual Studio from <a href="http://code.google.com/p/msinttypes/">msinttypes</a> in Google code. </li> </ul> <h3>Compile and check</h3> <ol> <li><b>cd tinymt</b></li> <li><b>make all</b></li> <li>Executable file check32 and check64 are made</li> <li>To check these programs: <blockquote> check32 8f7011ee fc78ff1f 3793fdff > tmp32.txt<br/> diff tmp32.txt check32.out.txt<br/> check64 fa051f40 ffd0fff4 58d02ffeffbfffbc > tmp64.txt<br/> diff tmp64.txt check64.out.txt </blockquote> O.K. if diff does not show differences</li> </ol> <h2>tinymtdc</h2> <p>tinymtdc is a parameter generator for tinymt. tinymtdc has an ability to generate more than 2<sup>16</sup> parameter sets per <b>ID</b> which is specified by users.</p> <ul> <li>There are two types of tinymtdc: tinymt32dc creates parameter sets for tinymt32, and tinymt64dc creates those for tinymt64.</li> <li>tinymtdc generates specified number of parameters for each ID. Maximum number of parameters for each id will be less than 2<sup>28</sup>.</li> <li>The characteristic polynomials of tinymt using parameter set generated by tinymtdc is different when ID used by tinymtdc is different.</li> </ul> <h3>Required Library</h3> <p>tinymtdc is written in C++ language using template features.</p> <ul> <li>Victor Shoup's <a href="http://shoup.net/ntl/"> NTL: A Library for doing Number Theory</a>.</li> <li><a href="http://www.boost.org/">C++ TR1 Libraries</a>. (g++ ver. 4.0 or later)</li> <li>(Only g++ 4.2.1 and icc 11.1 are tested)</li> </ul> <h3>Compile</h3> <ol> <li>change directory to <b>dc/src</b></li> <li><b>make all</b></li> <li>tinymt32dc, tinymt64dc and getid are created</li> </ol> <h3>Programs and usage</h3> <dl> <dt> tinymt32dc [-v] [-c count] [-s seed_string] [-f outputfile] ID<br/> tinymt64dc [-v] [-c count] [-s seed_string] [-f outputfile] ID </dt> <dd>These two programs create parameter sets for tinymt32 and tinymt64. <ul> <li>argument (required)<br/> <dl> <dt>ID</dt> <dd>ID should be a decimal number such that 0 <= ID < 2<sup>32</sup><br/> For different ID's, the generated random number sequences are highly independent. (Mathematically saying, the characteristic polynomials of the recursion are co-prime to each other.) </dd> </dl> </li> <li>arguments (optional)<br/> <dl> <dt>-v</dt> <dd>Verbose mode for debug. Do not use this.</dd> <dt>-c count</dt> <dd>specify number of parameter sets to output. If omitted, outputs one parameter set. ID is not counted up. A internal counter is updated and parameter sets are outputted. When ID or the internal counter is changed, the characteristic polynomial of state transition function will be changed.</dd> <dt>-a</dt> <dd>parameter sets are outputted as many as possible. if <b>-a</b> is specified <b>-c</b> is ignored.</dd> <dt>-s seq</dt> <dd>set the internal counter to be <b>seq</b> if omitted, max value is set.</dd> <dt>-m max-defect</dt> <dd>set the max value of intermediate evaluation value of tinymtdc, which is called total dimension defect. Parameter sets whose total dimension defect greater than <b>max-defect</b> are discarded. If omitted, no parameter sets are discarded by intermediate evaluation value. If 0 is specified, parameter sets which get the best intermediate evaluation value are only outputted. </dd> <dt>-f filename</dt> <dd>specify output file name. If omitted, standard output stream is used. </dd> </dl> </li> </ul> </dd> <dt>getid -b 32|64 mat1 mat2 <br/> getid -b 32|64 -r id seq </dt> <dd> This program calculates ID and the internal counter from parameter sets of tinymtdc. <b>-b</b> option is used to distinguish parameters for tinymt32 or tinymt64. If omitted -b 32 is assumed. When <b>-r</b> is specified, the program calculates mat1 and mat2.<br/> Next dialogue shows reproducing last output of tinymt32dc using getid and -s option. <blockquote> $ tail -1 tinymt32dc.0.20.txt<br/> 9443129baa73b98c7b097ab82c074d03,32,0,65980cb3,eb38facf, cc3b75ff,59,0<br/> $ ./getid 65980cb3 eb38facf<br/> id:0(0x0)<br/> seq:2147482983(0x7ffffd67)<br/> $ ./tinymt32dc -s 2147482983 0<br/> # charactristic, type, id, mat1, mat2, tmat, weight, delta<br/> 9443129baa73b98c7b097ab82c074d03,32,0,65980cb3,eb38facf,cc3b75ff,59,0 </blockquote> </dd> </dl> <h3>output format of tinymtdc</h3> <p>output of tinymtdc is Comma Separated Value. Here we explain each column. </p> <table border="1"> <tr> <th>Column or Row</th><th>Description</th> </tr> <tr> <td>The first row</td> <td> <pre># charactristic, type, id, mat1, mat2, tmat1, weight, delta</pre> The first row is always same as above. Each column of the row shows title of columns of following rows.</td> </tr> <tr> <td>1st column: charactristic</td> <td>The first column shows the characteristic polynomial of the state transition function. In tinymt's case, the characteristic polynomial is an irreducible polynomial of degree 127, and all of its coefficients are 0 or 1. Only coefficients are showed as hexadecimal number by descending order, i.e. the highest degree comes first. The first hexadecimal number is greater than or equals to 8, because its degree is 127, and the last hexadecimal number is odd, because irreducible polynomial (over F<sub>2</sub>) has constant term 1. </td> </tr> <tr> <td>2nd column: type</td> <td>The second column shows whether this parameter set is for tinymt32 or tinymt64. </td> </tr> <tr> <td>3rd column: id</td> <td>Third column is id user specified in command line. </td> </tr> <tr> <td>4th column: mat1</td> <td>The fourth column shows <b>mat1</b> parameter. This column is showed as a hexadecimal number. </td> </tr> <tr> <td>5th column: mat2</td> <td>The fifth column shows <b>mat2</b> parameter. This column is showed as a hexadecimal number. The parameters <b>mat1</b> and <b>mat2</b> determines the state transition function of the generator. </td> </tr> <tr> <td>6th column: tmat</td> <td>The sixth column shows <b>tmat</b> parameter. This column is showed as a hexadecimal number. The parameter <b>tmat</b> determines the output function of the generator. </td> </tr> <tr> <td>7th column: weight</td> <td>The seventh column shows Hamming weight of the characteristic polynomial. The weight is said to be nice when it is not far from half of the degree of the characteristic polynomial. </td> </tr> <tr> <td>8th column: delta</td> <td>The eighth column shows the intermediate evaluation value of tinymtdc. 0 is the best. tinymtdc select the parameter <b>tmat</b> so that delta gets to small. </td> </tr> </table> <h2>LICENSE</h2> <pre> Copyright (c) 2011 Mutsuo Saito, Makoto Matsumoto, Hiroshima University and The 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. </pre> </body> </html>
About
Tiny Mersenne Twister
Resources
License
Stars
Watchers
Forks
Releases
No releases published
Packages 0
No packages published
Languages
- C++ 69.0%
- C 22.3%
- HTML 6.4%
- Makefile 2.2%
- Shell 0.1%