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
|
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\
* This is GNU Go, a Go program. Contact gnugo@gnu.org, or see *
* http://www.gnu.org/software/gnugo/ for more information. *
* *
* Copyright 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, *
* 2008 and 2009 by the Free Software Foundation. *
* *
* This program is free software; you can redistribute it and/or *
* modify it under the terms of the GNU General Public License as *
* published by the Free Software Foundation - version 3 or *
* (at your option) any later version. *
* *
* This program is distributed in the hope that it will be useful, *
* but WITHOUT ANY WARRANTY; without even the implied warranty of *
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
* GNU General Public License in file COPYING for more details. *
* *
* You should have received a copy of the GNU General Public *
* License along with this program; if not, write to the Free *
* Software Foundation, Inc., 51 Franklin Street, Fifth Floor, *
* Boston, MA 02111, USA. *
\* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
#include <limits.h>
#include <assert.h>
#include "random.h"
/* This is an implementation of the TGFSR (twisted generalized
* feedback shift register) random number generator TT800, which was
* published in:
*
* Matsumoto, M. and Kurita, Y.: Twisted GFSR generators II.
* ACM Transactions on Modeling and Computer Simulations,
* Vol 4, No. 3, July 1994, pp 254--266
*
* The generator produces a pseudo-random sequence of 32 bit integers
* with period 2^800 - 1 and is reported to have excellent
* equidistribution properties, as well as being fast.
*/
/* Algorithm parameters. */
#define N 25
static const int m = 7;
static const int s = 7;
static const int t = 15;
static const unsigned int a = 0x8ebfd028U;
static const unsigned int b = 0x2b5b2500U;
static const unsigned int c = 0xdb8b0000U;
/* Global state for the random number generator. */
static unsigned int x[N];
static int k;
/* Set when properly seeded. */
static int rand_initialized = 0;
/* We use this to detect whether unsigned ints are bigger than 32
* bits. If they are we need to clear higher order bits, otherwise we
* can optimize by not doing the masking.
*/
#define BIG_UINT (UINT_MAX > 0xffffffffU)
/* Iterate the TGFSR once to get a new state which can be used to
* produce another 25 random numbers.
*/
static void
iterate_tgfsr(void)
{
int i;
for (i = 0; i < N - m; i++)
x[i] = x[i + m] ^ (x[i] >> 1) ^ ((x[i] & 1) ? a : 0);
for (; i < N; i++)
x[i] = x[i + m - N] ^ (x[i] >> 1) ^ ((x[i] & 1) ? a : 0);
}
/* Produce a random number from the next word of the internal state.
*/
static unsigned int
next_rand(void)
{
int y;
if (!rand_initialized) {
assert(rand_initialized); /* Abort. */
gg_srand(1); /* Initialize silently if assertions disabled. */
}
if (++k == N) {
iterate_tgfsr();
k = 0;
}
y = x[k] ^ ((x[k] << s) & b);
y ^= ((y << t) & c);
#if BIG_UINT
y &= 0xffffffffU;
#endif
return y;
}
/* Seed the random number generator. The first word of the internal
* state is set by the (lower) 32 bits of seed. The remaining 24 words
* are generated from the first one by a linear congruential pseudo
* random generator.
*
* FIXME: The constants in this generator has not been checked, but
* since they only are used to produce a very short sequence, which in
* turn only is a seed to a stronger generator, it probably doesn't
* matter much.
*/
void
gg_srand(unsigned int seed)
{
int i;
for (i = 0; i < N; i++) {
#if BIG_UINT
seed &= 0xffffffffU;
#endif
x[i] = seed;
seed *= 1313;
seed += 88897;
}
k = N-1; /* Force an immediate iteration of the TGFSR. */
rand_initialized = 1;
}
/* Obtain one random integer value in the interval [0, 2^31-1].
*/
int
gg_rand(void)
{
return (int) (next_rand() & 0x7fffffff);
}
/* Obtain one random integer value in the interval [0, 2^32-1].
*/
unsigned int
gg_urand(void)
{
return next_rand();
}
/* Obtain one random floating point value in the half open interval
* [0.0, 1.0).
*
* If the value is converted to a floating point type with less than
* 32 bits mantissa (or if the double type should happen to be
* unusually short), the value 1.0 may be attained.
*/
double
gg_drand(void)
{
return next_rand() * 2.328306436538696e-10;
}
/* Retrieve the internal state of the random generator.
*/
void
gg_get_rand_state(struct gg_rand_state *state)
{
int i;
for (i = 0; i < N; i++)
state->x[i] = x[i];
state->k = k;
}
/* Set the internal state of the random number generator.
*/
void
gg_set_rand_state(struct gg_rand_state *state)
{
int i;
for (i = 0; i < N; i++)
x[i] = state->x[i];
k = state->k;
}
/*
* Local Variables:
* tab-width: 8
* c-basic-offset: 2
* End:
*/
|
