1 #ifndef _MMPolynomial_H_ 2 #define _MMPolynomial_H_ 5 #include "../polynomial.h" 6 #include "../Utils/TemplateHelpers.hpp" 7 #include "../Ring/BPASField.hpp" 10 inline void coef_add_mod(Field* c, Field a, Field b, Field p) {
13 template <
class Field>
14 inline void coef_sub_mod(Field* c, Field a, Field b, Field p) {
16 if (*c < 0) { *c += p; }
18 template <
class Field>
19 inline void coef_neg_mod(Field* c, Field a, Field p) {
22 template <
class Field>
23 inline void coef_mul_mod(Field* c, Field a, Field b, Field p) {
31 template <
class Field>
33 private Derived_from<Field, BPASField<Field>> {
46 for (
int i = 0; i < n; ++i)
51 if (var != b.var || names[0] != b.names[0])
53 if (names[0] ==
"9") {
54 for (
int i = 1; i <= var; ++i) {
55 if (names[i] != b.names[i])
63 static mpz_class characteristic;
108 for (
int i = 0; i < var; ++i) {
111 acc[i+1] = acc[i] * (degs[i] + 1);
113 n = acc[var-1] * (degs[var-1] + 1);
114 coefs =
new Field[n];
117 names =
new Symbol[var+1];
119 for (
int i = 1; i <= var; ++i) {
120 std::ostringstream convert;
121 convert << var - i + 1;
123 names[i] += convert.str();
142 coefs =
new Field[2];
153 std::copy(b.degs, b.degs+var, degs);
155 std::copy(b.acc, b.acc+var, acc);
156 coefs =
new Field[n];
157 std::copy(b.coefs, b.coefs+n, coefs);
158 names =
new Symbol[var+1];
159 std::copy(b.names, b.names+var+1, names);
186 std::copy(b.degs, b.degs+var, degs);
188 std::copy(b.acc, b.acc+var, acc);
190 coefs =
new Field[n];
191 std::copy(b.coefs, b.coefs+n, coefs);
192 names =
new Symbol[var+1];
193 std::copy(b.names, b.names+var+1, names);
212 for (
int i = 0; i < n; ++i) {
232 for (
int i = 1; i < n; ++i) {
236 return (coefs[0] == 1);
245 for (
int i = 1; i < n; ++i)
254 for (
int i = 1; i < n; ++i) {
258 return (coefs[0] == p - 1);
267 for (
int i = 1; i < n; ++i)
276 for (
int i = 1; i < n; ++i) {
280 if (coefs[0] < (p / 2)) {
return 1; }
289 return variables().size();
306 for (
int i = 0; i < n; ++i)
307 if (coefs[i] != 0) { k++; }
323 std::cerr <<
"DistributedDenseMultivariateModularPolynomial::degree() NOT YET IMPLEMENTED" << std::endl;
335 for (
int i = 1; i <= var; ++i) {
341 for (
int i = 0; i < n; ++i) {
342 int e = (i / acc[k]) % (degs[k] + 1);
343 if (coefs[i] != 0 && e > d)
356 for (
int i = n-1; i > -1; --i) {
363 inline Field trailingCoefficient()
const {
364 for (
int i = 0; i < n; ++i) {
372 bool isConstantTermZero()
const {
381 Field leadInv = lead.inverse();
400 for (
int i = var-1, j = 0; i > -1 && j < v; --i, ++j) {
405 for (
int i = v-var-1; i > -1; --i)
406 if (d[i]) {
return 0; }
410 inline Field
coefficient(
const std::vector<int>& v)
const {
423 std::cout <<
"BPAS: error, DDMMP(" << var <<
"), but trying to setCoefficient with " << v <<
" variables." << std::endl;
427 for (
int i = var-1, j = 0; i > -1 && j < v; --i, ++j) {
431 std::cout <<
"BPAS: error, the degree of " << names[i+1] <<
" in DDMMP is " << degs[i] <<
"." << std::endl;
438 inline void setCoefficient(
const std::vector<int>& v,
const Field& val) {
449 if (k >= n || k < 0) {
450 std::cout <<
"BPAS: error, trying to access a non-exist coefficient in DDMMP<Field>." << std::endl;
456 inline Field content()
const {
458 std::cerr <<
"BPAS ERROR: DistributedDenseMultivariateModularPolynomial::content() NOT YET IMPLEMENTED" << std::endl;
464 std::cerr <<
"BPAS ERROR: DistributedDenseMultivariateModularPolynomial::primitivePart() NOT YET IMPLEMENTED" << std::endl;
474 if (var != b.var || p != b.p)
478 for (
int i = 0; i < n; ++i) {
480 for (
int j = 0; j < var; ++j) {
481 int e = (i / acc[j]) % (degs[j] + 1);
484 else if (coefs[i] != 0)
487 for (
int j = prev+1; j < k; ++j) {
491 if (coefs[i] != b.coefs[k])
495 for (
int i = n; i < b.n; ++i) {
507 return !(*
this == b);
517 std::cout <<
"BPAS: error, trying to add between Z/" << p <<
"Z and Z/" << b.p <<
"Z from DDMMP<Field>." << std::endl;
521 if (b.isConstant()) {
return *
this + b.coefs[0]; }
523 bool isSame = isSameRing(b);
525 std::cout <<
"BPAS: error, trying to add between Z/" << p <<
"Z[";
526 for (
int i = 1; i <= var; ++i) {
527 std::cout << names[i];
531 std::cout <<
"] and Z/" << b.p <<
"Z[";
532 for (
int i = 1; i <= b.var; ++i) {
533 std::cout << b.names[i];
537 std::cout <<
"] from DDMMP<Field>." << std::endl;
541 int* ds =
new int[var];
542 for (
int i = 0; i < var; ++i)
543 ds[i] = (degs[i] >= b.degs[i])? degs[i] : b.degs[i];
545 std::copy(names, names+var+1, res.names);
548 for (
int i = 0; i < res.n; ++i) {
550 int offseta = 0, offsetb = 0;
551 for (
int j = 0; j < var; ++j) {
552 int k = (i / res.acc[j]) % (res.degs[j] + 1);
553 if (offseta >= 0 && k <= degs[j])
554 offseta += k * acc[j];
557 if (offsetb >= 0 && k <= b.degs[j])
558 offsetb += k * b.acc[j];
562 if (offseta >= 0 && offsetb >= 0)
563 coef_add_mod(&elem, coefs[offseta], b.coefs[offsetb], p);
564 else if (offseta >= 0)
565 elem = coefs[offseta];
566 else if (offsetb >= 0)
567 elem = b.coefs[offsetb];
605 coef_add_mod(&coefs[0], coefs[0], e, p);
616 std::cout <<
"BPAS: error, trying to subtract between Z/" << p <<
"Z and Z/" << b.p <<
"Z from DDMMP<Field>." << std::endl;
620 if (b.isConstant()) {
return *
this - b.coefs[0]; }
622 bool isSame = isSameRing(b);
624 std::cout <<
"BPAS: error, trying to subtract between Z/" << p <<
"Z[";
625 for (
int i = 1; i <= var; ++i) {
626 std::cout << names[i];
630 std::cout <<
"] and Z/" << b.p <<
"Z[";
631 for (
int i = 1; i <= b.var; ++i) {
632 std::cout << b.names[i];
636 std::cout <<
"] from DDMMP<Field>." << std::endl;
640 int* ds =
new int[var];
641 for (
int i = 0; i < var; ++i)
642 ds[i] = (degs[i] >= b.degs[i])? degs[i] : b.degs[i];
644 std::copy(names, names+var+1, res.names);
646 for (
int i = 0; i < res.n; ++i) {
648 int offseta = 0, offsetb = 0;
649 for (
int j = 0; j < var; ++j) {
650 int k = (i / res.acc[j]) % (res.degs[j] + 1);
651 if (offseta >= 0 && k <= degs[j])
652 offseta += k * acc[j];
653 else { offseta = -1; }
654 if (offsetb >= 0 && k <= b.degs[j])
655 offsetb += k * b.acc[j];
656 else { offsetb = -1; }
658 if (offseta >= 0 && offsetb >= 0)
659 coef_sub_mod(&elem, coefs[offseta], b.coefs[offsetb], p);
660 else if (offseta >= 0)
661 elem = coefs[offseta];
662 else if (offsetb >= 0)
663 coef_neg_mod(&elem, b.coefs[offsetb], p);
687 std::copy(names, names+var+1, res.names);
688 for (
int i = 0; i < res.n; ++i)
689 coef_neg_mod(&res.coefs[i], coefs[i], p);
713 coef_sub_mod(&coefs[0], coefs[0], e, p);
723 for (
int i = 0; i < n; ++i)
724 coef_neg_mod(&coefs[i], coefs[i], p);
734 std::cout <<
"BPAS: error, trying to multiply between Z/" << p <<
"Z and Z/" << b.p <<
"Z from DDMMP<Field>." << std::endl;
738 if (b.isConstant()) {
return *
this * b.coefs[0]; }
740 bool isSame = isSameRing(b);
742 std::cout <<
"BPAS: error, trying to multiply between Z/" << p <<
"Z[";
743 for (
int i = 1; i <= var; ++i) {
744 std::cout << names[i];
748 std::cout <<
"] and Z/" << b.p <<
"Z[";
749 for (
int i = 1; i <= b.var; ++i) {
750 std::cout << b.names[i];
754 std::cout <<
"] from DDMMP<Field>." << std::endl;
758 int* ds =
new int[var];
759 for (
int i = 0; i < var; ++i)
760 ds[i] = degs[i] + b.degs[i];
762 std::copy(names, names+var+1, res.names);
764 for (
int i = 0; i < n; ++i) {
765 for (
int v = 0; v < var; ++v)
766 ds[v] = (i / acc[v]) % (degs[v] + 1);
767 for (
int j = 0; j < b.n; ++j) {
769 for (
int v = 0; v < b.var; ++v) {
770 int e = (j / b.acc[v]) % (b.degs[v] + 1);
772 k += (ds[v] + e) * res.acc[v];
776 for (
int v = b.var; v < var; ++v)
777 k += ds[v] * res.acc[v];
780 coef_mul_mod(&t, coefs[i], b.coefs[j], p);
781 coef_add_mod(&res.coefs[k], res.coefs[k], t, p);
819 if (f != 0 && f != 1) {
821 if (e < 0) { e = e % p + p; }
822 for (
int i = 0; i < n; ++i)
823 coef_mul_mod(&coefs[i], coefs[i], e, p);
825 else if (f == 0) {
zero(); }
831 std::cerr <<
"BPAS ERROR: DistributedDenseMultivariateModularPolynomial::operator^ NOT YET IMPLEMENTED" << std::endl;
837 std::cerr <<
"BPAS ERROR: DistributedDenseMultivariateModularPolynomial::operator^= NOT YET IMPLEMENTED" << std::endl;
849 std::cerr <<
"BPAS ERROR: DistributedDenseMultivariateModularPolynomial::operator/=(DistributedDenseMultivariateModularPolynomial) NOT YET IMPLEMENTED" << std::endl;
861 std::cerr <<
"BPAS ERROR: DistributedDenseMultivariateModularPolynomial::operator/= NOT YET IMPLEMENTED" << std::endl;
873 std::cerr <<
"BPAS ERROR: DDMMP shrinking and expanding polynomial ring NOT YET IMPLEMENTED" << std::endl;
877 for (
int i = var, j = 0; i > 0 && j < ns; --i, ++j)
887 std::vector<Symbol> xs;
888 for (
int i = var; i > 0; --i)
889 xs.push_back(names[i]);
893 inline std::vector<Symbol> variables()
const {
894 std::cerr <<
"BPAS ERROR: DDMMP::variables() NOT YET IMPLEMENTED" << std::endl;
905 inline void print(std::ostream &out)
const {
907 for (
int i = 0; i < this->n; ++i) {
908 if (this->coefs[i] != 0) {
910 if (this->coefs[i] >= 0)
912 else if (this->coefs[i] == -1)
914 if (this->coefs[i] != 1 && this->coefs[i] != -1)
915 out << this->coefs[i];
917 for (
int j = 0; j < this->var; ++j) {
918 int exp = (i / this->acc[j]) % (this->degs[j] + 1);
920 if ((this->coefs[i] != 1 && this->coefs[i] != -1 && isIt) || !isIt)
922 out << this->names[j+1];
929 else { out << this->coefs[i]; }
933 if (!isFirst) { out <<
"0"; }
941 std::cerr <<
"DistributedDenseMultivariateModularPolynomial::convertToExpressionTree() NOT YET IMPLEMENTED" << std::endl;
945 inline void differentiate(
const Symbol& s,
int k) {
946 std::cerr <<
"DistributedDenseMultivariateModularPolynomial::differentiate NOT YET IMPLEMENTED" << std::endl;
950 inline void differentiate(
const Symbol& s) {
956 ret.differentiate(s, k);
961 return derivative(s, 1);
966 std::cerr <<
"BPAS ERROR: DistributedDenseMultivariateModularPolynomial::evaluate NOT YET IMPLEMENTED" << std::endl;
972 std::cerr <<
"BPAS ERROR: DistributedDenseMultivariateModularPolynomial::evaluate NOT YET IMPLEMENTED" << std::endl;
978 std::cerr <<
"BPAS ERROR: DistributedDenseMultivariateModularPolynomial::gcd NOT YET IMPLEMENTED" << std::endl;
986 std::cerr <<
"DistributedDenseMultivariateModularPolynomial::squareFree NOT YET IMPLEMENTED" << std::endl;
988 std::vector<DistributedDenseMultivariateModularPolynomial> ret;
989 ret.push_back(*
this);
DistributedDenseMultivariateModularPolynomial(const DistributedDenseMultivariateModularPolynomial< Field > &b)
Copy constructor.
Definition: dmpolynomial.h:151
void negate()
Negate, f(-x)
Definition: dmpolynomial.h:722
ExpressionTree convertToExpressionTree() const
Convert *this to an expression tree.
Definition: dmpolynomial.h:939
DistributedDenseMultivariateModularPolynomial< Field > operator+(const DistributedDenseMultivariateModularPolynomial< Field > &b) const
Overload operator +.
Definition: dmpolynomial.h:515
Field leadingCoefficient() const
Get the leading coefficient.
Definition: dmpolynomial.h:355
int numberOfRingVariables() const
Get the number of variables in this polynomial ring.
Definition: dmpolynomial.h:295
Integer degree(const Symbol &x) const
Get a partial degree of variable x.
Definition: dmpolynomial.h:333
DistributedDenseMultivariateModularPolynomial< Field > & operator-=(const DistributedDenseMultivariateModularPolynomial< Field > &b)
Overload operator -=.
Definition: dmpolynomial.h:675
Integer numberOfTerms() const
Get the number of non-zero terms.
Definition: dmpolynomial.h:304
DistributedDenseMultivariateModularPolynomial(int v, int *ds, Field m)
Constructor with number of variables and terms.
Definition: dmpolynomial.h:104
void print(std::ostream &out) const
Overload stream operator <<.
Definition: dmpolynomial.h:905
DistributedDenseMultivariateModularPolynomial()
Constructor using a default field.
Definition: dmpolynomial.h:70
An ExpressionTree encompasses various forms of data that can be expressed generically as a binary tre...
Definition: ExpressionTree.hpp:17
DistributedDenseMultivariateModularPolynomial< Field > operator*(const DistributedDenseMultivariateModularPolynomial< Field > &b) const
Overload operator *.
Definition: dmpolynomial.h:732
Factors< DistributedDenseMultivariateModularPolynomial > squareFree() const
Compute squarefree factorization of *this.
Definition: dmpolynomial.h:985
Integer degree() const
Get the total degree.
Definition: dmpolynomial.h:322
void negativeOne()
Set polynomial to -1.
Definition: dmpolynomial.h:265
std::vector< Symbol > ringVariables() const
Get variable names.
Definition: dmpolynomial.h:886
int size() const
Get the size of the polynomial.
Definition: dmpolynomial.h:315
bool isOne() const
Is polynomial 1.
Definition: dmpolynomial.h:231
Field coefficient(int v, const int *d) const
Get a coefficient.
Definition: dmpolynomial.h:398
DistributedDenseMultivariateModularPolynomial(const Symbol &x, const Field &m)
Construct with a variable name such that f(x) = x;.
Definition: dmpolynomial.h:134
DistributedDenseMultivariateModularPolynomial< Field > & operator=(const DistributedDenseMultivariateModularPolynomial< Field > &b)
Overload operator =.
Definition: dmpolynomial.h:177
An abstract class defining the interface of a multivariate polynomial over an arbitrary BPASRing...
Definition: polynomial.h:117
DistributedDenseMultivariateModularPolynomial(const Field &m)
Constructor with the Field.
Definition: dmpolynomial.h:86
bool isZero() const
Is a zero polynomial.
Definition: dmpolynomial.h:211
A simple data structure for encapsulating a collection of Factor elements.
Definition: Factors.hpp:95
~DistributedDenseMultivariateModularPolynomial()
Deconstructor.
Definition: dmpolynomial.h:166
DistributedDenseMultivariateModularPolynomial< Field > operator-() const
Overload operator -, negate.
Definition: dmpolynomial.h:685
An arbitrary-precision Integer.
Definition: Integer.hpp:22
void zero()
Zero polynomial.
Definition: dmpolynomial.h:223
bool operator!=(const DistributedDenseMultivariateModularPolynomial< Field > &b) const
Overload operator !=.
Definition: dmpolynomial.h:506
void one()
Set polynomial to 1.
Definition: dmpolynomial.h:243
DistributedDenseMultivariateModularPolynomial< Field > & operator+=(const DistributedDenseMultivariateModularPolynomial< Field > &b)
Overload operator +=.
Definition: dmpolynomial.h:580
int numberOfVariables() const
Get the number of variables.
Definition: dmpolynomial.h:288
void setCoefficient(int v, const int *d, const Field &val)
Set a coefficient.
Definition: dmpolynomial.h:421
An encapsulation of a mathematical symbol.
Definition: Symbol.hpp:23
int isConstant() const
Is a constant.
Definition: dmpolynomial.h:275
A multivariate polynomial with coefficients in an arbitrary finite field represented densely...
Definition: dmpolynomial.h:32
DistributedDenseMultivariateModularPolynomial< Field > & operator*=(const DistributedDenseMultivariateModularPolynomial< Field > &b)
Overload operator *=.
Definition: dmpolynomial.h:794
bool operator==(const DistributedDenseMultivariateModularPolynomial< Field > &b) const
Overload operator ==.
Definition: dmpolynomial.h:473
void setRingVariables(const std::vector< Symbol > &xs)
Set variable names.
Definition: dmpolynomial.h:870
void setCoefficient(int k, const Field &val)
Set a coefficient.
Definition: dmpolynomial.h:448
bool isNegativeOne() const
Is polynomial -1.
Definition: dmpolynomial.h:253