Re: random numbers on clusters

[David Bateman]

Michael Creel wrote:

> David Bateman wrote:
>  
>
> > If your platform as /dev/urandom, then the octave-forge random 
> > generators will use it to seed the generators, and you will end up with 
> > independent number streams. Even if you don't have /dev/urandom, then 
> > these generators use the LSB of the clock to seed with (ie. usec) and so 
> > you'll probably find yourself with independent streams in any case.
> >    
>
> Hi David and list,
>
> Looking into this, I found the definition
>
> "Least Significant Bit (LSB) The LSB is the right most bit in a binary number. 
> For Example 00000001, 1 is the LSB."
>
> > From rand.cc:
> "By default, the generator is initialized from /dev/urandom if it is\n\
> available,otherwise from cpu time, wall clock time and the current\n\
> fraction of a second.\n\"
>
> I'm guessing that LSB here means decimal rather than binary numbers, but if 
> that's true then when the clock is used to initialize, then there are only 10 
> possible starting points for the sequence of random numbers. (?) If this is 
> the case then correlated streams on different nodes would be quite likely 
> even if only a small number of nodes are used, and it would be a certaintly 
> on any cluster with more than 10 nodes. I guess that this might be relevant 
> on Windows machines.
>
> Hoping I'm confused, Michael
>
>  

The relevant piece of code is

/* Look for entropy in /dev/urandom */
FILE* urandom =fopen("/dev/urandom", "rb");
if (urandom) {
while (n<MT_N) {
unsigned char word[4];
if (fread(word, 4, 1, urandom) != 1) break;
entropy[n++] = word[0]+(word[1]<<8)+(word[2]<<16)+(word[3]<<24);
}
fclose(urandom);
}

/* If there isn't enough entropy, gather some from various sources */
if (n < MT_N) entropy[n++] = time(NULL); /* Current time in seconds */
if (n < MT_N) entropy[n++] = clock(); /* CPU time used (usec) */
#ifdef HAVE_GETTIMEOFDAY
if (n < MT_N) {
struct timeval tv;
if (gettimeofday(&tv, NULL) != -1) {
entropy[n++] = tv.tv_usec; /* Fractional part of current time */
}
}
#endif

I'd thought the code only took the usec part of the time and cpu time 
for the entropy so that sequences that started near each other didn't 
have too many identical values in them. The fact is from the above, the 
wall time in seconds is used, pluse the cpu time in microseconds. If 
gettimeofday exists the microsecond part of the wall time is also added 
to the pool of entropy.... In general this will give you 96 bits of 
entropy that will be sufficient in most cases to have unique sequences, 
even in the absence of /dev/urandom...

Regards
David



--
David Bateman                                address@hidden
Motorola Labs - Paris                        +33 1 69 35 48 04 (Ph) 
Parc Les Algorithmes, Commune de St Aubin    +33 1 69 35 77 01 (Fax) 
91193 Gif-Sur-Yvette FRANCE

The information contained in this communication has been classified as: 

[x] General Business Information 
[ ] Motorola Internal Use Only 
[ ] Motorola Confidential Proprietary



-------------------------------------------------------------
Octave is freely available under the terms of the GNU GPL.

Octave's home on the web:  http://www.octave.org
How to fund new projects:  http://www.octave.org/funding.html
Subscription information:  http://www.octave.org/archive.html
-------------------------------------------------------------