In 1999, George Marsaglia posted a number of random-number generator on several mailing lists. They are defined as C macros, and use eleven global variables, of which eight are just a single letter. I have made them ito a C++ class containing inline functions. Here is the long but narrow header file:
# pragma once
class Marsaglia {
public:
typedef int int32;
typedef unsigned uint32;
typedef unsigned char uchar;
inline uint32 shr3() { //--- Period 2^32
jsr ^= (jsr << 17);
jsr ^= (jsr >> 13);
jsr ^= (jsr << 5);
return jsr;
}
inline uint32 mwc() { //--- Period 2^60
return (_znew()<<16) + _wnew();
}
inline uint32 kiss() { //--- Period 2^123
return (mwc()^cong()) + shr3();
}
inline uint32 lfib4() { //--- Period 2^287
c++;
table[c] += table[uc(c+ 58)];
table[c] += table[uc(c+119)];
table[c] += table[uc(c+178)];
return table[c];
}
inline uint32 swb() { //--- Period 2^7578
c++;
bro = (x<y);
y = table[uc(c+19)]+bro;
x = table[uc(c+34)];
table[c] = x-y;
return table[c];
}
inline double uni() {
return (kiss()*2.328306e-10);
}
inline double vni() {
return ((int32)kiss())*4.656613e-10;
}
void settable(); //--- Uses rand() for seeding
void settable(uint32 z, uint32 w, uint32 jsr,
uint32 jcong, uint32 a, uint32 b);
void set_xybroc(uint32 x = 0, uint32 y = 0,
uint32 bro = 0, uint32 c = 0);
public:
//--- cong() and fib() should probably not be used
//--- directly, so should be private. However, the test
//--- program marsaglia-main.cc uses them. Read
//--- Marsaglia's comments, below, before using them
//--- directly
inline uint32 cong() {
return (jcong = 69069*jcong+1234567);
}
inline uint32 fib() {
return ((b = a+b),(a = b-a));
}
private:
inline uchar uc(uint32 v) { return v; } //--- Implicit cast
inline uint32 _znew() {
z = 36969 * (z & 65535) + (z >> 16);
return z;
}
inline uint32 _wnew() {
w = 18000 * (w & 65535) + (w >> 16);
return w;
}
private:
uint32 z = 362436069; // _znew, mwc -> kiss
uint32 w = 521288629; // _wnew, mwc -> kiss
uint32 jsr = 123456789; // shr3 -> kiss
uint32 jcong = 380116160; // cong -> kiss
uint32 a = 224466889; // fib
uint32 b = 7584631; // fib
// !!! Warning: table[] is not initialized; see settable()
uint32 table[256]; // swb, lfib4
uint32 x = 0; // swb
uint32 y = 0; // swb
uint32 bro = 0; // swb
uchar c = 0; // swb, lfib4
};
The interesting part is the first five random-number generators.
| shr3 | Three shifts, with a period of 2^32-1. |
| mwc | Multiply With Carry, with a period of about 2^60. |
| kiss | Keep It Simple Stupid, with a period of about 2^123 |
| lfib4 | Lagged Fibonacci, with a period of about 2^287 |
| swb | Subtract with borrow. Has a very long period: about 2^7578. |
The remaining generators are not recommended for direct use, but are used by the five generators above.
How about execution times? Each generators has been tested by running it 10^9 times. This has been repeatd ten times, and the result sorted. The two sortest and the two longest times have been dropped, and the remaining six values have been averaged.
Each generator has been instantiated in four different ways
| As a static object | An instance of class Marsaglia declared as a file-static variable. |
| As an extern object | An instance of class Marsaglia defined in another compilation unit. |
| As a stack object | An instance of class Marsaglia defined local to a function. |
| As a namespace | Using a rewrite of class Marsaglia as a namespace. This, of course, is not an object at all. |
The generators are ordered by increasing period. The tag M: in the plot identifies Marsaglia RNGs. In the next plot, there will be some other RNGs as well
Time was measured using the C++ library in std::chrono. The details are in the
As can be seen from the table, it really does not matter how the class is instantiated. Variations are withing the margin of error, and another compiler may give different results. The tests were compiled with GCC 9.1.0 with option -O3.
The times in this plot are relative, not absolute. On my Intel box running at 2.4 MHz, the fastest generator takes about 3 nanoseconds per iteration.
Download
The source is available for download. Files include
| Makefile | Build marsaglia-expect.elf, and marsaglia-main.elf |
| marsaglia.h | Class definition, including all inline member functions. |
| marsaglia.cc | The remaining, non-inlined, functions. |
| marsaglia-namespace.h | The Marsaglia class rewritten as a namespace. For performance testing. |
| marsaglia-main.cc | Program to verify correctness of class Marsaglia. |
| marsaglia-expect.c | Original code, slightly modified to print results instead of zeroes. Output, which is assumed to be correct, is pasted into marsaglia-main.cc. |
| marsaglia-rng.html | Marsaglia’s 1999 post. |
| rngs/rngs.cc | Run and time one of the 20+ RNG variation. |
| rngs/rngs.sh | Run all or some RNG variations |
| rngs/Makefile | |
| rngs/README | Do read this. |
| rngs/lib.h | Utilities for measuring time |
| rngs/lib.cc | … implementation |
| rngs/mext.cc | Contains an instance of class Marsaglia, used by rngs.cc. |
You can reach me by email at “lars dash 7 at sdu dot se” or by telephone +46 705 189090