question on rand()

question on rand()

[Anna Sidera]

Hello,

I am using gcc on a unix machine. Can you tell me how many random numbers can be generated using

rand()

before the random numbers start repeating? I found that RAND_MAX is equal to 2147483647.

Thanks,
Anna

Re: question on rand()

[Andrew Haley]

On 08/06/2011 08:47 AM, Anna Sidera wrote:
> Hello,
> 
> I am using gcc on a unix machine. Can you tell me how many random numbers can be generated using
> 
> rand()
> 
> before the random numbers start repeating? I found that RAND_MAX is equal to 2147483647.

One would hope it has full period, i.e. it generates all RAND_MAX numbers,
but that depends on your system.

It's perhaps not a good idea to depend on the system's generator.  A decent
32-bit one is

unsigned int xor-generator()
{
   static unsigned int y=2463534242;
   y^=(y<<13); y^=(y>>17); return (y^=(y<<5));
}

Andrew.

http://www.jstatsoft.org/v08/i14/paper

Re: question on rand()

[Marc Glisse]

On Sat, 6 Aug 2011, Andrew Haley wrote:

> On 08/06/2011 08:47 AM, Anna Sidera wrote:
>> Hello,
>>
>> I am using gcc on a unix machine. Can you tell me how many random numbers can be generated using
>>
>> rand()
>>
>> before the random numbers start repeating?

man rand
If it's not there, complain to your unix vendor.
The period is required by posix to be larger or equal to 2^32.

> One would hope it has full period, i.e. it generates all RAND_MAX numbers,
> but that depends on your system.

One would even hope the period is larger, so the output of rand() is not a 
deterministic function of its last return value (random generators often 
keep a hidden state).

-- 
Marc Glisse

Re: question on rand()

[Anna Sidera]

The following program:

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

int main()
{

int i=0;
int j=rand();
while (rand()!=j) i++;
printf("%d\n",i);

return 0;
}



gives the following output:

-1406966551



From this, can I find out when the numbers start repeating? How can I find it? I cannot find the period using

man rand



Anna
----- Original Message -----
From: Marc Glisse <marc.glisse@inria.fr>
Date: Saturday, August 6, 2011 7:34 pm
Subject: Re: question on rand()

> On Sat, 6 Aug 2011, Andrew Haley wrote:
> 
> > On 08/06/2011 08:47 AM, Anna Sidera wrote:
> >> Hello,
> >>
> >> I am using gcc on a unix machine. Can you tell me how many 
> random numbers can be generated using
> >>
> >> rand()
> >>
> >> before the random numbers start repeating?
> 
> man rand
> If it's not there, complain to your unix vendor.
> The period is required by posix to be larger or equal to 2^32.
> 
> > One would hope it has full period, i.e. it generates all 
> RAND_MAX numbers,
> > but that depends on your system.
> 
> One would even hope the period is larger, so the output of rand() 
> is not a 
> deterministic function of its last return value (random generators 
> often 
> keep a hidden state).
> 
> -- 
> Marc Glisse
> 

Re: question on rand()

[Jeffrey Walton]

On Sat, Aug 6, 2011 at 12:53 PM, Anna Sidera <sidera.anna@ucy.ac.cy> wrote:
> The following program:
>
> [SNIP]
>
> From this, can I find out when the numbers start repeating? How can I find it? I cannot find the period using
>
This is a crypto question ;)

If you are attacking an LCG, see Joan Boyar's paper or constructing
alternate LCG from observations which creates the same output. If the
online poker sites have read Wagner's (et al) paper on fair deals, you
will probably be out of luck.

Finally, sci.math or sci.crypt might be a better forum.

Jeff

> ----- Original Message -----
> From: Marc Glisse <marc.glisse@inria.fr>
> Date: Saturday, August 6, 2011 7:34 pm
> Subject: Re: question on rand()
>
>> On Sat, 6 Aug 2011, Andrew Haley wrote:
>>
>> > On 08/06/2011 08:47 AM, Anna Sidera wrote:
>> >> Hello,
>> >>
>> >> I am using gcc on a unix machine. Can you tell me how many
>> random numbers can be generated using
>> >>
>> >> rand()
>> >>
>> >> before the random numbers start repeating?
>>
>> man rand
>> If it's not there, complain to your unix vendor.
>> The period is required by posix to be larger or equal to 2^32.
>>
>> > One would hope it has full period, i.e. it generates all
>> RAND_MAX numbers,
>> > but that depends on your system.
>>
>> One would even hope the period is larger, so the output of rand()
>> is not a
>> deterministic function of its last return value (random generators
>> often
>> keep a hidden state).
>>
>> --
>> Marc Glisse
>>
>

Re: question on rand()

[Ian Lance Taylor]

Anna Sidera <sidera.anna@ucy.ac.cy> writes:

>From this, can I find out when the numbers start repeating? How can I find it? I cannot find the period using
>
> man rand

This question really doesn't have anything to do with gcc.  gcc does not
provide a rand function.  The rand function will come from your C
library, and gcc does not include a C library.

If you are using GNU glibc, which is probably the case if you are using
a GNU/Linux system, then rand is not implemented as a linear
congruential generator, and the period is quite long.  See the source
code.

Ian

Re: question on rand()

[Anna Sidera]

The program I wrote uses 2*10^8 random numbers which are produced using rand. Is there a way to find if rand produces duplicates in my program? I found that RAND_MAX is equal to 2^31-1 in the machine I am using.

Anna

----- Original Message -----
From: Ian Lance Taylor <iant@google.com>
Date: Saturday, August 6, 2011 10:01 pm
Subject: Re: question on rand()

> Anna Sidera <sidera.anna@ucy.ac.cy> writes:
> 
> >>From this, can I find out when the numbers start repeating? How 
> can I find it? I cannot find the period using
> >
> > man rand
> 
> This question really doesn't have anything to do with gcc.  gcc 
> does not
> provide a rand function.  The rand function will come from your C
> library, and gcc does not include a C library.
> 
> If you are using GNU glibc, which is probably the case if you are 
> usinga GNU/Linux system, then rand is not implemented as a linear
> congruential generator, and the period is quite long.  See the source
> code.
> 
> Ian
> 

Re: question on rand()

[Ian Lance Taylor]

Anna Sidera <sidera.anna@ucy.ac.cy> writes:

> The program I wrote uses 2*10^8 random numbers which are produced using rand. Is there a way to find if rand produces duplicates in my program? I found that RAND_MAX is equal to 2^31-1 in the machine I am using.

This question doesn't have anything to do with gcc.  This is the wrong
mailing list.  Please take this discussion to some other list.  Thanks.

If duplicates are important, why not just collect the numbers and check?
It seems to me that a high quality random number generator would likely
produce a couple of duplicates in such a long sequence.  But I know
little about random number generation.

Ian

> ----- Original Message -----
> From: Ian Lance Taylor <iant@google.com>
> Date: Saturday, August 6, 2011 10:01 pm
> Subject: Re: question on rand()
>
>> Anna Sidera <sidera.anna@ucy.ac.cy> writes:
>> 
>> >>From this, can I find out when the numbers start repeating? How 
>> can I find it? I cannot find the period using
>> >
>> > man rand
>> 
>> This question really doesn't have anything to do with gcc.  gcc 
>> does not
>> provide a rand function.  The rand function will come from your C
>> library, and gcc does not include a C library.
>> 
>> If you are using GNU glibc, which is probably the case if you are 
>> usinga GNU/Linux system, then rand is not implemented as a linear
>> congruential generator, and the period is quite long.  See the source
>> code.
>> 
>> Ian
>> 

Re: question on rand()

[Dennis Clarke]

> On 08/06/2011 08:47 AM, Anna Sidera wrote:
>> Hello,
>>
>> I am using gcc on a unix machine. Can you tell me how many random
>> numbers can be generated using
>>
>> rand()
>>
>> before the random numbers start repeating? I found that RAND_MAX is
>> equal to 2147483647.
>
> One would hope it has full period, i.e. it generates all RAND_MAX numbers,
> but that depends on your system.
>
> It's perhaps not a good idea to depend on the system's generator.  A
> decent
> 32-bit one is
>
> unsigned int xor-generator()
> {
>    static unsigned int y=2463534242;
>    y^=(y<<13); y^=(y>>17); return (y^=(y<<5));
> }
>


If the system has /dev/random then it would be better to read bytes from
that. Provided it is crypto quality. ymmv

Dennis

Re: question on rand()

[Andrew Haley]

On 08/06/2011 01:19 PM, Dennis Clarke wrote:
> 
>> On 08/06/2011 08:47 AM, Anna Sidera wrote:
>>> Hello,
>>>
>>> I am using gcc on a unix machine. Can you tell me how many random
>>> numbers can be generated using
>>>
>>> rand()
>>>
>>> before the random numbers start repeating? I found that RAND_MAX is
>>> equal to 2147483647.
>>
>> One would hope it has full period, i.e. it generates all RAND_MAX numbers,
>> but that depends on your system.
>>
>> It's perhaps not a good idea to depend on the system's generator.  A
>> decent 32-bit one is
>>
>> unsigned int xor-generator()
>> {
>>    static unsigned int y=2463534242;
>>    y^=(y<<13); y^=(y>>17); return (y^=(y<<5));
>> }
> 
> If the system has /dev/random then it would be better to read bytes from
> that. Provided it is crypto quality. ymmv

/dev/urandom, please, unless you only want a few bytes: /dev/random
is unlikely to be able to provide much random data.  If you need
/dev/random you probably know that you need it, and why.

Andrew.

Re: question on rand()

[Dennis Clarke]

> Anna Sidera <sidera.anna@ucy.ac.cy> writes:
>
>>From this, can I find out when the numbers start repeating? How can I
>>> find it? I cannot find the period using
>>
>> man rand
>
> This question really doesn't have anything to do with gcc.  gcc does not
> provide a rand function.  The rand function will come from your C
> library, and gcc does not include a C library.
>
> If you are using GNU glibc, which is probably the case if you are using
> a GNU/Linux system, then rand is not implemented as a linear
> congruential generator, and the period is quite long.  See the source
> code.
>

At risk of being well and truely off topic, I suggest that prng folks look
at the "Mersenne twister" algorithm developed by Makoto Matsumoto and
Takuji Nishimura :

  http://en.wikipedia.org/wiki/Mersenne_twister

Works great.

I think that ends this topic.

-- 
--
+-------------------------+-----------------------------------+
| Dennis Clarke           | Solaris and Linux and Open Source |
| dclarke@blastwave.org   | are my passion. ( FREE == OPEN )  |
+-------------------------+-----------------------------------+