4
\$\begingroup\$

Some time ago (pre-C++11) I wrote a small random number generator library as part of a university assignment. The code has been stored on my hard drive for quite some time and today I dug it out and decided to post it here for review. It is now obsolete, since C++11 added a very extensive random library, but still, I'd like to receive suggestions on how to improve this piece of code.

It follows a somewhat similar architecture of the standard random library and it should be easily extensible, even though I have only provided two Engine implementations:

Random.hpp:

#pragma once

// ======================================================
// LCGEngine:
// ======================================================

// Implements a Linear Congruential Generator pseudo-random engine.
class LCGEngine {

public:

    // Maximum value returned by NextValue().
    static const int ValueMax = INT_MAX;

    // Constructors:
    LCGEngine();
    LCGEngine(const unsigned int seed);

    // Reset (seed) the pseudo-random generator engine.
    void Seed(const unsigned int seed);

    // Get the next value in the pseudo-random sequence.
    int NextValue();

private:

    // Random accumulators (LCG):
    unsigned int base0;
    unsigned int base1;
    unsigned int base2;
};

// ======================================================
// XORShiftEngine:
// ======================================================

// Implements a XOR-Shift pseudo-random engine.
class XORShiftEngine {

public:

    // Maximum value returned by NextValue().
    static const int ValueMax = INT_MAX;

    // Constructors:
    XORShiftEngine();
    XORShiftEngine(const unsigned int seed);

    // Reset (seed) the pseudo-random generator engine.
    void Seed(const unsigned int seed);

    // Get the next value in the pseudo-random sequence.
    int NextValue();

private:

    unsigned int x, y, z, w;
};

// ======================================================
// Random:
// ======================================================

//
// Pseudo-random number generator class with several distribution functions.
//
// The Random class is a template that accepts any compliant
// random generator engine. This class implements the most common
// distribution functions for the engines.
//
template<class ENGINE>
    class Random {

public:

    // Type of the underlaying random generator engine.
    typedef ENGINE EngineType;

    // Max integer value that can be generated.
    enum { ValueMax = ENGINE::ValueMax };

    // Construct with seed based on current time.
    Random();

    // Construct with user defined seed.
    Random(const unsigned int seed);

    // Construct with a preexistent random generator engine.
    Random(const ENGINE & eng);

    // Copy state from another generator.
    Random(const Random & other);

    // Reset (seed) the pseudo-random generator.
    void Seed(const unsigned int seed);

    // Pseudo-random boolean. 'true' or 'false'.
    bool NextBoolean();

    // Pseudo-random floating-point number in range [0, 1].
    float NextFloat();

    // Pseudo-random floating-point number in range [lowerBound, upperBound].
    float NextFloat(const float lowerBound, const float upperBound);

    // Pseudo-random floating-point number in range [-1, 1].
    float NextSymmetric();

    // Pseudo-random integer in range [0, ValueMax].
    int NextInteger();

    // Pseudo-random integer in range [lowerBound, upperBound].
    int NextInteger(const int lowerBound, const int upperBound);

    // Pseudo-random number with uniform distribution.
    float NextUniform(const float lowerBound, const float upperBound);

    // Pseudo-random number with exponential distribution.
    float NextExponential(const float average);

    // Pseudo-random number with normal (Gaussian) distribution.
    float NextGaussian(const float average, const float stdDeviation);

    // Access the underlaying random generator engine.
    ENGINE & GetRandomEngine();

    // Access the underlaying random generator engine (const overload).
    const ENGINE & GetRandomEngine() const;

private:

    // The pseudo-random generator engine.
    ENGINE engine;

    // Helper variables used by the normal distribution calculation.
    float leftover;
    bool  useLast;
};

// ======================================================
// Typedefs:
// ======================================================

// Linear Congruential Generator:
// http://en.wikipedia.org/wiki/Linear_congruential_generator
typedef Random<LCGEngine> LCGRandom;

// XOR-shift:
// http://en.wikipedia.org/wiki/Xorshift
typedef Random<XORShiftEngine> XORShiftRandom;

// ======================================================
// Helpers / globals:
// ======================================================

// Get a hash value based on the current time. Useful for seeding a pseudo-random generator.
unsigned int GenTimeSeed(const unsigned int seed);

#include "Engine/Core/Math/Random.inl"

Random.inl:

#include <cmath>

template<class ENGINE>
inline Random<ENGINE>::Random()
    : engine()
    , leftover(0.0f)
    , useLast(false)
{
    // Init with defaults.
}

template<class ENGINE>
inline Random<ENGINE>::Random(const unsigned int seed)
    : engine(seed)
    , leftover(0.0f)
    , useLast(false)
{
    // Init with user provided seed.
}

template<class ENGINE>
inline Random<ENGINE>::Random(const ENGINE & eng)
    : engine(eng)
    , leftover(0.0f)
    , useLast(false)
{
    // Init with engine.
}

template<class ENGINE>
inline Random<ENGINE>::Random(const Random<ENGINE> & other)
    : engine(other.engine)
    , leftover(other.leftover)
    , useLast(other.useLast)
{
    // Init from copy.
}

template<class ENGINE>
inline void Random<ENGINE>::Seed(const unsigned int seed)
{
    engine.Seed(seed);
}

template<class ENGINE>
inline bool Random<ENGINE>::NextBoolean()
{
    return ((engine.NextValue() & 1) == 0);
}

template<class ENGINE>
inline float Random<ENGINE>::NextFloat()
{
    return (engine.NextValue() * (1.0f / ENGINE::ValueMax));
}

template<class ENGINE>
inline float Random<ENGINE>::NextFloat(const float lowerBound, const float upperBound)
{
    const float f = (static_cast<float>(engine.NextValue()) + 0.5f) / ENGINE::ValueMax;
    return (lowerBound + (upperBound - lowerBound) * f);
}

template<class ENGINE>
inline float Random<ENGINE>::NextSymmetric()
{
    return (2.0f * NextFloat() - 1.0f);
}

template<class ENGINE>
inline int Random<ENGINE>::NextInteger()
{
    return (engine.NextValue());
}

template<class ENGINE>
inline int Random<ENGINE>::NextInteger(const int lowerBound, const int upperBound)
{
    if (lowerBound == upperBound)
    {
        return (lowerBound); // Avoid a division by zero.
    }
    return ((engine.NextValue() % (upperBound - lowerBound)) + lowerBound);
}

template<class ENGINE>
inline float Random<ENGINE>::NextUniform(const float lowerBound, const float upperBound)
{
    return (lowerBound + (NextFloat() * (upperBound - lowerBound)));
}

template<class ENGINE>
inline float Random<ENGINE>::NextExponential(const float average)
{
    return (-average * std::log(1.0f - NextFloat()));
}

template<class ENGINE>
inline float Random<ENGINE>::NextGaussian(const float average, const float stdDeviation)
{
    // See http://www.taygeta.com/random/gaussian.html
    // for a full explanation.

    float x1, x2, y1, y2, w;
    if (useLast) // Use value from previous call?
    {
        y1 = leftover;
        useLast = false;
    }
    else
    {
        do
        {
            x1 = (2.0f * NextFloat()) - 1.0f;
            x2 = (2.0f * NextFloat()) - 1.0f;
            w = (x1 * x1) + (x2 * x2);
        }
        while (w >= 1.0f);

        w = std::sqrt((-2.0f * std::log(w)) / w);
        y1 = (x1 * w);
        y2 = (x2 * w);

        leftover = y2;
        useLast  = true;
    }

    return (average + y1 * stdDeviation);
}

template<class ENGINE>
inline ENGINE & Random<ENGINE>::GetRandomEngine()
{
    return (engine);
}

template<class ENGINE>
inline const ENGINE & Random<ENGINE>::GetRandomEngine() const
{
    return (engine);
}

Random.cpp:

#include "Core/Utilities.hpp"
#include "Core/Math/Random.hpp"
#include <ctime>

// ======================================================
// LCGEngine:
// ======================================================

LCGEngine::LCGEngine()
    // Arbitrary constants:
    : base0(42)
    , base1(666)
    , base2(1337)
{
}

LCGEngine::LCGEngine(const unsigned int seed)
{
    Seed(seed);
}

void LCGEngine::Seed(const unsigned int seed)
{
    base0 = seed;
    base1 = seed;
    base2 = seed;
}

int LCGEngine::NextValue()
{
    // Triple LCG:
    base0 = (1664525 * base0-1 + 1013904223) % ValueMax;
    switch (base0 & 1)
    {
    case 0 :
        base1 = (214013 * base1-1 + 2531011) % ValueMax;
        return (base1);

    case 1 :
        base2 = (1103515245 * base2-1 + 12345) % ValueMax;
        return (base2);

    default :
        return (base0); // This never happens, it is here just to please the compiler.
    } // switch (base0 & 1)
}

// ======================================================
// XORShiftEngine:
// ======================================================

XORShiftEngine::XORShiftEngine()
    // Constants presented in this paper: http://www.jstatsoft.org/v08/i14/paper
    : x(123456789U)
    , y(362436069U)
    , z(521288629U)
    , w(88675123U)
{
}

XORShiftEngine::XORShiftEngine(const unsigned int seed)
{
    Seed(seed);
}

void XORShiftEngine::Seed(const unsigned int seed)
{
    x = (seed ^ 123456789U);
    y = (seed ^ 362436069U);
    z = (seed ^ 521288629U);
    w = (seed ^ 88675123U);
}

int XORShiftEngine::NextValue()
{
    // XOR-Shift-128 RNG:
    unsigned int t = x ^ (x << 11);
    x = y;
    y = z;
    z = w;
    w = w ^ (w >> 19) ^ t ^ (t >> 8);
    return (w);
}

// ======================================================
// GenTimeSeed():
// ======================================================

unsigned int GenTimeSeed(const unsigned int seed)
{
    // Zero is an OK default value for 'seed'
    const time_t now = std::time(nullptr);
    const unsigned char * p = reinterpret_cast<const unsigned char *>(&now);
    unsigned int s = seed;

    for (size_t i = 0; i < sizeof(now); ++i)
    {
        s = s * (0xff + 2U) + p[i];
    }

    return (s);
}

I've never used it thoroughly, so I don't know how it would hold out in a more demanding scenario. This was not devised to be cryptography safe, it was made for use with real-time applications like games, height map generators, noise functions and such.

I think NextInteger(const int lowerBound, const int upperBound) is probably worthless, since it uses %, which as far as I know completely obliterates the distribution.

Also, LCGEngine::NextValue() uses a "triple random" that I made up. Not sure if there is any gain on that...

Other suggestions are also very welcome. If you'd like to suggest the use of C++11 features, feel free, since I have a compliant compiler.

\$\endgroup\$
  • \$\begingroup\$ I think it's a good idea to prefix type arguments with 'T' letter, so you can distinguish them from "normal" types. \$\endgroup\$ – Agares Sep 24 '14 at 11:02
3
\$\begingroup\$
  1. You use a lot of unnecessary top level cv qualifiers on parameters that don't have any effect. That doesn't only look strange to me but is also quiet some unnecessary typing effort.
  2. You explicitly implement copy constructors on your own whilst the compiler generated one would have exactly the same behaviour. This also means that you have to update an additional method if you'd like to extend your class.
  3. I suggest you to make all your non-copy constructors explicit you really don't want an unsigned to implicitly convert to Random.
  4. A better implementation of NextBoolean() (especially for bad engines) would be to check, whether the value is greater / less than the median. To uniformly distribute on all bits is harder to achieve than uniformly distribute on the value range.
  5. In general, your way to implement NextInteger(int lowerBound, int upperBound) does not completely obliterate the distribution. It does not even harm it if INT_MAX is congruent to 0 modulo (upperBound - lowerBound) or in other words is a power of two. But there is an additional problem with linear congruential generators, since their own uniform distribution and their distribution over the bits is pretty bad. For a good implementation, you have to take up to two numbers from your generator and you have to do some bit twiddling.
  6. Both your engines return signed integers. It looks a bit weird to me since unsigned integer are easier to work with especially if it comes to bit shifting. Just because of that you made the mistake to implement NextFloat() wrong. In the comment above you statet that its return value is in [0, 1] what would have been true if you would have used unsigned types. With signed integers, it is in [-1, 1].
  7. x * (1 / y) is an obfuscating way to write x / y.
  8. NextSymmetric() is wrong in consequence of NextFloat() being wrong.
  9. If one invokes NextFloat(float lowerBound, float upperBound) with a large range, the resulting values fall into categories (corresponding to their initial value returned by NextFloat() between 0 and 1) and therefore not all possible numbers in this range can be returned by this function. But at the moment neither I know a better implementation beside some platform dependend bit twiddling on the floating point numbers.
  10. I don't quite get the difference between NextFloat and NextUniform. Is there even any? If not, why are there two different implementations instead of NextUniform just invoking NextFloat?
  11. You can avoid that undefined reinterpret_cast in GenTimeSeed by using bit masks and bit shifts.
  12. You don't have to write inline since modern compiler know better than programmers what's beneficial to inline and what's not (they'll mostly ignore it anyways).
  13. Explicitly invoking the members default constructor (since this happens implicitly as well) looks weird to me but this is just an opinion.

Sorry for my bad English. Hopefully it's clear enough to understand.

\$\endgroup\$
  • 2
    \$\begingroup\$ The const int and const float prevent accidental modification, which is good practice, but I agree that it looks weird and the same can be achieved by placing const int val = arg_ on top of the body to get the same security without poluting the interface. \$\endgroup\$ – user52292 Sep 19 '14 at 8:29
  • 1
    \$\begingroup\$ @firda Sometimes it's even quite useful to modify the arguments in order to avoid additional local variables. And how can an accidental modification be so bad, that one wants do prevent it? Typos occur extremely rare if you look at the screen whilst typing. And modern compilers even warn you if you assign something in a context where a comparison would be more usual (if). \$\endgroup\$ – Fytch Sep 19 '14 at 8:36
  • 2
    \$\begingroup\$ sure, I am not using this technique (const int) in the interface (argument list), but understand it. Sometimes it is good to have these inside the body. It can make it even more readable by clearly stating what is not to be changed. \$\endgroup\$ – user52292 Sep 19 '14 at 8:55
  • \$\begingroup\$ Thanks, this was a very good review! I use const for the reasons firda mentioned. It doesn't have side effects (besides arguable visual pollution) but it can have the benefit of making the code less error prone. \$\endgroup\$ – glampert Sep 19 '14 at 14:42
  • 1
    \$\begingroup\$ It is valid to declare method(int arg) (in header) and then define it method(const int arg) (in source or later in header) ;) Try it (works for me with GCC 4.8.3) \$\endgroup\$ – user52292 Sep 19 '14 at 19:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.