All Classes Functions Friends
sdmpolynomial.h
1 #ifndef _SMALLMMPOLYNOMIAL_H_
2 #define _SMALLMMPOLYNOMIAL_H_
3 
4 #include "../polynomial.h"
5 #include "src/modpn.h"
6 #include "src/general_routine.h"
7 #include "src/basic_routine.h"
8 #include "src/DDMP.h"
9 //#if FURER
10 //#include "src/fft_furer1.h"
11 //#else
12 //#include "src/fft_iter1.h"
13 //#endif
14 
15 
16 #define SDMPBASESIZE 1024
17 
19  private:
20  std::string* names; // Variable names
21  int var; // Number of variables
22  int n; // Number of terms
23  sfixn* coefs; // Coefficients in Prime field
24  int* degs; // Partial size
25  sfixn p; // Prime
26 
27  int* acc;
28 
29  void zeros();
31  bool shrink();
34 
35  public:
36  static int characteristic;
37  static bool isPrimeField;
38  static bool isComplexField;
39  /**
40  * Constructor using a default prime
41  **/
43  p = BPASPRIME;
44  coefs = new sfixn[1];
45  coefs[0] = 0;
46  degs = new int[1];
47  degs[0] = 0;
48  acc = new int[1];
49  acc[0] = 1;
50  names = new std::string[1];
51  names[0] = "1";
52  }
53  /**
54  * Constructor with the field
55  *
56  * @param m: The prime
57  **/
59  coefs = new sfixn[1];
60  coefs[0] = 0;
61  degs = new int[1];
62  degs[0] = 0;
63  acc = new int[1];
64  acc[0] = 1;
65  names = new std::string[1];
66  names[0] = "1";
67  }
68  /**
69  * Constructor with number of variables and terms
70  *
71  * @param v: Number of variables
72  * @param ds: Partial degrees
73  * @param m: The prime
74  **/
75  SmallPrimeFieldDistributedDenseMultivariateModularPolynomial (int v, int* ds, sfixn m) : var(v), p(m) {
76  degs = new int[var];
77  acc = new int[var];
78  acc[0] = 1;
79  for (int i = 0; i < var; ++i) {
80  degs[i] = ds[i];
81  if (i < var - 1)
82  acc[i+1] = acc[i] * (degs[i] + 1);
83  }
84  n = acc[var-1] * (degs[var-1] + 1);
85  coefs = new sfixn[n];
86  zeros();
87  names = new std::string[var+1];
88  names[0] = "1";
89  for (int i = 1; i <= var; ++i) {
90  std::ostringstream convert;
91  convert << var - i + 1;
92  names[i] = "_";
93  names[i] += convert.str();
94  }
95  }
96  /**
97  * Construct with a variable name
98  * such that f(x) = x;
99  *
100  * @param x: The variable name
101  * @param m: The prime
102  **/
103  SmallPrimeFieldDistributedDenseMultivariateModularPolynomial (std::string x, sfixn m) : var(1), n(2), p(m) {
104  names = new std::string[2];
105  names[0] = "9";
106  names[1] = x;
107  degs = new int[1];
108  degs[0] = 1;
109  acc = new int[1];
110  acc[0] = 1;
111  coefs = new sfixn[2];
112  coefs[0] = 0;
113  coefs[1] = 1;
114  }
115  /**
116  * Copy constructor
117  *
118  * @param b: A multivariate modular polynomial
119  **/
121  degs = new int[var];
122  std::copy(b.degs, b.degs+var, degs);
123  acc = new int[var];
124  std::copy(b.acc, b.acc+var, acc);
125  coefs = new sfixn[n];
126  std::copy(b.coefs, b.coefs+n, coefs);
127  names = new std::string[var+1];
128  std::copy(b.names, b.names+var+1, names);
129  }
130  /**
131  * Deconstructor
132  *
133  * @param
134  **/
136  delete [] coefs;
137  delete [] degs;
138  delete [] names;
139  delete [] acc;
140  }
141  /**
142  * Overload operator =
143  *
144  * @param b: A multivariate modular polynomial
145  **/
147  if (this != &b) {
148  delete [] coefs;
149  delete [] degs;
150  delete [] names;
151  delete [] acc;
152 
153  var = b.var;
154  degs = new int[var];
155  std::copy(b.degs, b.degs+var, degs);
156  acc = new int[var];
157  std::copy(b.acc, b.acc+var, acc);
158  n = b.n;
159  coefs = new sfixn[n];
160  std::copy(b.coefs, b.coefs+n, coefs);
161  names = new std::string[var+1];
162  std::copy(b.names, b.names+var+1, names);
163  p = b.p;
164  }
165  return *this;
166  }
167 
168 
169  /**
170  * Is a zero polynomial
171  *
172  * @param
173  **/
174  inline bool isZero() {
175  for (int i = 0; i < n; ++i) {
176  if (coefs[i] != 0)
177  return 0;
178  }
179  return 1;
180  }
181  /**
182  * Zero polynomial
183  *
184  * @param
185  **/
186  inline void zero() {
187  zeros();
188  }
189  /**
190  * Is polynomial 1
191  *
192  * @param
193  **/
194  inline bool isOne() {
195  for (int i = 1; i < n; ++i) {
196  if (coefs[i] != 0)
197  return 0;
198  }
199  return (coefs[0] == 1);
200  }
201  /**
202  * Set polynomial to 1
203  *
204  * @param
205  **/
206  inline void one() {
207  coefs[0] = 1;
208  for (int i = 1; i < n; ++i)
209  coefs[i] = 0;
210  }
211  /**
212  * Is polynomial -1
213  *
214  * @param
215  **/
216  inline bool isNegativeOne() {
217  for (int i = 1; i < n; ++i) {
218  if (coefs[i] != 0)
219  return 0;
220  }
221  return (coefs[0] == p - 1);
222  }
223  /**
224  * Set polynomial to -1
225  *
226  * @param
227  **/
228  inline void negativeOne() {
229  coefs[0] = p - 1;
230  for (int i = 1; i < n; ++i)
231  coefs[i] = 0;
232  }
233  /**
234  * Is a constant
235  *
236  * @param
237  **/
238  inline int isConstant() {
239  for (int i = 1; i < n; ++i) {
240  if (coefs[i] != 0)
241  return 0;
242  }
243  if (coefs[0] < (p >> 1)) { return 1; }
244  else { return -1; }
245  }
246  /**
247  * Get the number of variables
248  *
249  * @param
250  **/
251  inline int numberOfVariables() {
252  return var;
253  }
254  /**
255  * Get the number of non-zero terms
256  *
257  * @param
258  **/
259  inline int numberOfTerms() {
260  int k = 0;
261  for (int i = 0; i < n; ++i)
262  if (coefs[i] != 0) { k++; }
263  return k;
264  }
265  /**
266  * Get the size of the polynomial
267  *
268  * @param
269  **/
270  inline int size() {
271  return n;
272  }
273  /**
274  * Get a partial degree of variable x
275  *
276  * @param x: The variable name
277  **/
278  inline int degree(std::string x) {
279  int k = 0, d = 0;
280  for (int i = 1; i <= var; ++i) {
281  if (names[i] == x) {
282  k = i;
283  break;
284  }
285  }
286  if (k) {
287  k--;
288  for (int i = 0; i < n; ++i) {
289  int e = (i / acc[k]) % (degs[k] + 1);
290  if (coefs[i] != 0 && e > d)
291  d = e;
292  }
293  }
294  return d;
295  }
296  /**
297  * Get the leading coefficient
298  *
299  * @param
300  **/
301  inline sfixn leadingCoefficient() {
302  for (int i = n-1; i > -1; --i) {
303  if (coefs[i] != 0)
304  return coefs[i];
305  }
306  return 0;
307  }
308  /**
309  * Get a coefficient
310  *
311  * @param v: Number of variables
312  * @param d: The exponent of each variable
313  **/
314  inline sfixn coefficient(int v, int* d) {
315  int k = 0;
316  for (int i = var-1, j = 0; i > -1 && j < v; --i, ++j) {
317  if (d[j] <= degs[i])
318  k += d[j] * acc[i];
319  else { return 0; }
320  }
321  for (int i = v-var-1; i > -1; --i)
322  if (d[i]) { return 0; }
323  return coefs[k];
324  }
325  /**
326  * Set a coefficient
327  *
328  * @param v: Number of variables
329  * @param d: The exponent of each variable
330  * @param val: Value of the coefficient
331  **/
332  inline void setCoefficient(int v, int* d, sfixn val) {
333  if (v != var) {
334  std::cout << "BPAS: error, SFDDMMP(" << var << "), but trying to setCoefficient with " << v << " variables." << std::endl;
335  exit(1);
336  }
337  int k = 0;
338  for (int i = var-1, j = 0; i > -1 && j < v; --i, ++j) {
339  if (d[j] <= degs[i])
340  k += d[j] * acc[i];
341  else {
342  std::cout << "BPAS: error, the degree of " << names[i+1] << " in SFDDMMP is " << degs[i] << "." << std::endl;
343  exit(1);
344  }
345  }
346  coefs[k] = val;
347  }
348  /**
349  * Set a coefficient
350  *
351  * @param k: The offset in the coefficient array
352  * @param val: Value of the coefficient
353  **/
354  inline void setCoefficient(int k, sfixn val) {
355  if (k >= n || k < 0) {
356  std::cout << "BPAS: error, trying to access a non-exist coefficient in SFDDMMP<Field>." << std::endl;
357  exit(1);
358  }
359  coefs[k] = val;
360  }
361  /**
362  * Get variable names
363  *
364  * @param
365  **/
366  inline std::vector<std::string> variables() {
367  std::vector<std::string> xs;
368  for (int i = var; i > 0; --i)
369  xs.push_back(names[i]);
370  return xs;
371  }
372  /**
373  * Set variable names
374  *
375  * @param xs: Variable names
376  **/
377  inline void setVariableNames (std::vector<std::string> xs) {
378  int ns = xs.size();
379  if (ns != var) {
380  std::cout << "BPAS: error, SFDDMMP(" << var << "), but trying to setVariableNames with " << ns << " variables." << std::endl;
381  exit(1);
382  }
383  names[0] = "9";
384  for (int i = var, j = 0; i > 0 && j < ns; --i, ++j)
385  names[i] = xs[j];
386  }
387 
388  /**
389  * Overload operator ==
390  *
391  * @param b: A multivariate modular polynomial
392  **/
394  /**
395  * Overload operator !=
396  *
397  * @param b: A multivariate modular polynomial
398  **/
400  return !(*this == b);
401  }
402  /**
403  * Overload operator +
404  *
405  * @param b: A multivariate modular polynomial
406  **/
408  /**
409  * Overload operator +=
410  *
411  * @param b: A multivariate modular polynomial
412  **/
414  *this = *this + b;
415  return *this;
416  }
417  /**
418  * Overload operator +
419  *
420  * @param e: A constant
421  **/
424  return (r += e);
425  }
427  return (f + e);
428  }
429  /**
430  * Overload operator +=
431  *
432  * @param e: A constant
433  **/
435  /**
436  * Overload operator -
437  *
438  * @param b: A multivariate modular polynomial
439  **/
441  /**
442  * Overload operator -=
443  *
444  * @param b: A multivariate modular polynomial
445  **/
447  *this = *this - b;
448  return *this;
449  }
450  /**
451  * Overload operator -
452  *
453  * @param e: A constant
454  **/
457  return (r -= e);
458  }
460  return (-r + e);
461  }
462  /**
463  * Overload operator -=
464  *
465  * @param e: A constant
466  **/
468  /**
469  * Overload operator -, negate
470  *
471  * @param
472  **/
474  /**
475  * Negate, f(-x)
476  *
477  * @param
478  **/
479  void negate();
480  /**
481  * Overload operator *
482  *
483  * @param b: A multivariate modular polynomial
484  **/
486  /**
487  * Overload operator *=
488  *
489  * @param b: A multivariate modular polynomial
490  **/
492  *this = *this * b;
493  return *this;
494  }
495  /**
496  * Overload operator *
497  *
498  * @param e: A constant
499  **/
502  return (r *= e);
503  }
505  return (f * e);
506  }
507  /**
508  * Overload operator *=
509  *
510  * @param e: A constant
511  **/
513 
514  /**
515  * Overload stream operator <<
516  *
517  * @param out: Stream object
518  * @param b: The multivariate modular polynomial
519  **/
520  friend std::ostream& operator<< (std::ostream &out, SmallPrimeFieldDistributedDenseMultivariateModularPolynomial b);
521 };
522 
523 #endif
524 /* This file is part of the BPAS library http://www.bpaslib.org
525 
526  BPAS is free software: you can redistribute it and/or modify
527  it under the terms of the GNU General Public License as published by
528  the Free Software Foundation, either version 3 of the License, or
529  (at your option) any later version.
530 
531  BPAS is distributed in the hope that it will be useful,
532  but WITHOUT ANY WARRANTY; without even the implied warranty of
533  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
534  GNU General Public License for more details.
535 
536  You should have received a copy of the GNU General Public License
537  along with BPAS. If not, see <http://www.gnu.org/licenses/>.
538 
539  Copyright: Changbo Chen <changbo.chen@hotmail.com>
540  Farnam Mansouri <mansouri.farnam@gmail.com>
541  Marc Moreno Maza <moreno@csd.uwo.ca>
542  Ning Xie <nxie6@csd.uwo.ca>
543  Yuzhen Xie <yuzhenxie@yahoo.ca>
544 
545 */
546 
547 
friend std::ostream & operator<<(std::ostream &out, SmallPrimeFieldDistributedDenseMultivariateModularPolynomial b)
SmallPrimeFieldDistributedDenseMultivariateModularPolynomial operator+(SmallPrimeFieldDistributedDenseMultivariateModularPolynomial b)
SmallPrimeFieldDistributedDenseMultivariateModularPolynomial & operator+=(SmallPrimeFieldDistributedDenseMultivariateModularPolynomial b)
Definition: sdmpolynomial.h:413
SmallPrimeFieldDistributedDenseMultivariateModularPolynomial operator*(SmallPrimeFieldDistributedDenseMultivariateModularPolynomial b)
bool isNegativeOne()
Definition: sdmpolynomial.h:216
void setVariableNames(std::vector< std::string > xs)
Definition: sdmpolynomial.h:377
SmallPrimeFieldDistributedDenseMultivariateModularPolynomial(const SmallPrimeFieldDistributedDenseMultivariateModularPolynomial &b)
Definition: sdmpolynomial.h:120
int numberOfTerms()
Definition: sdmpolynomial.h:259
~SmallPrimeFieldDistributedDenseMultivariateModularPolynomial()
Definition: sdmpolynomial.h:135
SmallPrimeFieldDistributedDenseMultivariateModularPolynomial & operator=(SmallPrimeFieldDistributedDenseMultivariateModularPolynomial b)
Definition: sdmpolynomial.h:146
bool operator!=(SmallPrimeFieldDistributedDenseMultivariateModularPolynomial &b)
Definition: sdmpolynomial.h:399
bool operator==(SmallPrimeFieldDistributedDenseMultivariateModularPolynomial &b)
sfixn coefficient(int v, int *d)
Definition: sdmpolynomial.h:314
SmallPrimeFieldDistributedDenseMultivariateModularPolynomial(int v, int *ds, sfixn m)
Definition: sdmpolynomial.h:75
Definition: polynomial.h:74
SmallPrimeFieldDistributedDenseMultivariateModularPolynomial & operator*=(SmallPrimeFieldDistributedDenseMultivariateModularPolynomial b)
Definition: sdmpolynomial.h:491
SmallPrimeFieldDistributedDenseMultivariateModularPolynomial()
Definition: sdmpolynomial.h:42
void setCoefficient(int v, int *d, sfixn val)
Definition: sdmpolynomial.h:332
SmallPrimeFieldDistributedDenseMultivariateModularPolynomial(std::string x, sfixn m)
Definition: sdmpolynomial.h:103
SmallPrimeFieldDistributedDenseMultivariateModularPolynomial operator-()
void setCoefficient(int k, sfixn val)
Definition: sdmpolynomial.h:354
int degree(std::string x)
Definition: sdmpolynomial.h:278
std::vector< std::string > variables()
Definition: sdmpolynomial.h:366
SmallPrimeFieldDistributedDenseMultivariateModularPolynomial(sfixn m)
Definition: sdmpolynomial.h:58
SmallPrimeFieldDistributedDenseMultivariateModularPolynomial & operator-=(SmallPrimeFieldDistributedDenseMultivariateModularPolynomial b)
Definition: sdmpolynomial.h:446
void negativeOne()
Definition: sdmpolynomial.h:228
sfixn leadingCoefficient()
Definition: sdmpolynomial.h:301
int numberOfVariables()
Definition: sdmpolynomial.h:251