1 |
|
#pragma once |
2 |
|
|
3 |
|
#include <gmpxx.h> |
4 |
|
|
5 |
|
#include <iosfwd> |
6 |
|
|
7 |
|
#include "../integer.h" |
8 |
|
#include "integer_ring.h" |
9 |
|
|
10 |
|
namespace poly { |
11 |
|
|
12 |
|
class Rational; |
13 |
|
|
14 |
|
/** |
15 |
|
* Implements a wrapper for lp_integer_t. |
16 |
|
*/ |
17 |
|
class Integer { |
18 |
|
/** The actual integer. */ |
19 |
|
lp_integer_t mInt; |
20 |
|
|
21 |
|
public: |
22 |
|
/** Constructs zero. */ |
23 |
|
Integer(); |
24 |
|
/** Constructs from an int. */ |
25 |
|
explicit Integer(int i); |
26 |
|
/** Constructs from a long. */ |
27 |
|
explicit Integer(long i); |
28 |
|
/** Constructs from a long into the given ring. */ |
29 |
|
Integer(const IntegerRing& ir, long i); |
30 |
|
/** Constructs from a string. */ |
31 |
|
Integer(const char* x, int base); |
32 |
|
/** Constructs from a string into the given ring. */ |
33 |
|
Integer(const IntegerRing& ir, const char* x, int base); |
34 |
|
/** Constructs as copy. */ |
35 |
|
Integer(const Integer& i); |
36 |
|
/** Constructs as copy into the given ring. */ |
37 |
|
Integer(const IntegerRing& ir, const Integer& i); |
38 |
|
/** Constructs as copy, assuming the rational is indeed an integer. */ |
39 |
|
explicit Integer(const Rational& r); |
40 |
|
/** Constructs as copy, assuming the rational is indeed an integer, into the |
41 |
|
* given ring. */ |
42 |
|
Integer(const IntegerRing& ir, const Rational& r); |
43 |
|
|
44 |
|
/** Construct from a mpz_class, which is the underlying representation |
45 |
|
* anyway. */ |
46 |
|
explicit Integer(const mpz_class& m); |
47 |
|
/** Construct from a mpz_class, which is the underlying representation |
48 |
|
* anyway, into the given ring. */ |
49 |
|
Integer(const IntegerRing& ir, const mpz_class& m); |
50 |
|
/** Construct from an internal lp_integer_t pointer. */ |
51 |
|
explicit Integer(const lp_integer_t* i); |
52 |
|
/** Construct from an internal lp_integer_t pointer into the given ring. */ |
53 |
|
Integer(const IntegerRing& ir, const lp_integer_t* i); |
54 |
|
|
55 |
|
/** Custom destructor. */ |
56 |
|
~Integer(); |
57 |
|
/** Assign from an Integer. */ |
58 |
|
Integer& operator=(const Integer& i); |
59 |
|
/** Assign from an Integer into the given ring. */ |
60 |
|
Integer& assign(const IntegerRing& ir, const Integer& i); |
61 |
|
/** Move from an Integer. */ |
62 |
|
Integer& operator=(Integer&& i); |
63 |
|
/** Move from an Integer into the given ring. */ |
64 |
|
Integer& assign(const IntegerRing& ir, Integer&& i); |
65 |
|
/** Assign from the given integer. */ |
66 |
|
Integer& operator=(long i); |
67 |
|
/** Assign from the given integer into the given ring. */ |
68 |
|
Integer& assign(const IntegerRing& ir, long i); |
69 |
|
|
70 |
|
/** Get a non-const pointer to the internal lp_integer_t. Handle with care! |
71 |
|
*/ |
72 |
|
lp_integer_t* get_internal(); |
73 |
|
/** Get a const pointer to the internal lp_integer_t. */ |
74 |
|
const lp_integer_t* get_internal() const; |
75 |
|
}; |
76 |
|
|
77 |
|
/** Make sure that we can cast between Integer and lp_integer_t. */ |
78 |
|
static_assert(sizeof(Integer) == sizeof(lp_integer_t), |
79 |
|
"Please check the size of Integer."); |
80 |
|
static_assert(sizeof(Integer) == sizeof(mpz_class), |
81 |
|
"Please check the size of Integer."); |
82 |
|
namespace detail { |
83 |
|
/** Non-const cast from an Integer to a lp_integer_t. */ |
84 |
|
inline lp_integer_t* cast_to(Integer* i) { |
85 |
|
return reinterpret_cast<lp_integer_t*>(i); |
86 |
|
} |
87 |
|
/** Const cast from an Integer to a lp_integer_t. */ |
88 |
|
inline const lp_integer_t* cast_to(const Integer* i) { |
89 |
|
return reinterpret_cast<const lp_integer_t*>(i); |
90 |
|
} |
91 |
|
/** Non-const cast from an Integer to a mpz_class. */ |
92 |
|
inline mpz_class* cast_to_gmp(Integer* i) { |
93 |
|
return reinterpret_cast<mpz_class*>(i); |
94 |
|
} |
95 |
|
/** Const cast from an Integer to a mpz_class. */ |
96 |
123 |
inline const mpz_class* cast_to_gmp(const Integer* i) { |
97 |
123 |
return reinterpret_cast<const mpz_class*>(i); |
98 |
|
} |
99 |
|
/** Non-const cast from a lp_integer_t to an Integer. */ |
100 |
|
inline Integer* cast_from(lp_integer_t* i) { |
101 |
|
return reinterpret_cast<Integer*>(i); |
102 |
|
} |
103 |
|
/** Const cast from a lp_integer_t to an Integer. */ |
104 |
|
inline const Integer* cast_from(const lp_integer_t* i) { |
105 |
|
return reinterpret_cast<const Integer*>(i); |
106 |
|
} |
107 |
|
/** Non-const cast from a mpz_class to an Integer. */ |
108 |
|
inline Integer* cast_from(mpz_class* i) { |
109 |
|
return reinterpret_cast<Integer*>(i); |
110 |
|
} |
111 |
|
/** Const cast from a mpz_class to an Integer. */ |
112 |
|
inline const Integer* cast_from(const mpz_class* i) { |
113 |
|
return reinterpret_cast<const Integer*>(i); |
114 |
|
} |
115 |
|
} // namespace detail |
116 |
|
|
117 |
|
/** Stream the given Integer to an output stream. */ |
118 |
|
std::ostream& operator<<(std::ostream& os, const Integer& i); |
119 |
|
|
120 |
|
/** Number of bits needed for the given integer. */ |
121 |
|
std::size_t bit_size(const Integer& i); |
122 |
|
|
123 |
|
/** Compare two integers. */ |
124 |
|
bool operator==(const Integer& lhs, const Integer& rhs); |
125 |
|
/** Compare two integers. */ |
126 |
|
bool operator!=(const Integer& lhs, const Integer& rhs); |
127 |
|
/** Compare two integers according to the lexicographic ordering on (lower bound,upper bound). */ |
128 |
|
bool operator<(const Integer& lhs, const Integer& rhs); |
129 |
|
/** Compare two integers according to the lexicographic ordering on (lower bound,upper bound). */ |
130 |
|
bool operator<=(const Integer& lhs, const Integer& rhs); |
131 |
|
/** Compare two integers according to the lexicographic ordering on (lower bound,upper bound). */ |
132 |
|
bool operator>(const Integer& lhs, const Integer& rhs); |
133 |
|
/** Compare two integers according to the lexicographic ordering on (lower bound,upper bound). */ |
134 |
|
bool operator>=(const Integer& lhs, const Integer& rhs); |
135 |
|
|
136 |
|
/** Compare two integers over the given ring. */ |
137 |
|
int compare(const IntegerRing& ir, const Integer& lhs, const Integer& rhs); |
138 |
|
/** Compare two integers over the given ring. */ |
139 |
|
int compare(const IntegerRing& ir, const Integer& lhs, long rhs); |
140 |
|
/** Compare two integers over the given ring. */ |
141 |
|
int compare(const IntegerRing& ir, long lhs, const Integer& rhs); |
142 |
|
|
143 |
|
/** Checks whether lhs divides rhs. */ |
144 |
|
bool divides(const Integer& lhs, const Integer& rhs); |
145 |
|
/** Checks whether lhs divides rhs over the given ring. */ |
146 |
|
bool divides(const IntegerRing& ir, const Integer& lhs, const Integer& rhs); |
147 |
|
|
148 |
|
/** Swaps the contents of two integers. */ |
149 |
|
void swap(Integer& lhs, Integer& rhs); |
150 |
|
|
151 |
|
/** Pre-increment an integer. */ |
152 |
|
Integer& operator++(Integer& i); |
153 |
|
/** Pre-decrement an integer. */ |
154 |
|
Integer& operator--(Integer& i); |
155 |
|
/** Post-increment an integer. */ |
156 |
|
Integer operator++(Integer& i, int); |
157 |
|
/** Post-decrement an integer. */ |
158 |
|
Integer operator--(Integer& i, int); |
159 |
|
/** Pre-increment an integer. */ |
160 |
|
Integer& increment(const IntegerRing& ir, Integer& i); |
161 |
|
/** Pre-decrement an integer. */ |
162 |
|
Integer& decrement(const IntegerRing& ir, Integer& i); |
163 |
|
|
164 |
|
/** Add two integers. */ |
165 |
|
Integer operator+(const Integer& lhs, const Integer& rhs); |
166 |
|
/** Add and assign two integers. */ |
167 |
|
Integer& operator+=(Integer& lhs, const Integer& rhs); |
168 |
|
/** Add two integers in the given ring. */ |
169 |
|
Integer add(const IntegerRing& ir, const Integer& lhs, const Integer& rhs); |
170 |
|
/** Add and assign two integers in the given ring. */ |
171 |
|
Integer& add_assign(const IntegerRing& ir, Integer& lhs, const Integer& rhs); |
172 |
|
|
173 |
|
/** Subtract two integers. */ |
174 |
|
Integer operator-(const Integer& lhs, const Integer& rhs); |
175 |
|
/** Subtract and assign two integers. */ |
176 |
|
Integer& operator-=(Integer& lhs, const Integer& rhs); |
177 |
|
/** Subtract two integers in the given ring. */ |
178 |
|
Integer sub(const IntegerRing& ir, const Integer& lhs, const Integer& rhs); |
179 |
|
/** Subtract and assign two integers in the given ring. */ |
180 |
|
Integer& sub_assign(const IntegerRing& ir, Integer& lhs, const Integer& rhs); |
181 |
|
|
182 |
|
/** Negate an integer. */ |
183 |
|
Integer operator-(const Integer& i); |
184 |
|
/** Negate an integer in the given ring. */ |
185 |
|
Integer neg(const IntegerRing& ir, const Integer& i); |
186 |
|
|
187 |
|
/** Compute the absolute value. */ |
188 |
|
Integer abs(const Integer& i); |
189 |
|
/** Compute the absolute value in the given ring. */ |
190 |
|
Integer abs(const IntegerRing& ir, const Integer& i); |
191 |
|
|
192 |
|
/** Compute the inverse in the given ring. |
193 |
|
* Note that inverses do not exist in Z (except for -1 and 1). |
194 |
|
*/ |
195 |
|
Integer inverse(const IntegerRing& ir, const Integer& i); |
196 |
|
|
197 |
|
/** Multiply two integers. */ |
198 |
|
Integer operator*(const Integer& lhs, const Integer& rhs); |
199 |
|
/** Multiply two integers. */ |
200 |
|
Integer operator*(const Integer& lhs, long rhs); |
201 |
|
/** Multiply two integers. */ |
202 |
|
Integer operator*(long lhs, const Integer& rhs); |
203 |
|
/** Multiply and assign two integers. */ |
204 |
|
Integer& operator*=(Integer& lhs, const Integer& rhs); |
205 |
|
/** Multiply and assign two integers. */ |
206 |
|
Integer& operator*=(Integer& lhs, long rhs); |
207 |
|
/** Multiply two integers in the given ring. */ |
208 |
|
Integer mul(const IntegerRing& ir, const Integer& lhs, const Integer& rhs); |
209 |
|
/** Multiply two integers in the given ring. */ |
210 |
|
Integer mul(const IntegerRing& ir, const Integer& lhs, long rhs); |
211 |
|
/** Multiply two integers in the given ring. */ |
212 |
|
Integer mul(const IntegerRing& ir, long lhs, const Integer& rhs); |
213 |
|
/** Multiply and assign two integers in the given ring. */ |
214 |
|
Integer& mul_assign(const IntegerRing& ir, Integer& lhs, const Integer& rhs); |
215 |
|
/** Multiply and assign two integers in the given ring. */ |
216 |
|
Integer& mul_assign(const IntegerRing& ir, Integer& lhs, long rhs); |
217 |
|
|
218 |
|
/** Compute lhs * 2^rhs. */ |
219 |
|
Integer mul_pow2(const Integer& lhs, unsigned rhs); |
220 |
|
/** Compute lhs * 2^rhs in the given ring. */ |
221 |
|
Integer mul_pow2(const IntegerRing& ir, const Integer& lhs, unsigned rhs); |
222 |
|
|
223 |
|
/** Compute lhs^rhs. */ |
224 |
|
Integer pow(const Integer& lhs, unsigned rhs); |
225 |
|
/** Compute lhs^rhs in the given ring. */ |
226 |
|
Integer pow(const IntegerRing& ir, const Integer& lhs, unsigned rhs); |
227 |
|
|
228 |
|
/** Compute the (truncated part of the) square root. */ |
229 |
|
Integer sqrt(const Integer& i); |
230 |
|
|
231 |
|
/** Compute lhs += a * b. */ |
232 |
|
Integer& add_mul(Integer& lhs, const Integer& a, const Integer& b); |
233 |
|
/** Compute lhs += a * b in the given ring. */ |
234 |
|
Integer& add_mul(const IntegerRing& ir, Integer& lhs, const Integer& a, |
235 |
|
const Integer& b); |
236 |
|
/** Compute lhs += a * b. */ |
237 |
|
Integer& add_mul(Integer& lhs, const Integer& a, int b); |
238 |
|
/** Compute lhs += a * b in the given ring. */ |
239 |
|
Integer& add_mul(const IntegerRing& ir, Integer& lhs, const Integer& a, int b); |
240 |
|
|
241 |
|
/** Compute lhs -= a * b. */ |
242 |
|
Integer& sub_mul(Integer& lhs, const Integer& a, const Integer& b); |
243 |
|
/** Compute lhs -= a * b in the given ring. */ |
244 |
|
Integer& sub_mul(const IntegerRing& ir, Integer& lhs, const Integer& a, |
245 |
|
const Integer& b); |
246 |
|
|
247 |
|
/** Compute the (truncated part of the) quotient of two integers. */ |
248 |
|
Integer operator/(const Integer& lhs, const Integer& rhs); |
249 |
|
/** Compute and assign the (truncated part of the) quotient of two integers. |
250 |
|
*/ |
251 |
|
Integer& operator/=(Integer& lhs, const Integer& rhs); |
252 |
|
|
253 |
|
/** Compute the remainder of two integers. */ |
254 |
|
Integer operator%(const Integer& lhs, const Integer& rhs); |
255 |
|
/** Compute and assign the remainder of two integers. */ |
256 |
|
Integer& operator%=(Integer& lhs, const Integer& rhs); |
257 |
|
|
258 |
|
/** Compute the quotient of two integers, assuming that divides(lhs, rhs). */ |
259 |
|
Integer div_exact(const Integer& lhs, const Integer& rhs); |
260 |
|
/** Compute the quotient of two integers in the given ring, assuming that |
261 |
|
* divides(lhs, rhs). */ |
262 |
|
Integer div_exact(const IntegerRing& ir, const Integer& lhs, const Integer& rhs); |
263 |
|
|
264 |
|
/** Compute the quotient and remainder of two integers. */ |
265 |
|
Integer div_rem(Integer& rem, const Integer& lhs, const Integer& rhs); |
266 |
|
|
267 |
|
/** Compute the quotient and remainder of lhs and 2^rhs. */ |
268 |
|
Integer div_rem_pow2(Integer& rem, const Integer& lhs, unsigned rhs); |
269 |
|
|
270 |
|
/** Returns the integer as a long. May get truncated, but keeps the correct |
271 |
|
* sign. */ |
272 |
|
long to_int(const Integer& i); |
273 |
|
/** Returns the integer as a double. */ |
274 |
|
double to_double(const Integer& i); |
275 |
|
|
276 |
|
/** Checks whether the integer is a prime number. |
277 |
|
* If the integer is negative, checks whether abs(i) is a prime number. |
278 |
|
*/ |
279 |
|
bool is_prime(const Integer& i); |
280 |
|
/** Checks whether the integer is zero. */ |
281 |
|
bool is_zero(const Integer& i); |
282 |
|
/** Checks whether the integer is zero in the given ring. */ |
283 |
|
bool is_zero(const IntegerRing& ir, const Integer& i); |
284 |
|
/** Checks whether the integer is in the given ring. */ |
285 |
|
bool is_in_ring(const IntegerRing& ir, const Integer& i); |
286 |
|
|
287 |
|
/** Computes the hash of an integer. */ |
288 |
|
std::size_t hash(const Integer& i); |
289 |
|
|
290 |
|
/** Computes the sign of an integer. */ |
291 |
|
int sgn(const Integer& i); |
292 |
|
/** Computes the sign of an integer in the given ring. */ |
293 |
|
int sgn(const IntegerRing& ir, const Integer& i); |
294 |
|
|
295 |
|
/** Computes the greatest common divisor of two integers. */ |
296 |
|
Integer gcd(const Integer& a, const Integer& b); |
297 |
|
/** Computes the least common multiple of two integers. */ |
298 |
|
Integer lcm(const Integer& a, const Integer& b); |
299 |
|
|
300 |
|
} // namespace poly |
301 |
|
|
302 |
|
namespace std { |
303 |
|
template <> |
304 |
|
struct hash<poly::Integer> { |
305 |
|
std::size_t operator()(const poly::Integer& i) const { |
306 |
|
return poly::hash(i); |
307 |
|
} |
308 |
|
}; |
309 |
|
} // namespace std |