37 class Rational::Impl {
40 void canonicalize() { mpq_canonicalize(d_n); }
43 Impl() { mpq_init(d_n); }
45 Impl(
const Impl &x) { mpq_init(d_n); mpq_set(d_n, x.d_n); }
53 Impl(mpz_t n, mpz_t d) {
55 mpq_set_num(d_n, n); mpq_set_den(d_n, d);
65 Impl(
long int n,
long int d);
67 Impl(
unsigned int n,
unsigned int d,
unsigned int );
69 Impl(
const string &n,
int base);
71 Impl(
const string &n,
const string& d,
int base);
73 virtual ~Impl() { mpq_clear(d_n); }
76 Impl& operator=(
const Impl& x) {
77 if(
this == &x)
return *
this;
84 return Impl(mpq_numref(const_cast<Impl*>(
this)->d_n));
88 return Impl(mpq_denref(const_cast<Impl*>(
this)->d_n));
93 static Impl
min((
int)INT_MIN, 1),
max((
int)INT_MAX, 1);
95 "Rational::getInt(): Arithmetic overflow for "
97 return mpz_get_si(mpq_numref(d_n));
100 unsigned int getUnsigned()
const {
102 static Impl
min(0, 1, 0),
max(UINT_MAX, 1, 0);
104 "Rational::getUnsigned(): Arithmetic overflow for "
106 return mpz_get_ui(mpq_numref(d_n));
109 Unsigned getUnsignedMP()
const;
119 bool isInteger()
const;
122 friend bool operator==(
const Impl& x,
const Impl& y) {
123 return mpq_equal(x.d_n, y.d_n);
127 friend bool operator!=(
const Impl& x,
const Impl& y) {
128 return !mpq_equal(x.d_n, y.d_n);
131 friend bool operator<(
const Impl& x,
const Impl& y) {
132 return mpq_cmp(x.d_n, y.d_n) < 0;
135 friend bool operator<=(
const Impl& x,
const Impl& y) {
136 return mpq_cmp(x.d_n, y.d_n) <= 0;
139 friend bool operator>(
const Impl& x,
const Impl& y) {
140 return mpq_cmp(x.d_n, y.d_n) > 0;
143 friend bool operator>=(
const Impl& x,
const Impl& y) {
144 return mpq_cmp(x.d_n, y.d_n) >= 0;
148 friend Impl
operator+(
const Impl& x,
const Impl& y) {
150 mpq_add(res.d_n, x.d_n, y.d_n);
155 friend Impl
operator-(
const Impl& x,
const Impl& y) {
157 mpq_sub(res.d_n, x.d_n, y.d_n);
162 friend Impl
operator*(
const Impl& x,
const Impl& y) {
164 mpq_mul(res.d_n, x.d_n, y.d_n);
169 friend Impl
operator/(
const Impl& x,
const Impl& y) {
171 mpq_div(res.d_n, x.d_n, y.d_n);
175 friend Impl operator%(
const Impl& x,
const Impl& y) {
177 "Impl % Impl: x and y must be integers");
181 mpz_fdiv_r(res, mpq_numref(x.d_n), mpq_numref(y.d_n));
188 friend Impl mod(
const Impl& x,
const Impl& y) {
190 "Rational::Impl::mod(): x="+x.toString()
191 +
", y="+y.toString());
194 mpz_mod(res, mpq_numref(x.d_n), mpq_numref(y.d_n));
200 friend Impl intRoot(
const Impl& x,
unsigned long int y) {
202 "Rational::Impl::intRoot(): x="+x.toString());
205 int exact = mpz_root(res, mpq_numref(x.d_n), y);
214 friend Impl gcd(
const Impl& x,
const Impl& y) {
216 "Rational::Impl::gcd(): x="+x.toString()
217 +
", y="+y.toString());
218 TRACE(
"rational",
"Impl::gcd(", x,
", "+y.toString()+
") {");
221 mpz_gcd(res, mpq_numref(x.d_n), mpq_numref(y.d_n));
224 TRACE(
"rational",
"Impl::gcd => ", r,
"}");
228 friend Impl lcm(
const Impl& x,
const Impl& y) {
230 "Rational::Impl::lcm(): x="+x.toString()
231 +
", y="+y.toString());
234 mpz_lcm(res, mpq_numref(x.d_n), mpq_numref(y.d_n));
241 string toString(
int base = 10)
const {
242 char* str = (
char*)malloc(mpz_sizeinbase(mpq_numref(d_n), base)
243 +mpz_sizeinbase(mpq_denref(d_n), base)+3);
244 mpq_get_str(str, base, d_n);
252 Rational::Impl::Impl(
long int n,
long int d) {
255 mpq_set_si(d_n, n, (
unsigned long int)d);
260 Rational::Impl::Impl(
unsigned int n,
unsigned int d,
263 mpq_set_ui(d_n, n, (
unsigned long int)d);
268 Rational::Impl::Impl(
const string &n,
int base) {
270 mpq_set_str(d_n, n.c_str(), base);
275 Rational::Impl::Impl(
const string &n,
const string& d,
int base) {
277 mpq_set_str(d_n, (n+
"/"+d).c_str(), base);
283 mpq_neg(res.d_n, d_n);
287 Rational::Impl Rational::Impl::floor()
const {
290 mpz_fdiv_q(res, mpq_numref(d_n), mpq_denref(d_n));
296 Rational::Impl Rational::Impl::ceil()
const {
299 mpz_cdiv_q(res, mpq_numref(d_n), mpq_denref(d_n));
305 bool Rational::Impl::isInteger()
const {
306 bool res(mpz_cmp_ui(mpq_denref(d_n), 1) == 0);
307 TRACE(
"rational",
"Impl::isInteger(", *
this,
308 ") => "+
string(res?
"true" :
"false"));
314 #ifdef _DEBUG_RATIONAL_
315 int &num_created = getCreated();
321 Rational::Rational(
const Rational &n) : d_n(new Impl(*n.d_n)) {
322 #ifdef _DEBUG_RATIONAL_
323 int &num_created = getCreated();
329 Rational::Rational(
const Unsigned& n): d_n(new Impl(n.toString(), 10)) {
330 #ifdef _DEBUG_RATIONAL_
331 int &num_created = getCreated();
337 Rational::Rational(
const Impl& t): d_n(new Impl(t)) {
338 #ifdef _DEBUG_RATIONAL_
339 int &num_created = getCreated();
344 Rational::Rational(
int n,
int d): d_n(new Impl(n, d)) {
345 #ifdef _DEBUG_RATIONAL_
346 int &num_created = getCreated();
352 Rational::Rational(
const char* n,
int base)
353 : d_n(new Impl(string(n), base)) {
354 #ifdef _DEBUG_RATIONAL_
355 int &num_created = getCreated();
360 Rational::Rational(
const string& n,
int base)
361 : d_n(new Impl(n, base)) {
362 #ifdef _DEBUG_RATIONAL_
363 int &num_created = getCreated();
368 Rational::Rational(
const char* n,
const char* d,
int base)
369 : d_n(new Impl(string(n), string(d), base)) {
370 #ifdef _DEBUG_RATIONAL_
371 int &num_created = getCreated();
376 Rational::Rational(
const string& n,
const string& d,
int base)
377 : d_n(new Impl(n, d, base)) {
378 #ifdef _DEBUG_RATIONAL_
379 int &num_created = getCreated();
385 Rational::~Rational() {
386 #ifdef _DEBUG_RATIONAL_
387 int &num_deleted = getDeleted();
395 Rational Rational::getNumerator()
const
396 {
return Rational(d_n->getNum()); }
397 Rational Rational::getDenominator()
const
398 {
return Rational(d_n->getDen()); }
400 bool Rational::isInteger()
const {
return d_n->isInteger(); }
403 Rational& Rational::operator=(
const Rational& n) {
404 if(
this == &n)
return *
this;
406 d_n =
new Impl(*n.d_n);
410 ostream &
operator<<(ostream &os,
const Rational &n) {
411 return(os << n.toString());
415 std::ostream&
operator<<(std::ostream& os,
const Rational::Impl& n) {
416 return os << n.toString();
422 static void checkInt(
const Rational& n,
const string& funName) {
423 TRACE(
"rational",
"checkInt(", n,
")");
425 "CVC3::Rational::" + funName
426 +
": argument is not an integer: " + n.toString());
433 Rational gcd(
const Rational &x,
const Rational &y) {
434 checkInt(x,
"gcd(*x*,y)");
435 checkInt(y,
"gcd(x,*y*)");
436 return Rational(gcd(*x.d_n, *y.d_n));
439 Rational gcd(
const vector<Rational> &v) {
440 Rational::Impl g(1,1), zero;
442 checkInt(v[0],
"gcd(vector<Rational>[0])");
445 for(
size_t i=1; i<v.size(); i++) {
446 checkInt(v[i],
"gcd(vector<Rational>)");
449 else if(*(v[i].d_n) != zero)
450 g = gcd(g, *(v[i].d_n));
455 Rational lcm(
const Rational &x,
const Rational &y) {
456 checkInt(x,
"lcm(*x*,y)");
457 checkInt(y,
"lcm(x,*y*)");
458 return Rational(lcm(*x.d_n, *y.d_n));
461 Rational lcm(
const vector<Rational> &v) {
462 Rational::Impl g(1,1), zero;
463 for(
size_t i=0; i<v.size(); i++) {
464 checkInt(v[i],
"lcm(vector<Rational>)");
465 if(*v[i].d_n != zero)
466 g = lcm(g, *v[i].d_n);
471 Rational
abs(
const Rational &x) {
476 Rational floor(
const Rational &x) {
477 return Rational(x.d_n->floor());
480 Rational ceil(
const Rational &x) {
481 return Rational(x.d_n->ceil());
484 Rational mod(
const Rational &x,
const Rational &y) {
485 checkInt(x,
"mod(*x*,y)");
486 checkInt(y,
"mod(x,*y*)");
487 return(Rational(mod(*x.d_n, *y.d_n)));
490 Rational intRoot(
const Rational& base,
unsigned long int n) {
491 checkInt(base,
"intRoot(*x*,y)");
492 return Rational(intRoot(*base.d_n, n));
495 string Rational::toString(
int base)
const {
496 return(d_n->toString(base));
499 size_t Rational::hash()
const {
501 return h(toString().c_str());
504 void Rational::print()
const {
505 cout << (*this) <<
endl;
510 return Rational(-(*d_n));
513 Rational &Rational::operator+=(
const Rational &n2) {
514 *
this = (*this) + n2;
518 Rational &Rational::operator-=(
const Rational &n2) {
519 *
this = (*this) - n2;
523 Rational &Rational::operator*=(
const Rational &n2) {
524 *
this = (*this) * n2;
528 Rational &Rational::operator/=(
const Rational &n2) {
529 *
this = (*this) / n2;
533 int Rational::getInt()
const {
534 checkInt(*
this,
"getInt()");
535 return d_n->getInt();
538 unsigned int Rational::getUnsigned()
const {
539 checkInt(*
this,
"getUnsigned()");
540 return d_n->getUnsigned();
543 Unsigned Rational::getUnsignedMP()
const {
544 checkInt(*
this,
"getUnsignedMP()");
545 return d_n->getUnsignedMP();
548 #ifdef _DEBUG_RATIONAL_
549 void Rational::printStats() {
550 int &num_created = getCreated();
551 int &num_deleted = getDeleted();
552 if(num_created % 1000 == 0 || num_deleted % 1000 == 0) {
553 std::cerr <<
"Rational(" << *d_n <<
"): created " << num_created
554 <<
", deleted " << num_deleted
555 <<
", currently alive " << num_created-num_deleted
561 bool operator==(
const Rational &n1,
const Rational &n2) {
562 return(*n1.d_n == *n2.d_n);
565 bool operator<(
const Rational &n1,
const Rational &n2) {
566 return(*n1.d_n < *n2.d_n);
569 bool operator<=(
const Rational &n1,
const Rational &n2) {
570 return(*n1.d_n <= *n2.d_n);
573 bool operator>(
const Rational &n1,
const Rational &n2) {
574 return(*n1.d_n > *n2.d_n);
577 bool operator>=(
const Rational &n1,
const Rational &n2) {
578 return(*n1.d_n >= *n2.d_n);
581 bool operator!=(
const Rational &n1,
const Rational &n2) {
582 return(*n1.d_n != *n2.d_n);
585 Rational
operator+(
const Rational &n1,
const Rational &n2) {
586 return Rational((*n1.d_n) + (*n2.d_n));
589 Rational
operator-(
const Rational &n1,
const Rational &n2) {
590 return Rational((*n1.d_n) - (*n2.d_n));
593 Rational
operator*(
const Rational &n1,
const Rational &n2) {
594 return Rational((*n1.d_n) * (*n2.d_n));
597 Rational
operator/(
const Rational &n1,
const Rational &n2) {
598 return Rational((*n1.d_n) / (*n2.d_n));
601 Rational operator%(
const Rational &n1,
const Rational &n2) {
602 return Rational((*n1.d_n) % (*n2.d_n));
606 class Unsigned::Impl {
610 Impl() { mpz_init(d_n); }
612 Impl(
const Impl &x) { mpz_init(d_n); mpz_set(d_n, x.d_n); }
614 Impl(
const mpz_t n) {
619 Impl(
unsigned int n);
621 Impl(
const string &n,
int base);
623 virtual ~Impl() { mpz_clear(d_n); }
626 Impl& operator=(
const Impl& x) {
627 if(
this == &x)
return *
this;
634 static Impl
max((
int)INT_MAX);
636 "Unsigned::getInt(): Arithmetic overflow for "
638 return mpz_get_si(d_n);
641 unsigned long getUnsigned()
const {
643 static Impl
max(UINT_MAX);
645 "Unsigned::getUnsigned(): Arithmetic overflow for "
647 return mpz_get_ui(d_n);
654 friend bool operator==(
const Impl& x,
const Impl& y) {
655 return mpz_cmp(x.d_n, y.d_n) == 0;
659 friend bool operator!=(
const Impl& x,
const Impl& y) {
660 return mpz_cmp(x.d_n, y.d_n) != 0;
663 friend bool operator<(
const Impl& x,
const Impl& y) {
664 return mpz_cmp(x.d_n, y.d_n) < 0;
667 friend bool operator<=(
const Impl& x,
const Impl& y) {
668 return mpz_cmp(x.d_n, y.d_n) <= 0;
671 friend bool operator>(
const Impl& x,
const Impl& y) {
672 return mpz_cmp(x.d_n, y.d_n) > 0;
675 friend bool operator>=(
const Impl& x,
const Impl& y) {
676 return mpz_cmp(x.d_n, y.d_n) >= 0;
680 friend Impl
operator+(
const Impl& x,
const Impl& y) {
682 mpz_add(res.d_n, x.d_n, y.d_n);
687 friend Impl
operator-(
const Impl& x,
const Impl& y) {
689 mpz_sub(res.d_n, x.d_n, y.d_n);
694 friend Impl
operator*(
const Impl& x,
const Impl& y) {
696 mpz_mul(res.d_n, x.d_n, y.d_n);
701 friend Impl
operator/(
const Impl& x,
const Impl& y) {
703 mpz_div(res.d_n, x.d_n, y.d_n);
707 friend Impl operator%(
const Impl& x,
const Impl& y) {
711 mpz_fdiv_r(res, x.d_n, y.d_n);
717 friend Impl
operator<<(
const Impl& x,
unsigned y) {
720 mpz_mul_2exp (res, x.d_n, y);
726 friend Impl operator&(
const Impl& x,
const Impl& y) {
729 mpz_and (res, x.d_n, y.d_n);
736 friend Impl mod(
const Impl& x,
const Impl& y) {
739 mpz_mod(res, x.d_n, y.d_n);
745 friend Impl intRoot(
const Impl& x,
unsigned long int y) {
748 int exact = mpz_root(res, x.d_n, y);
757 friend Impl gcd(
const Impl& x,
const Impl& y) {
760 mpz_gcd(res, x.d_n, y.d_n);
766 friend Impl lcm(
const Impl& x,
const Impl& y) {
769 mpz_lcm(res, x.d_n, y.d_n);
776 string toString(
int base = 10)
const {
777 char* str = (
char*)malloc(mpz_sizeinbase(d_n, base)+2);
778 mpz_get_str(str, base, d_n);
785 friend ostream&
operator<<(ostream& os,
const Unsigned::Impl& n) {
786 return os << n.toString();
792 Unsigned::Impl::Impl(
unsigned int n) {
798 Unsigned::Impl::Impl(
const string &n,
int base) {
800 mpz_set_str(d_n, n.c_str(), base);
805 mpz_neg(res.d_n, d_n);
810 Unsigned::Unsigned() : d_n(new Impl) { }
812 Unsigned::Unsigned(
const Unsigned &n) : d_n(new Impl(*n.d_n)) { }
814 Unsigned::Unsigned(
int n) : d_n(new Impl((unsigned)n)) { }
816 Unsigned::Unsigned(
unsigned n) : d_n(new Impl(n)) { }
818 Unsigned::Unsigned(
const Impl& t): d_n(new Impl(t)) { }
820 Unsigned::Unsigned(
const char* n,
int base)
821 : d_n(new Impl(string(n), base)) { }
822 Unsigned::Unsigned(
const string& n,
int base)
823 : d_n(new Impl(n, base)) { }
825 Unsigned::~Unsigned() {
830 Unsigned& Unsigned::operator=(
const Unsigned& n) {
831 if(
this == &n)
return *
this;
833 d_n =
new Impl(*n.d_n);
837 ostream &
operator<<(ostream &os,
const Unsigned &n) {
838 return(os << n.toString());
848 Unsigned gcd(
const Unsigned &x,
const Unsigned &y) {
849 return Unsigned(gcd(*x.d_n, *y.d_n));
852 Unsigned gcd(
const vector<Unsigned> &v) {
853 Unsigned::Impl g(1), zero;
857 for(
size_t i=1; i<v.size(); i++) {
860 else if(*(v[i].d_n) != zero)
861 g = gcd(g, *(v[i].d_n));
866 Unsigned lcm(
const Unsigned &x,
const Unsigned &y) {
867 return Unsigned(lcm(*x.d_n, *y.d_n));
870 Unsigned lcm(
const vector<Unsigned> &v) {
871 Unsigned::Impl g(1), zero;
872 for(
size_t i=0; i<v.size(); i++) {
873 if(*v[i].d_n != zero)
874 g = lcm(g, *v[i].d_n);
879 Unsigned mod(
const Unsigned &x,
const Unsigned &y) {
880 return(Unsigned(mod(*x.d_n, *y.d_n)));
883 Unsigned intRoot(
const Unsigned& base,
unsigned long int n) {
884 return Unsigned(intRoot(*base.d_n, n));
887 string Unsigned::toString(
int base)
const {
888 return(d_n->toString(base));
891 size_t Unsigned::hash()
const {
893 return h(toString().c_str());
896 void Unsigned::print()
const {
897 cout << (*this) <<
endl;
900 Unsigned &Unsigned::operator+=(
const Unsigned &n2) {
901 *
this = (*this) + n2;
905 Unsigned &Unsigned::operator-=(
const Unsigned &n2) {
906 *
this = (*this) - n2;
910 Unsigned &Unsigned::operator*=(
const Unsigned &n2) {
911 *
this = (*this) * n2;
915 Unsigned &Unsigned::operator/=(
const Unsigned &n2) {
916 *
this = (*this) / n2;
920 unsigned long Unsigned::getUnsigned()
const {
921 return d_n->getUnsigned();
924 bool operator==(
const Unsigned &n1,
const Unsigned &n2) {
925 return(*n1.d_n == *n2.d_n);
928 bool operator<(
const Unsigned &n1,
const Unsigned &n2) {
929 return(*n1.d_n < *n2.d_n);
932 bool operator<=(
const Unsigned &n1,
const Unsigned &n2) {
933 return(*n1.d_n <= *n2.d_n);
936 bool operator>(
const Unsigned &n1,
const Unsigned &n2) {
937 return(*n1.d_n > *n2.d_n);
940 bool operator>=(
const Unsigned &n1,
const Unsigned &n2) {
941 return(*n1.d_n >= *n2.d_n);
944 bool operator!=(
const Unsigned &n1,
const Unsigned &n2) {
945 return(*n1.d_n != *n2.d_n);
948 Unsigned
operator+(
const Unsigned &n1,
const Unsigned &n2) {
949 return Unsigned((*n1.d_n) + (*n2.d_n));
952 Unsigned
operator-(
const Unsigned &n1,
const Unsigned &n2) {
953 return Unsigned((*n1.d_n) - (*n2.d_n));
956 Unsigned
operator*(
const Unsigned &n1,
const Unsigned &n2) {
957 return Unsigned((*n1.d_n) * (*n2.d_n));
960 Unsigned
operator/(
const Unsigned &n1,
const Unsigned &n2) {
961 return Unsigned((*n1.d_n) / (*n2.d_n));
964 Unsigned operator%(
const Unsigned &n1,
const Unsigned &n2) {
965 return Unsigned((*n1.d_n) % (*n2.d_n));
968 Unsigned
operator<<(
const Unsigned &n1,
unsigned n2) {
969 return Unsigned((*n1.d_n) << n2);
972 Unsigned operator&(
const Unsigned &n1,
const Unsigned &n2) {
973 return Unsigned((*n1.d_n) & (*n2.d_n));
976 Unsigned Rational::Impl::getUnsignedMP()
const {
977 return Unsigned(Unsigned::Impl(mpq_numref(d_n)));