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,2013, 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
  42 #include <gmx_random.h>
  43
  44 #include <stdio.h>
  45 #include <stdlib.h>
  46 #ifdef HAVE_UNISTD_H
  47 #include <unistd.h>
  48 #endif
  49 #include <time.h>
  50 #include <math.h>
  51 #ifdef GMX_NATIVE_WINDOWS
  52 #include <process.h>
  53 #endif
  54
  55 #include "maths.h"
  56 #include "gmx_random_gausstable.h"
  57
  58 #define RNG_N 624
  59 #define RNG_M 397
  60 #define RNG_MATRIX_A 0x9908b0dfUL   /* constant vector a */
  61 #define RNG_UPPER_MASK 0x80000000UL /* most significant w-r bits */
  62 #define RNG_LOWER_MASK 0x7fffffffUL /* least significant r bits */
  63
  64 /* Note that if you change the size of the Gaussian table you will also
  65  * have to generate new initialization data for the table in
  66  * gmx_random_gausstable.h
  67  *
  68  * A routine print_gaussian_table() is in contrib/random.c
  69  * for convenience - use it if you need a different size of the table.
  70  */
  71 #define GAUSS_TABLE 14 /* the size of the gauss table is 2^GAUSS_TABLE */
  72 #define GAUSS_SHIFT (32 - GAUSS_TABLE)
  73
  74
  75 struct gmx_rng {
  76   unsigned int  mt[RNG_N];
  77   int           mti;
  78   int           has_saved;
  79   double        gauss_saved;
  80 };
  81
  82
  83
  84 int
  85 gmx_rng_n(void)
  86 {
  87   return RNG_N;
  88 }
  89
  90
  91 gmx_rng_t
  92 gmx_rng_init(unsigned int seed)
  93 {
  94   struct gmx_rng *rng;
  95
  96   if((rng=(struct gmx_rng *)malloc(sizeof(struct gmx_rng)))==NULL)
  97         return NULL;
  98
  99   rng->has_saved=0; /* no saved gaussian number yet */
 100
 101   rng->mt[0]= seed & 0xffffffffUL;
 102   for (rng->mti=1; rng->mti<RNG_N; rng->mti++) {
 103     rng->mt[rng->mti] =
 104       (1812433253UL * (rng->mt[rng->mti-1] ^
 105                        (rng->mt[rng->mti-1] >> 30)) + rng->mti);
 106     /* See Knuth TAOCP Vol2. 3rd Ed. P.106 for multiplier. */
 107     /* In the previous versions, MSBs of the seed affect   */
 108     /* only MSBs of the array mt[].                        */
 109     /* 2002/01/09 modified by Makoto Matsumoto             */
 110     rng->mt[rng->mti] &= 0xffffffffUL;
 111     /* for >32 bit machines */
 112   }
 113   return rng;
 114 }
 115
 116 gmx_rng_t
 117 gmx_rng_init_array(unsigned int seed[], int seed_length)
 118 {
 119     int i, j, k;
 120     gmx_rng_t rng;
 121
 122     if((rng=gmx_rng_init(19650218UL))==NULL)
 123           return NULL;
 124
 125     i=1; j=0;
 126     k = (RNG_N>seed_length ? RNG_N : seed_length);
 127     for (; k; k--) {
 128         rng->mt[i] = (rng->mt[i] ^ ((rng->mt[i-1] ^
 129                                      (rng->mt[i-1] >> 30)) * 1664525UL))
 130           + seed[j] + j; /* non linear */
 131         rng->mt[i] &= 0xffffffffUL; /* for WORDSIZE > 32 machines */
 132         i++; j++;
 133         if (i>=RNG_N) { rng->mt[0] = rng->mt[RNG_N-1]; i=1; }
 134         if (j>=seed_length) j=0;
 135     }
 136     for (k=RNG_N-1; k; k--) {
 137         rng->mt[i] = (rng->mt[i] ^ ((rng->mt[i-1] ^
 138                                      (rng->mt[i-1] >> 30)) *
 139                                     1566083941UL))
 140           - i; /* non linear */
 141         rng->mt[i] &= 0xffffffffUL; /* for WORDSIZE > 32 machines */
 142         i++;
 143         if (i>=RNG_N) { rng->mt[0] = rng->mt[RNG_N-1]; i=1; }
 144     }
 145
 146     rng->mt[0] = 0x80000000UL;
 147     /* MSB is 1; assuring non-zero initial array */
 148     return rng;
 149 }
 150
 151
 152 void
 153 gmx_rng_destroy(gmx_rng_t rng)
 154 {
 155   if(rng)
 156     free(rng);
 157 }
 158
 159
 160 void
 161 gmx_rng_get_state(gmx_rng_t rng, unsigned int *mt,int *mti)
 162 {
 163   int i;
 164
 165   for(i=0; i<RNG_N; i++) {
 166     mt[i] = rng->mt[i];
 167   }
 168   *mti = rng->mti;
 169 }
 170
 171
 172 void
 173 gmx_rng_set_state(gmx_rng_t rng,  unsigned int *mt,int mti)
 174 {
 175   int i;
 176
 177   for(i=0; i<RNG_N; i++) {
 178     rng->mt[i] = mt[i];
 179   }
 180   rng->mti = mti;
 181 }
 182
 183
 184 unsigned int
 185 gmx_rng_make_seed(void)
 186 {
 187   FILE *fp;
 188   unsigned int data;
 189   int ret;
 190   long my_pid;
 191
 192 #ifdef HAVE_UNISTD_H
 193   fp=fopen("/dev/random","rb"); /* will return NULL if it is not present */
 194 #else
 195   fp=NULL;
 196 #endif
 197   if(fp!=NULL) {
 198     ret=fread(&data,sizeof(unsigned int),1,fp);
 199     fclose(fp);
 200   } else {
 201     /* No random device available, use time-of-day and process id */
 202 #ifdef GMX_NATIVE_WINDOWS
 203     my_pid = (long)_getpid();
 204 #else
 205     my_pid = (long)getpid();
 206 #endif
 207     data=(unsigned int)(((long)time(NULL)+my_pid) % (long)1000000);
 208   }
 209   return data;
 210 }
 211
 212
 213 /* The random number state contains RNG_N entries that are returned one by
 214  * one as random numbers. When we run out of them, this routine is called to
 215  * regenerate RNG_N new entries.
 216  */
 217 static void
 218 gmx_rng_update(gmx_rng_t rng)
 219 {
 220     unsigned int lastx,x1,x2,y,*mt;
 221     int mti,k;
 222     const unsigned int mag01[2] = {0x0UL, RNG_MATRIX_A};
 223     /* mag01[x] = x * MATRIX_A  for x=0,1 */
 224
 225     /* update random numbers */
 226     mt = rng->mt;   /* pointer to array - avoid repeated dereferencing */
 227     mti = rng->mti;
 228
 229     x1        = mt[0];
 230     for (k = 0; k < RNG_N-RNG_M-3; k += 4)
 231     {
 232         x2      = mt[k+1];
 233         y       = (x1 & RNG_UPPER_MASK) | (x2 & RNG_LOWER_MASK);
 234         mt[k]   = mt[k+RNG_M]   ^ (y >> 1) ^ mag01[y & 0x1UL];
 235         x1      = mt[k+2];
 236         y       = (x2 & RNG_UPPER_MASK) | (x1 & RNG_LOWER_MASK);
 237         mt[k+1] = mt[k+RNG_M+1] ^ (y >> 1) ^ mag01[y & 0x1UL];
 238         x2      = mt[k+3];
 239         y       = (x1 & RNG_UPPER_MASK) | (x2 & RNG_LOWER_MASK);
 240         mt[k+2] = mt[k+RNG_M+2] ^ (y >> 1) ^ mag01[y & 0x1UL];
 241         x1      = mt[k+4];
 242         y       = (x2 & RNG_UPPER_MASK) | (x1 & RNG_LOWER_MASK);
 243         mt[k+3] = mt[k+RNG_M+3] ^ (y >> 1) ^ mag01[y & 0x1UL];
 244     }
 245     x2        = mt[k+1];
 246     y         = (x1 & RNG_UPPER_MASK) | (x2 & RNG_LOWER_MASK);
 247     mt[k]     = mt[k+RNG_M] ^ (y >> 1) ^ mag01[y & 0x1UL];
 248     k++;
 249     x1        = mt[k+1];
 250     y         = (x2 & RNG_UPPER_MASK) | (x1 & RNG_LOWER_MASK);
 251     mt[k]     = mt[k+RNG_M] ^ (y >> 1) ^ mag01[y & 0x1UL];
 252     k++;
 253     x2        = mt[k+1];
 254     y         = (x1 & RNG_UPPER_MASK) | (x2 & RNG_LOWER_MASK);
 255     mt[k]     = mt[k+RNG_M] ^ (y >> 1) ^ mag01[y & 0x1UL];
 256     k++;
 257     for (; k < RNG_N-1; k += 4)
 258     {
 259         x1      = mt[k+1];
 260         y       = (x2 & RNG_UPPER_MASK) | (x1 & RNG_LOWER_MASK);
 261         mt[k]   = mt[k+(RNG_M-RNG_N)]   ^ (y >> 1) ^ mag01[y & 0x1UL];
 262         x2      = mt[k+2];
 263         y       = (x1 & RNG_UPPER_MASK) | (x2 & RNG_LOWER_MASK);
 264         mt[k+1] = mt[k+(RNG_M-RNG_N)+1] ^ (y >> 1) ^ mag01[y & 0x1UL];
 265         x1      = mt[k+3];
 266         y       = (x2 & RNG_UPPER_MASK) | (x1 & RNG_LOWER_MASK);
 267         mt[k+2] = mt[k+(RNG_M-RNG_N)+2] ^ (y >> 1) ^ mag01[y & 0x1UL];
 268         x2      = mt[k+4];
 269         y       = (x1 & RNG_UPPER_MASK) | (x2 & RNG_LOWER_MASK);
 270         mt[k+3] = mt[k+(RNG_M-RNG_N)+3] ^ (y >> 1) ^ mag01[y & 0x1UL];
 271     }
 272     y = (x2 & RNG_UPPER_MASK) | (mt[0] & RNG_LOWER_MASK);
 273     mt[RNG_N-1] = mt[RNG_M-1] ^ (y >> 1) ^ mag01[y & 0x1UL];
 274
 275     rng->mti = 0;
 276 }
 277
 278
 279 real
 280 gmx_rng_gaussian_real(gmx_rng_t rng)
 281 {
 282   real x,y,r;
 283
 284   if(rng->has_saved) {
 285     rng->has_saved=0;
 286     return rng->gauss_saved;
 287   } else {
 288     do {
 289       x=2.0*gmx_rng_uniform_real(rng)-1.0;
 290       y=2.0*gmx_rng_uniform_real(rng)-1.0;
 291       r=x*x+y*y;
 292     } while(r>1.0 || r==0.0);
 293
 294     r=sqrt(-2.0*log(r)/r);
 295     rng->gauss_saved=y*r; /* save second random number */
 296     rng->has_saved=1;
 297     return x*r; /* return first random number */
 298   }
 299 }
 300
 301
 302
 303
 304 /* Return a random unsigned integer, i.e. 0..4294967295
 305  * Provided in header file for performace reasons.
 306  * Unfortunately this function cannot be inlined, since
 307  * it needs to refer the internal-linkage gmx_rng_update().
 308  */
 309 unsigned int
 310 gmx_rng_uniform_uint32(gmx_rng_t rng)
 311 {
 312   unsigned int y;
 313
 314   if(rng->mti==RNG_N)
 315     gmx_rng_update(rng);
 316   y=rng->mt[rng->mti++];
 317
 318   y ^= (y >> 11);
 319   y ^= (y << 7) & 0x9d2c5680UL;
 320   y ^= (y << 15) & 0xefc60000UL;
 321   y ^= (y >> 18);
 322
 323   return y;
 324 }
 325
 326
 327
 328
 329
 330 /* Return a uniform floating point number on the interval 0<=x<1 */
 331 real
 332 gmx_rng_uniform_real(gmx_rng_t rng)
 333 {
 334   if(sizeof(real)==sizeof(double))
 335     return ((double)gmx_rng_uniform_uint32(rng))*(1.0/4294967296.0);
 336   else
 337     return ((float)gmx_rng_uniform_uint32(rng))*(1.0/4294967423.0);
 338   /* divided by the smallest number that will generate a
 339     * single precision real number on 0<=x<1.
 340     * This needs to be slightly larger than MAX_UNIT since
 341     * we are limited to an accuracy of 1e-7.
 342     */
 343 }
 344
 345
 346
 347 real
 348 gmx_rng_gaussian_table(gmx_rng_t rng)
 349 {
 350   unsigned int i;
 351
 352   i = gmx_rng_uniform_uint32(rng);
 353
 354   /* The Gaussian table is a static constant in this file */
 355   return gaussian_table[i >> GAUSS_SHIFT];
 356 }
 357
 358