I've created a threaded application where each thread calls rand() several hundred thousand times a second. As you might guess, this causes problems. A large percentage of the generated numbers are duplicated, which causes wasted processing power.
I'm looking for a way to generate random numbers between 0 and about 64 that will produce unique results between threads.
I got the idea to create my own class, named Random, that contained custom functions for generating the random numbers I need. I could then instantiate the class inside every thread, use a unique seed, and every result would be different.
The only problem is that I don't know where to begin to create an RNG. I'd like it to be simple, so I'd like to avoid dedicated libraries for this. Can some veterans enlighten me on how to get started on a custom RNG?
Here's a simple RNG I use in my programs. I have a more complicated one that has a longer period, as well, but this one is good and very lightweight. Algorithm courtesy of George Marsaglia on Google Groups.
#ifndef __DSHLIB_RNGBASE_H__
#define __DSHLIB_RNGBASE_H__
//////////////////////////////////////////
#include "../file/file.h"
#include <ctime>
/*
* RNGBase is a base class for pRNGs to be derived from.
*/
namespace dshlib
{
class RNGBase
{
public:
/*
* Random number generation
*/
// this to be filled by the derived RNG -- to produce a u32 [0-FFFFFFFF]
virtual u32f Gen() = 0; // unsigned 32-bit value
virtualvoid Reseed(u32f s) = 0; // to reseed the RNG
virtualvoid SeedTime()
{
u32f t = (u32f)time(0);
Reseed(t*t);
}
/*
* State saving/loading
*/
virtual size_t StateSize() = 0; // returns size needed to save state of RNG
virtualvoid StateSave(File* file) = 0; // saves state to given file
virtualvoid StateLoad(File* file) = 0; // loads state from given file
int Gen(int mx) { return (int)(Gen() % mx); } // int between [0-mx)
double Real0() { return Gen() / ((double)0xFFFFFFFF+1); } // number between [0-1)
double Real01() { return Gen() / ((double)0xFFFFFFFF); } // number between [0-1]
};
} // namespace dshlib
#endif // __DSHLIB_RNGBASE_H__
#ifndef __DSHLIB_GMSIMPLE32_H__
#define __DSHLIB_GMSIMPLE32_H__
/*
* GMSimple32 -- a pRNG posted by George Marsaglia on Google Groups.
* This RNG was casually posted on google groups without a name or any copyright
* information. About the only thing I know about it is it's by
* George Marsaglia and ?presumably? has a period of 2^32
*
* This is a pretty quick and lightweight algorithm
*/
namespace dshlib
{
class GMSimple32 : public RNGBase
{
public:
/*
* ctors / assignment
*/
GMSimple32() { SeedTime(); }
GMSimple32(const GMSimple32& v) { state = v.state; }
GMSimple32(u32f seed) { state = seed; }
GMSimple32& operator = (const GMSimple32& v) { state = v.state; }
/*
* Reseeding
*/
virtualvoid Reseed(u32f s) { state = s; }
/*
* Random number generation
*/
virtual u32f Gen()
{
return state = (69069*state) + 362437;
}
/*
* State saving/loading
*/
virtual size_t StateSize() { returnsizeof(u32); }
virtualvoid StateSave(File* file) { file->PutInt(state); }
virtualvoid StateLoad(File* file) { state = file->GetInt<u32>(); }
protected:
u32 state;
};
} // namespace dshlib
#endif // __DSHLIB_GMSIMPLE32_H__
I found George Marsaglia's pRNGs on Google Groups after researching Mersenne Twister a while back. There's a link to the thread on the MT wikipedia article, iirc. In that thread is the algorithm I pasted before, as well as the more complicated one I alluded to in an earlier post (labelled CMWC4096 in the googlegroups thread), which apparently is "better" than MT (longer period, faster calculations).
I generally agree with Skorj. Making a good RNG is actually quite tricky... and it's very easy to make a poor one. George Marsaglia appears to be very knowledgeable ane experienced in this department, though, and so far my (admittedly limited) use of his RNGs has yielded wonderful results.
One of the downsides to using a standard library RNG is that there's no guarantee that it's implemented the same everywhere. There might be occasions where you'll want to reproduce the same string of random numbers with a given seed or state (for example, recording and playing back keylog based movies in an emulator or game... if a different string is generated during movie playback, the movie will desync). This same thing can be said of using an RNG in a library like Boost. If they ever happen to change the RNG algorithm ever so slightly -- you're pretty much screwed.
This is one of the reasons why I prefer to have my own copy of an algorithm handy.