PRNG using a "random multiply-with-carry" algorithm.

randMulCarry.cpp

/**
 *  Testing the PRNG "Multiply with Carry" by George Marsaglia:
 *  
 *  http://en.wikipedia.org/wiki/Multiply-with-carry
 *  
 *  g++ -std=c++11 -Wall -Werror -Wextra -pedantic -pedantic-errors randMulCarry.cpp -o randMulCarry
 */

#include <algorithm>
#include <cstdint>
#include <ctime>
#include <iostream>
#include <utility>

//-----------------------------------------------------------------------------
//      PRNG Abstract Base class
//-----------------------------------------------------------------------------
/**
 *  Pseudo-Random  number abstract base class.
 */
class random {
    public:
        /**
         *  Constructor
         *  
         *  Initializes all variables.
         */
        random() = default;
        
        /**
         *  Copy Constructor
         *  
         *  Initializes the variables in *this and copies the data from the
         *  input parameter into *this.
         *  
         *  @param random
         *  A constant reference to a random object type.
         */
        random(const random&) = default;
        
        /**
         *  Move Constructor
         *  
         *  Moves all data from the input parameter into *this. No copies are
         *  performed.
         *  
         *  @param random
         *  An r-value reference to a random object type that's about to go out of
         *  scope.
         */
        random(random&&) = default;
        
        /**
         *  Pure virtual destructor to be implemented by derived classes.
         */
        virtual ~random() = 0;
        
        /**
         *  Copy Operator
         *  
         *  Copies data from the input parameter into *this.
         *  
         *  @param random
         *  A constant reference to a random object type.
         *  
         *  @return
         *  A reference to *this.
         */
        random& operator=(const random&) = default;
        
        /**
         *  Move Operator
         *  
         *  Moves all data from the input parameter into *this. No copies are
         *  performed.
         *  
         *  @param random
         *  An r-value reference to a random object type that's about to go out
         *  of scope.
         *  
         *  @return
         *  A reference to *this.
         */
        random& operator=(random&&) = default;
        
        /**
         *  Seed
         *  
         *  Seeds the build-in PRNG function and optionally allows the
         *  generation function to reset, making generated values more
         *  deterministic.
         *  
         *  @param s
         *  A 32-bit unsigned integral type that will be used to initialize the
         *  pseudo-random number generator.
         *  
         *  @param beDeterministic
         *  A boolean that will allow for this PRNG to generate the same set of
         *  pseudo-random numbers using the same seed value.
         */
        virtual void seed(const uint32_t, bool beDeterministic = true) = 0;
        
        /**
         *  Get
         *  
         *  Generates a pseudo-random number.
         *  
         *  @return
         *  A pseudo-randomly generated number, determined by derived random
         *  class objects.
         */
        virtual uint32_t get() = 0;
};

/*
 * Virtual destructor
 */
random::~random() {}

//-----------------------------------------------------------------------------
//      PRNG: Complementary Multiply With Carry
//-----------------------------------------------------------------------------
/**
 *  Complementary-Multiply-With-Carry PRNG.
 *  
 *  This implementation is based on George Marsaglia's CMWC algorithm found in
 *  the Journal of Modern Applied Statistical Methods (Vol 2, Issue 1, Article
 *  #2, pg. 9):
 *  http://digitalcommons.wayne.edu/jmasm/vol2/iss1/2
 */
template <unsigned lag_size_t = 4096>
class randomCMWC_t final : public random {
    
    static_assert(lag_size_t > 3, "A lag-size (cache size) greater than 3 is required.");
    
    private:
        /**
         *  Initial values for various variables.
         */
        enum : uint32_t {
            MEM_SIZE    = lag_size_t,
            INDEX_SIZE  = MEM_SIZE-1,
            SEED_VAL    = 123,
            RAND_MASK   = 0xFFFFFFFE
        };
        
        /**
         *  Array holding the random values
         */
        uint32_t* q;
        
        /**
         *  Computation cache for the next generated random value.
         */
        uint32_t c;
        
        /**
         *  Index variable to hold the position in the array 'q' where the next
         *  randomly generated variable will be placed.
         */
        uint32_t i;
        
    public:
        /**
         *  Constructor
         *  
         *  Generates the random-value array and initializes variables to
         *  specifically chosed magic numbers.
         */
        randomCMWC_t();
        
        /**
         *  Copy Constructor
         *  
         *  Initializes the variables in *this and copies the data from the
         *  input parameter into *this.
         *  
         *  @param randomCMWC_t
         *  A constant reference to a randomCMWC_t variable.
         */
        randomCMWC_t(const randomCMWC_t&);
        
        /**
         *  Move Constructor
         *  
         *  Moves all data from the input parameter into *this. No copies are
         *  performed.
         *  
         *  @param randomCMWC_t
         *  An r-value reference to a randomCMWC_t that's about to go out of
         *  scope.
         */
        randomCMWC_t(randomCMWC_t&&);
        
        /**
         *  Destructor
         *  
         *  Frees all memory used by the dynamically allocated random number
         *  array.
         */
        virtual ~randomCMWC_t();
        
        /**
         *  Copy Operator
         *  
         *  Copies data from the input parameter into *this.
         *  
         *  @param randomCMWC_t
         *  A constant reference to a randomCMWC_t variable.
         *  
         *  @return
         *  A reference to *this.
         */
        randomCMWC_t& operator=(const randomCMWC_t&);
        
        /**
         *  Move Operator
         *  
         *  Moves all data from the input parameter into *this. No copies are
         *  performed.
         *  
         *  @param randomCMWC_t
         *  An r-value reference to a randomCMWC_t that's about to go out of
         *  scope.
         *  
         *  @return
         *  A reference to *this.
         */
        randomCMWC_t& operator=(randomCMWC_t&&);
        
        /**
         *  Seed
         *  
         *  Seeds the build-in PRNG function and optionally resets the index
         *  to make this PRNG's generated values more deterministic.
         *  
         *  @param s
         *  A 32-bit unsigned integral type that will be used to initialize the
         *  pseudo-random number generator.
         *  
         *  @param beDeterministic
         *  A boolean that will allow for this PRNG to generate the same set of
         *  pseudo-random numbers using the same seed value.
         */
        virtual void seed(const uint32_t s, bool beDeterministic = true) override;
        
        /**
         *  Get
         *  
         *  Generates a pseudo-random number.
         *  
         *  @return
         *  A pseudo-randomly generated number using the complementary multiply
         *  with-carry method described by George Marsaglia.
         */
        virtual uint32_t get() override;
};

/*
 *  Constructor
 */
template <unsigned lag_size_t>
randomCMWC_t<lag_size_t>::randomCMWC_t() :
    random{},
    q{new uint32_t[MEM_SIZE]},
    c{SEED_VAL},
    i{INDEX_SIZE}
{}

/*
 *  Copy Constructor
 */
template <unsigned lag_size_t>
randomCMWC_t<lag_size_t>::randomCMWC_t(const randomCMWC_t& mwc) :
    random{mwc},
    q{new uint32_t[MEM_SIZE]},
    c{mwc.c},
    i{mwc.i}
{
    std::copy(mwc.q, mwc.q+MEM_SIZE, q);
}

/*
 *  Move Constructor
 */
template <unsigned lag_size_t>
randomCMWC_t<lag_size_t>::randomCMWC_t(randomCMWC_t&& mwc) :
    random{std::move(mwc)},
    q{mwc.q},
    c{mwc.c},
    i{mwc.i}
{
    mwc.q = nullptr;
}

/*
 *  Destructor
 */
template <unsigned lag_size_t>
randomCMWC_t<lag_size_t>::~randomCMWC_t() {
    delete [] q;
    q = nullptr;
}

/*
 *  Copy Operator
 */
template <unsigned lag_size_t>
randomCMWC_t<lag_size_t>& randomCMWC_t<lag_size_t>::operator=(const randomCMWC_t& mwc) {
    random::operator=(mwc);
    
    std::copy(mwc.q, mwc.q+MEM_SIZE, q);
    
    c = mwc.c;
    i = mwc.i;
    
    return *this;
}

/*
 *  Move Operator
 */
template <unsigned lag_size_t>
randomCMWC_t<lag_size_t>& randomCMWC_t<lag_size_t>::operator=(randomCMWC_t&& mwc) {
    random::operator=(std::move(mwc));
    
    delete [] q;
    q = mwc.q;
    mwc.q = nullptr;
    
    c = mwc.c;
    i = mwc.i;
    
    return *this;
}

/*
 *  Seed the prng
 */
template <unsigned lag_size_t>
void randomCMWC_t<lag_size_t>::seed(const uint32_t s, bool beDeterministic) {
    /*
    q[0] = ~s;
    q[1] = q[0] ^ s;
    q[2] = q[1] & ~s;
    */
    
    q[0] = s;
    q[1] = 809430660ULL * q[0]+c;
    c = q[1] >> 15;
    q[2] = q[1];
    
    for (uint32_t iter = 3; iter < MEM_SIZE; ++iter) {
        q[iter] = q[iter-3] ^ q[iter-2] ^ ~s ^ iter;
    }
    
    if (beDeterministic) {
        i = INDEX_SIZE;
    }
}

/*
 *  Get a pseudo-random number.
 */
template <unsigned lag_size_t>
uint32_t randomCMWC_t<lag_size_t>::get() {
    i = (i+1) & INDEX_SIZE;
    const uint64_t t = (18782ULL * q[i]) + c;
    c = t >> 32;
    uint32_t x = t + c;
    
    if (x < c) {
        ++x;
        ++c;
    }
    
    return q[i] = RAND_MASK - x;
}

//-----------------------------------------------------------------------------
//      randomCMWC PRNG typedefs
//-----------------------------------------------------------------------------
typedef randomCMWC_t<4096> randomCMWC;

//-----------------------------------------------------------------------------
//      Main()
//-----------------------------------------------------------------------------
int main() {
    const uint32_t seedVal = time(nullptr);
    //const uint32_t seedVal = 42;
    random* testRand = new randomCMWC();
    
    std::cout << "Calling a PRNG with the seed " << seedVal << std::endl;
    testRand->seed(seedVal);
    
    for (int i = 0; i < 128; ++i) {
        std::cout << testRand->get() << std::endl;
    }
    
    delete testRand;
    
    return 0;
}