Zp_field.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
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_ZP_H_
18#define MATRIX_FIELD_ZP_H_
19
20#include <utility>
21#include <array>
22#include <limits.h>
23
24namespace Gudhi {
25namespace persistence_fields {
26
37template <unsigned int characteristic, typename Unsigned_integer_type = unsigned int,
38 class = std::enable_if_t<std::is_unsigned_v<Unsigned_integer_type> > >
40 public:
41 using Element = Unsigned_integer_type;
43 template <class T>
44 using isInteger = std::enable_if_t<std::is_integral_v<T> >;
45
49 Zp_field_element() : element_(0) { static_assert(_is_prime(), "Characteristic has to be a prime number."); }
56 template <typename Integer_type, class = isInteger<Integer_type> >
57 Zp_field_element(Integer_type element) : element_(_get_value(element)) {
58 static_assert(_is_prime(), "Characteristic has to be a prime number.");
59 }
65 Zp_field_element(const Zp_field_element& toCopy) : element_(toCopy.element_) {}
71 Zp_field_element(Zp_field_element&& toMove) noexcept : element_(std::exchange(toMove.element_, 0)) {}
72
76 friend void operator+=(Zp_field_element& f1, const Zp_field_element& f2) {
77 f1.element_ = Zp_field_element::_add(f1.element_, f2.element_);
78 }
83 f1 += f2;
84 return f1;
85 }
89 template <typename Integer_type, class = isInteger<Integer_type> >
90 friend void operator+=(Zp_field_element& f, const Integer_type& v) {
91 f.element_ = Zp_field_element::_add(f.element_, _get_value(v));
92 }
98 template <typename Integer_type, class = isInteger<Integer_type> >
99 friend Zp_field_element operator+(Zp_field_element f, const Integer_type& v) {
100 f += v;
101 return f;
102 }
108 template <typename Integer_type, class = isInteger<Integer_type> >
109 friend Integer_type operator+(const Integer_type& v, Zp_field_element f) {
110 f += v;
111 return f.element_;
112 }
113
117 friend void operator-=(Zp_field_element& f1, const Zp_field_element& f2) {
118 f1.element_ = Zp_field_element::_subtract(f1.element_, f2.element_);
119 }
124 f1 -= f2;
125 return f1;
126 }
130 template <typename Integer_type, class = isInteger<Integer_type> >
131 friend void operator-=(Zp_field_element& f, const Integer_type& v) {
132 f.element_ = Zp_field_element::_subtract(f.element_, _get_value(v));
133 }
139 template <typename Integer_type, class = isInteger<Integer_type> >
140 friend Zp_field_element operator-(Zp_field_element f, const Integer_type& v) {
141 f -= v;
142 return f;
143 }
149 template <typename Integer_type, class = isInteger<Integer_type> >
150 friend Integer_type operator-(const Integer_type& v, const Zp_field_element& f) {
151 return Zp_field_element::_subtract(_get_value(v), f.element_);
152 }
153
157 friend void operator*=(Zp_field_element& f1, const Zp_field_element& f2) {
158 f1.element_ = Zp_field_element::_multiply(f1.element_, f2.element_);
159 }
164 f1 *= f2;
165 return f1;
166 }
170 template <typename Integer_type, class = isInteger<Integer_type> >
171 friend void operator*=(Zp_field_element& f, const Integer_type& v) {
172 f.element_ = Zp_field_element::_multiply(f.element_, _get_value(v));
173 }
179 template <typename Integer_type, class = isInteger<Integer_type> >
180 friend Zp_field_element operator*(Zp_field_element f, const Integer_type& v) {
181 f *= v;
182 return f;
183 }
189 template <typename Integer_type, class = isInteger<Integer_type> >
190 friend Integer_type operator*(const Integer_type& v, Zp_field_element f) {
191 f *= v;
192 return f.element_;
193 }
194
198 friend bool operator==(const Zp_field_element& f1, const Zp_field_element& f2) {
199 return f1.element_ == f2.element_;
200 }
206 template <typename Integer_type, class = isInteger<Integer_type> >
207 friend bool operator==(const Integer_type& v, const Zp_field_element& f) {
208 return Zp_field_element::_get_value(v) == f.element_;
209 }
215 template <typename Integer_type, class = isInteger<Integer_type> >
216 friend bool operator==(const Zp_field_element& f, const Integer_type& v) {
217 return Zp_field_element::_get_value(v) == f.element_;
218 }
222 friend bool operator!=(const Zp_field_element& f1, const Zp_field_element& f2) { return !(f1 == f2); }
228 template <typename Integer_type, class = isInteger<Integer_type> >
229 friend bool operator!=(const Integer_type& v, const Zp_field_element& f) {
230 return !(v == f);
231 }
237 template <typename Integer_type, class = isInteger<Integer_type> >
238 friend bool operator!=(const Zp_field_element& f, const Integer_type& v) {
239 return !(v == f);
240 }
241
246 std::swap(element_, other.element_);
247 return *this;
248 }
254 template <typename Integer_type, class = isInteger<Integer_type> >
255 Zp_field_element& operator=(const Integer_type& value) {
256 element_ = _get_value(value);
257 return *this;
258 }
262 friend void swap(Zp_field_element& f1, Zp_field_element& f2) { std::swap(f1.element_, f2.element_); }
263
267 operator unsigned int() const { return element_; }
268
275 if (element_ != 0 && inverse_[element_] == 0) { // initialize everything at instantiation instead?
276 inverse_[element_] = _get_inverse(element_);
277 }
278
279 return Zp_field_element<characteristic>(inverse_[element_]);
280 }
287 std::pair<Zp_field_element, unsigned int> get_partial_inverse(unsigned int productOfCharacteristics) const {
288 return {get_inverse(), productOfCharacteristics};
289 }
290
309 static Zp_field_element get_partial_multiplicative_identity([[maybe_unused]] unsigned int productOfCharacteristics) {
311 }
317 static constexpr unsigned int get_characteristic() { return characteristic; }
318
324 Element get_value() const { return element_; }
325
326 // static constexpr bool handles_only_z2() { return false; }
327
328 private:
329 Element element_;
330 static inline std::array<unsigned int, characteristic> inverse_;
332 static Element _add(Element element, Element v) {
333 if (UINT_MAX - element < v) {
334 // automatic unsigned integer overflow behaviour will make it work
335 element += v;
336 element -= characteristic;
337 return element;
338 }
339
340 element += v;
341 if (element >= characteristic) element -= characteristic;
342
343 return element;
344 }
345 static Element _subtract(Element element, Element v) {
346 if (element < v) {
347 element += characteristic;
348 }
349 element -= v;
350
351 return element;
352 }
353 static Element _multiply(Element element, Element v) {
354 Element a = element;
355 element = 0;
356 Element temp_b;
357
358 while (a != 0) {
359 if (a & 1) {
360 if (v >= characteristic - element) element -= characteristic;
361 element += v;
362 }
363 a >>= 1;
364
365 temp_b = v;
366 if (v >= characteristic - v) temp_b -= characteristic;
367 v += temp_b;
368 }
369
370 return element;
371 }
372 static int _get_inverse(Element element) {
373 // to solve: Ax + My = 1
374 int M = characteristic;
375 int A = element;
376 int y = 0, x = 1;
377 // extended euclidean division
378 while (A > 1) {
379 int quotient = A / M;
380 int temp = M;
381
382 M = A % M, A = temp;
383 temp = y;
384
385 y = x - quotient * y;
386 x = temp;
387 }
388
389 if (x < 0) x += characteristic;
390
391 return x;
392 }
393
394 template <typename Integer_type, class = isInteger<Integer_type> >
395 static constexpr Element _get_value(Integer_type e) {
396 if constexpr (std::is_signed_v<Integer_type>) {
397 if (e < -static_cast<Integer_type>(characteristic)) e = e % characteristic;
398 if (e < 0) return e += characteristic;
399 return e < static_cast<Integer_type>(characteristic) ? e : e % characteristic;
400 } else {
401 return e < characteristic ? e : e % characteristic;
402 }
403 }
404
405 static constexpr bool _is_prime() {
406 if (characteristic <= 1) return false;
407 if (characteristic <= 3) return true;
408 if (characteristic % 2 == 0 || characteristic % 3 == 0) return false;
409
410 for (long i = 5; i * i <= characteristic; i = i + 6)
411 if (characteristic % i == 0 || characteristic % (i + 2) == 0) return false;
412
413 return true;
414 }
415};
416
417} // namespace persistence_fields
418} // namespace Gudhi
419
420#endif // MATRIX_FIELD_ZP_H_
Class representing an element of the field for any prime number .
Definition: Zp_field.h:39
Zp_field_element(Integer_type element)
Constructor setting the element to the given value.
Definition: Zp_field.h:57
Zp_field_element & operator=(Zp_field_element other)
Assign operator.
Definition: Zp_field.h:245
friend Zp_field_element operator-(Zp_field_element f1, const Zp_field_element &f2)
operator-
Definition: Zp_field.h:123
Zp_field_element & operator=(const Integer_type &value)
Assign operator.
Definition: Zp_field.h:255
friend Zp_field_element operator-(Zp_field_element f, const Integer_type &v)
operator-
Definition: Zp_field.h:140
friend Integer_type operator*(const Integer_type &v, Zp_field_element f)
operator*
Definition: Zp_field.h:190
static Zp_field_element get_multiplicative_identity()
Returns the multiplicative identity of the field.
Definition: Zp_field.h:302
Zp_field_element get_inverse() const
Returns the inverse of the element in the field.
Definition: Zp_field.h:274
Unsigned_integer_type Element
Definition: Zp_field.h:41
friend Integer_type operator+(const Integer_type &v, Zp_field_element f)
operator+
Definition: Zp_field.h:109
friend bool operator!=(const Integer_type &v, const Zp_field_element &f)
operator!=
Definition: Zp_field.h:229
friend void operator+=(Zp_field_element &f, const Integer_type &v)
operator+=
Definition: Zp_field.h:90
friend void swap(Zp_field_element &f1, Zp_field_element &f2)
Swap operator.
Definition: Zp_field.h:262
friend Zp_field_element operator*(Zp_field_element f, const Integer_type &v)
operator*
Definition: Zp_field.h:180
friend void operator-=(Zp_field_element &f1, const Zp_field_element &f2)
operator-=
Definition: Zp_field.h:117
friend bool operator==(const Zp_field_element &f1, const Zp_field_element &f2)
operator==
Definition: Zp_field.h:198
Element get_value() const
Returns the value of the element.
Definition: Zp_field.h:324
friend void operator*=(Zp_field_element &f, const Integer_type &v)
operator*=
Definition: Zp_field.h:171
friend void operator*=(Zp_field_element &f1, const Zp_field_element &f2)
operator*=
Definition: Zp_field.h:157
friend Integer_type operator-(const Integer_type &v, const Zp_field_element &f)
operator-
Definition: Zp_field.h:150
Zp_field_element(Zp_field_element &&toMove) noexcept
Move constructor.
Definition: Zp_field.h:71
std::pair< Zp_field_element, unsigned int > get_partial_inverse(unsigned int productOfCharacteristics) const
For interface purposes with multi-fields. Returns the inverse together with the argument.
Definition: Zp_field.h:287
static Zp_field_element get_partial_multiplicative_identity(unsigned int productOfCharacteristics)
For interface purposes with multi-fields. Returns the multiplicative identity of the field.
Definition: Zp_field.h:309
friend Zp_field_element operator*(Zp_field_element f1, const Zp_field_element &f2)
operator*
Definition: Zp_field.h:163
Zp_field_element(const Zp_field_element &toCopy)
Copy constructor.
Definition: Zp_field.h:65
friend Zp_field_element operator+(Zp_field_element f, const Integer_type &v)
operator+
Definition: Zp_field.h:99
friend void operator-=(Zp_field_element &f, const Integer_type &v)
operator-=
Definition: Zp_field.h:131
friend bool operator==(const Zp_field_element &f, const Integer_type &v)
operator==
Definition: Zp_field.h:216
Zp_field_element()
Default constructor. Sets the element to 0.
Definition: Zp_field.h:49
friend bool operator!=(const Zp_field_element &f, const Integer_type &v)
operator!=
Definition: Zp_field.h:238
static Zp_field_element get_additive_identity()
Returns the additive identity of the field.
Definition: Zp_field.h:296
static constexpr unsigned int get_characteristic()
Returns the current characteristic.
Definition: Zp_field.h:317
friend bool operator==(const Integer_type &v, const Zp_field_element &f)
operator==
Definition: Zp_field.h:207
friend Zp_field_element operator+(Zp_field_element f1, const Zp_field_element &f2)
operator+
Definition: Zp_field.h:82
friend bool operator!=(const Zp_field_element &f1, const Zp_field_element &f2)
operator!=
Definition: Zp_field.h:222
Element Characteristic
Definition: Zp_field.h:42
friend void operator+=(Zp_field_element &f1, const Zp_field_element &f2)
operator+=
Definition: Zp_field.h:76
Gudhi namespace.
Definition: SimplicialComplexForAlpha.h:14