I was reading the section in the book about the random number generator and the pseudo-random traversal of a set, and I did some reading on the method itself (which is actually a form of a linear congruential generator), and so I built a generator from it. I'm not sure how well it works in larger scale projects, it may or may not be random enough, but in my testing it's around 3 times faster than the STL rand() function in release runtimes (it's actually significantly slower in debug runtimes, though).
Display All
I'm sure there are things that could be optimized, and it may or may not be random enough for your tastes, but it's fast and it's simple. I attempted to make it appear more random by looping until it had a value less than 2^32, but then I realized that the range between 2^32 and 2^64 is enormous, and attempting to skip all those values is painfully slow. It was slow enough that I'm pretty sure it was an infinite loop or something. I suppose the randomize seed function could be better, but it might appear random enough for some people.
It pretty much works almost like the pseudo-random traversal in GCC, because the form for linear congruential generators is k(n)=(ak(n-1)+b) mod c. So long as c and b are co-prime (I figured it was easier just to make b prime, period) and so long as a-1 is divisible by all prime factors of c and divisible by 4 so long as c is divisible by 4, it will traverse every single number in the set once before it repeats. C is 2^64, so all values are automatically truncated, which saves a modulo operation to constrain it to that range. You can mess with the settings if you feel like it, and feel free to offer any suggestions you may have.
Source Code
- #pragma once
- /////////////////////////
- // Filename: CRandom.h //
- /////////////////////////
- //This file defines a simple pseudo-random number generator class. The algorithm
- //used is quite simple. It is essentially a linear congruential generator. It uses
- //64 bits, but there are plenty of functions to allow it to constrain the range.
- #define INCREMENT 0xe5b86046d8db09d
- #define LIMIT 1.0/4294967296.0/4294967296.0
- #define MULTIPLIER 4294967297
- class CRandom
- {
- public:
- inline CRandom()
- {
- seed=0;
- }
- inline unsigned long long GetRandom()
- {
- seed=MULTIPLIER*seed+INCREMENT;
- return seed;
- }
- inline unsigned long long GetRandom(unsigned long long range)
- {
- seed=MULTIPLIER*seed+INCREMENT;
- return seed%range;
- }
- inline unsigned int GetRandom(unsigned int range)
- {
- seed=MULTIPLIER*seed+INCREMENT;
- return seed%range;
- }
- inline int GetRandom(int range)
- {
- seed=MULTIPLIER*seed+INCREMENT;
- return seed%range;
- }
- inline double GetFactor()
- {
- seed=MULTIPLIER*seed+INCREMENT;
- return ((double)seed)*LIMIT;
- }
- inline unsigned long long GetSeed()
- {
- return seed;
- }
- inline void SetSeed(unsigned long long value)
- {
- seed=value;
- return;
- }
- inline void RandomizeSeed()
- {
- seed*=seed;
- return;
- }
- private:
- //A seed value, which should be 64 bits.
- unsigned long long seed;
- };
I'm sure there are things that could be optimized, and it may or may not be random enough for your tastes, but it's fast and it's simple. I attempted to make it appear more random by looping until it had a value less than 2^32, but then I realized that the range between 2^32 and 2^64 is enormous, and attempting to skip all those values is painfully slow. It was slow enough that I'm pretty sure it was an infinite loop or something. I suppose the randomize seed function could be better, but it might appear random enough for some people.
It pretty much works almost like the pseudo-random traversal in GCC, because the form for linear congruential generators is k(n)=(ak(n-1)+b) mod c. So long as c and b are co-prime (I figured it was easier just to make b prime, period) and so long as a-1 is divisible by all prime factors of c and divisible by 4 so long as c is divisible by 4, it will traverse every single number in the set once before it repeats. C is 2^64, so all values are automatically truncated, which saves a modulo operation to constrain it to that range. You can mess with the settings if you feel like it, and feel free to offer any suggestions you may have.