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