src/gmxlib/gmx_random.c

   1 /*
   2  * This file is part of the GROMACS molecular simulation package.
   3  *
   4  * Copyright (c) 1991-2000, University of Groningen, The Netherlands.
   5  * Copyright (c) 2001-2008, The GROMACS development team,
   6  * check out http://www.gromacs.org for more information.
   7  * Copyright (c) 2012, by the GROMACS development team, led by
   8  * David van der Spoel, Berk Hess, Erik Lindahl, and including many
   9  * others, as listed in the AUTHORS file in the top-level source
  10  * directory and at http://www.gromacs.org.
  11  *
  12  * GROMACS is free software; you can redistribute it and/or
  13  * modify it under the terms of the GNU Lesser General Public License
  14  * as published by the Free Software Foundation; either version 2.1
  15  * of the License, or (at your option) any later version.
  16  *
  17  * GROMACS is distributed in the hope that it will be useful,
  18  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  19  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  20  * Lesser General Public License for more details.
  21  *
  22  * You should have received a copy of the GNU Lesser General Public
  23  * License along with GROMACS; if not, see
  24  * http://www.gnu.org/licenses, or write to the Free Software Foundation,
  25  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA.
  26  *
  27  * If you want to redistribute modifications to GROMACS, please
  28  * consider that scientific software is very special. Version
  29  * control is crucial - bugs must be traceable. We will be happy to
  30  * consider code for inclusion in the official distribution, but
  31  * derived work must not be called official GROMACS. Details are found
  32  * in the README & COPYING files - if they are missing, get the
  33  * official version at http://www.gromacs.org.
  34  *
  35  * To help us fund GROMACS development, we humbly ask that you cite
  36  * the research papers on the package. Check out http://www.gromacs.org.
  37  */
  38 #ifdef HAVE_CONFIG_H
  39 #include <config.h>
  40 #endif
  41 #include "gmx_header_config.h"
  42
  43 #include <gmx_random.h>
  44
  45 #include <stdio.h>
  46 #include <stdlib.h>
  47 #ifdef HAVE_UNISTD_H
  48 #include <unistd.h>
  49 #endif
  50 #include <time.h>
  51 #include <math.h>
  52 #ifdef GMX_NATIVE_WINDOWS
  53 #include <process.h>
  54 #endif
  55
  56 #include "maths.h"
  57 #include "gmx_random_gausstable.h"
  58
  59 #define RNG_N 624
  60 #define RNG_M 397
  61 #define RNG_MATRIX_A 0x9908b0dfUL   /* constant vector a */
  62 #define RNG_UPPER_MASK 0x80000000UL /* most significant w-r bits */
  63 #define RNG_LOWER_MASK 0x7fffffffUL /* least significant r bits */
  64
  65 /* Note that if you change the size of the Gaussian table you will also
  66  * have to generate new initialization data for the table in
  67  * gmx_random_gausstable.h
  68  *
  69  * A routine print_gaussian_table() is in contrib/random.c
  70  * for convenience - use it if you need a different size of the table.
  71  */
  72 #define GAUSS_TABLE 14 /* the size of the gauss table is 2^GAUSS_TABLE */
  73 #define GAUSS_SHIFT (32 - GAUSS_TABLE)
  74
  75
  76 struct gmx_rng {
  77   unsigned int  mt[RNG_N];
  78   int           mti;
  79   int           has_saved;
  80   double        gauss_saved;
  81 };
  82
  83
  84
  85 int
  86 gmx_rng_n(void)
  87 {
  88   return RNG_N;
  89 }
  90
  91
  92 gmx_rng_t
  93 gmx_rng_init(unsigned int seed)
  94 {
  95   struct gmx_rng *rng;
  96
  97   if((rng=(struct gmx_rng *)malloc(sizeof(struct gmx_rng)))==NULL)
  98         return NULL;
  99
 100   rng->has_saved=0; /* no saved gaussian number yet */
 101
 102   rng->mt[0]= seed & 0xffffffffUL;
 103   for (rng->mti=1; rng->mti<RNG_N; rng->mti++) {
 104     rng->mt[rng->mti] =
 105       (1812433253UL * (rng->mt[rng->mti-1] ^
 106                        (rng->mt[rng->mti-1] >> 30)) + rng->mti);
 107     /* See Knuth TAOCP Vol2. 3rd Ed. P.106 for multiplier. */
 108     /* In the previous versions, MSBs of the seed affect   */
 109     /* only MSBs of the array mt[].                        */
 110     /* 2002/01/09 modified by Makoto Matsumoto             */
 111     rng->mt[rng->mti] &= 0xffffffffUL;
 112     /* for >32 bit machines */
 113   }
 114   return rng;
 115 }
 116
 117 gmx_rng_t
 118 gmx_rng_init_array(unsigned int seed[], int seed_length)
 119 {
 120     int i, j, k;
 121     gmx_rng_t rng;
 122
 123     if((rng=gmx_rng_init(19650218UL))==NULL)
 124           return NULL;
 125
 126     i=1; j=0;
 127     k = (RNG_N>seed_length ? RNG_N : seed_length);
 128     for (; k; k--) {
 129         rng->mt[i] = (rng->mt[i] ^ ((rng->mt[i-1] ^
 130                                      (rng->mt[i-1] >> 30)) * 1664525UL))
 131           + seed[j] + j; /* non linear */
 132         rng->mt[i] &= 0xffffffffUL; /* for WORDSIZE > 32 machines */
 133         i++; j++;
 134         if (i>=RNG_N) { rng->mt[0] = rng->mt[RNG_N-1]; i=1; }
 135         if (j>=seed_length) j=0;
 136     }
 137     for (k=RNG_N-1; k; k--) {
 138         rng->mt[i] = (rng->mt[i] ^ ((rng->mt[i-1] ^
 139                                      (rng->mt[i-1] >> 30)) *
 140                                     1566083941UL))
 141           - i; /* non linear */
 142         rng->mt[i] &= 0xffffffffUL; /* for WORDSIZE > 32 machines */
 143         i++;
 144         if (i>=RNG_N) { rng->mt[0] = rng->mt[RNG_N-1]; i=1; }
 145     }
 146
 147     rng->mt[0] = 0x80000000UL;
 148     /* MSB is 1; assuring non-zero initial array */
 149     return rng;
 150 }
 151
 152
 153 void
 154 gmx_rng_destroy(gmx_rng_t rng)
 155 {
 156   if(rng)
 157     free(rng);
 158 }
 159
 160
 161 void
 162 gmx_rng_get_state(gmx_rng_t rng, unsigned int *mt,int *mti)
 163 {
 164   int i;
 165
 166   for(i=0; i<RNG_N; i++) {
 167     mt[i] = rng->mt[i];
 168   }
 169   *mti = rng->mti;
 170 }
 171
 172
 173 void
 174 gmx_rng_set_state(gmx_rng_t rng,  unsigned int *mt,int mti)
 175 {
 176   int i;
 177
 178   for(i=0; i<RNG_N; i++) {
 179     rng->mt[i] = mt[i];
 180   }
 181   rng->mti = mti;
 182 }
 183
 184
 185 unsigned int
 186 gmx_rng_make_seed(void)
 187 {
 188   FILE *fp;
 189   unsigned int data;
 190   int ret;
 191   long my_pid;
 192
 193 #ifdef HAVE_UNISTD_H
 194   fp=fopen("/dev/random","rb"); /* will return NULL if it is not present */
 195 #else
 196   fp=NULL;
 197 #endif
 198   if(fp!=NULL) {
 199     ret=fread(&data,sizeof(unsigned int),1,fp);
 200     fclose(fp);
 201   } else {
 202     /* No random device available, use time-of-day and process id */
 203 #ifdef GMX_NATIVE_WINDOWS
 204     my_pid = (long)_getpid();
 205 #else
 206     my_pid = (long)getpid();
 207 #endif
 208     data=(unsigned int)(((long)time(NULL)+my_pid) % (long)1000000);
 209   }
 210   return data;
 211 }
 212
 213
 214 /* The random number state contains RNG_N entries that are returned one by
 215  * one as random numbers. When we run out of them, this routine is called to
 216  * regenerate RNG_N new entries.
 217  */
 218 static void
 219 gmx_rng_update(gmx_rng_t rng)
 220 {
 221     unsigned int lastx,x1,x2,y,*mt;
 222     int mti,k;
 223     const unsigned int mag01[2] = {0x0UL, RNG_MATRIX_A};
 224     /* mag01[x] = x * MATRIX_A  for x=0,1 */
 225
 226     /* update random numbers */
 227     mt = rng->mt;   /* pointer to array - avoid repeated dereferencing */
 228     mti = rng->mti;
 229
 230     x1        = mt[0];
 231     for (k = 0; k < RNG_N-RNG_M-3; k += 4)
 232     {
 233         x2      = mt[k+1];
 234         y       = (x1 & RNG_UPPER_MASK) | (x2 & RNG_LOWER_MASK);
 235         mt[k]   = mt[k+RNG_M]   ^ (y >> 1) ^ mag01[y & 0x1UL];
 236         x1      = mt[k+2];
 237         y       = (x2 & RNG_UPPER_MASK) | (x1 & RNG_LOWER_MASK);
 238         mt[k+1] = mt[k+RNG_M+1] ^ (y >> 1) ^ mag01[y & 0x1UL];
 239         x2      = mt[k+3];
 240         y       = (x1 & RNG_UPPER_MASK) | (x2 & RNG_LOWER_MASK);
 241         mt[k+2] = mt[k+RNG_M+2] ^ (y >> 1) ^ mag01[y & 0x1UL];
 242         x1      = mt[k+4];
 243         y       = (x2 & RNG_UPPER_MASK) | (x1 & RNG_LOWER_MASK);
 244         mt[k+3] = mt[k+RNG_M+3] ^ (y >> 1) ^ mag01[y & 0x1UL];
 245     }
 246     x2        = mt[k+1];
 247     y         = (x1 & RNG_UPPER_MASK) | (x2 & RNG_LOWER_MASK);
 248     mt[k]     = mt[k+RNG_M] ^ (y >> 1) ^ mag01[y & 0x1UL];
 249     k++;
 250     x1        = mt[k+1];
 251     y         = (x2 & RNG_UPPER_MASK) | (x1 & RNG_LOWER_MASK);
 252     mt[k]     = mt[k+RNG_M] ^ (y >> 1) ^ mag01[y & 0x1UL];
 253     k++;
 254     x2        = mt[k+1];
 255     y         = (x1 & RNG_UPPER_MASK) | (x2 & RNG_LOWER_MASK);
 256     mt[k]     = mt[k+RNG_M] ^ (y >> 1) ^ mag01[y & 0x1UL];
 257     k++;
 258     for (; k < RNG_N-1; k += 4)
 259     {
 260         x1      = mt[k+1];
 261         y       = (x2 & RNG_UPPER_MASK) | (x1 & RNG_LOWER_MASK);
 262         mt[k]   = mt[k+(RNG_M-RNG_N)]   ^ (y >> 1) ^ mag01[y & 0x1UL];
 263         x2      = mt[k+2];
 264         y       = (x1 & RNG_UPPER_MASK) | (x2 & RNG_LOWER_MASK);
 265         mt[k+1] = mt[k+(RNG_M-RNG_N)+1] ^ (y >> 1) ^ mag01[y & 0x1UL];
 266         x1      = mt[k+3];
 267         y       = (x2 & RNG_UPPER_MASK) | (x1 & RNG_LOWER_MASK);
 268         mt[k+2] = mt[k+(RNG_M-RNG_N)+2] ^ (y >> 1) ^ mag01[y & 0x1UL];
 269         x2      = mt[k+4];
 270         y       = (x1 & RNG_UPPER_MASK) | (x2 & RNG_LOWER_MASK);
 271         mt[k+3] = mt[k+(RNG_M-RNG_N)+3] ^ (y >> 1) ^ mag01[y & 0x1UL];
 272     }
 273     y = (x2 & RNG_UPPER_MASK) | (mt[0] & RNG_LOWER_MASK);
 274     mt[RNG_N-1] = mt[RNG_M-1] ^ (y >> 1) ^ mag01[y & 0x1UL];
 275
 276     rng->mti = 0;
 277 }
 278
 279
 280 real
 281 gmx_rng_gaussian_real(gmx_rng_t rng)
 282 {
 283   real x,y,r;
 284
 285   if(rng->has_saved) {
 286     rng->has_saved=0;
 287     return rng->gauss_saved;
 288   } else {
 289     do {
 290       x=2.0*gmx_rng_uniform_real(rng)-1.0;
 291       y=2.0*gmx_rng_uniform_real(rng)-1.0;
 292       r=x*x+y*y;
 293     } while(r>1.0 || r==0.0);
 294
 295     r=sqrt(-2.0*log(r)/r);
 296     rng->gauss_saved=y*r; /* save second random number */
 297     rng->has_saved=1;
 298     return x*r; /* return first random number */
 299   }
 300 }
 301
 302
 303
 304
 305 /* Return a random unsigned integer, i.e. 0..4294967295
 306  * Provided in header file for performace reasons.
 307  * Unfortunately this function cannot be inlined, since
 308  * it needs to refer the internal-linkage gmx_rng_update().
 309  */
 310 unsigned int
 311 gmx_rng_uniform_uint32(gmx_rng_t rng)
 312 {
 313   unsigned int y;
 314
 315   if(rng->mti==RNG_N)
 316     gmx_rng_update(rng);
 317   y=rng->mt[rng->mti++];
 318
 319   y ^= (y >> 11);
 320   y ^= (y << 7) & 0x9d2c5680UL;
 321   y ^= (y << 15) & 0xefc60000UL;
 322   y ^= (y >> 18);
 323
 324   return y;
 325 }
 326
 327
 328
 329
 330
 331 /* Return a uniform floating point number on the interval 0<=x<1 */
 332 real
 333 gmx_rng_uniform_real(gmx_rng_t rng)
 334 {
 335   if(sizeof(real)==sizeof(double))
 336     return ((double)gmx_rng_uniform_uint32(rng))*(1.0/4294967296.0);
 337   else
 338     return ((float)gmx_rng_uniform_uint32(rng))*(1.0/4294967423.0);
 339   /* divided by the smallest number that will generate a
 340     * single precision real number on 0<=x<1.
 341     * This needs to be slightly larger than MAX_UNIT since
 342     * we are limited to an accuracy of 1e-7.
 343     */
 344 }
 345
 346
 347
 348 real
 349 gmx_rng_gaussian_table(gmx_rng_t rng)
 350 {
 351   unsigned int i;
 352
 353   i = gmx_rng_uniform_uint32(rng);
 354
 355   /* The Gaussian table is a static constant in this file */
 356   return gaussian_table[i >> GAUSS_SHIFT];
 357 }
 358
 359