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.