About rand()

[Spiros Bousbouras]

The standard says that rand() should return a pseudo-random
number but what does pseudorandom mean ? If an implementation
of rand() always returned the same number would it be conforming ?
What if it always alternated between 2 values ?

On the practical side do you have any thoughts on what one
could realistically expect from the behaviour of rand() ? Could
for example one expect that eventually any value in the range
[0,RAND_MAX] will be returned ?

[Spoon]

Walter Roberson wrote:

Spiros Bousbouras wrote:

>The standard says that rand() should return a pseudo-random
number but what does pseudorandom mean ? If an implementation
of rand() always returned the same number would it be conforming ?
What if it always alternated between 2 values ?

It must produce a pseudo-random sequence in the range 0
to RAND_MAX, where RAND_MAX is at least 32767. If on a particular
implementation it can never produce RAND_MAX then RAND_MAX
for that implementation would be defined as the largest value that
it -could- produce, and if that value was not at least 32767 then
the implementation would be non-conforming.

One could similarily argue that if 0 cannot be produced that
the implementation is non-conforming; the argument is perhaps
a bit weaker.

The sequence
u{n+1} = M * u{n} MOD C
with M=16807 and C=2^31-1
is often used as a PRNG.

It does not produce 0. (Otherwise it would always return 0.)

glibc's rand() implementation does not produce 0.

#include <stdio.h>
#include <stdlib.h>
int main(void)
{
unsigned long i = 1;
for (i=1; i; ++i)
{
if (rand() == 0) puts("rand() == 0");
}
return 0;
}

$ /usr/bin/time ./a.out
161.65user 0.08system 2:56.68elapsed 91%CPU

If the implementation alternated between 0 and RAND_MAX then
it would be conforming.

>On the practical side do you have any thoughts on what one
could realistically expect from the behaviour of rand() ? Could
for example one expect that eventually any value in the range
[0,RAND_MAX] will be returned ?

I would not -expect- any self-respecting rand() to not be
able to produce one of the values in the range, eventually;
I would -expect- at worst the sample function given in the
standard. But it wouldn't shock me if some organization
that produced a C-like language used what they -thought-
was a good rand() but which turned out not to be able to produce
some set of values. [NB: the number of organizations that
produce C-like languages appears to far outnumber the ones that
produce conforming C.]

Regards.

[Spoon]

Spoon wrote:

glibc's rand() implementation does not produce 0.

#include <stdio.h>
#include <stdlib.h>
int main(void)
{
unsigned long i = 1;
for (i=1; i; ++i)
{
if (rand() == 0) puts("rand() == 0");
}
return 0;
}

$ /usr/bin/time ./a.out
161.65user 0.08system 2:56.68elapsed 91%CPU

Doh! This only means that glibc's rand() does not return 0 after 2^32
invocations. Not that it never returns 0.

[Spoon]

Spoon wrote:

Spoon wrote:

>glibc's rand() implementation does not produce 0.

#include <stdio.h>
#include <stdlib.h>
int main(void)
{
unsigned long i = 1;
for (i=1; i; ++i)
{
if (rand() == 0) puts("rand() == 0");
}
return 0;
}

$ /usr/bin/time ./a.out
161.65user 0.08system 2:56.68elapsed 91%CPU

Doh! This only means that glibc's rand() does not return 0 after 2^32
invocations. Not that it never returns 0.

#include <stdlib.h>
int main(void)
{
while (rand() != 0);
return 0;
}

$ /usr/bin/time ./a.out
181.70user 0.03system 3:05.70elapsed 97%CPU

I stand corrected.

What is true is that linear congruential generators with B=0 obviously
never output 0.

http://en.wikipedia.org/wiki/Linear_...tial_generator

[Malcolm McLean]

"Spiros Bousbouras" <sp****@gmail.c omwrote in message

The standard says that rand() should return a pseudo-random
number but what does pseudorandom mean ? If an implementation
of rand() always returned the same number would it be conforming ?
What if it always alternated between 2 values ?

Pseudorandom means that it passes or nearly passes a lot of tests for
randomness, but is in fact deterministic.
When you say "would a rand() that always returned the same number/
alternated between 2 values be conforming?" really you are asking a
meaningless question. It just depends on the precise English-language
sentence used in the standard. There are no requirements for RNGs other than
that they be RNGs.

>
On the practical side do you have any thoughts on what one
could realistically expect from the behaviour of rand() ? Could
for example one expect that eventually any value in the range
[0,RAND_MAX] will be returned ?

A decent implementation will do this, but you cannot rely on it. The numbers
will be very roughly uniformly distributed throughout the range, but the
lower bits are allowed to cycle.
Hence

x * rand()/(RAND_MAX + 1.0)

rather than

rand() % x;