source: mainline/uspace/lib/cpp/include/impl/random.hpp@ 1a617ac

lfn serial ticket/834-toolchain-update topic/msim-upgrade topic/simplify-dev-export
Last change on this file since 1a617ac was 1a617ac, checked in by Dzejrou <dzejrou@…>, 7 years ago

cpp: added linear_congruential_engine
  • Property mode set to 100644
File size: 14.4 KB
Line 
1/*
2 * Copyright (c) 2018 Jaroslav Jindrak
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 *
9 * - Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * - Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 * - The name of the author may not be used to endorse or promote products
15 * derived from this software without specific prior written permission.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 */
28
29#ifndef LIBCPP_RANDOM
30#define LIBCPP_RANDOM
31
32#include <cstdlib>
33#include <ctime>
34#include <initializer_list>
35#include <internal/builtins.hpp>
36#include <limits>
37#include <type_traits>
38#include <vector>
39
40/**
41 * Note: Variables with one or two lettered
42 * names here are named after their counterparts in
43 * the standard. If one needs to understand their meaning,
44 * they should seek the mentioned standard section near
45 * the declaration of these variables.
46 * Note: There will be a lot of mathematical expressions in this header.
47 * All of these are taken directly from the standard's requirements
48 * and as such won't be commented here, check the appropriate
49 * sections if you need explanation of these forumulae.
50 */
51
52namespace std
53{
54 namespace aux
55 {
56 /**
57 * This is the minimum requirement imposed by the
58 * standard for a type to qualify as a seed sequence
59 * in overloading resolutions.
60 * (This is because the engines have constructors
61 * that accept sequence and seed and without this
62 * minimal requirements overload resolution would fail.)
63 */
64 template<class Sequence, class ResultType>
65 struct is_seed_sequence
66 : aux::value_is<
67 bool, !is_convertible_v<Sequence, ResultType>
68 >
69 { /* DUMMY BODY */ };
70
71 template<class T, class Engine>
72 inline constexpr bool is_seed_sequence_v = is_seed_sequence<T, Engine>::value;
73 }
74
75 /**
76 * 26.5.3.1, class template linear_congruential_engine:
77 */
78
79 template<class UIntType, UIntType a, UIntType c, UIntType m>
80 class linear_congruential_engine
81 {
82 static_assert(m == 0 || (a < m && c < m));
83
84 public:
85 using result_type = UIntType;
86
87 static constexpr result_type multiplier = a;
88 static constexpr result_type increment = c;
89 static constexpr result_type modulus = m;
90
91 static constexpr min()
92 {
93 return c == 0U ? 1U : 0U;
94 }
95
96 static constexpr max()
97 {
98 return m - 1U;
99 }
100
101 static constexpr result_type default_seed = 1U;
102
103 explicit linear_congruential_engine(result_type s = default_seed)
104 : state_{}
105 {
106 seed(s);
107 }
108
109 linear_congruential_engine(const linear_congruential_engine& other)
110 : state_{other.state_}
111 { /* DUMMY BODY */ }
112
113 template<class Seq>
114 explicit linear_congruential_engine(
115 enable_if_t<aux::is_seed_sequence_v<Seq, result_type>, Seq&> q
116 )
117 : state_{}
118 {
119 size_t k = static_cast<size_t>(aux::ceil(aux::log2(modulus_) / 32));
120 auto arr = new result_type[k + 3];
121
122 q.generate(arr, arr + k + 3);
123
124 result_type s{};
125 for (size_t j = 0; j < k; ++j)
126 s += a[j + 3] * aux::pow2(32U * j);
127 s = s % modulus_;
128
129 seed(s);
130 }
131
132 void seed(result_type s = default_seed)
133 {
134 if (c % modulus_ == 0 && s == 0)
135 state_ = 0;
136 else
137 state_ = s;
138 }
139
140 template<class Seq>
141 void seed(
142 enable_if_t<aux::is_seed_sequence_v<Seq, result_type>, Seq&> q
143 );
144
145 result_type operator()()
146 {
147 return generate_();
148 }
149
150 void discard(unsigned long long z)
151 {
152 for (unsigned long long i = 0ULL; i < z; ++i)
153 transition_();
154 }
155
156 bool operator==(const linear_congruential_engine& rhs) const
157 {
158 return state_ = rhs.state_;
159 }
160
161 bool operator!=(const linear_congruential_engine& rhs) const
162 {
163 return !(*this == rhs);
164 }
165
166 template<class Char, class Traits>
167 basic_ostream<Char, Traits>& operator<<(basic_ostream<Char, Traits>& os) const
168 {
169 auto flags = os.flags();
170 os.flags(ios_base::dec | ios_base::left);
171
172 os << state_;
173
174 os.flags(flags);
175 return os;
176 }
177
178 template<class Char, class Traits>
179 basic_istream<Char, Traits>& operator>>(basic_istream<Char, Traits>& is) const
180 {
181 auto flags = is.flags();
182 is.flags(ios_base::dec);
183
184 result_type tmp{};
185 if (is >> tmp)
186 state_ = tmp;
187 else
188 is.setstate(ios::failbit);
189
190 is.flags(flags);
191 return is;
192 }
193
194 private:
195 result_type state_;
196
197 static constexpr result_type modulus_ =
198 (m == 0) ? (numeric_limits<result_type>::max() + 1) : m;
199
200 void transition_()
201 {
202 state_ = (a * state_ + c) % modulus_;
203 }
204
205 result_type generate_()
206 {
207 transition_();
208
209 return state_;
210 }
211 };
212
213 /**
214 * 26.5.3.2, class template mersenne_twister_engine:
215 */
216
217 template<
218 class UIntType, size_t w, size_t n, size_t m, size_t r,
219 UIntType a, size_t u, UIntType d, size_t s,
220 UIntType b, size_t t, UIntType c, size_t l, UIntType f
221 >
222 class mersenne_twister_engine;
223
224 /**
225 * 26.5.3.3, class template subtract_with_carry_engine:
226 */
227
228 template<class UIntType, size_t w, size_t s, size_t r>
229 class subtract_with_carry_engine;
230
231 /**
232 * 26.5.4.2, class template discard_block_engine:
233 */
234
235 template<class Engine, size_t p, size_t r>
236 class discard_block_engine;
237
238 /**
239 * 26.5.4.3, class template independent_bits_engine:
240 */
241
242 template<class Engine, size_t w, class UIntType>
243 class independent_bits_engine;
244
245 /**
246 * 26.5.4.4, class template shiffle_order_engine:
247 */
248
249 template<class Engine, size_t k>
250 class shuffle_order_engine;
251
252 /**
253 * 26.5.5, engines and engine adaptors with predefined
254 * parameters:
255 * TODO: check their requirements for testing
256 */
257
258 using minstd_rand0 = linear_congruential_engine<uint_fast32_t, 16807, 0, 2147483647>;
259 using minstd_rand = linear_congruential_engine<uint_fast32_t, 48271, 0, 2147483647>;
260 using mt19937 = mersenne_twister_engine<
261 uint_fast32_t, 32, 624, 397, 31, 0x9908b0df, 11, 0xffffffff, 7,
262 0x9d2c5680, 15, 0xefc60000, 18, 1812433253
263 >;
264 using mt19937_64 = mersenne_twister_engine<
265 uint_fast64_t, 64, 312, 156, 31, 0xb5026f5aa96619e9, 29,
266 0x5555555555555555, 17, 0x71d67fffeda60000, 37, 0xfff7eee000000000,
267 43, 6364136223846793005
268 >;
269 using ranlux24_base = subtract_with_carry_engine<uint_fast32_t, 24, 10, 24>;
270 using ranlux48_base = subtract_with_carry_engine<uint_fast64_t, 48, 5, 12>;
271 using ranlux24 = discard_block_engine<ranlux24_base, 223, 23>;
272 using ranlux48 = discard_block_engine<ranlux48_base, 389, 11>;
273 using knuth_b = shuffle_order_engine<minstd_rand0, 256>;
274
275 using default_random_engine = minstd_rand0;
276
277 /**
278 * 26.5.6, class random_device:
279 */
280
281 class random_device
282 {
283 using result_type = unsigned int;
284
285 static constexpr result_type min()
286 {
287 return numeric_limits<result_type>::min();
288 }
289
290 static constexpr result_type max()
291 {
292 return numeric_limits<result_type>::max();
293 }
294
295 explicit random_device(const string& token = "")
296 {
297 /**
298 * Note: token can be used to choose between
299 * random generators, but HelenOS only
300 * has one :/
301 * Also note that it is implementation
302 * defined how this class generates
303 * random numbers and I decided to use
304 * time seeding with C stdlib random,
305 * - feel free to change it if you know
306 * something better.
307 */
308 hel::srandom(hel::time(nullptr));
309 }
310
311 result_type operator()()
312 {
313 return hel::random();
314 }
315
316 double entropy() const noexcept
317 {
318 return 0.0;
319 }
320
321 random_device(const random_device&) = delete;
322 random_device& operator=(const random_device&) = delete;
323 };
324
325 /**
326 * 26.5.7.1, class seed_seq:
327 */
328
329 class seed_seq
330 {
331 public:
332 using result_type = uint_least32_t;
333
334 seed_seq()
335 : vec_{}
336 { /* DUMMY BODY */ }
337
338 template<class T>
339 seed_seq(initializer_list<T> init)
340 : seed_seq(init.begin(), init.end())
341 { /* DUMMY BODY */ }
342
343 template<class InputIterator>
344 seed_seq(InputIterator first, InputIterator last)
345 : vec_{}
346 {
347 while (first != last)
348 vec_.push_back(*first++ % aux::pow2(32));
349 }
350
351 template<class RandomAccessGenerator>
352 void generate(RandomAccessGenerator first,
353 RandomAccessGenerator last)
354 {
355 if (first == last)
356 return;
357
358 // TODO: research this
359 }
360
361 size_t size() const
362 {
363 return vec_.size();
364 }
365
366 template<class OutputIterator>
367 void param(OutputIterator dest) const
368 {
369 for (const auto& x: vec_)
370 *dest++ = x;
371 }
372
373 seed_seq(const seed_seq&) = delete;
374 seed_seq& operator=(const seed_seq&) = delete;
375
376 private:
377 vector<result_type> vec_;
378 };
379
380 /**
381 * 26.5.7.2, function template generate_canonical:
382 */
383
384 template<class RealType, size_t bits, class URNG>
385 RealType generate_canonical(URNG& g);
386
387 /**
388 * 26.5.8.2.1, class template uniform_int_distribution:
389 */
390
391 template<class IntType = int>
392 class uniform_int_distribution;
393
394 /**
395 * 26.5.8.2.2, class template uniform_real_distribution:
396 */
397
398 template<class RealType = double>
399 class uniform_real_distribution;
400
401 /**
402 * 26.5.8.3.1, class bernoulli_distribution:
403 */
404
405 class bernoulli_distribution;
406
407 /**
408 * 26.5.8.3.2, class template binomial_distribution:
409 */
410
411 template<class IntType = int>
412 class binomial_distribution;
413
414 /**
415 * 26.5.8.3.3, class template geometric_distribution:
416 */
417
418 template<class IntType = int>
419 class geometric_distribution;
420
421 /**
422 * 26.5.8.3.4, class template negative_binomial_distribution:
423 */
424
425 template<class IntType = int>
426 class negative_binomial_distribution;
427
428 /**
429 * 26.5.8.4.1, class template poisson_distribution:
430 */
431
432 template<class IntType = int>
433 class poisson_distribution;
434
435 /**
436 * 26.5.8.4.2, class template exponential_distribution:
437 */
438
439 template<class RealType = double>
440 class exponential_distribution;
441
442 /**
443 * 26.5.8.4.3, class template gamma_distribution:
444 */
445
446 template<class RealType = double>
447 class gamma_distribution;
448
449 /**
450 * 26.5.8.4.4, class template weibull_distribution:
451 */
452
453 template<class RealType = double>
454 class weibull_distribution;
455
456 /**
457 * 26.5.8.4.5, class template extreme_value_distribution:
458 */
459
460 template<class RealType = double>
461 class extreme_value_distribution;
462
463 /**
464 * 26.5.8.5.1, class template normal_distribution:
465 */
466
467 template<class RealType = double>
468 class normal_distribution;
469
470 /**
471 * 26.5.8.5.2, class template lognormal_distribution:
472 */
473
474 template<class RealType = double>
475 class lognormal_distribution;
476
477 /**
478 * 26.5.8.5.3, class template chi_squared_distribution:
479 */
480
481 template<class RealType = double>
482 class chi_squared_distribution;
483
484 /**
485 * 26.5.8.5.4, class template cauchy_distribution:
486 */
487
488 template<class RealType = double>
489 class cauchy_distribution;
490
491 /**
492 * 26.5.8.5.5, class template fisher_f_distribution:
493 */
494
495 template<class RealType = double>
496 class fisher_f_distribution;
497
498 /**
499 * 26.5.8.5.6, class template student_t_distribution:
500 */
501
502 template<class RealType = double>
503 class student_t_distribution;
504
505 /**
506 * 26.5.8.6.1, class template discrete_distribution:
507 */
508
509 template<class IntType = int>
510 class discrete_distribution;
511
512 /**
513 * 26.5.8.6.2, class template piecewise_constant_distribution:
514 */
515
516 template<class RealType = double>
517 class piecewise_constant_distribution;
518
519 /**
520 * 26.5.8.6.3, class template piecewise_linear_distribution:
521 */
522
523 template<class RealType = double>
524 class piecewise_linear_distribution;
525}
526
527#endif
Note: See TracBrowser for help on using the repository browser.