Spiros Bousbouras
Guest
Posts: n/a

 01-16-2007
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 ?

Peter Nilsson
Guest
Posts: n/a

 01-16-2007
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 ?
>
> 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 ?

It's entirely a QoI issue. Pragmatically, it is trivial to write a
rand()
that returns every value at some point, even if the distribution is
not perfect. [A few implementations I've seen copy the example
shown in K&R2.]

The FAQ has a number of comments on the issues of rand().

Anyone needing to use random numbers in a serious program will
likely roll their own routine from the plethora of PRNG's available on
the net. [E.g. http://www.stanford.edu/~blp/writings/clc/random.html.]

--
Peter

Spiros Bousbouras
Guest
Posts: n/a

 01-16-2007
Peter Nilsson 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 ?
> >
> > 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 ?

>
> It's entirely a QoI issue. Pragmatically, it is trivial to write a
> rand()
> that returns every value at some point, even if the distribution is
> not perfect. [A few implementations I've seen copy the example
> shown in K&R2.]

By "perfect" distribution do you mean uniform distribution ?

Walter Roberson
Guest
Posts: n/a

 01-16-2007
In article <(E-Mail Removed) .com>,
Spiros Bousbouras <(E-Mail Removed)> 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.

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.]

--
If you lie to the compiler, it will get its revenge. -- Henry Spencer

Spiros Bousbouras
Guest
Posts: n/a

 01-16-2007
Walter Roberson wrote:
> In article <(E-Mail Removed) .com>,
> Spiros Bousbouras <(E-Mail Removed)> 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.

The standard says "The rand function computes a
sequence of pseudo-random numbers in the range
of 0 to RAND_MAX." I don't see how it follows from
that that the largest value which can be produced
will by definition be RAND_MAX.

Richard Tobin
Guest
Posts: n/a

 01-16-2007
In article <(E-Mail Removed). com>,
Spiros Bousbouras <(E-Mail Removed)> wrote:

>The standard says "The rand function computes a
>sequence of pseudo-random numbers in the range
>of 0 to RAND_MAX." I don't see how it follows from
>that that the largest value which can be produced
>will by definition be RAND_MAX.

The standard is rather weak in its description of rand(). It makes
no mention of the distribution of random numbers, so an implementation
that returns 1 99.99999999% of the time could still be conforming.
Presumably this would be considered a quality of implementation issue,
and the same goes for an implementation that never produced RAND_MAX.

-- Richard

--
"Consideration shall be given to the need for as many as 32 characters
in some alphabets" - X3.4, 1963.

user923005
Guest
Posts: n/a

 01-16-2007
Spiros Bousbouras wrote:
> Walter Roberson wrote:
> > In article <(E-Mail Removed) .com>,
> > Spiros Bousbouras <(E-Mail Removed)> 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.

>
> The standard says "The rand function computes a
> sequence of pseudo-random numbers in the range
> of 0 to RAND_MAX." I don't see how it follows from
> that that the largest value which can be produced
> will by definition be RAND_MAX.

According to that definition the sequence:
1,1,1,1...
seems to fit because 1 is between 0 and RAND_MAX.

The rand() function cannot produce negative numbers (by definition)
The rand() function cannot produce numbers larger than RAND_MAX (by
definition).

Generally speaking, a halfway-decent rand() implementation will
eventually produce every number between and including 0 .. RAND_MAX.

However, there is not guarantee in the standard that rand() is halfway
decent (e.g. that it passes Marsaglia's tests).

If you want good pseudo-random numbers, then use the Mersenne Twister.

David T. Ashley
Guest
Posts: n/a

 01-17-2007
"Spiros Bousbouras" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed) oups.com...
> 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 ?
>

Pseudo-random means that the next value of the output is a function of some
internal state. Often, the state and the returned value are the same thing.
Pseudo-random means that the next value is algorithmically predictable, i.e.
it isn't truly random where one could not predict.

http://en.wikipedia.org/wiki/Pseudo-random

The most common approach to pseudo-random generators is to use prime moduli.

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

In fact, most people who implement their own random number generators are
pretty happy with the simple one at the link immediately above. I believe
as long as the requirement of coprimality between a couple of the parameters
is met, the generated sequence is guaranteed to hit every value in the
interval. I'm sure all the math is at the link above.

--
David T. Ashley ((E-Mail Removed))
http://gpl.e3ft.com (GPL Publications and Projects)

CBFalconer
Guest
Posts: n/a

 01-17-2007
"David T. Ashley" wrote:
>

.... snip ...
>
> In fact, most people who implement their own random number
> generators are pretty happy with the simple one at the link
> immediately above. I believe as long as the requirement of
> coprimality between a couple of the parameters is met, the
> generated sequence is guaranteed to hit every value in the
> interval. I'm sure all the math is at the link above.

Just read Knuth (TAOCP). He has a thorough treatment of linear
congruential generators, including some cookbook tables.

--
Chuck F (cbfalconer at maineline dot net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net>

David T. Ashley
Guest
Posts: n/a

 01-17-2007
"CBFalconer" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
> "David T. Ashley" wrote:
>>

> ... snip ...
>>
>> In fact, most people who implement their own random number
>> generators are pretty happy with the simple one at the link
>> immediately above. I believe as long as the requirement of
>> coprimality between a couple of the parameters is met, the
>> generated sequence is guaranteed to hit every value in the
>> interval. I'm sure all the math is at the link above.

>
> Just read Knuth (TAOCP). He has a thorough treatment of linear
> congruential generators, including some cookbook tables.

Thanks. I have those books on my shelves and actually didn't know that
random number generation was in it (I've used it most for extended-precision
arithmetic and searching and sorting).

There is a lot packed into those books.

--
David T. Ashley ((E-Mail Removed))
http://gpl.e3ft.com (GPL Publications and Projects)