Basic Polynomial Algebra Subprograms (BPAS)  v. 1.652
Integer.hpp
1
2 #ifndef _BPAS_INTEGER_H_
3 #define _BPAS_INTEGER_H_
4
5 #include "BPASEuclideanDomain.hpp"
6 #include <gmpxx.h>
7
8 //forward declarations
9 class RationalNumber;
11 class SmallPrimeField;
12 class BigPrimeField;
16 template <class Ring>
18
19 /**
20  * An arbitrary-precision Integer.
21  */
22 class Integer : public BPASEuclideanDomain<Integer> {
23  private:
24  mpz_class _m;
25  public:
26  static mpz_class characteristic;
27  static RingProperties properties;
28  // static bool isPrimeField;
29  // static bool isSmallPrimeField;
30  // static bool isComplexField;
31
32  /**
33  * Get a zero integer.
34  */
35  Integer ();
36
37  /**
38  * Construct and Integer from an int.
39  */
40  Integer (int a);
41
42  /**
43  * Construct an integer form a GMP mpz_t.
44  */
45  Integer (const mpz_t& a);
46
47  /**
48  * Construct an integer from a GMP mpz_class.
49  */
50  Integer (const mpz_class& a);
51  // Integer (mpz_class a);
52
53  /**
54  * Copy assignment from another Integer.
55  */
56  Integer (const Integer& a);
57
58  /**
59  * Attempts to construct an Integer from a rational number.
60  * If the conversion is not exact, causes an error.
61  */
62  explicit Integer (const RationalNumber& a);
63
64  /**
65  * Attempts to construct an Integer from a complex rational number.
66  * If the conversion is not exact, causes an error.
67  */
68  explicit Integer (const ComplexRationalNumber& a);
69
70  /**
71  * Attempts to construct an Integer from a SmallPrimeField.
72  * If the conversion is not exact, causes an error.
73  */
74  explicit Integer (const SmallPrimeField& a);
75
76  /**
77  * Attempts to construct an Integer from a BigPrimeField.
78  * If the conversion is not exact, causes an error.
79  */
80  explicit Integer (const BigPrimeField& a);
81
82  /**
83  * Attempts to construct an Integer from a GeneralizedFermatPrimeField.
84  * If the conversion is not exact, causes an error.
85  */
86  explicit Integer (const GeneralizedFermatPrimeField& a);
87
88  /**
89  * Attempts to construct an Integer from a DenseUnivariateIntegerPolynomial.
90  * If the conversion is not exact, causes an error.
91  */
92  explicit Integer (const DenseUnivariateIntegerPolynomial& a);
93
94  /**
95  * Attempts to construct an Integer from a DenseUnivariateRationalPolynomial.
96  * If the conversion is not exact, causes an error.
97  */
98  explicit Integer (const DenseUnivariateRationalPolynomial& a);
99
100  /**
101  * Attempts to construct an Integer from a SparseUnivariatePolynomial<Integer>.
102  * If the conversion is not exact, causes an error.
103  */
104  explicit Integer (const SparseUnivariatePolynomial<Integer>& a);
105
106  /**
107  * Attempts to construct an Integer from a SparseUnivariatePolynomial<RationalNumber>.
108  * If the conversion is not exact, causes an error.
109  */
111
112  /**
113  * Attempts to construct an Integer from a SparseUnivariatePolynomial<ComplexRationalNumber>.
114  * If the conversion is not exact, causes an error.
115  */
117
118  /**
119  * Attempts to construct an Integer from a SparseUniveraitePolynomial<Ring>
120  * for a generic ring. If the conversion is not exact, causes an error.
121  */
122  template <class Ring>
123  explicit Integer (const SparseUnivariatePolynomial<Ring>& a);
124
125  inline mpz_class& get_mpz_ref() {
126  return _m;
127  }
128
129  inline const mpz_class& get_mpz_ref() const {
130  return _m;
131  }
132
133  inline mpz_class get_mpz () const {
134  return _m;
135  }
136
137  inline mpz_ptr get_mpz_t() {
138  return _m.get_mpz_t();
139  }
140
141  inline mpz_srcptr get_mpz_t() const {
142  return _m.get_mpz_t();
143  }
144
145
146  inline double get_d() const {
147  return _m.get_d();
148  }
149
150  inline long int get_si() const {
151  return _m.get_si();
152  }
153
154  inline unsigned long int get_ui() const {
155  return _m.get_ui();
156  }
157
158  /**
159  * Is a zero
160  *
161  * @param
162  **/
163  inline bool isZero() const {
164  return (_m == 0);
165  }
166
167  /**
168  * Assign to zero
169  *
170  * @param
171  **/
172  inline void zero() {
173  _m = 0;
174  }
175
176  /**
177  * Is a 1
178  *
179  * @param
180  **/
181  inline bool isOne() const {
182  return (_m == 1);
183  }
184
185  /**
186  * Assign to one
187  *
188  * @param
189  **/
190  inline void one() {
191  _m = 1;
192  }
193
194  /**
195  * Is a -1
196  *
197  * @param
198  **/
199  inline bool isNegativeOne() const {
200  return (_m == -1);
201  }
202
203  /**
204  * Assign to negative one
205  *
206  * @param
207  **/
208  inline void negativeOne() {
209  _m = -1;
210  }
211
212  /**
213  * Is a constant
214  *
215  * @param
216  **/
217  inline int isConstant() const {
218  if (_m >= 0)
219  return 1;
220  else { return -1; }
221  }
222
223  /**
224  * Obtain the unit normal (a.k.a canonical associate) of an element.
225  * If either parameters u, v, are non-NULL then the units are returned such that
226  * b = ua, v = u^-1. Where b is the unit normal of a, and is the returned value.
227  */
228  Integer unitCanonical(Integer* u = NULL, Integer* v = NULL) const;
229
230  /**
231  * Copy assignment.
232  */
233  Integer& operator= (const Integer& a);
234
235  /**
236  * Addition.
237  */
238  inline Integer operator+ (const Integer& i) const {
239  Integer ret = *this;
240  ret += i;
241  return ret;
242  }
243
244  /**
245  * Addition assignment.
246  */
247  inline Integer& operator+= (const Integer& i) {
248  _m += i._m;
249  return *this;
250  }
251
252  /**
253  * Subtraction.
254  */
255  inline Integer operator- (const Integer& i) const {
256  Integer ret = *this;
257  ret -= i;
258  return ret;
259  }
260
261  /**
262  * Subtraction assignment.
263  */
264  inline Integer& operator-= (const Integer& i) {
265  _m -= i._m;
266  return *this;
267  }
268
269  /**
270  * Negation.
271  */
272  inline Integer operator- () const {
273  Integer ret;
274  mpz_neg(ret._m.get_mpz_t(), _m.get_mpz_t());
275  return ret;
276  }
277
278  /**
279  * Multiplication.
280  */
281  inline Integer operator* (const Integer& i) const {
282  Integer ret = *this;
283  ret *= i;
284  return ret;
285  }
286
287  /**
288  * Multiplication assignment.
289  */
290  inline Integer& operator*= (const Integer& i) {
291  _m *= i._m;
292  return *this;
293  }
294
295  /**
296  * Exponentiation.
297  */
298  inline Integer operator^ (long long int e) const {
299  Integer r;
300  mpz_pow_ui(r._m.get_mpz_t(), _m.get_mpz_t(), (unsigned long int) e);
301  return r;
302  }
303
304  /**
305  * Exponentiation assignment.
306  */
307  inline Integer& operator^= (long long int e) {
308  *this = *this ^ e;
309  return *this;
310  }
311
312  /**
313  * Equality test,
314  *
315  * returns true iff equal
316  */
317  inline bool operator== (const Integer& i) const {
318  return (mpz_cmp(_m.get_mpz_t(), i._m.get_mpz_t()) == 0);
319  }
320
321  /**
322  * Inequality test,
323  *
324  * returns true iff not equal.
325  */
326  inline bool operator!= (const Integer& i) const {
327  return (mpz_cmp(_m.get_mpz_t(), i._m.get_mpz_t()) != 0);
328  }
329
330  inline bool operator< (const Integer& r) const {
331  return _m < r._m;
332  }
333
334  inline bool operator<= (const Integer& r) const {
335  return _m <= r._m;
336  }
337
338  inline bool operator> (const Integer& r) const {
339  return _m > r._m;
340  }
341
342  inline bool operator>= (const Integer& r) const {
343  return _m >= r._m;
344  }
345
346  /**
347  * Convert this to an expression tree.
348  *
349  * returns an expression tree describing *this.
350  */
352  return ExpressionTree(new ExprTreeNode(_m));
353
354  }
355
356  /**
357  * Exact division.
358  */
359  inline Integer operator/ (const Integer& i) const {
360  //TODO ensure this is exact and not rounded
361  Integer ret = *this;
362  ret /= i;
363  return ret;
364  }
365
366  /**
367  * Exact division assignment.
368  */
369  inline Integer& operator/= (const Integer& i) {
370  if (mpz_divisible_p(_m.get_mpz_t(), i._m.get_mpz_t())) {
371  mpz_divexact(_m.get_mpz_t(), _m.get_mpz_t(), i._m.get_mpz_t());
372  } else {
373  std::cerr << "BPAS ERROR: Non-exact division in Integer: " << _m << " / " << i._m << std::endl;
374  exit(1);
375  }
376  return *this;
377  }
378
379  inline Integer operator% (const Integer& r) const {
380  Integer ret(this->_m % r._m);
381  return ret;
382  }
383
384  inline Integer& operator%= (const Integer& r) {
385  _m = _m % r._m;
386  return *this;
387  }
388
389  /**
390  * Get GCD of *this and other.
391  */
392  inline Integer gcd(const Integer& other) const {
393  Integer c;
394  mpz_gcd(c._m.get_mpz_t(), _m.get_mpz_t(), other._m.get_mpz_t());
395  return c;
396  }
397  /**
398  * Compute squarefree factorization of *this
399  */
400  inline Factors<Integer> squareFree() const {
401  std::vector<Integer> ret;
402  ret.push_back(*this);
403  return ret;
404  }
405
406  /**
407  * Get the euclidean size of *this.
408  */
409  inline Integer euclideanSize() const {
410  if (*this < 0) {
411  return -(*this);
412  }
413  return *this;
414  }
415
416  /**
417  * Perform the eucldiean division of *this and b. Returns the
418  * remainder. If q is not NULL, then returns the quotient in q.
419  */
420  Integer euclideanDivision(const Integer& b, Integer* q = NULL) const;
421
422  /**
423  * Perform the extended euclidean division on *this and b.
424  * Returns the GCD. If s and t are not NULL, returns the bezout coefficients in them.
425  */
426  Integer extendedEuclidean(const Integer& b, Integer* s = NULL, Integer* t = NULL) const;
427
428  /**
429  * Get the quotient of *this and b.
430  */
431  Integer quotient(const Integer& b) const;
432
433  /**
434  * Get the remainder of *this and b.
435  */
436  Integer remainder(const Integer& b) const;
437
438
439  inline friend Integer operator+(int a, const Integer& r) {
440  return Integer(mpz_class(a) + r._m);
441  }
442
443  inline friend Integer operator-(int a, const Integer& r) {
444  return Integer(mpz_class(a) - r._m);
445  }
446
447  inline friend Integer operator*(int a, const Integer& r) {
448  return Integer(mpz_class(a) * r._m);
449  }
450
451  inline friend Integer operator/(int a, const Integer& r) {
452  return Integer(mpz_class(a) / r._m);
453  }
454
455  inline friend bool operator<(int a, const Integer& r) {
456  return r > a;
457  }
458
459  inline friend bool operator<=(int a, const Integer& r) {
460  return r >= a;
461  }
462
463  inline friend bool operator>(int a, const Integer& r) {
464  return r < a;
465  }
466
467  inline friend bool operator>=(int a, const Integer& r) {
468  return r <= a;
469  }
470
471  inline friend Integer operator+(long int a, const Integer& r) {
472  return Integer(mpz_class(a) + r._m);
473  }
474
475  inline friend Integer operator-(long int a, const Integer& r) {
476  return Integer(mpz_class(a) - r._m);
477  }
478
479  inline friend Integer operator*(long int a, const Integer& r) {
480  return Integer(mpz_class(a) * r._m);
481  }
482
483  inline friend Integer operator/(long int a, const Integer& r) {
484  return Integer(mpz_class(a) / r._m);
485  }
486
487  inline friend Integer abs(const Integer& i) {
488  return Integer(abs(i._m));
489  }
490
491  inline friend bool operator<(long int a, const Integer& r) {
492  return r > a;
493  }
494
495  inline friend bool operator<=(long int a, const Integer& r) {
496  return r >= a;
497  }
498
499  inline friend bool operator>(long int a, const Integer& r) {
500  return r < a;
501  }
502
503  inline friend bool operator>=(long int a, const Integer& r) {
504  return r <= a;
505  }
506
507
508 };
509
510 #endif
Integer operator-() const
Negation.
Definition: Integer.hpp:272
Integer & operator-=(const Integer &i)
Subtraction assignment.
Definition: Integer.hpp:264
Integer extendedEuclidean(const Integer &b, Integer *s=NULL, Integer *t=NULL) const
Perform the extended euclidean division on *this and b.
A univariate polynomial over an arbitrary BPASRing represented sparsely.
Definition: BigPrimeField.hpp:21
void negativeOne()
Assign to negative one.
Definition: Integer.hpp:208
Integer operator/(const Integer &i) const
Exact division.
Definition: Integer.hpp:359
Integer quotient(const Integer &b) const
Get the quotient of *this and b.
Integer()
Get a zero integer.
An arbitrary-precision complex rational number.
Definition: ComplexRationalNumber.hpp:23
Integer operator+(const Integer &i) const
Addition.
Definition: Integer.hpp:238
Integer & operator/=(const Integer &i)
Exact division assignment.
Definition: Integer.hpp:369
An ExpressionTree encompasses various forms of data that can be expressed generically as a binary tre...
Definition: ExpressionTree.hpp:17
Integer euclideanSize() const
Get the euclidean size of *this.
Definition: Integer.hpp:409
A finite field whose prime should be a generalized fermat number.
Definition: GeneralizedFermatPrimeField.hpp:36
Integer unitCanonical(Integer *u=NULL, Integer *v=NULL) const
Obtain the unit normal (a.k.a canonical associate) of an element.
A prime field whose prime is 32 bits or less.
Definition: SmallPrimeField.hpp:449
A univariate polynomial with Integer coefficients using a dense representation.
Definition: uzpolynomial.h:13
bool operator!=(const Integer &i) const
Inequality test,.
Definition: Integer.hpp:326
Integer & operator*=(const Integer &i)
Multiplication assignment.
Definition: Integer.hpp:290
A univariate polynomial with RationalNumber coefficients represented densely.
Definition: urpolynomial.h:15
bool operator==(const Integer &i) const
Equality test,.
Definition: Integer.hpp:317
Integer remainder(const Integer &b) const
Get the remainder of *this and b.
A prime field whose prime can be arbitrarily large.
Definition: BigPrimeField.hpp:27
bool isNegativeOne() const
Is a -1.
Definition: Integer.hpp:199
int isConstant() const
Is a constant.
Definition: Integer.hpp:217
Integer gcd(const Integer &other) const
Get GCD of *this and other.
Definition: Integer.hpp:392
Integer & operator^=(long long int e)
Exponentiation assignment.
Definition: Integer.hpp:307
A simple data structure for encapsulating a collection of Factor elements.
Definition: Factors.hpp:95
ExpressionTree convertToExpressionTree() const
Convert this to an expression tree.
Definition: Integer.hpp:351
Integer & operator%=(const Integer &r)
Assign *this to be the remainder of *this and b.
Definition: Integer.hpp:384
An arbitrary-precision Integer.
Definition: Integer.hpp:22
Integer & operator=(const Integer &a)
Copy assignment.
Integer operator%(const Integer &r) const
Get the remainder of *this and b;.
Definition: Integer.hpp:379
Integer & operator+=(const Integer &i)
Addition assignment.
Definition: Integer.hpp:247
An abstract class defining the interface of a Euclidean domain.
Definition: BPASEuclideanDomain.hpp:12
An arbitrary-precision rational number.
Definition: RationalNumber.hpp:24
virtual mpz_class characteristic()
The characteristic of this ring class.
Definition: BPASRing.hpp:87
Factors< Integer > squareFree() const
Compute squarefree factorization of *this.
Definition: Integer.hpp:400
Integer operator^(long long int e) const
Exponentiation.
Definition: Integer.hpp:298
void zero()
Assign to zero.
Definition: Integer.hpp:172
Integer euclideanDivision(const Integer &b, Integer *q=NULL) const
Perform the eucldiean division of *this and b.
ExprTreeNode is a single node in the bianry tree of an ExpressionTree.
Definition: ExprTreeNode.hpp:76
bool isZero() const
Is a zero.
Definition: Integer.hpp:163
Integer operator*(const Integer &i) const
Multiplication.
Definition: Integer.hpp:281
bool isOne() const
Is a 1.
Definition: Integer.hpp:181
void one()
Assign to one.
Definition: Integer.hpp:190