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