00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013 #ifndef __MMX_INTEGER_HPP
00014 #define __MMX_INTEGER_HPP
00015 #include <basix/basix-config.hpp>
00016 #include <numerix/mmx_gmp.hpp>
00017 #include <basix/int.hpp>
00018 namespace mmx {
00019
00020 class integer;
00021 class integer_rep;
00022 class rational;
00023 template<typename V> class floating;
00024 integer copy (const integer& i);
00025 template<typename T,typename F> struct as_helper;
00026
00027
00028
00029
00030
00031 class integer_rep REP_STRUCT {
00032 private:
00033 mpz_t x;
00034 public:
00035 inline integer_rep () { mpz_init (x); }
00036 inline integer_rep (nat sz) { mpz_init2 (x, sz); }
00037 inline ~integer_rep () { mpz_clear (x); }
00038 friend class integer;
00039 friend class rational;
00040 };
00041
00042 class integer {
00043 INDIRECT_PROTO (integer, integer_rep)
00044 public:
00045 inline const mpz_t& operator * () const { return rep->x; }
00046 inline mpz_t& operator * () { secure(); return rep->x; }
00047
00048 public:
00049
00050 inline integer (): rep (new integer_rep ()) {}
00051 inline integer (signed char i):
00052 rep (new integer_rep ()) { mpz_set_si (rep->x, i); }
00053 inline integer (unsigned char i):
00054 rep (new integer_rep ()) { mpz_set_ui (rep->x, i); }
00055 inline integer (signed int i):
00056 rep (new integer_rep ()) { mpz_set_si (rep->x, i); }
00057 inline integer (unsigned int i):
00058 rep (new integer_rep ()) { mpz_set_ui (rep->x, i); }
00059 inline integer (signed short int i):
00060 rep (new integer_rep ()) { mpz_set_si (rep->x, i); }
00061 inline integer (unsigned short int i):
00062 rep (new integer_rep ()) { mpz_set_ui (rep->x, i); }
00063 inline integer (signed long int i):
00064 rep (new integer_rep ()) { mpz_set_si (rep->x, i); }
00065 inline integer (unsigned long int i):
00066 rep (new integer_rep ()) { mpz_set_ui (rep->x, i); }
00067 #if defined(BASIX_HAVE_LONG_LONG_INT)
00068 inline integer (signed long long int i):
00069 rep (new integer_rep ()) {
00070 static const nat s = 8*sizeof(unsigned long int);
00071 bool b = false;
00072 if (i<0) { b = true; i = -i; }
00073 mpz_set_ui (rep->x, (unsigned long int)
00074 MMX_SAFE_RIGHT_SHIFT_INT (unsigned long long int,i,s));
00075 (*this) <<= s;
00076 mpz_add_ui (rep->x, rep->x, (unsigned long int) i);
00077 if (b) mpz_neg (rep->x, rep->x); }
00078 inline integer (unsigned long long int i):
00079 rep (new integer_rep ()) {
00080 static const nat s = 8*sizeof(unsigned long int);
00081 mpz_set_ui (rep->x, (unsigned long int)
00082 MMX_SAFE_RIGHT_SHIFT_INT (unsigned long long int,i,s));
00083 (*this) <<= s;
00084 mpz_add_ui (rep->x, rep->x,(unsigned long int) i); }
00085 #endif
00086 inline integer (char* s, int base= 10):
00087 rep (new integer_rep ()) { mpz_set_str (rep->x, s, base); }
00088 inline integer (const string& s, int base= 10):
00089 rep (new integer_rep ()) {
00090 char* r= as_charp (s);
00091 mpz_set_str (rep->x, r, base);
00092 free_charp (r); }
00093
00094
00095 inline friend bool is_int (const integer& x) {
00096 return mpz_fits_sint_p (*x); }
00097
00098 inline friend int as_int (const integer& x) {
00099 return (int) mpz_get_si (*x); }
00100
00101 inline friend double as_double (const integer& x) {
00102 return mpz_get_d (*x); }
00103
00104 friend string as_string (const integer& x);
00105
00106
00107 inline friend integer copy (const integer& x1) {
00108 integer r; mpz_set (*r, *x1); return r; }
00109
00110 inline friend integer operator - (const integer& x1) {
00111 integer r; mpz_neg (*r, *x1); return r; }
00112
00113 inline friend integer operator + (const integer& x1, const integer& x2) {
00114 integer r; mpz_add (*r, *x1, *x2); return r; }
00115
00116 inline friend integer operator - (const integer& x1, const integer& x2) {
00117 integer r; mpz_sub (*r, *x1, *x2); return r; }
00118
00119 inline friend integer operator * (const integer& x1, const integer& x2) {
00120 integer r; mpz_mul (*r, *x1, *x2); return r; }
00121
00122 inline friend integer square (const integer& x1) {
00123 integer r; mpz_mul (*r, *x1, *x1); return r; }
00124
00125 inline friend integer
00126 operator / (const integer& x1, const integer& x2) {
00127 ASSERT (mpz_sgn (*x2) != 0, "division by zero");
00128 #ifdef BASIX_ENABLE_VERIFY
00129 integer r; mpz_fdiv_r (*r, *x1, *x2);
00130 ASSERT (mpz_sgn (*r) == 0, "unexact division");
00131 mpz_divexact (*r, *x1, *x2); return r;
00132 #else
00133 integer r; mpz_divexact (*r, *x1, *x2); return r;
00134 #endif
00135 }
00136 inline friend integer quo (const integer& x1, const integer& x2) {
00137 if (mpz_sgn (*x2) == 0) return x2;
00138 integer r; mpz_fdiv_q (*r, *x1, *x2); return r; }
00139
00140 inline friend integer rem (const integer& x1, const integer& x2) {
00141 if (mpz_sgn (*x2) == 0) return x1;
00142 integer r; mpz_fdiv_r (*r, *x1, *x2); return r; }
00143
00144 inline friend bool divides (const integer& x1, const integer& x2) {
00145 return mpz_divisible_p (*x2, *x1); }
00146
00147 inline friend bool is_invertible (const integer& x) {
00148 return x == 1 || x == -1; }
00149
00150 inline friend integer rem (const integer& x1, const integer& x2,
00151 integer& q) {
00152 if (mpz_sgn (*x2) == 0) { q= x2; return x1; }
00153 integer r; mpz_fdiv_qr (*q, *r, *x1, *x2); return r; }
00154
00155 inline friend integer operator % (const integer& x1, const integer& x2) {
00156 return rem (x1, x2); }
00157
00158 inline friend integer& operator %= (integer& x1, const integer& x2) {
00159 x1.secure (); x1= rem (x1, x2); return x1; }
00160
00161 inline friend integer operator << (const integer& x1, int shift) {
00162 integer r; mpz_mul_2si (*r, *x1, shift); return r; }
00163
00164 inline friend integer operator >> (const integer& x1, int shift) {
00165 integer r; mpz_mul_2si (*r, *x1, -shift); return r; }
00166
00167 inline friend integer& operator += (integer& x1, const integer& x2) {
00168 x1.secure (); mpz_add (*x1, *x1, *x2); return x1; }
00169
00170 inline friend integer& operator -= (integer& x1, const integer& x2) {
00171 x1.secure (); mpz_sub (*x1, *x1, *x2); return x1; }
00172
00173 inline friend integer& operator *= (integer& x1, const integer& x2) {
00174 x1.secure (); mpz_mul (*x1, *x1, *x2); return x1; }
00175
00176 inline friend integer& operator <<= (integer& x1, int shift) {
00177 x1.secure (); mpz_mul_2si (*x1, *x1, shift); return x1; }
00178
00179 inline friend void
00180 neg (integer& r) { r.secure (); mpz_neg (*r, *r); }
00181
00182 inline friend void
00183 neg (integer& r, const integer& x) { r.secure (); mpz_neg (*r, *x); }
00184
00185 inline friend void
00186 add (integer& r, const integer& x1, const integer& x2) {
00187 r.secure (); mpz_add (*r, *x1, *x2); }
00188
00189 inline friend void
00190 sub (integer& r, const integer& x1, const integer& x2) {
00191 r.secure (); mpz_sub (*r, *x1, *x2); }
00192
00193 inline friend void
00194 mul (integer& r, const integer& x1, const integer& x2) {
00195 r.secure (); mpz_mul (*r, *x1, *x2); }
00196
00197 inline friend void
00198 mul_add (integer& r, const integer& x1, const integer& x2) {
00199 r.secure (); mpz_addmul (*r, *x1, *x2); }
00200
00201 inline friend void
00202 mul_sub (integer& r, const integer& x1, const integer& x2) {
00203 r.secure (); mpz_submul (*r, *x1, *x2); }
00204
00205
00206 inline friend bool operator == (const integer& x1, const integer& x2) {
00207 return mpz_cmp (*x1, *x2) == 0; }
00208
00209 inline friend bool operator != (const integer& x1, const integer& x2) {
00210 return mpz_cmp (*x1, *x2) != 0; }
00211
00212 inline friend bool operator < (const integer& x1, const integer& x2) {
00213 return mpz_cmp (*x1, *x2) < 0; }
00214
00215 inline friend bool operator > (const integer& x1, const integer& x2) {
00216 return mpz_cmp (*x1, *x2) > 0; }
00217
00218 inline friend bool operator <= (const integer& x1, const integer& x2) {
00219 return mpz_cmp (*x1, *x2) <= 0; }
00220
00221 inline friend bool operator >= (const integer& x1, const integer& x2) {
00222 return mpz_cmp (*x1, *x2) >= 0; }
00223
00224 inline friend int sign (const integer& x1) {
00225 int r= mpz_sgn (*x1); return (r<0? -1: (r==0? 0: 1)); }
00226
00227 inline friend integer abs (const integer& x1) {
00228 integer r; mpz_abs (*r, *x1); return r; }
00229
00230 inline friend integer min (const integer& x1, const integer& x2) {
00231 return x1 <= x2? x1: x2; }
00232
00233 inline friend integer max (const integer& x1, const integer& x2) {
00234 return x1 >= x2? x1: x2; }
00235
00236
00237 inline friend integer operator & (const integer& x1, const integer& x2) {
00238 integer r; mpz_and (*r, *x1, *x2); return r; }
00239
00240 inline friend integer operator | (const integer& x1, const integer& x2) {
00241 integer r; mpz_ior (*r, *x1, *x2); return r; }
00242
00243 inline friend integer operator ^ (const integer& x1, const integer& x2) {
00244 integer r; mpz_xor (*r, *x1, *x2); return r; }
00245
00246 inline friend integer operator ~ (const integer& x1) {
00247 integer r; mpz_com (*r, *x1); return r; }
00248
00249 inline bool operator [] (nat index) const {
00250 return (bool) mpz_tstbit (rep->x, index); }
00251
00252 inline friend nat hamming_norm (const integer& x1) {
00253 return mpz_popcount (*x1); }
00254
00255 inline friend nat hamming_distance (const integer& x1, const integer& x2) {
00256 return mpz_hamdist (*x1, *x2); }
00257
00258
00259 #define RIGHT_DOWNGRADE_INFIX(op, U, I) \
00260 inline friend integer operator op (const integer& x1, U x2) { \
00261 return x1 op (unsigned long int) x2; } \
00262 inline friend integer operator op (const integer& x1, I x2) { \
00263 return x1 op (long int) x2; } \
00264
00265 #define LEFT_DOWNGRADE_INFIX(op, U, I) \
00266 inline friend integer operator op (U x1, const integer& x2) { \
00267 return (unsigned long int) x1 op x2; } \
00268 inline friend integer operator op (I x1, const integer& x2) { \
00269 return (long int) x1 op x2; }
00270
00271 #define LEFT_DOWNGRADE_INFIX_COMMUTATIVE(op, U, I) \
00272 inline friend integer operator op (U x2, const integer& x1) { \
00273 return x1 op (unsigned long int) x2; } \
00274 inline friend integer operator op (I x2, const integer& x1) { \
00275 return x1 op (long int) x2; }
00276
00277 #define DOWNGRADE_LONG_LONG(op) \
00278 inline friend integer operator op (unsigned long long int x1, \
00279 const integer& x2) { \
00280 return integer (x1) op x2; } \
00281 inline friend integer operator op (long long int x1, \
00282 const integer& x2) { \
00283 return integer (x1) op x2; } \
00284 inline friend integer operator op (const integer& x1, \
00285 unsigned long long int x2) { \
00286 return x1 op integer (x2); } \
00287 inline friend integer operator op (const integer& x1, \
00288 long long int x2) { \
00289 return x1 op integer (x2); }
00290
00291 #define DOWNGRADE_INPLACE(op, U, I) \
00292 inline friend integer& operator op (integer& x1, U x2) { \
00293 return x1 op (unsigned long int) x2; } \
00294 inline friend integer& operator op (integer& x1, I x2) { \
00295 return x1 op (long int) x2; }
00296
00297 #define DOWNGRADE_INPLACE_LONG_LONG(op) \
00298 inline friend integer& operator op (integer& x1, \
00299 unsigned long long x2) { \
00300 return x1 op integer (x2); } \
00301 inline friend integer& operator op (integer& x1, \
00302 long long x2) { \
00303 return x1 op integer (x2); }
00304
00305 #define RIGHT_DOWNGRADE_FUN_INPLACE(fun, U, I) \
00306 inline friend void fun (integer& r, const integer& x1, U x2) { \
00307 fun (r, x1, (unsigned long int) x2); } \
00308 inline friend void fun (integer& r, const integer& x1, I x2) { \
00309 fun (r, x1, (long int) x2); }
00310
00311 #define LEFT_DOWNGRADE_FUN_INPLACE(fun, U, I) \
00312 inline friend void fun (integer& r, U x1, const integer& x2) { \
00313 fun (r, (unsigned long int) x1, x2); } \
00314 inline friend void fun (integer& r, I x1, const integer& x2) { \
00315 fun (r, (long int) x1, x2); }
00316
00317 #define LEFT_DOWNGRADE_FUN_INPLACE_COMMUTATIVE(fun, U, I) \
00318 inline friend void fun (integer& r, U x1, const integer& x2) { \
00319 fun (r, x2, (unsigned long int) x1); } \
00320 inline friend void fun (integer& r, I x1, const integer& x2) { \
00321 fun (r, x2, (long int) x1); }
00322
00323 #define DOWNGRADE_FUN_INPLACE_LONG_LONG(fun) \
00324 inline friend void fun (integer& r, unsigned long long int x1, \
00325 const integer& x2) { \
00326 fun (r, integer (x1), x2); } \
00327 inline friend void fun (integer& r, long long int x1, \
00328 const integer& x2) { \
00329 fun (r, integer (x1), x2); } \
00330 inline friend void fun (integer& r, const integer& x1, \
00331 unsigned long long int x2) { \
00332 fun (r, x1, integer (x2)); } \
00333 inline friend void fun (integer& r, const integer& x2, \
00334 long long int x1) { \
00335 fun (r, x1, integer (x2)); }
00336
00337 #define RIGHT_DOWNGRADE_FUN(fun, U, I) \
00338 inline friend integer fun (const integer& x1, U x2) { \
00339 return fun (x1, (unsigned long int) x2); } \
00340 inline friend integer fun (const integer& x1, I x2) { \
00341 return fun (x1, (long int) x2); }
00342
00343 #define RIGHT_DOWNGRADE_FUN_X(fun, U, I, X) \
00344 inline friend integer fun (const integer& x1, U x2, X x) { \
00345 return fun (x1, (unsigned long int) x2, x); } \
00346 inline friend integer fun (const integer& x1, I x2, X x) { \
00347 return fun (x1, (long int) x2, x); }
00348
00349 #define LEFT_DOWNGRADE_FUN(fun, U, I) \
00350 inline friend integer fun (U x1, const integer& x2) { \
00351 return fun ((unsigned long int) x1, x2); } \
00352 inline friend integer fun (I x1, const integer& x2) { \
00353 return fun ((long int) x1, x2); }
00354
00355 #define LEFT_DOWNGRADE_FUN_X(fun, U, I, X) \
00356 inline friend integer fun (U x1, const integer& x2, X x) { \
00357 return fun ((unsigned long int) x1, x2, x); } \
00358 inline friend integer fun (I x1, const integer& x2, X x) { \
00359 return fun ((long int) x1, x2, x); }
00360
00361 #define DOWNGRADE_FUN_LONG_LONG(fun) \
00362 inline friend integer fun (unsigned long long int x1, \
00363 const integer& x2) { \
00364 return fun (integer (x1), x2); } \
00365 inline friend integer fun (long long int x1, \
00366 const integer& x2) { \
00367 return fun (integer (x1), x2); } \
00368 inline friend integer fun (const integer& x1, \
00369 unsigned long long int x2) { \
00370 return fun (x1, integer (x2)); } \
00371 inline friend integer fun (const integer& x1, \
00372 long long int x2) { \
00373 return fun (x1, integer (x2)); }
00374
00375 #define DOWNGRADE_FUN_X_LONG_LONG(fun, X) \
00376 inline friend integer fun (unsigned long long int x1, \
00377 const integer& x2, X x) { \
00378 return fun (integer (x1), x2, x); } \
00379 inline friend integer fun (long long int x1, \
00380 const integer& x2, X x) { \
00381 return fun (integer (x1), x2, x); } \
00382 inline friend integer fun (const integer& x1, \
00383 unsigned long long int x2, X x) { \
00384 return fun (x1, integer (x2), x); } \
00385 inline friend integer fun (const integer& x1, \
00386 long long int x2, X x) { \
00387 return fun (x1, integer (x2), x); }
00388
00389 #define RIGHT_DOWNGRADE_TEST(op, U, I) \
00390 inline friend bool operator op (const integer& x1, U x2) { \
00391 return x1 op (unsigned long int) x2; } \
00392 inline friend bool operator op (const integer& x1, I x2) { \
00393 return x1 op (long int) x2; } \
00394
00395 #define LEFT_DOWNGRADE_TEST(op, U, I) \
00396 inline friend bool operator op (U x1, const integer& x2) { \
00397 return (unsigned long int) x1 op x2; } \
00398 inline friend bool operator op (I x1, const integer& x2) { \
00399 return (long int) x1 op x2; }
00400
00401 #define DOWNGRADE_TEST_LONG_LONG(op) \
00402 inline friend bool operator op (const integer& x1, \
00403 unsigned long long int x2) { \
00404 return x1 op integer (x2); } \
00405 inline friend bool operator op (const integer& x1, \
00406 long long int x2) { \
00407 return x1 op integer (x2); } \
00408 inline friend bool operator op (unsigned long long int x1, \
00409 const integer& x2) { \
00410 return integer (x1) op x2; } \
00411 inline friend bool operator op (long long int x1, \
00412 const integer& x2) { \
00413 return integer (x1) op x2; }
00414
00415 inline friend integer operator + (const integer& x1,
00416 const unsigned long int& x2) {
00417 integer r; mpz_add_ui (*r, *x1, x2); return r; }
00418 inline friend integer operator + (const integer& x1,
00419 const long int& x2) {
00420 integer r;
00421 if (x2 < 0) mpz_sub_ui (*r, *x1, (unsigned long int) (-x2));
00422 else mpz_add_ui (*r, *x1, (unsigned long int) x2);
00423 return r; }
00424 RIGHT_DOWNGRADE_INFIX (+, unsigned int, int)
00425 RIGHT_DOWNGRADE_INFIX (+, unsigned short int, short int)
00426 RIGHT_DOWNGRADE_INFIX (+, unsigned char, char)
00427 LEFT_DOWNGRADE_INFIX_COMMUTATIVE (+, long unsigned int, long int)
00428 LEFT_DOWNGRADE_INFIX_COMMUTATIVE (+, unsigned int, int)
00429 LEFT_DOWNGRADE_INFIX_COMMUTATIVE (+, unsigned short int, short int)
00430 LEFT_DOWNGRADE_INFIX_COMMUTATIVE (+, unsigned char, char)
00431 #if defined (BASIX_HAVE_LONG_LONG_INT)
00432 DOWNGRADE_LONG_LONG (+)
00433 #endif
00434
00435 inline friend integer operator - (const integer& x1,
00436 unsigned long int x2) {
00437 integer r; mpz_sub_ui (*r, *x1, x2); return r; }
00438 inline friend integer operator - (const integer& x1,
00439 long int x2) {
00440 integer r;
00441 if (x2 < 0) mpz_add_ui (*r, *x1, (unsigned long int) (-x2));
00442 else mpz_sub_ui (*r, *x1, (unsigned long int) x2);
00443 return r; }
00444 RIGHT_DOWNGRADE_INFIX (-, unsigned int, int)
00445 RIGHT_DOWNGRADE_INFIX (-, unsigned short int, short int)
00446 RIGHT_DOWNGRADE_INFIX (-, unsigned char, char)
00447
00448 inline friend integer operator - (unsigned long int x1,
00449 const integer& x2) {
00450 integer r; mpz_ui_sub (*r, x1, *x2); return r; }
00451 inline friend integer operator - (long int x1,
00452 const integer& x2) {
00453 integer r;
00454 if (x1 < 0) { mpz_add_ui (*r, *x2, (unsigned long int) (-x1));
00455 neg (r); }
00456 else mpz_ui_sub (*r, (unsigned long int) x1, *x2);
00457 return r; }
00458 LEFT_DOWNGRADE_INFIX (-, unsigned int, int)
00459 LEFT_DOWNGRADE_INFIX (-, unsigned short int, short int)
00460 LEFT_DOWNGRADE_INFIX (-, unsigned char, char)
00461 #if defined(BASIX_HAVE_LONG_LONG_INT)
00462 DOWNGRADE_LONG_LONG (-)
00463 #endif
00464
00465 inline friend integer operator * (const integer& x1,
00466 const unsigned long int& x2) {
00467 integer r; mpz_mul_ui (*r, *x1, x2); return r; }
00468 inline friend integer operator * (const integer& x1,
00469 const long int& x2) {
00470 integer r; mpz_mul_si (*r, *x1, x2); return r; }
00471 RIGHT_DOWNGRADE_INFIX (*, unsigned int, int)
00472 RIGHT_DOWNGRADE_INFIX (*, unsigned short int, short int)
00473 RIGHT_DOWNGRADE_INFIX (*, unsigned char, char)
00474 LEFT_DOWNGRADE_INFIX_COMMUTATIVE (*, long unsigned int, long int)
00475 LEFT_DOWNGRADE_INFIX_COMMUTATIVE (*, unsigned int, int)
00476 LEFT_DOWNGRADE_INFIX_COMMUTATIVE (*, unsigned short int, short int)
00477 LEFT_DOWNGRADE_INFIX_COMMUTATIVE (*, unsigned char, char)
00478 #if defined(BASIX_HAVE_LONG_LONG_INT)
00479 DOWNGRADE_LONG_LONG (*)
00480 #endif
00481
00482 inline friend integer operator / (const integer& x1,
00483 unsigned long int x2) {
00484 ASSERT (x2 != 0, "division by zero");
00485 integer r; mpz_divexact_ui (*r, *x1, x2); return r; }
00486 inline friend integer operator / (const integer& x1,
00487 long int x2) {
00488 ASSERT (x2 != 0, "division by zero");
00489 integer r;
00490 if (x2 < 0) { mpz_divexact_ui (*r, *x1, (unsigned long int) (-x2));
00491 neg (r); }
00492 else mpz_divexact_ui (*r, *x1, (unsigned long int) x2);
00493 return r; }
00494 RIGHT_DOWNGRADE_INFIX (/, unsigned int, int)
00495 RIGHT_DOWNGRADE_INFIX (/, unsigned short int, short int)
00496 RIGHT_DOWNGRADE_INFIX (/, unsigned char, char)
00497
00498 inline friend integer operator / (unsigned long int x1,
00499 const integer& x2) {
00500 return integer (x1) / x2; }
00501 inline friend integer operator / (long int x1,
00502 const integer& x2) {
00503 return integer (x1) / x2; }
00504 LEFT_DOWNGRADE_INFIX (/, unsigned int, int)
00505 LEFT_DOWNGRADE_INFIX (/, unsigned short int, short int)
00506 LEFT_DOWNGRADE_INFIX (/, unsigned char, char)
00507 #if defined(BASIX_HAVE_LONG_LONG_INT)
00508 DOWNGRADE_LONG_LONG (/)
00509 #endif
00510
00511 inline friend integer& operator += (integer& x1, unsigned long int x2) {
00512 x1.secure (); mpz_add_ui (*x1, *x1, x2); return x1; }
00513 inline friend integer& operator += (integer& x1, long int x2) {
00514 x1.secure ();
00515 if (x2 < 0) mpz_sub_ui (*x1, *x1, (unsigned long int) (-x2));
00516 else mpz_add_ui (*x1, *x1, (unsigned long int) x2);
00517 return x1; }
00518 DOWNGRADE_INPLACE (+=, unsigned int, int)
00519 DOWNGRADE_INPLACE (+=, unsigned short int, short int)
00520 DOWNGRADE_INPLACE (+=, unsigned char, signed char)
00521 #if defined(BASIX_HAVE_LONG_LONG_INT)
00522 DOWNGRADE_INPLACE_LONG_LONG (+=)
00523 #endif
00524
00525 inline friend integer& operator -= (integer& x1, unsigned long int x2) {
00526 x1.secure (); mpz_sub_ui (*x1, *x1, x2); return x1; }
00527 inline friend integer& operator -= (integer& x1, long int x2) {
00528 x1.secure ();
00529 if (x2 < 0) mpz_add_ui (*x1, *x1, (unsigned long int) (-x2));
00530 else mpz_sub_ui (*x1, *x1, (unsigned long int) x2);
00531 return x1; }
00532 DOWNGRADE_INPLACE (-=, unsigned int, int)
00533 DOWNGRADE_INPLACE (-=, unsigned short int, short int)
00534 DOWNGRADE_INPLACE (-=, unsigned char, signed char)
00535 #if defined(BASIX_HAVE_LONG_LONG_INT)
00536 DOWNGRADE_INPLACE_LONG_LONG (-=)
00537 #endif
00538
00539 inline friend integer& operator *= (integer& x1, unsigned long int x2) {
00540 x1.secure (); mpz_mul_ui (*x1, *x1, x2); return x1; }
00541 inline friend integer& operator *= (integer& x1, long int x2) {
00542 x1.secure (); mpz_mul_si (*x1, *x1, x2); return x1; }
00543 DOWNGRADE_INPLACE (*=, unsigned int, int)
00544 DOWNGRADE_INPLACE (*=, unsigned short int, short int)
00545 DOWNGRADE_INPLACE (*=, unsigned char, signed char)
00546 #if defined(BASIX_HAVE_LONG_LONG_INT)
00547 DOWNGRADE_INPLACE_LONG_LONG (*=)
00548 #endif
00549 #if defined(BASIX_HAVE_LONG_LONG_INT)
00550 inline friend void neg (integer& r, unsigned long long int x1) {
00551 neg (r, integer (x1)); }
00552 inline friend void neg (integer& r, long long int x1) {
00553 neg (r, integer (x1)); }
00554 #endif
00555 inline friend void neg (integer& r, unsigned long int x1) {
00556 r.secure (); mpz_set_ui (*r, x1); neg (r); }
00557 inline friend void neg (integer& r, long int x1) {
00558 r.secure (); mpz_set_si (*r, -x1); }
00559 inline friend void neg (integer& r, unsigned int x1) {
00560 r.secure (); mpz_set_ui (*r, x1); neg (r); }
00561 inline friend void neg (integer& r, int x1) {
00562 r.secure (); mpz_set_si (*r, -x1); }
00563 inline friend void neg (integer& r, unsigned short int x1) {
00564 r.secure (); mpz_set_ui (*r, x1); neg (r); }
00565 inline friend void neg (integer& r, short int x1) {
00566 r.secure (); mpz_set_si (*r, -x1); }
00567 inline friend void neg (integer& r, unsigned char x1) {
00568 r.secure (); mpz_set_ui (*r, x1); neg (r); }
00569 inline friend void neg (integer& r, signed char x1) {
00570 r.secure (); mpz_set_si (*r, -x1); }
00571
00572 inline friend void
00573 add (integer& r, const integer& x1, unsigned long int x2) {
00574 r.secure (); mpz_add_ui (*r, *x1, x2); }
00575 inline friend void
00576 add (integer& r, const integer& x1, long int x2) {
00577 r.secure ();
00578 if (x2 < 0) mpz_sub_ui (*r, *x1, (unsigned long int) (-x2));
00579 else mpz_add_ui (*r, *x1, (unsigned long int) x2); }
00580 RIGHT_DOWNGRADE_FUN_INPLACE (add, unsigned int, int)
00581 RIGHT_DOWNGRADE_FUN_INPLACE (add, unsigned short int, short int)
00582 RIGHT_DOWNGRADE_FUN_INPLACE (add, unsigned char, signed char)
00583 LEFT_DOWNGRADE_FUN_INPLACE_COMMUTATIVE (add, unsigned long int, long int)
00584 LEFT_DOWNGRADE_FUN_INPLACE_COMMUTATIVE (add, unsigned int, int)
00585 LEFT_DOWNGRADE_FUN_INPLACE_COMMUTATIVE (add, unsigned short int, short int)
00586 LEFT_DOWNGRADE_FUN_INPLACE_COMMUTATIVE (add, unsigned char, signed char)
00587 #if defined(BASIX_HAVE_LONG_LONG_INT)
00588 DOWNGRADE_FUN_INPLACE_LONG_LONG (add)
00589 #endif
00590
00591 inline friend void
00592 sub (integer& r, const integer& x1, unsigned long int x2) {
00593 r.secure (); mpz_sub_ui (*r, *x1, x2); }
00594 inline friend void
00595 sub (integer& r, const integer& x1, long int x2) {
00596 r.secure ();
00597 if (x2 < 0) mpz_add_ui (*r, *x1, (unsigned long int) (-x2));
00598 else mpz_sub_ui (*r, *x1, (unsigned long int) x2); }
00599 RIGHT_DOWNGRADE_FUN_INPLACE (sub, unsigned int, int)
00600 RIGHT_DOWNGRADE_FUN_INPLACE (sub, unsigned short int, short int)
00601 RIGHT_DOWNGRADE_FUN_INPLACE (sub, unsigned char, signed char)
00602
00603 inline friend void
00604 sub (integer& r, unsigned long int x1, const integer& x2) {
00605 r.secure (); mpz_ui_sub (*r, x1, *x2); }
00606 inline friend void
00607 sub (integer& r, long int x1, const integer& x2) {
00608 r.secure ();
00609 if (x1 < 0) { mpz_add_ui (*r, *x2, (unsigned long int) (-x1));
00610 neg (r); }
00611 else mpz_ui_sub (*r, (unsigned long int) x1, *x2); }
00612 LEFT_DOWNGRADE_FUN_INPLACE (sub, unsigned int, int)
00613 LEFT_DOWNGRADE_FUN_INPLACE (sub, unsigned short int, short int)
00614 LEFT_DOWNGRADE_FUN_INPLACE (sub, unsigned char, signed char)
00615 #if defined(BASIX_HAVE_LONG_LONG_INT)
00616 DOWNGRADE_FUN_INPLACE_LONG_LONG (sub)
00617 #endif
00618
00619 inline friend void
00620 mul (integer& r, const integer& x1, unsigned long int x2) {
00621 r.secure (); mpz_mul_ui (*r, *x1, x2); }
00622 inline friend void
00623 mul (integer& r, const integer& x1, long int x2) {
00624 r.secure (); mpz_mul_si (*r, *x1, x2); }
00625 RIGHT_DOWNGRADE_FUN_INPLACE (mul, unsigned int, int)
00626 RIGHT_DOWNGRADE_FUN_INPLACE (mul, unsigned short int, short int)
00627 RIGHT_DOWNGRADE_FUN_INPLACE (mul, unsigned char, signed char)
00628 LEFT_DOWNGRADE_FUN_INPLACE_COMMUTATIVE (mul, unsigned long int, long int)
00629 LEFT_DOWNGRADE_FUN_INPLACE_COMMUTATIVE (mul, unsigned int, int)
00630 LEFT_DOWNGRADE_FUN_INPLACE_COMMUTATIVE (mul, unsigned short int, short int)
00631 LEFT_DOWNGRADE_FUN_INPLACE_COMMUTATIVE (mul, unsigned char, signed char)
00632 #if defined(BASIX_HAVE_LONG_LONG_INT)
00633 DOWNGRADE_FUN_INPLACE_LONG_LONG (mul)
00634 #endif
00635
00636 inline friend void
00637 mul_add (integer& r, const integer& x1, unsigned long int x2) {
00638 r.secure (); mpz_addmul_ui (*r, *x1, x2); }
00639 inline friend void
00640 mul_add (integer& r, const integer& x1, long int x2) {
00641 r.secure ();
00642 if (x2 < 0) mpz_submul_ui (*r, *x1, (unsigned long int) (-x2));
00643 else mpz_addmul_ui (*r, *x1, (unsigned long int) x2);}
00644 RIGHT_DOWNGRADE_FUN_INPLACE (mul_add, unsigned int, int)
00645 RIGHT_DOWNGRADE_FUN_INPLACE (mul_add, unsigned short int, short int)
00646 RIGHT_DOWNGRADE_FUN_INPLACE (mul_add, unsigned char, signed char)
00647 LEFT_DOWNGRADE_FUN_INPLACE_COMMUTATIVE (mul_add, unsigned long int, long int)
00648 LEFT_DOWNGRADE_FUN_INPLACE_COMMUTATIVE (mul_add, unsigned int, int)
00649 LEFT_DOWNGRADE_FUN_INPLACE_COMMUTATIVE (mul_add, unsigned short, short int)
00650 LEFT_DOWNGRADE_FUN_INPLACE_COMMUTATIVE (mul_add, unsigned char, signed char)
00651 #if defined(BASIX_HAVE_LONG_LONG_INT)
00652 DOWNGRADE_FUN_INPLACE_LONG_LONG (mul_add)
00653 #endif
00654
00655 inline friend void
00656 mul_sub (integer& r, const integer& x1, unsigned long int x2) {
00657 r.secure (); mpz_submul_ui (*r, *x1, x2); }
00658 inline friend void
00659 mul_sub (integer& r, const integer& x1, long int x2) {
00660 r.secure ();
00661 if (x2 < 0) mpz_addmul_ui (*r, *x1, (unsigned long int) (-x2));
00662 else mpz_submul_ui (*r, *x1, (unsigned long int) x2); }
00663 RIGHT_DOWNGRADE_FUN_INPLACE (mul_sub, unsigned int, int)
00664 RIGHT_DOWNGRADE_FUN_INPLACE (mul_sub, unsigned short int, short int)
00665 RIGHT_DOWNGRADE_FUN_INPLACE (mul_sub, unsigned char, signed char)
00666 LEFT_DOWNGRADE_FUN_INPLACE_COMMUTATIVE (mul_sub, unsigned long int, long int)
00667 LEFT_DOWNGRADE_FUN_INPLACE_COMMUTATIVE (mul_sub, unsigned int, int)
00668 LEFT_DOWNGRADE_FUN_INPLACE_COMMUTATIVE (mul_sub, unsigned short, short int)
00669 LEFT_DOWNGRADE_FUN_INPLACE_COMMUTATIVE (mul_sub, unsigned char, signed char)
00670 #if defined(BASIX_HAVE_LONG_LONG_INT)
00671 DOWNGRADE_FUN_INPLACE_LONG_LONG (mul_sub)
00672 #endif
00673
00674 inline friend integer quo (const integer& x1,
00675 unsigned long int x2) {
00676 if (x2 == 0) return x2;
00677 integer r; mpz_fdiv_q_ui (*r, *x1, x2); return r; }
00678 inline friend integer quo (const integer& x1,
00679 const long int& x2) {
00680 return (x2 < 0) ? - quo (x1, (unsigned long int) (-x2)) :
00681 quo (x1, (unsigned long int) x2); }
00682 RIGHT_DOWNGRADE_FUN (quo, unsigned int, int)
00683 RIGHT_DOWNGRADE_FUN (quo, unsigned short int, short int)
00684 RIGHT_DOWNGRADE_FUN (quo, unsigned char, signed char)
00685
00686 inline friend integer quo (unsigned long int x1,
00687 const integer& x2) {
00688 return quo (integer (x1), x2); }
00689 inline friend integer quo (long int x1,
00690 const integer& x2) {
00691 return quo (integer (x1), x2); }
00692 LEFT_DOWNGRADE_FUN (quo, unsigned int, int)
00693 LEFT_DOWNGRADE_FUN (quo, unsigned short int, short int)
00694 LEFT_DOWNGRADE_FUN (quo, unsigned char, signed char)
00695 #if defined(BASIX_HAVE_LONG_LONG_INT)
00696 DOWNGRADE_FUN_LONG_LONG (quo)
00697 #endif
00698
00699 inline friend integer rem (const integer& x1, unsigned long int x2) {
00700 if (x2 == 0) return x1;
00701 integer r; mpz_fdiv_r_ui (*r, *x1, x2); return r; }
00702 inline friend integer rem (const integer& x1, long int x2) {
00703 return rem (x1, (unsigned long int) abs (x2)); }
00704 RIGHT_DOWNGRADE_FUN (rem, unsigned int, int)
00705 RIGHT_DOWNGRADE_FUN (rem, unsigned short int, short int)
00706 RIGHT_DOWNGRADE_FUN (rem, unsigned char, signed char)
00707
00708 inline friend integer rem (unsigned long int x1,
00709 const integer& x2) {
00710 return rem (integer (x1), x2); }
00711 inline friend integer rem (long int x1,
00712 const integer& x2) {
00713 return rem (integer (x1), x2); }
00714 LEFT_DOWNGRADE_FUN (rem, unsigned int, int)
00715 LEFT_DOWNGRADE_FUN (rem, unsigned short int, short int)
00716 LEFT_DOWNGRADE_FUN (rem, unsigned char, signed char)
00717 #if defined(BASIX_HAVE_LONG_LONG_INT)
00718 DOWNGRADE_FUN_LONG_LONG (rem)
00719 #endif
00720
00721 inline friend integer rem (const integer& x1, unsigned long int x2,
00722 integer& q) {
00723 if (x2 == 0) { q= x2; return x1; }
00724 integer r; mpz_fdiv_qr_ui (*q, *r, *x1, x2); return r; }
00725 inline friend integer rem (const integer& x1, long int x2,
00726 integer& q) {
00727 integer r= rem (x1, (unsigned long int) abs (x2), q);
00728 if (x2 < 0) neg (q); return r; }
00729 RIGHT_DOWNGRADE_FUN_X (rem, unsigned int, int, integer&)
00730 RIGHT_DOWNGRADE_FUN_X (rem, unsigned short int, short int, integer&)
00731 RIGHT_DOWNGRADE_FUN_X (rem, unsigned char, signed char, integer&)
00732
00733 inline friend integer rem (unsigned long int x1, const integer& x2,
00734 integer& q) {
00735 return rem (integer (x1), x2, q); }
00736 inline friend integer rem (long int x1, const integer& x2,
00737 integer& q) {
00738 return rem (integer (x1), x2, q); }
00739 LEFT_DOWNGRADE_FUN_X (rem, unsigned int, int, integer&)
00740 LEFT_DOWNGRADE_FUN_X (rem, unsigned short int, short int, integer&)
00741 LEFT_DOWNGRADE_FUN_X (rem, unsigned char, signed char, integer&)
00742 #if defined(BASIX_HAVE_LONG_LONG_INT)
00743 DOWNGRADE_FUN_X_LONG_LONG (rem, integer&)
00744 #endif
00745
00746 inline friend integer operator % (const integer& x1,
00747 unsigned long int x2) {
00748 return rem (x1, x2); }
00749 inline friend integer operator % (const integer& x1,
00750 long int x2) {
00751 return rem (x1, x2); }
00752 RIGHT_DOWNGRADE_INFIX (%, unsigned int, int);
00753 RIGHT_DOWNGRADE_INFIX (%, unsigned short int, short int);
00754 RIGHT_DOWNGRADE_INFIX (%, unsigned char, signed char);
00755
00756 inline friend integer operator % (unsigned long int x1,
00757 const integer& x2) {
00758 return rem (x1, x2); }
00759 inline friend integer operator % (long int x1,
00760 const integer& x2) {
00761 return rem (x1, x2); }
00762 LEFT_DOWNGRADE_INFIX (%, unsigned int, int);
00763 LEFT_DOWNGRADE_INFIX (%, unsigned short int, short int);
00764 LEFT_DOWNGRADE_INFIX (%, unsigned char, signed char);
00765 #if defined(BASIX_HAVE_LONG_LONG_INT)
00766 DOWNGRADE_LONG_LONG (%)
00767 #endif
00768
00769 inline friend bool operator == (const integer& x1, unsigned long int x2) {
00770 return mpz_cmp_ui (*x1, x2) == 0; }
00771 inline friend bool operator == (const integer& x1, long int x2) {
00772 return mpz_cmp_si (*x1, x2) == 0; }
00773 RIGHT_DOWNGRADE_TEST (==, unsigned int, int);
00774 RIGHT_DOWNGRADE_TEST (==, unsigned short int, short int);
00775 RIGHT_DOWNGRADE_TEST (==, unsigned char, signed char);
00776
00777 inline friend bool operator == (unsigned long int x1, const integer& x2) {
00778 return mpz_cmp_ui (*x2, x1) == 0; }
00779 inline friend bool operator == (long int x1, const integer& x2) {
00780 return mpz_cmp_si (*x2, x1) == 0; }
00781 LEFT_DOWNGRADE_TEST (==, unsigned int, int);
00782 LEFT_DOWNGRADE_TEST (==, unsigned short int, short int);
00783 LEFT_DOWNGRADE_TEST (==, unsigned char, signed char);
00784 #if defined(BASIX_HAVE_LONG_LONG_INT)
00785 DOWNGRADE_TEST_LONG_LONG (==)
00786 #endif
00787
00788 inline friend bool operator != (const integer& x1, unsigned long int x2) {
00789 return mpz_cmp_ui (*x1, x2) != 0; }
00790 inline friend bool operator != (const integer& x1, long int x2) {
00791 return mpz_cmp_si (*x1, x2) != 0; }
00792 RIGHT_DOWNGRADE_TEST (!=, unsigned int, int);
00793 RIGHT_DOWNGRADE_TEST (!=, unsigned short int, short int);
00794 RIGHT_DOWNGRADE_TEST (!=, unsigned char, signed char);
00795
00796 inline friend bool operator != (unsigned long int x1, const integer& x2) {
00797 return mpz_cmp_ui (*x2, x1) != 0; }
00798 inline friend bool operator != (long int x1, const integer& x2) {
00799 return mpz_cmp_si (*x2, x1) != 0; }
00800 LEFT_DOWNGRADE_TEST (!=, unsigned int, int);
00801 LEFT_DOWNGRADE_TEST (!=, unsigned short int, short int);
00802 LEFT_DOWNGRADE_TEST (!=, unsigned char, signed char);
00803 #if defined(BASIX_HAVE_LONG_LONG_INT)
00804 DOWNGRADE_TEST_LONG_LONG (!=)
00805 #endif
00806
00807 inline friend bool operator < (const integer& x1, unsigned long int x2) {
00808 return mpz_cmp_ui (*x1, x2) < 0; }
00809 inline friend bool operator < (const integer& x1, long int x2) {
00810 return mpz_cmp_si (*x1, x2) < 0; }
00811 RIGHT_DOWNGRADE_TEST (<, unsigned int, int);
00812 RIGHT_DOWNGRADE_TEST (<, unsigned short int, short int);
00813 RIGHT_DOWNGRADE_TEST (<, unsigned char, signed char);
00814
00815 inline friend bool operator < (unsigned long int x1, const integer& x2) {
00816 return mpz_cmp_ui (*x2, x1) > 0; }
00817 inline friend bool operator < (long int x1, const integer& x2) {
00818 return mpz_cmp_si (*x2, x1) > 0; }
00819 LEFT_DOWNGRADE_TEST (<, unsigned int, int);
00820 LEFT_DOWNGRADE_TEST (<, unsigned short int, short int);
00821 LEFT_DOWNGRADE_TEST (<, unsigned char, signed char);
00822 #if defined(BASIX_HAVE_LONG_LONG_INT)
00823 DOWNGRADE_TEST_LONG_LONG (<)
00824 #endif
00825
00826 inline friend bool operator > (const integer& x1, unsigned long int x2) {
00827 return mpz_cmp_ui (*x1, x2) > 0; }
00828 inline friend bool operator > (const integer& x1, long int x2) {
00829 return mpz_cmp_si (*x1, x2) > 0; }
00830 RIGHT_DOWNGRADE_TEST (>, unsigned int, int);
00831 RIGHT_DOWNGRADE_TEST (>, unsigned short int, short int);
00832 RIGHT_DOWNGRADE_TEST (>, unsigned char, signed char);
00833
00834 inline friend bool operator > (unsigned long int x1, const integer& x2) {
00835 return mpz_cmp_ui (*x2, x1) < 0; }
00836 inline friend bool operator > (long int x1, const integer& x2) {
00837 return mpz_cmp_si (*x2, x1) < 0; }
00838 LEFT_DOWNGRADE_TEST (>, unsigned int, int);
00839 LEFT_DOWNGRADE_TEST (>, unsigned short int, short int);
00840 LEFT_DOWNGRADE_TEST (>, unsigned char, signed char);
00841 #if defined(BASIX_HAVE_LONG_LONG_INT)
00842 DOWNGRADE_TEST_LONG_LONG (>)
00843 #endif
00844
00845 inline friend bool operator <= (const integer& x1, unsigned long int x2) {
00846 return mpz_cmp_ui (*x1, x2) <= 0; }
00847 inline friend bool operator <= (const integer& x1, long int x2) {
00848 return mpz_cmp_si (*x1, x2) <= 0; }
00849 RIGHT_DOWNGRADE_TEST (<=, unsigned int, int);
00850 RIGHT_DOWNGRADE_TEST (<=, unsigned short int, short int);
00851 RIGHT_DOWNGRADE_TEST (<=, unsigned char, signed char);
00852
00853 inline friend bool operator <= (unsigned long int x1, const integer& x2) {
00854 return mpz_cmp_ui (*x2, x1) >= 0; }
00855 inline friend bool operator <= (long int x1, const integer& x2) {
00856 return mpz_cmp_si (*x2, x1) >= 0; }
00857 LEFT_DOWNGRADE_TEST (<=, unsigned int, int);
00858 LEFT_DOWNGRADE_TEST (<=, unsigned short int, short int);
00859 LEFT_DOWNGRADE_TEST (<=, unsigned char, signed char);
00860 #if defined(BASIX_HAVE_LONG_LONG_INT)
00861 DOWNGRADE_TEST_LONG_LONG (<=)
00862 #endif
00863
00864 inline friend bool operator >= (const integer& x1, unsigned long int x2) {
00865 return mpz_cmp_ui (*x1, x2) >= 0; }
00866 inline friend bool operator >= (const integer& x1, long int x2) {
00867 return mpz_cmp_si (*x1, x2) >= 0; }
00868 RIGHT_DOWNGRADE_TEST (>=, unsigned int, int);
00869 RIGHT_DOWNGRADE_TEST (>=, unsigned short int, short int);
00870 RIGHT_DOWNGRADE_TEST (>=, unsigned char, signed char);
00871
00872 inline friend bool operator >= (unsigned long int x1, const integer& x2) {
00873 return mpz_cmp_ui (*x2, x1) <= 0; }
00874 inline friend bool operator >= (long int x1, const integer& x2) {
00875 return mpz_cmp_si (*x2, x1) <= 0; }
00876 LEFT_DOWNGRADE_TEST (>=, unsigned int, int);
00877 LEFT_DOWNGRADE_TEST (>=, unsigned short int, short int);
00878 LEFT_DOWNGRADE_TEST (>=, unsigned char, signed char);
00879 #if defined(BASIX_HAVE_LONG_LONG_INT)
00880 DOWNGRADE_TEST_LONG_LONG (>=)
00881 #endif
00882
00883 #undef RIGHT_DOWNGRADE_INFIX
00884 #undef LEFT_DOWNGRADE_INFIX
00885 #undef LEFT_DOWNGRADE_INFIX_COMMUTATIVE
00886 #undef LEFT_DOWNGRADE_INFIX
00887 #undef DOWNGRADE_INPLACE
00888 #undef DOWNGRADE_LONG_LONG
00889 #undef DOWNGRADE_INPLACE_LONG_LONG
00890 #undef RIGHT_DOWNGRADE_FUN_INPLACE
00891 #undef LEFT_DOWNGRADE_FUN_INPLACE
00892 #undef LEFT_DOWNGRADE_FUN_INPLACE_COMMUTATIVE
00893 #undef DOWNGRADE_FUN_INPLACE_LONG_LONG
00894 #undef RIGHT_DOWNGRADE_FUN
00895 #undef RIGHT_DOWNGRADE_FUN_X
00896 #undef LEFT_DOWNGRADE_FUN
00897 #undef LEFT_DOWNGRADE_FUN_X
00898 #undef DOWNGRADE_FUN_LONG_LONG
00899 #undef RIGHT_DOWNGRADE_TEST
00900 #undef DOWNGRADE_FUN_X_LONG_LONG
00901 #undef RIGHT_DOWNGRADE_TEST
00902 #undef LEFT_DOWNGRADE_TEST
00903 #undef DOWNGRADE_TEST_LONG_LONG
00904
00905
00906 inline friend bool is_square (const integer& a) {
00907 return mpz_perfect_square_p (*a); }
00908
00909 inline friend integer sqrt (const integer& a) {
00910 VERIFY (is_square (a), "not a perfect square");
00911 integer r; mpz_sqrt (*r, *a); return r; }
00912
00913 inline friend integer floor_sqrt (const integer& a) {
00914 ASSERT (a >= 0, "wrong sign");
00915 integer r; mpz_sqrt (*r, *a); return r; }
00916
00917 inline friend integer pow (const integer& x1, const int& i) {
00918 ASSERT (i >= 0, "positive int expected");
00919 integer r; mpz_pow_ui (*r, *x1, (nat) i); return r; }
00920
00921 inline friend integer pow (const integer& x1, const nat& i) {
00922 integer r; mpz_pow_ui (*r, *x1, i); return r; }
00923
00924 inline friend integer pow (const integer& x1, const integer& i) {
00925 ASSERT (i >= 0, "positive int expected");
00926 if (i == 0) return 1;
00927 if (x1 == 0) return 0;
00928 if (i == 1) return x1;
00929 if (x1 == 1) return x1;
00930 if (x1 == -1) return as_int (i & 1) ? -1 : 1;
00931 ASSERT (mpz_fits_ulong_p (*i), "exponent too large");
00932 integer r; mpz_pow_ui (*r, *x1, mpz_get_ui (*i));
00933 return r; }
00934
00935 inline friend integer gcd (const integer& a, const integer& b) {
00936 integer r; mpz_gcd (*r, *a, *b); return r; }
00937
00938 inline friend integer gcd (const integer& a, const integer& b,
00939 integer& co_a) {
00940 integer r; mpz_gcdext (*r, *co_a, NULL, *a, *b); return r; }
00941
00942 inline friend integer gcd (const integer& a, const integer& b,
00943 integer& co_a, integer& co_b) {
00944 integer r; mpz_gcdext (*r, *co_a, *co_b, *a, *b); return r; }
00945
00946 inline friend integer lcm (const integer& a, const integer& b) {
00947 integer r; mpz_lcm (*r, *a, *b); return r; }
00948
00949 inline friend xgcd_matrix<integer> xgcd(const integer& a, const integer& b) {
00950 integer g; xgcd_matrix<integer> r;
00951 mpz_gcdext (*g, *(r.a), *(r.b), *a, *b);
00952 r.c= -b/g; r.d= a/g; return r; }
00953
00954 inline friend integer invert_modulo (const integer& a, const integer& b) {
00955 integer r; mpz_invert (*r, *a, *b); return r; }
00956
00957 inline friend int jacobi (const integer& a, const integer& b) {
00958 ASSERT ((b&1) != 0, "second argument must be odd");
00959 return mpz_jacobi (*a, *b); }
00960
00961 inline friend int legendre (const integer& a, const integer& b) {
00962 ASSERT ((b&1) != 0, "second argument must be odd");
00963 return mpz_legendre (*a, *b); }
00964
00965 inline friend int kronecker (const integer& a, const integer& b) {
00966 return mpz_kronecker (*a, *b); }
00967
00968
00969 inline friend integer floor (const integer& x) { return x; }
00970 inline friend integer trunc (const integer& x) { return x; }
00971 inline friend integer ceil (const integer& x) { return x; }
00972 inline friend integer round (const integer& x) { return x; }
00973
00974
00975 inline friend integer raw_integer (nat limb_sz);
00976
00977 inline friend nat hash (const integer& x) {
00978 const __mpz_struct& rep= (*x)[0];
00979 if (rep._mp_size == 0) return 0;
00980 return ((nat) (rep._mp_d[0])) ^ ((nat) (rep._mp_size << 11));
00981 }
00982
00983 inline friend xnat size (const integer& x, nat base) {
00984 return mpz_sizeinbase (*x, base); }
00985
00986 inline friend xnat bit_size (const integer& x) {
00987 return mpz_sizeinbase (*x, 2); }
00988
00989 inline friend xnat limb_size (const integer& x) {
00990 return mpz_size (*x); }
00991
00992 inline friend nat N (const integer& x) {
00993 return limb_size (x); }
00994
00995 inline friend integer lshiftz (const integer& x1, nat shift) {
00996 if (shift == 0) return x1;
00997 if ((GMP_LIMB_BITS * shift) / GMP_LIMB_BITS != shift)
00998 return lshiftz (lshiftz (x1, shift >> 1), shift - (shift >> 1));
00999 integer r; mpz_mul_2exp (*r, *x1, GMP_LIMB_BITS * shift);
01000 return r; }
01001
01002 inline friend integer rshiftz (const integer& x1, nat shift) {
01003 if (shift == 0) return x1;
01004 if ((GMP_LIMB_BITS * shift) / GMP_LIMB_BITS != shift)
01005 return rshiftz (rshiftz (x1, shift >> 1) , shift - (shift >> 1));
01006 integer r; mpz_fdiv_q_2exp (*r, *x1, GMP_LIMB_BITS * shift);
01007 return r; }
01008
01009 inline friend integer co_rshiftz (const integer& x1, nat shift) {
01010 if (shift == 0) return 0;
01011 if ((GMP_LIMB_BITS * shift) / GMP_LIMB_BITS != shift)
01012 return lshiftz (co_rshiftz (rshiftz (x1, shift >> 1),
01013 shift - (shift >> 1)), shift >> 1)
01014 + co_rshiftz (x1, shift >> 1);
01015 integer r; mpz_fdiv_r_2exp (*r, *x1, GMP_LIMB_BITS * shift);
01016 return r; }
01017
01018 friend class rational;
01019 friend integer numerator (const rational& x1);
01020 friend integer denominator (const rational& x1);
01021 template<typename V> friend class floating;
01022 template<typename V> friend integer as_integer (const floating<V>& x);
01023 };
01024 INDIRECT_IMPL (integer, integer_rep)
01025
01026 template<> struct symbolic_type_information<integer> {
01027 static const nat id= SYMBOLIC_INTEGER; };
01028
01029 inline integer raw_integer (nat limb_sz) {
01030 return new integer_rep (limb_sz * BITS_PER_LIMB); }
01031 generic construct (const integer& i);
01032 template<> inline integer duplicate (const integer& i) { return copy (i); }
01033
01034 TRUE_TO_EXACT_IDENTITY_SUGAR(,integer)
01035 POOR_MAN_ELEMENTARY_SUGAR(,integer)
01036
01037
01038
01039
01040
01041 syntactic flatten (const integer& i);
01042
01043 template<>
01044 struct binary_helper<integer>: public void_binary_helper<integer> {
01045 static inline string short_type_name () { return "Z"; }
01046 static inline generic full_type_name () { return "Integer"; }
01047 static inline generic disassemble (const integer& x) {
01048 return as<generic> (as_string (x)); }
01049 static inline integer assemble (const generic& x) {
01050 return integer (as<string> (x)); }
01051 static inline void write (const port& out, const integer& i) {
01052 mpz_binary_write (out, *i); }
01053 static inline integer read (const port& in) {
01054 integer i; mpz_binary_read (in, *i); return i; }
01055 };
01056
01057 template<>
01058 struct as_helper<signed char,integer> {
01059 static inline signed char cv (const integer& i) {
01060 VERIFY (mpz_fits_sshort_p (*i), "integer too large");
01061 signed short r= mpz_get_si (*i);
01062 VERIFY ((unsigned short) abs (r)
01063 <= (unsigned short) ((unsigned char) (-1)), "integer too large");
01064 return (signed char) r; }
01065 };
01066
01067 template<>
01068 struct as_helper<unsigned char,integer> {
01069 static inline unsigned char cv (const integer& i) {
01070 VERIFY (mpz_fits_ushort_p (*i), "integer too large");
01071 unsigned short r= mpz_get_ui (*i);
01072 VERIFY (r <= (unsigned short) ((unsigned char) (-1)), "integer too large");
01073 return (unsigned char) r; }
01074 };
01075
01076 template<>
01077 struct as_helper<short int,integer> {
01078 static inline short int cv (const integer& i) {
01079 VERIFY (mpz_fits_sshort_p (*i), "integer too large");
01080 return (short int) mpz_get_si (*i); }
01081 };
01082
01083 template<>
01084 struct as_helper<unsigned short int,integer> {
01085 static inline unsigned short int cv (const integer& i) {
01086 VERIFY (mpz_fits_ushort_p (*i), "integer too large");
01087 return (unsigned short) mpz_get_ui (*i); }
01088 };
01089
01090 template<>
01091 struct as_helper<int,integer> {
01092 static inline int cv (const integer& i) {
01093 VERIFY (mpz_fits_sint_p (*i), "integer too large");
01094 return (int) mpz_get_si (*i); }
01095 };
01096
01097 template<>
01098 struct as_helper<unsigned int,integer> {
01099 static inline unsigned int cv (const integer& i) {
01100 VERIFY (mpz_fits_uint_p (*i), "integer too large");
01101 return (unsigned int) mpz_get_ui (*i); }
01102 };
01103
01104 template<>
01105 struct as_helper<long int,integer> {
01106 static inline long int cv (const integer& i) {
01107 VERIFY (mpz_fits_slong_p (*i), "integer too large");
01108 return mpz_get_si (*i); }
01109 };
01110
01111 template<>
01112 struct as_helper<unsigned long int,integer> {
01113 static inline unsigned long int cv (const integer& i) {
01114 VERIFY (mpz_fits_ulong_p (*i), "integer too large");
01115 return mpz_get_ui (*i); }
01116 };
01117
01118 #if defined(BASIX_HAVE_LONG_LONG_INT)
01119 template<>
01120 struct as_helper<unsigned long long int,integer> {
01121 static inline unsigned long long int cv (const integer& i) {
01122 const nat s= 8*sizeof(unsigned long int);
01123 return mpz_get_ui (*i)
01124 + MMX_SAFE_LEFT_SHIFT_INT (unsigned long int,
01125 as<unsigned long int> (i >> s), s); }
01126 };
01127
01128 template<>
01129 struct as_helper<long long int,integer> {
01130 static inline long long int cv (const integer& i) {
01131 if (i > 0) return as<unsigned long long int> (i);
01132 return - as<unsigned long long int> (-i); }
01133 };
01134 #endif
01135
01136 template<>
01137 struct is_signed_helper<integer> {
01138 static const bool value = true; };
01139
01140 template<>
01141 struct as_helper<double,integer> {
01142 static inline double cv (const integer& i) { return as_double (i); }
01143 };
01144
01145 template<typename F> inline integer
01146 promote (const F& x, const integer&) { return as<integer> (x); }
01147
01148 inline void set_default (integer& r) { r= 0; }
01149 inline void set_nan (integer& r) { r= 0; }
01150
01151
01152
01153
01154
01155 inline integer factorial (nat i) {
01156 integer r; mpz_fac_ui (*r, i); return r; }
01157
01158 inline integer binomial (nat i, nat j) {
01159 integer r; mpz_bin_uiui (*r, i, j); return r; }
01160
01161 inline integer factorial (const integer& i) {
01162 ASSERT (i >= 0, "positive argument expected");
01163 return factorial ((nat) as_int (i)); }
01164
01165 inline integer binomial (const integer& i, const integer& j) {
01166 ASSERT (i >= 0 && j >= 0, "positive argument expected");
01167 return binomial ((nat) as_int (i), (nat) as_int (j)); }
01168
01169 inline bool is_probable_prime (const integer& i) {
01170 int n= 5, b;
01171 while ((b= mpz_probab_prime_p (*i, n)) == 1 && n < 10) n++;
01172 return b != 0;
01173 }
01174
01175 inline integer probable_previous_prime (const integer& i) {
01176 integer j (i-1);
01177 while (! is_probable_prime (j)) j -= 1;
01178 return j;
01179 }
01180
01181 inline integer probable_next_prime (const integer& i) {
01182 integer j (i+1);
01183 while (! is_probable_prime (j)) j += 1;
01184 return j;
01185 }
01186
01187 template<typename C> C
01188 binpow (const C& i, const integer& n) {
01189 if (n <= 1) return n == 0 ? promote (1, i) : i;
01190 C j= binpow (i, n >> 1);
01191 if ((n & 1) == 0) return square (j);
01192 else return square (j) * i;
01193 }
01194
01195 inline nat dyadic_valuation (const integer& i) {
01196 if (i == integer (0)) return (nat) -1;
01197 return mpz_scan1 (* i, 0);
01198 }
01199
01200 #define HELPER(type) \
01201 inline nat dyadic_valuation (const type& i) { \
01202 if (i == 0) return (nat) -1; \
01203 for(nat v= 0; v < (8 * sizeof (i)); ++v) \
01204 if ((i >> v) & 1) return v; \
01205 return (nat) -1; \
01206 }
01207
01208 HELPER(signed char)
01209 HELPER(unsigned char)
01210 HELPER(signed short)
01211 HELPER(unsigned short)
01212 HELPER(signed int)
01213 HELPER(unsigned int)
01214 HELPER(signed long)
01215 HELPER(unsigned long)
01216 HELPER(signed long long)
01217 HELPER(unsigned long long)
01218 #undef HELPER
01219
01220 bool reconstruct (integer& n, integer& d,
01221 const integer& u, const integer& m,
01222 const integer& N, const integer& D);
01223
01224
01225
01226
01227 bool reconstruct (integer& n, integer& d, const integer& u, const integer& m);
01228
01229
01230
01231
01232
01233 #define make_literal_integer make_literal<integer>
01234 #define integer_construct(i) as<generic> (integer (i))
01235
01236
01237 class literal;
01238 void numeric_to_string (const integer& x, string& s);
01239 bool string_to_numeric (const string& s, integer& val);
01240 bool is_literal_integer (const literal& l);
01241 integer as_literal_integer (const literal& l);
01242
01243 }
01244 #endif // __MMX_INTEGER_HPP