By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
424,694 Members | 1,847 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 424,694 IT Pros & Developers. It's quick & easy.

Generating 2 independent random numbers

P: n/a
What is the correct method for generating 2 independent random numbers?
They will be compared whether they are equal.

What about this method:

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

Jun 27 '08 #1
Share this Question
Share on Google+
26 Replies


P: n/a
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 about this method:

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

Jun 27 '08 #2

P: n/a
Sam
bilgekhan writes:
What is the correct method for generating 2 independent random numbers?
They will be compared whether they are equal.

What about this method:

srand(time(0));
int r1 = rand();
srand(rand());
int r2 = rand();
bool f = r1 == r2;
If you truly need a source of random numbers, you're better off using a
cryptographic library like gcrypt or openssl that provide a "more random"
random number generator; they have a much more sophisticated mechanism of
seeding the entropy pool.

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (GNU/Linux)

iEYEABECAAYFAkg9PhMACgkQx9p3GYHlUOJLUgCdE0f2M85XqR TCvrSskDagRLbZ
7L0An0BGWYtrtdFvqs2rcSo3TXmlAJ23
=XdOJ
-----END PGP SIGNATURE-----

Jun 27 '08 #3

P: n/a
"bilgekhan" <bi*******@bilgekhanbilgekhan.net.trwrites:
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.
What about this method:

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__
Jun 27 '08 #4

P: n/a
On 2008-05-28 07:08:17 -0400, "bilgekhan"
<bi*******@bilgekhanbilgekhan.net.trsaid:
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 ?
What do you mean by "independent"?
They will immediately be compared for equality.

What about this method:

srand(time(0));
int r1 = rand() % 100;
srand(rand());
int r2 = rand() % 100;
bool f = r1 == r2;
It's probably overkill. The point of using random number generators is
that their output is (pseudo-)random. Whether any particular one
succeeds is, of course, a separate question. But hacking around with
reordering sequences is not a good approach unless you've analysed the
underlying sequences and understand what their limitations are. Knuth
gives an example where he wrote an algorithm that, for each number
need, randomly chose one of six or seven different algorithms to use.
Turned out to be worse than any of the individual algorithms.

--
Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com) Author of "The
Standard C++ Library Extensions: a Tutorial and Reference
(www.petebecker.com/tr1book)

Jun 27 '08 #5

P: n/a
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.

What about this method:

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.

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
Jun 27 '08 #6

P: n/a
"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.
What about this method:

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 ? :-)

Jun 27 '08 #7

P: n/a
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
Jun 27 '08 #8

P: n/a
"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.

What about this method:

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!

Jun 27 '08 #9

P: n/a
"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).

Jun 27 '08 #10

P: n/a
On 2008-05-28 10:22:43 -0400, "bilgekhan"
<bi*******@bilgekhanbilgekhan.net.trsaid:
"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.
It generates value in the range [0, RAND_MAX]. That doesn' t mean that
it will generate every number in that range once on each cycle, nor
does it mean that after it has generated every number it must repeat
the sequence.
After generating RAND_MAX numbers the sequence
starts over again to generate again the same sequence of numbers.
Not necessarily. The number of different values generated has no
inherent connection to the length of the sequence.

When I'm thinking about random number generators I find it helpful to
reduce the notion of a generator to something utterly trivial, to help
get the concepts straight. That makes it easier to understand less
simple ones. So for a trivial generator, pretend RAND_MAX is 1, that
is, the generator produces only 0's and 1's. Suppose it produces this
sequence: 0, 1, 0, 1, 1, 1, 0, 1, 0, then repeats. It's not
particularly useful, because its period is so short, but looking at the
first two values (i.e. RAND_MAX numbers), the sequence doesn't start
over again.
>
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. :-)
If you know how long the period of the generator is, you can store that
many numbers, and then you can "predict" what the next value will be.
But RAND_MAX is not the period; it's the maximum value that will be
produced.
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.
Define "independent". <g>

--
Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com) Author of "The
Standard C++ Library Extensions: a Tutorial and Reference
(www.petebecker.com/tr1book)

Jun 27 '08 #11

P: n/a
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
Jun 27 '08 #12

P: n/a
On 2008-05-28 10:22:29 -0400, "bilgekhan"
<bi*******@bilgekhanbilgekhan.net.trsaid:
>
Unfortuately it's not divisable by 100, and
unfortunately on my machine RAND_MAX is only 32767 :-(
The usual solution here is to compute the largest multiple of 100
that's less than RAND_MAX, and ignore any generated values that are
equal to or greater than that value:

int rand100()
{
const int max = (RAND_MAX / 100) * 100;
int tmp = rand();
while (max <= tmp)
tmp = rand();
return tmp % 100;
}

--
Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com) Author of "The
Standard C++ Library Extensions: a Tutorial and Reference
(www.petebecker.com/tr1book)

Jun 27 '08 #13

P: n/a
On May 28, 10:22*am, "bilgekhan" <bilgek...@bilgekhanbilgekhan.net.tr>
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.
No. It generates numbers between 0 and RAND_MAX. RAND_MAX has no
relationship to how long the period of the rand() RNG is.

Furthermore, even if you were right and it could only generate each
value once, mapping the RNG output to values [0, 100) means that many
(RAND_MAX/100) values from the RNG map to one value in the output, so
the expression rand() % 100 could very well generate '5' twice in a
row.
So within a sequence it cannot generate the same number twice.
False, or at best buggy. In fact, this is a dangerous property for an
RNG, and no respectable PRNG has it. If your system's rand() RNG
can't generate a value twice in the same period, report it to the
appropriate vendor's bug list and get it fixed.
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. *:-)
This is true: iff you know the period of your rng (the number of
samples it produces before repeating its list). However, the period
of rand() is allowed to be much larger than RAND_MAX -- in which case
it must, by simple counting logic, produce at least one value more
than once.
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).
Indeed. It's better to understand the probability distribution you
want -- often you can achieve it with only a single RNG, even for more
complicated distributions. Multiple RNG samples aren't any "more
random" than a single sample.
Jun 27 '08 #14

P: n/a
On 2008-05-28 11:01:03 -0400, Lionel B <me@privacy.netsaid:
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.
Right. Simple linear congruential generators typically have a RAND_MAX
whose value is one less than a power of two, and the generator produces
sequences whose length is RAND_MAX + 1. But that's an implementation
artifact, not a requirement. And an implementation that uses a more
sophisticated generator (for example, a linear congruential generator
that uses a 32-bit word, when rand() returns a 16-bit result) doesn't
do this.

--
Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com) Author of "The
Standard C++ Library Extensions: a Tutorial and Reference
(www.petebecker.com/tr1book)

Jun 27 '08 #15

P: n/a
Pete Becker wrote:
On 2008-05-28 10:22:43 -0400, "bilgekhan"
[snip]
>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.
If that is true, then the implementation of the RNG you are using sucks. A
good pseudo random number generator will pass tests for statistical
independence of subsequent returns.

Define "independent". <g>
As far as I can see, the OP just uses the ordinary concept of independent
random events/variables: knowing one does not help predicting the other.
Why do you ask? do you have any reason to suspect otherwise?
Best

Kai-Uwe Bux
Jun 27 '08 #16

P: n/a
On Wed, 28 May 2008 10:58:51 -0400, Pete Becker wrote:
On 2008-05-28 10:22:43 -0400, "bilgekhan"
<bi*******@bilgekhanbilgekhan.net.trsaid:
>"Lionel B" wrote:
>>On Wed, 28 May 2008 14:26:27 +0200, bilgekhan wrote:
"Pascal J. Bourguignon" wrote:
>

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.

Define "independent". <g>
I assume the OP intends "independent" in the (perfectly well-defined)
probability-theoretic sense.

I guess you could argue that it doesn't make much sense to talk about
independence of *pseudo* random numbers. In practice, however, you can
perfectly well look for statistics such as serial (sample) correlation
between successive random deviates generated by some PRNG - this is one
intuitive notion of "how independent" successive deviates are. This would
certainly be one (of many) tests routinely applied to gauge the quality
of a PRNG.

The whole question of "how random is a sequence of numbers" leads into
astonishingly deep and murky mathematical/philosophical waters (of which
I have little knowledge).

--
Lionel B
Jun 27 '08 #17

P: n/a
"bilgekhan" <bi*******@bilgekhanbilgekhan.net.trwrites:
"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.
What about this method:

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 ? :-)
Yes, that's what I'd expect. And that's why the OP could expect too,
"If [he] care[s] so little about [his] randomness" so as not to read
the rand(3) man page.

--
__Pascal Bourguignon__
Jun 27 '08 #18

P: n/a
"Pete Becker" wrote:
On 2008-05-28 10:22:29 -0400, "bilgekhan" said:

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

The usual solution here is to compute the largest multiple of 100
that's less than RAND_MAX, and ignore any generated values that are
equal to or greater than that value:

int rand100()
{
const int max = (RAND_MAX / 100) * 100;
int tmp = rand();
while (max <= tmp)
tmp = rand();
return tmp % 100;
}

Hmm... this method has a drawback of slowing the program.
If RAND_MAX is say 32767 then the window in the routine above
is just 0.3% of the full range, so in 99.7% of the calls it will waste
extra calls to rand()...

Jun 27 '08 #19

P: n/a
On Wed, 28 May 2008 17:36:52 +0200, bilgekhan wrote:
"Pete Becker" wrote:
>On 2008-05-28 10:22:29 -0400, "bilgekhan" said:
>
Unfortuately it's not divisable by 100, and unfortunately on my
machine RAND_MAX is only 32767 :-(

The usual solution here is to compute the largest multiple of 100
that's less than RAND_MAX, and ignore any generated values that are
equal to or greater than that value:

int rand100()
{
const int max = (RAND_MAX / 100) * 100; int tmp = rand();
while (max <= tmp)
tmp = rand();
return tmp % 100;
}


Hmm... this method has a drawback of slowing the program. If RAND_MAX is
say 32767 then the window in the routine above is just 0.3% of the full
range, so in 99.7% of the calls it will waste extra calls to rand()...
No, if RAND_MAX is 32767 then (RAND_MAX / 100) * 100 = 32700, so you
waste only about 0.2% of calls.

--
Lionel B
Jun 27 '08 #20

P: n/a
"Pete Becker" wrote:
On 2008-05-28 10:22:43 -0400, "bilgekhan" said:

If you know how long the period of the generator is, you can store that
many numbers, and then you can "predict" what the next value will be.
But RAND_MAX is not the period; it's the maximum value that will be
produced.
Ok, but it should be no problem to get the length of the period... :-)
For example:
Store, say 256 rand() call results in an array.
Then infinetely call rand() and check after how many calls
it repeats the same sequence stored in the array.... :-)
and then quit the loop.
A simpler way would be of course looking in the TM of the compiler/library...
(but OTOH who does RTFM ?... :-)
I did some experiments and I come to the conclusion
that it is NOT possible to let 1 RNG _correctly_ generate
2 independent random numbers.

Define "independent". <g>
Independent as so far as 2 consecutive calls to rand()
also generate twice the same random number as
theoretically would be expected in 10% of 1 million cases
when each time generating 2 numbers between 0 and 99.
That's 1e6 / 100 = 10000 = 10% of 1e6.

For achieving this independence one needs to switch
to another seed sequence. But my experiments show
that then the distribution is flawed as it deviates from
the theoretical expectation. I managed to get it within
+1.16% more matches by using the following ugly kludge:
srand((1U + rand()) * (1U + rand()) * 4U /* - 1 */);
as RAND_MAX on my machine is only 32767.
But then I discarded the idea of wanting to have just one RNG
generate such 2 independent random numbers.

Using just one RNG, and within the same period (srand sequence),
it is not possible to get the theoretically expected _correct_ number
of matches. Ie. one would need two identical but independent RNGs
and then both initialized with different seed values.

Jun 27 '08 #21

P: n/a
In article <g1**********@aioe.org>, bi*******@bilgekhanbilgekhan.net.tr
says...

[ ... ]
Because it is the same sequence of the RNG... :-)
A seed sequence of rand() always generates
RAND_MAX different random numbers.
False. It usually _will_, but there's no guarantee of it.
So within a sequence it cannot generate the same number twice.
Even more thoroughly false. I've cut out a bunch more statements, but
they all reflect the same misconception.

You're assuming that RAND_MAX reflects not only the range, but also the
period of the PRNG. While the standard's definition is loose enough to
_allow_ that, it's most assuredly not required. I'd add that, IMO, such
an implementation is _far_ from ideal.

From a practical viewpoint, having the range and the period of the
generator equal appears to be fairly unusual. For example, consider the
following code:

#include <stdlib.h>
#include <iostream>

int main() {
srand(1);

int i;

for (i=0; i<9; i++)
std::cout << rand() << "\t";
std::cout << "\n";

for (; i<RAND_MAX; i++)
rand();

for (i=0; i<9; i++)
std::cout << rand() << "\t";
std::cout << "\n";
return 0;
}

According to your statements, the two lines should be identical (with a
possible offset). With the compilers I have handy, that's not the case.
Here's the output from VC++ 7.1:

41 18467 6334 26500 19169 15724 11478 29358 26962
29246 17262 12374 18983 5450 31630 32102 30438 30332

With g++ (4.3.1), these are the results:

1481765933 1085377743 1270216262 1191391529
812669700553475508 445349752 1344887256 730417256

1039805031 1083326686 1331336834 716584787
2033177353934031309 1079589791 1155192414 1372256943

In neither case does repetition appear after producing RAND_MAX numbers.
For most things, I also test with Comeau, but it normally uses the back-
end compiler's implementation of rand(), so it would produce results
identical to the back-end compiler's.

--
Later,
Jerry.

The universe is a figment of its own imagination.
Jun 27 '08 #22

P: n/a
In article <g1**********@aioe.org>, bi*******@bilgekhanbilgekhan.net.tr
says...

[ ... ]
Ok, but it should be no problem to get the length of the period... :-)
For example:
Store, say 256 rand() call results in an array.
Then infinetely call rand() and check after how many calls
it repeats the same sequence stored in the array.... :-)
and then quit the loop.
A simpler way would be of course looking in the TM of the compiler/library...
(but OTOH who does RTFM ?... :-)
Consider the Mersenne Twister, which has a period of 2**19937-1.

You won't live long enough to see a repeat -- and neither will the sun.

In fact, playing with numbers like this quickly leads to cosmological
questions. For example, assume you could generate a random number with a
single quantum leap. Is there enough energy in the universe to generate
that many random numbers? I haven't figured it up, but my immediate
guess is no. For reference, consider that the number of atoms in the
universe is something like 2**200, so you need approximately 2**19737
quantum leaps per atom to do the job. Offhand, I don't recall how long a
quantum leap takes, but my immediate guess is that the second law of
thermodynamics wins first (i.e. the universe goes into heat death).

--
Later,
Jerry.

The universe is a figment of its own imagination.
Jun 27 '08 #23

P: n/a
On May 29, 6:30 am, Jerry Coffin <jcof...@taeus.comwrote:
In article <g1jpsm$h5...@aioe.org>, bilgek...@bilgekhanbilgekhan.net.tr
says...
[ ... ]
Because it is the same sequence of the RNG... :-)
A seed sequence of rand() always generates
RAND_MAX different random numbers.
False. It usually _will_, but there's no guarantee of it.
As far as the standard goes, no. All the standard says is that
"The rand function computes a sequence of pseudo-random integers
in the range 0 to RAND_MAX." It doesn't say anything about the
quality of this sequence, nor even define what it means by
"pseudo-random integers". These issues are left to quality of
implementation considerations.

Presumably, something like:

#define RAND_MAX 60000
inline void srand( unsigned ) {}
inline int rand() { return 1 ; }

would be conforming, although it's really stretching the
definition of "pseudo-random integers", and it would certainly
not be considered to have acceptable quality, from a QoI point
of view. The C standard contains an example implementation,
which is however known to be "bad".

In general, if some particular "quality" of the random numbers
is important, you won't use std::rand(), but rather a known
generator with known characteristics. (The next version of the
C++ standard will contain a number of these.)
So within a sequence it cannot generate the same number
twice.
Even more thoroughly false. I've cut out a bunch more
statements, but they all reflect the same misconception.
You're assuming that RAND_MAX reflects not only the range, but also the
period of the PRNG. While the standard's definition is loose enough to
_allow_ that, it's most assuredly not required. I'd add that, IMO, such
an implementation is _far_ from ideal.
From a practical viewpoint, having the range and the period of
the generator equal appears to be fairly unusual.
Let's say that if the range is something like 32767, it would be
a very, very poor generator which didn't have a longer period.
A 32 bit linear congruent generator like that described in
"Random Number Generators: Good Ones Are Hard to Find" (Park and
Miller, CACM, Oct. 1988) will have both RAND_MAX and the period
equal to 2147483647 (or something similar).
For example, consider the
following code:
#include <stdlib.h>
#include <iostream>
int main() {
srand(1);

int i;

for (i=0; i<9; i++)
std::cout << rand() << "\t";
std::cout << "\n";

for (; i<RAND_MAX; i++)
rand();

for (i=0; i<9; i++)
std::cout << rand() << "\t";
std::cout << "\n";
return 0;
}
According to your statements, the two lines should be
identical (with a possible offset).
If the period of the generator is RAND_MAX, the middle loop
should execute RAND_MAX-9, not RAND_MAX, for the two lines to
be the same.

Not that that actually changes the concrete results. As you
say, the period is almost always longer than RAND_MAX. (On a
lot of systems, RAND_MAX is only 32767, presumably for some
obscure historical reason.)

--
James Kanze (GABI Software) email:ja*********@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

Jun 27 '08 #24

P: n/a
James Kanze schrieb:
>For example, consider the
following code:
>#include <stdlib.h>
#include <iostream>
>int main() {
srand(1);

int i;

for (i=0; i<9; i++)
std::cout << rand() << "\t";
std::cout << "\n";

for (; i<RAND_MAX; i++)
rand();

for (i=0; i<9; i++)
std::cout << rand() << "\t";
std::cout << "\n";
return 0;
}
>According to your statements, the two lines should be
identical (with a possible offset).

If the period of the generator is RAND_MAX, the middle loop
should execute RAND_MAX-9, not RAND_MAX, for the two lines to
be the same.
It will. The middle loop doesn't reset i to 0.
Not that that actually changes the concrete results. As you
say, the period is almost always longer than RAND_MAX. (On a
lot of systems, RAND_MAX is only 32767, presumably for some
obscure historical reason.)
--
Thomas
Jun 27 '08 #25

P: n/a
In article <d6b1612b-98bf-46bd-b70b-
02**********@r66g2000hsg.googlegroups.com>, ja*********@gmail.com
says...

[ ... ]
For example, consider the
following code:
#include <stdlib.h>
#include <iostream>
int main() {
srand(1);

int i;

for (i=0; i<9; i++)
std::cout << rand() << "\t";
std::cout << "\n";

for (; i<RAND_MAX; i++)
rand();

for (i=0; i<9; i++)
std::cout << rand() << "\t";
std::cout << "\n";
return 0;
}
According to your statements, the two lines should be
identical (with a possible offset).

If the period of the generator is RAND_MAX, the middle loop
should execute RAND_MAX-9, not RAND_MAX, for the two lines to
be the same.
Look at it again. The initialization part of the second loop is empty.

--
Later,
Jerry.

The universe is a figment of its own imagination.
Jun 27 '08 #26

P: n/a
On May 28, 11:30*pm, Jerry Coffin <jcof...@taeus.comwrote:
In article <g1jpsm$h5...@aioe.org>, bilgek...@bilgekhanbilgekhan.net.tr
says...

[ ... ]
Because it is the same sequence of the RNG... *:-)
A seed sequence of rand() always generates
RAND_MAX different random numbers.

False. It usually _will_, but there's no guarantee of it.
So within a sequence it cannot generate the same number twice.

Even more thoroughly false. I've cut out a bunch more statements, but
they all reflect the same misconception.

You're assuming that RAND_MAX reflects not only the range, but also the
period of the PRNG. While the standard's definition is loose enough to
_allow_ that, it's most assuredly not required. I'd add that, IMO, such
an implementation is _far_ from ideal.

FWIW, the LCG PRNG suggested by the standard (see below), and used by
many implementations, has a period of 2**32.

Suggested by C standard:

#define RAND_MAX 32767
unsigned long next =1;

int rand(void)
{
next = next * 1103515245 +12345; /* note implicit mod 2**32 */
return (unsigned int)(next / 65536) % 32768;
}
It's not a great generator, but it's not horrible either.

From a practical viewpoint, having the range and the period of the
generator equal appears to be fairly unusual. For example, consider the
following code:

Indeed, that would normally be horrible, unless the range was very
large, and even then it fundamentally adds an increasing bias as you
get further into the sequence.
Jun 27 '08 #27

This discussion thread is closed

Replies have been disabled for this discussion.