Re: [boost] [random] seeding with arbitrary integers

Subject: Re: [boost] [random] seeding with arbitrary integers
From: Robert Ramey (ramey_at_[hidden])
Date: 2009-10-20 19:56:27

This sounds like the functions in question will silently alter the seed so 
that it "just works".

If this is what it is, I should say I don't like it.  This means that if I 
do
something invalid (a bad seed), I never find out about it.  I would
much prefer that if I pass an invalid parameter, I get either
an return error code or an exception.  Of course this is
a pain as I have to go to the manual and figure out what I'm
doing wrong.  But it's much better than trying discover at
some later time that things weren't doing what I thought
they were.

It's also a pain that this means that the documentation has
to be updated to explain why some seeds are not valid.
But, that should already be in there.

Robert Ramey

Steven Watanabe wrote:
>> AMDG
>>
>> 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
>>
>>
>
>
>
>> Index: boost/random/linear_feedback_shift.hpp
>> ===================================================================
>> --- boost/random/linear_feedback_shift.hpp (revision 57008)
>> +++ boost/random/linear_feedback_shift.hpp (working copy)
>> @@ -77,7 +77,12 @@
>>     seed(first, last);
>>   }
>>
>> -  void seed(UIntType s0 = 341) { assert(s0 >= (1 << (w-k))); value
>> = s0; } +  void seed(UIntType s0 = 341) {
>> +      if(s0 < (1 << (w-k))) {
>> +          s0 += 1 << (w-k);
>> +      }
>> +      value = s0;
>> +  }
>>   template<class It> void seed(It& first, It last)
>>   {
>>     if(first == last)
>> Index: boost/random/linear_congruential.hpp
>> ===================================================================
>> --- boost/random/linear_congruential.hpp (revision 57008)
>> +++ boost/random/linear_congruential.hpp (working copy)
>> @@ -54,12 +54,9 @@
>>   // BOOST_STATIC_ASSERT(m == 0 || c < m);
>>
>>   explicit linear_congruential(IntType x0 = 1)
>> -    : _modulus(modulus), _x(_modulus ? (x0 % _modulus) : x0)
>> +    : _modulus(modulus)
>>   {
>> -    assert(c || x0); /* if c == 0 and x(0) == 0 then x(n) = 0 for
>> all n */
>> -    // overflow check
>> -    // disabled because it gives spurious "divide by zero" gcc
>> warnings
>> -    // assert(m == 0 || (a*(m-1)+c) % m == (c < a ? c-a+m : c-a));
>> +    seed(x0);
>>
>>     // MSVC fails BOOST_STATIC_ASSERT with std::numeric_limits at
>> class scope #ifndef BOOST_NO_LIMITS_COMPILE_TIME_CONSTANTS
>> @@ -77,8 +74,18 @@
>>   // compiler-generated copy constructor and assignment operator are
>>   fine void seed(IntType x0 = 1)
>>   {
>> -    assert(c || x0);
>> -    _x = (_modulus ? (x0 % _modulus) : x0);
>> +    // wrap _x if it doesn't fit in the destination type
>> +    if(_modulus == 0) {
>> +      _x = x0;
>> +    } else {
>> +      _x = x0 % (modulus - min());
>> +    }
>> +    // adjust to the correct range
>> +    if(_x < min()) {
>> +      _x += (modulus - min());
>> +    }
>> +    assert(_x >= min());
>> +    assert(_x <= max());
>>   }
>>
>>   template<class It>
>> @@ -86,8 +93,7 @@
>>   {
>>     if(first == last)
>>       throw std::invalid_argument("linear_congruential::seed");
>> -    IntType value = *first++;
>> -    _x = (_modulus ? (value % _modulus) : value);
>> +    seed(*first++);
>>   }
>>
>>   result_type min BOOST_PREVENT_MACRO_SUBSTITUTION () const { return
>> c == 0 ? 1 : 0; } @@ -261,7 +267,7 @@
>>     if(sizeof(T) < sizeof(uint64_t)) {
>>       return (static_cast<uint64_t>(x) << 16) | 0x330e;
>>     } else {
>> -        return(static_cast<uint64_t>(x));
>> +      return(static_cast<uint64_t>(x));
>>     }
>>   }
>>   static uint64_t cnv(float x) { return(static_cast<uint64_t>(x)); }
>> Index: libs/random/instantiate.cpp
>> ===================================================================
>> --- libs/random/instantiate.cpp (revision 57008)
>> +++ libs/random/instantiate.cpp (working copy)
>> @@ -133,53 +133,63 @@
>>                    boost::gamma_distribution<RealType>(1));
>> }
>>
>> -template<class URNG, class T>
>> -void test_seed(URNG & urng, const T & t) {
>> -    URNG urng2(t);
>> -    BOOST_CHECK(urng == urng2);
>> -    urng2.seed(t);
>> -    BOOST_CHECK(urng == urng2);
>> +template<class URNG, class T, class Converted>
>> +void test_seed_conversion(URNG & urng, const T & t, const Converted
>> &) { +    Converted c = static_cast<Converted>(t);
>> +    if(static_cast<T>(c) == t) {
>> +        URNG urng2(c);
>> +        BOOST_CHECK_MESSAGE(urng == urng2, std::string("Testing
>> seed constructor: ") + typeid(Converted).name()); +
>> urng2.seed(c); +        BOOST_CHECK(urng == urng2);
>> +    }
>> }
>>
>> // rand48 uses non-standard seeding
>> -template<class T>
>> -void test_seed(boost::rand48 & urng, const T & t) {
>> +template<class T, class Converted>
>> +void test_seed_conversion(boost::rand48 & urng, const T & t, const
>>     Converted &) { boost::rand48 urng2(t);
>>     urng2.seed(t);
>> }
>>
>> template<class URNG, class ResultType>
>> -void instantiate_seed(const URNG &, const ResultType &) {
>> +void test_seed(const URNG &, const ResultType & v) {
>> +    typename URNG::result_type value = static_cast<typename
>> URNG::result_type>(v); +
>> +    URNG urng(value);
>> +
>> +    // integral types
>> +    test_seed_conversion(urng, value, static_cast<char>(0));
>> +    test_seed_conversion(urng, value, static_cast<signed char>(0));
>> +    test_seed_conversion(urng, value, static_cast<unsigned
>> char>(0)); +    test_seed_conversion(urng, value,
>> static_cast<short>(0)); +    test_seed_conversion(urng, value,
>> static_cast<unsigned short>(0)); +    test_seed_conversion(urng,
>> value, static_cast<int>(0)); +    test_seed_conversion(urng, value,
>> static_cast<unsigned int>(0)); +    test_seed_conversion(urng,
>> value, static_cast<long>(0)); +    test_seed_conversion(urng, value,
>> static_cast<unsigned long>(0)); +#if !defined(BOOST_NO_INT64_T)
>> +    test_seed_conversion(urng, value,
>> static_cast<boost::int64_t>(0)); +    test_seed_conversion(urng,
>> value, static_cast<boost::uint64_t>(0)); +#endif
>> +
>> +    // floating point types
>> +    test_seed_conversion(urng, value, static_cast<float>(0));
>> +    test_seed_conversion(urng, value, static_cast<double>(0));
>> +    test_seed_conversion(urng, value, static_cast<long double>(0));
>> +}
>> +
>> +template<class URNG, class ResultType>
>> +void instantiate_seed(const URNG & urng, const ResultType &) {
>>     {
>>         URNG urng;
>>         URNG urng2;
>>         urng2.seed();
>>         BOOST_CHECK(urng == urng2);
>>     }
>> -    {
>> -        int value = 127;
>> -        URNG urng(value);
>> -
>> -        // integral types
>> -        test_seed(urng, static_cast<char>(value));
>> -        test_seed(urng, static_cast<signed char>(value));
>> -        test_seed(urng, static_cast<unsigned char>(value));
>> -        test_seed(urng, static_cast<short>(value));
>> -        test_seed(urng, static_cast<unsigned short>(value));
>> -        test_seed(urng, static_cast<int>(value));
>> -        test_seed(urng, static_cast<unsigned int>(value));
>> -        test_seed(urng, static_cast<long>(value));
>> -        test_seed(urng, static_cast<unsigned long>(value));
>> -#if !defined(BOOST_NO_INT64_T)
>> -        test_seed(urng, static_cast<boost::int64_t>(value));
>> -        test_seed(urng, static_cast<boost::uint64_t>(value));
>> -#endif
>> -
>> -        // floating point types
>> -        test_seed(urng, static_cast<float>(value));
>> -        test_seed(urng, static_cast<double>(value));
>> -        test_seed(urng, static_cast<long double>(value));
>> -    }
>> +    test_seed(urng, 0);
>> +    test_seed(urng, 127);
>> +    test_seed(urng, 539157235);
>> +    test_seed(urng, ~0u);
>> }
>>
>> template<class URNG, class ResultType>
>>
>
>
>
>> _______________________________________________
>> Unsubscribe & other changes:
>> http://lists.boost.org/mailman/listinfo.cgi/boost