Thread-Safe Random Number Generator

[GenTiradentes]

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?

[Disch]

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.

You can drop the dshlib and file saving stuff:

#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
    virtual void    Reseed(u32f s) = 0; // to reseed the RNG
    virtual void    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
    virtual void    StateSave(File* file) = 0;      // saves state to given file
    virtual void    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
	 */
    virtual void	Reseed(u32f s)      { state = s;         }

	/*
	 *	Random number generation
	 */
	virtual u32f    Gen()
    {
        return state = (69069*state) + 362437;
    }

    /*
     *	State saving/loading
     */
    virtual size_t  StateSize()             { return sizeof(u32);       }
    virtual void    StateSave(File* file)   { file->PutInt(state);      }
    virtual void    StateLoad(File* file)   { state = file->GetInt<u32>();   }

protected:
    u32         state;
};

} // namespace dshlib

#endif //  __DSHLIB_GMSIMPLE32_H__ 

[Zaita]

http://www.boost.org/doc/libs/1_38_0/libs/random/index.html

[Skorj]

The Standard C++ Library TR1 Extension includes a random number generator.

#include <random>

It's the same one as "boost/tr1/random.hpp", but many compilers have a TR1 extension available now, if you prefer that to Boost.

Writing your own RNG is like writing your own crypto: usually a mistake.

[GenTiradentes]

The problem is I don't need just a random number generator, that's more than easy enough.

What I need is an RNG that I can create separate instances of, so that each random number generated is unique across threads.

Disch, thanks for the code, I'll try that.

[seymore15074]

Could you have a single thread generate the random numbers and communicate the numbers to the other threads?

[helios]

One of the best generators there are: Mersenne Twister.

#ifndef MERSENNETWISTER
#define MERSENNETWISTER
#include <ctime>
//Note: Not standard.
#include <stdint.h>

typedef unsigned long uint32_t;
typedef unsigned short ushort;

uint32_t initseed(){
	uint32_t c=time(0);
	bool d=c%2;
	c=c>>2;
	c=c<<1;
	c+=d;
	return c<<16+c;
}

class MersenneTwister{
	uint32_t vector[624];
	ushort state;
public:
	MersenneTwister(){
		state=0xFFFF;
		vector[0]=initseed();
		for (ushort a=1;a<624;a++)
			vector[a]=(0x10DCD*vector[a-1])&0xFFFFFFFF;
	}
	MersenneTwister(uint32_t seed){
		state=0xFFFF;
		vector[0]=seed;
		for (ushort a=1;a<624;a++)
			vector[a]=(0x10DCD*vector[a-1])&0xFFFFFFFF;
	}
	void gen(){
		uint32_t y=0;
		for (ushort a=0;a<=622;a++){
			y=this->vector[a]&7FFFFFFF;
			y+=uint32_t(double(this->vector[a+1]&0xFFFFFFFF)/0xFFFFFFFF);
			if (!(y%2))
				this->vector[a]=this->vector[(a+367)%624]^(y>>1);
			else
				this->vector[a]=this->vector[(a+397)%624]^(y>>1)^0x9908B0DF;
		}
		y=this->vector[623]&0x7FFFFFFF;
		y+=(uint32_t)(double(this->vector[0]&0xFFFFFFFF)/0xFFFFFFFF);
		if (!(y%2))
			this->vector[623]=this->vector[396]^(y>>1);
		else
			this->vector[623]=this->vector[396]^(y>>1)^0x9908B0DF;
	}
	//0<=uint32_t<256^4-1
	uint32_t rnd(){
		uint32_t y;
		if (this->state==0xFFFF){
			this->state=1;
			this->gen();
			y=this->vector[0];
		}else{
			y=this->vector[this->state];
			this->state++;
			y=y^(y>>11);
			y=y^(y<<7)&0x9D2C5680;
			y=y^(y<<15)&0xEFC60000;
			y=y^(y>>18);
			if (this->state==623){
				this->state=0;
				this->gen();
			}
		}
		return y-1;
	}
	//0<=double<1
	double rnd2(){
		uint32_t y=this->rnd();
		return y==0xFFFFFFFF?double(y-1)/0xFFFFFFFF:double(y)/0xFFFFFFFF;
	}
};
#endif 

[Disch]

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.