Possible Speed-up in real number generation

Backe to Mersenne Twister in C, C++

Wouter Kager kindly gave us a mail about "Possible Speed-up in real number generation."


For some platforms and compilers, the generation of real-valued random numbers can be speeded up significantly by casting the generated random integers to signed integers before converting to double. The reason for this is that many processors can only load signed (and not unsigned) integers directly to the floating-point unit. The following alternatives of the genrand_real functions may therefore be more efficient in some implementations:

/* generates a random number on [0,1]-real-interval */
double genrand_real1(void)
{
  unsigned long y = genrand_int32();
  return (double)((int)y) * (1.0/4294967295.0)
    + (0.5 + 0.5/4294967295.0);
}

/* generates a random number on [0,1)-real-interval */
double genrand_real2(void)
{
  unsigned long y = genrand_int32();
  return (double)((int)y) * (1.0/4294967296.0) + 0.5;
}

/* generates a random number on (0,1)-real-interval */
double genrand_real3(void)
{
  unsigned long y = genrand_int32();
  return (double)((int)y) * (1.0/4294967296.0)
    + (0.5 + 0.5/4294967296.0);
}

For higher-precision random numbers, the following alternatives may be worth considering:

/* generates a random number on [0,1) with 53-bit resolution */
double genrand_res53(void)
{
  long a = (long)(genrand_int32()>>5);
  long b = (long)(genrand_int32()>>6);
  return(a*67108864.0+b)*(1.0/9007199254740992.0);
}

/* generates a random number on [0,1) with 63-bit resolution */
long double genrand_res63(void)
{
  long a = (long)genrand_int32();
  long b = (long)genrand_int32();
  return (long double)(a * (1.0/4294967296.0))
    + (long double)(b * (1.0/18446744073709551616.0))
    + (0.5 + 0.5/4294967296.0);
}

To get an idea of the possible speed improvement, here are the results from a test of the number of seconds it takes to generate 2 billion random numbers (1 billion for genrand_res53) on a Pentium D processor using the gcc compiler (optimization -O2):

 genrand_real1 genrand_real2  genrand_real3 genrand_res53
original67.9467.94 72.8468.89
alternative33.5933.61 33.5932.89

This is (independently and previously) discovered by Jurgen A Doornik

Doornik, J. A. 2007. Conversion of high-period random numbers to floating point. ACM Trans. Model. Comput. Simul. 17, 1 (Jan. 2007), 3. DOI=http://doi.acm.org/10.1145/1189756.1189759
Backe to Mersenne Twister in C, C++