Basic Polynomial Algebra Subprograms (BPAS)  v. 1.791
dmpolynomial.h
1 #ifndef _MMPolynomial_H_
2 #define _MMPolynomial_H_
3 
4 
5 #include "../Polynomial/BPASMultivarPolynomial.hpp"
6 #include "../Utils/TemplateHelpers.hpp"
7 #include "../Ring/BPASField.hpp"
8 
9 template <class Field>
10 inline void coef_add_mod(Field* c, Field a, Field b, Field p) {
11  *c = (a + b) % p;
12 }
13 template <class Field>
14 inline void coef_sub_mod(Field* c, Field a, Field b, Field p) {
15  *c = (a - b) % p;
16  if (*c < 0) { *c += p; }
17 }
18 template <class Field>
19 inline void coef_neg_mod(Field* c, Field a, Field p) {
20  *c = p - a;
21 }
22 template <class Field>
23 inline void coef_mul_mod(Field* c, Field a, Field b, Field p) {
24  *c = (a * b) % p;
25 }
26 
27 /**
28  * A multivariate polynomial with coefficients in an arbitrary finite field represented densely.
29  * The class is templated by a Field which should be a BPASField.
30  */
31 template <class Field>
32 class DistributedDenseMultivariateModularPolynomial : public BPASMultivariatePolynomial<Field,DistributedDenseMultivariateModularPolynomial<Field>>,
33  private Derived_from<Field, BPASField<Field>> {
34  private:
35  Symbol* names; // Variable names
36  int var; // Number of variables
37  int n; // Number of terms
38  Field* coefs; // Coefficients in Prime field
39  int* degs; // Partial size
40  Field p; // Prime
41 
42 
43  int* acc;
44 
45  inline void zeros() {
46  for (int i = 0; i < n; ++i)
47  coefs[i] = 0;
48  }
49 
50  inline bool isSameRing(const DistributedDenseMultivariateModularPolynomial& b) const {
51  if (var != b.var || names[0] != b.names[0])
52  return 0;
53  if (names[0] == "9") {
54  for (int i = 1; i <= var; ++i) {
55  if (names[i] != b.names[i])
56  return 0;
57  }
58  }
59  return 1;
60  }
61 
62  public:
63  static mpz_class characteristic;
64  // static bool isPrimeField;
65  // static bool isSmallPrimeField;
66  // static bool isComplexField;
67  /**
68  * Constructor using a default field
69  **/
71  coefs = new Field[1];
72  coefs[0] = 0;
73  degs = new int[1];
74  degs[0] = 0;
75  acc = new int[1];
76  acc[0] = 1;
77  names = new Symbol[1];
78  names[0] = "1";
79  }
80 
81  /**
82  * Constructor with the Field
83  *
84  * @param m: The prime
85  **/
86  DistributedDenseMultivariateModularPolynomial (const Field& m) : var(0), n(0), p(m) {
87  coefs = new Field[1];
88  coefs[0] = 0;
89  degs = new int[1];
90  degs[0] = 0;
91  acc = new int[1];
92  acc[0] = 1;
93  names = new Symbol[1];
94  names[0] = "1";
95  }
96 
97  /**
98  * Constructor with number of variables and terms
99  *
100  * @param v: Number of variables
101  * @param ds: Partial degrees
102  * @param m: The prime
103  **/
104  DistributedDenseMultivariateModularPolynomial(int v, int* ds, Field m) : var(v), p(m) {
105  degs = new int[var];
106  acc = new int[var];
107  acc[0] = 1;
108  for (int i = 0; i < var; ++i) {
109  degs[i] = ds[i];
110  if (i < var - 1)
111  acc[i+1] = acc[i] * (degs[i] + 1);
112  }
113  n = acc[var-1] * (degs[var-1] + 1);
114  coefs = new Field[n];
115  zeros();
116  //coefs[0] = 0;
117  names = new Symbol[var+1];
118  names[0] = "1";
119  for (int i = 1; i <= var; ++i) {
120  std::ostringstream convert;
121  convert << var - i + 1;
122  names[i] = "_";
123  names[i] += convert.str();
124  }
125  }
126 
127  /**
128  * Construct with a variable name
129  * such that f(x) = x;
130  *
131  * @param x: The variable name
132  * @param m: The prime
133  **/
134  DistributedDenseMultivariateModularPolynomial (const Symbol& x, const Field& m) : var(1), n(2), p(m) {
135  names = new Symbol[2];
136  names[0] = "9";
137  names[1] = x;
138  degs = new int[1];
139  degs[0] = 1;
140  acc = new int[1];
141  acc[0] = 1;
142  coefs = new Field[2];
143  coefs[0] = 0;
144  coefs[1] = 1;
145  }
146  /**
147  * Copy constructor
148  *
149  * @param b: A multivariate modular polynomial
150  **/
152  degs = new int[var];
153  std::copy(b.degs, b.degs+var, degs);
154  acc = new int[var];
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);
160  }
161  /**
162  * Deconstructor
163  *
164  * @param
165  **/
167  delete [] coefs;
168  delete [] degs;
169  delete [] names;
170  delete [] acc;
171  }
172  /**
173  * Overload operator =
174  *
175  * @param b: A multivariate modular polynomial
176  **/
178  if (this != &b) {
179  delete [] coefs;
180  delete [] degs;
181  delete [] names;
182  delete [] acc;
183 
184  var = b.var;
185  degs = new int[var];
186  std::copy(b.degs, b.degs+var, degs);
187  acc = new int[var];
188  std::copy(b.acc, b.acc+var, acc);
189  n = b.n;
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);
194  p = b.p;
195  }
196  return *this;
197  }
198 
199  /**
200  * Overload operator =. Assign this to a be a base Field element.
201  */
204  return *this;
205  }
206 
207 
208  /**
209  * The characteristic of this ring class.
210  */
211  mpz_class getCharacteristic() const override {
213  }
214 
215 
216  /**
217  * Is a zero polynomial
218  *
219  * @param
220  **/
221  inline bool isZero() const {
222  for (int i = 0; i < n; ++i) {
223  if (coefs[i] != 0)
224  return 0;
225  }
226  return 1;
227  }
228  /**
229  * Zero polynomial
230  *
231  * @param
232  **/
233  inline void zero() {
234  zeros();
235  }
236  /**
237  * Is polynomial 1
238  *
239  * @param
240  **/
241  inline bool isOne() const {
242  for (int i = 1; i < n; ++i) {
243  if (coefs[i] != 0)
244  return 0;
245  }
246  return (coefs[0] == 1);
247  }
248  /**
249  * Set polynomial to 1
250  *
251  * @param
252  **/
253  inline void one() {
254  coefs[0] = 1;
255  for (int i = 1; i < n; ++i)
256  coefs[i] = 0;
257  }
258  /**
259  * Is polynomial -1
260  *
261  * @param
262  **/
263  inline bool isNegativeOne() const {
264  for (int i = 1; i < n; ++i) {
265  if (coefs[i] != 0)
266  return 0;
267  }
268  return (coefs[0] == p - 1);
269  }
270  /**
271  * Set polynomial to -1
272  *
273  * @param
274  **/
275  inline void negativeOne() {
276  coefs[0] = p - 1;
277  for (int i = 1; i < n; ++i)
278  coefs[i] = 0;
279  }
280  /**
281  * Is a constant
282  *
283  * @param
284  **/
285  inline int isConstant() const {
286  for (int i = 1; i < n; ++i) {
287  if (coefs[i] != 0)
288  return 0;
289  }
290  if (coefs[0] < (p / 2)) { return 1; }
291  else { return -1; }
292  }
293  /**
294  * Get the number of variables
295  *
296  * @param
297  **/
298  inline int numberOfVariables() const {
299  return variables().size();
300  }
301 
302  /**
303  * Get the number of variables in this polynomial ring.
304  */
305  inline int numberOfRingVariables() const {
306  return ringVariables().size();
307  }
308 
309  /**
310  * Get the number of non-zero terms
311  *
312  * @param
313  **/
314  inline Integer numberOfTerms() const {
315  int k = 0;
316  for (int i = 0; i < n; ++i)
317  if (coefs[i] != 0) { k++; }
318  return k;
319  }
320  /**
321  * Get the size of the polynomial
322  *
323  * @param
324  **/
325  inline int size() const {
326  return n;
327  }
328 
329  /**
330  * Get the total degree.
331  */
332  inline Integer degree() const {
333  Integer ret;
334  for (int i = 0; i < var; ++i) {
335  ret += degs[i];
336  }
337  return ret;
338  }
339 
340  /**
341  * Get a partial degree of variable x
342  *
343  * @param x: The variable name
344  **/
345  inline Integer degree(const Symbol& x) const {
346  int k = 0, d = 0;
347  for (int i = 1; i <= var; ++i) {
348  if (names[i] == x)
349  k = i;
350  }
351  if (k) {
352  k--;
353  for (int i = 0; i < n; ++i) {
354  int e = (i / acc[k]) % (degs[k] + 1);
355  if (coefs[i] != 0 && e > d)
356  d = e;
357  }
358  }
359  return d;
360  }
361 
362  /**
363  * Get the leading coefficient
364  *
365  * @param
366  **/
367  inline Field leadingCoefficient() const {
368  for (int i = n-1; i > -1; --i) {
369  if (coefs[i] != 0)
370  return coefs[i];
371  }
372  return 0;
373  }
374 
375  inline Field trailingCoefficient() const {
376  for (int i = 0; i < n; ++i) {
377  if (coefs[i] != 0) {
378  return coefs[i];
379  }
380  }
381  return 0;
382  }
383 
384  bool isConstantTermZero() const {
385  int d[var];
386  Field f = coefficient(var, d);
387  return (f == 0);
388  }
389 
392  Field lead = leadingCoefficient();
393  Field leadInv = lead.inverse();
394  DistributedDenseMultivariateModularPolynomial ret = *this * leadInv;
395  if (u != NULL) {
396  *u = lead;
397  }
398  if (v != NULL) {
399  *v = leadInv;
400  }
401  return ret;
402  }
403 
404  /**
405  * Get a coefficient
406  *
407  * @param v: Number of variables
408  * @param d: The exponent of each variable
409  **/
410  inline Field coefficient(int v, const int* d) const {
411  int k = 0;
412  for (int i = var-1, j = 0; i > -1 && j < v; --i, ++j) {
413  if (d[j] <= degs[i])
414  k += d[j] * acc[i];
415  else { return 0; }
416  }
417  for (int i = v-var-1; i > -1; --i)
418  if (d[i]) { return 0; }
419  return coefs[k];
420  }
421 
422  inline Field coefficient(const std::vector<int>& v) const {
423  return coefficient(v.size(), v.data());
424  }
425 
426  /**
427  * Set a coefficient
428  *
429  * @param v: Number of variables
430  * @param d: The exponent of each variable
431  * @param val: Value of the coefficient
432  **/
433  inline void setCoefficient(int v, const int* d, const Field& val) {
434  if (v != var) {
435  std::cout << "BPAS: error, DDMMP(" << var << "), but trying to setCoefficient with " << v << " variables." << std::endl;
436  exit(1);
437  }
438  int k = 0;
439  for (int i = var-1, j = 0; i > -1 && j < v; --i, ++j) {
440  if (d[j] <= degs[i])
441  k += d[j] * acc[i];
442  else {
443  std::cout << "BPAS: error, the degree of " << names[i+1] << " in DDMMP is " << degs[i] << "." << std::endl;
444  exit(1);
445  }
446  }
447  coefs[k] = val;
448  }
449 
450  inline void setCoefficient(const std::vector<int>& v, const Field& val) {
451  setCoefficient(v.size(), v.data(), val);
452  }
453 
454  /**
455  * Set a coefficient
456  *
457  * @param k: The offset in the coefficient array
458  * @param val: Value of the coefficient
459  **/
460  inline void setCoefficient(int k, const Field& val) {
461  if (k >= n || k < 0) {
462  std::cout << "BPAS: error, trying to access a non-exist coefficient in DDMMP<Field>." << std::endl;
463  exit(1);
464  }
465  coefs[k] = val;
466  }
467 
468  inline Field content() const {
469  //TODO
470  std::cerr << "BPAS ERROR: DistributedDenseMultivariateModularPolynomial::content() NOT YET IMPLEMENTED" << std::endl;
471  return Field(1);
472  }
473 
474  inline DistributedDenseMultivariateModularPolynomial primitivePart() const {
475  //TODO
476  std::cerr << "BPAS ERROR: DistributedDenseMultivariateModularPolynomial::primitivePart() NOT YET IMPLEMENTED" << std::endl;
477  return *this;
478  }
479 
480  /**
481  * Overload operator ==
482  *
483  * @param b: A multivariate modular polynomial
484  **/
486  if (var != b.var || p != b.p)
487  return 0;
488 
489  int prev = 0;
490  for (int i = 0; i < n; ++i) {
491  int k = 0;
492  for (int j = 0; j < var; ++j) {
493  int e = (i / acc[j]) % (degs[j] + 1);
494  if (e <= b.degs[j])
495  k += e * b.acc[j];
496  else if (coefs[i] != 0)
497  return 0;
498  }
499  for (int j = prev+1; j < k; ++j) {
500  if (b.coefs[j] != 0)
501  return 0;
502  }
503  if (coefs[i] != b.coefs[k])
504  return 0;
505  prev = k;
506  }
507  for (int i = n; i < b.n; ++i) {
508  if (b.coefs[i] != 0)
509  return 0;
510  }
511  return 1;
512  }
513  /**
514  * Overload operator !=
515  *
516  * @param b: A multivariate modular polynomial
517  **/
519  return !(*this == b);
520  }
521 
522  /**
523  * Overload operator +
524  *
525  * @param b: A multivariate modular polynomial
526  **/
528  if (p != b.p) {
529  std::cout << "BPAS: error, trying to add between Z/" << p << "Z and Z/" << b.p << "Z from DDMMP<Field>." << std::endl;
530  exit(1);
531  }
532  if (isConstant()) { return b + coefs[0]; }
533  if (b.isConstant()) { return *this + b.coefs[0]; }
534 
535  bool isSame = isSameRing(b);
536  if (!isSame) {
537  std::cout << "BPAS: error, trying to add between Z/" << p << "Z[";
538  for (int i = 1; i <= var; ++i) {
539  std::cout << names[i];
540  if (i < var)
541  std::cout << ", ";
542  }
543  std::cout << "] and Z/" << b.p << "Z[";
544  for (int i = 1; i <= b.var; ++i) {
545  std::cout << b.names[i];
546  if (i < b.var)
547  std::cout << ", ";
548  }
549  std::cout << "] from DDMMP<Field>." << std::endl;
550  exit(1);
551  }
552 
553  int* ds = new int[var];
554  for (int i = 0; i < var; ++i)
555  ds[i] = (degs[i] >= b.degs[i])? degs[i] : b.degs[i];
557  std::copy(names, names+var+1, res.names);
558 
559  //#pragma cilk_grainsize = 1024;
560  for (int i = 0; i < res.n; ++i) {
561  Field elem = 0;
562  int offseta = 0, offsetb = 0;
563  for (int j = 0; j < var; ++j) {
564  int k = (i / res.acc[j]) % (res.degs[j] + 1);
565  if (offseta >= 0 && k <= degs[j])
566  offseta += k * acc[j];
567  else
568  offseta = -1;
569  if (offsetb >= 0 && k <= b.degs[j])
570  offsetb += k * b.acc[j];
571  else
572  offsetb = -1;
573  }
574  if (offseta >= 0 && offsetb >= 0)
575  coef_add_mod(&elem, coefs[offseta], b.coefs[offsetb], p);
576  else if (offseta >= 0)
577  elem = coefs[offseta];
578  else if (offsetb >= 0)
579  elem = b.coefs[offsetb];
580  res.coefs[i] = elem;
581  }
582 
583  delete [] ds;
584  return res;
585  }
586 
587  /**
588  * Overload operator +=
589  *
590  * @param b: A multivariate modular polynomial
591  **/
593  *this = *this + b;
594  return *this;
595  }
596 
597  /**
598  * Overload operator +
599  *
600  * @param e: A constant
601  **/
604  return (r += e);
605  }
606 
608  return (f + e);
609  }
610 
611  /**
612  * Overload operator +=
613  *
614  * @param e: A constant
615  **/
617  coef_add_mod(&coefs[0], coefs[0], e, p);
618  return *this;
619  }
620 
621  /**
622  * Overload operator -
623  *
624  * @param b: A multivariate modular polynomial
625  **/
627  if (p != b.p) {
628  std::cout << "BPAS: error, trying to subtract between Z/" << p << "Z and Z/" << b.p << "Z from DDMMP<Field>." << std::endl;
629  exit(1);
630  }
631  if (isConstant()) { return -b + coefs[0]; }
632  if (b.isConstant()) { return *this - b.coefs[0]; }
633 
634  bool isSame = isSameRing(b);
635  if (!isSame) {
636  std::cout << "BPAS: error, trying to subtract between Z/" << p << "Z[";
637  for (int i = 1; i <= var; ++i) {
638  std::cout << names[i];
639  if (i < var)
640  std::cout << ", ";
641  }
642  std::cout << "] and Z/" << b.p << "Z[";
643  for (int i = 1; i <= b.var; ++i) {
644  std::cout << b.names[i];
645  if (i < b.var)
646  std::cout << ", ";
647  }
648  std::cout << "] from DDMMP<Field>." << std::endl;
649  exit(1);
650  }
651 
652  int* ds = new int[var];
653  for (int i = 0; i < var; ++i)
654  ds[i] = (degs[i] >= b.degs[i])? degs[i] : b.degs[i];
656  std::copy(names, names+var+1, res.names);
657 
658  for (int i = 0; i < res.n; ++i) {
659  Field elem = 0;
660  int offseta = 0, offsetb = 0;
661  for (int j = 0; j < var; ++j) {
662  int k = (i / res.acc[j]) % (res.degs[j] + 1);
663  if (offseta >= 0 && k <= degs[j])
664  offseta += k * acc[j];
665  else { offseta = -1; }
666  if (offsetb >= 0 && k <= b.degs[j])
667  offsetb += k * b.acc[j];
668  else { offsetb = -1; }
669  }
670  if (offseta >= 0 && offsetb >= 0)
671  coef_sub_mod(&elem, coefs[offseta], b.coefs[offsetb], p);
672  else if (offseta >= 0)
673  elem = coefs[offseta];
674  else if (offsetb >= 0)
675  coef_neg_mod(&elem, b.coefs[offsetb], p);
676  res.coefs[i] = elem;
677  }
678  delete [] ds;
679  return res;
680  }
681 
682  /**
683  * Overload operator -=
684  *
685  * @param b: A multivariate modular polynomial
686  **/
688  *this = *this - b;
689  return *this;
690  }
691 
692  /**
693  * Overload operator -, negate
694  *
695  * @param
696  **/
699  std::copy(names, names+var+1, res.names);
700  for (int i = 0; i < res.n; ++i)
701  coef_neg_mod(&res.coefs[i], coefs[i], p);
702  return res;
703  }
704 
705  /**
706  * Overload operator -
707  *
708  * @param e: A constant
709  **/
712  return (r -= e);
713  }
714 
716  return (-f + e);
717  }
718 
719  /**
720  * Overload operator -=
721  *
722  * @param e: A constant
723  **/
725  coef_sub_mod(&coefs[0], coefs[0], e, p);
726  return *this;
727  }
728 
729  /**
730  * Negate, f(-x)
731  *
732  * @param
733  **/
734  inline void negate() {
735  for (int i = 0; i < n; ++i)
736  coef_neg_mod(&coefs[i], coefs[i], p);
737  }
738 
739  /**
740  * Overload operator *
741  *
742  * @param b: A multivariate modular polynomial
743  **/
745  if (p != b.p) {
746  std::cout << "BPAS: error, trying to multiply between Z/" << p << "Z and Z/" << b.p << "Z from DDMMP<Field>." << std::endl;
747  exit(1);
748  }
749  if (isConstant()) { return b * coefs[0]; }
750  if (b.isConstant()) { return *this * b.coefs[0]; }
751 
752  bool isSame = isSameRing(b);
753  if (!isSame) {
754  std::cout << "BPAS: error, trying to multiply between Z/" << p << "Z[";
755  for (int i = 1; i <= var; ++i) {
756  std::cout << names[i];
757  if (i < var)
758  std::cout << ", ";
759  }
760  std::cout << "] and Z/" << b.p << "Z[";
761  for (int i = 1; i <= b.var; ++i) {
762  std::cout << b.names[i];
763  if (i < b.var)
764  std::cout << ", ";
765  }
766  std::cout << "] from DDMMP<Field>." << std::endl;
767  exit(1);
768  }
769 
770  int* ds = new int[var];
771  for (int i = 0; i < var; ++i)
772  ds[i] = degs[i] + b.degs[i];
774  std::copy(names, names+var+1, res.names);
775 
776  for (int i = 0; i < n; ++i) {
777  for (int v = 0; v < var; ++v)
778  ds[v] = (i / acc[v]) % (degs[v] + 1);
779  for (int j = 0; j < b.n; ++j) {
780  int k = 0;
781  for (int v = 0; v < b.var; ++v) {
782  int e = (j / b.acc[v]) % (b.degs[v] + 1);
783  if (v < var)
784  k += (ds[v] + e) * res.acc[v];
785  else
786  k += e * res.acc[v];
787  }
788  for (int v = b.var; v < var; ++v)
789  k += ds[v] * res.acc[v];
790  // res.coefs[k] += coefs[i] * b.coefs[j];
791  Field t;
792  coef_mul_mod(&t, coefs[i], b.coefs[j], p);
793  coef_add_mod(&res.coefs[k], res.coefs[k], t, p);
794  }
795  }
796 
797  delete [] ds;
798  return res;
799  }
800 
801  /**
802  * Overload operator *=
803  *
804  * @param b: A multivariate modular polynomial
805  **/
807  *this = *this * b;
808  return *this;
809  }
810 
811  /**
812  * Overload operator *
813  *
814  * @param e: A constant
815  **/
818  return (r *= e);
819  }
820 
822  return (f * e);
823  }
824 
825  /**
826  * Overload operator *=
827  *
828  * @param e: A constant
829  **/
831  if (f != 0 && f != 1) {
832  Field e(f);
833  if (e < 0) { e = e % p + p; }
834  for (int i = 0; i < n; ++i)
835  coef_mul_mod(&coefs[i], coefs[i], e, p);
836  }
837  else if (f == 0) { zero(); }
838  return *this;
839  }
840 
841  inline DistributedDenseMultivariateModularPolynomial<Field> operator^ (long long int e) const {
842  //TODO
843  std::cerr << "BPAS ERROR: DistributedDenseMultivariateModularPolynomial::operator^ NOT YET IMPLEMENTED" << std::endl;
844  return *this;
845  }
846 
847  inline DistributedDenseMultivariateModularPolynomial<Field>& operator^= (long long int e) {
848  //TODO
849  std::cerr << "BPAS ERROR: DistributedDenseMultivariateModularPolynomial::operator^= NOT YET IMPLEMENTED" << std::endl;
850  return *this;
851  }
852 
855  ret /= p;
856  return ret;
857  }
858 
860  //TODO
861  std::cerr << "BPAS ERROR: DistributedDenseMultivariateModularPolynomial::operator/=(DistributedDenseMultivariateModularPolynomial) NOT YET IMPLEMENTED" << std::endl;
862  return *this;
863  }
864 
865  inline DistributedDenseMultivariateModularPolynomial<Field> operator/ (const Field& e) const {
867  ret /= e;
868  return ret;
869  }
870 
871  inline DistributedDenseMultivariateModularPolynomial<Field>& operator/= (const Field& e) {
872  //TODO
873  std::cerr << "BPAS ERROR: DistributedDenseMultivariateModularPolynomial::operator/= NOT YET IMPLEMENTED" << std::endl;
874  return *this;
875  }
876 
877  /**
878  * Set variable names
879  *
880  * @param xs: Variable names
881  **/
882  inline void setRingVariables (const std::vector<Symbol>& xs) {
883  int ns = xs.size();
884  if (ns != var) {
885  std::cerr << "BPAS ERROR: DDMMP shrinking and expanding polynomial ring NOT YET IMPLEMENTED" << std::endl;
886  return;
887  }
888  names[0] = "9";
889  for (int i = var, j = 0; i > 0 && j < ns; --i, ++j)
890  names[i] = xs[j];
891  }
892 
893  /**
894  * Get variable names
895  *
896  * @param
897  **/
898  inline std::vector<Symbol> ringVariables() const {
899  std::vector<Symbol> xs;
900  for (int i = var; i > 0; --i)
901  xs.push_back(names[i]);
902  return xs;
903  }
904 
905  inline std::vector<Symbol> variables() const {
906  std::cerr << "BPAS ERROR: DDMMP::variables() NOT YET IMPLEMENTED" << std::endl;
907  return ringVariables();
908  }
909 
910 
911  /**
912  * Overload stream operator <<
913  *
914  * @param out: Stream object
915  * @param b: The multivariate modular polynomial
916  **/
917  inline void print(std::ostream &out) const {
918  bool isFirst = 0;
919  for (int i = 0; i < this->n; ++i) {
920  if (this->coefs[i] != 0) {
921  if (isFirst) {
922  if (this->coefs[i] >= 0)
923  out << "+";
924  else if (this->coefs[i] == -1)
925  out << "-";
926  if (this->coefs[i] != 1 && this->coefs[i] != -1)
927  out << this->coefs[i];
928  bool isIt = 1;
929  for (int j = 0; j < this->var; ++j) {
930  int exp = (i / this->acc[j]) % (this->degs[j] + 1);
931  if (exp) {
932  if ((this->coefs[i] != 1 && this->coefs[i] != -1 && isIt) || !isIt)
933  out << "*";
934  out << this->names[j+1];
935  if (exp > 1)
936  out << "^" << exp;
937  isIt = 0;
938  }
939  }
940  }
941  else { out << this->coefs[i]; }
942  isFirst = 1;
943  }
944  }
945  if (!isFirst) { out << "0"; }
946  }
947 
948  /**
949  * Convert *this to an expression tree
950  */
952  //TODO
953  std::cerr << "DistributedDenseMultivariateModularPolynomial::convertToExpressionTree() NOT YET IMPLEMENTED" << std::endl;
954  return ExpressionTree();
955  }
956 
957  inline void differentiate(const Symbol& s, int k) {
958  std::cerr << "DistributedDenseMultivariateModularPolynomial::differentiate NOT YET IMPLEMENTED" << std::endl;
959  //TODO
960  }
961 
962  inline void differentiate(const Symbol& s) {
963  differentiate(s, 1);
964  }
965 
968  ret.differentiate(s, k);
969  return ret;
970  }
971 
973  return derivative(s, 1);
974  }
975 
976  inline DistributedDenseMultivariateModularPolynomial<Field> evaluate(const std::vector<Symbol>& syms, const std::vector<Field>& vals) const {
977  //TODO
978  std::cerr << "BPAS ERROR: DistributedDenseMultivariateModularPolynomial::evaluate NOT YET IMPLEMENTED" << std::endl;
979  return *this;
980  }
981 
982  inline DistributedDenseMultivariateModularPolynomial<Field> evaluate(int n, const Symbol* syms, const Field* vals) const {
983  //TODO
984  std::cerr << "BPAS ERROR: DistributedDenseMultivariateModularPolynomial::evaluate NOT YET IMPLEMENTED" << std::endl;
985  return *this;
986  }
987 
989  //TODO
990  std::cerr << "BPAS ERROR: DistributedDenseMultivariateModularPolynomial::gcd NOT YET IMPLEMENTED" << std::endl;
991  return *this;
992  }
993 
994  /**
995  * Compute squarefree factorization of *this
996  */
998  std::cerr << "DistributedDenseMultivariateModularPolynomial::squareFree NOT YET IMPLEMENTED" << std::endl;
999  //TODO
1000  std::vector<DistributedDenseMultivariateModularPolynomial> ret;
1001  ret.push_back(*this);
1002  return ret;
1003  }
1004 
1005 
1006 
1007 
1008 
1009 
1010 
1011 };
1012 
1013 #endif
DistributedDenseMultivariateModularPolynomial(const DistributedDenseMultivariateModularPolynomial< Field > &b)
Copy constructor.
Definition: dmpolynomial.h:151
void negate()
Negate, f(-x)
Definition: dmpolynomial.h:734
Field coefficient(const std::vector< int > &v) const
Get the coefficient of this polynomial with respect to the monomial defined by exponent vector exps...
Definition: dmpolynomial.h:422
DistributedDenseMultivariateModularPolynomial< Field > derivative(const Symbol &s, int k) const
Differentiate this polynomial k times, with respect to a particular variable, setting itself to its d...
Definition: dmpolynomial.h:966
ExpressionTree convertToExpressionTree() const
Convert *this to an expression tree.
Definition: dmpolynomial.h:951
DistributedDenseMultivariateModularPolynomial< Field > operator+(const DistributedDenseMultivariateModularPolynomial< Field > &b) const
Overload operator +.
Definition: dmpolynomial.h:527
Field leadingCoefficient() const
Get the leading coefficient.
Definition: dmpolynomial.h:367
int numberOfRingVariables() const
Get the number of variables in this polynomial ring.
Definition: dmpolynomial.h:305
Integer degree(const Symbol &x) const
Get a partial degree of variable x.
Definition: dmpolynomial.h:345
DistributedDenseMultivariateModularPolynomial< Field > & operator-=(const DistributedDenseMultivariateModularPolynomial< Field > &b)
Overload operator -=.
Definition: dmpolynomial.h:687
Integer numberOfTerms() const
Get the number of non-zero terms.
Definition: dmpolynomial.h:314
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:917
mpz_class getCharacteristic() const override
The characteristic of this ring class.
Definition: dmpolynomial.h:211
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:744
Factors< DistributedDenseMultivariateModularPolynomial > squareFree() const
Compute squarefree factorization of *this.
Definition: dmpolynomial.h:997
Integer degree() const
Get the total degree.
Definition: dmpolynomial.h:332
void negativeOne()
Set polynomial to -1.
Definition: dmpolynomial.h:275
std::vector< Symbol > ringVariables() const
Get variable names.
Definition: dmpolynomial.h:898
int size() const
Get the size of the polynomial.
Definition: dmpolynomial.h:325
void setCoefficient(const std::vector< int > &v, const Field &val)
Set the coefficient of this polynomial for the monomial defined by exponent vector exps to r...
Definition: dmpolynomial.h:450
bool isOne() const
Is polynomial 1.
Definition: dmpolynomial.h:241
Field coefficient(int v, const int *d) const
Get a coefficient.
Definition: dmpolynomial.h:410
DistributedDenseMultivariateModularPolynomial< Field > evaluate(int n, const Symbol *syms, const Field *vals) const
Evaluate this polynomial by substituting the input ring elements elems for the variables vars...
Definition: dmpolynomial.h:982
DistributedDenseMultivariateModularPolynomial< Field > evaluate(const std::vector< Symbol > &syms, const std::vector< Field > &vals) const
Evaluate this polynomial by substituting the input ring elements elems for the variables vars...
Definition: dmpolynomial.h:976
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: BPASMultivarPolynomial.hpp:17
DistributedDenseMultivariateModularPolynomial(const Field &m)
Constructor with the Field.
Definition: dmpolynomial.h:86
std::vector< Symbol > variables() const
Get all the variables in this polynomial with positive degree.
Definition: dmpolynomial.h:905
bool isZero() const
Is a zero polynomial.
Definition: dmpolynomial.h:221
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:697
void differentiate(const Symbol &s, int k)
Differentiate this polynomial k times, with respect to a particular variable, setting itself to its d...
Definition: dmpolynomial.h:957
An arbitrary-precision Integer.
Definition: Integer.hpp:22
void zero()
Zero polynomial.
Definition: dmpolynomial.h:233
bool operator!=(const DistributedDenseMultivariateModularPolynomial< Field > &b) const
Overload operator !=.
Definition: dmpolynomial.h:518
void one()
Set polynomial to 1.
Definition: dmpolynomial.h:253
DistributedDenseMultivariateModularPolynomial< Field > & operator+=(const DistributedDenseMultivariateModularPolynomial< Field > &b)
Overload operator +=.
Definition: dmpolynomial.h:592
int numberOfVariables() const
Get the number of variables.
Definition: dmpolynomial.h:298
DistributedDenseMultivariateModularPolynomial< Field > derivative(const Symbol &s) const
Differentiate this polynomial, with respect to a particular variable, setting itself to its derivativ...
Definition: dmpolynomial.h:972
void setCoefficient(int v, const int *d, const Field &val)
Set a coefficient.
Definition: dmpolynomial.h:433
An encapsulation of a mathematical symbol.
Definition: Symbol.hpp:23
int isConstant() const
Is a constant.
Definition: dmpolynomial.h:285
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:806
bool operator==(const DistributedDenseMultivariateModularPolynomial< Field > &b) const
Overload operator ==.
Definition: dmpolynomial.h:485
void setRingVariables(const std::vector< Symbol > &xs)
Set variable names.
Definition: dmpolynomial.h:882
void setCoefficient(int k, const Field &val)
Set a coefficient.
Definition: dmpolynomial.h:460
bool isNegativeOne() const
Is polynomial -1.
Definition: dmpolynomial.h:263
void differentiate(const Symbol &s)
Differentiate this polynomial, with respect to a particular variable, setting itself to its derivativ...
Definition: dmpolynomial.h:962