Random number generators discussion

Random number generators | www.agner.org

 
thread What happened to RanRot? - Carlos Cordoba - 2009-12-12
last reply What happened to RanRot? - Agner - 2009-12-15
 
What happened to RanRot?
Author:  Date: 2009-12-12 17:31
Hi Agner,

I was looking for new versions of your algorithms and I found that you no longer distribute RanRot. I've been using it in the past with very good results so I wonder why you discontinued it. Is it something wrong with it?

Thanks for your help,
Carlos

   
What happened to RanRot?
Author: Agner Date: 2009-12-15 09:09
You can still use the RANROT generator, but it is no longer included in my random number generator library.

When designing a pseudo random number generator, there is a dilemma between making a very chaotic system or making a system that is easy to analyze theoretically. Many theorists prefer the Mersenne Twister type of generators because the theory is well understood and the properties can be analyzed theoretically. However, the simpler theoretical structure is also a weakness. All Mersenne Twister type generators fail certain tests for randomness (Linear complexity test and binary matrix rank test with sufficiently large matrix). The RANROT generator passes these tests. Since the RANROT has a more chaotic structure it is also more difficult to analyze theoretically. If the RANROT was better understood it migt also be possible to construct a test that it fails.

The RANROT generator doesn't fit well into the SIMD/vector instructions of modern PCs. Therefore, it is not as fast as the new "SIMD-oriented Fast Mersenne Twister" (SFMT). The weakness of the SFMT generator with respect to the abovementioned tests can be compensated for by combining it with the Mother-Of-All generator.

I have provided the theoretical description of the RANROT generator at www.agner.org/random/theory/chaosran.pdf

Here is a simple C++ implementation of a RANROT generator:

// RANROT generator type B, by Agner Fog
#include <string.h>  // some compilers require <mem.h> instead
#include <stdio.h>
#include <stdlib.h>
#include <intrin.h>  // if not found, use definition of _lrotl below

typedef unsigned int uint32;  // Define 32-bit unsigned integer

// If your system doesn't have the intrin.h header file defining a 
// rotate function for 32 bits integers, then use the definition below. 
// uint32 _lrotl (uint32 x, int r) {
//   return (x << r) | (x >> (sizeof(x)*8-r));}

class TRanrotBGenerator {              // encapsulate random number generator
  enum constants {                     // define parameters
    KK = 17, JJ = 10, R1 = 13, R2 =  9};
  public:
  void RandomInit(uint32 seed);        // initialization
  int IRandom(int min, int max);       // get integer random number in desired interval
  double Random();                     // get floating point random number
  TRanrotBGenerator(uint32 seed);      // constructor
  protected:
  int p1, p2;                          // indexes into buffer
  uint32 randbuffer[KK];               // history buffer
  uint32 randbufcopy[KK*2];            // used for self-test
};


// constructor:
TRanrotBGenerator::TRanrotBGenerator(uint32 seed) {
  RandomInit(seed);
  }


// returns a random number between 0 and 1:
double TRanrotBGenerator::Random() {
  uint32 x;
  // generate next random number
  x = randbuffer[p1] = _lrotl(randbuffer[p2], R1) + _lrotl(randbuffer[p1], R2);
  // rotate list pointers
  if (--p1 < 0) p1 = KK - 1;
  if (--p2 < 0) p2 = KK - 1;
  // perform self-test
  if (randbuffer[p1] == randbufcopy[0] &&
    memcmp(randbuffer, randbufcopy+KK-p1, KK*sizeof(uint32)) == 0) {
      // self-test failed
      if ((p2 + KK - p1) % KK != JJ) {
        // note: the way of printing error messages depends on system
        // In Windows you may use FatalAppExit
        printf("Random number generator not initialized");}
      else {
        printf("Random number generator returned to initial state");}
      exit(1);}
  // conversion to float:
  return (double)x * (1./((double)(uint32)(-1L)+1.));}


// returns integer random number in desired interval:
int TRanrotBGenerator::IRandom(int min, int max) {
  int iinterval = max - min + 1;
  if (iinterval <= 0) return 0x80000000; // error
  int i = (int)(iinterval * Random()); // truncate
  if (i >= iinterval) i = iinterval-1;
  return min + i;}
  

void TRanrotBGenerator::RandomInit (uint32 seed) {
  // this function initializes the random number generator.
  int i;
  uint32 s = seed;

  // make random numbers and put them into the buffer
  for (i = 0; i < KK; i++) {
    s = s * 2891336453 + 1;
    randbuffer[i] = s;}

  // initialize pointers to circular buffer
  p1 = 0;  p2 = JJ;
  // store state for self-test
  memcpy (randbufcopy, randbuffer, KK*sizeof(uint32));
  memcpy (randbufcopy+KK, randbuffer, KK*sizeof(uint32));
  // randomize some more
  for (i = 0; i < 9; i++)  Random();
}

// Example of use:
int main() {
   TRanrotBGenerator ran(12345);

   for (int i = 0; i < 100; i++) {
      printf("  %6i", ran.IRandom(0,99));
   }
   printf("\n");
   return 0;
}