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@forked.de>