C(++)ECCO
C++ Error Control COding: a header-only library for ECC simulations and experiments, modeling complete coding systems across arbitrary finite fields and complex inter-field relationships - Christian Senger <senger@inue.uni-stuttgart.de>
Loading...
Searching...
No Matches
helpers.hpp
Go to the documentation of this file.
1/**
2 * @file helpers.hpp
3 * @brief Utility functions and mathematical helpers
4 * @author Christian Senger <senger@inue.uni-stuttgart.de>
5 * @version 2.2.2
6 * @date 2026
7 *
8 * @copyright
9 * Copyright (c) 2026, Christian Senger <senger@inue.uni-stuttgart.de>
10 *
11 * Licensed for noncommercial use only, including academic teaching, research, and personal non-profit purposes.
12 * Commercial use is prohibited without a separate commercial license. See the [LICENSE](../../LICENSE) file in the
13 * repository root for full terms and how to request a commercial license.
14 *
15 * @section Description
16 *
17 * This header collects small utilities used by the algebraic types: random number generation,
18 * integer arithmetic, square-and-multiply exponentiation, double-and-add multiplication,
19 * caching, maxima, constexpr floor, and divisibility tests.
20 */
21
22#ifndef HELPERS_HPP
23#define HELPERS_HPP
24
25#include <algorithm>
26#include <atomic>
27#include <cmath>
28#include <cstdint>
29#include <functional>
30#include <limits>
31#include <mutex>
32#include <new>
33#include <optional>
34#include <random>
35#include <stdexcept>
36#include <string>
37#include <thread>
38#include <tuple>
39#include <type_traits>
40#include <utility>
41#include <vector>
42
43#include "InfInt.hpp"
44
45namespace CECCO {
46
47/**
48 * @brief Thread-local random number generator with shared seeding policy
49 *
50 * Provides one `std::mt19937` engine per thread. `seed()` selects deterministic seeding;
51 * `use_hardware_seed()` returns to seeding from `std::random_device`. A seed change is observed
52 * on the next call to @ref get in each thread.
53 *
54 * @note Use the static interface; the class has no object state.
55 */
56class RNG {
57 public:
58 /**
59 * @brief Get thread-local random number generator
60 * @return Reference to thread-local std::mt19937 generator
61 *
62 * Initializes the engine on first access. If the global seed generation changed since
63 * the previous access in this thread, reseeds before returning.
64 */
65 static std::mt19937& get() {
66 static thread_local std::mt19937 generator{get_initial_seed()};
67 if (should_reseed()) generator.seed(get_current_seed());
68 return generator;
69 }
70
71 /**
72 * @brief Set deterministic seed for all threads
73 * @param seed Base seed value (combined with a per-thread registration index)
74 *
75 * Selects deterministic seeding. Each thread derives its seed from @p seed and an index
76 * assigned on the thread's first use of the generator; the first thread (index 0) uses
77 * @p seed unchanged. Single-threaded runs are therefore fully reproducible. In
78 * multithreaded runs the set of streams is fixed, but their assignment to threads follows
79 * first-use order, which scheduling may permute across runs.
80 */
81 static void seed(uint32_t seed) {
82 use_deterministic_seed.store(true);
83 deterministic_seed_value.store(seed);
84 reseed_generation.fetch_add(1); // Signal all threads to reseed
85 }
86
87 /**
88 * @brief Enable hardware-based random seeding
89 *
90 * Selects seeding from `std::random_device`.
91 */
92 static void use_hardware_seed() {
93 use_deterministic_seed.store(false);
94 reseed_generation.fetch_add(1); // Signal all threads to reseed
95 }
96
97 private:
98 static inline std::atomic<bool> use_deterministic_seed{false};
99 static inline std::atomic<uint32_t> deterministic_seed_value{0};
100 static inline std::atomic<uint32_t> reseed_generation{0};
101
102 static uint32_t get_initial_seed() {
103 if (use_deterministic_seed.load()) {
104 // Weyl increment (2^32 / golden ratio) decorrelates the per-thread seeds
105 return deterministic_seed_value.load() + 0x9e3779b9u * thread_index();
106 } else {
107 static thread_local std::random_device rd;
108 return rd();
109 }
110 }
111
112 static uint32_t thread_index() {
113 static std::atomic<uint32_t> count{0};
114 static thread_local const uint32_t index = count.fetch_add(1);
115 return index;
116 }
117
118 static uint32_t get_current_seed() { return get_initial_seed(); }
119
120 static bool should_reseed() {
121 static thread_local uint32_t last_seen_generation = 0;
122 uint32_t current_generation = reseed_generation.load();
123 if (current_generation != last_seen_generation) {
124 last_seen_generation = current_generation;
125 return true;
126 }
127 return false;
128 }
129};
130
131/**
132 * @brief Current thread's random number generator
133 * @return Reference to thread-local random number generator
134 *
135 * Equivalent to @ref RNG::get.
136 */
137inline std::mt19937& gen() { return RNG::get(); }
138
139/**
140 * @brief Indices of all maximum elements
141 * @tparam T Element type (must support operator< for comparison)
142 * @param v Input vector
143 * @return Indices i with `v[i] == max(v)`; empty if @p v is empty
144 *
145 * Uses two passes over @p v.
146 */
147template <class T>
149 std::vector<size_t> indices;
150 if (v.empty()) return indices;
151 const auto max_value = *std::max_element(v.begin(), v.end());
152 for (size_t i = 0; i < v.size(); ++i) {
153 if (v[i] == max_value) indices.push_back(i);
154 }
155 return indices;
156}
157
158/**
159 * @brief Primality test by trial division
160 * @tparam T Unsigned integer type
161 * @param a Number to test for primality
162 * @return true if a is prime, false otherwise
163 *
164 * Tests odd divisors up to √a. Returns false for a ≤ 1 and even a > 2.
165 */
166template <class T>
167constexpr bool is_prime(T a) noexcept {
168 if (a == 2) return true;
169 if (a <= 1 || !(a & 1)) return false;
170 // find "smaller half" of factorization (if factor > sqrt(a) there must be a factor < sqrt(a))
171 for (T b = 3; b * b <= a; b += 2)
172 if ((a % b) == 0) return false;
173 return true;
174}
175
176/**
177 * @brief Greatest common divisor and optional Bézout coefficients
178 * @tparam T Signed integral type
179 * @param a First integer
180 * @param b Second integer
181 * @param s Pointer to store Bézout coefficient for a (optional)
182 * @param t Pointer to store Bézout coefficient for b (optional)
183 * @return Greatest common divisor of a and b
184 *
185 * If @p s and @p t are non-null, stores coefficients satisfying `a*s + b*t = gcd(a,b)`.
186 */
187template <class T>
188constexpr T GCD(T a, T b, T* s = nullptr, T* t = nullptr) {
189 static_assert((std::is_integral_v<T> && std::is_signed_v<T>) || std::is_same_v<T, InfInt>,
190 "GCD requires signed integral type or InfInt");
191 if (s != nullptr && t != nullptr) { // extended EA
192 *s = T(1);
193 *t = T(0);
194 T u = T(0);
195 T v = T(1);
196 while (b != T(0)) {
197 const T q = a / b;
198 T b1 = std::move(b);
199 b = a - q * b1;
200 a = std::move(b1);
201 T u1 = std::move(u);
202 u = *s - q * u1;
203 *s = std::move(u1);
204 T v1 = std::move(v);
205 v = *t - q * v1;
206 *t = std::move(v1);
207 }
208 } else { // "normal" EA
209 while (b != T(0)) {
210 const T q = a / b;
211 T b1 = std::move(b);
212 b = a - q * b1;
213 a = std::move(b1);
214 }
215 }
216 return a;
217}
218
219/**
220 * @brief Multiplicative inverse modulo a prime
221 * @tparam p Prime modulus (must be prime for correct results)
222 * @tparam T Signed integer type
223 * @param a Element to invert
224 * @return Modular inverse a^(-1) mod p
225 *
226 * Uses the extended Euclidean algorithm.
227 */
228template <uint16_t p, class T>
229constexpr T modinv(T a) {
230 static_assert(is_prime(p), "p is not a prime");
231 T s, t;
232 GCD<T>(std::move(a), T(p), &s, &t); // don't actually need the gcd
233 T result = s % T(p);
234 return result < 0 ? result + T(p) : result;
235}
236
237/**
238 * @brief Factorial a!
239 * @tparam T Integer type
240 * @param a Non-negative integer
241 * @return `a! = a * (a-1) * ... * 2 * 1`
242 */
243template <class T>
244T fac(T a) {
245 T res = 1;
246 while (a > 1) {
247 res *= a;
248 --a;
249 }
250 return res;
251}
252
253/**
254 * @brief Binomial coefficient C(n,k)
255 * @tparam T Integer type
256 * @param n Total number of items
257 * @param k Number of items to choose
258 * @return `C(n,k) = n! / (k! * (n-k)!)`
259 *
260 * Uses the multiplicative formula and the symmetry `C(n,k) = C(n,n-k)`.
261 */
262template <class T>
263T bin(const T& n, T k) {
264 if (k > n) return 0;
265 if (k == 0 || n == k) return 1;
266 if (k > n - k) k = n - k; // symmetry
267 T res = 1;
268 for (T i = 1; i <= k; ++i) res = res * (n - k + i) / i;
269 return res;
270}
271
272/**
273 * @brief Binomial coefficient specialization for @ref InfInt
274 * @param n Total number of items
275 * @param k Number of items to choose
276 * @return `C(n,k)` as an @ref InfInt
277 *
278 * Builds numerator and denominator separately, then performs one division.
279 */
280template <>
281inline InfInt bin(const InfInt& n, InfInt k) {
282 if (k > n) return 0;
283 if (k == 0 || n == k) return 1;
284 if (n == 0) return 0;
285 if (k > n - k) k = n - k; // symmetry
286 InfInt numerator = 1;
287 InfInt denominator = 1;
288 for (InfInt i = 1; i <= k; ++i) {
289 numerator *= n + 1 - i;
290 denominator *= i;
291 }
292 return numerator / denominator;
293}
294
295/**
296 * @brief Base-2 logarithm of a positive @ref InfInt of arbitrary magnitude
297 * @param v Positive integer
298 * @return `log2(v)` as `long double`
299 * @throws std::invalid_argument if v <= 0
300 *
301 * Evaluates the leading decimal digits and shifts by the remaining length, avoiding any
302 * conversion of @p v to a builtin integer type (which would overflow beyond 2^64).
303 */
304inline long double log2(const InfInt& v) {
305 if (v <= 0) throw std::invalid_argument("log2 requires a positive argument!");
306 const std::string s = v.to_string();
307 const size_t lead = std::min<size_t>(s.size(), 18);
308 return std::log2(std::stold(s.substr(0, lead))) + static_cast<long double>(s.size() - lead) * std::log2(10.0L);
309}
310
311/**
312 * @brief Conversion of an @ref InfInt of arbitrary magnitude to `long double`
313 * @param v Integer
314 * @return Nearest representable value (about 18 significant decimal digits are preserved)
315 */
316inline long double to_long_double(const InfInt& v) {
317 const std::string s = v.to_string();
318 const size_t sign = (s[0] == '-') ? 1 : 0;
319 const size_t digits = s.size() - sign;
320 const size_t lead = std::min<size_t>(digits, 18);
321 const long double head = std::stold(s.substr(0, sign + lead));
322 return head * std::pow(10.0L, static_cast<long double>(digits - lead));
323}
324
325/**
326 * @brief Sierpinski triangle (Pascal's triangle modulo p)
327 *
328 * Provides binomial coefficients `C(n,k) mod p` without overflow or multi-precision arithmetic.
329 */
331 public:
332 /**
333 * @brief Precompute `C(n,k) mod p` for all n <= n_max and k <= k_max
334 * @throws std::invalid_argument if p is zero
335 */
336 SierpinskiTriangle(size_t n_max, size_t k_max, size_t p)
337 : n_max(n_max), k_max(k_max), table((n_max + 1) * (k_max + 1)) {
338 if (p == 0) throw std::invalid_argument("SierpinskiTriangle modulus must be positive!");
339 for (size_t n = 0; n <= n_max; ++n) {
340 table[n * (k_max + 1)] = 1 % p;
341 for (size_t k = 1; k <= std::min(n, k_max); ++k)
342 table[n * (k_max + 1) + k] =
343 (table[(n - 1) * (k_max + 1) + k - 1] + table[(n - 1) * (k_max + 1) + k]) % p;
344 }
345 }
346
347 /// @brief `C(n,k) mod p`, zero whenever k > n (even beyond the precomputed range)
348 /// @throws std::invalid_argument if k <= n and n > n_max or k > k_max
350 if (k > n) return 0;
351 if (n > n_max || k > k_max)
352 throw std::invalid_argument("SierpinskiTriangle argument(s) beyond precomputed range!");
353 return table[n * (k_max + 1) + k];
354 }
355
356 private:
357 size_t n_max;
358 size_t k_max;
359 std::vector<size_t> table;
360};
361
362/**
363 * @brief Exponentiation by square-and-multiply
364 * @tparam T Type supporting multiplication and, for negative exponents, division
365 * @param b Base value
366 * @param e Exponent
367 * @return `b^e`
368 *
369 * For negative exponents, computes `(1/b)^|e|`.
370 *
371 * @note Returns `T(1)` for e = 0.
372 * @throws std::overflow_error if T is an integral type and the result would overflow it
373 * @throws std::invalid_argument for negative exponents when T is integral or has no division
374 */
375template <class T>
376constexpr T sqm(T b, int e) {
377 static_assert(std::is_integral_v<decltype(e)>, "exponent must be integral type");
378 if (e == 0) return T(1);
379 if (e < 0) {
380 if constexpr (std::is_integral_v<T> || std::is_same_v<T, InfInt> || !requires(T x) { T(1) / x; }) {
381 throw std::invalid_argument("sqm: negative exponent requires an invertible base type!");
382 } else {
383 b = T(1) / b;
384 if (e == std::numeric_limits<int>::min())
385 throw std::invalid_argument(
386 "Exponent e too large!"); // INT_MIN might be INT_MAX+1, potential problem in next line
387 e = -e;
388 }
389 }
390 // square and multiply
391 T temp(1);
392 unsigned int exp = static_cast<unsigned int>(e);
393 if constexpr (std::is_integral_v<T>) {
394 const auto mul = [](T x, T y) -> T {
395 if constexpr (std::is_unsigned_v<T>) {
396 if (x != T(0) && y > std::numeric_limits<T>::max() / x)
397 throw std::overflow_error("sqm: integer overflow");
398 } else {
399 constexpr T max = std::numeric_limits<T>::max();
400 constexpr T min = std::numeric_limits<T>::min();
401 if (x != T(0) && y != T(0)) {
402 if (x > T(0) ? (y > T(0) ? x > max / y : y < min / x) : (y > T(0) ? x < min / y : y < max / x))
403 throw std::overflow_error("sqm: integer overflow");
404 }
405 }
406 return x * y;
407 };
408 while (exp > 0) {
409 if (exp & 1) temp = mul(temp, b);
410 exp >>= 1;
411 if (exp > 0) b = mul(b, b);
412 }
413 } else {
414 while (exp > 0) {
415 if (exp & 1) temp *= b;
416 exp >>= 1;
417 if (exp > 0) b *= b;
418 }
419 }
420 return temp;
421}
422
423/**
424 * @brief Scalar multiplication by double-and-add
425 * @tparam T Type supporting addition and unary minus
426 * @param b Multiplicand
427 * @param m Integer multiplier
428 * @return `b * m`
429 *
430 * For negative multipliers, computes `(-b) * |m|`.
431 *
432 * @note Returns `T(0)` for m = 0.
433 */
434template <class T>
435constexpr T daa(T b, int m) {
436 static_assert(std::is_integral_v<decltype(m)>, "multiplicand must be integral type");
437 if (m == 0) return T(0);
438 if (m < 0) {
439 b = -b;
440 if (m == std::numeric_limits<int>::min())
441 throw std::invalid_argument(
442 "Multiplier m too large!"); // INT_MIN might be INT_MAX+1, potential problem in next line
443 m = -m;
444 }
445 // double and add
446 T temp(0);
447 unsigned int um = static_cast<unsigned int>(m);
448 while (um > 0) {
449 if (um & 1) temp += b;
450 um >>= 1;
451 if (um > 0) b += b;
452 }
453 return temp;
454}
455
456namespace details {
457
458/**
459 * @brief Reservoir-sampling acceptance test for randomized tie-breaking
460 * @param count Number of candidates tied for best so far, including the current one (≥ 1)
461 * @return true with probability 1/count
462 *
463 * Reservoir sampling with a reservoir of size one, Algorithm R (Wikipedia, "Reservoir
464 * sampling"): for the i-th stream item draw `randomInteger(1, i)` and keep it iff the draw is 1,
465 * i.e. with probability 1/i. Passing the running tie count (incremented for the current
466 * candidate) thus leaves every tied candidate equally likely to be the one finally kept. Used by
467 * the Viterbi, BCJR, and standard-array tie-breaks.
468 *
469 * @code{.cpp}
470 * if (metric < best) { best = metric; choice = cand; ties = 1; }
471 * else if (metric == best && details::reservoir_accept(++ties)) choice = cand;
472 * @endcode
473 */
474inline bool reservoir_accept(size_t count) { return std::uniform_int_distribution<size_t>(1, count)(gen()) == 1; }
475
476/**
477 * @brief Constexpr floor function
478 * @param x Floating-point value
479 * @return Floor of x (largest integer ≤ x)
480 *
481 * Alternative to `std::floor` for constant evaluation.
482 *
483 * @note Returns `double`, matching `std::floor`.
484 */
485constexpr double floor_constexpr(double x) {
486 long int i = static_cast<long int>(x);
487 return (x < 0 && x != i) ? i - 1 : i;
488}
489
490/**
491 * @brief Cache entry specification
492 * @tparam ID Entry identifier
493 * @tparam T Stored value type
494 *
495 * Associates an entry ID with its value type for @ref Cache.
496 *
497 * @note IDs must be unique within one @ref Cache instance.
498 */
499template <auto ID, typename T>
501 static constexpr auto id = ID;
502 using type = T;
503};
504
505/**
506 * @brief Heterogeneous cache indexed by entry ID
507 *
508 * @tparam ENTRIES Pack of @ref CacheEntry types
509 *
510 * Each ID gets its own `std::optional<T>` slot in a `std::tuple`, so different IDs may share
511 * the same value type without ambiguity. Lookup is by compile-time ID; an unknown ID is a
512 * compile-time error.
513 *
514 * @warning Not thread-safe for concurrent writes. Use external synchronisation if multiple
515 * threads may call `set()`, `invalidate()`, or `operator()` simultaneously.
516 *
517 * @section Usage_Example
518 *
519 * @code{.cpp}
520 * using Entry1 = CacheEntry<0, std::vector<int>>;
521 * using Entry2 = CacheEntry<1, double>;
522 * using Entry3 = CacheEntry<5, std::string>; // IDs need not be consecutive
523 * Cache<Entry1, Entry2, Entry3> cache;
524 *
525 * cache.set<0>(std::vector<int>{1, 2, 3});
526 * auto& vec = cache.get_or_compute<0>([] { return std::vector<int>{4, 5, 6}; });
527 * if (cache.is_set<0>()) cache.invalidate<0>();
528 * @endcode
529 */
530template <typename... ENTRIES>
531class Cache {
532 private:
533 // ID -> position in the ENTRIES pack. Two constrained partial specialisations select
534 // lazily, so the recursion only instantiates the not-yet-matched tail.
535 template <auto ID, size_t I, typename...>
536 struct index_finder;
537
538 template <auto ID, size_t I, typename First, typename... Rest>
539 requires(First::id == ID)
540 struct index_finder<ID, I, First, Rest...> {
541 static constexpr size_t value = I;
542 };
543
544 template <auto ID, size_t I, typename First, typename... Rest>
545 requires(First::id != ID)
546 struct index_finder<ID, I, First, Rest...> {
547 static constexpr size_t value = index_finder<ID, I + 1, Rest...>::value;
548 };
549
550 template <auto ID>
551 static constexpr size_t index_for = index_finder<ID, 0, ENTRIES...>::value;
552
553 template <auto ID>
554 using type_for = typename std::tuple_element_t<index_for<ID>, std::tuple<ENTRIES...>>::type;
555
556 // One slot per entry, indexed by position. Independent slots avoid the duplicate-types
557 // ambiguity that a `std::variant<monostate, T1, T2, …>` would have when two entries
558 // happen to share the same value type.
559 mutable std::tuple<std::optional<typename ENTRIES::type>...> slots{};
560
561 public:
562 Cache() = default;
563
564 template <auto ID>
565 bool is_set() const noexcept {
566 return std::get<index_for<ID>>(slots).has_value();
567 }
568
569 template <auto ID, typename TYPE>
570 void set(TYPE&& value) const {
571 std::get<index_for<ID>>(slots) = static_cast<type_for<ID>>(std::forward<TYPE>(value));
572 }
573
574 template <auto ID>
575 bool invalidate() const noexcept {
576 auto& slot = std::get<index_for<ID>>(slots);
577 const bool was_set = slot.has_value();
578 slot.reset();
579 return was_set;
580 }
581
582 bool invalidate() const noexcept {
583 return std::apply(
584 [](auto&... s) {
585 const bool any = (s.has_value() || ...);
586 (s.reset(), ...);
587 return any;
588 },
589 slots);
590 }
591
592 template <auto ID>
593 const type_for<ID>& operator()(auto&& calculate_func) const {
594 auto& slot = std::get<index_for<ID>>(slots);
595 if (!slot.has_value()) slot = calculate_func();
596 return *slot;
597 }
598
599 template <auto ID>
601 return std::get<index_for<ID>>(slots);
602 }
603
604 template <auto ID>
605 const type_for<ID>& get_or_compute(auto&& calculate_func) const {
606 return operator()<ID>(std::forward<decltype(calculate_func)>(calculate_func));
607 }
608};
609
610/**
611 * @brief Thread-safe single-value cache
612 * @tparam T Value type stored in the cache
613 *
614 * Stores one optional value together with a `std::once_flag`. Use `call_once()` to guard
615 * lazy initialization when multiple threads may read the same object. Copying or moving a
616 * cache copies or moves the stored value, if any, and creates a fresh once flag.
617 *
618 * @note Classes containing `OnceCache` members need no hand-written copy or move operations:
619 * compiler-generated memberwise operations use the cache's copy and move operations, transferring
620 * the cached value while giving each destination cache its own fresh `std::once_flag`.
621 *
622 * @warning Concurrent reads through `call_once()` are thread-safe. Assignment, `emplace()`, and
623 * manual value changes are not synchronization points and must not race with other operations.
624 *
625 * @section Usage_Example
626 *
627 * @code{.cpp}
628 * mutable OnceCache<size_t> weight;
629 *
630 * weight.call_once([this] {
631 * if (weight.has_value()) return;
632 * weight.emplace(calculate_weight());
633 * });
634 *
635 * return weight.value();
636 * @endcode
637 */
638template <class T>
640 public:
641 OnceCache() = default;
642
643 OnceCache(const OnceCache& other) {
644 if (other.has_value()) data.emplace(other.value());
645 }
646
648 if (other.has_value()) data.emplace(std::move(other.value()));
649 }
650
651 OnceCache& operator=(const OnceCache& other) {
652 if (this != &other) {
653 reset();
654 if (other.has_value()) data.emplace(other.value());
655 }
656 return *this;
657 }
658
660 if (this != &other) {
661 reset();
662 if (other.has_value()) data.emplace(std::move(other.value()));
663 }
664 return *this;
665 }
666
667 OnceCache& operator=(const T& value) {
668 data = value;
669 return *this;
670 }
671
672 OnceCache& operator=(T&& value) {
673 data = std::move(value);
674 return *this;
675 }
676
677 template <class F>
678 void call_once(F&& f) const {
679 std::call_once(flag, std::forward<F>(f));
680 }
681
682 template <class... Args>
683 T& emplace(Args&&... args) const {
684 return data.emplace(std::forward<Args>(args)...);
685 }
686
687 bool has_value() const noexcept { return data.has_value(); }
688
689 explicit operator bool() const noexcept { return has_value(); }
690
691 T& value() { return data.value(); }
692
693 const T& value() const { return data.value(); }
694
695 T& operator*() { return *data; }
696
697 const T& operator*() const { return *data; }
698
699 T* operator->() { return &*data; }
700
701 const T* operator->() const { return &*data; }
702
703 void reset() const {
704 data.reset();
705 flag.~once_flag();
706 new (&flag) std::once_flag();
707 }
708
709 private:
710 mutable std::optional<T> data;
711 mutable std::once_flag flag;
712};
713
714inline std::string basename(const char* path) {
715 std::string s(path);
716
717 const auto pos = s.find_last_of("/\\");
718 if (pos != std::string::npos) s.erase(0, pos + 1);
719
720 const auto dot = s.find_last_of('.');
721 if (dot != std::string::npos && dot != 0) s.erase(dot);
722
723 return s;
724}
725
726static const uint8_t colormap[64][3] = {
727 {0, 0, 0}, {0, 0, 24}, {0, 0, 40}, {0, 0, 56}, {0, 0, 72}, {0, 0, 88},
728 {0, 0, 104}, {0, 0, 120}, {0, 0, 136}, {0, 0, 152}, {0, 0, 167}, {0, 0, 183},
729 {0, 0, 199}, {0, 0, 215}, {0, 0, 231}, {0, 0, 252}, {0, 6, 253}, {0, 24, 232},
730 {0, 40, 216}, {0, 56, 200}, {0, 72, 184}, {0, 88, 168}, {0, 104, 152}, {0, 120, 136},
731 {0, 136, 120}, {0, 152, 104}, {0, 167, 88}, {0, 183, 72}, {0, 199, 56}, {0, 215, 41},
732 {0, 231, 25}, {0, 249, 6}, {6, 255, 0}, {24, 255, 0}, {40, 255, 0}, {56, 255, 0},
733 {72, 255, 0}, {88, 255, 0}, {104, 255, 0}, {120, 255, 0}, {136, 255, 0}, {152, 255, 0},
734 {167, 255, 0}, {183, 255, 0}, {199, 255, 0}, {215, 255, 0}, {231, 255, 0}, {249, 255, 0},
735 {255, 255, 6}, {255, 255, 24}, {255, 255, 40}, {255, 255, 56}, {255, 255, 72}, {255, 255, 88},
736 {255, 255, 104}, {255, 255, 120}, {255, 255, 136}, {255, 255, 152}, {255, 255, 167}, {255, 255, 183},
737 {255, 255, 199}, {255, 255, 215}, {255, 255, 231}, {255, 255, 255}};
738
739} // namespace details
740
741} // namespace CECCO
742
743#endif
Thread-local random number generator with shared seeding policy.
Definition helpers.hpp:56
static void seed(uint32_t seed)
Set deterministic seed for all threads.
Definition helpers.hpp:81
static void use_hardware_seed()
Enable hardware-based random seeding.
Definition helpers.hpp:92
static std::mt19937 & get()
Get thread-local random number generator.
Definition helpers.hpp:65
Sierpinski triangle (Pascal's triangle modulo p).
Definition helpers.hpp:330
size_t operator()(size_t n, size_t k) const
C(n,k) mod p, zero whenever k > n (even beyond the precomputed range)
Definition helpers.hpp:349
SierpinskiTriangle(size_t n_max, size_t k_max, size_t p)
Precompute C(n,k) mod p for all n <= n_max and k <= k_max.
Definition helpers.hpp:336
Heterogeneous cache indexed by entry ID.
Definition helpers.hpp:531
std::optional< type_for< ID > > get() const
Definition helpers.hpp:600
bool invalidate() const noexcept
Definition helpers.hpp:582
bool is_set() const noexcept
Definition helpers.hpp:565
bool invalidate() const noexcept
Definition helpers.hpp:575
const type_for< ID > & get_or_compute(auto &&calculate_func) const
Definition helpers.hpp:605
void set(TYPE &&value) const
Definition helpers.hpp:570
const type_for< ID > & operator()(auto &&calculate_func) const
Definition helpers.hpp:593
Thread-safe single-value cache.
Definition helpers.hpp:639
OnceCache & operator=(const OnceCache &other)
Definition helpers.hpp:651
void call_once(F &&f) const
Definition helpers.hpp:678
const T & operator*() const
Definition helpers.hpp:697
const T * operator->() const
Definition helpers.hpp:701
OnceCache & operator=(const T &value)
Definition helpers.hpp:667
OnceCache(const OnceCache &other)
Definition helpers.hpp:643
T & emplace(Args &&... args) const
Definition helpers.hpp:683
OnceCache & operator=(T &&value)
Definition helpers.hpp:672
OnceCache(OnceCache &&other)
Definition helpers.hpp:647
operator bool() const noexcept
Definition helpers.hpp:689
bool has_value() const noexcept
Definition helpers.hpp:687
OnceCache & operator=(OnceCache &&other)
Definition helpers.hpp:659
const T & value() const
Definition helpers.hpp:693
bool operator<=(const InfInt &rhs) const
Definition InfInt.hpp:743
bool operator>(const InfInt &rhs) const
Definition InfInt.hpp:768
std::string to_string() const
Definition InfInt.hpp:897
const InfInt & operator*=(const InfInt &rhs)
Definition InfInt.hpp:492
const InfInt & operator=(const InfInt &l)
Definition InfInt.hpp:428
const InfInt & operator++()
Definition InfInt.hpp:436
InfInt operator-(const InfInt &rhs) const
Definition InfInt.hpp:583
InfInt operator/(const InfInt &rhs) const
Definition InfInt.hpp:632
bool operator==(const InfInt &rhs) const
Definition InfInt.hpp:692
Contains implementation details not to be exposed to the user. Functions and classes here may change ...
Definition blocks.hpp:59
std::string basename(const char *path)
Definition helpers.hpp:714
bool reservoir_accept(size_t count)
Reservoir-sampling acceptance test for randomized tie-breaking.
Definition helpers.hpp:474
static const uint8_t colormap[64][3]
Definition helpers.hpp:726
constexpr double floor_constexpr(double x)
Constexpr floor function.
Definition helpers.hpp:485
Provides a framework for error correcting codes.
Definition blocks.hpp:57
constexpr T modinv(T a)
Multiplicative inverse modulo a prime.
Definition helpers.hpp:229
std::mt19937 & gen()
Current thread's random number generator.
Definition helpers.hpp:137
std::vector< size_t > find_maxima(const std::vector< T > &v)
Indices of all maximum elements.
Definition helpers.hpp:148
constexpr T daa(T b, int m)
Scalar multiplication by double-and-add.
Definition helpers.hpp:435
T fac(T a)
Factorial a!
Definition helpers.hpp:244
long double to_long_double(const InfInt &v)
Conversion of an InfInt of arbitrary magnitude to long double.
Definition helpers.hpp:316
long double log2(const InfInt &v)
Base-2 logarithm of a positive InfInt of arbitrary magnitude.
Definition helpers.hpp:304
InfInt bin(const InfInt &n, InfInt k)
Binomial coefficient specialization for InfInt.
Definition helpers.hpp:281
constexpr T sqm(T b, int e)
Exponentiation by square-and-multiply.
Definition helpers.hpp:376
constexpr bool is_prime(T a) noexcept
Primality test by trial division.
Definition helpers.hpp:167
T bin(const T &n, T k)
Binomial coefficient C(n,k).
Definition helpers.hpp:263
constexpr T GCD(T a, T b, T *s=nullptr, T *t=nullptr)
Greatest common divisor and optional Bézout coefficients.
Definition helpers.hpp:188
Cache entry specification.
Definition helpers.hpp:500
static constexpr auto id
Definition helpers.hpp:501