Debian Codegraph @

examples/mt19937ar.c

raw
1 /*
2 A C-program for MT19937, with initialization improved 2002/1/26.
3 Coded by Takuji Nishimura and Makoto Matsumoto.
4
5 Before using, initialize the state by using init_genrand(seed)
6 or init_by_array(init_key, key_length).
7
8 Copyright (C) 1997 - 2002, Makoto Matsumoto and Takuji Nishimura,
9 All rights reserved.
10
11 Redistribution and use in source and binary forms, with or without
12 modification, are permitted provided that the following conditions
13 are met:
14
15 1. Redistributions of source code must retain the above copyright
16 notice, this list of conditions and the following disclaimer.
17
18 2. Redistributions in binary form must reproduce the above copyright
19 notice, this list of conditions and the following disclaimer in the
20 documentation and/or other materials provided with the distribution.
21
22 3. The names of its contributors may not be used to endorse or promote
23 products derived from this software without specific prior written
24 permission.
25
26 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
27 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
28 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
29 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
30 CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
31 EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
32 PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
33 PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
34 LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
35 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
36 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
37
38
39 Any feedback is very welcome.
40 http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html
41 email: m-mat @ math.sci.hiroshima-u.ac.jp (remove space)
42 */
43
44 #include <stdio.h>
45 #include <orc/orc.h>
46 #include <stdlib.h>
47 #include <string.h>
48 #include "mt19937arorc.h"
49
50 /* Period parameters */
51 #define N 624
52 #define M 397
53 #define MATRIX_A 0x9908b0dfUL /* constant vector a */
54 #define UPPER_MASK 0x80000000UL /* most significant w-r bits */
55 #define LOWER_MASK 0x7fffffffUL /* least significant r bits */
56
57 static unsigned long mt[N]; /* the array for the state vector */
58 static int mti=N+1; /* mti==N+1 means mt[N] is not initialized */
59
60 /* initializes mt[N] with a seed */
61 void init_genrand(unsigned long s)
62 {
63 mt[0]= s & 0xffffffffUL;
64 for (mti=1; mti<N; mti++) {
65 mt[mti] =
66 (1812433253UL * (mt[mti-1] ^ (mt[mti-1] >> 30)) + mti);
67 /* See Knuth TAOCP Vol2. 3rd Ed. P.106 for multiplier. */
68 /* In the previous versions, MSBs of the seed affect */
69 /* only MSBs of the array mt[]. */
70 /* 2002/01/09 modified by Makoto Matsumoto */
71 mt[mti] &= 0xffffffffUL;
72 /* for >32 bit machines */
73 }
74 }
75
76 /* initialize by an array with array-length */
77 /* init_key is the array for initializing keys */
78 /* key_length is its length */
79 /* slight change for C++, 2004/2/26 */
80 void init_by_array(orc_uint32 init_key[], int key_length)
81 {
82 int i, j, k;
83 init_genrand(19650218UL);
84 i=1; j=0;
85 k = (N>key_length ? N : key_length);
86 for (; k; k--) {
87 mt[i] = (mt[i] ^ ((mt[i-1] ^ (mt[i-1] >> 30)) * 1664525UL))
88 + init_key[j] + j; /* non linear */
89 mt[i] &= 0xffffffffUL; /* for WORDSIZE > 32 machines */
90 i++; j++;
91 if (i>=N) { mt[0] = mt[N-1]; i=1; }
92 if (j>=key_length) j=0;
93 }
94 for (k=N-1; k; k--) {
95 mt[i] = (mt[i] ^ ((mt[i-1] ^ (mt[i-1] >> 30)) * 1566083941UL))
96 - i; /* non linear */
97 mt[i] &= 0xffffffffUL; /* for WORDSIZE > 32 machines */
98 i++;
99 if (i>=N) { mt[0] = mt[N-1]; i=1; }
100 }
101
102 mt[0] = 0x80000000UL; /* MSB is 1; assuring non-zero initial array */
103 }
104
105 /* generates a random number on [0,0xffffffff]-interval */
106 unsigned long genrand_int32(void)
107 {
108 unsigned long y;
109 static unsigned long mag01[2]={0x0UL, MATRIX_A};
110 /* mag01[x] = x * MATRIX_A for x=0,1 */
111
112 if (mti >= N) { /* generate N words at one time */
113 int kk;
114
115 if (mti == N+1) /* if init_genrand() has not been called, */
116 init_genrand(5489UL); /* a default initial seed is used */
117
118 for (kk=0;kk<N-M;kk++) {
119 y = (mt[kk]&UPPER_MASK)|(mt[kk+1]&LOWER_MASK);
120 mt[kk] = mt[kk+M] ^ (y >> 1) ^ mag01[y & 0x1UL];
121 }
122 for (;kk<N-1;kk++) {
123 y = (mt[kk]&UPPER_MASK)|(mt[kk+1]&LOWER_MASK);
124 mt[kk] = mt[kk+(M-N)] ^ (y >> 1) ^ mag01[y & 0x1UL];
125 }
126 y = (mt[N-1]&UPPER_MASK)|(mt[0]&LOWER_MASK);
127 mt[N-1] = mt[M-1] ^ (y >> 1) ^ mag01[y & 0x1UL];
128
129 mti = 0;
130 }
131
132 y = mt[mti++];
133
134 /* Tempering */
135 y ^= (y >> 11);
136 y ^= (y << 7) & 0x9d2c5680UL;
137 y ^= (y << 15) & 0xefc60000UL;
138 y ^= (y >> 18);
139
140 return y;
141 }
142
143 /* Orc version */
144
145 typedef struct _OrcRandomContext OrcRandomContext;
146 struct _OrcRandomContext {
147 orc_uint32 d[N];
148 orc_uint32 mt[N+1];
149 int mti;
150 };
151
152 OrcRandomContext *
153 orc_random_context_new (void)
154 {
155 OrcRandomContext *context;
156 context = malloc(sizeof(OrcRandomContext));
157 memset (context, 0, sizeof(OrcRandomContext));
158 context->mti = N+1;
159 return context;
160 }
161
162 void
163 orc_random_init_genrand(OrcRandomContext *context, orc_uint32 s)
164 {
165 orc_uint32 *mt = context->mt;
166 int mti;
167
168 mt[0] = s;
169 for (mti=1; mti<N; mti++) {
170 mt[mti] =
171 (1812433253UL * (mt[mti-1] ^ (mt[mti-1] >> 30)) + mti);
172 /* See Knuth TAOCP Vol2. 3rd Ed. P.106 for multiplier. */
173 }
174 context->mti = mti;
175 }
176
177 void
178 orc_random_init_by_array (OrcRandomContext *context, orc_uint32 *init_key,
179 int key_length)
180 {
181 int i, j, k;
182 orc_uint32 *mt = context->mt;
183
184 orc_random_init_genrand (context, 19650218UL);
185 i=1; j=0;
186 k = (N>key_length ? N : key_length);
187 for (; k; k--) {
188 mt[i] = (mt[i] ^ ((mt[i-1] ^ (mt[i-1] >> 30)) * 1664525UL))
189 + init_key[j] + j; /* non linear */
190 i++; j++;
191 if (i>=N) { mt[0] = mt[N-1]; i=1; }
192 if (j>=key_length) j=0;
193 }
194 for (k=N-1; k; k--) {
195 mt[i] = (mt[i] ^ ((mt[i-1] ^ (mt[i-1] >> 30)) * 1566083941UL))
196 - i; /* non linear */
197 i++;
198 if (i>=N) { mt[0] = mt[N-1]; i=1; }
199 }
200
201 mt[0] = 0x80000000UL; /* MSB is 1; assuring non-zero initial array */
202 }
203
204 #if 0
205 /* These are the functions that were converted to Orc code. */
206 static void
207 mix (orc_uint32 *mt, orc_uint32 *mt2, int n)
208 {
209 orc_uint32 y;
210 int kk;
211
212 for (kk=0;kk<n;kk++) {
213 orc_uint32 t1;
214 orc_uint32 t2;
215
216 t1 = mt[kk]&UPPER_MASK;
217 t2 = mt[kk+1]&LOWER_MASK;
218 y = t1 | t2;
219
220 t1 = y&1;
221 t1 = (t1) ? MATRIX_A : 0;
222 y = y >> 1;
223 y ^= t1;
224
225 mt[kk] = mt2[kk] ^ y;
226 }
227 }
228
229 static void
230 temper (orc_uint32 *d, orc_uint32 *mt, int n)
231 {
232 orc_uint32 y;
233 int i;
234
235 for(i=0;i<N;i++){
236 y = mt[i];
237 y ^= (y >> 11);
238 y ^= (y << 7) & 0x9d2c5680UL;
239 y ^= (y << 15) & 0xefc60000UL;
240 y ^= (y >> 18);
241 d[i] = y;
242 }
243 }
244 #endif
245
246 static void
247 update_context (OrcRandomContext *context)
248 {
249 orc_uint32 *d = context->d;
250 orc_uint32 *mt = context->mt;
251
252 #if 0
253 mix (mt, mt + M, N-M);
254 mt[N] = mt[0];
255 mix (mt + N - M, mt, M);
256 temper (d, mt, N);
257 #endif
258
259 mt19937ar_mix (mt, mt + 1, mt + M, N-M);
260 mt[N] = mt[0];
261 mt19937ar_mix (mt + N - M, mt + N - M + 1, mt, M);
262 mt19937ar_temper (d, mt, N);
263
264 #if 0
265 /* too many temp variables, compiles incorrectly */
266 mt19937ar_mix_temper (d, mt, mt + 1, mt + M, N-M);
267 mt[N] = mt[0];
268 mt19937ar_mix_temper (d + N - M, mt + N - M, mt + N - M + 1, mt, M);
269 #endif
270 }
271
272 orc_uint32
273 orc_random_genrand_int32 (OrcRandomContext *context)
274 {
275 if (context->mti >= N) { /* generate N words at one time */
276 if (context->mti == N+1) /* if init_genrand() has not been called, */
277 orc_random_init_genrand(context, 5489UL); /* a default initial seed is used */
278
279 update_context (context);
280
281 context->mti = 0;
282 }
283
284 return context->d[context->mti++];
285 }
286
287
288 int main(void)
289 {
290 int i;
291 orc_uint32 init[4]={0x123, 0x234, 0x345, 0x456};
292 int length=4;
293 orc_uint32 ref, test;
294 OrcRandomContext *context;
295 int error = 0;
296
297 init_by_array(init, length);
298
299 context = orc_random_context_new ();
300 orc_random_init_by_array (context, init, length);
301
302 printf("1000 outputs of genrand_int32()\n");
303 for (i=0; i<1000; i++) {
304 ref = genrand_int32();
305 test = orc_random_genrand_int32(context);
306 printf("%08x %08x %c\n", ref, test, (ref == test) ? ' ' : '*');
307 if (ref != test) error = 1;
308 }
309 if (error) {
310 printf("FAIL\n");
311 }
312
313 return 0;
314 }
315