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
50namespace KBLIB_NS {
51
62template <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
155template <typename T>
157
158template <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>
161struct 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
165template <typename UIntType, UIntType a, UIntType c, UIntType m>
166struct 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
173template <typename UIntType, std::size_t w, std::size_t s, std::size_t r>
174struct state_size<std::subtract_with_carry_engine<UIntType, w, s, r>>
175 : std::integral_constant<std::size_t, r*((w + 31) / 32)> {};
176
177template <typename Engine, std::size_t P, std::size_t R>
178struct state_size<std::discard_block_engine<Engine, P, R>>
179 : state_size<Engine> {};
180
181template <typename Engine, std::size_t W, typename UIntType>
182struct state_size<std::independent_bits_engine<Engine, W, UIntType>>
183 : state_size<Engine> {};
184
185template <typename Engine, std::size_t K>
186struct state_size<std::shuffle_order_engine<Engine, K>> : state_size<Engine> {};
187
188template <typename T>
189constexpr std::size_t state_size_v = state_size<T>::value;
190
191static_assert(state_size_v<std::mt19937> == std::mt19937::state_size, "");
192static_assert(state_size_v<std::mt19937_64> == std::mt19937_64::state_size * 2,
193 "");
194
195template <typename T, typename = void>
196constexpr std::size_t seed_discard_v = 0;
197template <typename T>
198constexpr std::size_t seed_discard_v<
200 seed_discard;
201
202static_assert(seed_discard_v<std::minstd_rand> == 3,
203 "linear_congruential_engines discard 3 words of seed data");
204
205template <typename Gen, typename Source>
206KBLIB_NODISCARD auto seeded(Source&& s) -> Gen {
207 auto seed
208 = trivial_seed_seq(std::ref(s), state_size_v<Gen>, seed_discard_v<Gen>);
209 return Gen{seed};
210}
211
212template <typename Gen>
213KBLIB_NODISCARD auto seeded() -> Gen {
214 return seeded<Gen>(std::random_device{});
215}
216
217template <typename URBG, typename Transform>
219 private:
220 using E = URBG;
221 static_assert(std::is_default_constructible<Transform>::value, "");
222
223 KBLIB_NODISCARD constexpr auto engine() -> E& {
224 return static_cast<E&>(*this);
225 }
226 KBLIB_NODISCARD constexpr auto engine() const -> const E& {
227 return static_cast<const E&>(*this);
228 }
229
230 public:
231 using result_type = typename Transform::result_type;
232
233 constexpr transform_engine() = default;
234 constexpr transform_engine(const transform_engine&) noexcept(
235 std::is_nothrow_copy_constructible<URBG>::value)
236 = default;
237 constexpr transform_engine(transform_engine&&) noexcept(
238 std::is_nothrow_move_constructible<URBG>::value)
239 = default;
241 : E(s) {}
242 template <typename SSeq,
243 typename
245 constexpr transform_engine(SSeq& s)
246 : E(s) {}
247
249 -> transform_engine& = delete;
251 -> transform_engine& = delete;
252
253 ~transform_engine() = default;
254
255 KBLIB_NODISCARD constexpr auto operator()() noexcept -> result_type {
256 return Transform{}(engine()());
257 }
258
259 // using E::seed;
260
261 using E::discard;
262
263 KBLIB_NODISCARD static constexpr auto min() noexcept -> result_type {
265 }
266 KBLIB_NODISCARD static constexpr auto max() noexcept -> result_type {
268 }
269
270 KBLIB_NODISCARD friend constexpr auto operator==(
271 const transform_engine& lhs, const transform_engine& rhs) noexcept
272 -> bool {
273 return lhs.engine() == rhs.engine();
274 }
275 KBLIB_NODISCARD friend constexpr auto operator!=(
276 const transform_engine& lhs, const transform_engine& rhs) noexcept
277 -> bool {
278 return ! (lhs == rhs);
279 }
280
281 friend constexpr auto operator<<(std::ostream& os, const transform_engine& e)
282 -> std::ostream& {
283 return os << e.engine();
284 }
285 friend constexpr auto operator>>(std::istream& is, transform_engine& e)
286 -> std::istream& {
287 return is >> e.engine();
288 }
289};
290
291template <typename Engine, typename Transform>
292struct state_size<transform_engine<Engine, Transform>> : state_size<Engine> {};
293
294template <typename UIntType, UIntType shift, UIntType mask = max>
296 using result_type = UIntType;
297
298 template <typename UIntInput>
299 KBLIB_NODISCARD static constexpr auto g(UIntInput in) noexcept -> UIntType {
300 return static_cast<UIntType>(in >> shift) & mask;
301 }
302 KBLIB_NODISCARD constexpr auto operator()(UIntType in) const noexcept
303 -> UIntType {
304 return g(in);
305 }
306 KBLIB_NODISCARD static constexpr auto min(UIntType min,
307 KBLIB_UNUSED UIntType max) noexcept
308 -> UIntType {
309 return g(min);
310 }
311 KBLIB_NODISCARD static constexpr auto max(KBLIB_UNUSED UIntType min,
312 UIntType max) noexcept
313 -> UIntType {
314 return g(max);
315 }
316};
317
318template <typename UIntType>
319KBLIB_NODISCARD constexpr auto ipow2(UIntType b) noexcept -> UIntType {
320 if (b == std::numeric_limits<UIntType>::digits) {
321 return 0u;
322 } else {
323 return UIntType{1} << b;
324 }
325}
326
327inline namespace lcgs {
328 // shortcut alias for common case of m = 2^b
329 template <typename UIntType, UIntType a, UIntType c, UIntType b>
330 using lcg_p2 = std::linear_congruential_engine<UIntType, a, c, ipow2(b)>;
331
332 inline namespace common_lcgs {
333 using rand48
337
340 shift_mask<std::uint_fast32_t, 0, ipow2(30) - 1>>;
343 shift_mask<std::uint_fast32_t, 16, ipow2(14) - 1>>;
344
345 using knuth_lcg = std::linear_congruential_engine<
346 uint64_t, 6364136223846793005U, 1442695040888963407U,
347 0U>; /* Knuth's preferred 64-bit LCG */
348
349 } // namespace common_lcgs
350
351 inline namespace best_lcgs {
352 // mcg = multiplicative congruential generator
353 // note that for an mcg to work effectively, the seed must be coprime to m
354 // in this case, that means seeds must be odd
355
356 // lcgs do not have this restriction.
357
360
363
366
367 } // namespace best_lcgs
368
369} // namespace lcgs
370
371} // namespace KBLIB_NS
372
373#endif // RANDOM_H
Provides general-purpose algorithms, similar to the <algorithms> header.
friend constexpr auto operator>>(std::istream &is, transform_engine &e) -> std::istream &
Definition: random.h:285
constexpr transform_engine(SSeq &s)
Definition: random.h:245
friend constexpr auto operator!=(const transform_engine &lhs, const transform_engine &rhs) noexcept -> bool
Definition: random.h:275
constexpr transform_engine()=default
friend constexpr auto operator==(const transform_engine &lhs, const transform_engine &rhs) noexcept -> bool
Definition: random.h:270
friend constexpr auto operator<<(std::ostream &os, const transform_engine &e) -> std::ostream &
Definition: random.h:281
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:231
static constexpr auto max() noexcept -> result_type
Definition: random.h:266
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:263
constexpr auto operator()() noexcept -> result_type
Definition: random.h:255
auto operator=(transform_engine &&) -> transform_engine &=delete
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:186
lcg_p2< std::uint_fast64_t, 0xbdcdbb079f8du, 0u, 48u > mcg48
Definition: random.h:362
lcg_p2< std::uint_fast64_t, 0xf1357aea2e62a9c5u, 0u, 64u > mcg64
Definition: random.h:365
lcg_p2< std::uint_fast64_t, 0xb67a49a5466du, 1u, 48u > lcg48
Definition: random.h:361
lcg_p2< std::uint_fast32_t, 0x93d765ddu, 0u, 32u > mcg32
Definition: random.h:359
lcg_p2< std::uint_fast32_t, 0xa13fc965u, 1u, 32u > lcg32
Definition: random.h:358
lcg_p2< std::uint_fast64_t, 0xaf251af3b0f025b5u, 1u, 64u > lcg64
Definition: random.h:364
std::linear_congruential_engine< uint64_t, 6364136223846793005U, 1442695040888963407U, 0U > knuth_lcg
Definition: random.h:347
transform_engine< lcg_p2< std::uint_fast64_t, 25214903917u, 11u, 48u >, shift_mask< std::uint_fast32_t, 16u > > rand48
Definition: random.h:335
std::linear_congruential_engine< UIntType, a, c, ipow2(b)> lcg_p2
Definition: random.h:330
constexpr struct kblib::nums::min_t min
constexpr struct kblib::nums::max_t max
constexpr auto to_signed(I x) -> std::make_signed_t< I >
Cast integral argument to corresponding signed type.
Definition: fakestd.h:599
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:61
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:1565
auto seeded() -> Gen
Definition: random.h:213
constexpr auto e() -> T
Definition: stats.h:468
constexpr auto ipow2(UIntType b) noexcept -> UIntType
Definition: random.h:319
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:196
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:721
Provides general utilities which do not fit in any more specific header.
Provides numerical and mathematical utilities.
static constexpr auto max(UIntType min, UIntType max) noexcept -> UIntType
Definition: random.h:311
static constexpr auto min(UIntType min, UIntType max) noexcept -> UIntType
Definition: random.h:306
constexpr auto operator()(UIntType in) const noexcept -> UIntType
Definition: random.h:302
UIntType result_type
Definition: random.h:296
static constexpr auto g(UIntInput in) noexcept -> UIntType
Definition: random.h:299
Provides macros and basic templates used by the rest of kblib.
#define KBLIB_NS
Definition: tdecl.h:113
#define KBLIB_UNUSED
This internal macro is used to provide a fallback for [[maybe_unused]] in C++14.
Definition: tdecl.h:130
#define KBLIB_NODISCARD
This internal macro is used to provide a fallback for [[nodiscard]] in C++14.
Definition: tdecl.h:129
#define KBLIB_CONSTANT_M
Definition: tdecl.h:139