Problem using rand() function

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?
--
Chris Gordon-Smith
London
http://www.simsoup.info

re: Problem using rand() function

"Chris Gordon-Smith" <use.address@my.homepage> wrote in message
news:3qssj7Fg6preU1@individual.net...[color=blue]
>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?
> --
> Chris Gordon-Smith
> London
> http://www.simsoup.info
>[/color]

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.

--
Cy
http://home.rochester.rr.com/cyhome/

re: Problem using rand() function

Cy Edmunds wrote:
[color=blue]
>
> 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.
>[/color]

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.

--
Chris Gordon-Smith
London
http://www.simsoup.info

re: Problem using rand() function

Chris Gordon-Smith wrote:
[color=blue]
> 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?[/color]

Yes, that is the obvious guess.

[color=blue]
> 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?[/color]

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

re: Problem using rand() function

Kai-Uwe Bux wrote:
[color=blue]
> Chris Gordon-Smith wrote:
>[color=green]
>> 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?[/color]
>
> Yes, that is the obvious guess.
>
>[color=green]
>> 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?[/color]
>
> 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.
> */[/color]
[snip][color=blue]
>
> 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[/color]

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.

--
Chris Gordon-Smith
London
http://www.simsoup.info

re: Problem using rand() function

Chris Gordon-Smith wrote:
[snip][color=blue]
> 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.[/color]

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.

re: Problem using rand() function

Kai-Uwe Bux wrote:
[color=blue]
> Chris Gordon-Smith wrote:
> [snip][color=green]
>> 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.[/color]
>
> 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.[/color]

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
London
http://www.simsoup.info

re: Problem using rand() function

Chris Gordon-Smith wrote:
[color=blue]
> Kai-Uwe Bux wrote:
>[color=green]
>> Chris Gordon-Smith wrote:
>> [snip][color=darkred]
>>> 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.[/color]
>>
>> 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.[/color]
>
> 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.[/color]

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


--
Chris Gordon-Smith
London
http://www.simsoup.info