1 /* boost random/detail/gray_coded_qrng.hpp header file 2 * 3 * Copyright Justinas Vygintas Daugmaudis 2010-2018 4 * Distributed under the Boost Software License, Version 1.0. (See 5 * accompanying file LICENSE_1_0.txt or copy at 6 * http://www.boost.org/LICENSE_1_0.txt) 7 */ 8 9 #ifndef BOOST_RANDOM_DETAIL_GRAY_CODED_QRNG_HPP 10 #define BOOST_RANDOM_DETAIL_GRAY_CODED_QRNG_HPP 11 12 #include <boost/random/detail/qrng_base.hpp> 13 14 #include <boost/multiprecision/integer.hpp> // lsb 15 16 #include <functional> // bit_xor 17 18 #include <boost/mpl/if.hpp> 19 20 #include <boost/integer/integer_mask.hpp> 21 22 //!\file 23 //!Describes the gray-coded quasi-random number generator base class template. 24 25 namespace boost { 26 namespace random { 27 28 namespace qrng_detail { 29 30 template<typename LatticeT> 31 class gray_coded_qrng 32 : public qrng_base< 33 gray_coded_qrng<LatticeT> 34 , LatticeT 35 , typename LatticeT::value_type 36 > 37 { 38 public: 39 typedef typename LatticeT::value_type result_type; 40 typedef result_type size_type; 41 42 private: 43 typedef gray_coded_qrng<LatticeT> self_t; 44 typedef qrng_base<self_t, LatticeT, size_type> base_t; 45 46 // The base needs to access modifying member f-ns, and we 47 // don't want these functions to be available for the public use 48 friend class qrng_base<self_t, LatticeT, size_type>; 49 50 // Respect lattice bit_count here 51 struct check_nothing { bit_posboost::random::qrng_detail::gray_coded_qrng::check_nothing52 inline static void bit_pos(unsigned) {} code_sizeboost::random::qrng_detail::gray_coded_qrng::check_nothing53 inline static void code_size(size_type) {} 54 }; 55 struct check_bit_range { raise_bit_countboost::random::qrng_detail::gray_coded_qrng::check_bit_range56 static void raise_bit_count() { 57 boost::throw_exception( std::range_error("gray_coded_qrng: bit_count") ); 58 } bit_posboost::random::qrng_detail::gray_coded_qrng::check_bit_range59 inline static void bit_pos(unsigned bit_pos) { 60 if (bit_pos >= LatticeT::bit_count) 61 raise_bit_count(); 62 } code_sizeboost::random::qrng_detail::gray_coded_qrng::check_bit_range63 inline static void code_size(size_type code) { 64 if (code > (self_t::max)()) 65 raise_bit_count(); 66 } 67 }; 68 69 // We only want to check whether bit pos is outside the range if given bit_count 70 // is narrower than the size_type, otherwise checks compile to nothing. 71 BOOST_STATIC_ASSERT(LatticeT::bit_count <= std::numeric_limits<size_type>::digits); 72 73 typedef typename mpl::if_c< 74 ((LatticeT::bit_count) < std::numeric_limits<size_type>::digits) 75 , check_bit_range 76 , check_nothing 77 >::type check_bit_range_t; 78 79 public: 80 //!Returns: Tight lower bound on the set of values returned by operator(). 81 //! 82 //!Throws: nothing. BOOST_PREVENT_MACRO_SUBSTITUTION()83 static BOOST_CONSTEXPR result_type min BOOST_PREVENT_MACRO_SUBSTITUTION () 84 { return 0; } 85 86 //!Returns: Tight upper bound on the set of values returned by operator(). 87 //! 88 //!Throws: nothing. BOOST_PREVENT_MACRO_SUBSTITUTION()89 static BOOST_CONSTEXPR result_type max BOOST_PREVENT_MACRO_SUBSTITUTION () 90 { return low_bits_mask_t<LatticeT::bit_count>::sig_bits; } 91 gray_coded_qrng(std::size_t dimension)92 explicit gray_coded_qrng(std::size_t dimension) 93 : base_t(dimension) 94 {} 95 96 // default copy c-tor is fine 97 98 // default assignment operator is fine 99 seed()100 void seed() 101 { 102 set_zero_state(); 103 update_quasi(0); 104 base_t::reset_seq(0); 105 } 106 seed(const size_type init)107 void seed(const size_type init) 108 { 109 if (init != this->curr_seq()) 110 { 111 // We don't want negative seeds. 112 check_seed_sign(init); 113 114 size_type seq_code = boost::next(init); 115 if (BOOST_UNLIKELY(!(init < seq_code))) 116 boost::throw_exception( std::range_error("gray_coded_qrng: seed") ); 117 118 seq_code ^= (seq_code >> 1); 119 // Fail if we see that seq_code is outside bit range. 120 // We do that before we even touch engine state. 121 check_bit_range_t::code_size(seq_code); 122 123 set_zero_state(); 124 for (unsigned r = 0; seq_code != 0; ++r, seq_code >>= 1) 125 { 126 if (seq_code & static_cast<size_type>(1)) 127 update_quasi(r); 128 } 129 } 130 // Everything went well, set the new seq count 131 base_t::reset_seq(init); 132 } 133 134 private: compute_seq(size_type seq)135 void compute_seq(size_type seq) 136 { 137 // Find the position of the least-significant zero in sequence count. 138 // This is the bit that changes in the Gray-code representation as 139 // the count is advanced. 140 // Xor'ing with max() has the effect of flipping all the bits in seq, 141 // except for the sign bit. 142 unsigned r = multiprecision::lsb(seq ^ (self_t::max)()); 143 check_bit_range_t::bit_pos(r); 144 update_quasi(r); 145 } 146 update_quasi(unsigned r)147 void update_quasi(unsigned r) 148 { 149 // Calculate the next state. 150 std::transform(this->state_begin(), this->state_end(), 151 this->lattice.iter_at(r * this->dimension()), this->state_begin(), 152 std::bit_xor<result_type>()); 153 } 154 set_zero_state()155 void set_zero_state() 156 { 157 std::fill(this->state_begin(), this->state_end(), result_type /*zero*/ ()); 158 } 159 }; 160 161 } // namespace qrng_detail 162 163 } // namespace random 164 } // namespace boost 165 166 #endif // BOOST_RANDOM_DETAIL_GRAY_CODED_QRNG_HPP 167