Random numbers...

Started by Noods August 23, 2001 05:01 PM

18 comments, last by Noods 23 years, 5 months ago

136

August 25, 2001 08:46 AM

quote:
Original post by Noods
I have actually seen the ''MT'' but I am still learning C++ and I dont quite understand the code. I have found that the rand and srand dont generate quality random numbers, I usually ended up with duplicate stats, and stats that were constantly too low. I am optimally looking for a function that I can send a maximum, minimum and possibly an interval to, and it can send back a random number within the givens sepecifications. Im not expecting anyone to code this out and send it to me, (although it would be nice) but any incite on how to do this would be appreciated. The problem is, is that generating a quality random number is not easy, especially for someone who is semi new. Timkin - I have emailed you but have not received a response. No rush, just letting you know. Thanks for the help.

-Noods

Actually the MT is not C++ but is instead C. Treat it as a "black box" and don''t worry about what
they are doing within, as long as it produces a quality set of psuedo-random numbers, what do you care?

FWIW, getting a quality random number is trivial. Just use MT or as Timkin suggested, one of Knuth''s RNG.

As for your max/min/interval request, you can always scale the output of any RNG to meet your needs.
Look up the ''%'' (modulus) operator in C, I think you will find it useful for getting your max/min handled.
Experiment a bit, and you will be rewarded.

Good Luck.

Eric

Timkin

864

August 27, 2001 12:00 AM

To those that have emailed me for the random number generator code, my apologies for not replying yet. I have had a horrid few days and I simply haven''t gotten around to getting myself organised.

The code is on my home PC and I will post it to GameDev tonight (Australian time).

Cheers,

Timkin

Noods

Author

205

August 27, 2001 02:11 AM

OK everyone Im stuck again. I have modified the "Mersenne Twister" so now I have a program that generates a great random number between 0 and whatever integer I specify!!! And its totally worthless!!! Sure the program is simple and quick, but what good is the algo if it has to sit right in main??? Here is the code, its the MersenneTwister.h that is important

////////////////////////////////////////////
#include
#include
#include
#include "MersenneTwister.h"

int main(void)
{
MTRand mtrand1;

int d = mtrand1.randInt( 42 );

cout << "An integer in the range [0,42]: " << d << endl;

return 0;
}
////////////////////////////////////////////

So if I display d, I get the random number. But what I need is a function that I can send my maximum to, let MT do its thing, and have the number sent back. Sure, I dont need to know what the code does If I just want a program that generates a random number. But I do need to know what it does to manpulate it in any way. So if someone can break down what //MTRand mtrand1;// and //int d = mtrand1.randInt( 42 );// exactly mean to me, or tell me how to translate them to a fucntion, that would be great. Otherwise the "MT" is worthless to a n00b like me. Oh yea, here is whats in the MersenneTwister.h Have fun, and let me know if you find an answer!!!

Thanks!
-Noods

////////////////////////////////////////////
#ifndef MERSENNETWISTER_H
#define MERSENNETWISTER_H

#include
#include
#include

class MTRand {
public:
typedef unsigned long uint32;

enum { N = 624 };
enum { SAVE = N + 1 };

protected:
enum { M = 397 };
enum { MAGIC = 0x9908b0dfU };

uint32 state[N];
uint32 *pNext;
int left;

public:
MTRand( const uint32& oneSeed );
MTRand( uint32 *const bigSeed );
MTRand();

double rand();
double rand( const double& n );
double randExc();
double randExc( const double& n );
double randDblExc();
double randDblExc( const double& n );
uint32 randInt();
uint32 randInt( const uint32& n );
double operator()() { return rand(); }

void seed( uint32 oneSeed );
void seed( uint32 *const bigSeed );
void seed();

void save( uint32* saveArray ) const;
void load( uint32 *const loadArray );
friend std::ostream& operator<<( std::ostream& os, const MTRand& mtrand );
friend std::istream& operator>>( std::istream& is, MTRand& mtrand );

protected:
void reload();
uint32 hiBit( const uint32& u ) const { return u & 0x80000000U; }
uint32 loBit( const uint32& u ) const { return u & 0x00000001U; }
uint32 loBits( const uint32& u ) const { return u & 0x7fffffffU; }
uint32 mixBits( const uint32& u, const uint32& v ) const
{ return hiBit(u) | loBits(v); }
uint32 twist( const uint32& m, const uint32& s0, const uint32& s1 ) const
{ return m ^ (mixBits(s0,s1)>>1) ^ (loBit(s1) ? MAGIC : 0U); }
static uint32 hash( time_t t, clock_t c );
};

inline MTRand::MTRand( const uint32& oneSeed )
{ seed(oneSeed); }

inline MTRand::MTRand( uint32 *const bigSeed )
{ seed(bigSeed); }

inline MTRand::MTRand()
{ seed(); }

inline double MTRand::rand()
{ return double(randInt()) * 2.3283064370807974e-10; }

inline double MTRand::rand( const double& n )
{ return rand() * n; }

inline double MTRand::randExc()
{ return double(randInt()) * 2.3283064365386963e-10; }

inline double MTRand::randExc( const double& n )
{ return randExc() * n; }

inline double MTRand::randDblExc()
{ return double( 1.0 + randInt() ) * 2.3283064359965952e-10; }

inline double MTRand::randDblExc( const double& n )
{ return randDblExc() * n; }

inline MTRand::uint32 MTRand::randInt()
{
if( left == 0 ) reload();
--left;

register uint32 s1;
s1 = *pNext++;
s1 ^= (s1 >> 11);
s1 ^= (s1 << 7) & 0x9d2c5680U;
s1 ^= (s1 << 15) & 0xefc60000U;
return ( s1 ^ (s1 >> 18) );
}

inline MTRand::uint32 MTRand::randInt( const uint32& n )
{
uint32 used = ~0;
for( uint32 m = n; m; used <<= 1, m >>= 1 ) {}
used = ~used;

uint32 i;
do
i = randInt() & used;
while( i > n );
return i;
}

inline void MTRand::seed( uint32 oneSeed )
{
register uint32 *s;
register int i;
for( i = N, s = state;
i--;
*s = oneSeed & 0xffff0000,
*s++ |= ( (oneSeed *= 69069U)++ & 0xffff0000 ) >> 16,
(oneSeed *= 69069U)++ ) {}
reload();
}

inline void MTRand::seed( uint32 *const bigSeed )
{
register uint32 *s = state, *b = bigSeed;
register int i = N;
for( ; i--; *s++ = *b++ & 0xffffffff ) {}
reload();
}

inline void MTRand::seed()
{

FILE* urandom = fopen( "/dev/urandom", "rb" );
if( urandom )
{
register uint32 *s = state;
register int i = N;
register bool success = true;
while( success && i-- )
{
success = fread( s, sizeof(uint32), 1, urandom );
*s++ &= 0xffffffff;
}
fclose(urandom);
if( success )
{

reload();
return;
}
}
seed( hash( time(NULL), clock() ) );
}

inline void MTRand::reload()
{

register uint32 *p = state;
register int i;
for( i = N - M; i--; ++p )
*p = twist( p[M], p[0], p[1] );
for( i = M; --i; ++p )
*p = twist( p[M-N], p[0], p[1] );
*p = twist( p[M-N], p[0], state[0] );

left = N, pNext = state;
}

inline MTRand::uint32 MTRand::hash( time_t t, clock_t c )
{

static uint32 differ = 0;

uint32 h1 = 0;
unsigned char *p = (unsigned char *) &t
for( size_t i = 0; i < sizeof(t); ++i )
{
h1 *= UCHAR_MAX + 2U;
h1 += p;
}
uint32 h2 = 0;
p = (unsigned char *) &c
for( size_t j = 0; j < sizeof(c); ++j )
{
h2 *= UCHAR_MAX + 2U;
h2 += p[j];
}
return ( h1 + differ++ ) ^ h2;
}

inline void MTRand::save( uint32* saveArray ) const
{
register uint32 *sa = saveArray;
register const uint32 *s = state;
register int i = N;
for( ; i--; *sa++ = *s++ ) {}
*sa = left;
}

inline void MTRand::load( uint32 *const loadArray )
{
register uint32 *s = state;
register uint32 *la = loadArray;
register int i = N;
for( ; i--; *s++ = *la++ ) {}
left = *la;
pNext = &state[N-left];
}

inline std::ostream& operator<<( std::ostream& os, const MTRand& mtrand )
{
register const MTRand::uint32 *s = mtrand.state;
register int i = mtrand.N;
for( ; i--; os << *s++ << "\t" ) {}
return os << mtrand.left;
}

inline std::istream& operator>>( std::istream& is, MTRand& mtrand )
{
register MTRand::uint32 *s = mtrand.state;
register int i = mtrand.N;
for( ; i--; is >> *s++ ) {}
is >> mtrand.left;
mtrand.pNext = &mtrand.state[mtrand.N-mtrand.left];
return is;
}

#endif

Geta

136

August 27, 2001 10:00 AM

quote:
Original post by Noods
OK everyone Im stuck again. I have modified the "Mersenne Twister" so now I have a program that generates a great random number between 0 and whatever integer I specify!!! And its totally worthless!!! Sure the program is simple and quick, but what good is the algo if it has to sit right in main???

Why would it have to be in main?

Actually, a ceiling for a random number can be quite useful.

quote:

Here is the code, its the MersenneTwister.h that is important

////////////////////////////////////////////
#include
#include
#include
#include "MersenneTwister.h"

int main(void)
{
MTRand mtrand1;

int d = mtrand1.randInt( 42 );

cout << "An integer in the range [0,42]: " << d << endl;

return 0;
}
////////////////////////////////////////////

So if I display d, I get the random number. But what I need is a function that I can send my maximum to, let MT do its thing, and have the number sent back.

Then write one. Pretty simple really: "int getRandom(int iCeiling) { return gMT.randInt(iCeiling); }"
where gMT is a globally available instance of MTRand, that is declared with a simple "MTRand gMT;"
(and should be seeded before use) and is located outside of your main() above.

quote:

Sure, I dont need to know what the code does If I just want a program that generates a random number. But I do need to know what it does to manpulate it in any way.

Why? If all you need is a random number, who cares how it goes about doing it, as long as it
is fast and produces a reasonable distribution of psuedo-random numbers.

quote:

So if someone can break down what //MTRand mtrand1;// and //int d = mtrand1.randInt( 42 );// exactly mean to me, or tell me how to translate them to a fucntion, that would be great.

"MTRand mtrand1;" is declaring an instance of the object MTRand. This is basic C++.
"mtrand1.randInt()" is calling a method of the object MTRand. Again, basic C++.

Using them in a function is already given as an example: main() is a function. getRandom() above
is a function. I''m not sure what you don''t understand about this usage.

Eric

Anonymous

August 27, 2001 05:18 PM

OK. For all intensive purposes, I will say I am new to C++, therefore common C++ may be alien to me. So now, I have some more questions...

Whats a ceiling, in terms of C++?

////////////int getRandom(int iCeiling)
{
return gMT.randInt(iCeiling);
}

where gMT is a globally available instance of MTRand, that is declared with a simple "MTRand gMT;"
(and should be seeded before use) and is located outside of your main() above.//////////////

Ok, I think I understand the instance and declaration, but what is gMT, a variable?

////////////////////Why? If all you need is a random number, who cares how it goes about doing it, as long as it is fast and produces a reasonable distribution of psuedo-random numbers.///////////////////

You are right, I dont care how it works, but I need it to be in a function so I can call it whenever I need it, otherwise its useless to me. And to put it in that function, I need to know what ///MTRand mtrand1;/// and ///int d = mtrand1.randInt( 42 );/// are.

////////////////////////////"MTRand mtrand1;" is declaring an instance of the object MTRand. This is basic C++. "mtrand1.randInt()" is calling a method of the object MTRand. Again, basic C++. Using them in a function is already given as an example: main() is a function. ////////////////////////

What exactly is an object? Is it a variable? How does this relate to what is in MersenneTwister.h? How can I declare/call this in a function? I tried cutting the code from main and sticking it in my function, but it didnt work.

//////////////////////getRandom() above is a function. I''m not sure what you don''t understand about this usage./////////////////////////

This is also syntax I dont understand. The point is I dont know what this is, and therefore dont know how to port this into a function. It may be just because my C++ isnt up to par. In either case, any further help with this is appreciated.

-Noods

Geta

136

August 28, 2001 08:34 AM

quote:
Original post by Anonymous Poster
OK. For all intensive purposes, I will say I am new to C++, therefore common C++ may be alien to me. So now, I have some more questions...

You are going to have to be able to understand some basics before anyone is going to be
able to be of much help to you. There are begining programming articles all over the web.

quote:

Whats a ceiling, in terms of C++?

////////////int getRandom(int iCeiling)
{
return gMT.randInt(iCeiling);
}

where gMT is a globally available instance of MTRand, that is declared with a simple "MTRand gMT;"
(and should be seeded before use) and is located outside of your main() above.//////////////

Ok, I think I understand the instance and declaration, but what is gMT, a variable?

"ceiling" is a parameter name, as in function parameter .
"gMT" is the name of an instance of a MTRand object that is declared outside of all your functions
and thus through reference is available to all your functions. Lookup "global variables".

quote:

////////////////////Why? If all you need is a random number, who cares how it goes about doing it, as long as it is fast and produces a reasonable distribution of psuedo-random numbers.///////////////////

You are right, I dont care how it works, but I need it to be in a function so I can call it whenever I need it, otherwise its useless to me. And to put it in that function, I need to know what ///MTRand mtrand1;/// and ///int d = mtrand1.randInt( 42 );/// are.

////////////////////////////"MTRand mtrand1;" is declaring an instance of the object MTRand. This is basic C++. "mtrand1.randInt()" is calling a method of the object MTRand. Again, basic C++. Using them in a function is already given as an example: main() is a function. ////////////////////////

What exactly is an object? Is it a variable? How does this relate to what is in MersenneTwister.h? How can I declare/call this in a function? I tried cutting the code from main and sticking it in my function, but it didnt work.

You can''t just cut and paste code and expect things to work. Programming is not that way.

"MersenneTwister.h" declares the class MTRand which encapsulates the data and methods
that define the object that does the work of the MT.

If you don''t know what an object is, then do a google search on "C++ Tutorials" and study
some C++ tutorials.

I already gave you an example of calling a method (the randInt() method of the object mtrand1)
in the "GetRandom()" example.

quote:

//////////////////////getRandom() above is a function. I''m not sure what you don''t understand about this usage./////////////////////////

This is also syntax I dont understand. The point is I dont know what this is, and therefore dont know how to port this into a function. It may be just because my C++ isnt up to par. In either case, any further help with this is appreciated.

"int getRandom(int iCeiling)" is a C function declaration that accepts an integer function parameter (the
''iCeiling'') and returns an integer. The ''iCeiling'' in this case is the number passed to the MT randInt()
method and acts as a ceiling (as in floor and ceiling, or min and max, or low and high) for the random
number (look at all iCeiling is used in getRandom()). If you don''t understand that syntax then you should
do a google search on "C Language Tutorials" and study.

Eric

Mathematix

259

September 01, 2001 08:33 PM

quote:
Original post by Noods
Hi all.

Im trying to generate a random number with the built in rand and srand abilities, but I cannot get this to "re-seed." I have coded these to generate a random number between 0 and a specified max, but all that happens is the main seed is generated, and I get the same random (ha!) number through out the program. Any help is appreciated. If someone has an
alternate method of generating random numbers they wouldnt mind sharing that would be awesome. Here is the code I am using, it is a simple bit of code that would eventually be elaborated on to make a D&D like character generation program. I have included multiple couts in my loop to identify what value the variables held at different time in the executable.

-Noods

A book called ''Numerical Recipes in C'' has very good random number generators that avoid the use of the predictable srand() function.

Regards,
Mathematix.

Timkin

864

September 03, 2001 08:54 PM

It seems that posting this code under its own header last week was not the way to go!

If you want to use this random number generator (from an algorithm by Knuth) then include the header in your module that uses the random number generator and link the compiled source file into your project. Call initRand() to initialise the generator (no seed is needed... it is generated from your system clock) and then use either random() to return a random double between 0 and 1 or random(low,high) to obtain a random integer between high and low.

NOTE: This code has not been optimised but is rather written for clarity of the algorithm. Feel free to optimise it to your hearts delight.

Here's the header file...

          #ifndef RAND_H#define RAND_Hvoid		initRand(void);void		advanceRand(void);double	        random(void);int		random(int low, int high);#endif

..and here's the source file.

                  /**************************************************************************** *  Module RAND.CPP                                                                                                             * *  Based on an algorithm by Donald Knuth                                                                                * *  (c) 2000 Tim Wilkin.                                                                                                          * *  Permission is hereby given to use this as you see fit. I ask only that you                                    * *  keep this header information intact.                                                                                     * ****************************************************************************/#include <time.h>#include "rand.h"#include <math.h>#include <iostream>#include <fstream>const	int  RAND_ARRAY_LEN=55;		// Length of array of stored random numbersconst int  SPECIAL_INDEX=24;		// Just what the name suggests!static double	oldRand[RAND_ARRAY_LEN];	// Array of random numbersstatic unsigned int	index2Rand = 0;      // Index into array of randoms/********************************************** * Function: initRand. Initialise the random number generator  *       **********************************************/void	initRand(void){   long totalseconds = time(NULL);   int seconds = static_cast<int>(totalseconds%60L);	double seed = 0.91999/ seconds;   double	newRand = 1.0e-9;   double	prevRand = seed;   oldRand[RAND_ARRAY_LEN-1] = prevRand;   for (unsigned int i=0; i<RAND_ARRAY_LEN; i++)   {   	unsigned int j = (21*i) % RAND_ARRAY_LEN;      oldRand[j] = newRand;      newRand = prevRand - newRand;      if (newRand < 0.0)      	newRand += 1.0;      prevRand = oldRand[j];   }   advanceRand();   advanceRand();   advanceRand();   index2Rand = 0;}/********************************************************************** * Function: advanceRand. Function to generate new random numbers once array is used up * **********************************************************************/void advanceRand(void){	double	newRand;   for (unsigned int j=0; j<SPECIAL_INDEX; j++)   {   	newRand = oldRand[j]-oldRand[j+(RAND_ARRAY_LEN-SPECIAL_INDEX)];      if (newRand < 0.0)      	newRand += 1.0;      oldRand[j] = newRand;   }   for (unsigned int j=SPECIAL_INDEX; j<RAND_ARRAY_LEN; j++)   {   	newRand = oldRand[j] - oldRand[j-SPECIAL_INDEX];      if (newRand < 0.0)      	newRand += 1.0;      oldRand[j] = newRand;   }}/******************************************************************* * Function: random(void). Generate a double precision random number from the set [0,1] * *******************************************************************/double random(void){   index2Rand++;   if (index2Rand >= RAND_ARRAY_LEN)   {   	index2Rand = 0;      advanceRand();   }   return oldRand[index2Rand];}/******************************************************************** * Function: random(low,high). Generate an integer random number from the set [low,high] * ********************************************************************/int	random(int low, int high){	if (low>=high)   	return low;	int	tempRand = floor(random()*(double)(high-low+1) + (double)low);   if (tempRand > high)   	tempRand = high;   return tempRand;}

Questions can be directed to me at taw@csse.monash.edu.au

Cheers,

Timkin

Edited by - Timkin on September 3, 2001 9:56:21 PM