Loading...
Searching...
No Matches
Multi_field_small_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, Clément Maria
*
* Copyright (C) 2022-24 Inria
*
* Modification(s):
* - YYYY/MM Author: Description of the modification
*/
#ifndef MATRIX_FIELD_MULTI_SMALL_OPERATORS_H_
#define MATRIX_FIELD_MULTI_SMALL_OPERATORS_H_
#include <utility>
#include <vector>
#include <limits.h>
#include <stdexcept>
#include <numeric>
namespace Gudhi {
namespace persistence_fields {
class Multi_field_operators_with_small_characteristics
{
public:
using Element = unsigned int;
using Characteristic = Element;
Multi_field_operators_with_small_characteristics() : productOfAllCharacteristics_(0) /* , multiplicativeID_(1) */
{}
Multi_field_operators_with_small_characteristics(int minCharacteristic, int maxCharacteristic)
: productOfAllCharacteristics_(0) //, multiplicativeID_(1)
{
set_characteristic(minCharacteristic, maxCharacteristic);
}
Multi_field_operators_with_small_characteristics(const Multi_field_operators_with_small_characteristics& toCopy)
: primes_(toCopy.primes_),
productOfAllCharacteristics_(toCopy.productOfAllCharacteristics_),
partials_(toCopy.partials_) /* ,
multiplicativeID_(toCopy.multiplicativeID_) */
{}
Multi_field_operators_with_small_characteristics(Multi_field_operators_with_small_characteristics&& toMove) noexcept
: primes_(std::move(toMove.primes_)),
productOfAllCharacteristics_(std::move(toMove.productOfAllCharacteristics_)),
partials_(std::move(toMove.partials_)) /* ,
multiplicativeID_(std::move(toMove.multiplicativeID_)) */
{}
void set_characteristic(int minimum, int maximum) {
if (maximum < 2) throw std::invalid_argument("Characteristic must be strictly positive");
if (minimum > maximum) throw std::invalid_argument("The given interval is not valid.");
if (minimum == maximum && !_is_prime(minimum))
throw std::invalid_argument("The given interval does not contain a prime number.");
productOfAllCharacteristics_ = 1;
primes_.clear();
for (unsigned int i = minimum; i <= static_cast<unsigned int>(maximum); ++i) {
if (_is_prime(i)) {
primes_.push_back(i);
productOfAllCharacteristics_ *= i;
}
}
if (primes_.empty()) throw std::invalid_argument("The given interval does not contain a prime number.");
partials_.resize(primes_.size());
for (unsigned int i = 0; i < primes_.size(); ++i) {
unsigned int p = primes_[i];
Characteristic base = productOfAllCharacteristics_ / p;
unsigned int exp = p - 1;
partials_[i] = 1;
while (exp > 0) {
// If exp is odd, multiply with result
if (exp & 1) partials_[i] = _multiply(partials_[i], base, productOfAllCharacteristics_);
// y must be even now
exp = exp >> 1; // y = y/2
base = _multiply(base, base, productOfAllCharacteristics_);
}
}
// If I understood the paper well, multiplicativeID_ always equals to 1. But in Clement's code,
// multiplicativeID_ is computed (see commented loop below). TODO: verify with Clement.
// for (unsigned int i = 0; i < partials_.size(); ++i){
// multiplicativeID_ = (multiplicativeID_ + partials_[i]) % productOfAllCharacteristics_;
// }
}
const Characteristic& get_characteristic() const { return productOfAllCharacteristics_; }
Element get_value(Element e) const {
return e < productOfAllCharacteristics_ ? e : e % productOfAllCharacteristics_;
}
Element add(Element e1, Element e2) const {
return _add(get_value(e1), get_value(e2), productOfAllCharacteristics_);
}
void add_inplace(Element& e1, Element e2) const {
e1 = _add(get_value(e1), get_value(e2), productOfAllCharacteristics_);
}
Element subtract(Element e1, Element e2) const {
return _subtract(get_value(e1), get_value(e2), productOfAllCharacteristics_);
}
void subtract_inplace_front(Element& e1, Element e2) const {
e1 = _subtract(get_value(e1), get_value(e2), productOfAllCharacteristics_);
}
void subtract_inplace_back(Element e1, Element& e2) const {
e2 = _subtract(get_value(e1), get_value(e2), productOfAllCharacteristics_);
}
Element multiply(Element e1, Element e2) const {
return _multiply(get_value(e1), get_value(e2), productOfAllCharacteristics_);
}
void multiply_inplace(Element& e1, Element e2) const {
e1 = _multiply(get_value(e1), get_value(e2), productOfAllCharacteristics_);
}
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(const Element& e) const {
return get_partial_inverse(e, productOfAllCharacteristics_).first;
}
std::pair<Element, Characteristic> get_partial_inverse(
const Element& e, const Characteristic& productOfCharacteristics) const {
Characteristic gcd = std::gcd(e, productOfAllCharacteristics_);
if (gcd == productOfCharacteristics) return {0, get_multiplicative_identity()}; // partial inverse is 0
Characteristic QT = productOfCharacteristics / gcd;
const Characteristic inv_qt = _get_inverse(e, QT);
auto res = get_partial_multiplicative_identity(QT);
res = _multiply(res, inv_qt, productOfAllCharacteristics_);
return {res, QT};
}
static constexpr Element get_additive_identity() { return 0; }
static constexpr Element get_multiplicative_identity() { return 1; }
// static Element get_multiplicative_identity(){ return multiplicativeID_; }
Element get_partial_multiplicative_identity(const Characteristic& productOfCharacteristics) const {
if (productOfCharacteristics == 0) {
return get_multiplicative_identity();
}
Element multIdentity = 0;
for (unsigned int idx = 0; idx < primes_.size(); ++idx) {
if ((productOfCharacteristics % primes_[idx]) == 0) {
multIdentity = _add(multIdentity, partials_[idx], productOfAllCharacteristics_);
}
}
return multIdentity;
}
// static constexpr bool handles_only_z2() { return false; }
Multi_field_operators_with_small_characteristics& operator=(Multi_field_operators_with_small_characteristics other) {
primes_.swap(other.primes_);
productOfAllCharacteristics_ = other.productOfAllCharacteristics_;
partials_.swap(other.partials_);
return *this;
}
friend void swap(Multi_field_operators_with_small_characteristics& f1,
Multi_field_operators_with_small_characteristics& f2) {
f1.primes_.swap(f2.primes_);
std::swap(f1.productOfAllCharacteristics_, f2.productOfAllCharacteristics_);
f1.partials_.swap(f2.partials_);
}
private:
std::vector<unsigned int> primes_;
Characteristic productOfAllCharacteristics_;
std::vector<Characteristic> partials_;
// static inline constexpr unsigned int multiplicativeID_ = 1;
static Element _add(Element element, Element v, Characteristic characteristic);
static Element _subtract(Element element, Element v, Characteristic characteristic);
static Element _multiply(Element a, Element b, Characteristic characteristic);
static constexpr long int _get_inverse(Element element, Characteristic mod);
static constexpr bool _is_prime(const int p);
};
inline Multi_field_operators_with_small_characteristics::Element
Multi_field_operators_with_small_characteristics::_add(Element element, Element v,
Characteristic characteristic) {
if (UINT_MAX - element < v) {
// automatic unsigned integer overflow behaviour will make it work
element += v;
element -= characteristic;
return element;
}
element += v;
if (element >= characteristic) element -= characteristic;
return element;
}
inline Multi_field_operators_with_small_characteristics::Element
Multi_field_operators_with_small_characteristics::_subtract(Element element, Element v,
Characteristic characteristic) {
if (element < v) {
element += characteristic;
}
element -= v;
return element;
}
inline Multi_field_operators_with_small_characteristics::Element
Multi_field_operators_with_small_characteristics::_multiply(Element a, Element b,
Characteristic characteristic) {
Element res = 0;
Element temp_b = 0;
if (b < a) std::swap(a, b);
while (a != 0) {
if (a & 1) {
/* Add b to res, modulo m, without overflow */
if (b >= characteristic - res) res -= characteristic;
res += b;
}
a >>= 1;
/* Double b, modulo m */
temp_b = b;
if (b >= characteristic - b) temp_b -= characteristic;
b += temp_b;
}
return res;
}
inline constexpr long int Multi_field_operators_with_small_characteristics::_get_inverse(Element element,
Characteristic mod) {
// to solve: Ax + My = 1
Element M = mod;
Element A = element;
long int y = 0, x = 1;
// extended euclidean division
while (A > 1) {
int quotient = A / M;
int temp = M;
M = A % M, A = temp;
temp = y;
y = x - quotient * y;
x = temp;
}
if (x < 0) x += mod;
return x;
}
inline constexpr bool Multi_field_operators_with_small_characteristics::_is_prime(const int p) {
if (p <= 1) return false;
if (p <= 3) return true;
if (p % 2 == 0 || p % 3 == 0) return false;
for (long i = 5; i * i <= p; i = i + 6)
if (p % i == 0 || p % (i + 2) == 0) return false;
return true;
}
} // namespace persistence_fields
} // namespace Gudhi
#endif // MATRIX_FIELD_MULTI_SMALL_OPERATORS_H_
Gudhi::persistence_fields::Multi_field_operators_with_small_characteristics::subtract
Element subtract(Element e1, Element e2) const
Returns the subtraction in the field of the first element by the second element.
Definition Multi_field_small_operators.h:177
Gudhi::persistence_fields::Multi_field_operators_with_small_characteristics::Characteristic
Element Characteristic
Definition Multi_field_small_operators.h:41
Gudhi::persistence_fields::Multi_field_operators_with_small_characteristics::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 Multi_field_small_operators.h:234
Gudhi::persistence_fields::Multi_field_operators_with_small_characteristics::multiply
Element multiply(Element e1, Element e2) const
Returns the multiplication of two elements in the field.
Definition Multi_field_small_operators.h:209
Gudhi::persistence_fields::Multi_field_operators_with_small_characteristics::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 Multi_field_small_operators.h:276
Gudhi::persistence_fields::Multi_field_operators_with_small_characteristics::get_partial_multiplicative_identity
Element get_partial_multiplicative_identity(const Characteristic &productOfCharacteristics) const
Returns the partial multiplicative identity of the multi-field from the given product....
Definition Multi_field_small_operators.h:371
Gudhi::persistence_fields::Multi_field_operators_with_small_characteristics::get_value
Element get_value(Element e) const
Returns the value of an element in the field. That is the positive value of the integer modulo the cu...
Definition Multi_field_small_operators.h:144
Gudhi::persistence_fields::Multi_field_operators_with_small_characteristics::get_multiplicative_identity
static constexpr Element get_multiplicative_identity()
Returns the multiplicative identity of a field.
Definition Multi_field_small_operators.h:362
Gudhi::persistence_fields::Multi_field_operators_with_small_characteristics::Multi_field_operators_with_small_characteristics
Multi_field_operators_with_small_characteristics(const Multi_field_operators_with_small_characteristics &toCopy)
Copy constructor.
Definition Multi_field_small_operators.h:65
Gudhi::persistence_fields::Multi_field_operators_with_small_characteristics::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 Multi_field_small_operators.h:315
Gudhi::persistence_fields::Multi_field_operators_with_small_characteristics::Multi_field_operators_with_small_characteristics
Multi_field_operators_with_small_characteristics(int minCharacteristic, int maxCharacteristic)
Constructor setting the characteristics to all prime numbers between the two given integers....
Definition Multi_field_small_operators.h:55
Gudhi::persistence_fields::Multi_field_operators_with_small_characteristics::get_additive_identity
static constexpr Element get_additive_identity()
Returns the additive identity of a field.
Definition Multi_field_small_operators.h:356
Gudhi::persistence_fields::Multi_field_operators_with_small_characteristics::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 Multi_field_small_operators.h:289
Gudhi::persistence_fields::Multi_field_operators_with_small_characteristics::add
Element add(Element e1, Element e2) const
Returns the sum of two elements in the field.
Definition Multi_field_small_operators.h:155
Gudhi::persistence_fields::Multi_field_operators_with_small_characteristics::Multi_field_operators_with_small_characteristics
Multi_field_operators_with_small_characteristics(Multi_field_operators_with_small_characteristics &&toMove) noexcept
Move constructor.
Definition Multi_field_small_operators.h:76
Gudhi::persistence_fields::Multi_field_operators_with_small_characteristics::set_characteristic
void set_characteristic(int minimum, int maximum)
Set the characteristics of the field, which are stored in a single value as a product of all of them....
Definition Multi_field_small_operators.h:91
Gudhi::persistence_fields::Multi_field_operators_with_small_characteristics::get_partial_inverse
std::pair< Element, Characteristic > get_partial_inverse(const Element &e, const Characteristic &productOfCharacteristics) const
Returns the inverse of the given element in the multi-field corresponding to the given sub-product of...
Definition Multi_field_small_operators.h:335
Gudhi::persistence_fields::Multi_field_operators_with_small_characteristics::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 Multi_field_small_operators.h:303
Gudhi::persistence_fields::Multi_field_operators_with_small_characteristics::operator=
Multi_field_operators_with_small_characteristics & operator=(Multi_field_operators_with_small_characteristics other)
Assign operator.
Definition Multi_field_small_operators.h:389
Gudhi::persistence_fields::Multi_field_operators_with_small_characteristics::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 Multi_field_small_operators.h:198
Gudhi::persistence_fields::Multi_field_operators_with_small_characteristics::Element
unsigned int Element
Definition Multi_field_small_operators.h:40
Gudhi::persistence_fields::Multi_field_operators_with_small_characteristics::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) % produc...
Definition Multi_field_small_operators.h:261
Gudhi::persistence_fields::Multi_field_operators_with_small_characteristics::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 Multi_field_small_operators.h:220
Gudhi::persistence_fields::Multi_field_operators_with_small_characteristics::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 Multi_field_small_operators.h:188
Gudhi::persistence_fields::Multi_field_operators_with_small_characteristics::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) % productOf...
Definition Multi_field_small_operators.h:166
Gudhi::persistence_fields::Multi_field_operators_with_small_characteristics::get_inverse
Element get_inverse(const Element &e) const
Returns the inverse of the given element in the sense of boissonnat:hal-00922572 with respect to the ...
Definition Multi_field_small_operators.h:324
Gudhi::persistence_fields::Multi_field_operators_with_small_characteristics::swap
friend void swap(Multi_field_operators_with_small_characteristics &f1, Multi_field_operators_with_small_characteristics &f2)
Swap operator.
Definition Multi_field_small_operators.h:399
Gudhi::persistence_fields::Multi_field_operators_with_small_characteristics::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) % produc...
Definition Multi_field_small_operators.h:247
Gudhi::persistence_fields::Multi_field_operators_with_small_characteristics::Multi_field_operators_with_small_characteristics
Multi_field_operators_with_small_characteristics()
Default constructor, sets the product of all characteristics to 0.
Definition Multi_field_small_operators.h:46
Gudhi::persistence_fields::Multi_field_operators_with_small_characteristics::get_characteristic
const Characteristic & get_characteristic() const
Returns the current characteristics as the product of all of them.
Definition Multi_field_small_operators.h:135
Gudhi::persistence_fields
Field namespace.
Definition Intro_field_elements_and_operators.h:16
Gudhi
Gudhi namespace.
Definition SimplicialComplexForAlpha.h:14