Re: [OctDev] random numbers for distributed computations

[Michael C. <mic...@ua...>]

On Monday 11 April 2005 13:14, David Bateman wrote:
> 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? M.
>
> The octave-forge generators are based on the Mersenne Twister, and it
> doesn't have a seed but rather a state of 32 values. So the unique
> starting points are defined from this state vector.. The period of the
> Mersenne Twister is 2^19937-1, so I wouldn''t worry about it repeating
> itself in yours or my lifetimes.
>
> Regards
> David

Well, the issue of how the starting values are chosen is potentially 
important. See this paper for reference:
http://w3.tmit.bme.hu/~vidacs/education/simulation_techniques/sim_papers/01_01_hechenleitner-ips2003.pdf

However, on page 8, there is a test of the Mersenne Twister, and the results 
indicate that using a random starting points on each node will very likely 
give independent streams on a cluster, due to the astronomical period of the 
MT. But with a shorter period, there would be trouble. But at any rate, I 
convinced that this is a non-issue, at least on my platform of choice. 
Thanks, Michael