isisd/topology/random.c

   1 /*********************************************************************/
   2 /*                                                                   */
   3 /* current processor time in seconds                                 */
   4 /* difference between two calls is processor time spent by your code */
   5 /* needs: <sys/types.h>, <sys/times.h>                               */
   6 /* depends on compiler and OS                                        */
   7 /*                                                                   */
   8 /*********************************************************************/
   9
  10 #include <zebra.h>
  11 #include <sys/types.h>
  12 #include <sys/times.h>
  13
  14 /*
  15  * Prototypes.
  16  */
  17 unsigned long timer(void);
  18 void init_rand(long);
  19 double rand01(void);
  20 double randg01(void);
  21 long nrand(long);
  22 void free_arc(void *);
  23
  24 unsigned long timer ()
  25    { struct tms hold;
  26
  27         times(&hold);
  28         return (unsigned long) ((float) (hold.tms_utime) / 60.0);
  29    }
  30
  31
  32 /*********************************************************************/
  33 /*                                                                   */
  34 /*            Family of random number generators                     */
  35 /*                                                                   */
  36 /*  Initialisation:                                                  */
  37 /*            void init_rand ( seed );                               */
  38 /*                 long seed     - any positive number               */
  39 /*                                 if seed<=0 init_rand takes time   */
  40 /*                                 from timer instead of seed        */
  41 /*                                                                   */
  42 /*  Whole number uniformly distributed on [0,n):                     */
  43 /*            long nrand (n);                                        */
  44 /*                 long n                                            */
  45 /*                                                                   */
  46 /*  Real number uniformly distributed on [0,1]                       */
  47 /*            double rand01();                                       */
  48 /*                                                                   */
  49 /*  Real number with Gauss(0,1) disitribution:                       */
  50 /*            double randg01();                                      */
  51 /*                                                                   */
  52 /*  Algorithm:                                                       */
  53 /*            x(n+1) = (x(n) * 5^13) mod 2^31                        */
  54 /*                                                                   */
  55 /*********************************************************************/
  56
  57 unsigned long internal_seed;
  58
  59 void init_rand ( init_seed )
  60
  61 long init_seed;
  62
  63 { internal_seed = ( init_seed > 0 )
  64                  ? (unsigned long) init_seed
  65                  : (unsigned long) timer();
  66
  67
  68   /* only odd numbers are acceptable */
  69   if ( internal_seed % 2 == 0 ) internal_seed --;
  70 }
  71
  72 /*********************************************************************/
  73 /*                                                                   */
  74 /* Internal function  irand  may depend on OS and compiler           */
  75 /*                                                                   */
  76 /* irand assumption:                                                 */
  77 /* unsigned long i,j;                                                */
  78 /*   if i*j > max(unsigned long)                                     */
  79 /*           1. No overflow interruption                             */
  80 /*           2. i*j = i*j mod max(unsigned long)                     */
  81 /*                                                                   */
  82 /* This assumption is true for a lot of computers.                   */
  83 /* If your computer fails:                                           */
  84 /*   rename: irand <---> xrand                                       */
  85 /*                                                                   */
  86 /*********************************************************************/
  87
  88 #define  A   1220703125
  89 #define  B   2147483647
  90 #define  BF  2147483647.
  91
  92 static long irand ()
  93
  94 { internal_seed = ( internal_seed * A ) & B;
  95   return (long) internal_seed ;
  96 }
  97
  98 #if 0 /* Not used. */
  99 /*********************************************************************/
 100 /*                                                                   */
 101 /*              computer independent variant of  irand               */
 102 /*                                                                   */
 103 /*********************************************************************/
 104
 105
 106 #define T15  32768
 107 #define T16  65536
 108 #define A1   37252
 109 #define A2   29589
 110
 111 static long xrand()
 112
 113 { unsigned long is1, is2;
 114
 115   is1 = internal_seed / T15;
 116   is2 = internal_seed % T15;
 117
 118   internal_seed = ( (((is2 * A1) + (is1 * A2))% T16 )* T15 + (is2 * A2) ) & B;
 119   return (long) ( internal_seed ) ;
 120 }
 121 #endif
 122
 123 /*********************************************************************/
 124
 125
 126 double rand01()
 127
 128 { return  (double) (irand() / BF) ;
 129 }
 130
 131 /*********************************************************************/
 132
 133 #define NK  12
 134
 135 double randg01()
 136
 137 { int i;
 138   double sum = 0;
 139
 140   for ( i = 0; i < NK; i++ ) sum += rand01();
 141   return sum - 6.;
 142
 143   /* if   NK != 12  then you must return (12/NK)*sum - (NK/2) */
 144 }
 145
 146 #undef NK
 147
 148
 149 /*********************************************************************/
 150
 151 long nrand ( n )
 152
 153 long n;
 154
 155 { return (long) ( rand01() * (double) n );
 156 }
 157
 158 /*********************************************************************/
 159
 160 #undef A
 161 #undef A1
 162 #undef A2
 163 #undef B
 164 #undef BF
 165 #undef T15
 166 #undef T16