Boost logo

Boost :

From: Tiago de Paula Peixoto (tiago_at_[hidden])
Date: 2005-01-25 21:52:26


On Tue, 2005-01-25 at 16:07 +0000, John Maddock wrote:
> >The Mersenne Twister RNG was updated by the original author in 2002,
> >because of a small problem in the seeding procedure, which was that the
> >most significant bit of the seed was not well reflected to the state
> >vector. Read
> >http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/MT2002/emt19937ar.html
> >for more details.
> >
> >The version implemented in Boost is the original 1998 one, which
> >contains the problem. The attached patch implements the new seeding
> >procedure, which uses something different than the linear congruential
> >RNG to initialize the state vector. I haven't identified the new
> >procedure to match any generator already implemented in Boost, so I just
> >wrote it there (please correct me if I'm wrong).
>
> The problem we have here is that the behavior of our mersenne twister is now
> part of the C++ Technical Report 1, we should really report this as a
> defect, and get it changed there if this is indeed a problem.

Regarding the severity of the problem, read the author's page above for
more details. What it amounts to, in a nutshell (as I understand it), is
that because the old seeding procedure doesn't reflect well the most
significant bit of the seed value to the state vector, two seed values
that are close to each other may generate series which are also close.
This undermines the overall (very good) quality of the generator. It is
a minor problem, because it doesn't happen for most pair of seeds, and
therefore shouldn't happen very often, but it's a problem nevertheless.

Also the version of the algorithm with the new seeding procedure is
considered the "standard" by the original authors, and may be what users
expect to find. And as a "bonus", the new procedure allows for seed
values of zero. The current implementation in boost aborts at runtime if
a zero seed is used.

Since I'm not a boost developer, I don't think there's anything else I
can do, besides posting the problem here with the fix. How difficult is
it to change this in the C++ Technical Report? Is there any chance of
this fix reaching CVS before then?

Should I add this to the sourceforge bug system, so it can be tracked?

Thanks.

-- 
Tiago de Paula Peixoto <tiago_at_[hidden]>



Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk