From 360d8eade0332f2c1aa5c205ca772cd506c35b26 Mon Sep 17 00:00:00 2001 From: peterbell10 Date: Tue, 13 Jun 2017 20:35:30 +0100 Subject: FastRandom rewrite (#3754) --- src/FastRandom.h | 200 +++++++++++++++++++++++++++++++++++++++++++++---------- 1 file changed, 165 insertions(+), 35 deletions(-) (limited to 'src/FastRandom.h') diff --git a/src/FastRandom.h b/src/FastRandom.h index a21da8391..77bafc217 100644 --- a/src/FastRandom.h +++ b/src/FastRandom.h @@ -4,17 +4,10 @@ // Declares the cFastRandom class representing a fast random number generator /* -The cFastRandom aims to provide a very fast, although not very cryptographically secure, random generator. -It is fast to instantiate, fast to query next, and partially multi-thread-safe. -It is multi-thread-safe in the sense that it can be accessed from multiple threads without crashing, but it may -yield duplicate numbers in that case. - -Internally, this works similar to cNoise's integral noise generation, with some predefined inputs: the seed is -taken from a global counter and the random is calculated using a counter that is incremented on each use (hence -the multi-thread duplication). Two alternatives exists for each function, one that takes a range parameter, -and another that takes an additional "salt" parameter; this salt is used as an additional input to the random, -in order to avoid multi-thread duplication. If two threads both use the class at the same time with different -salts, the values they get will be different. +The cFastRandom alias should be avoided in favor of the result of a call to GetRandomProvider(). +The MTRand generator used is faster, has a better range and provides higher quality randomness. +Note that MTRand is relatively costly to construct and so instances should be long lived, +prefer calls to GetRandomProvider over creating new instances. */ @@ -23,58 +16,195 @@ salts, the values they get will be different. #pragma once #include +#include +#include -class cFastRandom +namespace Detail +{ + /** Returns a low quality seed. */ + UInt32 GetRandomSeed(); + + /** Aliases true_type if Char is any variant of char ignoring signed-ness. */ + template + using IsChar = typename std::is_same::type, signed char>::type; + + template + struct cUniformImpl : + public std::conditional< + IsChar::value, + typename std::conditional< // Match signed-ness of IntType + std::is_signed::value, + std::uniform_int_distribution, + std::uniform_int_distribution + >::type, + std::uniform_int_distribution + > + { + }; + + /** uniform_int_distribution is undefined so this aliases a valid type. */ + template + using cUniform = typename cUniformImpl::type; +} + + + + + +/** Class to wrap any random engine to provide a more convenient interface. */ +template +class cRandomWrapper { public: + /** Initialize with a low quality seed. */ + cRandomWrapper(): + m_Engine(Detail::GetRandomSeed()) + { + } - cFastRandom(void); - /** Returns a random int in the range [0 .. a_Range - 1]; a_Range must be less than 1M */ - int NextInt(int a_Range); + /** Initialize with a SeedSequence. */ + template + cRandomWrapper(SeedSeq & a_SeedSeq): + m_Engine(a_SeedSeq) + { + } - /** Returns a random float in the range [0 .. a_Range]; a_Range must be less than 1M */ - float NextFloat(float a_Range); - /** Returns a random float between 0 and 1. */ - float NextFloat(void) { return NextFloat(1); } - /** Returns a random int in the range [a_Begin .. a_End] */ - int GenerateRandomInteger(int a_Begin, int a_End); + /** Return a random IntType in the range [a_Min, a_Max]. */ + template + IntType RandInt(ArgType a_Min, ArgType a_Max) + { + ASSERT( + (a_Max >= a_Min) && + (a_Max <= std::numeric_limits::max()) && + (a_Min >= std::numeric_limits::min()) + ); + Detail::cUniform dist( + static_cast(a_Min), + static_cast(a_Max) + ); + return static_cast(dist(m_Engine)); + } -private: - std::minstd_rand m_LinearRand; -}; + /** Return a random IntType in the range [0, a_Max]. */ + template + IntType RandInt(ArgType a_Max) + { + ASSERT((a_Max >= 0) && (a_Max <= std::numeric_limits::max())); + Detail::cUniform dist(IntType(0), static_cast(a_Max)); + return static_cast(dist(m_Engine)); + } + + + + + + /** Return a random IntType in the range [0, std::numeric_limits::max()]. */ + template + IntType RandInt() + { + Detail::cUniform dist(IntType(0), std::numeric_limits::max()); + return static_cast(dist(m_Engine)); + } + + + + + + /** Return a random RealType in the range [a_Min, a_Max). */ + template + RealType RandReal(ArgType a_Min, ArgType a_Max) + { + std::uniform_real_distribution dist(a_Min, a_Max); + return dist(m_Engine); + } -class MTRand -{ -public: - MTRand(void); - /** Returns a random integer in the range [0 .. a_Range]. */ - int randInt(int a_Range); - /** Returns a random integer in the range [0 .. MAX_INT]. */ - int randInt(void); + /** Return a random RealType in the range [0, a_Max). */ + template + RealType RandReal(ArgType a_Max) + { + std::uniform_real_distribution dist(RealType(0), a_Max); + return dist(m_Engine); + } - /** Returns a random floating point number in the range [0 .. a_Range]. */ - double rand(double a_Range); + + + + + /** Return a random RealType in the range [0, 1). */ + template + RealType RandReal() + { + std::uniform_real_distribution dist; + return dist(m_Engine); + } + + + + + + /** Return a random bool with the given probability of being true. */ + bool RandBool(double a_TrueProbability = 0.5) + { + std::bernoulli_distribution dist(a_TrueProbability); + return dist(m_Engine); + } + + + + + /** Returns a reference to the underlying random engine. */ + RandomEngine & Engine() + { + return m_Engine; + } private: - std::mt19937 m_MersenneRand; + RandomEngine m_Engine; }; + +/** Utility to seed a random engine with maximal entropy from random_device. */ +struct cRandomDeviceSeeder +{ + using result_type = std::random_device::result_type; + + template + void generate(Itr first, Itr last) + { + std::random_device rd; + std::uniform_int_distribution dist; + for (; first != last; ++first) + { + *first = dist(rd); + } + } +}; + + + + + +using cFastRandom = cRandomWrapper; +using MTRand = cRandomWrapper; + +/** Returns the current thread's random number source. */ +MTRand & GetRandomProvider(); -- cgit v1.2.3