February 2009


Options: Use Proportional Font
Show Text Part by Default
Show All Mail Headers

Message: [<< First] [< Prev] [Next >] [Last >>]
Topic: [<< First] [< Prev] [Next >] [Last >>]
Author: [<< First] [< Prev] [Next >] [Last >>]

Print Reply
Sean Luke <[log in to unmask]>
Reply To:
Tue, 3 Feb 2009 19:43:33 -0500
text/plain (67 lines)
Pelle Evensen wrote:

> Randy Casstevens wrote:
>> Do some random seeds give better quality results for
>> MersenneTwisterFast?  I have heard that random seeds should be odd
>> numbers, large numbers, and/or prime numbers, but does it matter for
>> MersenneTwisterFast?
> In short, for any good quality PRNG (the MersenneTwister would be one) 
> the choice of seed does not matter at all as far as "quality" goes.

Actually, many very high-grade RNGs are known to have certain 
pathological seed cases.  The crucial issue is: do we know what those 
cases are?  If so, we're fine -- just avoid those seed choices.

Mersenne Twister is no exception: and it's considered among  best of the 
best!  MT's internal state is an array of about 600 32-bit integers. 
Its seeding pathology is to fill that array initially with lots of 
zeros.  It takes Mersenne Twister a while to work its way out of that 
state, during which time it tends to produce lots of relatively poorly 
random numbers.

This turned out to be a problem for early seeding algorithms common 
among the Mersenne Twister community.  The current standard seeding 
algorithm is to take a seed and hand it off to a simple but relatively 
random RNG (in this case, a particular linear congruential generator in 
one of Knuth's books), and pump that generator 600-ish times.  Each 
output of the generator gets put into a different slot in the Mersenne 
Twister array.  That gives you a nice random collection of numbers, and 
an acceptably small number of initial zeros.

FWIW, my MersenneTwisterFast code follows the current standards.

> The only thing to possibly worry about is if you start many different 
> simulations with nearby seeds. For some generators (depending on how the 
> seed is expanded to the internal state of the generator) this will be a 
> problem and for some others, it won't be. What the state of the Mersenne 
> Twister as implemented in MASON is, I don't know.

Generally MT doesn't have this problem, partly because as an algorithm 
it's pretty robust to that issue, and partly because the Knuth seeding 
procedure described above creates very different initial internal array 
states from very similar random numbers.  Overall, most high grade RNGs 
are robust against similar seeds.

> A better (or at least safer) approach than the Mersenne Twister would be 
> to have a generator that generates distinct streams. This article 
> discusses the desirability of distinct streams; 

Having a generator which is forkable is a nice feature.  But I would be 
very hesitant to rely on an algorithm that doesn't have fairly provable 
features: and the paper you cited is actually a technical report for a 
code library, not an algorithmic description.  My suggestion about 
ALGORITHMS.  I don't get a good feeling about the lack of formality in 
this paper.

Stream protocols etc. are often implementable directly on top of 
well-regarded generators.  MT would be particularly good for this given 
its famously gigantic period.  It might be worthwhile to investigate the 
current RNG literature for formal protocols.