src/surf/random_mgr.c

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