Random number generators | www.agner.org

Begin New Subject | Threaded View | Search | List | List Messageboards | Help |

What happened to RanRot? - Carlos Cordoba - 2009-12-12 |

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, |

Reply To This Message |

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; } |

Reply To This Message |

Begin New Subject | Threaded View | Search | List | List Messageboards | Help |