From 4782cbf2b807dfaaf2969c2f3a10f68a16fd8e69 Mon Sep 17 00:00:00 2001
From: mquinson <mquinson@48e7efb5-ca39-0410-a469-dd3cf9ba447f>
Date: Mon, 9 Jun 2008 09:04:32 +0000
Subject: [PATCH] Ensure that the random generator respects the provided mean
 and standard deviation. Based on a patch from Louis-Claude Canon, thanks

git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/simgrid/simgrid/trunk@5566 48e7efb5-ca39-0410-a469-dd3cf9ba447f
---
 src/include/surf/random_mgr.h |  3 +-
 src/surf/random_mgr.c         | 96 +++++++++++++++++++++--------------
 2 files changed, 61 insertions(+), 38 deletions(-)

diff --git a/src/include/surf/random_mgr.h b/src/include/surf/random_mgr.h
index d839d55a64..7e0d4956af 100644
--- a/src/include/surf/random_mgr.h
+++ b/src/include/surf/random_mgr.h
@@ -13,7 +13,8 @@ typedef enum {NONE, DRAND48, RAND} Generator;
 
 typedef struct random_data_desc {
   long int seed;
-  double max, min, mean, stdDeviation;
+  double max, min;
+  double mean, std; /* note: mean and standard deviation are normalized */
   Generator generator;
 } s_random_data_t, *random_data_t;
 
diff --git a/src/surf/random_mgr.c b/src/surf/random_mgr.c
index 2a28e072b5..bae7a68ca5 100644
--- a/src/surf/random_mgr.c
+++ b/src/surf/random_mgr.c
@@ -1,4 +1,3 @@
-
 #include "surf/random_mgr.h"
 #include "xbt/sysdep.h"
 
@@ -11,59 +10,82 @@ static double drand48(void)
 
 static double rand_r(unsigned int* seed)
 {
-	THROW_UNIMPLEMENTED;
+   THROW_UNIMPLEMENTED;
    return -1;
 }
-
 #endif
 
 static double custom_random(Generator generator, long int *seed){
    switch(generator) {
-   case DRAND48:
-     return drand48(); 	
-   case RAND: 
-     return (double)rand_r((unsigned int*)seed)/RAND_MAX; 
-   default: return drand48();
+
+    case DRAND48:
+      return drand48();
+    case RAND: 
+      return (double)rand_r((unsigned int*)seed)/RAND_MAX;
+    default: 
+      return drand48();
    }
 }
 
 /* Generate numbers between min and max with a given mean and standard deviation */
-double random_generate(random_data_t random){  
-  double x1, x2, w, y;
-  
-  if (random == NULL) return 0.0f;  
+double random_generate(random_data_t random) {
+  double a, b;
+  double alpha, beta, gamma;
+  double U1, U2, V, W, X;
+
+  if (random == NULL) return 0.0f;
+
+  a = random->mean * ( random->mean * (1 - random->mean) / (random->std*random->std) - 1 );
+  b = (1 - random->mean) * ( random->mean * (1 - random->mean) / (random->std*random->std) - 1 );
+
+  alpha = a + b;
+  if (a <= 1. || b <= 1.)
+    beta = ((1./a)>(1./b))?(1./a):(1./b);
+  else
+    beta = sqrt ((alpha-2.) / (2.*a*b - alpha));
+  gamma = a + 1./beta;
 
   do {
-    /* Apply the polar form of the Box-Muller Transform to map the two uniform random numbers to a pair of numbers from a normal distribution.
-       It is good for speed because it does not call math functions many times. Another way would be to simply:
-         y1 = sqrt( - 2 * log(x1) ) * cos( 2 * pi * x2 )
-    */ 
-    do {
-      x1 = 2.0 * custom_random(random->generator,&(random->seed)) - 1.0;
-      x2 = 2.0 * custom_random(random->generator,&(random->seed)) - 1.0;
-      w = x1 * x1 + x2 * x2;
-    } while ( w >= 1.0 );
-
-    w = sqrt( (-2.0 * log( w ) ) / w );
-    y = x1 * w;
-
-    /* Multiply the Box-Muller value by the standard deviation and add the mean */
-    y = y * random->stdDeviation + random->mean;
-  } while (!(random->min <= y && y <= random->max));
-
-  return y;
+    /* Random generation for the Beta distribution based on
+     *   R. C. H. Cheng (1978). Generating beta variates with nonintegral shape parameters. _Communications of the ACM_, *21*, 317-322.
+     *   It is good for speed because it does not call math functions many times and respect the 4 given constraints
+     */
+    U1 = custom_random(random->generator,&(random->seed));
+    U2 = custom_random(random->generator,&(random->seed));
+
+    V = beta * log(U1/(1-U1));
+    W = a * exp(V);
+  } while (alpha * log(alpha/(b + W)) + gamma*V - log(4) < log(U1*U1*U2));
+
+  X = W / (b + W);
+
+  return X * (random->max - random->min) + random->min;
 }
 
-random_data_t random_new(Generator generator, long int seed, 
-			 double min, double max, double mean, 
-			 double stdDeviation){
+random_data_t random_new(Generator generator, long int seed,
+			 double min, double max, 
+			 double mean, double std){
   random_data_t random = xbt_new0(s_random_data_t, 1);
+   
   random->generator = generator;
-  random->seed = seed;
+  random->seed = seed;   
   random->min = min;
   random->max = max;
-  random->mean = mean;
-  random->stdDeviation = stdDeviation;
+
+  /* Check user stupidities */
+  if (max < min)
+     THROW2(arg_error,0,"random->max < random->min (%f < %f)",max, min);
+  if (mean < min)
+     THROW2(arg_error,0,"random->mean < random->min (%f < %f)",mean, min);
+  if (mean > max)
+     THROW2(arg_error,0,"random->mean > random->max (%f > %f)",mean, max);
+
+  /* normalize the mean and standard deviation before storing */
+  random->mean = (mean - min) / (max - min);
+  random->std = std / (max - min);
+
+  if (random->mean * (1-random->mean) < random->std*random->std) 
+     THROW2(arg_error,0,"Invalid mean and standard deviation (%f and %f)",random->mean, random->std);
+   
   return random;
 }
-
-- 
2.20.1