Debian Codegraph @

ext/mt-random/mt-random.c

raw
1 /*
2 * mt-random.c - implements MT19937 random number generation algorithm
3 *
4 * Mersenne Twister algorithm invented by Makoto Matsumoto & Takuji Nishimura.
5 * http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html
6 * This code is based on mt18837ar.c (2002/1/16). It is released under
7 * BSD license.
8 * I modified the code in the following parts.
9 * - make it modular, esp., all the state information is kept in
10 * the allocated memory for random number generator object.
11 * - changed the names of the functions
12 * - added stuff to make it as a Gauche extension module.
13 *
14 * The original copyright notice follows.
15 */
16 /*
17 A C-program for MT19937, with initialization improved 2002/1/26.
18 Coded by Takuji Nishimura and Makoto Matsumoto.
19
20 Before using, initialize the state by using init_genrand(seed)
21 or init_by_array(init_key, key_length).
22
23 Copyright (C) 1997 - 2002, Makoto Matsumoto and Takuji Nishimura,
24 All rights reserved.
25
26 Redistribution and use in source and binary forms, with or without
27 modification, are permitted provided that the following conditions
28 are met:
29
30 1. Redistributions of source code must retain the above copyright
31 notice, this list of conditions and the following disclaimer.
32
33 2. Redistributions in binary form must reproduce the above copyright
34 notice, this list of conditions and the following disclaimer in the
35 documentation and/or other materials provided with the distribution.
36
37 3. The names of its contributors may not be used to endorse or promote
38 products derived from this software without specific prior written
39 permission.
40
41 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
42 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
43 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
44 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
45 CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
46 EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
47 PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
48 PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
49 LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
50 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
51 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
52
53
54 Any feedback is very welcome.
55 http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html
56 email: m-mat @ math.sci.hiroshima-u.ac.jp (remove space)
57 */
58
59 #include <math.h>
60 #include "mt-random.h"
61
62 /* Period parameters */
63 #define M 397
64 #define MATRIX_A 0x9908b0dfUL /* constant vector a */
65 #define UPPER_MASK 0x80000000UL /* most significant w-r bits */
66 #define LOWER_MASK 0x7fffffffUL /* least significant r bits */
67
68 /* initializes mt[N] with a seed. caller needs to hold lock */
69 static void init_by_ui(ScmMersenneTwister *mt, unsigned long s)
70 {
71 int mti;
72 mt->mt[0]= s & 0xffffffffUL;
73 for (mti=1; mti<N; mti++) {
74 mt->mt[mti] =
75 (1812433253UL * (mt->mt[mti-1] ^ (mt->mt[mti-1] >> 30)) + mti);
76 /* See Knuth TAOCP Vol2. 3rd Ed. P.106 for multiplier. */
77 /* In the previous versions, MSBs of the seed affect */
78 /* only MSBs of the array mt[]. */
79 /* 2002/01/09 modified by Makoto Matsumoto */
80 mt->mt[mti] &= 0xffffffffUL;
81 /* for >32 bit machines */
82 }
83 mt->mti = mti;
84 mt->seed = Scm_MakeIntegerU(s);
85 }
86
87 /* initialize by an array with array-length */
88 /* init_key is the array for initializing keys */
89 /* key_length is its length */
90 /* caller needs to hold lock */
91 static void init_by_array(ScmMersenneTwister *mt,
92 int32_t init_key[],
93 unsigned long key_length)
94 {
95 int i, j, k;
96 init_by_ui(mt, 19650218UL);
97 i=1; j=0;
98 k = (N>key_length ? N : key_length);
99 for (; k; k--) {
100 mt->mt[i] = (mt->mt[i] ^ ((mt->mt[i-1] ^ (mt->mt[i-1] >> 30)) * 1664525UL))
101 + init_key[j] + j; /* non linear */
102 mt->mt[i] &= 0xffffffffUL; /* for WORDSIZE > 32 machines */
103 i++; j++;
104 if (i>=N) { mt->mt[0] = mt->mt[N-1]; i=1; }
105 if (j>=(int)key_length) j=0;
106 }
107 for (k=N-1; k; k--) {
108 mt->mt[i] = (mt->mt[i] ^ ((mt->mt[i-1] ^ (mt->mt[i-1] >> 30)) * 1566083941UL))
109 - i; /* non linear */
110 mt->mt[i] &= 0xffffffffUL; /* for WORDSIZE > 32 machines */
111 i++;
112 if (i>=N) { mt->mt[0] = mt->mt[N-1]; i=1; }
113 }
114
115 mt->mt[0] = 0x80000000UL; /* MSB is 1; assuring non-zero initial array */
116 /* NB: We coerce the seed value to u32vector, for the compability of
117 Scheme-level mt-random-set-seed!. */
118 mt->seed = Scm_MakeU32VectorFromArray(key_length, (uint32_t*)init_key);
119 }
120
121 #define LOCK(mt) \
122 do { \
123 if (SCM_MERSENNE_TWISTER_NEED_LOCK(mt)) { \
124 SCM_INTERNAL_MUTEX_LOCK(mt->lock); \
125 } \
126 } while (0)
127
128 #define UNLOCK(mt) \
129 do { \
130 if (SCM_MERSENNE_TWISTER_NEED_LOCK(mt)) { \
131 SCM_INTERNAL_MUTEX_UNLOCK(mt->lock); \
132 } \
133 } while (0)
134
135
136 void Scm_MTSetSeed(ScmMersenneTwister *mt, ScmObj seed)
137 {
138 if (!(SCM_INTP(seed) || SCM_BIGNUMP(seed) || SCM_U32VECTORP(seed))) {
139 Scm_TypeError("random seed", "an exact integer or u32vector", seed);
140 }
141
142 LOCK(mt);
143 if (SCM_INTP(seed)) {
144 /* For the backward compatibility, we only use the lower 32bit. */
145 init_by_ui(mt, (uint32_t)Scm_GetUInteger(seed));
146 } else if (SCM_BIGNUMP(seed)) {
147 #if SIZEOF_LONG == 4
148 init_by_array(mt, (int32_t*)SCM_BIGNUM(seed)->values,
149 (int)SCM_BIGNUM_SIZE(seed));
150 #elif SIZEOF_LONG == 8
151 /* We can't just pass seed->values as (int32_t*), for the result
152 would differ by endianness. */
153 int32_t seedv[SCM_BIGNUM_SIZE(seed)*2];
154 for (size_t i=0; i<SCM_BIGNUM_SIZE(seed); i++) {
155 seedv[i*2] = (int32_t)(SCM_BIGNUM(seed)->values[i]&0xffffffff);
156 seedv[i*2+1] = (int32_t)(SCM_BIGNUM(seed)->values[i]>>32);
157 }
158 init_by_array(mt, seedv, (int)SCM_BIGNUM_SIZE(seed)*2);
159 #else
160 #error "sizeof(long) must be 4 or 8"
161 #endif
162 } else {
163 /* seed must be u32vector */
164 init_by_array(mt, (int32_t*)SCM_U32VECTOR_ELEMENTS(seed),
165 SCM_U32VECTOR_SIZE(seed));
166 }
167 /* NB: mt->seed is set by either init_by_ui or init_by_array. */
168
169 UNLOCK(mt);
170 }
171
172 /* internal. caller holds the lock */
173 static u_long genrand_u32(ScmMersenneTwister *mt)
174 {
175 unsigned long y;
176 int mti = mt->mti;
177 static unsigned long mag01[2]={0x0UL, MATRIX_A};
178 /* mag01[x] = x * MATRIX_A for x=0,1 */
179
180 if (mti >= N) { /* generate N words at one time */
181 int kk;
182
183 if (mti == N+1) { /* if init_by_ui() has not been called, */
184 init_by_ui(mt, 5489UL); /* a default initial seed is used */
185 }
186
187 for (kk=0;kk<N-M;kk++) {
188 y = (mt->mt[kk]&UPPER_MASK)|(mt->mt[kk+1]&LOWER_MASK);
189 mt->mt[kk] = mt->mt[kk+M] ^ (y >> 1) ^ mag01[y & 0x1UL];
190 }
191 for (;kk<N-1;kk++) {
192 y = (mt->mt[kk]&UPPER_MASK)|(mt->mt[kk+1]&LOWER_MASK);
193 mt->mt[kk] = mt->mt[kk+(M-N)] ^ (y >> 1) ^ mag01[y & 0x1UL];
194 }
195 y = (mt->mt[N-1]&UPPER_MASK)|(mt->mt[0]&LOWER_MASK);
196 mt->mt[N-1] = mt->mt[M-1] ^ (y >> 1) ^ mag01[y & 0x1UL];
197
198 mti = 0;
199 }
200
201 y = mt->mt[mti++];
202
203 /* Tempering */
204 y ^= (y >> 11);
205 y ^= (y << 7) & 0x9d2c5680UL;
206 y ^= (y << 15) & 0xefc60000UL;
207 y ^= (y >> 18);
208
209 mt->mti = mti;
210
211 return y;
212 }
213
214 ScmObj Scm_MTGetState(ScmMersenneTwister *mt)
215 {
216 ScmObj v = Scm_MakeU32Vector(N+1, 0);
217 LOCK(mt);
218 for (int i=0; i < N; i++) {
219 SCM_U32VECTOR_ELEMENT(v, i) = mt->mt[i];
220 }
221 SCM_U32VECTOR_ELEMENT(v, N) = mt->mti;
222 UNLOCK(mt);
223 return v;
224 }
225
226 void Scm_MTSetState(ScmMersenneTwister *mt, ScmU32Vector *v)
227 {
228 if (SCM_U32VECTOR_SIZE(v) != N+1) {
229 Scm_Error("u32vector of length %d is required, but got length %d",
230 N+1, SCM_U32VECTOR_SIZE(v));
231 }
232 LOCK(mt);
233 for (int i=0; i < N; i++) {
234 mt->mt[i] = SCM_U32VECTOR_ELEMENT(v, i);
235 }
236 mt->mti = SCM_U32VECTOR_ELEMENT(v, N);
237 UNLOCK(mt);
238 }
239
240
241 /* generates a random number on [0,0xffffffff]-interval */
242 unsigned long Scm_MTGenrandU32(ScmMersenneTwister *mt)
243 {
244 u_long r;
245 LOCK(mt);
246 r = genrand_u32(mt);
247 UNLOCK(mt);
248 return r;
249 }
250
251 /* generates a random number on (0,1) or [0,1) -real-interval */
252 static float genrand_f32(ScmMersenneTwister *mt, int exclude0)
253 {
254 float r;
255 do {
256 r = (float)(genrand_u32(mt)*(1.0/4294967296.0));
257 /* divided by 2^32 */
258 } while (exclude0 && r == 0.0); /*if we get 0.0, try another one. */;
259 return r;
260 }
261
262 float Scm_MTGenrandF32(ScmMersenneTwister *mt, int exclude0)
263 {
264 LOCK(mt);
265 float r = genrand_f32(mt, exclude0);
266 UNLOCK(mt);
267 return r;
268 }
269
270 /* generates a random number on (0,1) or [0,1) with 53-bit resolution*/
271 static double genrand_f64(ScmMersenneTwister *mt, int exclude0)
272 {
273 double r;
274 unsigned long a, b;
275 do {
276 a = genrand_u32(mt)>>5;
277 b = genrand_u32(mt)>>6;
278 r = (a*67108864.0+b)*(1.0/9007199254740992.0);
279 } while (exclude0 && r == 0.0); /*if we get 0.0, try another one. */;
280 return r;
281 }
282
283 double Scm_MTGenrandF64(ScmMersenneTwister *mt, int exclude0)
284 {
285 LOCK(mt);
286 double r = genrand_f64(mt, exclude0);
287 UNLOCK(mt);
288 return r;
289 }
290
291 /*
292 * Generic integer routine for [0, n-1], 0 < n <= 2^32
293 */
294
295 /* if integer N is 2^e, returns e; otherwise, returns -1. */
296 static inline int xlog2(unsigned long n)
297 {
298 #if SIZEOF_LONG == 4
299 # define START_BIT 16
300 # define MAX_BIT 31
301 #else /* assume sizeof(long) == 8 */
302 # define START_BIT 32
303 # define MAX_BIT 63
304 #endif
305 int e = START_BIT;
306 unsigned long m = (1UL<<START_BIT);
307
308 if (n < m) {
309 do {
310 m >>= 1;
311 e--;
312 if (n == m) return e;
313 } while (e >= 0 && n < m);
314 } else if (n > m) {
315 do {
316 m <<= 1;
317 e++;
318 if (n == m) return e;
319 } while (e < MAX_BIT && n > m);
320 } else { /* n == m */
321 return e;
322 }
323 return -1;
324 #undef START_BIT
325 #undef MAX_BIT
326 }
327
328
329 /* generates a random number on [0,n-1], n < 2^32. */
330 static ScmObj genrand_int_small(ScmMersenneTwister *mt, unsigned long n)
331 {
332 int e;
333 unsigned long r;
334 if ((e = xlog2(n)) == 0) {
335 return SCM_MAKE_INT(0);
336 } else if (e > 0) {
337 /* optimize for 2^e case */
338 r = Scm_MTGenrandU32(mt);
339 if (e == 32) return Scm_MakeIntegerFromUI(r);
340 else return Scm_MakeIntegerFromUI(r >> (32-e));
341 } else {
342 double q = floor((double)0xffffffff / (double)n);
343 double qn = q * n;
344 do {
345 r = Scm_MTGenrandU32(mt);
346 } while (r >= qn);
347 return Scm_MakeIntegerFromUI((unsigned long)(r/q));
348 }
349 }
350
351 ScmObj Scm_MTGenrandInt(ScmMersenneTwister *mt, ScmObj n)
352 {
353 if (SCM_INTP(n)) {
354 long m = SCM_INT_VALUE(n);
355 if (m <= 0) goto err;
356 return genrand_int_small(mt, m);
357 }
358 #if SIZEOF_LONG == 4
359 if (SCM_BIGNUMP(n)) {
360 if (SCM_BIGNUM_SIGN(n) <= 0) goto err;
361 if (SCM_BIGNUM_SIZE(n) == 1) {
362 return genrand_int_small(mt, SCM_BIGNUM(n)->values[0]);
363 }
364 if (SCM_BIGNUM_SIZE(n) == 2
365 && SCM_BIGNUM(n)->values[0] == 0
366 && SCM_BIGNUM(n)->values[1] == 1) {
367 return Scm_MakeIntegerFromUI(Scm_MTGenrandU32(mt));
368 }
369 }
370 #endif
371 err:
372 Scm_Error("bad type of argument for n: positive exact integer up to 2^32 is required, but got %S", n);
373 return SCM_UNDEFINED; /*dummy*/
374 }
375
376 ScmObj Scm_MTFillUvector(ScmMersenneTwister *mt, ScmObj v)
377 {
378 if (SCM_U32VECTORP(v)) {
379 LOCK(mt);
380 for (int i = 0; i < SCM_U32VECTOR_SIZE(v); i++) {
381 SCM_U32VECTOR_ELEMENT(v, i) = genrand_u32(mt);
382 }
383 UNLOCK(mt);
384 } else if (SCM_F32VECTORP(v)) {
385 LOCK(mt);
386 for (int i = 0; i < SCM_F32VECTOR_SIZE(v); i++) {
387 SCM_F32VECTOR_ELEMENT(v, i) = genrand_f32(mt, TRUE);
388 }
389 UNLOCK(mt);
390 } else if (SCM_F64VECTORP(v)) {
391 LOCK(mt);
392 for (int i = 0; i < SCM_F64VECTOR_SIZE(v); i++) {
393 SCM_F64VECTOR_ELEMENT(v, i) = genrand_f64(mt, TRUE);
394 }
395 UNLOCK(mt);
396 }
397 return v;
398 }
399
400 /*
401 * Gauche specific stuff
402 */
403 ScmObj Scm_MakeMT(ScmObj seed, u_int flags)
404 {
405 ScmMersenneTwister *mt = SCM_NEW(ScmMersenneTwister);
406 SCM_SET_CLASS(mt, &Scm_MersenneTwisterClass);
407 mt->flags = flags;
408 mt->mti = N+1;
409 mt->seed = SCM_UNDEFINED;
410 if (!SCM_FALSEP(seed)) Scm_MTSetSeed(mt, seed);
411 if (SCM_MERSENNE_TWISTER_NEED_LOCK(mt)) {
412 SCM_INTERNAL_MUTEX_INIT(mt->lock);
413 }
414 return SCM_OBJ(mt);
415 }