src/gmxlib/gmx_random.c

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