February 2009


Options: Use Monospaced 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.