Problem using rand() function

[Chris Gordon-Smith]

I have a simulation program that calls the rand() function at various points
while it executes.

For the user interface that displays statistics etc. while the program runs,
I use the Lazarus GUI library, which is based on GTK. Depending on which
libraries I link in, I can have either a GTK1 or GTK2 user interface.

I'm finding that the simulation behaves differently depending on whether I
link with GTK1 or GTK2.

I think the reason for this may be that one or both of the graphics
libraries (GTK1 / 2) is calling rand(), and they call it in different ways
so that when my own program calls rand() it sees a different sequence of
random numbers depending on how GTK1 / 2 have been calling rand().

Firstly, can anyone comment. Is this likely to be the problem?

Secondly, what can I do about it? Can I somehow put together my own version
of rand() that is not disrupted by calls to the random number generator
being made by the graphics software?

 

[Cy Edmunds]

I have a simulation program that calls the rand() function at various
points
while it executes.

For the user interface that displays statistics etc. while the program
runs,
I use the Lazarus GUI library, which is based on GTK. Depending on which
libraries I link in, I can have either a GTK1 or GTK2 user interface.

I'm finding that the simulation behaves differently depending on whether I
link with GTK1 or GTK2.

I think the reason for this may be that one or both of the graphics
libraries (GTK1 / 2) is calling rand(), and they call it in different ways
so that when my own program calls rand() it sees a different sequence of
random numbers depending on how GTK1 / 2 have been calling rand().

Firstly, can anyone comment. Is this likely to be the problem?

Secondly, what can I do about it? Can I somehow put together my own
version
of rand() that is not disrupted by calls to the random number generator
being made by the graphics software?

I don't know why you are having this problem, but it is never a bad idea to
use a good third party number generator rather than rand(). I suggest you
look at www.boost.org for better alternatives.

 

[Chris Gordon-Smith]

I don't know why you are having this problem, but it is never a bad idea
to use a good third party number generator rather than rand(). I suggest
you look at www.boost.org for better alternatives.

That's certainly an option. My initial thought however is that my
requirement is very simple and I'm reluctant to start using another fairly
sophisticated library (in addition to the STL).

This is partly because it may be a sledgehammer to crack a nut, and partly
because the Boost licence is not the same as the GPL, so that it will
complicate things when I release my code under the GPL.

 

[Kai-Uwe Bux]

I have a simulation program that calls the rand() function at various
points while it executes.

For the user interface that displays statistics etc. while the program
runs, I use the Lazarus GUI library, which is based on GTK. Depending on
which libraries I link in, I can have either a GTK1 or GTK2 user
interface.

I'm finding that the simulation behaves differently depending on whether I
link with GTK1 or GTK2.

I think the reason for this may be that one or both of the graphics
libraries (GTK1 / 2) is calling rand(), and they call it in different ways
so that when my own program calls rand() it sees a different sequence of
random numbers depending on how GTK1 / 2 have been calling rand().

Firstly, can anyone comment. Is this likely to be the problem?

Yes, that is the obvious guess.

Secondly, what can I do about it? Can I somehow put together my own
version of rand() that is not disrupted by calls to the random number
generator being made by the graphics software?

It appears that you need a RNG that allows you to create independent
instances so that calls to one RNG object do not affect the sequences
produced by other instances. For the reason you mentioned, rand() will not
be useful here.

RNGs are tricky. You may want to have a look into boost.

If your requirements are really low, or you just want to try out something,
you can use a *very* simple linear congruence RNG like this one:


class SimpleRandomNumberGenerator {
/*
| This is a simple linear congruence random number generator.
| It is *not* meant to be a good generator. (However, the
| multiplier chosen is not too bad.)
|
| The whole point of this class is that you can have several
| independend instances of SimpleRandomNumberGenerator.
*/
private:

static
const unsigned long lower_bound = 0;

static
const unsigned long upper_bound = 0xffffffff;

public:
/*
| The modulus of this generator is 2^32. The multiplier is taken
| from Knuth [line 16 in table 1 of section 3.3.4]. This shift is
| a bad guess.
*/


SimpleRandomNumberGenerator ( unsigned long _seed ) :
seed( _seed )
{}

unsigned long lower ( void ) const {
return ( lower_bound );
}

unsigned long upper ( void ) const {
return ( upper_bound );
}

unsigned long operator() ( void ) {
// return a random number in [lower(),upper()]
seed = ( seed * a + c ) & upper_bound;
return( seed );
}

unsigned long operator() ( unsigned long bound ) {
// return a random number in [0,bound)
unsigned long int_width = upper_bound / bound;
unsigned long max_valid = int_width * bound;
do {
seed = ( seed * a + c ) & upper_bound;
} while ( seed >= max_valid );
return( seed / int_width );
}

private:

mutable unsigned long seed;
static const unsigned long a = 1664525U;
static const unsigned long c = 31415927U;

}; // class SimpleRandomNumberGenerator


You use this like so:

SimpleRandomNumberGenerator RNG ( 1234 );
...
if ( RNG(2) ) { // unbiased coin
}
...
std::random_shuffle( v.begin(), v.end, RNG );
...

g = RNG(200) // random number below 200

and RNG() can be used as a substitute for rand().


Beware that simple linear congruence RNGs have not-quite-that-random lower
order bits. The operator()(bound) tries its best to work around that
limitation. Also, it produces evenly distributed results even if bound is
not a power of 2. As a price it might change the internal state several
times. However, the loop will be traversed at most twice (on the average).

This code at least illustrates how one can go about implementing a RNG that
allows for independent instances each of which keeps its own internal
state. For production code, however, I would recommend using a solution
from boost.


Best

Kai-Uwe Bux

 

[Chris Gordon-Smith]

I have a simulation program that calls the rand() function at various
points while it executes.

For the user interface that displays statistics etc. while the program
runs, I use the Lazarus GUI library, which is based on GTK. Depending on
which libraries I link in, I can have either a GTK1 or GTK2 user
interface.

I'm finding that the simulation behaves differently depending on whether
I link with GTK1 or GTK2.

I think the reason for this may be that one or both of the graphics
libraries (GTK1 / 2) is calling rand(), and they call it in different
ways so that when my own program calls rand() it sees a different
sequence of random numbers depending on how GTK1 / 2 have been calling
rand().

Firstly, can anyone comment. Is this likely to be the problem?

Yes, that is the obvious guess.

Secondly, what can I do about it? Can I somehow put together my own
version of rand() that is not disrupted by calls to the random number
generator being made by the graphics software?

It appears that you need a RNG that allows you to create independent
instances so that calls to one RNG object do not affect the sequences
produced by other instances. For the reason you mentioned, rand() will not
be useful here.

RNGs are tricky. You may want to have a look into boost.

If your requirements are really low, or you just want to try out
something, you can use a *very* simple linear congruence RNG like this
one:


class SimpleRandomNumberGenerator {
/*
| This is a simple linear congruence random number generator.
| It is *not* meant to be a good generator. (However, the
| multiplier chosen is not too bad.)
|
| The whole point of this class is that you can have several
| independend instances of SimpleRandomNumberGenerator.
*/ [snip]

This code at least illustrates how one can go about implementing a RNG
that allows for independent instances each of which keeps its own internal
state. For production code, however, I would recommend using a solution
from boost.
instances.

Best

Kai-Uwe Bux

Thanks for this.

How about this as an alternative:-

Create a class that has an internal cache of random numbers. Initialise the
cache at construction time by calling rand() repeatedly. Then use a class
method to supply random numbers as and when they are required. When the
last random number in the cache is reached, re-initialise the cache using
the last random number in the cache as the seed for srand(seed).

I think that this approach should enable my simulation code to be isolated
from the effects of other parts of the program (eg library code) calling
rand(), and it does not need a new random number generator to be
implemented.

 

[Kai-Uwe Bux]

Chris Gordon-Smith wrote:
[snip]

How about this as an alternative:-

Create a class that has an internal cache of random numbers. Initialise
the cache at construction time by calling rand() repeatedly. Then use a
class method to supply random numbers as and when they are required. When
the last random number in the cache is reached, re-initialise the cache
using the last random number in the cache as the seed for srand(seed).

I think that this approach should enable my simulation code to be isolated
from the effects of other parts of the program (eg library code) calling
rand(), and it does not need a new random number generator to be
implemented.

The rule of thumb is to seed once and only once.

Therefore, I would be worried about the quality of the RNG resulting from
your method. Let me illustrate this using the period as a rough measure of
quality. Assuming that your library comes with a good RNG, its internal
state is very likely much more than just some 32 bits from a seed. Since
the internal state is finite, the sequence of random number eventually will
cycle. The internal state can be considered as the current position within
that cycle. What you suggest is to reseed periodically. Now, you construct
a new internal state from the 32-bit seed (I am assuming here that unsigned
long is 32 bits, but in any case it is probably much less than the internal
state of your libraries RNG). That means that at the reseeding points not
all possible positions in the cycle are possible targets for your jump.
Thus, your operation will very likely reduce the period of the RNG quite a
bit. I would guess you ca get at most a period of length:

cache_size * 2^bitlength(seed)

This period is very likely much smaller than the original period. And, the
actual period you get could be much smaller than the upper bound given
above.

Also, keep in mind D. Knuth's warning: "... random number should not be
generated with a method chosen at random. Some theory should be used." Very
likely, the RNG in your library was designed using some reasonable
mathematics to make sure that the results are decent. Your proposed method
will break the theory and can result in poor quality. My understanding is
that examples of such side-effects abound.

For more qualified answers, you might try:

sci.crypt.random-numbers

or some other more appropriate source.


Best

Kai-Uwe Bux

ps.: I still think you would be better off looking into boost.

 

[Chris Gordon-Smith]

Chris Gordon-Smith wrote:
[snip]

How about this as an alternative:-

Create a class that has an internal cache of random numbers. Initialise
the cache at construction time by calling rand() repeatedly. Then use a
class method to supply random numbers as and when they are required. When
the last random number in the cache is reached, re-initialise the cache
using the last random number in the cache as the seed for srand(seed).

I think that this approach should enable my simulation code to be
isolated from the effects of other parts of the program (eg library code)
calling rand(), and it does not need a new random number generator to be
implemented.

The rule of thumb is to seed once and only once.

Therefore, I would be worried about the quality of the RNG resulting from
your method. Let me illustrate this using the period as a rough measure of
quality. Assuming that your library comes with a good RNG, its internal
state is very likely much more than just some 32 bits from a seed. Since
the internal state is finite, the sequence of random number eventually
will cycle. The internal state can be considered as the current position
within that cycle. What you suggest is to reseed periodically. Now, you
construct a new internal state from the 32-bit seed (I am assuming here
that unsigned long is 32 bits, but in any case it is probably much less
than the internal state of your libraries RNG). That means that at the
reseeding points not all possible positions in the cycle are possible
targets for your jump. Thus, your operation will very likely reduce the
period of the RNG quite a bit. I would guess you ca get at most a period
of length:

cache_size * 2^bitlength(seed)

This period is very likely much smaller than the original period. And, the
actual period you get could be much smaller than the upper bound given
above.

Also, keep in mind D. Knuth's warning: "... random number should not be
generated with a method chosen at random. Some theory should be used."
Very likely, the RNG in your library was designed using some reasonable
mathematics to make sure that the results are decent. Your proposed method
will break the theory and can result in poor quality. My understanding is
that examples of such side-effects abound.

For more qualified answers, you might try:

sci.crypt.random-numbers

or some other more appropriate source.


Best

Kai-Uwe Bux

ps.: I still think you would be better off looking into boost.

Thanks for this comprehensive answer. Despite my reluctance to start using a
new library, I suspect that you and Cy Edmunds are probably right. If the
cycle time is at the theoretical maximum you mention above that is probably
good enough for my purposes. The worry is that it could perhaps be much
less.

 

[Chris Gordon-Smith]

Chris Gordon-Smith wrote:
[snip]

How about this as an alternative:-

Create a class that has an internal cache of random numbers. Initialise
the cache at construction time by calling rand() repeatedly. Then use a
class method to supply random numbers as and when they are required.
When the last random number in the cache is reached, re-initialise the
cache using the last random number in the cache as the seed for
srand(seed).

I think that this approach should enable my simulation code to be
isolated from the effects of other parts of the program (eg library
code) calling rand(), and it does not need a new random number generator
to be implemented.

The rule of thumb is to seed once and only once.

Therefore, I would be worried about the quality of the RNG resulting from
your method. Let me illustrate this using the period as a rough measure
of quality. Assuming that your library comes with a good RNG, its
internal state is very likely much more than just some 32 bits from a
seed. Since the internal state is finite, the sequence of random number
eventually will cycle. The internal state can be considered as the
current position within that cycle. What you suggest is to reseed
periodically. Now, you construct a new internal state from the 32-bit
seed (I am assuming here that unsigned long is 32 bits, but in any case
it is probably much less than the internal state of your libraries RNG).
That means that at the reseeding points not all possible positions in the
cycle are possible targets for your jump. Thus, your operation will very
likely reduce the period of the RNG quite a bit. I would guess you ca get
at most a period of length:

cache_size * 2^bitlength(seed)

This period is very likely much smaller than the original period. And,
the actual period you get could be much smaller than the upper bound
given above.

Also, keep in mind D. Knuth's warning: "... random number should not be
generated with a method chosen at random. Some theory should be used."
Very likely, the RNG in your library was designed using some reasonable
mathematics to make sure that the results are decent. Your proposed
method will break the theory and can result in poor quality. My
understanding is that examples of such side-effects abound.

For more qualified answers, you might try:

sci.crypt.random-numbers

or some other more appropriate source.


Best

Kai-Uwe Bux

ps.: I still think you would be better off looking into boost.

Thanks for this comprehensive answer. Despite my reluctance to start using
a new library, I suspect that you and Cy Edmunds are probably right. If
the cycle time is at the theoretical maximum you mention above that is
probably good enough for my purposes. The worry is that it could perhaps
be much less.

I've now implemented my own version of rand(), based on the idea of holding
a cache of 10,000 random numbers as described above.

I've tested it by calling it one thousand million times and writing out the
value of the random number taken from the cache whenever it lies in the
range 100000000 to 100000050.

I have included the output below. As you can see, the sequence repeats
itself four times, which means that the sequence repeats roughly every 250
million calls to my random function.

This is good enough for my purposes.

Current_Seq_Val = 100000028
Current_Seq_Val = 100000026
Current_Seq_Val = 100000038
Current_Seq_Val = 100000034
Current_Seq_Val = 100000003
Current_Seq_Val = 100000003
Current_Seq_Val = 100000028
Current_Seq_Val = 100000026
Current_Seq_Val = 100000038
Current_Seq_Val = 100000034
Current_Seq_Val = 100000003
Current_Seq_Val = 100000003
Current_Seq_Val = 100000028
Current_Seq_Val = 100000026
Current_Seq_Val = 100000038
Current_Seq_Val = 100000034
Current_Seq_Val = 100000003
Current_Seq_Val = 100000003
Current_Seq_Val = 100000028
Current_Seq_Val = 100000026
Current_Seq_Val = 100000038
Current_Seq_Val = 100000034
Current_Seq_Val = 100000003
Current_Seq_Val = 100000003
Current_Seq_Val = 100000028
Current_Seq_Val = 100000026
Current_Seq_Val = 100000038