docs/math_8hpp_source.html
| | Taskflow: A General-purpose Task-parallel Programming System |
Loading...
Searching...
No Matches
math.hpp
1#pragma once
2
3#include <algorithm>
4#include <atomic>
5#include <chrono>
6#include <concepts>
7#include <numeric>
8
9namespace tf {
10
28template <typename T>
29requires (std::is_unsigned_v<std::decay_t<T>> && sizeof(T) == 8)
30constexpr T next_pow2(T x) {
31if(x == 0) return 1;
32 x--;
33 x |= x >> 1;
34 x |= x >> 2;
35 x |= x >> 4;
36 x |= x >> 8;
37 x |= x >> 16;
38 x |= x >> 32;
39 x++;
40return x;
41}
42
59template <typename T>
60requires (std::is_unsigned_v<std::decay_t<T>> && sizeof(T) == 4)
61constexpr T next_pow2(T y) {
62if(y == 0) return 1;
63 y--;
64 y |= y >> 1;
65 y |= y >> 2;
66 y |= y >> 4;
67 y |= y >> 8;
68 y |= y >> 16;
69 y++;
70return y;
71}
72
91template <std::integral T>
92constexpr bool is_pow2(const T& x) {
93return x && (!(x&(x-1)));
94}
95
111template <size_t N>
112constexpr size_t static_floor_log2() {
113return (N < 2) ? 0 : 1 + static_floor_log2<N / 2>();
114//auto log = 0;
115//while (N >>= 1) {
116// ++log;
117//}
118//return log;
119}
120
121
142template <typename RandItr, typename C>
143RandItr median_of_three(RandItr l, RandItr m, RandItr r, C cmp) {
144return cmp(*l, *m) ? (cmp(*m, *r) ? m : (cmp(*l, *r) ? r : l ))
145 : (cmp(*r, *m) ? m : (cmp(*r, *l) ? r : l ));
146}
147
170template <typename RandItr, typename C>
171RandItr pseudo_median_of_nine(RandItr beg, RandItr end, C cmp) {
172size_t N = std::distance(beg, end);
173size_t offset = N >> 3;
174return median_of_three(
175median_of_three(beg, beg+offset, beg+(offset*2), cmp),
176median_of_three(beg+(offset*3), beg+(offset*4), beg+(offset*5), cmp),
177median_of_three(beg+(offset*6), beg+(offset*7), end-1, cmp),
178 cmp
179 );
180}
181
200template<typename Iter, typename Compare>
201void sort2(Iter a, Iter b, Compare comp) {
202if (comp(*b, *a)) std::iter_swap(a, b);
203}
204
225template<typename Iter, typename Compare>
226void sort3(Iter a, Iter b, Iter c, Compare comp) {
227sort2(a, b, comp);
228sort2(b, c, comp);
229sort2(a, b, comp);
230}
231
251template <std::integral T>
253static std::atomic<T> counter{0};
254return counter.fetch_add(1, std::memory_order_relaxed);
255}
256
277template <typename T>
278inline void atomic_max(std::atomic<T>& v, const T& max_v) noexcept {
279 T prev = v.load(std::memory_order_relaxed);
280while(prev < max_v &&
281 !v.compare_exchange_weak(prev, max_v, std::memory_order_relaxed,
282 std::memory_order_relaxed)) {
283 }
284}
285
306template <typename T>
307inline void atomic_min(std::atomic<T>& v, const T& min_v) noexcept {
308 T prev = v.load(std::memory_order_relaxed);
309while(prev > min_v &&
310 !v.compare_exchange_weak(prev, min_v, std::memory_order_relaxed,
311 std::memory_order_relaxed)) {
312 }
313}
314
330template <typename T>
332return std::chrono::system_clock::now().time_since_epoch().count();
333}
334
335// ------------------------------------------------------------------------------------------------
336// coprime
337// ------------------------------------------------------------------------------------------------
338
352constexpr size_t coprime(size_t N) {
353if(N < 3) {
354return 1;
355 }
356for (size_t x = N; --x > 0;) {
357if (std::gcd(x, N) == 1) {
358return x;
359 }
360 }
361return 1;
362}
363
378template <size_t N>
379constexpr std::array<size_t, N> make_coprime_lut() {
380static_assert(N>0, "N must be greater than 0");
381 std::array<size_t, N> coprimes{};
382for (size_t n = 0; n < N; ++n) {
383 coprimes[n] = coprime(n);
384 }
385return coprimes;
386}
387
388//template <typename T>
389//constexpr T lemire_range(T x, T range) {
390// return (uint32_t)(((uint64_t)x * (uint64_t)range) >> 32);
391//}
392
393
411template <typename T>
413static_assert(std::is_unsigned<T>::value, "Xorshift requires an unsigned integral type.");
414
415public:
416
429
442Xorshift(T value) : _state(value) {}
443
458 _state = value;
459 }
460
480 T operator()() {
481if constexpr (sizeof(T) == 8) {
482// Xorshift64 constants
483 _state ^= _state << 13;
484 _state ^= _state >> 7;
485 _state ^= _state << 17;
486return _state * 0x2545F4914F6CDD1DULL;
487 }
488else if constexpr (sizeof(T) == 4) {
489// Xorshift32 constants
490 _state ^= _state << 13;
491 _state ^= _state >> 17;
492 _state ^= _state << 5;
493return _state;
494 }
495else {
496static_assert(sizeof(T) == 0, "Unsupported bit-width for Xorshift. Use uint32_t or uint64_t.");
497 }
498 }
499
500private:
501
502 T _state; // must be initialized with non-zero
503};
504
505} // end of namespace tf -----------------------------------------------------
void seed(T value)
seeds the generator with a new value
Definition math.hpp:457
T operator()()
generates the next pseudo-random value
Definition math.hpp:480
Xorshift(T value)
constructs a xor-shift generator with the given seed
Definition math.hpp:442
Xorshift()=default
constructs an uninitialized xor-shift generator
taskflow namespace
Definition small_vector.hpp:20
RandItr median_of_three(RandItr l, RandItr m, RandItr r, C cmp)
finds the median of three numbers pointed to by iterators using the given comparator
Definition math.hpp:143
T unique_id()
generates a program-wide unique ID of the given type in a thread-safe manner
Definition math.hpp:252
constexpr size_t coprime(size_t N)
computes a coprime of a given number
Definition math.hpp:352
T seed() noexcept
generates a random seed based on the current system clock
Definition math.hpp:331
constexpr T next_pow2(T x)
rounds the given 64-bit unsigned integer to the nearest power of 2
Definition math.hpp:30
void atomic_max(std::atomic< T > &v, const T &max_v) noexcept
updates an atomic variable with the maximum value
Definition math.hpp:278
void atomic_min(std::atomic< T > &v, const T &min_v) noexcept
updates an atomic variable with the minimum value
Definition math.hpp:307
constexpr std::array< size_t, N > make_coprime_lut()
generates a compile-time array of coprimes for numbers from 0 to N-1
Definition math.hpp:379
RandItr pseudo_median_of_nine(RandItr beg, RandItr end, C cmp)
finds the pseudo median of a range of items using a spread of nine numbers
Definition math.hpp:171
void sort3(Iter a, Iter b, Iter c, Compare comp)
Sorts three elements of dereferenced iterators using the given comparison function.
Definition math.hpp:226
void sort2(Iter a, Iter b, Compare comp)
sorts two elements of dereferenced iterators using the given comparison function
Definition math.hpp:201
constexpr size_t static_floor_log2()
returns the floor of log2(N) at compile time
Definition math.hpp:112
constexpr bool is_pow2(const T &x)
checks if the given number is a power of 2
Definition math.hpp:92