Crossings Minimization  1.0
random.c
Go to the documentation of this file.
1 /*
2  * Mersenne Twister (MT19937)
3  * Copyright (C) 1997 - 2002, Makoto Matsumoto and Takuji Nishimura
4  * http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html
5  * email: m-mat [at] math.sci.hiroshima-u.ac.jp
6  * All rights reserved.
7  *
8  * Redistribution and use in source and binary forms, with or without
9  * modification, are permitted provided that the following conditions
10  * are met:
11  *
12  * 1. Redistributions of source code must retain the above copyright
13  * notice, this list of conditions and the following disclaimer.
14  *
15  * 2. Redistributions in binary form must reproduce the above copyright
16  * notice, this list of conditions and the following disclaimer in the
17  * documentation and/or other materials provided with the distribution.
18  *
19  * 3. The names of its contributors may not be used to endorse or promote
20  * products derived from this software without specific prior written
21  * permission.
22  *
23  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
24  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
25  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
26  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
27  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
28  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
29  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
30  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
31  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
32  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
33  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
34  */
35 
36 #include <stdlib.h>
37 #include <string.h>
38 #include "random.h"
39 
40 /* Period parameters */
41 #define N 624
42 #define M 397
43 #define MATRIX_A 0x9908b0dfUL /* constant vector a */
44 #define UPPER_MASK 0x80000000UL /* most significant w-r bits */
45 #define LOWER_MASK 0x7fffffffUL /* least significant r bits */
46 
47 
48 static unsigned long mt[N]; /* the array for the state vector */
49 static int mti=N+1; /* mti==N+1 means mt[N] is not initialized */
50 
51 
52 /* initializes mt[N] with a seed */
53 void init_genrand(unsigned long s)
54 {
55  mt[0]= s & 0xffffffffUL;
56  for (mti=1; mti<N; mti++) {
57  mt[mti] =
58  (1812433253UL * (mt[mti-1] ^ (mt[mti-1] >> 30)) + mti);
59  /* See Knuth TAOCP Vol2. 3rd Ed. P.106 for multiplier. */
60  /* In the previous versions, MSBs of the seed affect */
61  /* only MSBs of the array mt[]. */
62  /* 2002/01/09 modified by Makoto Matsumoto */
63  mt[mti] &= 0xffffffffUL;
64  /* for >32 bit machines */
65  }
66 }
67 
68 
69 /* initialize by an array with array-length */
70 /* init_key is the array for initializing keys */
71 /* key_length is its length */
72 /* slight change for C++, 2004/2/26 */
73 void init_by_array(unsigned long init_key[], int key_length)
74 {
75  int i, j, k;
76  init_genrand(19650218UL);
77  i=1; j=0;
78  k = (N>key_length ? N : key_length);
79  for (; k; k--) {
80  mt[i] = (mt[i] ^ ((mt[i-1] ^ (mt[i-1] >> 30)) * 1664525UL))
81  + init_key[j] + j; /* non linear */
82  mt[i] &= 0xffffffffUL; /* for WORDSIZE > 32 machines */
83  i++; j++;
84  if (i>=N) { mt[0] = mt[N-1]; i=1; }
85  if (j>=key_length) j=0;
86  }
87  for (k=N-1; k; k--) {
88  mt[i] = (mt[i] ^ ((mt[i-1] ^ (mt[i-1] >> 30)) * 1566083941UL))
89  - i; /* non linear */
90  mt[i] &= 0xffffffffUL; /* for WORDSIZE > 32 machines */
91  i++;
92  if (i>=N) { mt[0] = mt[N-1]; i=1; }
93  }
94 
95  mt[0] = 0x80000000UL; /* MSB is 1; assuring non-zero initial array */
96 }
97 
98 
99 /* generates a random number on [0,0xffffffff]-interval */
100 unsigned long genrand_int32(void)
101 {
102  unsigned long y;
103  static unsigned long mag01[2]={0x0UL, MATRIX_A};
104  /* mag01[x] = x * MATRIX_A for x=0,1 */
105 
106  if (mti >= N) { /* generate N words at one time */
107  int kk;
108 
109  if (mti == N+1) /* if init_genrand() has not been called, */
110  init_genrand(5489UL); /* a default initial seed is used */
111 
112  for (kk=0;kk<N-M;kk++) {
113  y = (mt[kk]&UPPER_MASK)|(mt[kk+1]&LOWER_MASK);
114  mt[kk] = mt[kk+M] ^ (y >> 1) ^ mag01[y & 0x1UL];
115  }
116  for (;kk<N-1;kk++) {
117  y = (mt[kk]&UPPER_MASK)|(mt[kk+1]&LOWER_MASK);
118  mt[kk] = mt[kk+(M-N)] ^ (y >> 1) ^ mag01[y & 0x1UL];
119  }
120  y = (mt[N-1]&UPPER_MASK)|(mt[0]&LOWER_MASK);
121  mt[N-1] = mt[M-1] ^ (y >> 1) ^ mag01[y & 0x1UL];
122 
123  mti = 0;
124  }
125 
126  y = mt[mti++];
127 
128  /* Tempering */
129  y ^= (y >> 11);
130  y ^= (y << 7) & 0x9d2c5680UL;
131  y ^= (y << 15) & 0xefc60000UL;
132  y ^= (y >> 18);
133 
134  return y;
135 }
136 
137 
138 /* generates a random number on [0,0x7fffffff]-interval */
139 long genrand_int31(void)
140 {
141  return (long)(genrand_int32()>>1);
142 }
143 
144 
145 /* generates a random number on [0,1]-real-interval */
146 double genrand_real1(void)
147 {
148  return genrand_int32()*(1.0/4294967295.0);
149  /* divided by 2^32-1 */
150 }
151 
152 
153 /* generates a random number on [0,1)-real-interval */
154 double genrand_real2(void)
155 {
156  return genrand_int32()*(1.0/4294967296.0);
157  /* divided by 2^32 */
158 }
159 
160 
161 /* generates a random number on (0,1)-real-interval */
162 double genrand_real3(void)
163 {
164  return (((double)genrand_int32()) + 0.5)*(1.0/4294967296.0);
165  /* divided by 2^32 */
166 }
167 
168 
169 /* generates a random number on [0,1) with 53-bit resolution*/
170 double genrand_res53(void)
171 {
172  unsigned long a=genrand_int32()>>5, b=genrand_int32()>>6;
173  return(a*67108864.0+b)*(1.0/9007199254740992.0);
174 }
175 /* These real versions are due to Isaku Wada, 2002/01/09 added */
176 
177 
178 /**
179  * The following are added by Matthias Stallmann
180  * $Id: random.c 96 2014-09-09 16:37:16Z mfms $
181  */
182 
183 void genrand_permute( void * A, int length, int element_size ) {
184  int i = length;
185  void * temp = malloc( element_size );
186  while ( --i > 0 ) {
187  /* swap A[i] with a random element among A[0],...,A[i] */
188  int j = genrand_int31() % (i + 1);
189  if ( j != i ) {
190  memcpy( temp, A + (i * element_size), element_size );
191  memcpy( A + (i * element_size), A + (j * element_size), element_size );
192  memcpy( A + (j * element_size), temp, element_size );
193  }
194  }
195  free( temp );
196 }
197 
198 int * genrand_permutation( void * A, int length, int element_size ) {
199  int i;
200  void * temp = malloc( element_size );
201  int * retval = malloc( length * sizeof( int ) );
202  int tmp = 0;
203 
204  /* initialize retval to be the identity permutation */
205  for( i = 0; i < length; ++i ) {
206  retval[ i ] = i;
207  }
208 
209  i = length;
210  while ( --i > 0 ) {
211  /* swap A[i] with a random element among A[0],...,A[i] */
212  int j = genrand_int31() % (i + 1);
213  if ( j != i ) {
214  memcpy( temp, A + (i * element_size), element_size );
215  memcpy( A + (i * element_size), A + (j * element_size), element_size );
216  memcpy( A + (j * element_size), temp, element_size );
217 
218  tmp = retval[ i ];
219  retval[ i ] = retval[ j ];
220  retval[ j ] = tmp;
221  }
222  }
223  free( temp );
224  return retval;
225 }
226 
227 /* [Last modified: 2014 09 09 at 16:31:29 GMT] */
double genrand_real2(void)
Definition: random.c:154
double genrand_res53(void)
Definition: random.c:170
unsigned long genrand_int32(void)
Definition: random.c:100
static unsigned long mt[N]
Definition: random.c:48
void init_by_array(unsigned long init_key[], int key_length)
Definition: random.c:73
double genrand_real1(void)
Definition: random.c:146
int * genrand_permutation(void *A, int length, int element_size)
Definition: random.c:198
#define MATRIX_A
Definition: random.c:43
static int mti
Definition: random.c:49
#define M
Definition: random.c:42
#define UPPER_MASK
Definition: random.c:44
long genrand_int31(void)
Definition: random.c:139
double genrand_real3(void)
Definition: random.c:162
#define N
Definition: random.c:41
void init_genrand(unsigned long s)
Definition: random.c:53
#define LOWER_MASK
Definition: random.c:45
void genrand_permute(void *A, int length, int element_size)
Definition: random.c:183