Velocity Reviews > C++ > Generating 2 independent random numbers

# Generating 2 independent random numbers

bilgekhan
Guest
Posts: n/a

 05-28-2008
What is the correct method for generating 2 independent random numbers?
They will be compared whether they are equal.

srand(time(0));
int r1 = rand();
srand(rand());
int r2 = rand();
bool f = r1 == r2;

bilgekhan
Guest
Posts: n/a

 05-28-2008
In my prev. posting I forgot to mention that the
random numbers shall be in the range 0 to 99.
So here my updated question:

What is the correct method for generating
2 independent random numbers in the range 0 to 99 ?
They will immediately be compared for equality.

srand(time(0));
int r1 = rand() % 100;
srand(rand());
int r2 = rand() % 100;
bool f = r1 == r2;

Pascal J. Bourguignon
Guest
Posts: n/a

 05-28-2008
"bilgekhan" <(E-Mail Removed)> writes:

> In my prev. posting I forgot to mention that the
> random numbers shall be in the range 0 to 99.
> So here my updated question:
>
> What is the correct method for generating
> 2 independent random numbers in the range 0 to 99 ?
> They will immediately be compared for equality.

What Sam said.

>
> srand(time(0));
> int r1 = rand() % 100;
> srand(rand());
> int r2 = rand() % 100;
> bool f = r1 == r2;

The rand() function returns a pseudo-random integer between 0 and RAND_MAX.

Therefore, assuming it's excluding RAND_MAX, and including 0, and
assuming each value is equiprobable (which is not specified by the man
page of rand(3) on Linux), if RAND_MAX % 100 is not 0, then your
randoms r1 and r2 won't be equiprobable.

But this is already assuming too much, as further reading of the
rand(3) man page.

If you care so little about your randomness, you could as well write

bool f=((rand()%100)==(rand()%100));

--
__Pascal Bourguignon__

Kai-Uwe Bux
Guest
Posts: n/a

 05-28-2008
bilgekhan wrote:

> In my prev. posting I forgot to mention that the
> random numbers shall be in the range 0 to 99.
> So here my updated question:
>
> What is the correct method for generating
> 2 independent random numbers in the range 0 to 99 ?
> They will immediately be compared for equality.
>
>
> srand(time(0));
> int r1 = rand() % 100;
> srand(rand());
> int r2 = rand() % 100;
> bool f = r1 == r2;

Not good: the reseeding of the RNG just has unknown effects. If the RNG used
by rand() is good, the reseeding very likely will make it worse. At the
very least, you loose all the good things that the theory inspiring the RNG
guarantees.

a) How to generate independently distributed random numbers?

b) How to generate random numbers in [0,100)?

As for (a), any RNG is supposed to yield pseudo random numbers that look
independent. Therefore, just using a decent RNG will take care of the
independence requirement.

As for (b), the %-trick is probably good enough for your purposes. However,
beware that unless RAND_MAX+1 is divisible by 100.

As for the immediate comparison part: if you discard r1 and r2 immediately
after the comparison, and only keep f, then it suffices to generate one
number r in [0,100) and do:

bool f = ( r == 0 );

because that will yield true with probability 0.01, too.

Best

Kai-Uwe Bux

Lionel B
Guest
Posts: n/a

 05-28-2008
On Wed, 28 May 2008 13:08:17 +0200, bilgekhan wrote:

> In my prev. posting I forgot to mention that the random numbers shall be
> in the range 0 to 99. So here my updated question:
>
> What is the correct method for generating 2 independent random numbers
> in the range 0 to 99 ? They will immediately be compared for equality.

As others have mentioned, most random number generators (and almost
certainly your `rand()' call) generate *pseudo*-random sequences of
numbers. "Real" random number sequences (and it's by no means trivial to
say what that even means) are hard to come by and will generally involve
some hardware-based solution. I'll assume that pseudo random is good

But be aware that there is a huge variation in the "randomness" of
sequences generated by pseudo random generators. The system-supplied
generators (like `rand()') are often astonishingly non-random, and the
(current) C++ standard allows them to be as cruddy as they please.
Thankfully, the forthcoming C++ standard will include some higher quality
generators such as the Mersenne Twister (recommended, Google it). But
even that would not be good enough e.g. for cryptographic purposes.

>
> srand(time(0));

This is ok as long as you don't call this routine again so quickly that
time(0) returns the same value as for the last call.

> int r1 = rand() % 100;

This can be a bad idea, particularly for so-called "linear congruential"
rngs (and there's a fair chance your `rand()' will be linear
congruential). The reason for this is that mod-ing a number basically
involves using just the lower-order bits, which for many rngs - and
linear congruential ones in particular - are frequently the "least
random".

Safer is something along the lines of:

int r1 = int(100.0*double(rand())/double(RAND_MAX));

that is, you generate a uniform(ish) random double in the range [0,1),
multiply it by 100 and take the integer part. This gives you a uniform
(ish) random int in the range [0,99). It's safer because it relies more
heavily on the higher-order bits of the number returned by your rng.

> srand(rand());

^^^^^^^^^^^^^^

Probably a bad idea to re-seed your rng with a number generated by the
same rng... and pointless in any case. Seed once and generate away...
Leave out that line.

> int r2 = rand() % 100;

Again, as for r1 above.

> bool f = r1 == r2;

--
Lionel B

bilgekhan
Guest
Posts: n/a

 05-28-2008
"Pascal J. Bourguignon" wrote:
> "bilgekhan" writes:
>
> > In my prev. posting I forgot to mention that the
> > random numbers shall be in the range 0 to 99.
> > So here my updated question:
> >
> > What is the correct method for generating
> > 2 independent random numbers in the range 0 to 99 ?
> > They will immediately be compared for equality.

>
> What Sam said.
>
> >
> > srand(time(0));
> > int r1 = rand() % 100;
> > srand(rand());
> > int r2 = rand() % 100;
> > bool f = r1 == r2;

>
> The rand() function returns a pseudo-random integer between 0 and RAND_MAX.
>
> Therefore, assuming it's excluding RAND_MAX, and including 0, and
> assuming each value is equiprobable (which is not specified by the man
> page of rand(3) on Linux), if RAND_MAX % 100 is not 0, then your
> randoms r1 and r2 won't be equiprobable.
>
> But this is already assuming too much, as further reading of the
> rand(3) man page.
>
>
> If you care so little about your randomness, you could as well write
>
> bool f=((rand()%100)==(rand()%100));

Have you tried this in a loop of say 1 million times and counted the hits?
I think theoretically there should be about 10,000 matches.
What result do you get?
Maybe 0 ?

Lionel B
Guest
Posts: n/a

 05-28-2008
On Wed, 28 May 2008 14:26:27 +0200, bilgekhan wrote:

> "Pascal J. Bourguignon" wrote:
>> "bilgekhan" writes:
>>
>> If you care so little about your randomness, you could as well write
>>
>> bool f=((rand()%100)==(rand()%100));

>
> Have you tried this in a loop of say 1 million times and counted the
> hits? I think theoretically there should be about 10,000 matches. What
> result do you get?
> Maybe 0 ?

Why do you think you might get 0 ?

--
Lionel B

bilgekhan
Guest
Posts: n/a

 05-28-2008
"Kai-Uwe Bux" wrote:
> bilgekhan wrote:
>
> > In my prev. posting I forgot to mention that the
> > random numbers shall be in the range 0 to 99.
> > So here my updated question:
> >
> > What is the correct method for generating
> > 2 independent random numbers in the range 0 to 99 ?
> > They will immediately be compared for equality.
> >
> >
> > srand(time(0));
> > int r1 = rand() % 100;
> > srand(rand());
> > int r2 = rand() % 100;
> > bool f = r1 == r2;

>
> Not good: the reseeding of the RNG just has unknown effects. If the RNG used
> by rand() is good, the reseeding very likely will make it worse. At the
> very least, you loose all the good things that the theory inspiring the RNG
> guarantees.
>
> Your question has two aspects:
>
> a) How to generate independently distributed random numbers?
>
> b) How to generate random numbers in [0,100)?
>
> As for (a), any RNG is supposed to yield pseudo random numbers that look
> independent. Therefore, just using a decent RNG will take care of the
> independence requirement.

I did some experiments with the standard pseudo-RNG
of the compiler and I come to the conclusion that it is
impossible to let 1 RNG _correctly_ generate 2 independent
random numbers.
If someone manages this let me know pls, though
I solved my original problem by the clever method of Kai-Uwe below.

> As for (b), the %-trick is probably good enough for your purposes. However,
> beware that unless RAND_MAX+1 is divisible by 100.

Unfortuately it's not divisable by 100, and
unfortunately on my machine RAND_MAX is only 32767

> As for the immediate comparison part: if you discard r1 and r2 immediately
> after the comparison, and only keep f, then it suffices to generate one
> number r in [0,100) and do:
>
> bool f = ( r == 0 );
>
> because that will yield true with probability 0.01, too.

That's really a nice solution!
So there is no need for 2 random numbers at all,
and all the other associated problems with it.
Thanks, Kai-Uwe!

bilgekhan
Guest
Posts: n/a

 05-28-2008
"Lionel B" wrote:
> On Wed, 28 May 2008 14:26:27 +0200, bilgekhan wrote:
> > "Pascal J. Bourguignon" wrote:
> >>
> >> If you care so little about your randomness, you could as well write
> >> bool f=((rand()%100)==(rand()%100));

> >
> > Have you tried this in a loop of say 1 million times and counted the
> > hits? I think theoretically there should be about 10,000 matches. What
> > result do you get?
> > Maybe 0 ?

>
> Why do you think you might get 0 ?

Because it is the same sequence of the RNG...
A seed sequence of rand() always generates
RAND_MAX different random numbers.
So within a sequence it cannot generate the same number twice.
After generating RAND_MAX numbers the sequence
starts over again to generate again the same sequence of numbers.

Since the program is within the same sequence
and since the two numbers are generated together
it never can happen that these 2 numbers somehow match...

Ie. rand() is predictable: if you generate RAND_MAX numbers
and store them somewhere then you can look there what random
number it will generate next.
But this works only if you don't change the rand sequence
by calling srand() a second time.

I did some experiments and I come to the conclusion
that it is not NOT possible to let 1 RNG _correctly_ generate
2 independent random numbers.
One has to solve it cleverly via just 1 random number only
as was shown by Kai-Uwe Bux (cf. his posting).

Lionel B
Guest
Posts: n/a

 05-28-2008
On Wed, 28 May 2008 16:22:43 +0200, bilgekhan wrote:

> "Lionel B" wrote:
>> On Wed, 28 May 2008 14:26:27 +0200, bilgekhan wrote:
>> > "Pascal J. Bourguignon" wrote:
>> >>
>> >> If you care so little about your randomness, you could as well write
>> >> bool f=((rand()%100)==(rand()%100));
>> >
>> > Have you tried this in a loop of say 1 million times and counted the
>> > hits? I think theoretically there should be about 10,000 matches.
>> > What result do you get?
>> > Maybe 0 ?

>>
>> Why do you think you might get 0 ?

>
> Because it is the same sequence of the RNG... A seed sequence of
> rand() always generates RAND_MAX different random numbers.

Really? The documentation for my system doesn't say that. It simply says:
"The rand() function returns a pseudo-random integer between 0 and
RAND_MAX". Maybe your rand() does what you say... there is no requirement
for it to do so.

In any case, that's irrelevant, since x !=y does not imply x%100 != y%
100. Think about it - and try it:

#include <iostream>
#include <cstdlib>

int main()
{
const int N = 1000000;

int hits = 0;
for (int n=0;n<N;++n)
if ((std::rand()%100)==(std::rand()%100)) ++hits;

std::cout << "hits = " << hits << '\n';
}

On my system this outputs:

hits = 10195

--
Lionel B