| 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
9 namespace tf {
10
28 template <typename T>
29 requires (std::is_unsigned_v<std::decay_t<T>> && sizeof(T) == 8)
30 constexpr T next_pow2(T x) {
31 if(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++;
40 return x;
41}
42
59 template <typename T>
60 requires (std::is_unsigned_v<std::decay_t<T>> && sizeof(T) == 4)
61 constexpr T next_pow2(T y) {
62 if(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++;
70 return y;
71}
72
91 template <std::integral T>
92 constexpr bool is_pow2(const T& x) {
93 return x && (!(x&(x-1)));
94}
95
111 template <size_t N>
112 constexpr size_t static_floor_log2() {
113 return (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
142 template <typename RandItr, typename C>
143RandItr median_of_three(RandItr l, RandItr m, RandItr r, C cmp) {
144 return cmp(*l, *m) ? (cmp(*m, *r) ? m : (cmp(*l, *r) ? r : l ))
145 : (cmp(*r, *m) ? m : (cmp(*r, *l) ? r : l ));
146}
147
170 template <typename RandItr, typename C>
171RandItr pseudo_median_of_nine(RandItr beg, RandItr end, C cmp) {
172 size_t N = std::distance(beg, end);
173 size_t offset = N >> 3;
174 return median_of_three(
175 median_of_three(beg, beg+offset, beg+(offset*2), cmp),
176 median_of_three(beg+(offset*3), beg+(offset*4), beg+(offset*5), cmp),
177 median_of_three(beg+(offset*6), beg+(offset*7), end-1, cmp),
178 cmp
179 );
180}
181
200 template<typename Iter, typename Compare>
201 void sort2(Iter a, Iter b, Compare comp) {
202 if (comp(*b, *a)) std::iter_swap(a, b);
203}
204
225 template<typename Iter, typename Compare>
226 void sort3(Iter a, Iter b, Iter c, Compare comp) {
227 sort2(a, b, comp);
228 sort2(b, c, comp);
229 sort2(a, b, comp);
230}
231
251 template <std::integral T>
252T unique_id() {
253 static std::atomic<T> counter{0};
254 return counter.fetch_add(1, std::memory_order_relaxed);
255}
256
277 template <typename T>
278 inline void atomic_max(std::atomic<T>& v, const T& max_v) noexcept {
279 T prev = v.load(std::memory_order_relaxed);
280 while(prev < max_v &&
281 !v.compare_exchange_weak(prev, max_v, std::memory_order_relaxed,
282 std::memory_order_relaxed)) {
283 }
284}
285
306 template <typename T>
307 inline void atomic_min(std::atomic<T>& v, const T& min_v) noexcept {
308 T prev = v.load(std::memory_order_relaxed);
309 while(prev > min_v &&
310 !v.compare_exchange_weak(prev, min_v, std::memory_order_relaxed,
311 std::memory_order_relaxed)) {
312 }
313}
314
330 template <typename T>
331 inline T seed() noexcept {
332 return std::chrono::system_clock::now().time_since_epoch().count();
333}
334
335// ------------------------------------------------------------------------------------------------
336// coprime
337// ------------------------------------------------------------------------------------------------
338
352 constexpr size_t coprime(size_t N) {
353 if(N < 3) {
354 return 1;
355 }
356 for (size_t x = N; --x > 0;) {
357 if (std::gcd(x, N) == 1) {
358 return x;
359 }
360 }
361 return 1;
362}
363
378 template <size_t N>
379 constexpr std::array<size_t, N> make_coprime_lut() {
380 static_assert(N>0, "N must be greater than 0");
381 std::array<size_t, N> coprimes{};
382 for (size_t n = 0; n < N; ++n) {
383 coprimes[n] = coprime(n);
384 }
385 return 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
411 template <typename T>
412 class Xorshift {
413 static_assert(std::is_unsigned<T>::value, "Xorshift requires an unsigned integral type.");
414
415 public:
416
428 Xorshift() = default;
429
442 Xorshift(T value) : _state(value) {}
443
457 void seed(T value) {
458 _state = value;
459 }
460
480 T operator()() {
481 if constexpr (sizeof(T) == 8) {
482 // Xorshift64 constants
483 _state ^= _state << 13;
484 _state ^= _state >> 7;
485 _state ^= _state << 17;
486 return _state * 0x2545F4914F6CDD1DULL;
487 }
488 else if constexpr (sizeof(T) == 4) {
489 // Xorshift32 constants
490 _state ^= _state << 13;
491 _state ^= _state >> 17;
492 _state ^= _state << 5;
493 return _state;
494 }
495 else {
496 static_assert(sizeof(T) == 0, "Unsupported bit-width for Xorshift. Use uint32_t or uint64_t.");
497 }
498 }
499
500 private:
501
502 T _state; // must be initialized with non-zero
503};
504
505} // end of namespace tf -----------------------------------------------------
tf::Xorshift
class to create a fast xorshift-based pseudo-random number generator
Definition math.hpp:412
tf::Xorshift::seed
void seed(T value)
seeds the generator with a new value
Definition math.hpp:457
tf::Xorshift::operator()
T operator()()
generates the next pseudo-random value
Definition math.hpp:480
tf::Xorshift::Xorshift
Xorshift(T value)
constructs a xor-shift generator with the given seed
Definition math.hpp:442
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:143
tf::unique_id
T unique_id()
generates a program-wide unique ID of the given type in a thread-safe manner
Definition math.hpp:252
tf::coprime
constexpr size_t coprime(size_t N)
computes a coprime of a given number
Definition math.hpp:352
tf::seed
T seed() noexcept
generates a random seed based on the current system clock
Definition math.hpp:331
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:30
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:278
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:307
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:379
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:171
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:226
tf::sort2
void sort2(Iter a, Iter b, Compare comp)
sorts two elements of dereferenced iterators using the given comparison function
Definition math.hpp:201
tf::static_floor_log2
constexpr size_t static_floor_log2()
returns the floor of log2(N) at compile time
Definition math.hpp:112
tf::is_pow2
constexpr bool is_pow2(const T &x)
checks if the given number is a power of 2
Definition math.hpp:92