On 2010-06-10 14:20:05 -1000, Thomas J. Gritzan said:
Am 10.06.2010 07:37, schrieb orz:
On Jun 9, 1:37 pm, "Thomas J. Gritzan" <phygon_antis...@gmx.de> wrote:
Am 09.06.2010 17:52, schrieb orz:
Oh, on the subject or RNGs in Boost, their MT19937 implementation
looks rather odd. It basically includes two copies of the RNG state.
It looks like a clever optimization, but I don't see anything that it
actually optimizes.
From the source file:
// The goal is to always have x(i-n) ... x(i-1) available for
// operator== and save/restore.
(with i = <next word to output> and n = <# of words in state>)
You could store x(i)...x(i+n-1) instead, but you'ld had to precalculate
them each time you do a operator==.
(f'up to c.l.c++)
--
Thomas
It is true that that makes efficient full equality checks a bit
easier. But...
1. Equality check is not a common operation on MT.
Agreed. And it wouldn't be done in a performance critical loop, would it?
2. Even without the state double, full equality checks on MT instances
are not inefficient.
Well... you would have to bring both instances to the same state, so
that both either store x(i)...x(i+n-1) or x(i-n)...x(i-1). If you don't
want to change the original objects (they are const in the op==), you
have to make a copy of both for the check.
3. You could do mostly the same thing for equality checks with just a
single extra integer instead of 624 extras.
How? Comparing the original seeds and number of calls?
4. The naive approach to MT equality checks mostly works okay anyway.
Not perfectly, but I think the only ways to trip it up require either
running an instance of MT through an entire period (functionally
impossible to do without a skip-ahead type method, which is not
provided), or comparing two instances of MT originally seeded with
different seeds but then moved to the exact same position (on average
requires going through half of a full cycle, though it is possible to
do so with slightly less by way of bad luck, or a lot less if you pick
your seeds with great care).
A simple save/restore might invalidate the naive approach, depending on
how you do it. I think an equality check should be robust, if it is
provided. So it must normalize the internal state before comparing.
5. The Boost random docs list MT as taking up the normal amount of
memory, not the doubled amount of memory.
Interestingly, the TR1 implementation of Dinkumware (Visual Studio 2010)
also uses the double amount of memory.
For reasons that have nothing to do with equality tests. It's for speed.
Roundhouse Consulting, Ltd. (www.versatilecoding.com) Author of "The