Logo AND Algorithmique Numérique Distribuée

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