| Taskflow: A General-purpose Task-parallel Programming System

Loading...
Searching...
No Matches
math.hpp
1#pragma once
2
3#include <atomic>
4#include <chrono>
5#include <concepts>
6#include <numeric>
7
8 namespace tf {
9
13 template <typename T>
14 requires (std::is_unsigned_v<std::decay_t<T>> && sizeof(T) == 8)
15 constexpr T next_pow2(T x) {
16 if(x == 0) return 1;
17 x--;
18 x |= x >> 1;
19 x |= x >> 2;
20 x |= x >> 4;
21 x |= x >> 8;
22 x |= x >> 16;
23 x |= x >> 32;
24 x++;
25 return x;
26}
27
31 template <typename T>
32 requires (std::is_unsigned_v<std::decay_t<T>> && sizeof(T) == 4)
33 constexpr T next_pow2(T y) {
34 if(y == 0) return 1;
35 y--;
36 y |= y >> 1;
37 y |= y >> 2;
38 y |= y >> 4;
39 y |= y >> 8;
40 y |= y >> 16;
41 y++;
42 return y;
43}
44
57 template <std::integral T>
58 constexpr bool is_pow2(const T& x) {
59 return x && (!(x&(x-1)));
60}
61
65 template <size_t N>
66 constexpr size_t static_floor_log2() {
67 return (N < 2) ? 0 : 1 + static_floor_log2<N / 2>();
68 //auto log = 0;
69 //while (N >>= 1) {
70 // ++log;
71 //}
72 //return log;
73}
74
75
91 template <typename RandItr, typename C>
92RandItr median_of_three(RandItr l, RandItr m, RandItr r, C cmp) {
93 return cmp(*l, *m) ? (cmp(*m, *r) ? m : (cmp(*l, *r) ? r : l ))
94 : (cmp(*r, *m) ? m : (cmp(*r, *l) ? r : l ));
95}
96
115 template <typename RandItr, typename C>
116RandItr pseudo_median_of_nine(RandItr beg, RandItr end, C cmp) {
117 size_t N = std::distance(beg, end);
118 size_t offset = N >> 3;
119 return median_of_three(
120 median_of_three(beg, beg+offset, beg+(offset*2), cmp),
121 median_of_three(beg+(offset*3), beg+(offset*4), beg+(offset*5), cmp),
122 median_of_three(beg+(offset*6), beg+(offset*7), end-1, cmp),
123 cmp
124 );
125}
126
140 template<typename Iter, typename Compare>
141 void sort2(Iter a, Iter b, Compare comp) {
142 if (comp(*b, *a)) std::iter_swap(a, b);
143}
144
160 template<typename Iter, typename Compare>
161 void sort3(Iter a, Iter b, Iter c, Compare comp) {
162 sort2(a, b, comp);
163 sort2(b, c, comp);
164 sort2(a, b, comp);
165}
166
181 template <std::integral T>
182T unique_id() {
183 static std::atomic<T> counter{0};
184 return counter.fetch_add(1, std::memory_order_relaxed);
185}
186
202 template <typename T>
203 inline void atomic_max(std::atomic<T>& v, const T& max_v) noexcept {
204 T prev = v.load(std::memory_order_relaxed);
205 while(prev < max_v &&
206 !v.compare_exchange_weak(prev, max_v, std::memory_order_relaxed,
207 std::memory_order_relaxed)) {
208 }
209}
210
226 template <typename T>
227 inline void atomic_min(std::atomic<T>& v, const T& min_v) noexcept {
228 T prev = v.load(std::memory_order_relaxed);
229 while(prev > min_v &&
230 !v.compare_exchange_weak(prev, min_v, std::memory_order_relaxed,
231 std::memory_order_relaxed)) {
232 }
233}
234
246 template <typename T>
247 inline T seed() noexcept {
248 return std::chrono::system_clock::now().time_since_epoch().count();
249}
250
251// ------------------------------------------------------------------------------------------------
252// coprime
253// ------------------------------------------------------------------------------------------------
254
264 constexpr size_t coprime(size_t N) {
265 if(N < 3) {
266 return 1;
267 }
268 for (size_t x = N; --x > 0;) {
269 if (std::gcd(x, N) == 1) {
270 return x;
271 }
272 }
273 return 1;
274}
275
285 template <size_t N>
286 constexpr std::array<size_t, N> make_coprime_lut() {
287 static_assert(N>0, "N must be greater than 0");
288 std::array<size_t, N> coprimes{};
289 for (size_t n = 0; n < N; ++n) {
290 coprimes[n] = coprime(n);
291 }
292 return coprimes;
293}
294
295//template <typename T>
296//constexpr T lemire_range(T x, T range) {
297// return (uint32_t)(((uint64_t)x * (uint64_t)range) >> 32);
298//}
299
300
318 template <typename T>
319 class Xorshift {
320 static_assert(std::is_unsigned<T>::value, "Xorshift requires an unsigned integral type.");
321
322 public:
323
330 Xorshift() = default;
331
339 Xorshift(T value) : _state(value) {}
340
349 void seed(T value) {
350 _state = value;
351 }
352
366 T operator()() {
367 if constexpr (sizeof(T) == 8) {
368 // Xorshift64 constants
369 _state ^= _state << 13;
370 _state ^= _state >> 7;
371 _state ^= _state << 17;
372 return _state * 0x2545F4914F6CDD1DULL;
373 }
374 else if constexpr (sizeof(T) == 4) {
375 // Xorshift32 constants
376 _state ^= _state << 13;
377 _state ^= _state >> 17;
378 _state ^= _state << 5;
379 return _state;
380 }
381 else {
382 static_assert(sizeof(T) == 0, "Unsupported bit-width for Xorshift. Use uint32_t or uint64_t.");
383 }
384 }
385
386 private:
387
388 T _state; // must be initialized with non-zero
389};
390
391} // end of namespace tf -----------------------------------------------------
tf::Xorshift::seed
void seed(T value)
seeds the generator with a new value
Definition math.hpp:349
tf::Xorshift::operator()
T operator()()
generates the next pseudo-random value
Definition math.hpp:366
tf::Xorshift::Xorshift
Xorshift(T value)
constructs a xor-shift generator with the given seed
Definition math.hpp:339
tf::Xorshift::Xorshift
Xorshift()=default
constructs an uninitialized xor-shift generator
tf
taskflow namespace
Definition small_vector.hpp:20
tf::median_of_three
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:92
tf::unique_id
T unique_id()
generates a program-wide unique ID of the given type in a thread-safe manner
Definition math.hpp:182
tf::coprime
constexpr size_t coprime(size_t N)
computes a coprime of a given number
Definition math.hpp:264
tf::seed
T seed() noexcept
generates a random seed based on the current system clock
Definition math.hpp:247
tf::next_pow2
constexpr T next_pow2(T x)
rounds the given 64-bit unsigned integer to the nearest power of 2
Definition math.hpp:15
tf::atomic_max
void atomic_max(std::atomic< T > &v, const T &max_v) noexcept
updates an atomic variable with the maximum value
Definition math.hpp:203
tf::atomic_min
void atomic_min(std::atomic< T > &v, const T &min_v) noexcept
updates an atomic variable with the minimum value
Definition math.hpp:227
tf::make_coprime_lut
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:286
tf::pseudo_median_of_nine
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:116
tf::sort3
void sort3(Iter a, Iter b, Iter c, Compare comp)
Sorts three elements of dereferenced iterators using the given comparison function.
Definition math.hpp:161
tf::sort2
void sort2(Iter a, Iter b, Compare comp)
sorts two elements of dereferenced iterators using the given comparison function
Definition math.hpp:141
tf::static_floor_log2
constexpr size_t static_floor_log2()
returns the floor of log2(N) at compile time
Definition math.hpp:66
tf::is_pow2
constexpr bool is_pow2(const T &x)
checks if the given number is a power of 2
Definition math.hpp:58