Sean Luke wrote:
> 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.
Using the definition from "Definition 1" of
http://www.iro.umontreal.ca/~lecuyer/myftp/papers/cacm90.pdf (P.
L'Ecuyer, ``Random Numbers for Simulation'', Communications of the ACM,
33 (1990), 85--98),
I distinguish between the *state*, S, and the *seed*, s_0. My point was
that if the API is well designed, s_0 is indeed in S but the set of
possible (reasonable, if you wish) s_0 is a strict subset of S. Well
designed in the sense that the implementer of the PRNG at hand most
likely can make sure that any s_0 is transformed into a unique initial
state for the generator where pathological behaviours are avoided.
> 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.
And this is exactly why one should distinguish between seed and state;
you may want to be able to access the state to make sure that you can
clone a stream or resume a previous simulation but one should not
manipulate it by direct means, if that makes sense.
The "best of the best" is as usual depending on what you want to use it
for. It does fail some randomness tests;
See page 29 of
http://www.iro.umontreal.ca/~lecuyer/myftp/papers/testu01.pdf
It is possibly also slightly slower (the measurements shown in the
TestU01 paper are from C-code) and has a shorter period than some other
generators tested on pages 28-29.
> 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.
So this is the seed expansion or seed -> state transformation which
(hopefully) makes sure that you can not set up the MT in any
particularly bad state.
>> 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 peculiarity about the MersenneTwisterFast class is that the
constructor taking a long and the setSeed(long) (I guess for some
compatibility with java.util.Random) ignores the topmost 32 bits. Since
there is nothing magical about the seed expansion, and Java handles 64
bit arithmetic just fine, why not use a 64-bit generator or two separate
32 bit generators to initialize the state (mt[...]) in an interleaved
fashion? It should still be trivial to guarantee that we won't get a bad
state.
Yet another peculiarity is that all conversions from int to the lower
precision types is made by shifting instead of bitmasking. Is this
faster for most CPU's? If there is an explicit conversion, the masking
will probably take place anyway. I don't know if the javac compiler or
JIT-compiler is clever enough to recognize that the msb:s are all zero.
For a linear congruential generator this makes sense but is there some
results (published or not) that supports the hypothesis that the msb:s
from MT19937 are any "worse" than the lsb:s?
>> 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;
>> http://www.iro.umontreal.ca/~lecuyer/myftp/papers/rstream.pdf
> 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 random numbers: BE VERY CAREFUL ABOUT DEVIATING FROM
> WELL-STUDIED ALGORITHMS. I don't get a good feeling about the lack of
> formality in this paper.
I should have pointed to this paper instead;
http://www.iro.umontreal.ca/~lecuyer/myftp/papers/streams00.pdf
<http://www.iro.umontreal.ca/%7Elecuyer/myftp/papers/streams00.pdf> P.
L'Ecuyer, R. Simard, E. J. Chen, and W. D. Kelton, ``An
Objected-Oriented Random-Number Package with Many Long Streams and
Substreams'', Operations Research, 50, 6 (2002), 1073--1075.
This provides an algorithmic description. I don't think anyone should
worry too much about the lack of formality in
http://www.iro.umontreal.ca/~lecuyer/myftp/papers/rstream.pdf. L'Ecuyer
may be the most prolific writer of journal papers on PRNG:s and PRNG
testing. A few of his papers are co-authored with Matsumoto of MT-fame.
Sorry for pointing to the wrong paper; it was mostly the reasoning and
motivation for independent streams I was after.
Sean Luke: Have you measured the performance effects of having the
MersenneTwisterFast implement some sensible interface? (Yeah, so
java.util.Random should *really* be an interface, not a class)?
If one is to do exact replication of some existing program written in a
different environment it may be much easier to replace the PRNG in MASON
than doing it in the original program. Being able to replace the
generator with a quasi-random generator or something easily observed as
deterministic would also simplify some testing and debugging.
> 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.
Yes, if any one is aware of fast methods of transforming an arbitrary
(but good) generator into one with independent streams, I'd very much
like to hear about it.
It can be done trivially but *not fast* by using any (reasonably strong)
symmetric block cipher like this;
Let $R$ be a simulation-quality PRNG outputting $n$-bit words.
Let $E_k(m)$ be encryption of $k$-bit message $m$ under the key $k$.
Note that $n \le k$ for this to work.
Now for each output of $R$, we run it through $E$ and since we do expect
all permutations to be equally likely, the streams would be independent,
of course under the assumption that the original generator has a period
shorter than $2^k$.
I will hopefully soon find the time to try this with reduced versions of
some common block ciphers. It may very well be that the function call
overhead is so large that can still be considered fast if one does batch
generation of numbers, in a way similar to what the MT19937
implementation does in MASON.
Even though the state space of MT19937 is huge, we don't have any
theoretical guarantees that two different seeds don't make us use two
sequences that are (partially) overlapping.
/Pelle
|
