/* boost random/detail/qrng_base.hpp header file
|
*
|
* Copyright Justinas Vygintas Daugmaudis 2010-2018
|
* Distributed under the Boost Software License, Version 1.0. (See
|
* accompanying file LICENSE_1_0.txt or copy at
|
* http://www.boost.org/LICENSE_1_0.txt)
|
*/
|
|
#ifndef BOOST_RANDOM_DETAIL_QRNG_BASE_HPP
|
#define BOOST_RANDOM_DETAIL_QRNG_BASE_HPP
|
|
#include <stdexcept>
|
#include <vector>
|
#include <limits>
|
|
#include <istream>
|
#include <ostream>
|
#include <sstream>
|
|
#include <boost/cstdint.hpp>
|
#include <boost/random/detail/operators.hpp>
|
|
#include <boost/throw_exception.hpp>
|
|
#include <boost/type_traits/integral_constant.hpp>
|
|
#include <boost/random/detail/disable_warnings.hpp>
|
|
//!\file
|
//!Describes the quasi-random number generator base class template.
|
|
namespace boost {
|
namespace random {
|
|
namespace qrng_detail {
|
|
// If the seed is a signed integer type, then we need to
|
// check that the value is positive:
|
template <typename Integer>
|
inline void check_seed_sign(const Integer& v, const boost::true_type)
|
{
|
if (v < 0)
|
{
|
boost::throw_exception( std::range_error("seed must be a positive integer") );
|
}
|
}
|
template <typename Integer>
|
inline void check_seed_sign(const Integer&, const boost::false_type) {}
|
|
template <typename Integer>
|
inline void check_seed_sign(const Integer& v)
|
{
|
check_seed_sign(v, integral_constant<bool, std::numeric_limits<Integer>::is_signed>());
|
}
|
|
|
template<typename DerivedT, typename LatticeT, typename SizeT>
|
class qrng_base
|
{
|
public:
|
typedef SizeT size_type;
|
typedef typename LatticeT::value_type result_type;
|
|
explicit qrng_base(std::size_t dimension)
|
// Guard against invalid dimensions before creating the lattice
|
: lattice(prevent_zero_dimension(dimension))
|
, quasi_state(dimension)
|
{
|
derived().seed();
|
}
|
|
// default copy c-tor is fine
|
|
// default assignment operator is fine
|
|
//!Returns: The dimension of of the quasi-random domain.
|
//!
|
//!Throws: nothing.
|
std::size_t dimension() const { return quasi_state.size(); }
|
|
//!Returns: Returns a successive element of an s-dimensional
|
//!(s = X::dimension()) vector at each invocation. When all elements are
|
//!exhausted, X::operator() begins anew with the starting element of a
|
//!subsequent s-dimensional vector.
|
//!
|
//!Throws: range_error.
|
result_type operator()()
|
{
|
return curr_elem != dimension() ? load_cached(): next_state();
|
}
|
|
//!Fills a range with quasi-random values.
|
template<typename Iter> void generate(Iter first, Iter last)
|
{
|
for (; first != last; ++first)
|
*first = this->operator()();
|
}
|
|
//!Effects: Advances *this state as if z consecutive
|
//!X::operator() invocations were executed.
|
//!
|
//!Throws: range_error.
|
void discard(boost::uintmax_t z)
|
{
|
const std::size_t dimension_value = dimension();
|
|
// Compiler knows how to optimize subsequent x / y and x % y
|
// statements. In fact, gcc does this even at -O1, so don't
|
// be tempted to "optimize" % via subtraction and multiplication.
|
|
boost::uintmax_t vec_n = z / dimension_value;
|
std::size_t carry = curr_elem + (z % dimension_value);
|
|
vec_n += carry / dimension_value;
|
carry = carry % dimension_value;
|
|
// Avoid overdiscarding by branchlessly correcting the triple
|
// (D, S + 1, 0) to (D, S, D) (see equality operator)
|
const bool corr = (!carry) & static_cast<bool>(vec_n);
|
|
// Discards vec_n (with correction) consecutive s-dimensional vectors
|
discard_vector(vec_n - static_cast<boost::uintmax_t>(corr));
|
|
#ifdef BOOST_MSVC
|
#pragma warning(push)
|
// disable unary minus operator applied to an unsigned type,
|
// result still unsigned.
|
#pragma warning(disable:4146)
|
#endif
|
|
// Sets up the proper position of the element-to-read
|
// curr_elem = carry + corr*dimension_value
|
curr_elem = carry ^ (-static_cast<std::size_t>(corr) & dimension_value);
|
|
#ifdef BOOST_MSVC
|
#pragma warning(pop)
|
#endif
|
}
|
|
//!Writes the textual representation of the generator to a @c std::ostream.
|
BOOST_RANDOM_DETAIL_OSTREAM_OPERATOR(os, qrng_base, s)
|
{
|
os << s.dimension() << " " << s.seq_count << " " << s.curr_elem;
|
return os;
|
}
|
|
//!Reads the textual representation of the generator from a @c std::istream.
|
BOOST_RANDOM_DETAIL_ISTREAM_OPERATOR(is, qrng_base, s)
|
{
|
std::size_t dim;
|
size_type seed;
|
boost::uintmax_t z;
|
if (is >> dim >> std::ws >> seed >> std::ws >> z) // initialize iff success!
|
{
|
// Check seed sign before resizing the lattice and/or recomputing state
|
check_seed_sign(seed);
|
|
if (s.dimension() != prevent_zero_dimension(dim))
|
{
|
s.lattice.resize(dim);
|
s.quasi_state.resize(dim);
|
}
|
// Fast-forward to the correct state
|
s.derived().seed(seed);
|
if (z != 0) s.discard(z);
|
}
|
return is;
|
}
|
|
//!Returns true if the two generators will produce identical sequences of outputs.
|
BOOST_RANDOM_DETAIL_EQUALITY_OPERATOR(qrng_base, x, y)
|
{
|
const std::size_t dimension_value = x.dimension();
|
|
// Note that two generators with different seq_counts and curr_elems can
|
// produce the same sequence because the generator triple
|
// (D, S, D) is equivalent to (D, S + 1, 0), where D is dimension, S -- seq_count,
|
// and the last one is curr_elem.
|
|
return (dimension_value == y.dimension()) &&
|
// |x.seq_count - y.seq_count| <= 1
|
!((x.seq_count < y.seq_count ? y.seq_count - x.seq_count : x.seq_count - y.seq_count)
|
> static_cast<size_type>(1)) &&
|
// Potential overflows don't matter here, since we've already ascertained
|
// that sequence counts differ by no more than 1, so if they overflow, they
|
// can overflow together.
|
(x.seq_count + (x.curr_elem / dimension_value) == y.seq_count + (y.curr_elem / dimension_value)) &&
|
(x.curr_elem % dimension_value == y.curr_elem % dimension_value);
|
}
|
|
//!Returns true if the two generators will produce different sequences of outputs.
|
BOOST_RANDOM_DETAIL_INEQUALITY_OPERATOR(qrng_base)
|
|
protected:
|
typedef std::vector<result_type> state_type;
|
typedef typename state_type::iterator state_iterator;
|
|
// Getters
|
size_type curr_seq() const { return seq_count; }
|
|
state_iterator state_begin() { return quasi_state.begin(); }
|
state_iterator state_end() { return quasi_state.end(); }
|
|
// Setters
|
void reset_seq(size_type seq)
|
{
|
seq_count = seq;
|
curr_elem = 0u;
|
}
|
|
private:
|
DerivedT& derived() throw()
|
{
|
return *static_cast<DerivedT * const>(this);
|
}
|
|
// Load the result from the saved state.
|
result_type load_cached()
|
{
|
return quasi_state[curr_elem++];
|
}
|
|
result_type next_state()
|
{
|
size_type new_seq = seq_count;
|
if (BOOST_LIKELY(++new_seq > seq_count))
|
{
|
derived().compute_seq(new_seq);
|
reset_seq(new_seq);
|
return load_cached();
|
}
|
boost::throw_exception( std::range_error("qrng_base: next_state") );
|
}
|
|
// Discards z consecutive s-dimensional vectors,
|
// and preserves the position of the element-to-read
|
void discard_vector(boost::uintmax_t z)
|
{
|
const boost::uintmax_t max_z = std::numeric_limits<size_type>::max() - seq_count;
|
|
// Don't allow seq_count + z overflows here
|
if (max_z < z)
|
boost::throw_exception( std::range_error("qrng_base: discard_vector") );
|
|
std::size_t tmp = curr_elem;
|
derived().seed(static_cast<size_type>(seq_count + z));
|
curr_elem = tmp;
|
}
|
|
static std::size_t prevent_zero_dimension(std::size_t dimension)
|
{
|
if (dimension == 0)
|
boost::throw_exception( std::invalid_argument("qrng_base: zero dimension") );
|
return dimension;
|
}
|
|
// Member variables are so ordered with the intention
|
// that the typical memory access pattern would be
|
// incremental. Moreover, lattice is put before quasi_state
|
// because we want to construct lattice first. Lattices
|
// can do some kind of dimension sanity check (as in
|
// dimension_assert below), and if that fails then we don't
|
// need to do any more work.
|
private:
|
std::size_t curr_elem;
|
size_type seq_count;
|
protected:
|
LatticeT lattice;
|
private:
|
state_type quasi_state;
|
};
|
|
inline void dimension_assert(const char* generator, std::size_t dim, std::size_t maxdim)
|
{
|
if (!dim || dim > maxdim)
|
{
|
std::ostringstream os;
|
os << "The " << generator << " quasi-random number generator only supports dimensions in range [1; "
|
<< maxdim << "], but dimension " << dim << " was supplied.";
|
boost::throw_exception( std::invalid_argument(os.str()) );
|
}
|
}
|
|
} // namespace qrng_detail
|
|
} // namespace random
|
} // namespace boost
|
|
#include <boost/random/detail/enable_warnings.hpp>
|
|
#endif // BOOST_RANDOM_DETAIL_QRNG_BASE_HPP
|
