Loading...
Searching...
No Matches
Multi_field_small.h
Go to the documentation of this file.
1/* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT.
2 * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details.
3 * Author(s): Hannah Schreiber, Clément Maria
4 *
5 * Copyright (C) 2022-24 Inria
6 *
7 * Modification(s):
8 * - YYYY/MM Author: Description of the modification
9 */
10
17#ifndef MATRIX_FIELD_MULTI_SMALL_H_
18#define MATRIX_FIELD_MULTI_SMALL_H_
19
20#include <utility>
21#include <vector>
22#include <limits.h>
23#include <numeric>
24
25namespace Gudhi {
26namespace persistence_fields {
27
41template <unsigned int minimum, unsigned int maximum, typename Unsigned_integer_type = unsigned int,
42 class = std::enable_if_t<std::is_unsigned_v<Unsigned_integer_type> > >
44 public:
45 using Element = Unsigned_integer_type;
47 template <class T>
48 using isInteger = std::enable_if_t<std::is_integral_v<T> >;
49
54 static_assert(maximum >= 2, "Characteristics have to be positive.");
55 static_assert(minimum <= maximum, "The given interval is not valid.");
56 static_assert(minimum != maximum || _is_prime(minimum), "The given interval does not contain a prime number.");
57 static_assert(productOfAllCharacteristics_ != 1, "The given interval does not contain a prime number.");
58 }
64 template <typename Integer_type, class = isInteger<Integer_type> >
66 : element_(_get_value(element)) {
67 static_assert(maximum >= 2, "Characteristics has to be positive.");
68 static_assert(minimum <= maximum, "The given interval is not valid.");
69 static_assert(minimum != maximum || _is_prime(minimum), "The given interval does not contain a prime number.");
70 static_assert(productOfAllCharacteristics_ != 1, "The given interval does not contain a prime number.");
71 }
85 : element_(std::exchange(toMove.element_, 0)) {}
86
92 f1.element_ = _add(f1.element_, f2.element_);
93 }
107 template <typename Integer_type, class = isInteger<Integer_type> >
108 friend void operator+=(Multi_field_element_with_small_characteristics& f, const Integer_type& v) {
109 f.element_ = _add(f.element_, _get_value(v));
110 }
116 template <typename Integer_type, class = isInteger<Integer_type> >
118 const Integer_type& v) {
119 f += v;
120 return f;
121 }
127 template <typename Integer_type, class = isInteger<Integer_type> >
128 friend Integer_type operator+(const Integer_type& v, Multi_field_element_with_small_characteristics f) {
129 f += v;
130 return f.element_;
131 }
132
138 f1.element_ = _subtract(f1.element_, f2.element_);
139 }
153 template <typename Integer_type, class = isInteger<Integer_type> >
154 friend void operator-=(Multi_field_element_with_small_characteristics& f, const Integer_type& v) {
155 f.element_ = _subtract(f.element_, _get_value(v));
156 }
162 template <typename Integer_type, class = isInteger<Integer_type> >
164 const Integer_type& v) {
165 f -= v;
166 return f;
167 }
173 template <typename Integer_type, class = isInteger<Integer_type> >
174 friend Integer_type operator-(const Integer_type& v, const Multi_field_element_with_small_characteristics& f) {
175 return _subtract(_get_value(v), f.element_);
176 }
177
183 f1.element_ = _multiply(f1.element_, f2.element_);
184 }
198 template <typename Integer_type, class = isInteger<Integer_type> >
199 friend void operator*=(Multi_field_element_with_small_characteristics& f, const Integer_type& v) {
200 f.element_ = _multiply(f.element_, _get_value(v));
201 }
207 template <typename Integer_type, class = isInteger<Integer_type> >
209 const Integer_type& v) {
210 f *= v;
211 return f;
212 }
218 template <typename Integer_type, class = isInteger<Integer_type> >
219 friend Integer_type operator*(const Integer_type& v, Multi_field_element_with_small_characteristics f) {
220 f *= v;
221 return f.element_;
222 }
223
229 return f1.element_ == f2.element_;
230 }
236 template <typename Integer_type, class = isInteger<Integer_type> >
237 friend bool operator==(const Integer_type v, const Multi_field_element_with_small_characteristics& f) {
238 return _get_value(v) == f.element_;
239 }
245 template <typename Integer_type, class = isInteger<Integer_type> >
246 friend bool operator==(const Multi_field_element_with_small_characteristics& f, const Integer_type v) {
247 return _get_value(v) == f.element_;
248 }
254 return !(f1 == f2);
255 }
261 template <typename Integer_type, class = isInteger<Integer_type> >
262 friend bool operator!=(const Integer_type v, const Multi_field_element_with_small_characteristics& f) {
263 return !(v == f);
264 }
270 template <typename Integer_type, class = isInteger<Integer_type> >
271 friend bool operator!=(const Multi_field_element_with_small_characteristics& f, const Integer_type v) {
272 return !(v == f);
273 }
274
279 std::swap(element_, other.element_);
280 return *this;
281 }
287 template <typename Integer_type, class = isInteger<Integer_type> >
289 element_ = _get_value(value);
290 return *this;
291 }
297 std::swap(f1.element_, f2.element_);
298 }
299
303 operator unsigned int() const { return element_; }
304
311 return get_partial_inverse(productOfAllCharacteristics_).first;
312 }
320 std::pair<Multi_field_element_with_small_characteristics,Characteristic> get_partial_inverse(
321 Characteristic productOfCharacteristics) const {
322 Characteristic gcd = std::gcd(element_, productOfAllCharacteristics_);
323
324 if (gcd == productOfCharacteristics)
325 return {Multi_field_element_with_small_characteristics(), multiplicativeID_}; // partial inverse is 0
326
327 Characteristic QT = productOfCharacteristics / gcd;
328
329 const Element inv_qt = _get_inverse(element_, QT);
330
332 res *= inv_qt;
333
334 return {res, QT};
335 }
336
361 const Characteristic& productOfCharacteristics) {
362 if (productOfCharacteristics == 0) {
364 }
366 for (Characteristic idx = 0; idx < primes_.size(); ++idx) {
367 if ((productOfCharacteristics % primes_[idx]) == 0) {
368 mult += partials_[idx];
369 }
370 }
371 return mult;
372 }
378 static constexpr Characteristic get_characteristic() { return productOfAllCharacteristics_; }
379
385 Element get_value() const { return element_; }
386
387 // static constexpr bool handles_only_z2() { return false; }
388
389 private:
390 static constexpr bool _is_prime(const unsigned int p) {
391 if (p <= 1) return false;
392 if (p <= 3) return true;
393 if (p % 2 == 0 || p % 3 == 0) return false;
394
395 for (unsigned long i = 5; i * i <= p; i = i + 6)
396 if (p % i == 0 || p % (i + 2) == 0) return false;
397
398 return true;
399 }
400 static constexpr Element _multiply(Element a, Element b) {
401 Element res = 0;
402 Element temp_b = 0;
403
404 if (b < a) std::swap(a, b);
405
406 while (a != 0) {
407 if (a & 1) {
408 /* Add b to res, modulo m, without overflow */
409 if (b >= productOfAllCharacteristics_ - res) res -= productOfAllCharacteristics_;
410 res += b;
411 }
412 a >>= 1;
413
414 /* Double b, modulo m */
415 temp_b = b;
416 if (b >= productOfAllCharacteristics_ - b) temp_b -= productOfAllCharacteristics_;
417 b += temp_b;
418 }
419 return res;
420 }
421 static constexpr Element _add(Element element, Element v) {
422 if (UINT_MAX - element < v) {
423 // automatic unsigned integer overflow behaviour will make it work
424 element += v;
425 element -= productOfAllCharacteristics_;
426 return element;
427 }
428
429 element += v;
430 if (element >= productOfAllCharacteristics_) element -= productOfAllCharacteristics_;
431
432 return element;
433 }
434 static constexpr Element _subtract(Element element, Element v) {
435 if (element < v) {
436 element += productOfAllCharacteristics_;
437 }
438 element -= v;
439
440 return element;
441 }
442 static constexpr int _get_inverse(Element element, const Element mod) {
443 // to solve: Ax + My = 1
444 int M = mod;
445 int A = element;
446 int y = 0, x = 1;
447 // extended euclidean division
448 while (A > 1) {
449 int quotient = A / M;
450 int temp = M;
451
452 M = A % M, A = temp;
453 temp = y;
454
455 y = x - quotient * y;
456 x = temp;
457 }
458
459 if (x < 0) x += mod;
460
461 return x;
462 }
463
464 template <typename Integer_type, class = isInteger<Integer_type> >
465 static constexpr Element _get_value(Integer_type e) {
466 if constexpr (std::is_signed_v<Integer_type>){
467 if (e < -static_cast<Integer_type>(productOfAllCharacteristics_)) e = e % productOfAllCharacteristics_;
468 if (e < 0) return e += productOfAllCharacteristics_;
469 return e < static_cast<Integer_type>(productOfAllCharacteristics_) ? e : e % productOfAllCharacteristics_;
470 } else {
471 return e < productOfAllCharacteristics_ ? e : e % productOfAllCharacteristics_;
472 }
473 }
474
475 Element element_;
476 static inline const std::vector<Characteristic> primes_ = []() {
477 std::vector<Characteristic> res;
478 for (Characteristic i = minimum; i <= maximum; ++i) {
479 if (_is_prime(i)) {
480 res.push_back(i);
481 }
482 }
483 return res;
484 }();
485 static inline constexpr Characteristic productOfAllCharacteristics_ = []() {
486 Characteristic res = 1;
487 for (Characteristic i = minimum; i <= maximum; ++i) {
488 if (_is_prime(i)) {
489 res *= i;
490 }
491 }
492 return res;
493 }();
494 static inline const std::vector<Characteristic> partials_ = []() {
495 std::vector<Characteristic> res;
496
497 if (productOfAllCharacteristics_ == 1) return res;
498
499 for (Characteristic i = 0; i < primes_.size(); ++i) {
500 Characteristic p = primes_[i];
501 Characteristic base = productOfAllCharacteristics_ / p;
502 Characteristic exp = p - 1;
503 res.push_back(1);
504
505 while (exp > 0) {
506 // If exp is odd, multiply with result
507 if (exp & 1) res.back() = _multiply(res.back(), base);
508 // y must be even now
509 exp = exp >> 1;
510 base = _multiply(base, base);
511 }
512 }
513
514 return res;
515 }();
516 // If I understood the paper well, multiplicativeID_ always equals to 1. But in Clement's code,
517 // multiplicativeID_ is computed (see commented lambda function below). TODO: verify with Clement.
518 static inline constexpr Element multiplicativeID_ = 1; /*= [](){
519 unsigned int res = 0;
520 for (unsigned int i = 0; i < partials_.size(); ++i){
521 res = (res + partials_[i]) % productOfAllCharacteristics_;
522 }
523
524 return res;
525 }();*/
526};
527
528} // namespace persistence_fields
529} // namespace Gudhi
530
531#endif // MATRIX_FIELD_MULTI_SMALL_H_
Class representing an element of a multi-field, such that the product of all characteristics fits int...
Definition Multi_field_small.h:43
friend Multi_field_element_with_small_characteristics operator-(Multi_field_element_with_small_characteristics f1, Multi_field_element_with_small_characteristics const &f2)
operator-
Definition Multi_field_small.h:143
friend void operator+=(Multi_field_element_with_small_characteristics &f, const Integer_type &v)
operator+=
Definition Multi_field_small.h:108
Multi_field_element_with_small_characteristics & operator=(Multi_field_element_with_small_characteristics other)
Assign operator.
Definition Multi_field_small.h:278
friend void operator-=(Multi_field_element_with_small_characteristics &f, const Integer_type &v)
operator-=
Definition Multi_field_small.h:154
friend void operator*=(Multi_field_element_with_small_characteristics &f1, Multi_field_element_with_small_characteristics const &f2)
operator*=
Definition Multi_field_small.h:181
friend bool operator!=(const Integer_type v, const Multi_field_element_with_small_characteristics &f)
operator!=
Definition Multi_field_small.h:262
friend void operator-=(Multi_field_element_with_small_characteristics &f1, Multi_field_element_with_small_characteristics const &f2)
operator-=
Definition Multi_field_small.h:136
Element get_value() const
Returns the value of the element.
Definition Multi_field_small.h:385
friend bool operator==(const Integer_type v, const Multi_field_element_with_small_characteristics &f)
operator==
Definition Multi_field_small.h:237
Multi_field_element_with_small_characteristics()
Default constructor. Sets the element to 0.
Definition Multi_field_small.h:53
friend void swap(Multi_field_element_with_small_characteristics &f1, Multi_field_element_with_small_characteristics &f2)
Swap operator.
Definition Multi_field_small.h:295
friend Integer_type operator-(const Integer_type &v, const Multi_field_element_with_small_characteristics &f)
operator-
Definition Multi_field_small.h:174
std::pair< Multi_field_element_with_small_characteristics, Characteristic > get_partial_inverse(Characteristic productOfCharacteristics) const
Returns the inverse of the element with respect to a sub-product of the characteristics in the multi-...
Definition Multi_field_small.h:320
friend Multi_field_element_with_small_characteristics operator*(Multi_field_element_with_small_characteristics f, const Integer_type &v)
operator*
Definition Multi_field_small.h:208
friend Integer_type operator+(const Integer_type &v, Multi_field_element_with_small_characteristics f)
operator+
Definition Multi_field_small.h:128
Multi_field_element_with_small_characteristics get_inverse() const
Returns the inverse of the element in the multi-field, see .
Definition Multi_field_small.h:310
friend Multi_field_element_with_small_characteristics operator+(Multi_field_element_with_small_characteristics f1, Multi_field_element_with_small_characteristics const &f2)
operator+
Definition Multi_field_small.h:97
static Multi_field_element_with_small_characteristics get_partial_multiplicative_identity(const Characteristic &productOfCharacteristics)
Returns the partial multiplicative identity of the multi-field from the given product....
Definition Multi_field_small.h:360
Multi_field_element_with_small_characteristics(Integer_type element)
Constructor setting the element to the given value.
Definition Multi_field_small.h:65
Multi_field_element_with_small_characteristics(const Multi_field_element_with_small_characteristics &toCopy)
Copy constructor.
Definition Multi_field_small.h:77
friend Multi_field_element_with_small_characteristics operator-(Multi_field_element_with_small_characteristics f, const Integer_type &v)
operator-
Definition Multi_field_small.h:163
Unsigned_integer_type Element
Definition Multi_field_small.h:45
friend Multi_field_element_with_small_characteristics operator*(Multi_field_element_with_small_characteristics f1, Multi_field_element_with_small_characteristics const &f2)
operator*
Definition Multi_field_small.h:188
Multi_field_element_with_small_characteristics(Multi_field_element_with_small_characteristics &&toMove) noexcept
Move constructor.
Definition Multi_field_small.h:84
friend bool operator==(const Multi_field_element_with_small_characteristics &f, const Integer_type v)
operator==
Definition Multi_field_small.h:246
friend void operator+=(Multi_field_element_with_small_characteristics &f1, Multi_field_element_with_small_characteristics const &f2)
operator+=
Definition Multi_field_small.h:90
static Multi_field_element_with_small_characteristics get_additive_identity()
Returns the additive identity of a field.
Definition Multi_field_small.h:342
friend bool operator!=(const Multi_field_element_with_small_characteristics &f, const Integer_type v)
operator!=
Definition Multi_field_small.h:271
friend bool operator!=(const Multi_field_element_with_small_characteristics &f1, const Multi_field_element_with_small_characteristics &f2)
operator!=
Definition Multi_field_small.h:252
static Multi_field_element_with_small_characteristics get_multiplicative_identity()
Returns the multiplicative identity of a field.
Definition Multi_field_small.h:350
static constexpr Characteristic get_characteristic()
Returns the product of all characteristics.
Definition Multi_field_small.h:378
friend Integer_type operator*(const Integer_type &v, Multi_field_element_with_small_characteristics f)
operator*
Definition Multi_field_small.h:219
friend void operator*=(Multi_field_element_with_small_characteristics &f, const Integer_type &v)
operator*=
Definition Multi_field_small.h:199
friend Multi_field_element_with_small_characteristics operator+(Multi_field_element_with_small_characteristics f, const Integer_type &v)
operator+
Definition Multi_field_small.h:117
friend bool operator==(const Multi_field_element_with_small_characteristics &f1, const Multi_field_element_with_small_characteristics &f2)
operator==
Definition Multi_field_small.h:227
Multi_field_element_with_small_characteristics & operator=(const Integer_type &value)
Assign operator.
Definition Multi_field_small.h:288
Gudhi namespace.
Definition SimplicialComplexForAlpha.h:14