<tt>xoshiro
Loading...
Searching...
No Matches
xoshiro.h
Go to the documentation of this file.
1#pragma once
2// SPDX-FileCopyrightText: 2023 Nessan Fitzmaurice <nessan.fitzmaurice@me.com>
3// SPDX-License-Identifier: MIT
4
8
9#include <algorithm>
10#include <array>
11#include <bit>
12#include <cassert>
13#include <chrono>
14#include <concepts>
15#include <cstdint>
16#include <format>
17#include <iterator>
18#include <limits>
19#include <ostream>
20#include <random>
21#include <ranges>
22#include <stdexcept>
23#include <string>
24#include <type_traits>
25#include <vector>
26
27// If the `gf2` library is available, we provide extra methods---primarily for analysing new RNG variants.
28// For normal use, this is not required & the single-header xoshiro.h works fine without it.
29#ifdef GF2
30 #include <gf2/gf2.h>
31#endif
32
33namespace xso {
34
35// --------------------------------------------------------------------------------------------------------------------
36// A C++ concept that lets us distinguish standard distribution types from other types.
37// --------------------------------------------------------------------------------------------------------------------
38
45template<typename Dist>
46concept Distribution = requires { typename Dist::param_type; };
47
48// --------------------------------------------------------------------------------------------------------------------
49// Forward declarations of methods defined later in this file.
50// --------------------------------------------------------------------------------------------------------------------
51template<typename State>
52constexpr auto jump_coefficients(std::size_t J, bool J_is_log2 = false);
53
54template<std::unsigned_integral word_type, std::size_t N>
55constexpr auto reduce(const std::array<word_type, N>& p, std::size_t J, bool J_is_log2 = false);
56
57// --------------------------------------------------------------------------------------------------------------------
58// The xoshiro/xoroshiro pseudorandom number generator class template.
59// --------------------------------------------------------------------------------------------------------------------
60
68template<typename State, typename Scrambler>
69class generator {
70public:
73
75 using state_type = State;
76
78 using scrambler_type = Scrambler;
79
81 using word_type = typename State::word_type;
82
84 using array_type = typename State::array_type;
85
92 static constexpr std::size_t word_count() { return State::word_count(); }
93
100 static constexpr std::size_t bit_count() { return State::bit_count(); }
101
114 static constexpr auto type_string() {
115 return std::format("{} with {}", State::type_string(), Scrambler::type_string());
116 }
117
121
128
138 static constexpr result_type min() noexcept { return 0; }
139
149 static constexpr result_type max() noexcept { return std::numeric_limits<result_type>::max(); }
150
154
166
177 explicit constexpr generator(word_type s) { seed(s); }
178
196 template<std::input_iterator Iter>
197 requires std::convertible_to<std::iter_value_t<Iter>, word_type>
198 explicit constexpr generator(Iter b, Iter e) {
199 seed(b, e);
200 }
201
205
220 void seed() {
221 // We will use std::random_device as the principal source of entropy.
222 std::random_device dev;
223
224 // Fill a full seed array with calls to dev() -- may need a couple of dev() calls to fill one word of state.
225 array_type full_state;
226 if constexpr (sizeof(word_type) <= sizeof(std::random_device::result_type)) {
227 for (auto& word : full_state) word = static_cast<word_type>(dev());
228 } else {
229 for (auto& word : full_state) word = static_cast<word_type>(static_cast<uint64_t>(dev()) << 32 | dev());
230 }
231
232 // However, `std::random_device` may be poor so add data from a call to a high resolution clock for first word.
233 using clock_type = std::chrono::high_resolution_clock;
234 auto ticks = static_cast<std::uint64_t>(clock_type::now().time_since_epoch().count());
235
236 // From call to call, time ticks only changes in the low order bits -- better scramble things a bit!
237 ticks = murmur_scramble64(ticks);
238
239 // Fold the scrambled ticks variable into the first seed word.
240 full_state[0] ^= static_cast<word_type>(ticks);
241
242 // Seed the state from our full "high quality" seed array.
243 m_state.seed(full_state.cbegin(), full_state.cend());
244 }
245
258 constexpr void seed(word_type seed) {
259 // Scramble the bits in the single seed we were given.
260 auto sm64_state = murmur_scramble64(seed);
261
262 // Use SplitMix64 to at least put some values in all the state words & seed the state.
263 array_type full_state;
264 for (auto& word : full_state) word = static_cast<word_type>(split_mix64(sm64_state));
265 m_state.seed(full_state.cbegin(), full_state.cend());
266 }
267
287 template<std::input_iterator Src>
288 requires std::convertible_to<std::iter_value_t<Src>, word_type>
289 constexpr void seed(Src b, Src e) {
290 m_state.seed(b, e);
291 }
292
296
298 constexpr void step() { m_state.step(); }
299
307 result_type result = m_scrambler(m_state);
308 step();
309 return result;
310 }
311
315
317 constexpr word_type operator[](std::size_t i) const { return m_state[i]; }
318
323 template<std::output_iterator<word_type> Dst>
324 constexpr void get_state(Dst dst) const {
325 m_state.get_state(dst);
326 }
327
331
346 template<std::integral T>
347 constexpr T sample(T a, T b) {
348 return std::uniform_int_distribution<T>{a, b}(*this);
349 }
350
365 template<std::floating_point T>
366 constexpr T sample(T a, T b) {
367 return std::uniform_real_distribution<T>{a, b}(*this);
368 }
369
384 template<std::integral T>
385 constexpr T index(T len) {
386 return sample(T{0}, len - 1);
387 }
388
405 template<std::input_iterator T>
406 constexpr auto sample(T b, T e) {
407 // Edge case?
408 auto len = std::distance(b, e);
409 if (len < 2) return *b;
410
411 // Pick an index inside the iteration at random & return the corresponding value.
412 auto i = index(len);
413 std::advance(b, i);
414 return *b;
415 }
416
435 template<typename Container>
436 requires std::ranges::input_range<const Container> && std::ranges::common_range<const Container>
437 constexpr auto sample(const Container& container) {
438 return sample(std::ranges::cbegin(container), std::ranges::cend(container));
439 }
440
463 template<std::input_iterator Src, std::output_iterator<std::iter_value_t<Src>> Dst>
464 constexpr Dst sample(Src b, Src e, Dst dst, std::size_t n) {
465 return std::sample(b, e, dst, n, *this);
466 }
467
492 template<typename Src, std::output_iterator<std::ranges::range_value_t<const Src>> Dst>
493 requires std::ranges::input_range<const Src> && std::ranges::common_range<const Src>
494 constexpr auto sample(const Src& src, Dst dst, std::size_t n) {
495 return sample(std::ranges::cbegin(src), std::ranges::cend(src), dst, n);
496 }
497
512 constexpr auto sample(Distribution auto& dist) { return dist(*this); }
513
533 template<typename Dst>
534 constexpr Dst sample(Distribution auto& dist, Dst dst, std::size_t n) {
535 while (n-- != 0) *dst++ = dist(*this);
536 return dst;
537 }
538
552 constexpr std::size_t roll(std::size_t n_sides = 6) { return sample(1uz, n_sides); }
553
565 constexpr bool flip(double p = 0.5) { return std::bernoulli_distribution{p}(*this); }
566
570
584 template<std::random_access_iterator Iter>
585 constexpr void shuffle(Iter b, Iter e) {
586 std::shuffle(b, e, *this);
587 }
588
602 template<typename Container>
603 requires std::ranges::random_access_range<Container> && std::ranges::common_range<Container>
604 constexpr void shuffle(Container& container) {
605 return shuffle(std::begin(container), std::end(container));
606 }
607
611
618 void discard(std::uint64_t z) {
619 for (std::uint64_t i = 0; i < z; ++i) step();
620 }
621
625
646 constexpr auto jump(std::size_t n, bool n_is_log2 = false) {
647 // Get the jump polynomial coefficients for this jump
648 auto jump_coeffs = xso::jump_coefficients<state_type>(n, n_is_log2);
649
650 // Perform the jump using those coefficients
651 jump(jump_coeffs);
652
653 // Return the jump polynomial coefficients to the caller for possible reuse later.
654 return jump_coeffs;
655 }
656
675 constexpr void jump(const array_type& jump_coefficients) {
676
677 // Constant
678 constexpr std::size_t bits_per_word = std::numeric_limits<word_type>::digits;
679
680 // lambda: `is_set(word, b)` returns true if bit `b` in `word` is set.
681 auto is_set = [=](const word_type word, std::size_t b) -> bool {
682 return word & static_cast<word_type>(word_type{1} << b);
683 };
684
685 // If the current state is `s` and the state's transition matrix is T then the jump we want is s <- (T^n).s.
686 // Cayley-Hamilton is invoked to equate T^n with a small polynomial sum r(T) where r(x) = x^n mod c(x)
687 // and c(x) is the characteristic polynomial for T. Thus (T^n).s == r(T).s which is doable.
688 //
689 // The `jump_coefficients` argument is assumed to have the coefficients of r(x) stored compactly in words.
690 // The next loop computes the sum r(T).s = r_0.s + r_1.s^1 + ... + r_{n-1} s^{n-1}.
691 // We compute s^{i+1} = T.s^i using the step() method (so s <- T.s <- (T^2).s by iteratively stepping s
692 // forward).
693 array_type sum;
694 sum.fill(0);
695 for (auto i = 0uz; i < word_count(); ++i) {
696
697 // Iterate over the bits in each coefficient word -- the bits are the coefficients of r(x).
698 word_type r_word = jump_coefficients[i];
699 for (auto b = 0uz; b < bits_per_word; ++b) {
700 if (is_set(r_word, b)) {
701 // This coefficient in r(x) is one, so contributes to the sum ...
702 for (auto w = 0uz; w < word_count(); ++w) sum[w] ^= m_state[w];
703 }
704 // Compute the next state s^{i+1} by calling the step() method (same as s <- T.s).
705 m_state.step();
706 }
707 }
708
709 // Store the computed jumped state back as our current state so we are ready to proceed from there ...
710 m_state.seed(sum.cbegin(), sum.cend());
711 }
712
731 template<std::output_iterator<word_type> Dst>
732 static constexpr void characteristic_coefficients(Dst dst) {
733 State::characteristic_coefficients(dst);
734 }
735
752 static constexpr auto characteristic_coefficients() {
753 array_type result;
754 State::characteristic_coefficients(result.begin());
755 return result;
756 }
757
758#ifdef GF2
759
763
767 void jump(gf2::BitPolynomial<word_type> const& jump_poly) {
768 array_type sum;
769
770 // Computing [r_0 + r_1 T + ... + r_{m-1} T^{m-1}].s where s is the current state and r is the jump polynomial.
771 // T is the state's transition matrix so we can compute s^{i+1} = T.s^i using the step() method.
772 sum.fill(0);
773 for (auto i = 0uz; i < jump_poly.size(); ++i) {
774 if (jump_poly[i])
775 for (std::size_t w = 0; w < word_count(); ++w) sum[w] ^= m_state[w];
776 m_state.step();
777 }
778
779 // Perform the computed jump by reseeding the state from the computed sum ...
780 m_state.seed(sum.cbegin(), sum.cend());
781 }
782#endif
784
785private:
786 State m_state;
787 Scrambler m_scrambler;
788
789 // Class method that is an implementation of the SplitMix64 random number generator -- a simple generator with 64
790 // bits of state.
791 //
792 // Used here to help seed our more complex generators from a single 64-bit seed value.
793 static constexpr std::uint64_t split_mix64(std::uint64_t& state) {
794 std::uint64_t z = (state += 0x9e3779b97f4a7c15);
795 z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9;
796 z = (z ^ (z >> 27)) * 0x94d049bb133111eb;
797 z = (z ^ (z >> 31));
798 return z;
799 };
800
801 // Class method that returns a 64-bit word that is a scrambled version of the input 64-bit value.
802 //
803 // This is based on the MurmurHash3 finalizer function.
804 static constexpr std::uint64_t murmur_scramble64(std::uint64_t x) {
805 x ^= x >> 33;
806 x *= 0xff51afd7ed558ccdL;
807 x ^= x >> 33;
808 x *= 0xc4ceb9fe1a85ec53L;
809 x ^= x >> 33;
810 return x;
811 }
812
813 // Class method that returns a 32-bit word that is a scrambled version of the input 32-bit value.
814 //
815 // This is based on the MurmurHash3 mix function.
816 static constexpr std::uint32_t murmur_scramble32(std::uint32_t x) {
817 x *= 0xcc9e2d51;
818 x = (x << 15) | (x >> 17);
819 x *= 0x1b873593;
820 return x;
821 }
822};
823
824// --------------------------------------------------------------------------------------------------------------------
825// The Xoshiro state:
826// --------------------------------------------------------------------------------------------------------------------
827
832template<std::size_t N, std::unsigned_integral T, std::uint8_t A, std::uint8_t B>
833class xoshiro {
834public:
836 using word_type = T;
837
839 using array_type = std::array<T, N>;
840
842 static constexpr std::size_t word_count() { return N; }
843
845 static constexpr std::size_t bit_count() { return N * std::numeric_limits<T>::digits; }
846
848 static constexpr auto type_string() {
849 return std::format("xoshiro<{}x{},{},{}>", N, std::numeric_limits<T>::digits, A, B);
850 }
851
853 constexpr T operator[](std::size_t i) const { return m_state[i]; }
854
859 template<std::output_iterator<word_type> Dst>
860 constexpr void get_state(Dst dst) const {
861 std::copy(m_state.cbegin(), m_state.cend(), dst);
862 }
863
869 template<std::input_iterator Src>
870 requires std::convertible_to<std::iter_value_t<Src>, word_type>
871 constexpr void seed(Src b, Src e) {
872 std::copy(b, e, m_state.begin());
873 }
874
881 constexpr void step() {
882 if constexpr (N == 4) {
883 auto tmp = m_state[1] << A;
884 m_state[2] ^= m_state[0];
885 m_state[3] ^= m_state[1];
886 m_state[1] ^= m_state[2];
887 m_state[0] ^= m_state[3];
888 m_state[2] ^= tmp;
889 m_state[3] = std::rotl(m_state[3], B);
890 } else if constexpr (N == 8) {
891 auto tmp = m_state[1] << A;
892 m_state[2] ^= m_state[0];
893 m_state[5] ^= m_state[1];
894 m_state[1] ^= m_state[2];
895 m_state[7] ^= m_state[3];
896 m_state[3] ^= m_state[4];
897 m_state[4] ^= m_state[5];
898 m_state[0] ^= m_state[6];
899 m_state[6] ^= m_state[7];
900 m_state[6] ^= tmp;
901 m_state[7] = std::rotl(m_state[7], B);
902 } else {
903 // Get a useful'ish error message by pumping a deliberately false condition into static_assert(...).
904 static_assert(N < 0, "No xoshiro step() implementation for this number of words of state!");
905 }
906 }
907
916 template<std::output_iterator<word_type> Dst>
917 static constexpr void characteristic_coefficients(Dst dst) {
918 // In practice we have precomputed the p(x) polynomial for just a few xoshiro's with specific parameters.
919 if constexpr (std::is_same_v<T, uint32_t> && N == 4 && A == 9 && B == 11) {
920 std::array<T, N> p = {0xde18fc01, 0x1b489db6, 0x6254b1, 0xfc65a2};
921 std::copy(p.cbegin(), p.cend(), dst);
922 } else if constexpr (std::is_same_v<T, uint64_t> && N == 4 && A == 17 && B == 45) {
923 std::array<T, N> p = {0x9d116f2bb0f0f001, 0x280002bcefd1a5e, 0x4b4edcf26259f85, 0x3c03c3f3ecb19};
924 std::copy(p.cbegin(), p.cend(), dst);
925 } else if constexpr (std::is_same_v<T, uint64_t> && N == 8 && A == 11 && B == 21) {
926 std::array<T, N> p = {0xcf3cff0c00000001, 0x7fdc78d886f00c63, 0xf05e63fca6d7b781, 0x7a67058e7bbab6f0,
927 0xf11eef832e32518f, 0x51ba7c47edc758ad, 0x8f2d27268ce4b20b, 0x500055d8b77f};
928 std::copy(p.cbegin(), p.cend(), dst);
929 } else {
930 throw std::invalid_argument("xoshiro characteristic polynomial not pre-computed for given parameters!");
931 }
932 }
933
943 static constexpr auto characteristic_coefficients() {
944 array_type result;
945 characteristic_coefficients(result.begin());
946 return result;
947 }
948
949private:
950 std::array<T, N> m_state = {1};
951};
952
953// --------------------------------------------------------------------------------------------------------------------
954// The Xoroshiro State:
955// --------------------------------------------------------------------------------------------------------------------
956
961template<std::size_t N, std::unsigned_integral T, std::uint8_t A, std::uint8_t B, std::uint8_t C>
963public:
965 using word_type = T;
966
968 using array_type = std::array<T, N>;
969
971 static constexpr std::size_t word_count() { return N; }
972
974 static constexpr std::size_t bit_count() { return N * std::numeric_limits<T>::digits; }
975
977 static constexpr auto type_string() {
978 return std::format("xoroshiro<{}x{},{},{},{}>", N, std::numeric_limits<T>::digits, A, B, C);
979 }
980
984 constexpr T operator[](std::size_t i) const { return m_state[(i + m_final + 1) % N]; }
985
992 template<std::output_iterator<word_type> Dst>
993 constexpr void get_state(Dst dst) const {
994 for (auto i = 0uz; i < N; ++i, ++dst) *dst = operator[](i);
995 }
996
1002 template<std::input_iterator Src>
1003 requires std::convertible_to<std::iter_value_t<Src>, word_type>
1004 constexpr void seed(Src b, Src e) {
1005 std::copy(b, e, m_state.begin());
1006
1007 // Reset the ring buffer final index
1008 m_final = N - 1;
1009 }
1010
1012 constexpr void step() {
1013 // Depending on the size of `N` we either do an explicit or implicit array shuffle of the state array.
1014 if constexpr (N == 2)
1015 simple_step();
1016 else
1017 clever_step();
1018 }
1019
1028 template<std::output_iterator<word_type> Dst>
1029 static constexpr void characteristic_coefficients(Dst dst) {
1030 if constexpr (std::is_same_v<T, uint32_t> && N == 2 && A == 26 && B == 9 && C == 13) {
1031 std::array<T, N> p = {0x6e2286c1, 0x53be9da};
1032 std::copy(p.cbegin(), p.cend(), dst);
1033 } else if constexpr (std::is_same_v<T, uint64_t> && N == 2 && A == 24 && B == 16 && C == 37) {
1034 std::array<T, N> p = {0x95b8f76579aa001, 0x8828e513b43d5};
1035 std::copy(p.cbegin(), p.cend(), dst);
1036 } else if constexpr (std::is_same_v<T, uint64_t> && N == 2 && A == 49 && B == 21 && C == 28) {
1037 std::array<T, N> p = {0x8dae70779760b081, 0x31bcf2f855d6e5};
1038 std::copy(p.cbegin(), p.cend(), dst);
1039 } else if constexpr (std::is_same_v<T, uint64_t> && N == 16 && A == 25 && B == 27 && C == 36) {
1040 std::array<T, N> p = {0x5cfeb8cc48ddb211, 0xb73e379d035a06dd, 0x17d5100a20a0350e, 0x7550223f68f98cac,
1041 0x29d373b5c5ed3459, 0x3689b412ef70de48, 0xa1d3b6ee079a7cc6, 0x9bf0b669abd100f8,
1042 0x955c84e105f60997, 0x6ca140c61889cddd, 0xabaf68c5fc3a0e4a, 0xa46134526b83adc5,
1043 0x710704d05683d63, 0x580d080b44b606a2, 0x8040a0580158a1, 0x800081};
1044 std::copy(p.cbegin(), p.cend(), dst);
1045 } else {
1046 throw std::invalid_argument("xoroshiro characteristic polynomial not pre-computed for given parameters!");
1047 }
1048 }
1049
1059 static constexpr auto characteristic_coefficients() {
1060 array_type result;
1061 characteristic_coefficients(result.begin());
1062 return result;
1063 }
1064
1065private:
1066 std::array<T, N> m_state = {1}; // The state is an array of words -- should never be all zeros!
1067 std::size_t m_final = N - 1; // Current location of the final word of state.
1068
1071 constexpr void simple_step() {
1072 // Capture the current values in the first and final words of state
1073 T s0 = m_state[0];
1074 T s1 = m_state[N - 1];
1075
1076 // Shift most of the words of state down one slot
1077 // Note: It could help to unroll this loop at least once for larger N but the shuffle indices method is
1078 // better
1079 for (auto i = 0uz; i < N - 2; ++i) m_state[i] = m_state[i + 1];
1080
1081 // Update the first and final words of state
1082 s1 ^= s0;
1083 m_state[N - 2] = std::rotl(s0, A) ^ (s1 << B) ^ s1;
1084 m_state[N - 1] = std::rotl(s1, C);
1085 }
1086
1089 constexpr void clever_step() {
1090 // Which indices point to the current final & first words of state
1091 std::size_t i_final = m_final;
1092 std::size_t i_first = (m_final + 1) % N;
1093
1094 // Capture the current values in the final & first words of state
1095 T s_final = m_state[i_final];
1096 T s_first = m_state[i_first];
1097
1098 // Update the values for the final & first words of state
1099 s_final ^= s_first;
1100 m_state[i_final] = std::rotl(s_first, A) ^ (s_final << B) ^ s_final;
1101 m_state[i_first] = std::rotl(s_final, C);
1102
1103 // Step the index of the final word of state -- this shuffles the state array down a slot.
1104 m_final = i_first;
1105 }
1106};
1107
1108// --------------------------------------------------------------------------------------------------------------------
1109// The Scramblers:
1110//
1111// A Scrambler is a functor that is passed a State and returns a single unsigned output word.
1112// --------------------------------------------------------------------------------------------------------------------
1113
1122template<auto S, std::size_t w = 0>
1123struct star {
1124 constexpr auto operator()(const auto& state) const { return S * state[w]; }
1125
1126 static constexpr auto type_string() { return std::format("star<{:x},{}>", S, w); }
1127};
1128
1139template<auto S, auto R, auto T, std::size_t w = 0>
1141 constexpr auto operator()(const auto& state) const { return T * std::rotl(S * state[w], R); }
1142
1143 static constexpr auto type_string() { return std::format("star_star<{:x},{},{:x},{}>", S, R, T, w); }
1144};
1145
1153template<std::size_t w0 = 0, std::size_t w1 = 1>
1154struct plus {
1155 constexpr auto operator()(const auto& state) const { return state[w0] + state[w1]; }
1156
1157 static constexpr auto type_string() { return std::format("plus<{},{}>", w0, w1); }
1158};
1159
1165template<auto R, std::size_t w0, std::size_t w1>
1167 constexpr auto operator()(const auto& state) const { return std::rotl(state[w0] + state[w1], R) + state[w0]; }
1168
1169 static constexpr auto type_string() { return std::format("plus_plus<{},{},{}>", R, w0, w1); }
1170};
1171
1172// --------------------------------------------------------------------------------------------------------------------
1173// Type aliases for all 17 generators discussed in the Black & Vigna paper
1174// --------------------------------------------------------------------------------------------------------------------
1175
1176// clang-format off
1177// The analysed versions of the xoshiro engine with specific choices for A & B:
1178using xoshiro_4x32 = xoshiro<4, uint32_t, 9, 11>;
1179using xoshiro_4x64 = xoshiro<4, uint64_t, 17, 45>;
1180using xoshiro_8x64 = xoshiro<8, uint64_t, 11, 21>;
1181
1182// The analysed versions of the xoshiro engine with specific choices for A, B & C:
1183using xoroshiro_2x32 = xoroshiro<2, uint32_t, 26, 9, 13>;
1184using xoroshiro_2x64 = xoroshiro<2, uint64_t, 24, 16, 37>;
1185using xoroshiro_2x64b = xoroshiro<2, uint64_t, 49, 21, 28>; // Alternative for 2x64 case
1186using xoroshiro_16x64 = xoroshiro<16, uint64_t, 25, 27, 36>;
1187
1188// The analyzed versions of the xoshiro generators:
1189using xoshiro_4x32_plus = generator<xoshiro_4x32, plus<0, 3>>;
1190using xoshiro_4x32_plus_plus = generator<xoshiro_4x32, plus_plus<7, 0, 3>>;
1191using xoshiro_4x32_star_star = generator<xoshiro_4x32, star_star<5, 7, 9, 1>>;
1192using xoshiro_4x64_plus = generator<xoshiro_4x64, plus<0, 3>>;
1193using xoshiro_4x64_plus_plus = generator<xoshiro_4x64, plus_plus<23, 0, 3>>;
1194using xoshiro_4x64_star_star = generator<xoshiro_4x64, star_star<5, 7, 9, 1>>;
1195using xoshiro_8x64_plus = generator<xoshiro_8x64, plus<2, 0>>;
1196using xoshiro_8x64_plus_plus = generator<xoshiro_8x64, plus_plus<17, 2, 0>>;
1197using xoshiro_8x64_star_star = generator<xoshiro_8x64, star_star<5, 7, 9, 1>>;
1198
1199// The analysed versions of the xoroshiro generators:
1200using xoroshiro_2x32_star = generator<xoroshiro_2x32, star<0x9E3779BB, 0>>;
1201using xoroshiro_2x32_star_star = generator<xoroshiro_2x32, star_star<0x9E3779BB, 5, 5, 0>>;
1202using xoroshiro_2x64_plus = generator<xoroshiro_2x64, plus<0, 1>>;
1203using xoroshiro_2x64_plus_plus = generator<xoroshiro_2x64b, plus_plus<17, 0, 1>>;
1204using xoroshiro_2x64_star_star = generator<xoroshiro_2x64, star_star<5, 7, 9, 0>>;
1205using xoroshiro_16x64_plus_plus = generator<xoroshiro_16x64, plus_plus<23, 15, 0>>;
1206using xoroshiro_16x64_star = generator<xoroshiro_16x64, star<0x9e3779b97f4a7c13, 0>>;
1207using xoroshiro_16x64_star_star = generator<xoroshiro_16x64, star_star<5, 7, 9, 0>>;
1208// clang-format on
1209
1211using rng32 = xoshiro_4x32_star_star;
1212
1214using rng64 = xoshiro_4x64_star_star;
1215
1217using rng = rng64;
1218
1219// --------------------------------------------------------------------------------------------------------------------
1220// Partitions of random number stream:
1221//
1222// For parallel processing applications it can be useful to split a single random number stream into a number of
1223// non-overlapping "partitions". Then different computational threads can get their "own set" of random numbers without
1224// worrying about stream overlaps etc.
1225//
1226// The partitions need to be very large so this only works for States where we can jump far ahead in an efficient way.
1227// --------------------------------------------------------------------------------------------------------------------
1228
1236template<typename RNG>
1238public:
1247 partition(const RNG& for_rng, std::size_t n_partitions) : m_rng{for_rng} {
1248 // Make sure the requested number of partitions makes sense -- silently fix any issues.
1249 if (n_partitions == 0) n_partitions = 1;
1250
1251 // How many bits of state in the RNG type?
1252 auto n_bits = RNG::bit_count();
1253
1254 // The period of the generator is `2^n_bits` so each partition ideally has size `2^n_bits / n_partitions`.
1255 // That number will probably overflow a std::size_t so we must instead keep everything in log 2 form.
1256 // First we find the smallest `n` such that `2^n >= n_partitions - 1`.
1257 // Note if `n_partitions` is 128 the following gives `n = 7` and does the same if `n = 100`.
1258 auto n = static_cast<std::size_t>(std::bit_width(n_partitions - 1));
1259
1260 // We will create `2^n` partitions which is probably more than needed but the wastage is negligible.
1261 // To create those `2^n` partitions we must be able to jump ahead `2^(n_bits - n)` steps many times.
1262 auto power_2 = n_bits - n;
1263
1264 // Precompute the jump coefficients to advance the generator `2^power_2` steps i.e. along to the next partition.
1265 m_jump_coefficients = xso::jump_coefficients<typename RNG::state_type>(power_2, true);
1266 }
1267
1270 RNG next() {
1271 // We already have a pre-baked generator seeded at the right spot ready to go.
1272 RNG result = m_rng;
1273
1274 // Prep for the next call by jumping the parent copy once more along its stream.
1275 m_rng.jump(m_jump_coefficients);
1276
1277 // And return the pre-baked one ...
1278 return result;
1279 }
1280
1281private:
1282 using array_type = typename RNG::array_type;
1283
1284 RNG m_rng;
1285 array_type m_jump_coefficients;
1286};
1287
1288// --------------------------------------------------------------------------------------------------------------------
1289// Non-member functions for computing jump polynomials:
1290// --------------------------------------------------------------------------------------------------------------------
1291
1305template<typename State>
1306constexpr auto
1307jump_coefficients(std::size_t n, bool n_is_log2) {
1308
1309 // Retrieve the low order coefficients of characteristic polynomial --- this can throw if not precomputed.
1310 std::array<typename State::word_type, State::word_count()> char_coefficients;
1311 State::characteristic_coefficients(char_coefficients.begin());
1312
1313 // The jump polynomial is x^J mod c(x) -- that computation expects to be handed p(x) where c(x) = x^n + p(x).
1314 return xso::reduce(char_coefficients, n, n_is_log2);
1315}
1316
1317// --------------------------------------------------------------------------------------------------------------------
1318// We have some "internal" functions that reduce x^J mod c(x) --- needed for the jump polynomial computations.
1319// These re-implement a more general reduction method in the gf2::BitPolynomial class (https://nessan/github.io/gf2/).
1320// Repeated here to make `xoshiro.h` self-contained.
1321//
1322// Not part of the public API but used for the jump calculations in the generator class.
1323// --------------------------------------------------------------------------------------------------------------------
1324
1325// Function to "riffle" a `src` word into two other words `lo` and `hi` containing the bits from `src`
1326// interleaved with zeros.
1327//
1328// So the 8-bit word `abcdefgh` fills `lo` as `a0b0c0d0` and `hi` as `e0f0g0h0`.
1329//
1330// # Example
1331// ```
1332// std::uint8_t src = 0b1111'1111;
1333// std::uint8_t lo, hi;
1334// xso::riffle(src, lo, hi);
1335// assert_eq(lo, 0b01010101, "lo is {:08b}", lo);
1336// assert_eq(hi, 0b01010101, "hi is {:08b}", hi);
1337// ```
1338// *NOTE:** This function is "public" for testing purposes only -- it is not part of the normal interface.
1339template<std::unsigned_integral word_type>
1340constexpr void
1341riffle(word_type src, word_type& lo, word_type& hi) {
1342 // Constants
1343 constexpr std::size_t bits_per_word = std::numeric_limits<word_type>::digits;
1344 constexpr std::size_t half_bits = bits_per_word / 2;
1345 constexpr word_type one{1};
1346 constexpr word_type ones = std::numeric_limits<word_type>::max();
1347
1348 // Split the src into lo and hi halves.
1349 lo = src & (ones >> half_bits);
1350 hi = src >> half_bits;
1351
1352 // Some magic to interleave the respective halves with zeros.
1353 for (auto i = bits_per_word / 4; i > 0; i /= 2) {
1354 word_type div = word_type(one << i) | one;
1355 word_type msk = ones / div;
1356 lo = (lo ^ (lo << i)) & msk;
1357 hi = (hi ^ (hi << i)) & msk;
1358 }
1359}
1360
1361// Function that riffles a `src` array of unsigneds into two others `lo` and `hi` which will be filled with the
1362// bits from `src` interleaved with zeros.
1363//
1364// We treat `lo` and `hi` as contiguous storage and fill the elements of `lo` first and then `hi`.
1365// This allows us to optionally reuse `src` for the output array `lo` -- the call `riffle(src, src, hi)` will work.
1366//
1367// # Example
1368// ```
1369// std::array<std::uint8_t, 2> src = {0b1111'1111, 0b1111'1111};
1370// std::array<std::uint8_t, 2> lo, hi;
1371// xso::riffle(src, lo, hi);
1372// assert_eq(lo, (std::array<std::uint8_t, 2>{0b01010101, 0b01010101}));
1373// assert_eq(hi, (std::array<std::uint8_t, 2>{0b01010101, 0b01010101}));
1374// ```
1375// *NOTE:** This function is "public" for testing purposes only -- it is not part of the normal interface.
1376template<std::unsigned_integral word_type, std::size_t N>
1377static constexpr void
1378riffle(const std::array<word_type, N>& src, std::array<word_type, N>& lo, std::array<word_type, N>& hi) {
1379 // We will riffle each word in src into two other words x & y
1380 word_type x, y;
1381
1382 // We work through `src` in reverse order -- this allows the reuse of `src` for `lo`!
1383 // Treating [lo|hi] as contiguous storage, first working back through hi and then back through lo.
1384 for (std::size_t i = N; i-- > 0;) {
1385 riffle(src[i], x, y);
1386 if (2 * i + 1 > N) {
1387 // Both x & y go in hi -- note that if 2i + 1 - N > 0 then 2i - N is >= 0.
1388 hi[2 * i - N] = x;
1389 hi[2 * i + 1 - N] = y;
1390 } else if (2 * i + 1 == N) {
1391 // Straddling situation where y goes in the first word of hi and x in the last word of lo.
1392 lo[N - 1] = x;
1393 hi[0] = y;
1394 } else {
1395 // Need to pop both x & y into the lo array.
1396 lo[2 * i] = x;
1397 lo[2 * i + 1] = y;
1398 }
1399 }
1400}
1401
1402// Function that computes r(x) = x^e mod c(x) in GF(2) where e = J or 2^J and J is an unsigned integer argument.
1403//
1404// The polynomial c(x) is monic of degree n so c(x) = x^n + p(x) where p(x) is a polynomial of degree less than n.
1405// We are passed the n coefficients of p(x) packed into an array of unsigned integers.
1406// We return the coefficients of r(x) = x^e mod c(x) packed into an array of unsigned integers in the same format.
1407//
1408// # Note
1409// Any linting tool you use will (reasonably) complain that the complexity of this method is too high!
1410// The method is a direct re-implementation of the `gf2::BitPolynomial::reduce` method which is also complex but
1411// easier to understand as it is properly factored. The version here is is less general as it assumes that the
1412// degree of p(x) is a multiple of 32.
1413//
1414// *NOTE:** This method "public" for testing purposes only -- it is not part of the normal interface.
1415template<std::unsigned_integral word_type, std::size_t N>
1416constexpr auto
1417reduce(const std::array<word_type, N>& p, std::size_t J, bool J_is_log2) {
1418
1419 // We will return the coefficients of r(x) = x^e mod c(x) packed into an array of unsigned integers of this type.
1420 using array_type = std::array<word_type, N>;
1421
1422 // Constant we use to indicate "no such position"/"not found" and a couple of others.
1423 constexpr auto npos = static_cast<std::size_t>(-1);
1424 constexpr word_type one{1};
1425
1426 // The polynomial c(x) = x^n + p(x) where p(x) = p_0 + p_1 x + ... + p_{n-1} x^{n-1} and n is:
1427 constexpr std::size_t bits_per_word = std::numeric_limits<word_type>::digits;
1428 constexpr std::size_t n = N * bits_per_word;
1429
1430 // lambda: Returns the index of the word that holds p_i.
1431 auto word = [=](std::size_t i) { return i / bits_per_word; };
1432
1433 // lambda: Returns the bit location of p_i inside the word that holds it.
1434 auto bit = [=](std::size_t i) { return i % bits_per_word; };
1435
1436 // lambda: Returns a mask that isolates p_i within the word that holds it.
1437 auto mask = [=](std::size_t i) { return word_type{one << bit(i)}; };
1438
1439 // lambda: Returns true if poly_i is 1.
1440 auto test = [=](const auto& poly, std::size_t i) -> bool { return poly[word(i)] & mask(i); };
1441
1442 // lambda: Sets poly_i to 1.
1443 auto set = [=](auto& poly, std::size_t i) { poly[word(i)] |= mask(i); };
1444
1445 // lambda: Returns the index for the least significant set bit in the argument or `npos` if none set.
1446 auto lsb = [=](word_type w) { return w == 0 ? npos : static_cast<std::size_t>(std::countr_zero(w)); };
1447
1448 // lambda: Returns the index for the most significant set bit in the argument or `npos` if none set.
1449 auto msb = [=](word_type w) { return static_cast<std::size_t>(std::bit_width(w) - 1); };
1450
1451 // lambda: Returns the first set coefficient in poly or `npos` if the coefficients are all zero.
1452 auto first_set = [=](const auto& poly) {
1453 for (auto i = 0uz; i < N; ++i)
1454 if (poly[i] != 0) return i * bits_per_word + lsb(poly[i]);
1455 return npos;
1456 };
1457
1458 // lambda: Returns the final set coefficient in poly or `npos` if the coefficients are all zero.
1459 auto final_set = [=](const auto& poly) {
1460 std::size_t i = N;
1461 while (i--)
1462 if (poly[i] != 0) return i * bits_per_word + msb(poly[i]);
1463 return npos;
1464 };
1465
1466 // lambda: Returns true if the highest coefficient in `poly` is set (then poly is said to be monic).
1467 auto monic = [=](const auto& poly) {
1468 constexpr std::size_t complement = bits_per_word - 1;
1469 constexpr auto final_bit_mask = word_type{one << complement};
1470 return poly[N - 1] & final_bit_mask;
1471 };
1472
1473 // lambda: Computes lhs <- lhs + rhs which in GF(2) is equivalent to lhs <- lhs^rhs.
1474 auto add = [=](auto& lhs, const auto& rhs) {
1475 for (auto i = 0uz; i < N; ++i) lhs[i] ^= rhs[i];
1476 };
1477
1478 // lambda: Performs a one place shift on the polynomial coefficients stored poly.
1479 // Shift is to the the right if you think the elements are in vector order [p0,p1,p2,p3] -> [0,p0,p1,p2].
1480 // Shift is to the left when you think in bit order [b3,b2,b1,b0] -> [b2,b1,b0,0].
1481 auto shift = [=](auto& poly) {
1482 constexpr std::size_t complement = bits_per_word - 1;
1483 for (std::size_t i = N - 1; i > 0; --i) {
1484 auto l = static_cast<word_type>(poly[i] << 1);
1485 auto r = static_cast<word_type>(poly[i - 1] >> complement);
1486 poly[i] = l | r;
1487 }
1488 poly[0] <<= 1;
1489 };
1490
1491 // lambda: If degree[poly] < n, this performs poly(x) <- x*poly(x) mod c(x) where c(x) = x^n + p(x).
1492 auto times_x_step = [&](auto& poly) {
1493 bool add_p = monic(poly);
1494 shift(poly);
1495 if (add_p) add(poly, p);
1496 };
1497
1498 // We precompute x^{n + i} mod c(x) for i = 0, ..., n-1 starting from the known x^n mod c(x) = p.
1499 // Each x^{n + i} mod c(x) is a word-vector of coefficients and we put the lot into a std::vector.
1500 std::vector<array_type> power_mod(n);
1501 power_mod[0] = p;
1502 for (std::size_t i = 1; i < n; ++i) {
1503 power_mod[i] = power_mod[i - 1];
1504 times_x_step(power_mod[i]);
1505 }
1506
1507 // Some work space we use below.
1508 array_type hi;
1509
1510 // lambda: If degree[poly] < n, performs: poly(x) <- poly(x)^2 mod c(x) where as usual c(x) = x^n + p(x).
1511 auto square_step = [&](auto& poly) {
1512 // Compute poly(x)^2 -- in GF(2) this means interspersing all the coefficients with zeros.
1513 // We actually riffle poly directly into two arrays lo & hi so that poly(x)^2 = lo(x) + x^n hi(x).
1514 // This only works because we assume n some multiple of N (i.e. all bits in poly matter).
1515 // NOTE: Our riffle method above for arrays lets us reuse the poly array for lo.
1516 riffle(poly, poly, hi);
1517
1518 // poly(x)^2 mod c(x) now is poly(x) + x^n hi(x) mod c(x) as degree[poly] < n.
1519 // Add the x^n hi(x) mod c(x) term-by-term noting that at most every second term in hi(x) is 1.
1520 auto hi_first = first_set(hi);
1521 if (hi_first != npos) {
1522 auto hi_final = final_set(hi);
1523 for (std::size_t i = hi_first; i <= hi_final; i += 2)
1524 if (test(hi, i)) add(poly, power_mod[i]);
1525 }
1526 };
1527
1528 // Initialize our return value to all zeros.
1529 array_type result;
1530 result.fill(0);
1531
1532 // Case: e = 2^J -- we just do J squaring steps starting from r(x) = x to get to x^(2^J) mod c(x).
1533 if (J_is_log2) {
1534 set(result, 1);
1535 for (std::size_t j = 0; j < J; ++j) square_step(result);
1536 return result;
1537 }
1538
1539 // Case e = J < n: Then x^J mod c(x) = x^J so we can set the appropriate coefficient in r and return.
1540 if (J < n) {
1541 set(result, J);
1542 return result;
1543 }
1544
1545 // Case e = J = n: Then x^J mod c(x) = p(x).
1546 if (J == n) return p;
1547
1548 // Case e = J > n: We use a square & multiply algorithm:
1549 // Note that if e.g. J = 0b00010111 then std::bit_floor(J) = 0b00010000.
1550 std::size_t J_bit = std::bit_floor(J);
1551
1552 // Start with r(x) = x mod c(x) which takes care of the most significant binary digit in J.
1553 set(result, 1);
1554 J_bit >>= 1;
1555
1556 // And off we go ...
1557 while (J_bit) {
1558
1559 // Always do a square step and then a times_x step if necessary (i.e. if current bit in J is set).
1560 square_step(result);
1561 if (J & J_bit) times_x_step(result);
1562
1563 // On to the next bit position in n.
1564 J_bit >>= 1;
1565 }
1566 return result;
1567}
1568
1569#ifdef GF2
1570
1571// --------------------------------------------------------------------------------------------------------------------
1572// Non-member functions that are only defined if we have access to the `gf2` library.
1573// See https://nessan.github.io/gf2/ for tools for working with polynomials and matrices over GF(2).
1574// --------------------------------------------------------------------------------------------------------------------
1575
1585template<typename State>
1586auto
1588
1589 using word_type = typename State::word_type;
1590
1591 // Some constants for our state size.
1592 constexpr auto n_words = State::word_count();
1593 constexpr auto n_bits = State::bit_count();
1594
1595 // The transition matrix will be a square n_bits x n_bits matrix over GF(2).
1596 gf2::BitMatrix<word_type> result{n_bits, n_bits};
1597
1598 // Some work-space in word and bit space
1599 gf2::BitVector<word_type> bits{n_bits};
1600 std::array<word_type, n_words> words;
1601
1602 // Create an State instance we will use to step through unit states.
1603 State state;
1604
1605 // We get the columns of the transition matrix by looking at the action of `step()` on all the unit states.
1606 for (std::size_t k = 0; k < n_bits; ++k) {
1607
1608 // Create the k'th unit state (i.e. the state just has the k'th bit set and all others are zero)
1609 bits.set_all(false);
1610 bits.set(k, true);
1611
1612 // Translate that unit bit-vector into an array of words.
1613 bits.to_words(words.begin());
1614
1615 // Seed the state from those words.
1616 state.seed(words.cbegin(), words.cend());
1617
1618 // Advance the state by one step.
1619 state.step();
1620
1621 // Translate the new state to bit-space.
1622 for (auto i = 0uz; i < n_words; ++i) bits.set_word(i, state[i]);
1623
1624 // Store those bits into column `k` of the transition matrix.
1625 // NOTE: Columnar access for a gf2::BitMatrix must be done element by element.
1626 for (auto i = 0uz; i < n_bits; ++i) result(i, k) = bits[i];
1627 }
1628
1629 return result;
1630}
1631
1636template<typename State>
1637auto
1640 return T.characteristic_polynomial();
1641}
1642
1650template<typename State>
1651auto
1652jump_polynomial(gf2::BitPolynomial<typename State::word_type> const& c, std::size_t N, bool N_is_log2 = false) {
1653 return c.reduce_x_to_the(N, N_is_log2);
1654}
1655
1656#endif
1657
1658} // namespace xso
1659
1660// --------------------------------------------------------------------------------------------------------------------
1661// Formatting and output stream support for our generators:
1662// --------------------------------------------------------------------------------------------------------------------
1663
1664// A concept that matches any type that has an accessible `type_string()` class `method.
1665template<typename T>
1666concept has_type_string_class_method = requires {
1667 { T::type_string() } -> std::convertible_to<std::string>;
1668};
1669
1673template<has_type_string_class_method T>
1674struct std::formatter<T> {
1675
1677 constexpr auto parse(const std::format_parse_context& ctx) {
1678 auto it = ctx.begin();
1679 assert(it == ctx.end() || *it == '}');
1680 return it;
1681 }
1682
1684 template<class FormatContext>
1685 auto format(const T&, FormatContext& ctx) const {
1686 return std::format_to(ctx.out(), "{}", T::type_string());
1687 }
1688};
1689
1693template<has_type_string_class_method T>
1694std::ostream&
1695operator<<(std::ostream& s, const T&) {
1696 s << T::type_string();
1697 return s;
1698}
A pseudorandom number generator combining a State and a Scrambler.
Definition xoshiro.h:69
static constexpr auto type_string()
Class method that returns a name for this type of generator — combining State and Scrambler names.
Definition xoshiro.h:114
static constexpr result_type max() noexcept
Returns the largest value this generator can produce.
Definition xoshiro.h:149
constexpr word_type operator[](std::size_t i) const
Returns the i'th state word.
Definition xoshiro.h:317
constexpr void jump(const array_type &jump_coefficients)
Efficiently jumps the generator's state forward by J steps where J can be huge (e....
Definition xoshiro.h:675
void seed()
Seeds the full state to random starting values using a combination of std::random_device and a high r...
Definition xoshiro.h:220
typename State::array_type array_type
A convenience container type to hold the full state of this generator, jump polynomial coefficients,...
Definition xoshiro.h:84
constexpr void step()
Advances the state by one step.
Definition xoshiro.h:298
static constexpr result_type min() noexcept
Returns the smallest value this generator can produce.
Definition xoshiro.h:138
State state_type
The State used for by generator type – one of the two state classes defined below.
Definition xoshiro.h:75
constexpr bool flip(double p=0.5)
Sampling method that flips a coin, where the probability of getting true is p (defaults to 0....
Definition xoshiro.h:565
constexpr std::size_t roll(std::size_t n_sides=6)
Sampling method that rolls a dice with an arbitrary number of sides (defaults to the usual 6).
Definition xoshiro.h:552
constexpr void seed(Src b, Src e)
Seeds the generator from an iteration of unsigned words which are all copied into the state.
Definition xoshiro.h:289
constexpr Dst sample(Src b, Src e, Dst dst, std::size_t n)
Sampling method that picks n elements without replacement from an iteration [b, e) and puts them in d...
Definition xoshiro.h:464
constexpr void shuffle(Container &container)
This method shuffles all the elements of a container.
Definition xoshiro.h:604
static constexpr std::size_t word_count()
Class method that returns the number of words of state for this type of generator.
Definition xoshiro.h:92
constexpr Dst sample(Distribution auto &dist, Dst dst, std::size_t n)
Sampling method that takes n samples from a distribution and puts them into a destination iterator.
Definition xoshiro.h:534
constexpr void seed(word_type seed)
Seeds the generator quickly but probably not well from a single unsigned integer value.
Definition xoshiro.h:258
constexpr auto sample(const Src &src, Dst dst, std::size_t n)
Sampling method that picks n elements without replacement from a container and puts them in dst.
Definition xoshiro.h:494
generator()
The default constructor seeds the full underlying state randomly using a combination of std::random_d...
Definition xoshiro.h:165
static constexpr std::size_t bit_count()
Class method that returns the number of bits of state for this type of generator.
Definition xoshiro.h:100
static constexpr auto characteristic_coefficients()
Class method that returns the state's precomputed characteristic polynomial coefficients packed into ...
Definition xoshiro.h:752
void discard(std::uint64_t z)
Discards the next z iterations in the random number sequence.
Definition xoshiro.h:618
constexpr T index(T len)
Sampling method that returns a single index from a uniform distribution over [0, len-1].
Definition xoshiro.h:385
constexpr generator(word_type s)
Construct a generator quickly but not well from a single unsigned integer value.
Definition xoshiro.h:177
constexpr result_type operator()()
Returns the next random value from the generator which is a result_type unsigned integer.
Definition xoshiro.h:306
constexpr generator(Iter b, Iter e)
Construct and seed from an iteration of unsigned words which are all copied into the state.
Definition xoshiro.h:198
typename State::word_type word_type
This generator type packs its state into words of this type (in practice, 32 or 64 bit unsigneds).
Definition xoshiro.h:81
constexpr auto jump(std::size_t n, bool n_is_log2=false)
Jumps the generator's state forward by J steps where J is either n or 2^n to accommodate huge jumps t...
Definition xoshiro.h:646
Scrambler scrambler_type
The Scrambler used for by generator type – one of the scrambler classes defined below.
Definition xoshiro.h:78
constexpr T sample(T a, T b)
Sampling method that returns a single integer value from a uniform distribution over [a,...
Definition xoshiro.h:347
constexpr auto sample(Distribution auto &dist)
Sampling method that returns a single random variate drawn from a distribution.
Definition xoshiro.h:512
static constexpr void characteristic_coefficients(Dst dst)
Class method that fills a destination iterator with the state's precomputed characteristic polynomial...
Definition xoshiro.h:732
constexpr void get_state(Dst dst) const
Copies the whole state into the destination iterator dst.
Definition xoshiro.h:324
constexpr void shuffle(Iter b, Iter e)
This method shuffles the elements in an iteration.
Definition xoshiro.h:585
constexpr auto sample(T b, T e)
Sampling method that returns a single value from an iteration – all elements are equally likely to be...
Definition xoshiro.h:406
constexpr auto sample(const Container &container)
Sampling method that returns a single value from a container – all elements are equally likely to be ...
Definition xoshiro.h:437
word_type result_type
The unsigned integer type returned by the generator's operator()() method.
Definition xoshiro.h:127
void jump(gf2::BitPolynomial< word_type > const &jump_poly)
Jumps a state/generator ahead in its random number stream by J steps.
Definition xoshiro.h:767
partition(const RNG &for_rng, std::size_t n_partitions)
Constructs a partition for the passed parent random number generator rng.
Definition xoshiro.h:1247
RNG next()
Returns the next generator that is seeded at the start of the next sub-stream of the parent random nu...
Definition xoshiro.h:1270
The state for the Xoroshiro family of pseudorandom number generators.
Definition xoshiro.h:962
static constexpr auto type_string()
Class method that returns a name for this state.
Definition xoshiro.h:977
constexpr void get_state(Dst dst) const
Copies the whole state into the destination iterator dst.
Definition xoshiro.h:993
constexpr void step()
Advance the state by one step.
Definition xoshiro.h:1012
T word_type
The type of the words of state.
Definition xoshiro.h:965
constexpr T operator[](std::size_t i) const
Returns the i'th state word.
Definition xoshiro.h:984
static constexpr std::size_t bit_count()
Class method that returns the number of bits of state.
Definition xoshiro.h:974
static constexpr auto characteristic_coefficients()
Class method that returns the state's precomputed characteristic polynomial coefficients packed into ...
Definition xoshiro.h:1059
static constexpr std::size_t word_count()
Class method that returns the number of words in the underlying state.
Definition xoshiro.h:971
constexpr void seed(Src b, Src e)
Sets the state from an iteration of words.
Definition xoshiro.h:1004
static constexpr void characteristic_coefficients(Dst dst)
Class method that fills a destination iterator with our precomputed characteristic polynomial coeffic...
Definition xoshiro.h:1029
std::array< T, N > array_type
A convenience container type to hold the full state of this generator, jump polynomial coefficients,...
Definition xoshiro.h:968
The state for the Xoshiro family of pseudorandom number generators.
Definition xoshiro.h:833
constexpr T operator[](std::size_t i) const
Returns the i'th state word.
Definition xoshiro.h:853
constexpr void step()
Advance the state by one step.
Definition xoshiro.h:881
static constexpr auto characteristic_coefficients()
Class method that returns the state's precomputed characteristic polynomial coefficients packed into ...
Definition xoshiro.h:943
static constexpr std::size_t word_count()
Class method that returns the number of words in the underlying state.
Definition xoshiro.h:842
static constexpr std::size_t bit_count()
Class method that returns the number of bits of state.
Definition xoshiro.h:845
T word_type
The state is stored as an array of N words of type T.
Definition xoshiro.h:836
static constexpr void characteristic_coefficients(Dst dst)
Class method that fills a destination iterator with our precomputed characteristic polynomial coeffic...
Definition xoshiro.h:917
std::array< T, N > array_type
A convenience container type to hold the full state of this generator, jump polynomial coefficients,...
Definition xoshiro.h:839
static constexpr auto type_string()
Class method that returns a name for this type of state.
Definition xoshiro.h:848
constexpr void get_state(Dst dst) const
Copies the whole state into the destination iterator dst.
Definition xoshiro.h:860
constexpr void seed(Src b, Src e)
Sets the state from an iteration of words.
Definition xoshiro.h:871
A C++ concept that lets us distinguish standard distribution types from other types.
Definition xoshiro.h:46
auto format(const T &, FormatContext &ctx) const
Push out a formatted xso::generator using its type_string() method.
Definition xoshiro.h:1685
constexpr auto parse(const std::format_parse_context &ctx)
Parse the format specifier – currently only handle the default empty specifier.
Definition xoshiro.h:1677
The plus_plus scrambler is passed a state array an returns rotl(state[w0] + state[w1],...
Definition xoshiro.h:1166
The plus scrambler is passed a state array an returns state[w0] + state[w1].
Definition xoshiro.h:1154
The star_star scrambler is passed a state array an returns T * rotl(S * state[w], R) where:
Definition xoshiro.h:1140
The star scrambler is passed a state array and will return S * state[w] where:
Definition xoshiro.h:1123
auto transition_matrix()
Returns the transition matrix for a state/generator type as a gf2::BitMatrix.
Definition xoshiro.h:1587
xoshiro_4x32_star_star rng32
The recommended 32-bit output generator – used as xso::rng32.
Definition xoshiro.h:1211
std::ostream & operator<<(std::ostream &s, const T &)
The usual output stream operator for an xso::generator, State, or Scrambler.
Definition xoshiro.h:1695
rng64 rng
The recommended default generator for most usage – used as xso::rng.
Definition xoshiro.h:1217
constexpr auto jump_coefficients(std::size_t J, bool J_is_log2=false)
Returns the coefficients of the jump polynomial that can be used to jump a generator/state ahead by ...
Definition xoshiro.h:1307
xoshiro_4x64_star_star rng64
The recommended 64-bit output generator – used as xso::rng64.
Definition xoshiro.h:1214
auto characteristic_polynomial()
Returns the characteristic polynomial for our state's transition matrix as a gf2::BitPolynomial.
Definition xoshiro.h:1638
auto jump_polynomial(gf2::BitPolynomial< typename State::word_type > const &c, std::size_t N, bool N_is_log2=false)
Returns a jump polynomial that moves the generator type J steps ahead in its random number stream.
Definition xoshiro.h:1652