Loading...
Searching...
No Matches
Zp_field_operators.h
Go to the documentation of this file.
/* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT.
* See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details.
* Author(s): Hannah Schreiber
*
* Copyright (C) 2024 Inria
*
* Modification(s):
* - YYYY/MM Author: Description of the modification
*/
#ifndef MATRIX_FIELD_ZP_OPERATOR_H_
#define MATRIX_FIELD_ZP_OPERATOR_H_
#include <stdexcept>
#include <utility>
#include <vector>
#include <limits.h>
namespace Gudhi {
namespace persistence_fields {
template <typename Unsigned_integer_type = unsigned int,
class = std::enable_if_t<std::is_unsigned_v<Unsigned_integer_type> > >
class Zp_field_operators
{
public:
using Element = Unsigned_integer_type;
using Characteristic = Element;
template <class T>
using isSignedInteger = std::enable_if_t<std::is_signed_v<T> >;
Zp_field_operators(Characteristic characteristic = 0) : characteristic_(0) {
if (characteristic != 0) set_characteristic(characteristic);
}
Zp_field_operators(const Zp_field_operators& toCopy)
: characteristic_(toCopy.characteristic_), inverse_(toCopy.inverse_) {}
Zp_field_operators(Zp_field_operators&& toMove) noexcept
: characteristic_(std::exchange(toMove.characteristic_, 0)), inverse_(std::move(toMove.inverse_)) {}
void set_characteristic(Characteristic characteristic) {
if (characteristic <= 1)
throw std::invalid_argument("Characteristic must be strictly positive and a prime number.");
inverse_.resize(characteristic);
inverse_[0] = 0;
for (unsigned int i = 1; i < characteristic; ++i) {
unsigned int inv = 1;
unsigned int mult = inv * i;
while ((mult % characteristic) != 1) {
++inv;
if (mult == characteristic) throw std::invalid_argument("Characteristic must be a prime number.");
mult = inv * i;
}
inverse_[i] = inv;
}
characteristic_ = characteristic;
}
const Characteristic& get_characteristic() const { return characteristic_; }
Element get_value(Element e) const { return e < characteristic_ ? e : e % characteristic_; }
template <typename Signed_integer_type, class = isSignedInteger<Signed_integer_type> >
Element get_value(Signed_integer_type e) const {
if (e < -static_cast<Signed_integer_type>(characteristic_)) e = e % characteristic_;
if (e < 0) return e += characteristic_;
return e < static_cast<Signed_integer_type>(characteristic_) ? e : e % characteristic_;
}
Element add(Element e1, Element e2) const {
return _add(get_value(e1), get_value(e2), characteristic_);
}
void add_inplace(Element& e1, Element e2) const {
e1 = _add(get_value(e1), get_value(e2), characteristic_);
}
Element subtract(Element e1, Element e2) const {
return _subtract(get_value(e1), get_value(e2), characteristic_);
}
void subtract_inplace_front(Element& e1, Element e2) const {
e1 = _subtract(get_value(e1), get_value(e2), characteristic_);
}
void subtract_inplace_back(Element e1, Element& e2) const {
e2 = _subtract(get_value(e1), get_value(e2), characteristic_);
}
Element multiply(Element e1, Element e2) const {
return _multiply(get_value(e1), get_value(e2), characteristic_);
}
void multiply_inplace(Element& e1, Element e2) const {
e1 = _multiply(get_value(e1), get_value(e2), characteristic_);
}
Element multiply_and_add(Element e, Element m, Element a) const { return get_value(e * m + a); }
void multiply_and_add_inplace_front(Element& e, Element m, Element a) const {
e = get_value(e * m + a);
}
void multiply_and_add_inplace_back(Element e, Element m, Element& a) const {
a = get_value(e * m + a);
}
Element add_and_multiply(Element e, Element a, Element m) const { return get_value((e + a) * m); }
void add_and_multiply_inplace_front(Element& e, Element a, Element m) const {
e = get_value((e + a) * m);
}
void add_and_multiply_inplace_back(Element e, Element a, Element& m) const {
m = get_value((e + a) * m);
}
bool are_equal(Element e1, Element e2) const { return get_value(e1) == get_value(e2); }
Element get_inverse(Element e) const { return inverse_[get_value(e)]; }
std::pair<Element, Characteristic> get_partial_inverse(Element e,
Characteristic productOfCharacteristics) const {
return {get_inverse(e), productOfCharacteristics};
}
static constexpr Element get_additive_identity() { return 0; }
static constexpr Element get_multiplicative_identity() { return 1; }
static constexpr Element get_partial_multiplicative_identity(
[[maybe_unused]] Characteristic productOfCharacteristics) {
return 1;
}
// static constexpr bool handles_only_z2() { return false; }
Zp_field_operators& operator=(Zp_field_operators other) {
std::swap(characteristic_, other.characteristic_);
inverse_.swap(other.inverse_);
return *this;
}
friend void swap(Zp_field_operators& f1, Zp_field_operators& f2) {
std::swap(f1.characteristic_, f2.characteristic_);
f1.inverse_.swap(f2.inverse_);
}
private:
Characteristic characteristic_;
std::vector<Element> inverse_;
static Element _add(Element e1, Element e2, Characteristic characteristic) {
if (UINT_MAX - e1 < e2) {
// automatic unsigned integer overflow behaviour will make it work
e1 += e2;
e1 -= characteristic;
return e1;
}
e1 += e2;
if (e1 >= characteristic) e1 -= characteristic;
return e1;
}
static Element _subtract(Element e1, Element e2, Characteristic characteristic) {
if (e1 < e2) {
e1 += characteristic;
}
e1 -= e2;
return e1;
}
static Element _multiply(Element e1, Element e2, Characteristic characteristic) {
unsigned int a = e1;
e1 = 0;
unsigned int temp_b;
while (a != 0) {
if (a & 1) {
if (e2 >= characteristic - e1) e1 -= characteristic;
e1 += e2;
}
a >>= 1;
temp_b = e2;
if (e2 >= characteristic - e2) temp_b -= characteristic;
e2 += temp_b;
}
return e1;
}
};
} // namespace persistence_fields
} // namespace Gudhi
#endif // MATRIX_FIELD_ZP_OPERATOR_H_
Gudhi::persistence_fields::Zp_field_operators::multiply_and_add_inplace_back
void multiply_and_add_inplace_back(Element e, Element m, Element &a) const
Multiplies the first element with the second one and adds the third one, that is (e * m + a) % charac...
Definition Zp_field_operators.h:237
Gudhi::persistence_fields::Zp_field_operators::get_characteristic
const Characteristic & get_characteristic() const
Returns the current characteristic.
Definition Zp_field_operators.h:101
Gudhi::persistence_fields::Zp_field_operators::Zp_field_operators
Zp_field_operators(const Zp_field_operators &toCopy)
Copy constructor.
Definition Zp_field_operators.h:62
Gudhi::persistence_fields::Zp_field_operators::get_inverse
Element get_inverse(Element e) const
Returns the inverse of the given element in the field.
Definition Zp_field_operators.h:297
Gudhi::persistence_fields::Zp_field_operators::multiply_and_add
Element multiply_and_add(Element e, Element m, Element a) const
Multiplies the first element with the second one and adds the third one. Returns the result in the fi...
Definition Zp_field_operators.h:212
Gudhi::persistence_fields::Zp_field_operators::Zp_field_operators
Zp_field_operators(Zp_field_operators &&toMove) noexcept
Move constructor.
Definition Zp_field_operators.h:69
Gudhi::persistence_fields::Zp_field_operators::get_value
Element get_value(Element e) const
Returns the value of an integer in the field. That is the positive value of the integer modulo the cu...
Definition Zp_field_operators.h:110
Gudhi::persistence_fields::Zp_field_operators::add
Element add(Element e1, Element e2) const
Returns the sum of two elements in the field.
Definition Zp_field_operators.h:133
Gudhi::persistence_fields::Zp_field_operators::set_characteristic
void set_characteristic(Characteristic characteristic)
Sets the characteristic of the field.
Definition Zp_field_operators.h:77
Gudhi::persistence_fields::Zp_field_operators::Characteristic
Element Characteristic
Definition Zp_field_operators.h:44
Gudhi::persistence_fields::Zp_field_operators::get_partial_inverse
std::pair< Element, Characteristic > get_partial_inverse(Element e, Characteristic productOfCharacteristics) const
For interface purposes with multi-fields. Returns the inverse together with the second argument.
Definition Zp_field_operators.h:305
Gudhi::persistence_fields::Zp_field_operators::add_and_multiply_inplace_back
void add_and_multiply_inplace_back(Element e, Element a, Element &m) const
Adds the first element to the second one and multiplies the third one with it, that is ((e + a) * m) ...
Definition Zp_field_operators.h:277
Gudhi::persistence_fields::Zp_field_operators::Zp_field_operators
Zp_field_operators(Characteristic characteristic=0)
Default constructor. If a non-zero characteristic is given, initializes the field with it....
Definition Zp_field_operators.h:54
Gudhi::persistence_fields::Zp_field_operators::Element
Unsigned_integer_type Element
Definition Zp_field_operators.h:43
Gudhi::persistence_fields::Zp_field_operators::get_multiplicative_identity
static constexpr Element get_multiplicative_identity()
Returns the multiplicative identity of the field.
Definition Zp_field_operators.h:321
Gudhi::persistence_fields::Zp_field_operators::are_equal
bool are_equal(Element e1, Element e2) const
Returns true if the two given elements are equal in the field, false otherwise.
Definition Zp_field_operators.h:289
Gudhi::persistence_fields::Zp_field_operators::add_and_multiply_inplace_front
void add_and_multiply_inplace_front(Element &e, Element a, Element m) const
Adds the first element to the second one and multiplies the third one with it, that is ((e + a) * m) ...
Definition Zp_field_operators.h:264
Gudhi::persistence_fields::Zp_field_operators::get_additive_identity
static constexpr Element get_additive_identity()
Returns the additive identity of the field.
Definition Zp_field_operators.h:315
Gudhi::persistence_fields::Zp_field_operators::subtract_inplace_back
void subtract_inplace_back(Element e1, Element &e2) const
Stores in the second element the subtraction in the field of the first element by the second element,...
Definition Zp_field_operators.h:176
Gudhi::persistence_fields::Zp_field_operators::get_value
Element get_value(Signed_integer_type e) const
Returns the value of an integer in the field. That is the positive value of the integer modulo the cu...
Definition Zp_field_operators.h:120
Gudhi::persistence_fields::Zp_field_operators::operator=
Zp_field_operators & operator=(Zp_field_operators other)
Assign operator.
Definition Zp_field_operators.h:338
Gudhi::persistence_fields::Zp_field_operators::swap
friend void swap(Zp_field_operators &f1, Zp_field_operators &f2)
Swap operator.
Definition Zp_field_operators.h:346
Gudhi::persistence_fields::Zp_field_operators::get_partial_multiplicative_identity
static constexpr Element get_partial_multiplicative_identity(Characteristic productOfCharacteristics)
For interface purposes with multi-fields. Returns the multiplicative identity of the field.
Definition Zp_field_operators.h:328
Gudhi::persistence_fields::Zp_field_operators::multiply
Element multiply(Element e1, Element e2) const
Returns the multiplication of two elements in the field.
Definition Zp_field_operators.h:187
Gudhi::persistence_fields::Zp_field_operators::subtract
Element subtract(Element e1, Element e2) const
Returns the subtraction in the field of the first element by the second element.
Definition Zp_field_operators.h:155
Gudhi::persistence_fields::Zp_field_operators::multiply_and_add_inplace_front
void multiply_and_add_inplace_front(Element &e, Element m, Element a) const
Multiplies the first element with the second one and adds the third one, that is (e * m + a) % charac...
Definition Zp_field_operators.h:224
Gudhi::persistence_fields::Zp_field_operators::multiply_inplace
void multiply_inplace(Element &e1, Element e2) const
Stores in the first element the multiplication of two given elements in the field,...
Definition Zp_field_operators.h:198
Gudhi::persistence_fields::Zp_field_operators::subtract_inplace_front
void subtract_inplace_front(Element &e1, Element e2) const
Stores in the first element the subtraction in the field of the first element by the second element,...
Definition Zp_field_operators.h:166
Gudhi::persistence_fields::Zp_field_operators::add_and_multiply
Element add_and_multiply(Element e, Element a, Element m) const
Adds the first element to the second one and multiplies the third one with it. Returns the result in ...
Definition Zp_field_operators.h:252
Gudhi::persistence_fields::Zp_field_operators::add_inplace
void add_inplace(Element &e1, Element e2) const
Stores in the first element the sum of two given elements in the field, that is (e1 + e2) % character...
Definition Zp_field_operators.h:144
Gudhi::persistence_fields
Field namespace.
Definition Intro_field_elements_and_operators.h:16
Gudhi
Gudhi namespace.
Definition SimplicialComplexForAlpha.h:14