Re: [Boost-users] Random permutations using boost::random_number_generator and std::random_shuffle.

Subject: Re: [Boost-users] Random permutations using boost::random_number_generator and std::random_shuffle.
From: Matthew Gwynne (mathew.gwynne_at_[hidden])
Date: 2011-01-23 05:00:31

Hi,

On Fri, Jan 21, 2011 at 10:16 PM, Steven Watanabe <watanabesj_at_[hidden]> wrote:
> AMDG
>
> On 1/21/2011 1:57 PM, Matthew Gwynne wrote:
>>
>> The problem we now have is that we don't know how the result of
>> mt19937 is being cast down into the number range we are asking for. As
>> far as I am aware, MT19937 only defines how to get a 32 bit integer,
>> not how to then scale that to say the range 1..10. Is it specified
>> clearly how boost::random_number_generator or
>> boost::uniform_distribution does this?
>>
>
> boost::random_number_generator is implemented using
> boost::uniform_int and no the algorithm isn't specified.
> It's considered an implementation detail.  If you
> really want to know the details, the source is in
> boost/random/uniform_int.hpp.  I don't expect the
> implementation to change again, but no guarantees.

Hmm... this seems odd. Surely the point behind having seeds and things
like mt19937 precisely specified is that they should be completely
reproducible and predictable. If there's no specification, then how
can one use such things reliably. I guess we'll either have to use it
and add lots of tests to ensure if it changes in future, that we can
implement the old version of the code. Either that or we simply
implement it ourselves.

Sorry if it seems like I'm averse to looking into the code. It's not
that, it's simply as you suggest, the code can change and I'm trying
to find out the interface that is being provided which then shouldn't
(or is less likely to change).

Thanks for the clarification!

>
>>>
>>>> However, we have two questions (open problems):
>>>>
>>>> 1) How does boost::variate_generator interact with mt19937, and the
>>>> distribution? Is this documented somewhere?
>>>>
>>>> In the attached code, it seems we can construct
>>>> boost::uniform_distribution with any maximum value, and still the
>>>> number generator returns values outside of that range? Is this really
>>>> right?
>>>>
>>>
>>> Yes.  You don't need to use uniform_int with
>>> random_number_generator.  You can plug mt19937
>>> directly into random_number_generator.
>>
>> Thanks! Is the behaviour exactly the same?
>
> It isn't going to be exactly the same. If you use
> mt19937 directly, then random_number_generator
> will transform the output of the generator to the
> desired range.  If you use uniform_int, the
> generator's output will first be transformed
> to the range that you specified for uniform_int,
> then again by random_number_generator.  The
> result will still have the correct distribution,
> but the exact values may be different.

Ah, thanks! We will have to pick one and stick with it as, for us, the
two aren't equivalent as they don't exhibit the same behaviour and so
if we swap from one to the other at some point, we lose
reproducibility of our experiments.

Thanks for the explanation!

>
>> It seems so, but the
>> documentation seems to suggest using boost::uniform_distribution.
>>
>
> Where in the documentation?

Apologies, it seems I remembered incorrectly, it was using
boost::uniform_distribution with boost::variate_generator :

http://www.boost.org/doc/libs/1_45_0/doc/html/boost_random.html

>
> In Christ,
> Steven Watanabe
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>

Thanks again!!

Matthew Gwynne
http://cs.swan.ac.uk/~csmg/