00001
00002
00003
00004
00005
00006
00007
00008 #ifndef SYNAPS_ARITHM__BC_H_INCLUDED_
00009 #define SYNAPS_ARITHM__BC_H_INCLUDED_
00010
00011 #ifndef NDEBUG
00012 #include <cassert>
00013 #endif
00014
00015
00016
00017
00018
00019 #ifdef win32
00020 #define const
00021 #endif
00022
00023 #include <synaps/init.h>
00024
00025 __BEGIN_NAMESPACE_SYNAPS
00026
00027
00028 template <class T> struct Scl<T>
00029 #ifdef PL_CMM
00030 : public GcObject
00031 #endif
00032 {
00033 public:
00034 Scl<T> ( );
00035 Scl<T> (const Scl<T>& b);
00036 Scl<T> (signed long sl);
00037 Scl<T> (unsigned long ul);
00038 Scl<T> (int si);
00039 Scl<T> (const char* string, int base = 10);
00040 Scl<T> ( MP_INT new_z ) { z = new_z; }
00041
00042 ~Scl<T> ();
00043 friend ostream& operator << (ostream& os, const Scl<T>& b);
00044 friend istream& operator >> (istream& is, Scl<T>& b);
00045
00046 friend unsigned long BigIntToUL (const Scl<T>& b);
00047 friend signed long BigIntToSL (const Scl<T>& b);
00048
00049 friend size_t log (const Scl<T>& b);
00050 friend size_t log (const Scl<T>& b, int base);
00051
00052 friend int sign (const Scl<T>& b);
00053
00054 friend int compare (const Scl<T>& b1, const Scl<T>& b2);
00055 friend int compare (const Scl<T>& b, unsigned long ul);
00056 friend int compare (const Scl<T>& b, long sl);
00057
00058 friend bool IsPositive (const Scl<T>& b);
00059 friend bool IsNegative (const Scl<T>& b);
00060 friend bool IsZero (const Scl<T>& b);
00061 friend bool IsOne (const Scl<T>& b);
00062 friend bool IsMinusOne (const Scl<T>& b);
00063 friend bool IsOdd (const Scl<T>& b);
00064 friend bool IsEven (const Scl<T>& b);
00065 friend bool IsPerfectSquare (const Scl<T>& b);
00066 friend bool IsProbablyPrime (const Scl<T>& b, int reps = 25);
00067
00068 bool operator == (const Scl<T>& rhs) const;
00069 bool operator != (const Scl<T>& rhs) const;
00070 bool operator > (const Scl<T>& rhs) const;
00071 bool operator >= (const Scl<T>& rhs) const;
00072 bool operator < (const Scl<T>& rhs) const;
00073 bool operator <= (const Scl<T>& rhs) const;
00074
00075 bool operator == (long sl) const;
00076 bool operator != (long sl) const;
00077 bool operator > (long sl) const;
00078 bool operator >= (long sl) const;
00079 bool operator < (long sl) const;
00080 bool operator <= (long sl) const;
00081
00082 bool operator == (int si) const;
00083 bool operator != (int si) const;
00084 bool operator > (int si) const;
00085 bool operator >= (int si) const;
00086 bool operator < (int si) const;
00087 bool operator <= (int si) const;
00088
00089 bool operator == (unsigned long ul) const;
00090 bool operator != (unsigned long ul) const;
00091 bool operator > (unsigned long ul) const;
00092 bool operator >= (unsigned long ul) const;
00093 bool operator < (unsigned long ul) const;
00094 bool operator <= (unsigned long ul) const;
00095
00096
00097
00098
00099
00100 void operator = (const Scl<T>& rhs);
00101 void operator += (const Scl<T>& rhs);
00102 void operator -= (const Scl<T>& rhs);
00103 void operator *= (const Scl<T>& rhs);
00104 void operator /= (const Scl<T>& rhs);
00105 void operator %= (const Scl<T>& rhs);
00106
00107 void operator = (unsigned long rhs);
00108 void operator += (unsigned long rhs);
00109 void operator -= (unsigned long rhs);
00110 void operator *= (unsigned long rhs);
00111 void operator /= (unsigned long rhs);
00112 void operator %= (unsigned long rhs);
00113
00114 void operator = (long rhs);
00115 void operator += (long rhs);
00116 void operator -= (long rhs);
00117 void operator *= (long rhs);
00118 void operator /= (long rhs);
00119 void operator %= (long rhs);
00120
00121 void operator ++ ( );
00122 void operator -- ( );
00123
00124 void Div2Exp (unsigned long exponent_of_2);
00125 void GCD (const Scl<T>& b2);
00126 void Mod2Exp (unsigned long exponent_of_2);
00127 void Mul2Exp (unsigned long exponent_of_2);
00128 void PowMod (const Scl<T>& exp, const Scl<T>& m);
00129 void PowMod (unsigned long exp, const Scl<T>& m);
00130 void abs ( );
00131 void factorial (unsigned long n);
00132 void negate ( );
00133 void pow (unsigned long exp);
00134 void pow (unsigned long base, unsigned long exp);
00135 void quo (const Scl<T>& divisor);
00136 void quo (unsigned long divisor);
00137 void rem (const Scl<T>& divisor);
00138 unsigned long rem (unsigned long divisor);
00139 void sqrt ( );
00140
00141 friend void SqrtRem (Scl<T>& sqrt, Scl<T>& rem, const Scl<T>& b);
00142
00143 friend void QuoRem (Scl<T>& q, Scl<T>& r,
00144 const Scl<T>& divdend, const Scl<T>& divisor);
00145
00146 friend unsigned long QuoRem (Scl<T>& q, Scl<T>& r,
00147 const Scl<T>& divdend, unsigned long divisor);
00148
00149 friend void DivMod (Scl<T>& q, Scl<T>& r,
00150 const Scl<T>& divdend, const Scl<T>& divisor);
00151
00152 friend void DivMod (Scl<T>& q, Scl<T>& r, const Scl<T>& divdend,
00153 unsigned long divisor);
00154
00155 friend void ExtGCD (Scl<T>& gcd, Scl<T>& a, Scl<T>& b,
00156 const Scl<T>& x, const Scl<T>& y);
00157
00158 friend void HalfExtGCD (Scl<T>& gcd, Scl<T>& a,
00159 const Scl<T>& x, const Scl<T>& y);
00160
00161
00162 #ifdef PL_CMM
00163 void traverse();
00164 #endif
00165 mpz z;
00166 };
00167
00168
00169
00170
00171
00172
00173 Scl<T>& operator - (const Scl<T>& b);
00174
00175 Scl<T> operator + (const Scl<T>& b1, const Scl<T>& b2);
00176 Scl<T>& operator - (const Scl<T>& b1, const Scl<T>& b2);
00177 Scl<T>& operator * (const Scl<T>& b1, const Scl<T>& b2);
00178 Scl<T>& operator / (const Scl<T>& b1, const Scl<T>& b2);
00179 Scl<T>& operator % (const Scl<T>& b1, const Scl<T>& b2);
00180
00181 Scl<T>& operator + (const Scl<T>& b, unsigned long ul);
00182 Scl<T>& operator - (const Scl<T>& b, unsigned long ul);
00183 Scl<T>& operator * (const Scl<T>& b, unsigned long ul);
00184 Scl<T>& operator / (const Scl<T>& b, unsigned long ul);
00185 Scl<T>& operator % (const Scl<T>& b, unsigned long ul);
00186
00187 Scl<T>& operator + (unsigned long ul, const Scl<T>& b);
00188 Scl<T>& operator * (unsigned long ul, const Scl<T>& b);
00189
00190 Scl<T>& operator + (const Scl<T>& b, long sl);
00191 Scl<T>& operator - (const Scl<T>& b, long sl);
00192 Scl<T>& operator * (const Scl<T>& b, long sl);
00193 Scl<T>& operator / (const Scl<T>& b, long sl);
00194 Scl<T>& operator % (const Scl<T>& b, long sl);
00195
00196 Scl<T>& operator + (long sl, const Scl<T>& b);
00197 Scl<T>& operator * (long sl, const Scl<T>& b);
00198
00199 Scl<T>& Div2Exp (const Scl<T>& b, unsigned long exponent_of_2);
00200 Scl<T>& GCD (const Scl<T>& b1, const Scl<T>& b2);
00201 Scl<T>& gcd (const Scl<T>& b1, const Scl<T>& b2);
00202 Scl<T>& Mod2Exp (const Scl<T>& b, unsigned long exponent_of_2);
00203 Scl<T>& Mul2Exp (const Scl<T>& b, unsigned long exponent_of_2);
00204 Scl<T>& PowMod (const Scl<T>& b, const Scl<T>& exp, const Scl<T>& m);
00205 Scl<T>& PowMod (const Scl<T>& b, unsigned long exp, const Scl<T>& m);
00206 Scl<T>& abs (const Scl<T>& b);
00207
00208 Scl<T>& pow (const Scl<T>& base, unsigned long exp);
00209 Scl<T>& quo (const Scl<T>& dividend, const Scl<T>& divisor);
00210 Scl<T>& quo (const Scl<T>& dividend, unsigned long divisor);
00211 Scl<T>& rem (const Scl<T>& dividend, const Scl<T>& divisor);
00212 Scl<T>& sqrt (const Scl<T>& b);
00213 unsigned long rem (const Scl<T>& b, unsigned long divisor);
00214
00215 Scl<T>& BigIntFactorial (unsigned long n);
00216
00217
00218
00219
00220 inline
00221 Scl<T>::Scl<T> ( )
00222 {
00223 mpz_init(&z);
00224 }
00225
00226 inline
00227 Scl<T>::Scl<T> (const Scl<T>& b)
00228 {
00229 mpz_init_set(&z, &b.z);
00230 }
00231
00232 inline
00233 Scl<T>::Scl<T> (signed long int sl)
00234 {
00235 mpz_init_set_si(&z, sl);
00236 }
00237
00238 inline
00239 Scl<T>::Scl<T> (unsigned long int ul)
00240 {
00241 mpz_init_set_ui(&z, ul);
00242 }
00243
00244 inline
00245 Scl<T>::Scl<T> (int si)
00246 {
00247 mpz_init_set_si(&z, (long) si);
00248 }
00249
00250 inline
00251 Scl<T>::Scl<T> (const char *string, int base)
00252 {
00253 if (mpz_init_set_str(&z, string, base))
00254 cerr << "Scl<T>::Scl<T>: The string " << string
00255 << " is not a valid number in base " << base << endl;
00256 }
00257
00258
00259
00260
00261 inline
00262 Scl<T>::~Scl<T> ( )
00263 {
00264 #if defined(PL_CMM)
00265
00266
00267
00268
00269
00270 #else
00271 mpz_clear(&z);
00272 #endif
00273 }
00274
00275
00276
00277
00278 inline unsigned long
00279 BigIntToUL (const Scl<T>& b)
00280 {
00281 return mpz_get_ui(&b.z);
00282 }
00283
00284
00285
00286
00287 inline signed long
00288 BigIntToSL (const Scl<T>& b)
00289 {
00290 return mpz_get_si(&b.z);
00291 }
00292
00293
00294
00295
00296 inline size_t
00297 log (const Scl<T>& b)
00298 {
00299 return mpz_size(&b.z);
00300 }
00301
00302 inline size_t
00303 log (const Scl<T>& b, int base)
00304 {
00305 assert(base >= 2 && base <= 36);
00306 return mpz_sizeinbase(&b.z, base);
00307 }
00308
00309
00310
00311 inline int
00312 sign (const Scl<T>& b)
00313 {
00314 if (b.z._mp_size == 0)
00315 return 0;
00316 else
00317 return b.z._mp_size > 0 ? 1 : -1;
00318 }
00319
00320
00321
00322
00323 inline int
00324 compare (const Scl<T>& b1, const Scl<T>& b2)
00325 {
00326 return mpz_cmp(&b1.z, &b2.z);
00327 }
00328
00329 inline int
00330 compare (const Scl<T>& b, unsigned long ul)
00331 {
00332 return mpz_cmp_ui(&b.z, ul);
00333 }
00334
00335 inline int
00336 compare (const Scl<T>& b, long sl)
00337 {
00338 return mpz_cmp_si(&b.z, sl);
00339 }
00340
00341
00342
00343
00344 inline bool
00345 IsPositive (const Scl<T>& b)
00346 {
00347 return b.z._mp_size > 0;
00348 }
00349
00350 inline bool
00351 IsNegative (const Scl<T>& b)
00352 {
00353 return b.z._mp_size < 0;
00354 }
00355
00356 inline bool
00357 IsZero (const Scl<T>& b)
00358 {
00359 return b.z._mp_size == 0;
00360 }
00361
00362 inline bool
00363 IsOne(const Scl<T>& b)
00364 {
00365 return b.z._mp_size == 1 && b.z._mp_d[0] == 1;
00366 }
00367
00368 inline bool
00369 IsMinusOne (const Scl<T>& b)
00370 {
00371 return b.z._mp_size == -1 && b.z._mp_d[0] == 1;
00372 }
00373
00374 inline bool
00375 IsOdd (const Scl<T>& b)
00376 {
00377 return b.z._mp_size != 0 && (b.z._mp_d[0] & ((mp_limb_t) 1));
00378 }
00379
00380 inline bool
00381 IsEven (const Scl<T>& b)
00382 {
00383 return b.z._mp_size == 0 || (b.z._mp_d[0] ^ ((mp_limb_t) 0));
00384 }
00385
00386 inline bool
00387 IsPerfectSquare (const Scl<T>& b)
00388 {
00389 return mpz_perfect_square_p(&b.z);
00390 }
00391
00392 inline bool
00393 IsProbablyPrime (const Scl<T>& b, int reps )
00394 {
00395 return mpz_probab_prime_p(&b.z, reps);
00396 }
00397
00398
00399
00400
00401 inline bool
00402 Scl<T>::operator == (const Scl<T>& rhs) const
00403 {
00404 return mpz_cmp(&z, &rhs.z) == 0;
00405 }
00406
00407 inline bool
00408 Scl<T>::operator != (const Scl<T>& rhs) const
00409 {
00410 return mpz_cmp(&z, &rhs.z) != 0;
00411 }
00412
00413 inline bool
00414 Scl<T>::operator > (const Scl<T>& rhs) const
00415 {
00416 return mpz_cmp(&z, &rhs.z) > 0;
00417 }
00418
00419 inline bool
00420 Scl<T>::operator >= (const Scl<T>& rhs) const
00421 {
00422 return mpz_cmp(&z, &rhs.z) >= 0;
00423 }
00424
00425 inline bool
00426 Scl<T>::operator < (const Scl<T>& rhs) const
00427 {
00428 return mpz_cmp(&z, &rhs.z) < 0;
00429 }
00430
00431 inline bool
00432 Scl<T>::operator <= (const Scl<T>& rhs) const
00433 {
00434 return mpz_cmp(&z, &rhs.z) <= 0;
00435 }
00436
00437
00438
00439
00440 inline bool
00441 Scl<T>::operator == (long sl) const
00442 {
00443 return mpz_cmp_si(&z, sl) == 0;
00444 }
00445
00446 inline bool
00447 Scl<T>::operator != (long sl) const
00448 {
00449 return mpz_cmp_si(&z, sl) != 0;
00450 }
00451
00452 inline bool
00453 Scl<T>::operator > (long sl) const
00454 {
00455 return mpz_cmp_si(&z, sl) > 0;
00456 }
00457
00458 inline bool
00459 Scl<T>::operator >= (long sl) const
00460 {
00461 return mpz_cmp_si(&z, sl) >= 0;
00462 }
00463
00464 inline bool
00465 Scl<T>::operator < (long sl) const
00466 {
00467 return mpz_cmp_si(&z, sl) < 0;
00468 }
00469
00470 inline bool
00471 Scl<T>::operator <= (long sl) const
00472 {
00473 return mpz_cmp_si(&z, sl) <= 0;
00474 }
00475
00476
00477
00478
00479 inline bool
00480 Scl<T>::operator == (int si) const
00481 {
00482 return mpz_cmp_si(&z, (long) si) == 0;
00483 }
00484
00485 inline bool
00486 Scl<T>::operator != (int si) const
00487 {
00488 return mpz_cmp_si(&z, (long) si) != 0;
00489 }
00490
00491 inline bool
00492 Scl<T>::operator > (int si) const
00493 {
00494 return mpz_cmp_si(&z, (long) si) > 0;
00495 }
00496
00497 inline bool
00498 Scl<T>::operator >= (int si) const
00499 {
00500 return mpz_cmp_si(&z, (long) si) >= 0;
00501 }
00502
00503 inline bool
00504 Scl<T>::operator < (int si) const
00505 {
00506 return mpz_cmp_si(&z, (long) si) < 0;
00507 }
00508
00509 inline bool
00510 Scl<T>::operator <= (int si) const
00511 {
00512 return mpz_cmp_si(&z, (long) si) <= 0;
00513 }
00514
00515
00516
00517
00518
00519 inline bool
00520 Scl<T>::operator == (unsigned long ul) const
00521 {
00522 return mpz_cmp_ui(&z, ul) == 0;
00523 }
00524
00525 inline bool
00526 Scl<T>::operator != (unsigned long ul) const
00527 {
00528 return mpz_cmp_ui(&z, ul) != 0;
00529 }
00530
00531 inline bool
00532 Scl<T>::operator > (unsigned long ul) const
00533 {
00534 return mpz_cmp_ui(&z, ul) > 0;
00535 }
00536
00537 inline bool
00538 Scl<T>::operator >= (unsigned long ul) const
00539 {
00540 return mpz_cmp_ui(&z, ul) >= 0;
00541 }
00542
00543 inline bool
00544 Scl<T>::operator < (unsigned long ul) const
00545 {
00546 return mpz_cmp_ui(&z, ul) < 0;
00547 }
00548
00549 inline bool
00550 Scl<T>::operator <= (unsigned long ul) const
00551 {
00552 return mpz_cmp_ui(&z, ul) <= 0;
00553 }
00554
00555
00556
00557 inline void
00558 Scl<T>::operator = (const Scl<T>& rhs)
00559 {
00560 if (this != &rhs)
00561 mpz_set(&z, &rhs.z);
00562 }
00563
00564 inline void
00565 Scl<T>::operator += (const Scl<T>& rhs)
00566 {
00567 mpz_add(&z, &z, &rhs.z);
00568 }
00569
00570 inline void
00571 Scl<T>::operator -= (const Scl<T>& rhs)
00572 {
00573 mpz_sub(&z, &z, &rhs.z);
00574 }
00575
00576 inline void
00577 Scl<T>::operator *= (const Scl<T>& rhs)
00578 {
00579 mpz_mul(&z, &z, &rhs.z);
00580 }
00581
00582 inline void
00583 Scl<T>::operator /= (const Scl<T>& rhs)
00584 {
00585
00586 mpz_divexact(&z, &z, &rhs.z);
00587 }
00588
00589 inline void
00590 Scl<T>::operator %= (const Scl<T>& rhs)
00591 {
00592 mpz_mod(&z, &z, &rhs.z);
00593 }
00594
00595
00596
00597
00598 inline void
00599 Scl<T>::operator = (unsigned long ul)
00600 {
00601 mpz_set_ui(&z, ul);
00602 }
00603
00604 inline void
00605 Scl<T>::operator += (unsigned long ul)
00606 {
00607 mpz_add_ui(&z, &z, ul);
00608 }
00609
00610 inline void
00611 Scl<T>::operator -= (unsigned long ul)
00612 {
00613 mpz_sub_ui(&z, &z, ul);
00614 }
00615
00616 inline void
00617 Scl<T>::operator *= (unsigned long ul)
00618 {
00619 mpz_mul_ui(&z, &z, ul);
00620 }
00621
00622 inline void
00623 Scl<T>::operator /= (unsigned long ul)
00624 {
00625 mpz_div_ui(&z, &z, ul);
00626 }
00627
00628 inline void
00629 Scl<T>::operator %= (unsigned long ul)
00630 {
00631 mpz_mod_ui(&z, &z, ul);
00632 }
00633
00634
00635
00636
00637 inline void
00638 Scl<T>::operator = (long sl)
00639 {
00640 mpz_set_si(&z, sl);
00641 }
00642
00643 inline void
00644 Scl<T>::operator += (long sl)
00645 {
00646 if (sl >= 0)
00647 mpz_add_ui(&z, &z, (unsigned long) sl);
00648 else
00649 mpz_sub_ui(&z, &z, ((unsigned long) -sl));
00650 }
00651
00652 inline void
00653 Scl<T>::operator -= (long sl)
00654 {
00655 if (sl >= 0)
00656 mpz_sub_ui(&z, &z, (unsigned long) sl);
00657 else
00658 mpz_add_ui(&z, &z, (unsigned long) sl);
00659 }
00660
00661 inline void
00662 Scl<T>::operator *= (long sl)
00663 {
00664 if (sl >= 0)
00665 mpz_mul_ui(&z, &z, (unsigned long) sl);
00666 else
00667 {
00668 z._mp_size = -z._mp_size;
00669 mpz_mul_ui(&z, &z, ((unsigned long) -sl));
00670 }
00671 }
00672
00673 inline void
00674 Scl<T>::operator /= (long sl)
00675 {
00676 if (sl >= 0)
00677 mpz_div_ui(&z, &z, (unsigned long) sl);
00678 else
00679 {
00680 z._mp_size = -z._mp_size;
00681 mpz_div_ui(&z, &z, ((unsigned long) -sl));
00682 }
00683 }
00684
00685
00686
00687
00688
00689
00690
00691
00692
00693
00694 inline void
00695 Scl<T>::operator ++ ( )
00696 {
00697 mpz_add_ui(&z, &z, 1);
00698 }
00699
00700 inline void
00701 Scl<T>::operator -- ( )
00702 {
00703 mpz_sub_ui(&z, &z, 1);
00704 }
00705
00706
00707
00708
00709 inline void
00710 Scl<T>::Div2Exp (unsigned long exponent_of_2)
00711 {
00712 mpz_div_2exp(&z, &z, exponent_of_2);
00713 }
00714
00715 inline void
00716 Scl<T>::GCD (const Scl<T>& b2)
00717 {
00718 mpz_gcd (&z, &z, &b2.z);
00719 }
00720
00721
00722 inline void
00723 Scl<T>::Mod2Exp (unsigned long exponent_of_2)
00724 {
00725 mpz_mod_2exp(&z, &z, exponent_of_2);
00726 }
00727
00728 inline void
00729 Scl<T>::Mul2Exp (unsigned long exponent_of_2)
00730 {
00731 mpz_mul_2exp(&z, &z, exponent_of_2);
00732 }
00733
00734 inline void
00735 Scl<T>::PowMod (const Scl<T>& exp, const Scl<T>& m)
00736 {
00737 mpz_powm(&z, &z, &exp.z, &m.z);
00738 }
00739
00740 inline void
00741 Scl<T>::PowMod (unsigned long exp, const Scl<T>& m)
00742 {
00743 mpz_powm_ui(&z, &z, exp, &m.z);
00744 }
00745
00746 inline void
00747 Scl<T>::abs ( )
00748 {
00749 if (z._mp_size < 0)
00750 z._mp_size = - z._mp_size;
00751 }
00752
00753 inline void
00754 Scl<T>::factorial (unsigned long n)
00755 {
00756 mpz_fac_ui(&z, n);
00757 }
00758
00759 inline void
00760 Scl<T>::negate ( )
00761 {
00762 z._mp_size = - z._mp_size;
00763 }
00764
00765 inline void
00766 Scl<T>::pow (unsigned long exp)
00767 {
00768 mpz_pow_ui(&z, &z, exp);
00769 }
00770
00771 inline void
00772 Scl<T>::pow (unsigned long base, unsigned long exp)
00773 {
00774 mpz_ui_pow_ui(&z, base, exp);
00775 }
00776
00777 inline void
00778 Scl<T>::quo (const Scl<T>& divisor)
00779 {
00780 mpz_mdiv (&z, &z, &divisor.z);
00781 }
00782
00783 inline void
00784 Scl<T>::quo (unsigned long divisor)
00785 {
00786 mpz_mdiv_ui(&z, &z, divisor);
00787 }
00788
00789 inline void
00790 Scl<T>::rem (const Scl<T>& divisor)
00791 {
00792 mpz_mmod(&z, &z, &divisor.z);
00793 }
00794
00795 inline unsigned long
00796 Scl<T>::rem (unsigned long divisor)
00797 {
00798 return mpz_mmod_ui(&z, &z, divisor);
00799 }
00800
00801 inline void
00802 Scl<T>::sqrt ( )
00803 {
00804 mpz_sqrt(&z, &z);
00805 }
00806
00807 inline void
00808 SqrtRem (Scl<T>& sqrt, Scl<T>& rem, const Scl<T>& b)
00809 {
00810 mpz_sqrtrem(&sqrt.z, &rem.z, &b.z);
00811 }
00812
00813 inline void
00814 QuoRem (Scl<T>& q, Scl<T>& r, const Scl<T>& divdend, const Scl<T>& divisor)
00815 {
00816 mpz_mdivmod(&q.z, &r.z, &divdend.z, &divisor.z);
00817 }
00818
00819 inline unsigned long
00820 QuoRem (Scl<T>& q, Scl<T>& r, const Scl<T>& divdend, unsigned long divisor)
00821 {
00822 return mpz_mdivmod_ui(&q.z, &r.z, &divdend.z, divisor);
00823 }
00824
00825 inline void
00826 DivMod (Scl<T>& q, Scl<T>& r, const Scl<T>& divdend, const Scl<T>& divisor)
00827 {
00828 mpz_divmod(&q.z, &r.z, &divdend.z, &divisor.z);
00829 }
00830
00831 inline void
00832 DivMod (Scl<T>& q, Scl<T>& r, const Scl<T>& divdend, unsigned long divisor)
00833 {
00834 mpz_divmod_ui(&q.z, &r.z, &divdend.z, divisor);
00835 }
00836
00837 inline void
00838 ExtGCD (Scl<T>& gcd, Scl<T>& a, Scl<T>& b, const Scl<T>& x, const Scl<T>& y)
00839 {
00840 mpz_gcdext(&gcd.z, &a.z, &b.z, &x.z, &y.z);
00841 }
00842
00843 inline void
00844 HalfExtGCD (Scl<T>& gcd, Scl<T>& a, const Scl<T>& x, const Scl<T>& y)
00845 {
00846 mpz_gcdext(&gcd.z, &a.z, 0, &x.z, &y.z);
00847 }
00848
00849
00850
00851
00852
00853
00854
00855 #if defined(__GNUG__) && !defined(NO_NRV)
00856 #define NRVAL(name) return name
00857 #define NRCODE(code) code
00858 #define NONRCODE(code)
00859 #else
00860 #define NRVAL(name)
00861 #define NRCODE(code)
00862 #define NONRCODE(code) code
00863 #endif
00864
00865
00866 inline Scl<T>
00867 operator - (const Scl<T>& b) NRVAL(r(b))
00868 {
00869 NRCODE(r.negate();)
00870 NONRCODE(Scl<T> r(b); r.negate(); return r;)
00871 }
00872
00873 inline Scl<T>
00874 operator + (const Scl<T>& b1, const Scl<T>& b2) NRVAL(r(b1))
00875 {
00876 NRCODE(r += b2;)
00877 NONRCODE(Scl<T> r(b1); r += b2; return r;)
00878 }
00879
00880 inline Scl<T>
00881 operator - (const Scl<T>& b1, const Scl<T>& b2) NRVAL(r(b1))
00882 {
00883 NRCODE(r -= b2;)
00884 NONRCODE(Scl<T> r(b1); r -= b2; return r;)
00885 }
00886
00887 inline Scl<T>
00888 operator * (const Scl<T>& b1, const Scl<T>& b2) NRVAL(r(b1))
00889 {
00890 NRCODE(r *= b2;)
00891 NONRCODE(Scl<T> r(b1); r *= b2; return r;)
00892 }
00893
00894 inline Scl<T>
00895 operator / (const Scl<T>& b1, const Scl<T>& b2) NRVAL(r(b1))
00896 {
00897 NRCODE(r /= b2;)
00898 NONRCODE(Scl<T> r(b1); r /= b2; return r;)
00899 }
00900
00901 inline Scl<T>
00902 operator % (const Scl<T>& b1, const Scl<T>& b2) NRVAL(r(b1))
00903 {
00904 NRCODE(r %= b2;)
00905 NONRCODE(Scl<T> r(b1); r %= b2; return r;)
00906 }
00907
00908
00909
00910 inline Scl<T>
00911 operator + (const Scl<T>& b, unsigned long ul) NRVAL(r(b))
00912 {
00913 NRCODE(r += ul;)
00914 NONRCODE(Scl<T> r(b); r += ul; return r;)
00915 }
00916
00917 inline Scl<T>
00918 operator - (const Scl<T>& b, unsigned long ul) NRVAL(r(b))
00919 {
00920 NRCODE(r -= ul;)
00921 NONRCODE(Scl<T> r(b); r -= ul; return r;)
00922 }
00923
00924 inline Scl<T>
00925 operator * (const Scl<T>& b, unsigned long ul) NRVAL(r(b))
00926 {
00927 NRCODE(r *= ul;)
00928 NONRCODE(Scl<T> r(b); r *= ul; return r;)
00929 }
00930
00931 inline Scl<T>
00932 operator / (const Scl<T>& b, unsigned long ul) NRVAL(r(b))
00933 {
00934 NRCODE(r /= ul;)
00935 NONRCODE(Scl<T> r(b); r /= ul; return r;)
00936 }
00937
00938 inline Scl<T>
00939 operator % (const Scl<T>& b, unsigned long ul) NRVAL(r(b))
00940 {
00941 NRCODE(r %= ul;)
00942 NONRCODE(Scl<T> r(b); r %= ul; return r;)
00943 }
00944
00945
00946
00947 inline Scl<T>
00948 operator + (unsigned long ul, const Scl<T>& b)
00949 {
00950 return b + ul;
00951 }
00952
00953 inline Scl<T>
00954 operator * (unsigned long ul, const Scl<T>& b)
00955 {
00956 return b * ul;
00957 }
00958
00959
00960
00961 inline Scl<T>
00962 operator + (const Scl<T>& b, long sl) NRVAL(r(b))
00963 {
00964 NRCODE(r += sl;)
00965 NONRCODE(Scl<T> r(b); r += sl; return r;)
00966 }
00967
00968
00969 inline Scl<T>
00970 operator - (const Scl<T>& b, long sl) NRVAL(r(b))
00971 {
00972 NRCODE(r -= sl;)
00973 NONRCODE(Scl<T> r(b); r -= sl; return r;)
00974 }
00975
00976
00977 inline Scl<T>
00978 operator * (const Scl<T>& b, long sl) NRVAL(r(b))
00979 {
00980 NRCODE(r *= sl;)
00981 NONRCODE(Scl<T> r(b); r *= sl; return r;)
00982 }
00983
00984
00985 inline Scl<T>
00986 operator / (const Scl<T>& b, long sl) NRVAL(r(b))
00987 {
00988 NRCODE(r /= sl;)
00989 NONRCODE(Scl<T> r(b); r /= sl; return r;)
00990 }
00991
00992
00993 inline Scl<T>
00994 operator % (const Scl<T>& b, long sl) NRVAL(r(b))
00995 {
00996 NRCODE(r %= sl;)
00997 NONRCODE(Scl<T> r(b); r %= sl; return r;)
00998 }
00999
01000
01001
01002 inline Scl<T>
01003 operator + (long sl, const Scl<T>& b)
01004 {
01005 return b + sl;
01006 }
01007
01008 inline Scl<T>
01009 operator * (long sl, const Scl<T>& b)
01010 {
01011 return b * sl;
01012 }
01013
01014
01015
01016 inline Scl<T>
01017 Div2Exp (const Scl<T>& b, unsigned long exponent_of_2) NRVAL(r(b))
01018 {
01019 NRCODE(r.Div2Exp(exponent_of_2);)
01020 NONRCODE(Scl<T> r(b); r.Div2Exp(exponent_of_2); return r;)
01021 }
01022
01023 inline Scl<T>
01024 GCD (const Scl<T>& b1, const Scl<T>& b2) NRVAL(r(b1))
01025 {
01026 NRCODE(r.GCD(b2);)
01027 NONRCODE(Scl<T> r(b1); r.GCD(b2); return r;)
01028 }
01029
01030 inline Scl<T>
01031 gcd (const Scl<T>& b1, const Scl<T>& b2) NRVAL(r(b1))
01032 {
01033 NRCODE(r.GCD(b2);)
01034 NONRCODE(Scl<T> r(b1); r.GCD(b2); return r;)
01035 }
01036
01037 inline Scl<T>
01038 Mod2Exp (const Scl<T>& b, unsigned long exponent_of_2) NRVAL(r(b))
01039 {
01040 NRCODE(r.Mod2Exp(exponent_of_2);)
01041 NONRCODE(Scl<T> r(b); r.Mod2Exp(exponent_of_2); return r;)
01042 }
01043
01044 inline Scl<T>
01045 Mul2Exp (const Scl<T>& b, unsigned long exponent_of_2) NRVAL(r(b))
01046 {
01047 NRCODE(r.Mul2Exp(exponent_of_2);)
01048 NONRCODE(Scl<T> r(b); r.Mul2Exp(exponent_of_2); return r;)
01049 }
01050
01051 inline Scl<T>
01052 PowMod (const Scl<T>& b, const Scl<T>& exp, const Scl<T>& m) NRVAL(r(b))
01053 {
01054 NRCODE(r.PowMod(exp, m);)
01055 NONRCODE(Scl<T> r(b); r.PowMod(exp,m); return r;)
01056 }
01057
01058 inline Scl<T>
01059 PowMod (const Scl<T>& b, unsigned long exp, const Scl<T>& m) NRVAL(r(b))
01060 {
01061 NRCODE(r.PowMod(exp, m);)
01062 NONRCODE(Scl<T> r(b); r.PowMod(exp,m); return r;)
01063 }
01064
01065 inline Scl<T>
01066 abs (const Scl<T>& b) NRVAL(r(b))
01067 {
01068 NRCODE(r.abs();)
01069 NONRCODE(Scl<T> r(b); r.abs(); return r;)
01070 }
01071
01072
01073
01074
01075
01076
01077
01078
01079 inline Scl<T>
01080 pow (const Scl<T>& base, unsigned long exp) NRVAL(r(base))
01081 {
01082 NRCODE(r.pow(exp);)
01083 NONRCODE(Scl<T> r(base); r.pow(exp); return r;)
01084 }
01085
01086 inline Scl<T>
01087 quo (const Scl<T>& dividend, const Scl<T>& divisor) NRVAL(r(dividend))
01088 {
01089 NRCODE(r.quo(divisor);)
01090 NONRCODE(Scl<T> r(dividend); r.quo(divisor); return r;)
01091 }
01092
01093 inline Scl<T>
01094 quo (const Scl<T>& dividend, unsigned long divisor) NRVAL(r(dividend))
01095 {
01096 NRCODE(r.quo(divisor);)
01097 NONRCODE(Scl<T> r(dividend); r.quo(divisor); return r;)
01098 }
01099
01100 inline Scl<T>
01101 rem (const Scl<T>& dividend, const Scl<T>& divisor) NRVAL(r(dividend))
01102 {
01103 NRCODE(r.rem(divisor);)
01104 NONRCODE(Scl<T> r(dividend); r.rem(divisor); return r;)
01105 }
01106
01107 inline Scl<T>
01108 sqrt (const Scl<T>& b) NRVAL(r(b))
01109 {
01110 NRCODE(r.sqrt();)
01111 NONRCODE(Scl<T> r(b); r.sqrt(); return r;)
01112 }
01113
01114 inline unsigned long
01115 rem (const Scl<T>& b, unsigned long divisor)
01116 {
01117 Scl<T> r(b);
01118 return r.rem(divisor);
01119 }
01120
01121 inline Scl<T>
01122 BigIntFactorial (unsigned long n) NRVAL(r)
01123 {
01124 NRCODE(r.factorial(n);)
01125 NONRCODE(Scl<T> r; r.factorial(n); return r;)
01126 }
01127
01128
01129 inline Scl<T>
01130 BigIntPow (unsigned long base, unsigned long exp) NRVAL(r)
01131 {
01132 NRCODE(r.pow(base, exp);)
01133 NONRCODE(Scl<T> r; r.pow(base, exp); return r;)
01134 }
01135
01136 #undef NRVAL
01137 #undef NRCODE
01138 #undef NONRCODE
01139
01140 __END_NAMESPACE_SYNAPS
01141
01142
01143 #endif
01144