Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
Fix type name and parsing for random generator.
[simgrid.git] / src / surf / random_mgr.c
1 /* Copyright (c) 2007, 2008, 2009, 2010. The SimGrid Team.
2  * All rights reserved.                                                     */
3
4 /* This program is free software; you can redistribute it and/or modify it
5   * under the terms of the license (GNU LGPL) which comes with this package. */
6
7 #include "surf/random_mgr.h"
8 #include "xbt/sysdep.h"
9 #include "gras_config.h" /*_XBT_WIN32*/
10
11 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(random, surf, "Random part of surf");
12
13 #ifdef _XBT_WIN32
14
15 static unsigned int _seed = 2147483647;
16
17 #ifdef __VISUALC__
18 typedef unsigned __int64 uint64_t;
19 typedef unsigned int uint32_t;
20 #endif
21
22 struct drand48_data {
23   unsigned short int __x[3];    /* Current state.  */
24   unsigned short int __old_x[3];        /* Old state.  */
25   unsigned short int __c;       /* Additive const. in congruential formula.  */
26   unsigned short int __init;    /* Flag for initializing.  */
27   unsigned long long int __a;   /* Factor in congruential formula.  */
28 };
29
30 static struct drand48_data __libc_drand48_data = { 0 };
31
32 union ieee754_double {
33   double d;
34
35   /* This is the IEEE 754 double-precision format.  */
36   struct {
37     /* Together these comprise the mantissa.  */
38     unsigned int mantissa1:32;
39     unsigned int mantissa0:20;
40     unsigned int exponent:11;
41     unsigned int negative:1;
42     /* Little endian.  */
43   } ieee;
44
45   /* This format makes it easier to see if a NaN is a signalling NaN.  */
46   struct {
47     /* Together these comprise the mantissa.  */
48     unsigned int mantissa1:32;
49     unsigned int mantissa0:19;
50     unsigned int quiet_nan:1;
51     unsigned int exponent:11;
52     unsigned int negative:1;
53
54   } ieee_nan;
55 };
56
57 #define IEEE754_DOUBLE_BIAS     0x3ff   /* Added to exponent.  */
58
59 double drand48(void);
60
61 int
62 _drand48_iterate(unsigned short int xsubi[3], struct drand48_data *buffer);
63
64 int
65 _erand48_r(unsigned short int xsubi[3], struct drand48_data *buffer,
66            double *result);
67
68
69 int
70 _erand48_r(unsigned short int xsubi[3], struct drand48_data *buffer,
71            double *result)
72 {
73   union ieee754_double temp;
74
75   /* Compute next state.  */
76   if (_drand48_iterate(xsubi, buffer) < 0)
77     return -1;
78
79   /* Construct a positive double with the 48 random bits distributed over
80      its fractional part so the resulting FP number is [0.0,1.0).  */
81
82   temp.ieee.negative = 0;
83   temp.ieee.exponent = IEEE754_DOUBLE_BIAS;
84   temp.ieee.mantissa0 = (xsubi[2] << 4) | (xsubi[1] >> 12);
85   temp.ieee.mantissa1 = ((xsubi[1] & 0xfff) << 20) | (xsubi[0] << 4);
86
87   /* Please note the lower 4 bits of mantissa1 are always 0.  */
88   *result = temp.d - 1.0;
89
90   return 0;
91 }
92
93 int _drand48_iterate(unsigned short int xsubi[3],
94                      struct drand48_data *buffer)
95 {
96   uint64_t X;
97   uint64_t result;
98
99   /* Initialize buffer, if not yet done.  */
100
101   if (buffer->__init == 0) {
102     buffer->__a = 0x5deece66dull;
103     buffer->__c = 0xb;
104     buffer->__init = 1;
105   }
106
107   /* Do the real work.  We choose a data type which contains at least
108      48 bits.  Because we compute the modulus it does not care how
109      many bits really are computed.  */
110
111   X = (uint64_t) xsubi[2] << 32 | (uint32_t) xsubi[1] << 16 | xsubi[0];
112
113   result = X * buffer->__a + buffer->__c;
114
115
116   xsubi[0] = result & 0xffff;
117   xsubi[1] = (result >> 16) & 0xffff;
118   xsubi[2] = (result >> 32) & 0xffff;
119
120   return 0;
121 }
122
123
124 double _drand48(void)
125 {
126   double result;
127
128   (void) _erand48_r(__libc_drand48_data.__x, &__libc_drand48_data,
129                     &result);
130
131   return result;
132 }
133
134 void _srand(unsigned int seed)
135 {
136   _seed = seed;
137 }
138
139 int _rand(void)
140 {
141   const long a = 16807;
142   const long m = 2147483647;
143   const long q = 127773;        /* (m/a) */
144   const long r = 2836;          /* (m%a) */
145
146   long lo, k, s;
147
148   s = (long) _seed;
149
150   k = (long) (s / q);
151
152   lo = (s - q * k);
153
154   s = a * lo - r * k;
155
156   if (s <= 0)
157     s += m;
158
159   _seed = (int) (s & RAND_MAX);
160
161   return _seed;
162 }
163
164 int _rand_r(unsigned int *pseed)
165 {
166   const long a = 16807;
167   const long m = 2147483647;
168   const long q = 127773;        /* (m/a) */
169   const long r = 2836;          /* (m%a) */
170
171   long lo, k, s;
172
173   s = (long) *pseed;
174
175   k = (long) (s / q);
176
177   lo = (s - q * k);
178
179   s = a * lo - r * k;
180
181   if (s <= 0)
182     s += m;
183
184   return (int) (s & RAND_MAX);
185
186 }
187
188
189 #define rand_r _rand_r
190 #define drand48 _drand48
191
192 #endif
193
194 static double custom_random(e_random_generator_t generator, long int *seed)
195 {
196   switch (generator) {
197
198   case DRAND48:
199     return drand48();
200   case RAND:
201     return (double) rand_r((unsigned int *) seed) / RAND_MAX;
202   case RNGSTREAM :
203           XBT_INFO("Seen RNGSTREAM");
204           return 0.0;
205   default:
206     return drand48();
207   }
208 }
209
210 /* Generate numbers between min and max with a given mean and standard deviation */
211 double random_generate(random_data_t random)
212 {
213   double a, b;
214   double alpha, beta, gamma;
215   double U1, U2, V, W, X;
216
217   if (random == NULL)
218     return 0.0f;
219
220   if (random->std == 0)
221     return random->mean * (random->max - random->min) + random->min;
222
223   a = random->mean * (random->mean * (1 - random->mean) /
224                       (random->std * random->std) - 1);
225   b = (1 -
226        random->mean) * (random->mean * (1 -
227                                         random->mean) / (random->std *
228                                                          random->std) - 1);
229
230   alpha = a + b;
231   if (a <= 1. || b <= 1.)
232     beta = ((1. / a) > (1. / b)) ? (1. / a) : (1. / b);
233   else
234     beta = sqrt((alpha - 2.) / (2. * a * b - alpha));
235   gamma = a + 1. / beta;
236
237   do {
238     /* Random generation for the Beta distribution based on
239      *   R. C. H. Cheng (1978). Generating beta variates with nonintegral shape parameters. _Communications of the ACM_, *21*, 317-322.
240      *   It is good for speed because it does not call math functions many times and respect the 4 given constraints
241      */
242     U1 = custom_random(random->generator, &(random->seed));
243     U2 = custom_random(random->generator, &(random->seed));
244
245     V = beta * log(U1 / (1 - U1));
246     W = a * exp(V);
247   } while (alpha * log(alpha / (b + W)) + gamma * V - log(4) <
248            log(U1 * U1 * U2));
249
250   X = W / (b + W);
251
252   return X * (random->max - random->min) + random->min;
253 }
254
255 random_data_t random_new(e_random_generator_t generator, long int seed,
256                          double min, double max, double mean, double std)
257 {
258   random_data_t random = xbt_new0(s_random_data_t, 1);
259
260   random->generator = generator;
261   random->seed = seed;
262   random->min = min;
263   random->max = max;
264
265   /* Check user stupidities */
266   if (max < min)
267     THROWF(arg_error, 0, "random->max < random->min (%f < %f)", max, min);
268   if (mean < min)
269     THROWF(arg_error, 0, "random->mean < random->min (%f < %f)", mean,
270            min);
271   if (mean > max)
272     THROWF(arg_error, 0, "random->mean > random->max (%f > %f)", mean,
273            max);
274
275   /* normalize the mean and standard deviation before storing */
276   random->mean = (mean - min) / (max - min);
277   random->std = std / (max - min);
278
279   if (random->mean * (1 - random->mean) < random->std * random->std)
280     THROWF(arg_error, 0, "Invalid mean and standard deviation (%f and %f)",
281            random->mean, random->std);
282
283   return random;
284 }