Kai-Uwe Bux said:
Hi,
I think, RAND_MAX is neither a reasonable expectation nor an appropriate
constraint. Any definition of this identifier will be a global constant
and thus not be tied to a particular instance of an RNG.
Personally, I prefer to go with the precedent established by
std::random_shuffle, and assume that the user supplied RGN will be a
function object R that provides the signature
unsigned long R ( unsigned long );
where R(n) returns a pseudo random number in [0,n). Compare std:25.2.11
[lib.alg.random.shuffle].
The random number generators from the Boost libraries can all be used in
this way as the library comes with an appropriate adapter. Most clients of
your class will probably use the default RNG of RNGs from that library.
Best
Kai-Uwe
To embark on this a little, I have drafted some code that wraps around the
two RNGs proposed in this thread: Here are two classes RNG_cstdlib and
RNG_crandom. Both implement a constructor that does the seeding, and define
unsigned long operator( unsigned long );
The implementation of this operator uses higher order bits. This is
especially important in the case of RNG_crandom as the lower order bits
of that RNG are particularly weak.
The sample code below uses these classes to simulate a coin. It then
proceeds to measure the average length of runs. The expected result is 2.
It should be noted that RNG_crandom has consistently runs that are a little
too long. The reason is that the multiplyer 37 is way too small.
#include <cstdlib>
class RNG_cstdlib {
private:
static
const unsigned long rand_max = RAND_MAX;
public:
RNG_cstdlib ( void ) {}
RNG_cstdlib ( unsigned long seed ) {
std::srand( seed );
}
unsigned long operator() ( unsigned long bound ) {
/*
| We will use the higher order bits of rand().
| Moreover, we avoid floating point arithmetic.
| The cost is that we might have to call rand()
| multiple times.
*/
unsigned long int int_width = rand_max / bound;
unsigned long int max_valid = int_width * bound;
/*
| max_valid is at least rand_max / 2.
*/
/*
| The following loop will be traversed
| rand_max/max_valid < 2 times on the average:
*/
while ( true ) {
// in the worst case, we
unsigned long int raw_random ( std::rand() );
if ( raw_random < max_valid ) {
return( raw_random / int_width );
}
}
}
}; // RNG_cstdlib
class RNG_crandom {
private:
static
const unsigned long internal_max = 4<<30;
static
const unsigned long rand_max = 4<<28;
unsigned long number;
public:
RNG_crandom ( void ) :
number( std::rand() )
{}
RNG_crandom (unsigned long int seed ) :
number( seed + 1 )
{}
unsigned long operator() ( unsigned long bound ) {
unsigned long int int_width = rand_max / bound;
unsigned long int max_valid = int_width * bound;
/*
| max_valid is at least rand_max / 2.
*/
/*
| The following loop will be traversed
| rand_max/max_valid < 2 times on the average:
*/
while ( true ) {
number=(number*37)&( internal_max - 1 );
unsigned long raw_random ( number >>2 );
if ( raw_random < max_valid ) {
return( raw_random / int_width );
}
}
}
}; // RNG_crandom
template < typename RNG >
double average_length_of_runs ( unsigned long tries,
RNG R ) {
unsigned int count = 1;
unsigned int parity = R(2);
for ( unsigned int i = 0; i < tries; ++i ) {
unsigned int next = R(2);
while ( parity == next ) {
++ count;
next = R(2);
}
parity = next;
++count;
}
return( double( count ) / double( tries ) );
}
#include <iostream>
int main ( void ) {
for ( unsigned long seed = 0; seed < 1000000; seed += 12334 ) {
std::cout << average_length_of_runs( 1000000, RNG_cstdlib( seed ) ) <<
" ";
std::cout << average_length_of_runs( 1000000, RNG_crandom( seed ) ) <<
std::endl;
}
}
