Subject: Re: [boost] [random] seeding with arbitrary integers
From: Topher Cooper (topher_at_[hidden])
Date: 2009-10-21 17:20:02
Does the documentation say that two different seeds will produce
different sequences? If so, is there a stated guarantee when they will
diverge? In general, unless you understand the guts of the algorithm --
including how a seed is turned into an initial state -- or have been
given a guarantee by someone who presumably does, you should not assume
that different seeds will definitely produce different results. You
should be able, however, to assume that two rngs seeded with two
arbitrarily chosen seeds have a very low probability of remaining in
sync for very long. One mark of good quality for an implementation of
an RNG is that the arbitrariness of the choice of those seeds doesn't
have to be very high: seeds that are small, or negative if interpreted
as signed, or powers of two or whatever don't cause problems.
When writing RNGs I generally do something like xor the seed with an
arbitrary mask so that rather unarbitrary seeds become much more
arbitrary ones. That is a better solution than adding the minimum value
to the seed, since it will not map small values into other slightly
less-small values. That circumstance makes it much more likely that two
carelessly chosen seeds will map to the same place.
Addressing this issue, by the way, was most of my "contribution" to the
initially-published/benchmark implementation of MT19937, that resulted
in my name plastered all over the Net. A lot of visibility for an hour
or so of code cleanup. MT19937 passes very stringent randomness
tests, both theoretical and pragmatic, under the assumption that the
starting point is chosen randomly. There are regions of the state
space, though, where its behavior is very far from random. The state
space is so large, however, the probability of a random starting point
hitting such a region is vanishingly small and can be ignored -- IF the
seed is chosen randomly. In particular if the 19937 bits in the state
vector have very few 1 bits then the next generation of the state vector
will also have very few 1 bits (though generally more than before).
Certain casual choices for the 32 bit seed in the initially circulated
version of the code could result in just this situation. I suggested
some changes (frankly, its been a while and I don't remember exactly
what) so that one would have to work very hard to figure out a 32 bit
seed value that would result in one ending up in this Random Number
Steven Watanabe wrote:
> Currently, some PRNGs cannot be seeded with certain values.
> For example, the seed for linear_congruential cannot be
> a multiple of the modulus if the offset is zero. lagged_fibonacci
> also cannot be seeded with 0, because it uses minstd_rand0.
> Since linear_congruential already tries to wrap the seed to fit
> in the range, I'd like to change it so that any seed works.
> The other generator that needs to be changed is linear_feedback_shift.
> linear_feedback_shift cannot be seeded with a small integer.
> What I've done is to add the minimum value to the seed, if
> the seed is too small. I'm not sure that this is a good solution,
> since this means that there are a few (and only a few) seeds
> that result in identical generators. Thoughts? Would it be
> better to wrap the values to make them fit in range instead?
> At least this would be consistent with linear_congruential.
> I've attached a patch with these changes and test cases.
> See also: http://svn.boost.org/trac/boost/ticket/3516
> which prompted this investigation.
> In Christ,
> Steven Watanabe
> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk