-
Notifications
You must be signed in to change notification settings - Fork 36
/
readme.html
365 lines (349 loc) · 13.7 KB
/
readme.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
<?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 a pseudorandom number
generator, while TinyMTDC is a parameter-set generator for TinyMT.
</p>
<h2>TinyMT</h2>
<p>
TinyMT is a 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 a particular hardware. It will run on
many types of hardware, because of its small size.
</li>
<li>TinyMT generates pseudorandom numbers using two functions:
a state transition function and an output function.
The state transition function is an F<sub>2</sub>-linear
function whose characteristic polynomial is irreducible of degree 127.
The output function is not F<sub>2</sub>-linear,
but almost F<sub>2</sub>-linear. The output function is composed
from several F<sub>2</sub>-linear functions, except for one
non F<sub>2</sub>-linear operation, namely an addition as integers
modulo 2<sup>32</sup> (or mod 2<sup>64</sup> for tinymt64) which
replaces an 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 in (with parameter sets and seeds), and we
could not find a systematic deviation when seeds are changed.
Thus, we conclude that TinyMT passed the Bigcrush test suite.
</li>
<li>
There is a notion of the dimension of equidistribution to v-bit
accuracy (k(v)). High values of k(v) shows high-dimensional
uniformity up to the v-bit precision. In the case of TinyMT,
we can not compute these values because of the non-linearity
of the output function. Instead, we compute k(v)s for a
linearized output function, and search for parameters with
high values of k(v). They are close to the theoretical
upper bound (dimension of the internal space / v), but far
smaller than Mersenne Twister 19937. For example, k(32) for
tinymt32 is smaller than 4, while k(32) for Mersenne Twister 19937
is 623.
</li>
<li>
TinyMT is not designed to replace Mersenne Twister.
In some applications, namely, hardware implementation or highly
parallel environment, the large state size (19937 bits) of
Mersenne Twister may be an obstruction for implementation.
TinyMT is designed for such situation, with small state size
and good randomness for that size of internal state.
</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.
A user specifies an ID and the number of sets of parameters to be
generated. TinyMTDC can generate more than 2<sup>16</sup> distinct set
of parameters (with ID embedded) to be used as parameters in TinyMT.
</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 the number of sets of parameters to
generate. If omitted, outputs one set of parameters.
When TinyMTDC is called with <b>-c</b>, an internal
counter is updated and parameter set are outputted.
When ID or the internal counter is distinct, the
characteristic polynomial of the state transition
function is assured to be distinct. Namely, different
pairs (ID, internal counter) yields different
characteristic polynomials.
</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, its max value is set.</dd>
<dt>-m max-defect</dt>
<dd>
the defect at v-bit accuracy means the gap between the
theoretical upper bound and the realized k(v). The total
dimension defect is the sum of these values for v=1 to 32
(for tinymt32) and for v=1 to 64 (for tinymt64).
If its value is smaller, then the generator is closer to
the theoretical upper bound. This option set the max
allowable value of this total dimension defect.
Parameter sets whose total dimension defect is greater
than max-defect are discarded. If
omitted, no parameter sets are discarded. If 0 is specified,
parameter sets with no defect at any v-bit accuracy will be
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 the 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, conversely, the program calculates
the parameters mat1 and mat2 from the ID and the internal counter.<br/>
This program may be used to resume parameter-set generation: from
the last (mat1, mat2) generated by TinyMTDC, getid computes the
corresponding (ID, seq). Then TinyMTDC with -s option for the
value (seq-1) will resume the previous parameter-set generation,
as follows.
<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 the 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 its coefficients are 0 or 1.
The corresponding hexadecimal number to the coefficients of
the polynomial (by descending order, i.e. the constant term comes
as LSB) is shown. The first digit of the 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 the ID specified by user, in command line.
</td>
</tr>
<tr>
<td>4th column: mat1</td>
<td>The fourth column shows <b>mat1</b> parameter
in the hexadecimal notation.
</td>
</tr>
<tr>
<td>5th column: mat2</td>
<td>The fifth column shows <b>mat2</b> parameter in
the hexadecimal notation.
The parameters <b>mat1</b> and <b>mat2</b> determine
the state transition function of the generator.
</td>
</tr>
<tr>
<td>6th column: tmat</td>
<td>The sixth column shows <b>tmat</b> parameter
in the hexadecimal notation.
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. A thumb-nail rule says that the weight value not far
from half of the degree of the characteristic polynomial is
preferable.
</td>
</tr>
<tr>
<td>8th column: delta</td>
<td>The eighth column shows the total dimension defect, which
measures the gap from the theoretical upper bounds on the
dimensions of equidistribution.
0 is the best. TinyMTDC selects the parameter
<b>tmat</b> for which delta is 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>