kblib  0.2.3
General utilities library for modern C++
random.h
Go to the documentation of this file.
1 /* *****************************************************************************
2  * kblib is a general utility library for C++14 and C++17, intended to provide
3  * performant high-level abstractions and more expressive ways to do simple
4  * things.
5  *
6  * Copyright (c) 2021 killerbee
7  *
8  * This program is free software: you can redistribute it and/or modify
9  * it under the terms of the GNU General Public License as published by
10  * the Free Software Foundation, either version 3 of the License, or
11  * (at your option) any later version.
12  *
13  * This program is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16  * GNU General Public License for more details.
17  *
18  * You should have received a copy of the GNU General Public License
19  * along with this program. If not, see <https://www.gnu.org/licenses/>.
20  * ****************************************************************************/
21 
32 #ifndef RANDOM_H
33 #define RANDOM_H
34 
35 #include "algorithm.h"
36 #include "iterators.h"
37 #include "memory.h"
38 #include "simple.h"
39 #include "stats.h"
40 #include "tdecl.h"
41 
42 #include <limits>
43 #include <random>
44 #include <vector>
45 
46 #if KBLIB_DEBUG_SEED_SEQ
47 # include <iostream>
48 #endif
49 
50 namespace kblib {
51 
62 template <typename Array, typename RandomGenerator, typename freqtype = double>
64  [[deprecated("Use std::discrete_distribution instead")]] constexpr auto
65  chooseCategorical(Array&& cats, RandomGenerator& r)
66  -> decltype(cats.size()) {
67  std::uniform_real_distribution<freqtype> uniform(
68  0.0, kblib::accumulate(cats.begin(), cats.end(), 0.0));
69  freqtype choose = uniform(r);
70  for (decltype(cats.size()) stop = 0; stop != cats.size(); ++stop) {
71  choose -= cats[stop];
72  if (choose <= 0) {
73  return stop;
74  }
75  }
76 #ifdef __has_builtin
77 # if __has_builtin(__builtin_unreachable)
78  __builtin_unreachable();
79 # else
80  return cats.size() - 1;
81 # endif
82 #else
83  return cats.size() - 1;
84 #endif
85 }
86 
88  public:
89  using result_type = std::uint32_t;
90 
91  trivial_seed_seq() = default;
92  template <typename InputIt>
93  trivial_seed_seq(InputIt begin, InputIt end)
94  : data(begin, end) {}
95  template <typename T>
96  trivial_seed_seq(std::initializer_list<T> il)
97  : trivial_seed_seq(il.begin(), il.end()) {}
98  template <typename Source>
99  trivial_seed_seq(Source gen, std::size_t count)
100  : data(count) {
101  kblib::generate_n(data.begin(), count, std::ref(gen));
102  }
103  // Work around std::linear_congruential_engine without overpulling from the
104  // random source
105  template <typename Source>
106  trivial_seed_seq(Source gen, std::size_t count, std::size_t discard)
107  : data(count + discard, 0x8b8b8b8bu) {
108  kblib::generate_n(data.begin() + kblib::to_signed(discard), count,
109  std::ref(gen));
110  }
111 
112  template <typename RandomAccessIt>
113  auto generate(RandomAccessIt begin, RandomAccessIt end) const -> void {
114  auto o_size = end - begin;
115  auto d_size = to_signed(data.size());
116 #if KBLIB_DEBUG_SEED_SEQ
117  if (o_size < d_size) {
118  std::clog << "trivial_seed_seq: overseeded for output size of "
119  << o_size << ", have data size " << d_size << '\n';
120  }
121 #endif
122  if (data.empty()) {
123  std::fill(begin, end, 0x8b8b8b8bu); // copied from std::seed_seq
124  } else {
125 #if KBLIB_DEBUG_SEED_SEQ
126  if (o_size > d_size) {
127  std::clog << "trivial_seed_seq: unexpectedly wrapping, output size "
128  << o_size << " greater than data size " << d_size << '\n';
129  }
130 #endif
131  auto dpos = begin;
132  do {
133  auto blk_size
134  = saturating_cast<std::size_t>(std::min(d_size, o_size));
135  dpos = std::copy_n(data.begin(), blk_size, dpos);
136  } while ((o_size -= d_size) > 0);
137  }
138  return;
139  }
140 
141  KBLIB_NODISCARD auto size() const noexcept -> std::size_t {
142  return data.size();
143  }
144 
145  template <typename OutputIt>
146  auto param(OutputIt dest) const -> void {
147  std::copy(data.begin(), data.end(), dest);
148  return;
149  }
150 
151  private:
152  std::vector<std::uint32_t> data;
153 };
154 
155 template <typename T>
156 struct state_size;
157 
158 template <typename UIntType, size_t w, size_t n, size_t m, size_t r, UIntType a,
159  size_t u, UIntType d, size_t s, UIntType b, size_t t, UIntType c,
160  size_t l, UIntType f>
161 struct state_size<std::mersenne_twister_engine<UIntType, w, n, m, r, a, u, d, s,
162  b, t, c, l, f>>
163  : std::integral_constant<std::size_t, n*((w + 31) / 32)> {};
164 
165 template <typename UIntType, UIntType a, UIntType c, UIntType m>
166 struct state_size<std::linear_congruential_engine<UIntType, a, c, m>>
167  : std::integral_constant<std::size_t, (filg2(m) + 31) / 32> {
168  // std::linear_congruential_engine discards 3 seed words due to hardcoded
169  // hack for std::seed_seq, so we work around that with this trait
170  KBLIB_CONSTANT_M std::size_t seed_discard = 3;
171 };
172 
173 template <typename UIntType, std::size_t w, std::size_t s, std::size_t r>
174 struct state_size<std::subtract_with_carry_engine<UIntType, w, s, r>>
175  : std::integral_constant<std::size_t, r*((w + 31) / 32)> {};
176 
177 template <typename Engine, std::size_t P, std::size_t R>
178 struct state_size<std::discard_block_engine<Engine, P, R>>
179  : state_size<Engine> {};
180 
181 template <typename Engine, std::size_t W, typename UIntType>
182 struct state_size<std::independent_bits_engine<Engine, W, UIntType>>
183  : state_size<Engine> {};
184 
185 template <typename Engine, std::size_t K>
186 struct state_size<std::shuffle_order_engine<Engine, K>> : state_size<Engine> {};
187 
188 template <typename T>
189 constexpr std::size_t state_size_v = state_size<T>::value;
190 
191 static_assert(state_size_v<std::mt19937> == std::mt19937::state_size);
192 static_assert(state_size_v<std::mt19937_64> == std::mt19937_64::state_size * 2);
193 
194 template <typename T, typename = void>
195 constexpr std::size_t seed_discard_v = 0;
196 template <typename T>
197 constexpr std::size_t seed_discard_v<
199  seed_discard;
200 
201 static_assert(seed_discard_v<std::minstd_rand> == 3,
202  "linear_congruential_engines discard 3 words of seed data");
203 
204 template <typename Gen, typename Source>
205 KBLIB_NODISCARD auto seeded(Source&& s) -> Gen {
206  auto seed
207  = trivial_seed_seq(std::ref(s), state_size_v<Gen>, seed_discard_v<Gen>);
208  return Gen{seed};
209 }
210 
211 template <typename Gen>
212 KBLIB_NODISCARD auto seeded() -> Gen {
213  return seeded<Gen>(std::random_device{});
214 }
215 
216 template <typename URBG, typename Transform>
218  private:
219  using E = URBG;
220  static_assert(std::is_default_constructible<Transform>::value, "");
221 
222  KBLIB_NODISCARD constexpr auto engine() -> E& {
223  return static_cast<E&>(*this);
224  }
225  KBLIB_NODISCARD constexpr auto engine() const -> const E& {
226  return static_cast<const E&>(*this);
227  }
228 
229  public:
230  using result_type = typename Transform::result_type;
231 
232  constexpr transform_engine() = default;
233  constexpr transform_engine(const transform_engine&) noexcept(
234  std::is_nothrow_copy_constructible<URBG>::value)
235  = default;
236  constexpr transform_engine(transform_engine&&) noexcept(
237  std::is_nothrow_move_constructible<URBG>::value)
238  = default;
240  : E(s) {}
241  template <typename SSeq,
242  typename
244  constexpr transform_engine(SSeq& s)
245  : E(s) {}
246 
248  -> transform_engine& = delete;
250  -> transform_engine& = delete;
251 
252  ~transform_engine() = default;
253 
254  KBLIB_NODISCARD constexpr auto operator()() noexcept -> result_type {
255  return Transform{}(engine()());
256  }
257 
258  using E::seed;
259 
260  using E::discard;
261 
262  KBLIB_NODISCARD static constexpr auto min() noexcept -> result_type {
263  return Transform::min(URBG::min(), URBG::max());
264  }
265  KBLIB_NODISCARD static constexpr auto max() noexcept -> result_type {
266  return Transform::max(URBG::min(), URBG::max());
267  }
268 
269  KBLIB_NODISCARD friend constexpr auto operator==(
270  const transform_engine& lhs, const transform_engine& rhs) noexcept
271  -> bool {
272  return lhs.engine() == rhs.engine();
273  }
274  KBLIB_NODISCARD friend constexpr auto operator!=(
275  const transform_engine& lhs, const transform_engine& rhs) noexcept
276  -> bool {
277  return ! (lhs == rhs);
278  }
279 
280  friend constexpr auto operator<<(std::ostream& os, const transform_engine& e)
281  -> std::ostream& {
282  return os << e.engine();
283  }
284  friend constexpr auto operator>>(std::istream& is, transform_engine& e)
285  -> std::istream& {
286  return is >> e.engine();
287  }
288 };
289 
290 template <typename Engine, typename Transform>
291 struct state_size<transform_engine<Engine, Transform>> : state_size<Engine> {};
292 
293 template <typename UIntType, UIntType shift, UIntType mask = max>
294 struct shift_mask {
295  using result_type = UIntType;
296 
297  template <typename UIntInput>
298  KBLIB_NODISCARD static constexpr auto g(UIntInput in) noexcept -> UIntType {
299  return static_cast<UIntType>(in >> shift) & mask;
300  }
301  KBLIB_NODISCARD constexpr auto operator()(UIntType in) const noexcept
302  -> UIntType {
303  return g(in);
304  }
305  KBLIB_NODISCARD static constexpr auto min(UIntType min,
306  KBLIB_UNUSED UIntType max) noexcept
307  -> UIntType {
308  return g(min);
309  }
310  KBLIB_NODISCARD static constexpr auto max(KBLIB_UNUSED UIntType min,
311  UIntType max) noexcept
312  -> UIntType {
313  return g(max);
314  }
315 };
316 
317 template <typename UIntType>
318 KBLIB_NODISCARD constexpr auto ipow2(UIntType b) noexcept -> UIntType {
319  if (b == std::numeric_limits<UIntType>::digits) {
320  return 0u;
321  } else {
322  return UIntType{1} << b;
323  }
324 }
325 
326 inline namespace lcgs {
327  template <typename UIntType, UIntType a, UIntType c, UIntType b>
328  using lcg_p2 = std::linear_congruential_engine<UIntType, a, c, ipow2(b)>;
329 
330  inline namespace common_lcgs {
331  using rand48
334  using java_rand
335  = std::linear_congruential_engine<std::uint_fast64_t, 0x5DEECE66D, 11,
336  1ull << 48u>;
337 
338  using knuth_lcg = std::linear_congruential_engine<
339  uint64_t, 6364136223846793005U, 1442695040888963407U,
340  0U>; /* Knuth's preferred 64-bit LCG */
341 
342  } // namespace common_lcgs
343 
344  inline namespace best_lcgs {
345 
348 
351 
354 
355  } // namespace best_lcgs
356 
357 } // namespace lcgs
358 
359 } // namespace kblib
360 
361 #endif // RANDOM_H
Provides general-purpose algorithms, similar to the <algorithms> header.
constexpr transform_engine(SSeq &s)
Definition: random.h:244
constexpr friend auto operator>>(std::istream &is, transform_engine &e) -> std::istream &
Definition: random.h:284
constexpr friend auto operator!=(const transform_engine &lhs, const transform_engine &rhs) noexcept -> bool
Definition: random.h:274
constexpr transform_engine()=default
auto operator=(const transform_engine &) -> transform_engine &=delete
constexpr transform_engine(transform_engine &&) noexcept(std::is_nothrow_move_constructible< URBG >::value)=default
typename Transform::result_type result_type
Definition: random.h:230
constexpr friend auto operator<<(std::ostream &os, const transform_engine &e) -> std::ostream &
Definition: random.h:280
static constexpr auto max() noexcept -> result_type
Definition: random.h:265
constexpr transform_engine(const transform_engine &) noexcept(std::is_nothrow_copy_constructible< URBG >::value)=default
static constexpr auto min() noexcept -> result_type
Definition: random.h:262
constexpr auto operator()() noexcept -> result_type
Definition: random.h:254
auto operator=(transform_engine &&) -> transform_engine &=delete
constexpr friend auto operator==(const transform_engine &lhs, const transform_engine &rhs) noexcept -> bool
Definition: random.h:269
trivial_seed_seq(Source gen, std::size_t count, std::size_t discard)
Definition: random.h:106
trivial_seed_seq(std::initializer_list< T > il)
Definition: random.h:96
auto generate(RandomAccessIt begin, RandomAccessIt end) const -> void
Definition: random.h:113
trivial_seed_seq(InputIt begin, InputIt end)
Definition: random.h:93
auto param(OutputIt dest) const -> void
Definition: random.h:146
auto size() const noexcept -> std::size_t
Definition: random.h:141
trivial_seed_seq(Source gen, std::size_t count)
Definition: random.h:99
std::uint32_t result_type
Definition: random.h:89
This file provides some iterators, ranges, iterator/range adapters, and operations that can be perfor...
Provides utilities to enable safe and expressive memory management and low-level memory manipulation.
typename make_void< Ts... >::type void_t
Definition: fakestd.h:178
lcg_p2< std::uint_fast64_t, 0xbdcdbb079f8du, 0u, 48u > mcg48
Definition: random.h:350
lcg_p2< std::uint_fast64_t, 0xf1357aea2e62a9c5u, 0u, 64u > mcg64
Definition: random.h:353
lcg_p2< std::uint_fast64_t, 0xb67a49a5466du, 1u, 48u > lcg48
Definition: random.h:349
lcg_p2< std::uint_fast32_t, 0x93d765ddu, 0u, 32u > mcg32
Definition: random.h:347
lcg_p2< std::uint_fast32_t, 0xa13fc965u, 1u, 32u > lcg32
Definition: random.h:346
lcg_p2< std::uint_fast64_t, 0xaf251af3b0f025b5u, 1u, 64u > lcg64
Definition: random.h:352
std::linear_congruential_engine< uint64_t, 6364136223846793005U, 1442695040888963407U, 0U > knuth_lcg
Definition: random.h:340
std::linear_congruential_engine< std::uint_fast64_t, 0x5DEECE66D, 11, 1ull<< 48u > java_rand
Definition: random.h:336
std::linear_congruential_engine< UIntType, a, c, ipow2(b)> lcg_p2
Definition: random.h:328
constexpr struct kblib::nums::min_t min
constexpr struct kblib::nums::max_t max
The main namespace in which all entities from kblib are defined.
Definition: algorithm.h:44
constexpr auto to_signed(I x) -> std::make_signed_t< I >
Cast integral argument to corresponding signed type.
Definition: fakestd.h:592
constexpr auto a(const std::initializer_list< T > &a) -> auto
Index an array literal without naming its type.
Definition: simple.h:255
typename std::enable_if< B, T >::type enable_if_t
Definition: fakestd.h:54
constexpr auto copy_n(InputIt first, Size count, OutputIt out) -> OutputIt
Copies all elements of [first, std::advance(first, n)) to out.
Definition: algorithm.h:1365
constexpr auto generate_n(OutputIt first, Size count, Generator g) noexcept(noexcept(*first++=g())) -> OutputIt
Like std::generate_n except that it is constexpr.
Definition: algorithm.h:1564
constexpr auto e() -> T
Definition: stats.h:465
auto seeded(Source &&s) -> Gen
Definition: random.h:205
constexpr auto ipow2(UIntType b) noexcept -> UIntType
Definition: random.h:318
constexpr auto accumulate(InputIt first, InputIt last, T init) -> T
A constexpr version of std::accumulate.
Definition: algorithm.h:162
constexpr std::size_t state_size_v
Definition: random.h:189
constexpr auto copy(InputIt first, EndIt last, OutputIt out) -> OutputIt
Copies all elements of [first, last) to out. It also allows for a sentinel end iterator.
Definition: algorithm.h:1322
constexpr std::size_t seed_discard_v
Definition: random.h:195
constexpr auto chooseCategorical(Array &&cats, RandomGenerator &r) -> decltype(cats.size())
Given a categorical distribution cats, selects one category.
Definition: random.h:65
Definition: bits.h:714
Provides general utilities which do not fit in any more specific header.
Provides numerical and mathematical utilities.
static constexpr auto max([[maybe_unused]] UIntType min, UIntType max) noexcept -> UIntType
Definition: random.h:310
static constexpr auto min(UIntType min, [[maybe_unused]] UIntType max) noexcept -> UIntType
Definition: random.h:305
constexpr auto operator()(UIntType in) const noexcept -> UIntType
Definition: random.h:301
UIntType result_type
Definition: random.h:295
static constexpr auto g(UIntInput in) noexcept -> UIntType
Definition: random.h:298
Provides macros and basic templates used by the rest of kblib.
#define KBLIB_UNUSED
This internal macro is used to provide a fallback for [[maybe_unused]] in C++14.
Definition: tdecl.h:92
#define KBLIB_NODISCARD
This internal macro is used to provide a fallback for [[nodiscard]] in C++14.
Definition: tdecl.h:81
#define KBLIB_CONSTANT_M
Definition: tdecl.h:100