help-octave
[Top][All Lists]

## Re: [OctDev] random numbers for distributed computations

 From: Michael Creel Subject: Re: [OctDev] random numbers for distributed computations Date: Mon, 11 Apr 2005 15:04:20 +0200 User-agent: KMail/1.7.2

```On Monday 11 April 2005 14:29, Paul Kienzle wrote:
> On Apr 11, 2005, at 6:42 AM, Michael Creel wrote:
> > On Monday 11 April 2005 11:57, Francesco Potorti` wrote:
> >>> I have a question about this. If a RNG has a period of X, that means
> >>> that
> >>> there are X unique values that are generated, and then the sequence
> >>> repeats.
> >>
> >> No, it means that the sequence repeats after X values are produced.
> >> The
> >> period length says nothing about the space of values.  However, for
> >> good
> >> general purpose generators, the size of the space of values is much
> >> smaller than the period.
> >
> > OK, you're saying that a generator with period 5 could produce values
> > like
> > 1 2 2 1 2 *** 1 2 2 1 2 *** 1 2 2 1 2
> > so the set of unique values is smaller than the period, correct?
> >
> > This may be, but for the moment my main question is whether the set of
> > unique
> > values that is generated depends upon the initial seed, or whether
> > it's just
> > the starting point in the sequence that depends on the initial seed.
> > Could
> > the unique values be 3 and 4, say, or will they always be 1 and 2?
>
> You are correct that the generator is entirely deterministic and the
> numbers
> will occur in the same order.  As David says elsewhere, however, if the
> sequence is very long and you start each processor at a different part
> of
> the sequence then you should be okay (e.g., by including processor # in
> the
> seed value).

If I understood David correctly, the octave-forge MT will get its initial
parameter using /dev/urandom, so this would not be necessary. If each machine
has a different parameter then the sequences will be different already,
regardless of the point in the sequence you start drawing from.

>
> A better approach is to use independent sequences on each processor,
> which
> you can do by choosing different constants in your random number
> generator.
> There is some concern that any RNG which is simple enough that you can
> do
> this will not have good statistical properties.
>
> You could try the parallel Mersenne Twister program (available from the
> main Mersenne Twister site):

I have looked at this. This seems to implement your suggestion to use
different parameters for the MT on each machine, letting the user specify
them. But since the octave-forge MT gets its initial parameter
from /dev/urandom, then this is already done.

>From what I understand from the previous discussion, and having looked at the
rand.cc code in octave-forge, it seems to me that sequences will be
independent on different nodes. Basically, it seems to me that the dynamic
creator method (http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/DC/dc.html)
has been implemented, more or less, in octave-forge.

>
>      http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html
>
> or the SPRNG scalable parallel random number generator:
>
>      http://sprng.cs.fsu.edu/

This one I was aware of. Its existence is what made me worry about the
potential problem of correlated streams in Octave. But I'm pretty much
convinced it's not a problem to worry about, at least on Linux.

>
> I haven't tried either of these.
>
> Hope that helps,
>
>       - Paul

Thanks, Michael

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

```