Marsaglia random numbers

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

View source for the content of this page.