Commit | Line | Data |
---|---|---|
7eeb782e AT |
1 | /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\ |
2 | * This is GNU Go, a Go program. Contact gnugo@gnu.org, or see * | |
3 | * http://www.gnu.org/software/gnugo/ for more information. * | |
4 | * * | |
5 | * Copyright 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, * | |
6 | * 2008 and 2009 by the Free Software Foundation. * | |
7 | * * | |
8 | * This program is free software; you can redistribute it and/or * | |
9 | * modify it under the terms of the GNU General Public License as * | |
10 | * published by the Free Software Foundation - version 3 or * | |
11 | * (at your option) any later version. * | |
12 | * * | |
13 | * This program is distributed in the hope that it will be useful, * | |
14 | * but WITHOUT ANY WARRANTY; without even the implied warranty of * | |
15 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * | |
16 | * GNU General Public License in file COPYING for more details. * | |
17 | * * | |
18 | * You should have received a copy of the GNU General Public * | |
19 | * License along with this program; if not, write to the Free * | |
20 | * Software Foundation, Inc., 51 Franklin Street, Fifth Floor, * | |
21 | * Boston, MA 02111, USA. * | |
22 | \* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ | |
23 | ||
24 | #include <limits.h> | |
25 | #include <assert.h> | |
26 | ||
27 | #include "random.h" | |
28 | ||
29 | /* This is an implementation of the TGFSR (twisted generalized | |
30 | * feedback shift register) random number generator TT800, which was | |
31 | * published in: | |
32 | * | |
33 | * Matsumoto, M. and Kurita, Y.: Twisted GFSR generators II. | |
34 | * ACM Transactions on Modeling and Computer Simulations, | |
35 | * Vol 4, No. 3, July 1994, pp 254--266 | |
36 | * | |
37 | * The generator produces a pseudo-random sequence of 32 bit integers | |
38 | * with period 2^800 - 1 and is reported to have excellent | |
39 | * equidistribution properties, as well as being fast. | |
40 | */ | |
41 | ||
42 | ||
43 | /* Algorithm parameters. */ | |
44 | #define N 25 | |
45 | static const int m = 7; | |
46 | static const int s = 7; | |
47 | static const int t = 15; | |
48 | static const unsigned int a = 0x8ebfd028U; | |
49 | static const unsigned int b = 0x2b5b2500U; | |
50 | static const unsigned int c = 0xdb8b0000U; | |
51 | ||
52 | ||
53 | /* Global state for the random number generator. */ | |
54 | static unsigned int x[N]; | |
55 | static int k; | |
56 | ||
57 | ||
58 | /* Set when properly seeded. */ | |
59 | static int rand_initialized = 0; | |
60 | ||
61 | /* We use this to detect whether unsigned ints are bigger than 32 | |
62 | * bits. If they are we need to clear higher order bits, otherwise we | |
63 | * can optimize by not doing the masking. | |
64 | */ | |
65 | #define BIG_UINT (UINT_MAX > 0xffffffffU) | |
66 | ||
67 | ||
68 | /* Iterate the TGFSR once to get a new state which can be used to | |
69 | * produce another 25 random numbers. | |
70 | */ | |
71 | ||
72 | static void | |
73 | iterate_tgfsr(void) | |
74 | { | |
75 | int i; | |
76 | for (i = 0; i < N - m; i++) | |
77 | x[i] = x[i + m] ^ (x[i] >> 1) ^ ((x[i] & 1) ? a : 0); | |
78 | for (; i < N; i++) | |
79 | x[i] = x[i + m - N] ^ (x[i] >> 1) ^ ((x[i] & 1) ? a : 0); | |
80 | } | |
81 | ||
82 | ||
83 | /* Produce a random number from the next word of the internal state. | |
84 | */ | |
85 | ||
86 | static unsigned int | |
87 | next_rand(void) | |
88 | { | |
89 | int y; | |
90 | if (!rand_initialized) { | |
91 | assert(rand_initialized); /* Abort. */ | |
92 | gg_srand(1); /* Initialize silently if assertions disabled. */ | |
93 | } | |
94 | if (++k == N) { | |
95 | iterate_tgfsr(); | |
96 | k = 0; | |
97 | } | |
98 | y = x[k] ^ ((x[k] << s) & b); | |
99 | y ^= ((y << t) & c); | |
100 | #if BIG_UINT | |
101 | y &= 0xffffffffU; | |
102 | #endif | |
103 | return y; | |
104 | } | |
105 | ||
106 | ||
107 | /* Seed the random number generator. The first word of the internal | |
108 | * state is set by the (lower) 32 bits of seed. The remaining 24 words | |
109 | * are generated from the first one by a linear congruential pseudo | |
110 | * random generator. | |
111 | * | |
112 | * FIXME: The constants in this generator has not been checked, but | |
113 | * since they only are used to produce a very short sequence, which in | |
114 | * turn only is a seed to a stronger generator, it probably doesn't | |
115 | * matter much. | |
116 | */ | |
117 | ||
118 | void | |
119 | gg_srand(unsigned int seed) | |
120 | { | |
121 | int i; | |
122 | for (i = 0; i < N; i++) { | |
123 | #if BIG_UINT | |
124 | seed &= 0xffffffffU; | |
125 | #endif | |
126 | x[i] = seed; | |
127 | seed *= 1313; | |
128 | seed += 88897; | |
129 | } | |
130 | k = N-1; /* Force an immediate iteration of the TGFSR. */ | |
131 | rand_initialized = 1; | |
132 | } | |
133 | ||
134 | ||
135 | /* Obtain one random integer value in the interval [0, 2^31-1]. | |
136 | */ | |
137 | ||
138 | int | |
139 | gg_rand(void) | |
140 | { | |
141 | return (int) (next_rand() & 0x7fffffff); | |
142 | } | |
143 | ||
144 | ||
145 | /* Obtain one random integer value in the interval [0, 2^32-1]. | |
146 | */ | |
147 | ||
148 | unsigned int | |
149 | gg_urand(void) | |
150 | { | |
151 | return next_rand(); | |
152 | } | |
153 | ||
154 | ||
155 | /* Obtain one random floating point value in the half open interval | |
156 | * [0.0, 1.0). | |
157 | * | |
158 | * If the value is converted to a floating point type with less than | |
159 | * 32 bits mantissa (or if the double type should happen to be | |
160 | * unusually short), the value 1.0 may be attained. | |
161 | */ | |
162 | ||
163 | double | |
164 | gg_drand(void) | |
165 | { | |
166 | return next_rand() * 2.328306436538696e-10; | |
167 | } | |
168 | ||
169 | ||
170 | /* Retrieve the internal state of the random generator. | |
171 | */ | |
172 | ||
173 | void | |
174 | gg_get_rand_state(struct gg_rand_state *state) | |
175 | { | |
176 | int i; | |
177 | for (i = 0; i < N; i++) | |
178 | state->x[i] = x[i]; | |
179 | state->k = k; | |
180 | } | |
181 | ||
182 | ||
183 | /* Set the internal state of the random number generator. | |
184 | */ | |
185 | ||
186 | void | |
187 | gg_set_rand_state(struct gg_rand_state *state) | |
188 | { | |
189 | int i; | |
190 | for (i = 0; i < N; i++) | |
191 | x[i] = state->x[i]; | |
192 | k = state->k; | |
193 | } | |
194 | ||
195 | ||
196 | /* | |
197 | * Local Variables: | |
198 | * tab-width: 8 | |
199 | * c-basic-offset: 2 | |
200 | * End: | |
201 | */ |