1 |
|
|
/* |
2 |
|
|
Teem: Tools to process and visualize scientific data and images . |
3 |
|
|
Copyright (C) 2013, 2012, 2011, 2010, 2009 University of Chicago |
4 |
|
|
Copyright (C) 2008, 2007, 2006, 2005 Gordon Kindlmann |
5 |
|
|
Copyright (C) 2004, 2003, 2002, 2001, 2000, 1999, 1998 University of Utah |
6 |
|
|
|
7 |
|
|
This library is free software; you can redistribute it and/or |
8 |
|
|
modify it under the terms of the GNU Lesser General Public License |
9 |
|
|
(LGPL) as published by the Free Software Foundation; either |
10 |
|
|
version 2.1 of the License, or (at your option) any later version. |
11 |
|
|
The terms of redistributing and/or modifying this software also |
12 |
|
|
include exceptions to the LGPL that facilitate static linking. |
13 |
|
|
|
14 |
|
|
This library is distributed in the hope that it will be useful, |
15 |
|
|
but WITHOUT ANY WARRANTY; without even the implied warranty of |
16 |
|
|
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
17 |
|
|
Lesser General Public License for more details. |
18 |
|
|
|
19 |
|
|
You should have received a copy of the GNU Lesser General Public License |
20 |
|
|
along with this library; if not, write to Free Software Foundation, Inc., |
21 |
|
|
51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA |
22 |
|
|
*/ |
23 |
|
|
/* |
24 |
|
|
This file is a modified version of the MersenneTwister.h source file |
25 |
|
|
written by Richard J. Wagner. The original copyright notice follows. |
26 |
|
|
|
27 |
|
|
Mersenne Twister random number generator -- a C++ class MTRand |
28 |
|
|
Based on code by Makoto Matsumoto, Takuji Nishimura, and Shawn Cokus |
29 |
|
|
Richard J. Wagner v1.0 15 May 2003 rjwagner@writeme.com |
30 |
|
|
|
31 |
|
|
The Mersenne Twister is an algorithm for generating random numbers. It |
32 |
|
|
was designed with consideration of the flaws in various other generators. |
33 |
|
|
The period, 2^19937-1, and the order of equidistribution, 623 dimensions, |
34 |
|
|
are far greater. The generator is also fast; it avoids multiplication and |
35 |
|
|
division, and it benefits from caches and pipelines. For more information |
36 |
|
|
see the inventors' web page at http://www.math.keio.ac.jp/~matumoto/emt.html |
37 |
|
|
|
38 |
|
|
Reference |
39 |
|
|
M. Matsumoto and T. Nishimura, "Mersenne Twister: A 623-Dimensionally |
40 |
|
|
Equidistributed Uniform Pseudo-Random Number Generator", ACM Transactions on |
41 |
|
|
Modeling and Computer Simulation, Vol. 8, No. 1, January 1998, pp 3-30. |
42 |
|
|
|
43 |
|
|
Copyright (C) 1997 - 2002, Makoto Matsumoto and Takuji Nishimura, |
44 |
|
|
Copyright (C) 2000 - 2003, Richard J. Wagner |
45 |
|
|
All rights reserved. |
46 |
|
|
|
47 |
|
|
Redistribution and use in source and binary forms, with or without |
48 |
|
|
modification, are permitted provided that the following conditions |
49 |
|
|
are met: |
50 |
|
|
|
51 |
|
|
1. Redistributions of source code must retain the above copyright |
52 |
|
|
notice, this list of conditions and the following disclaimer. |
53 |
|
|
|
54 |
|
|
2. Redistributions in binary form must reproduce the above copyright |
55 |
|
|
notice, this list of conditions and the following disclaimer in the |
56 |
|
|
documentation and/or other materials provided with the distribution. |
57 |
|
|
|
58 |
|
|
3. The names of its contributors may not be used to endorse or promote |
59 |
|
|
products derived from this software without specific prior written |
60 |
|
|
permission. |
61 |
|
|
|
62 |
|
|
THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
63 |
|
|
"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
64 |
|
|
LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS |
65 |
|
|
FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE |
66 |
|
|
COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, |
67 |
|
|
INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, |
68 |
|
|
BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; |
69 |
|
|
LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER |
70 |
|
|
CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT |
71 |
|
|
LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN |
72 |
|
|
ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE |
73 |
|
|
POSSIBILITY OF SUCH DAMAGE. |
74 |
|
|
|
75 |
|
|
The original code included the following notice: |
76 |
|
|
|
77 |
|
|
When you use this, send an email to: matumoto@math.keio.ac.jp |
78 |
|
|
with an appropriate reference to your work. |
79 |
|
|
|
80 |
|
|
It would be nice to CC: rjwagner@writeme.com and Cokus@math.washington.edu |
81 |
|
|
when you write. |
82 |
|
|
*/ |
83 |
|
|
|
84 |
|
|
#include "air.h" |
85 |
|
|
#include "privateAir.h" |
86 |
|
|
|
87 |
|
|
#define AIR_RANDMT_M 397 |
88 |
|
|
#define AIR_RANDMT_DEFAULT_SEED 42 |
89 |
|
|
|
90 |
|
|
/* Inlined class member functions that I made macros */ |
91 |
|
|
#define HIBIT( u ) ((u) & 0x80000000UL) |
92 |
|
|
#define LOBIT( u ) ((u) & 0x00000001UL) |
93 |
|
|
#define LOBITS( u ) ((u) & 0x7fffffffUL) |
94 |
|
|
#define MIXBITS( u, v ) (HIBIT(u) | LOBITS(v)) |
95 |
|
|
#define TWOSCOMP( u ) (~(u)+1) |
96 |
|
|
#define TWIST( m, s0, s1 ) \ |
97 |
|
|
((m) ^ (MIXBITS(s0,s1)>>1) ^ (TWOSCOMP(LOBIT(s1)) & 0x9908b0dfUL)) |
98 |
|
|
|
99 |
|
|
/* airRandMTStateGlobal is not allocated at compile-time because of |
100 |
|
|
weirdness of where non-initialized global objects go in shared |
101 |
|
|
libraries. Its allocation and initialization are controlled by |
102 |
|
|
_airRandMTStateGlobal_{allocated,initialized}. Users who want to |
103 |
|
|
ensure thread safety should be using airRandMTStateNew and |
104 |
|
|
airDrandMT_r, not the global state. |
105 |
|
|
*/ |
106 |
|
|
|
107 |
|
|
airRandMTState *airRandMTStateGlobal = NULL; |
108 |
|
|
static int _airRandMTStateGlobal_allocated = AIR_FALSE; |
109 |
|
|
static int _airRandMTStateGlobal_initialized = AIR_FALSE; |
110 |
|
|
|
111 |
|
|
static void |
112 |
|
|
_airRandMTInitialize(airRandMTState *rng, unsigned int seed) { |
113 |
|
|
/* Initialize generator state with seed See Knuth TAOCP Vol 2, 3rd |
114 |
|
|
Ed, p.106 for multiplier. In previous versions, most significant |
115 |
|
|
bits (MSBs) of the seed affect only MSBs of the state array. |
116 |
|
|
Modified 9 Jan 2002 by Makoto Matsumoto. |
117 |
|
|
*/ |
118 |
|
186 |
register unsigned int *s = rng->state; |
119 |
|
|
register unsigned int *r = rng->state; |
120 |
|
|
register int i = 1; |
121 |
|
93 |
*s++ = seed & 0xffffffffUL; |
122 |
✓✓ |
116064 |
for( ; i < AIR_RANDMT_N; ++i ) { |
123 |
|
57939 |
*s++ = ( 1812433253UL * ( *r ^ (*r >> 30) ) + i ) & 0xffffffffUL; |
124 |
|
57939 |
r++; |
125 |
|
|
} |
126 |
|
93 |
} |
127 |
|
|
|
128 |
|
|
static void |
129 |
|
|
_airRandMTReload(airRandMTState *rng) { |
130 |
|
|
/* Generate N new values in state. Made clearer and faster by |
131 |
|
|
Matthew Bellew (matthew.bellew@home.com) */ |
132 |
|
|
register int i; |
133 |
|
65994 |
register unsigned int *p = rng->state; |
134 |
✓✓ |
15046632 |
for (i=AIR_RANDMT_N - AIR_RANDMT_M; i--; ++p) { |
135 |
|
7490319 |
*p = TWIST( p[AIR_RANDMT_M], p[0], p[1] ); |
136 |
|
|
} |
137 |
✓✓✓✓
|
39299427 |
for (i=AIR_RANDMT_M; --i; ++p) { |
138 |
|
26166621 |
*p = TWIST( p[AIR_RANDMT_M-AIR_RANDMT_N], p[0], p[1] ); |
139 |
|
|
} |
140 |
|
32997 |
*p = TWIST( p[AIR_RANDMT_M-AIR_RANDMT_N], p[0], rng->state[0] ); |
141 |
|
|
|
142 |
|
32997 |
rng->left = AIR_RANDMT_N; |
143 |
|
32997 |
rng->pNext = rng->state; |
144 |
|
32997 |
} |
145 |
|
|
|
146 |
|
|
airRandMTState * |
147 |
|
|
airRandMTStateNew(unsigned int seed) { |
148 |
|
|
airRandMTState* ret; |
149 |
|
|
|
150 |
|
128 |
ret = AIR_CAST(airRandMTState*, malloc(sizeof(airRandMTState))); |
151 |
|
64 |
airSrandMT_r(ret, seed); |
152 |
|
64 |
return ret; |
153 |
|
|
} |
154 |
|
|
|
155 |
|
|
airRandMTState * |
156 |
|
|
airRandMTStateNix(airRandMTState *state) { |
157 |
|
104 |
airFree(state); |
158 |
|
52 |
return NULL; |
159 |
|
|
} |
160 |
|
|
|
161 |
|
|
void |
162 |
|
|
airSrandMT_r(airRandMTState *rng, unsigned int seed) { |
163 |
|
|
/* Seed the generator with a simple uint32 */ |
164 |
|
186 |
_airRandMTInitialize(rng, seed); |
165 |
|
93 |
_airRandMTReload(rng); |
166 |
|
93 |
} |
167 |
|
|
|
168 |
|
|
/* Pull a 32-bit integer from the generator state. Every other access |
169 |
|
|
** function simply transforms the numbers extracted here. |
170 |
|
|
*/ |
171 |
|
|
unsigned int |
172 |
|
|
airUIrandMT_r(airRandMTState *rng) { |
173 |
|
|
register unsigned int s1; |
174 |
|
|
|
175 |
✓✓ |
41079958 |
if (rng->left == 0) { |
176 |
|
32904 |
_airRandMTReload(rng); |
177 |
|
32904 |
} |
178 |
|
20539979 |
--rng->left; |
179 |
|
|
|
180 |
|
20539979 |
s1 = *rng->pNext++; |
181 |
|
20539979 |
s1 ^= (s1 >> 11); |
182 |
|
20539979 |
s1 ^= (s1 << 7) & 0x9d2c5680UL; |
183 |
|
20539979 |
s1 ^= (s1 << 15) & 0xefc60000UL; |
184 |
|
20539979 |
return ( s1 ^ (s1 >> 18) ); |
185 |
|
|
} |
186 |
|
|
|
187 |
|
|
/* This generates the closed interval [0,1] */ |
188 |
|
|
double |
189 |
|
|
airDrandMT_r(airRandMTState *rng) { |
190 |
|
28259248 |
double result = airUIrandMT_r(rng); |
191 |
|
14129624 |
return result * (1.0/4294967295.0); |
192 |
|
|
} |
193 |
|
|
|
194 |
|
|
/* [0,1) w/ 53 bit precision (capacity of IEEE double precision) */ |
195 |
|
|
double |
196 |
|
|
airDrandMT53_r(airRandMTState *rng) { |
197 |
|
|
unsigned int a, b; |
198 |
|
|
a = airUIrandMT_r(rng) >> 5; |
199 |
|
|
b = airUIrandMT_r(rng) >> 6; |
200 |
|
|
return ( a * 67108864.0 + b ) * (1.0/9007199254740992.0); /* by Isaku Wada */ |
201 |
|
|
} |
202 |
|
|
|
203 |
|
|
#define _GLOBAL_ALLOC \ |
204 |
|
|
if (!_airRandMTStateGlobal_allocated) { \ |
205 |
|
|
airRandMTStateGlobal = airRandMTStateNew(0); \ |
206 |
|
|
_airRandMTStateGlobal_allocated = AIR_TRUE; \ |
207 |
|
|
} |
208 |
|
|
#define _GLOBAL_INIT \ |
209 |
|
|
if (!_airRandMTStateGlobal_initialized) { \ |
210 |
|
|
airSrandMT(AIR_RANDMT_DEFAULT_SEED); \ |
211 |
|
|
} \ |
212 |
|
|
|
213 |
|
|
/* |
214 |
|
|
******** airRandMTStateGlobalInit |
215 |
|
|
** |
216 |
|
|
** Allocates and initializes airRandMTStateGlobal if it was not already |
217 |
|
|
** allocated and initialized. However, this does not need to be called |
218 |
|
|
** except if the user wants to use the airRandMTStateGlobal pointer. |
219 |
|
|
** The allocation and initialization is done as necessary inside the |
220 |
|
|
** the airSrandMT(), airDrandMT(), etc functions (all the functions |
221 |
|
|
** that use airRandMTStateGlobal |
222 |
|
|
*/ |
223 |
|
|
void |
224 |
|
|
airRandMTStateGlobalInit() { |
225 |
|
|
_GLOBAL_ALLOC; |
226 |
|
|
_GLOBAL_INIT; |
227 |
|
|
} |
228 |
|
|
|
229 |
|
|
void |
230 |
|
|
airSrandMT(unsigned int seed) { |
231 |
✓✓ |
48 |
_GLOBAL_ALLOC; |
232 |
|
19 |
airSrandMT_r(airRandMTStateGlobal, seed); |
233 |
|
19 |
_airRandMTStateGlobal_initialized = AIR_TRUE; |
234 |
|
19 |
} |
235 |
|
|
|
236 |
|
|
double |
237 |
|
|
airDrandMT() { |
238 |
✗✓ |
28232396 |
_GLOBAL_ALLOC; |
239 |
✗✓ |
14116198 |
_GLOBAL_INIT; |
240 |
|
14116198 |
return airDrandMT_r(airRandMTStateGlobal); |
241 |
|
|
} |
242 |
|
|
|
243 |
|
|
/* |
244 |
|
|
******** airRandInt |
245 |
|
|
** |
246 |
|
|
** returns a random integer in range [0, N-1] |
247 |
|
|
*/ |
248 |
|
|
unsigned int |
249 |
|
|
airRandInt(unsigned int N) { |
250 |
✓✓ |
86099 |
_GLOBAL_ALLOC; |
251 |
✓✓ |
43050 |
_GLOBAL_INIT; |
252 |
|
43049 |
return airUIrandMT_r(airRandMTStateGlobal)%N; |
253 |
|
|
} |
254 |
|
|
|
255 |
|
|
unsigned int |
256 |
|
|
airRandInt_r(airRandMTState *state, unsigned int N) { |
257 |
|
|
|
258 |
|
180 |
return airUIrandMT_r(state)%N; |
259 |
|
|
} |
260 |
|
|
|
261 |
|
|
/* This checks to see if the sequence of numbers we get is what we |
262 |
|
|
expect. It should return 1 if all is well, 0 if not. |
263 |
|
|
|
264 |
|
|
One thing to check for if it fails is the presence of twos |
265 |
|
|
complement interger representation. The code here relies on it. |
266 |
|
|
*/ |
267 |
|
|
int |
268 |
|
|
airRandMTSanity(void) { |
269 |
|
|
int result = 0; |
270 |
|
|
/* Create a new generator with our seed */ |
271 |
|
40 |
airRandMTState* rng = airRandMTStateNew(AIR_RANDMT_DEFAULT_SEED); |
272 |
|
|
|
273 |
✗✓ |
20 |
if (!rng) { |
274 |
|
|
/* Couldn't allocate memory */ |
275 |
|
|
return 0; |
276 |
|
|
} |
277 |
|
|
|
278 |
|
|
/* Now check against a predetermined list of values; any inequality |
279 |
|
|
will set result to be non-zero */ |
280 |
|
20 |
result |= airUIrandMT_r(rng) != 1608637542U; |
281 |
|
20 |
result |= airUIrandMT_r(rng) != 3421126067U; |
282 |
|
20 |
result |= airUIrandMT_r(rng) != 4083286876U; |
283 |
|
20 |
result |= airUIrandMT_r(rng) != 787846414U; |
284 |
|
20 |
result |= airUIrandMT_r(rng) != 3143890026U; |
285 |
|
20 |
result |= airUIrandMT_r(rng) != 3348747335U; |
286 |
|
20 |
result |= airUIrandMT_r(rng) != 2571218620U; |
287 |
|
20 |
result |= airUIrandMT_r(rng) != 2563451924U; |
288 |
|
20 |
result |= airUIrandMT_r(rng) != 670094950U; |
289 |
|
20 |
result |= airUIrandMT_r(rng) != 1914837113U; |
290 |
|
|
|
291 |
|
20 |
airRandMTStateNix(rng); |
292 |
|
20 |
return !result; |
293 |
|
20 |
} |