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