fork download

copy

#include <iostream>
#include <cstdlib>
//#include <stdlib.h>
#include <cstdint>
#include <cassert>
#include <string>
 
#define ID_GLOBAL 1111
#define ID_MPZCLASS 2222
 
struct supernode {
  int id;
  unsigned int size;
  void *data;
  int mark;
  struct supernode *next;
  struct supernode *before;
};
 
static struct supernode *superrootS = NULL;
 
#define N 4
void xmallocdump(void)
{
  int i;
  unsigned char c;
  struct supernode *p;
  if (superrootS == NULL) {
    fprintf(stderr, "xmallocdump(): root is NULL.\n");
  } else {
    p = superrootS;
    do {
      if (p->mark == 0) {
        fprintf(stderr, "Memory Leak <%p %p %p(%d):%d>", (void *)p, (void *)p->next, p->data, p->size, p->id);
        fflush(stderr);
        for (i = 0; i < N; i++) {
          c = *(unsigned char *)((char *)(p->data) + i);
          printf("%02x(%c) ", c , (isprint(c)) ? c : '.');
        }
        putchar('\n');
        fflush(stderr);
      }
      p = p->next;
    } while (p != superrootS);
  }
}
 
void *xmalloc(unsigned int n, int id)
{
  unsigned int i;
  struct supernode *p;
  rand();
  if ((p = (struct supernode *)malloc(sizeof(struct supernode))) == NULL) {
    fprintf(stderr, "xmalloc(): cannot malloc() in xmalloc()\n");
    abort();
  }
  if (superrootS == NULL) {
    superrootS = p;
    p->size = n;
    p->next = p;
    p->before = p;
    p->mark = 0;
  } else {
    p->size = n;
    p->next = superrootS->next;
    p->before = superrootS;
    superrootS->next = p;
    p->next->before = p;
    p->mark = 0;
  }
  if ((p->data = (void *)malloc(n)) == NULL) {
    fprintf(stderr, "xmalloc(): cannot malloc() in malloc()\n");
    abort();
  }
  for (i = 0; i < n; i++)
    *(char *)((char *)(p->data) + i) = (char)(rand() & 0xff);
  p->id = id;
//  printf("xmalloc():malloc id = %d(%p)\n", p->id, p->data);
  return p->data;
}
 
void xfree(void *p, int id)
{
  unsigned int flag, i;
  struct supernode *q;
//  printf("xfree():free id = %d(%p)\n", id, p);
  if (p == NULL)
    return;
  if (superrootS == NULL) {
    fprintf(stderr, "xfree(): root is null.\n");
    abort();
  }
  rand();
  flag = 0;
  q = superrootS;
  for (;;) {
    if (q->data == p) {
      if (q->id != id) {
        fprintf(stderr, "xfree(): bad ID. expected %d, but %d\n", q->id, id);
      }
      if (q->next == q) {
        for (i = 0; i < q->size; i++)
          *(char *)((char *)(q->data) + i) = (char)(rand() & 0xff);
        free(q->data);
        free(q);
        flag = 1;
        superrootS = NULL;
        break;
      } else {
        q->before->next = q->next;
        q->next->before = q->before;
        if (q == superrootS)
          superrootS = q->next;
        for (i = 0; i < q->size; i++)
          *(char *)((char *)(q->data) + i) = (char)(rand() & 0xff);
        free(q->data);
        free(q);
        flag = 1;
        break;
      }
    }
    if (q->next == superrootS)
      break;
    q = q->next;
  }
  if (flag != 1) {
    fprintf(stderr, "xfree(): cannot xfree(), no data.(id = %d, %p)\n", id, p);
    abort();
  }
}
 
void xmalloccancel() {
  if (superrootS != 0) {
    struct supernode *p = superrootS;
    do {
      p->mark = 1;
      p = p->next;
    } while (p != superrootS);
  }
}
 
void *operator new(size_t size) {
//  printf("new: GLOBAL size = %zu\n", size);
  return xmalloc(size, ID_GLOBAL);
}
void operator delete(void *p) noexcept {
//  printf("delete: GLOBAL\n");
  xfree(p, ID_GLOBAL);
}
 
typedef int64_t CONTAINER;
unsigned int BIT = 3; /* BIT <= 64bit - 2bit = 62bit */
 
CONTAINER CMASK = 1ULL << BIT;
CONTAINER BMASK = CMASK - 1;
 
namespace QZ {
  class mpz_base_class {
 
  private:
    unsigned int n;
    CONTAINER *b;
 
  private:
    static void LeftShift(mpz_base_class &a);
    static void RightShift(mpz_base_class &a, int &lsb_out);
    static void LeftShift2(int &msb, mpz_base_class &a);
    static void LeftShift3(mpz_base_class &a, int msb);
 
  protected:
    static bool iszero(mpz_base_class const &n);
 
  public:
    mpz_base_class(); //
    virtual ~mpz_base_class();
    mpz_base_class(const signed long c);
    mpz_base_class(mpz_base_class const &ob);
    mpz_base_class &operator=(mpz_base_class const &ob);
 
    friend bool operator==(mpz_base_class const &a, mpz_base_class const &b);
    friend bool operator!=(mpz_base_class const &a, mpz_base_class const &b) { return !(a == b); }
 
    friend std::ostream &operator<<(std::ostream &stream, mpz_base_class c);
 
    friend mpz_base_class operator+(mpz_base_class const &a, mpz_base_class const &b);
    friend mpz_base_class operator-(mpz_base_class const &a, mpz_base_class const &b);
 
    friend bool operator<(mpz_base_class const &a, mpz_base_class const &b);
    friend bool operator<=(mpz_base_class const &a, mpz_base_class const &b) { return (a < b) ? true : (a == b) ? true : false; }
    friend bool operator>(mpz_base_class const &a, mpz_base_class const &b) { return (a < b) ? false : (a == b) ? false : true; }
    friend bool operator>=(mpz_base_class const &a, mpz_base_class const &b) { return (a < b) ? false : (a == b) ? true : true; }
 
    friend mpz_base_class operator*(mpz_base_class const &a, mpz_base_class const &b);
    friend void div2(mpz_base_class const &a, mpz_base_class const &b, mpz_base_class &q, mpz_base_class &r);
    friend mpz_base_class operator/(mpz_base_class const &a, mpz_base_class const &b) { mpz_base_class q, r; div2(a, b, q, r); return q; }
    friend mpz_base_class operator%(mpz_base_class const &a, mpz_base_class const &b) { mpz_base_class q, r; div2(a, b, q, r); return r; }
 
    bool testBit(int n);
    mpz_base_class operator>>(int n) { int dmy; mpz_base_class r = *this; for (int i = 0; i < n; i++) RightShift(r, dmy); return r; }
    mpz_base_class operator<<(int n) { mpz_base_class r = *this; for (int i = 0; i < n; i++) LeftShift(r); return r; }
    int bitLength();
 
    unsigned int get_mpzclass_n() { return this->n; }
    CONTAINER *get_mpzclass_b() { return this->b; }
 
    virtual void dump() const {
      std::cout << "n = " << this->n << ": ";
      for (unsigned int i = 0; i < this->n; i++)
        std::cout << i << ":" << this->b[i] << ",";
      std::cout << std::endl;
    }
 
    void test42() {
      // *this == 4 + 256;
      this->b[2] = 0;
    }
  };
 
  class mpz_class : public mpz_base_class {
  private:
    bool negative;
 
  public:
    mpz_class();
    ~mpz_class();
    mpz_class(const signed long c);
    mpz_class(mpz_class const &ob);
    mpz_class &operator=(mpz_class const &ob);
    mpz_class &operator=(mpz_base_class const &ob);
 
    friend bool operator==(mpz_class const &a, mpz_class const &b);
    friend bool operator!=(mpz_class const &a, mpz_class const &b) { return !(a == b); }
 
    friend std::ostream &operator<<(std::ostream &stream, mpz_class c);
 
    friend mpz_class operator-(mpz_class const &a);
 
    friend bool operator<(mpz_class const &a, mpz_class const &b);
    friend bool operator<=(mpz_class const &a, mpz_class const &b) { return (a < b) ? true : (a == b) ? true : false; }
    friend bool operator>(mpz_class const &a, mpz_class const &b) { return (a < b) ? false : (a == b) ? false : true; }
    friend bool operator>=(mpz_class const &a, mpz_class const &b) { return (a < b) ? false : (a == b) ? true : true; }
 
    friend mpz_class operator+(mpz_class const &a, mpz_class const &b);
    friend mpz_class operator-(mpz_class const &a, mpz_class const &b);
 
    friend mpz_class operator*(mpz_class const &a, mpz_class const &b);
    friend mpz_class operator/(mpz_class const &a, mpz_class const &b);
    friend mpz_class operator%(mpz_class const &a, mpz_class const &b);
 
    mpz_class &operator+=(mpz_class const &n) { *this = *this + n; return *this; }
    mpz_class &operator-=(mpz_class const &n) { *this = *this - n; return *this; }
    mpz_class &operator*=(mpz_class const &n) { *this = *this * n; return *this; }
    mpz_class &operator/=(mpz_class const &n) { *this = *this / n; return *this; }
    mpz_class &operator%=(mpz_class const &n) { *this = *this % n; return *this; }
 
    mpz_class operator>>(int n) { mpz_class r; r = this->mpz_base_class::operator>>(n); return r; }
    mpz_class operator<<(int n) { mpz_class r; r = this->mpz_base_class::operator<<(n); return r; }
 
    bool get_mpzclass_negative() { return this->negative; }
 
    virtual void dump() const {
      mpz_base_class::dump();
      std::cout << "sign = " << this->negative << std::endl;
    }
  };
 
  mpz_base_class::mpz_base_class() {
//    std::cout << "mpz_base_class constructor1" << std::endl;
    this->n = 0;
    this->b = 0;
  }  
  mpz_base_class::~mpz_base_class() {
//    std::cout << "mpz_base_class destructor" << std::endl;
    if (this->b) delete [] this->b;
    this->n = 0;
    this->b = 0;
  }
  mpz_base_class::mpz_base_class(const signed long c) {
//    std::cout << "mpz_base_class constructor2" << std::endl;
    signed long cc;
    cc = c;
    if (c == 0) {
      this->n = 1;
      this->b = new CONTAINER [1];
      this->b[0] = 0;
      return;
    }
    if (c < 0) {
      cc = -c; /* for mpz_class not for mpz_base_class */
    }
    assert(cc > 0);
 
    CONTAINER *newbody;
    unsigned int i, j, r, pos;
 
    this->b = 0;
    this->n = 0;
 
    while (cc > 0) {
      r = 0;
      pos = 1;
      for (i = 0; i < BIT; i++) {
        if ((cc & 1) != 0) {
          r = (r | pos);
        } else {
        }
        pos = pos * 2;
        cc = cc / 2;
      }
      newbody = new CONTAINER [this->n + 1];
      for (j = 0; j < this->n; j++)
        newbody[j] = this->b[j];
      newbody[j] = r;
      delete [] this->b;
      this->b = newbody;
      this->n++;
    }
    assert(this->n != 0);
  }
 
  mpz_base_class::mpz_base_class(const mpz_base_class &ob) {
//    std::cout << "mpz_base_class constructor3" << std::endl;
    this->n = ob.n;
    if (ob.n == 0) {
      this->b = 0;
    } else {
      this->b = new CONTAINER [ob.n];
      for (unsigned int i = 0; i < ob.n; i++)
        this->b[i] = ob.b[i];
    }
    assert((this->n == 0 && this->b == 0) || (this->n > 0 && this->b != 0));
  }
 
  mpz_base_class &mpz_base_class::operator=(const mpz_base_class &ob) {
//    std::cout << "mpz_base_class operator=" << std::endl;
    CONTAINER *org_b = this->b; // for checking self-assignment
    this->n = ob.n;
    if (ob.n == 0) {
      this->b = 0;
      delete [] org_b;
    } else {
      this->b = new CONTAINER [ob.n];
      for (unsigned int i = 0; i < ob.n; i++)
        this->b[i] = ob.b[i];
      delete [] org_b;
    }
    assert((this->n == 0 && this->b == 0) || (this->n > 0 && this->b != 0));
    return *this;
  }
 
  bool operator==(mpz_base_class const &a, mpz_base_class const &b) {
//    std::cout << "mpz_base_class operator==" << std::endl;
    unsigned int i, less;
    bool isEqual = true;
 
    if (a.n < b.n)
      less = a.n;
    else
      less = b.n;
    for (i = 0; i < less; i++)
      if (a.b[i] != b.b[i]) {
        isEqual = false;
        goto label;
      }
    if (a.n < b.n) {
      for (; i < b.n; i++)
        if (b.b[i] != 0) {
          isEqual = false;
          goto label;
        }
    } else {
      for (; i < a.n; i++)
        if (a.b[i] != 0) { // be carefull! not b.b[] but a.b[]
          isEqual = false;
          goto label;
        }
    }
  label:
    return isEqual;
  }
 
 
  std::ostream &operator<<(std::ostream &stream, mpz_base_class c) {
//    std::cout << "mpz_base_class operator<<" << std::endl;
    std::basic_string<char> mod10;
    mpz_base_class q, n;
    int mod;
    bool fzero;
 
    fzero = true;
    n = c;
    for(;;) {
      /* div10(n, q, mod); */
      {
        q = n;
        mod = 0;
        for (unsigned int i = 0; i < n.n * BIT; i++) {
          /* shift_div(mod, q); */
          {
            unsigned int cy, i;
 
            cy = 0;
            for (i = 0; i < n.n; i++) {
              q.b[i] = q.b[i] << 1;
              if (cy)
                q.b[i] = q.b[i] | 0x01;
              cy = (q.b[i] >> BIT);
              q.b[i] = q.b[i] & BMASK;
            }
            mod = mod << 1;
            if (cy)
              mod = mod | 0x01;
 
          }
          if (mod >= 10) {
            q.b[0] = q.b[0] | 0x01;
            mod = mod - 10;
          }
        }
      }
      if (mpz_class::iszero(q) && mod == 0)
        break;
      mod10 = (char)('0' + mod) + mod10;
      fzero = false;
      n = q;
    }
 
    if (fzero)
      stream << '0';
    else
      stream << mod10;
    return stream;
  }
 
  mpz_base_class operator+(mpz_base_class const &a, mpz_base_class const &b) {
    mpz_base_class r;
    mpz_base_class const * more_ab;
    unsigned int less_n;
    if (a.n > b.n) {
      r.n = a.n;
      more_ab = &a;
      less_n = b.n;
    } else {
      r.n = b.n;
      more_ab = &b;
      less_n = a.n;
    }
    r.b = new CONTAINER [r.n];
    unsigned int i, carry = 0;
    for (i = 0; i < less_n; i++) {
      CONTAINER s = a.b[i] + b.b[i] + carry;
      if (s >= CMASK) {
        carry = 1;
        r.b[i] = (s  & BMASK);
      } else {
        carry = 0;
        r.b[i] = s; /* need */
      }
    }
    for (;i < r.n; i++) {
      CONTAINER s = more_ab->b[i] + carry;
      if (s >= CMASK) {
        carry = 1;
        r.b[i] = (s  & BMASK); /* need */
      } else {
        carry = 0;
        r.b[i] = (s  & BMASK); /* need */ /* do not to insert break keyword.*/
      }
    }
    if (carry) {
      CONTAINER *new_body = new CONTAINER [r.n + 1];
      for (i = 0; i < r.n; i++)
        new_body[i] = r.b[i];
      new_body[i] = carry;
      delete [] r.b;
      r.b = new_body;
      // r.b[r.n] = 1; /* NOT need */
      r.n++;
    }
    return r;
  }
 
 
  bool mpz_base_class::iszero(mpz_base_class const &n) {
    bool isZero = true;
    for (unsigned int i = 0; i < n.n; i++)
      if (n.b[i] != 0) {
        isZero = false;
        break;
      }
    return isZero;
  }
 
  mpz_base_class operator-(mpz_base_class const &a, mpz_base_class const &b) {
    int vCount, moreCount, i;
    CONTAINER diff;
    int borrowR = 0;
    bool flagMore, flagLess;
    mpz_base_class r;
    flagMore = false;
    flagLess = false;
    moreCount = a.n;
    vCount = a.n;
    r = a;
    if (a.n > b.n) {
      flagMore = true;
      vCount = b.n;
      moreCount = a.n;
      r = a;
    }
    if (a.n < b.n) {
      flagLess = true;
      vCount = a.n;  
      moreCount = b.n;
      r = b;
    }
 
    borrowR = 0;
    for (i = 0; i < vCount; i++) {
      diff = a.b[i] - b.b[i] - borrowR;
      if (diff < 0) {
        borrowR = 1;
        r.b[i] = diff + CMASK;
      } else {
        borrowR = 0;
        r.b[i] = diff;
      }
    }
    if (flagMore) {
      for (;i < moreCount; i++) {
        diff = a.b[i] - borrowR;
        if (diff < 0) {
          borrowR = 1;
          r.b[i] = diff + CMASK;
        } else {
          borrowR = 0;
          r.b[i] = diff;
        }
      }
    }
    if (flagLess) {
      for (;i < moreCount; i++) {
        if (b.b[i] > 0) {
          borrowR = 1;
        }
      }
    }
    if (borrowR > 0) throw std::underflow_error("negative value.");
    return r;
  }
 
  bool operator<(mpz_base_class const &a, mpz_base_class const &b) { // if a < b then true
    try {
      mpz_base_class r = a - b;
    } catch (std::underflow_error &e) {
      return true;
    }
    return false;
  }
 
  mpz_base_class operator*(mpz_base_class const &a, mpz_base_class const &b) {
    mpz_base_class Rshift = b;
    mpz_base_class Lshift = a;
    mpz_base_class r = 0;
    int lsb;
    while (!mpz_base_class::iszero(Rshift)) {
      mpz_base_class::RightShift(Rshift, lsb);
      if (lsb) {
        r = r + Lshift;
      }
      mpz_base_class::LeftShift(Lshift);
    }
    return r;
  }
 
  void mpz_base_class::LeftShift(mpz_base_class &a) {
    unsigned int i, msb;
    msb = 0;
    for (i = 0; i < a.n; i++) {
      a.b[i] *= 2;
      if (msb > 0)
        a.b[i] = (a.b[i] | 0x01);
 
      if (a.b[i] > BMASK) {
        msb = 1;
        a.b[i] -= CMASK;
      } else {
        msb = 0;
      }
    }
    if (msb > 0) {
      CONTAINER *newbody;
      newbody = new CONTAINER [a.n + 1];
      newbody[a.n] = 1;
      for (unsigned int i = 0; i < a.n; i++) {
        newbody[i] = a.b[i];
      }
      a.n++;
      delete [] a.b;
      a.b = newbody;
    }
  }
 
  void mpz_base_class::RightShift(mpz_base_class &a, int &lsb_out) {
    int i, lsb;
    lsb = 0;
    for (i = a.n - 1; i >= 0; --i) {
      if (lsb > 0)
        a.b[i] = (a.b[i] | CMASK);
 
      if ((a.b[i] & 0x01) > 0)
        lsb = 1;
      else
        lsb = 0;
      a.b[i] /= 2;
    }
    lsb_out = lsb;
    if (a.b[a.n - 1] == 0) {
      CONTAINER *newbody;
      newbody = new CONTAINER [a.n - 1];
      for (unsigned int i = 0; i < a.n - 1; i++)
        newbody[i] = a.b[i];
      a.n--;
      delete [] a.b;
      a.b = newbody;
    }
  }
 
  void mpz_base_class::LeftShift2(int &msb, mpz_base_class &a) {
    unsigned int i, msb_v;
    msb_v = 0;
    for (i = 0; i < a.n; i++) {
      a.b[i] *= 2;
      if (msb_v > 0)
        a.b[i] = (a.b[i] | 0x01);
 
      if (a.b[i] > BMASK) {
        msb_v = 1;
        a.b[i] -= CMASK;
      } else {
        msb_v = 0;
      }
    }
    msb = msb_v;
  }
 
  void mpz_base_class::LeftShift3(mpz_base_class &a, int msb) {
    unsigned int i, msb_v;
    msb_v = msb;
    for (i = 0; i < a.n; i++) {
      a.b[i] *= 2;
      if (msb_v > 0)
        a.b[i] = (a.b[i] | 0x01);
 
      if (a.b[i] > BMASK) {
        msb_v = 1;
        a.b[i] -= CMASK;
      } else {
        msb_v = 0;
      }
    }
    if (msb_v > 0) {
      CONTAINER *newbody;
      newbody = new CONTAINER [a.n + 1];
      newbody[a.n] = 1;
      for (unsigned int i = 0; i < a.n; i++) {
        newbody[i] = a.b[i];
      }
      a.n++;
      delete [] a.b;
      a.b = newbody;
    }
  }
  void div2(mpz_base_class const &a, mpz_base_class const &b, mpz_base_class &q, mpz_base_class &r) {
    if (b == mpz_base_class(0)) {
      std::cout << "null devided." << std::endl;
      return;
    }
 
    /* LeftRest <- LeftShiftBuff */
    mpz_base_class LeftRest(0);
    mpz_base_class LeftShiftBuff = a;
    mpz_base_class Quotient(0);
    int msb, lsb;
    msb = 0;
    int n = a.n * BIT;
    while (n > 0) {
      //    std::cout << "LeftShiftBuff=" << LeftShiftBuff << std::endl;
      //    std::cout << "LeftRest=" << LeftRest << std::endl;
      mpz_base_class::LeftShift2(msb, LeftShiftBuff);
      mpz_base_class::LeftShift3(LeftRest, msb);
      lsb = 0;
      if (b < LeftRest || b == LeftRest) {
        LeftRest = LeftRest - b;
        lsb = 1;
      }
      mpz_base_class::LeftShift3(Quotient, lsb);
      //    std::cout << "Quotient=" << Quotient << std::endl;
      n--;
    }
    q = Quotient;
    r = LeftRest;
  }
 
  bool mpz_base_class::testBit(int n) {
    unsigned int test_byte = n / BIT;
    int test_mask = 1 << (n % BIT);
    if (test_byte >= this->n) return false;
    if ((this->b[test_byte] & test_mask) > 0) return true;
    return false;
  }
 
/*----------------------------------------------*/
  mpz_class::mpz_class() : mpz_base_class() {
//    std::cout << "mpz_class constructor1" << std::endl;
    this->negative = false;
  }
 
  mpz_class::~mpz_class() {
//    std::cout << "mpz_class destructor1" << std::endl;
    this->negative = false;
  }
 
  mpz_class::mpz_class(const signed long c) : mpz_base_class(c) {
//    std::cout << "mpz_class costructor2" << std::endl;
    if (c >= 0) {
      this->negative = false;
    } else {
      this->negative = true;
    }
  }
 
  mpz_class::mpz_class(const mpz_class &ob) : mpz_base_class(ob) {
//    std::cout << "mpz_class constructor3" << std::endl;
    this->negative = ob.negative;
  }
 
  mpz_class &mpz_class::operator=(mpz_class const &ob) {
//    std::cout << "mpz_class operator=(mpz_class&)" << std::endl;
    this->mpz_base_class::operator=(ob);
    this->negative = ob.negative;
    return *this;
  }
 
  mpz_class &mpz_class::operator=(mpz_base_class const &ob) {
//   std::cout << "mpz_class operator=(mpz_base_class&)" << std::endl;
    this->mpz_base_class::operator=(ob);
    this->negative = false;
    return *this;
  }
 
  bool operator==(mpz_class const &a, mpz_class const &b) {
//    std::cout << "mpz_class::operator==" << std::endl;
    if (a.negative == b.negative)
      return operator==((mpz_base_class)a, (mpz_base_class)b);
    return false;
  }
 
  std::ostream &operator<<(std::ostream &stream, mpz_class c) {
    if (c.negative)
      stream << '-';
    return operator<<(stream, (mpz_base_class)c);
  }
 
  mpz_class operator-(mpz_class const &a) {
    mpz_class r = a;
    r.negative = !r.negative;
    return r;
  }
 
  mpz_class operator+(mpz_class const &a, mpz_class const &b) {
    mpz_class r;
    if (!a.negative && !b.negative) {
      r = (mpz_base_class)a + (mpz_base_class)b; /* operator=(mpz_class, mpz_base_class) */
      r.negative = false;
    } else if (a.negative && !b.negative) {
      mpz_class t = -a; assert(t.negative == false);
      if (operator<((mpz_base_class)t, (mpz_base_class)b) == true) { /* t < b */
        r = (mpz_base_class)b - (mpz_base_class)t;
        r.negative = false;
      } else { /* b < t */
        r = (mpz_base_class)t - (mpz_base_class)b;
        r.negative = true;
      }
      if (mpz_base_class::iszero(r))
        r.negative = false;
    } else if (!a.negative && b.negative) {
      mpz_class t = -b; assert(t.negative == false);
      if (operator<((mpz_base_class)t, (mpz_base_class)a) == true) { /* t < a */
        r = (mpz_base_class)a - (mpz_base_class)t;
        r.negative = false;
      } else { /* a < t */
        r = (mpz_base_class)t - (mpz_base_class)a;
        r.negative = true;
      }
      if (mpz_base_class::iszero(r))
        r.negative = false;
    } else if (a.negative && b.negative) {      
      QZ::mpz_class aa = a, bb = b;
      aa = -aa; bb = -bb;
      r = (mpz_base_class)aa + (mpz_base_class)bb;
      r.negative = true;
      if (mpz_base_class::iszero(r))
        r.negative = false;
    }
    return r;
  }
 
  mpz_class operator-(mpz_class const &a, mpz_class const &b) {
    QZ::mpz_class r = -b;
    return a + r;
  }
 
  bool operator<(mpz_class const &a, mpz_class const &b) {
    QZ::mpz_class r = a - b;
    if (r.negative)
      return true;
    return false;
  }
 
  mpz_class operator*(mpz_class const &a, mpz_class const &b) {
    mpz_class x = (a > 0) ? a : -a;
    mpz_class y = (b > 0) ? b : -b;
    assert(x >= 0 && y >= 0);
    mpz_class r;
    r = (mpz_base_class)x * (mpz_base_class)y;
 
    if (a >= 0 && b >= 0)  {
    } else if (a < 0 && b >= 0) {
      r = -r;
    } else if (a >= 0 && b < 0) {
      r = -r;
    } if (a < 0 && b < 0) {
    }
    if (mpz_base_class::iszero(r)) r.negative = false;
    return r;
  }
 
  mpz_class operator/(mpz_class const &a, mpz_class const &b) {
    mpz_class x = (a >= 0) ? a : -a;
    mpz_class y = (b >= 0) ? b : -b;
    mpz_class q, r;
    div2(x, y, q, r);
    if (a >= 0 && b >= 0) {
    } else if (a < 0 && b >= 0) {
      q = -q; r = -r;
      if (mpz_base_class::iszero(q)) q.negative = false;
      if (mpz_base_class::iszero(r)) r.negative = false;
    } else if (a >= 0 && b < 0) {
      q = -q;
      if (mpz_base_class::iszero(q)) q.negative = false;
      if (mpz_base_class::iszero(r)) r.negative = false;
    } else if (a < 0 && b < 0) {
      r = -r;
      if (mpz_base_class::iszero(q)) q.negative = false;
      if (mpz_base_class::iszero(r)) q.negative = false;
    }
    return q;
  }
 
  mpz_class operator%(mpz_class const &a, mpz_class const &b) {
    mpz_class x = (a >= 0) ? a : -a;
    mpz_class y = (b >= 0) ? b : -b;
    mpz_class q, r;
    div2(x, y, q, r);
    if (a >= 0 && b >= 0) {
    } else if (a < 0 && b >= 0) {
      q = -q; r = -r;
      if (mpz_base_class::iszero(q)) q.negative = false;
      if (mpz_base_class::iszero(r)) r.negative = false;
    } else if (a >= 0 && b < 0) {
      q = -q;
      if (mpz_base_class::iszero(q)) q.negative = false;
      if (mpz_base_class::iszero(r)) r.negative = false;
    } else if (a < 0 && b < 0) {
      r = -r;
      if (mpz_base_class::iszero(q)) q.negative = false;
      if (mpz_base_class::iszero(r)) r.negative = false;
    }
    return r;
  }
 
  int mpz_base_class::bitLength() {
    if (this->n == 0)
      return 0;
 
    int n = this->n;
    int i;
    for (i = n - 1; !(b[i] > 0); --i) {}
 
    CONTAINER msb = this->b[i];
 
    int j = 0;
    while (msb > 0) {
      j++;
      msb = msb >> 1;
    }
    return BIT * i + j;
  }
 
} /* namespace QZ */
 
bool test00() {
  std::cout << "test00" << std::endl;
  return true;
}
bool test01() {
  /* constructor1, destructor */
  std::cout << "test01" << std::endl;
  QZ::mpz_base_class a;
  a.dump();
  if (a.get_mpzclass_n() != 0) return false;
  if (a.get_mpzclass_b() != 0) return false;
  return true;
}
 
bool test02() {
  /* constructor2 */
  std::cout << "test02" << std::endl;
  std::cout << "test02:0" << std::endl;
  QZ::mpz_base_class a(0);
  a.dump();
  if (a.get_mpzclass_n() != 1) return false;
  if (*a.get_mpzclass_b() != 0) return false;
 
  std::cout << "test02:1" << std::endl;
  QZ::mpz_base_class b(1);
  b.dump();
  if (b.get_mpzclass_n() != 1) return false;
  if (*b.get_mpzclass_b() != 1) return false;
 
  std::cout << "test02:2" << std::endl;
  QZ::mpz_base_class c(2);
  c.dump();
  if (c.get_mpzclass_n() != 1) return false;
  if (*c.get_mpzclass_b() != 2) return false;
 
  std::cout << "test02:4" << std::endl;
  QZ::mpz_base_class d(4);
  d.dump();
  if (d.get_mpzclass_n() != 1) return false;
  if (*d.get_mpzclass_b() != 4) return false;
 
  std::cout << "test02:8" << std::endl;
  QZ::mpz_base_class e(8);
  e.dump();
  if (e.get_mpzclass_n() != 2) return false;
  if (*e.get_mpzclass_b() != 0) return false;
  if (*(e.get_mpzclass_b() + 1) != 1) return false;
 
  std::cout << "test02:10" << std::endl;
  QZ::mpz_base_class f(10);
  f.dump();
  if (f.get_mpzclass_n() != 2) return false;
  if (*f.get_mpzclass_b() != 2) return false;
  if (*(f.get_mpzclass_b() + 1) != 1) return false;
 
  std::cout << "test02:16" << std::endl;
  QZ::mpz_base_class g(16);
  g.dump();
  if (g.get_mpzclass_n() != 2) return false;
  if (*g.get_mpzclass_b() != 0) return false;
  if (*(g.get_mpzclass_b() + 1) != 2) return false;
 
  std::cout << "test02:32" << std::endl;
  QZ::mpz_base_class h(32);
  h.dump();  
  if (h.get_mpzclass_n() != 2) return false;
  if (*h.get_mpzclass_b() != 0) return false;
  if (*(h.get_mpzclass_b() + 1) != 4) return false;
 
  std::cout << "test02:64" << std::endl;
  QZ::mpz_base_class i(64);
  i.dump();  
  if (i.get_mpzclass_n() != 3) return false;
  if (*i.get_mpzclass_b() != 0) return false;
  if (*(i.get_mpzclass_b() + 1) != 0) return false;
  if (*(i.get_mpzclass_b() + 2) != 1) return false;
  return true;
}
 
bool test03() {
  /* constructor3 */
  std::cout << "test03" << std::endl;
  QZ::mpz_base_class a;
  QZ::mpz_base_class b = a;
  b.dump();
  if (b.get_mpzclass_n() != 0) return false;
  if (b.get_mpzclass_b() != 0) return false;
  QZ::mpz_base_class c = 1;
  QZ::mpz_base_class d = c;
  d.dump();
  if (d.get_mpzclass_n() != 1) return false;
  if (*d.get_mpzclass_b() != 1) return false;
  return true;
}
 
bool test04() {
  /* operator= */
  std::cout << "test04" << std::endl;
  QZ::mpz_base_class a;
  QZ::mpz_base_class b;
  b = a;
  a.dump();
  b.dump();
  if (b.get_mpzclass_n() != 0) return false;
  if (b.get_mpzclass_b() != 0) return false;
  QZ::mpz_base_class c = 1;
  c.dump();
  QZ::mpz_base_class d;
  d = c;
  d.dump();  
  if (d.get_mpzclass_n() != 1) return false;
  if (*d.get_mpzclass_b() != 1) return false;
  return true;
}
 
bool test05() {
  /* operator== */
  std::cout << "test05" << std::endl;
  QZ::mpz_base_class a = 1;
  QZ::mpz_base_class b = 1;
  if (!(a == b)) return false;
  QZ::mpz_base_class x = 100;
  QZ::mpz_base_class y = 100;
  if (!(x == y)) return false;  
  QZ::mpz_base_class u;
  QZ::mpz_base_class v;
  if (!(u == v)) return false;  
  QZ::mpz_base_class w = 0;
  if (!(u == w)) return false;  
  return true;
}
 
bool test06() {
  /* operator==, operator!= */
  std::cout << "test06" << std::endl;
  QZ::mpz_base_class a = 0;
  QZ::mpz_base_class b = 1;
  QZ::mpz_base_class c = 1;
  if (!(a != b)) return false;
  if (b != c) return false;
  if (a == b) return false;
  if (!(b == c)) return false;
  return true;
}
 
bool test07() {
  /* operator+(1)*/
  std::cout << "test07" << std::endl;
  QZ::mpz_base_class a = 1;
  QZ::mpz_base_class b = 2;
  QZ::mpz_base_class c = a + b;
  QZ::mpz_base_class z = 3;
 
  if (!(c == z)) return false;
  a = QZ::mpz_base_class(3);
  b = QZ::mpz_base_class(5);
  c = a + b;
  z = QZ::mpz_base_class(8);
  if (!(c == z)) return false;  
  QZ::mpz_base_class d;
  d.dump();
  c = d + a;
  c.dump();
  if (!(c == a)) return false;
 
  return true;
}
 
int const n = 10;
bool test08() {
  /* operator+(2)*/
  std::cout << "test08" << std::endl;
  int a, b;
  for (a = 0; a <= n; a++)
    for (b = 0; b <= n; b++) {
      QZ::mpz_base_class x(a), y(b);
      QZ::mpz_base_class z1= x +  y;
      QZ::mpz_base_class z2(a + b);
      if (z1 != z2) {
        std::cout << "not equal: z1= "; z1.dump();
        std::cout << "not equal: z2= "; z2.dump();
        return false;
      } else {
        std::cout << "equal: "; z1.dump();
      }
    }
  return true;
}
 
int const n2 = 50;
bool test09() {
  /* operator<<, operator+(3) */
  std::cout << "test09()" << std::endl;
  QZ::mpz_base_class a;
  a.dump();
  std::cout << "a = " << a << std::endl;
  QZ::mpz_base_class b = 0;
  b.dump();
  std::cout << "b = " << b << std::endl;
  QZ::mpz_base_class c = 1;
  c.dump();
  std::cout << "c = " << c << std::endl;
 
  for (int i = 0; i <= n2; i++) {
    for (int j = 0; j <= n2; j++) {
      QZ::mpz_base_class x(i), y(j);
      QZ::mpz_base_class z = x + y;
      std::cout << "i + j = " << i + j << ", z = " << z << " " << std::endl;
      if (z != i + j) {
        std::cout << "NOT EQUAL: x = " << x << ", y = " << y << ", z = " << z << ", i * j = " << i * j << std::endl;
        return false;
      }
    }
    std::cout << std::endl;
  }
  return true;
}
 
int const seed = 31415926;
int const n3 = 10000;
bool test10() {
  std::cout << "test10()" << std::endl;
  srand(seed);
  for (int i = 0; i < n3; i++) {
    int a, b;
    QZ::mpz_base_class x(a = rand() / 2);
    QZ::mpz_base_class y(b = rand() / 2);
    QZ::mpz_base_class z = x + y;
//    std::cout << "i = " << i << std::endl;
    if (z != a + b) {
      std::cout << "NOT EQUAL: x = " << x << ", y = " << y << ", a = " << a << ", b = " << b << ", a + b = " << a + b << std::endl;
      std::cout << "z = " << z << std::endl;
      z.dump();
      return false;
    }
  }
  return true;
}
 
bool test11() {
  /* operator-()i */
  std::cout << "test11()" << std::endl;
  QZ::mpz_base_class a = 5;
  QZ::mpz_base_class b = 3;
  QZ::mpz_base_class c = a - b;
  c.dump();
  if (c.get_mpzclass_n() != 1) return false;
  if (*c.get_mpzclass_b() != 2) return false;
  QZ::mpz_base_class d;
  d.dump();
  QZ::mpz_base_class e = a - d;
  e.dump();
  if (e.get_mpzclass_n() != 1) return false;
  if (*e.get_mpzclass_b() != 5) return false;
 
  return true;
}
 
int const n5 = 10000;
bool test12() {
  /* operator-()ii */
  std::cout << "test12()" << std::endl;
  srand(seed);
  for (int i = 0; i < n5; i++) {
    int a, b, c;
    QZ::mpz_base_class x(a = rand() / 2);
    QZ::mpz_base_class y(b = rand() / 2);
    QZ::mpz_base_class z;
    if (x < y) {
      z = y - x;
      c = b - a;
    } else {
      z = x - y;
      c = a - b;
    }
    if (z != c) {
      std::cout << "i = " << i << std::endl;
      std::cout << "NOT EQUAL: x = " << x << ", y = " << y << ", a = " << a << ", b = " << b << ", |a - b| = " << c << std::endl;
      std::cout << "z = " << z << std::endl;
      z.dump();
      return false;
    }
  }
  return true;
}
 
bool test13() {
  /* operator>(), operator<=(), operator>= */
  std::cout << "test13()" << std::endl;
  QZ::mpz_base_class a = 7;
  QZ::mpz_base_class b = 7;
  QZ::mpz_base_class c = 5;
  QZ::mpz_class d;
  std::cout << "5>7?" << std::endl;
  std::cout << "c > a == " << (c > a) << std::endl;
  if (c > a) return false;
 
  std::cout << "!(5<7)?" << std::endl;
  std::cout << "a > c == " << (a > c) << std::endl;
  if (!(a > c)) return false;
 
  if (b > a) return false;
  if (c >= a) return false;
  if (!(a >= c)) return false;
  if (!(b >= a)) return false;
 
  if (a <= c) return false;
  if (!(c <= a)) return false;
  if (!(b <= a)) return false;
  return true;
}
 
int const n6 = 10;
bool test14() {
  /* operator*()1 */
  std::cout << "test14()" << std::endl;
  QZ::mpz_base_class a = 3;
  QZ::mpz_base_class b = 2;
  QZ::mpz_base_class c = a * b;
  if (c != 6) return false;
  a = QZ::mpz_base_class(6);
  b = QZ::mpz_base_class(0);
  c = a * b;
  if (c != 0) return false;
  QZ::mpz_class d;
  d.dump();
  c = a * b;
  c.dump();
  if (c != 0) return false;
 
  for (int a = 0; a <= n6; a++) {
    for (int b = 0; b <= n6; b++) {
      QZ::mpz_base_class x(a), y(b);
      QZ::mpz_base_class z1 = x * y;
      QZ::mpz_class z2(a * b);
      if (z1 != z2) {
        std::cout << "not equal: z1= "; z1.dump();
        std::cout << "not equal: z2= "; z2.dump();
        return false;
      } else {
        std::cout << z1 << " ";
      }
    }
    std::cout << std::endl;
  }
  return true;
}
 
int const n7 = 1000;
bool test15() {
  /* operator*()2 */
  std::cout << "test15()" << std::endl;
  srand(seed);
  for (int i = 0; i < n7; i++) {
    int a, b;
    QZ::mpz_base_class x(a = (rand() >> 16));
    QZ::mpz_base_class y(b = (rand() >> 16));
//    std::cout << "x = " << x << std::endl;
    QZ::mpz_base_class z = x * y;
 
    if (z != a * b) {
      std::cout << "i = " << i << std::endl;
      std::cout << "NOT EQUAL: x = " << x << ", y = " << y << ", a = " << a << ", b = " << b << ", a * b = " << a * b << std::endl;
      std::cout << "z = " << z << std::endl;
      z.dump();
      return false;
    }
  }
  return true;
}
 
int const n8 = 10;
bool test16() {
  /* operator/() operator%()*/
  std::cout << "test16()" << std::endl;
  QZ::mpz_base_class a = 5;
  QZ::mpz_base_class b = 3;
  QZ::mpz_base_class q , r;
  div2(a, b, q, r);
  if (q != 1) return false;
  if (r != 2) return false;
 
  for (int a = 1; a <= n8; a++) {
    for (int b = 1; b <= n8; b++) {
      QZ::mpz_base_class x(a), y(b);
      QZ::mpz_base_class q1, r1;
      div2(x, y, q1, r1);
      QZ::mpz_base_class q2(a / b);
      QZ::mpz_base_class r2(a % b);
 
      if (q1 != q2) {
        std::cout << "not equal: q1= "; q1.dump();
        std::cout << "not equal: q2= "; q2.dump();
        return false;
      } else if (r1 != r2) {
        std::cout << "not equal: r1= "; r1.dump();
        std::cout << "not equal: r2= "; r2.dump();
        return false;
      } else {
        std::cout << "(" << q1 << "," << r1 << ") ";
      }
    }
    std::cout << std::endl;
  }
  return true;
}
 
int const n9 = 1000;
bool test17() {
  //operator/(), operator%()
  std::cout << "test17()" << std::endl;
  srand(seed);
  for (int i = 0; i < n9; i++) {
    int a, b;
    QZ::mpz_base_class x(a = rand());
    QZ::mpz_base_class y(b = rand());
//    std::cout << "x = " << x << std::endl;
    QZ::mpz_class q, r;
    div2(x, y, q, r);
 
    if (q != a / b || r != a % b) {
      std::cout << "i = " << i << std::endl;
      std::cout << "NOT EQUAL: x = " << x << ", y = " << y << ", a = " << a << ", b = " << b << ", a / b = " << a / b << ", a % b = " << a % b << std::endl;
      std::cout << "q = " << q << std::endl;
      std::cout << "r = " << r << std::endl;
      return false;
    }
  }
  return true;
}
 
int const n10 = 3000;
bool test18() {
  /* operator/(), operator%() */
  std::cout << "test18()" << std::endl;
  srand(seed);
  for (int i = 0; i < n10; i++) {
    QZ::mpz_base_class x(rand());
    QZ::mpz_base_class y(rand());
    QZ::mpz_base_class z(rand());
//    std::cout << ":x = " << x << std::endl;
    QZ::mpz_base_class q, r;
    div2(x * y, z, q, r);
 
    if (q * z + r != x * y) {
      std::cout << q << "*" << z << "+" << r << "!=" << x << "*" << y << std::endl;
      return false;
    }
  }
  return true;
}
 
bool test19() {
  /* for mpz_class not for mpz_base_lass */
  /* operator+=(), operator-=(), operator*=(), operator/=(), operator%=() */
  bool flag = true;
 
  std::cout << "test19()" << std::endl;
  QZ::mpz_class t; int n;
 
  for (n = 3, t = QZ::mpz_class(3); t < 100; n += 8, t += QZ::mpz_class(8)) {
    std::cout << t << ",";
    if (n != t) flag = false;
  }
  std::cout << std::endl;
 
  for (n = 123, t = QZ::mpz_class(123); t > 20; n -= 8, t -= 8) {
    std::cout << t << ",";
    if (n != t) flag = false;
  }
  std::cout << std::endl;
 
  for (n = 7, t = QZ::mpz_class(7); t < 500000; n *= 3, t *= 3) {
    std::cout << t << ",";
    if (n != t) flag = false;
  }
  std::cout << std::endl;
 
  for (n = 500000, t = QZ::mpz_class(500000); t > 200; n /= 3, t /= 3) {
    std::cout << t << ",";
    if (n != t) flag = false;
  }
  std::cout << std::endl;
 
  for (n = 500095, t = QZ::mpz_class(500095); t > 60; n %= 97, t %= 97) {
    std::cout << t << ",";
    if (n != t) flag = false;
  }
  std::cout << std::endl;
 
  return flag;
}
 
bool test20() {
  /* operaotr>>(), operator<<() */
  QZ::mpz_base_class t = 0x01000000;
  int n = 0x01000000;
  while (t != 0) {
    std::cout << t << std::endl;
    t = t >> 1;
    n = n >> 1;
    if (n != t) return false;
  }
 
  t = QZ::mpz_base_class(1);
  n = 1;
  for (int i = 0; i < 20; i++) {
    std::cout << t << std::endl;
    t = t << 1;
    n = n << 1;
    if (n != t) return false;
  }
  return true;
}
 
bool test21() {
  /* QZ::mpz_base_class::testBit() */
  QZ::mpz_base_class t = 0x5a5a;
  for (int i = 0; i < 16; i++) {
    if (t.testBit(i)) std::cout << "(1)" << std::endl;
    else std::cout << "(-)" << std::endl;
  }  
  return true;
}
 
bool test22() {
  /* QZ::mpz_base_class::testBit() */
  /* operaotr>>(), operator<<() */
  bool flag = true;
  int t1 = 0x5a5a;
  QZ::mpz_base_class t2(t1);
  int mask, bitnum;
  for (mask = 1, bitnum = 0; bitnum < 8; mask = mask << 1, bitnum++) {
    if (((t1 & mask) > 0) ^ (t2.testBit(bitnum))) {
      std::cout << "***not equal: bitnum = " << bitnum << std::endl;
      std::cout << "***not equal: mask = " << (t1 & mask) << std::endl;
      flag = false;
    }
  }
  return flag;
}
 
bool test23() {
  /* addition sign flag to mpz_class */
  /* constructor1 */
  std::cout << "test23" << std::endl;
  QZ::mpz_class x;
  x.dump();
  if (x.get_mpzclass_n() != 0) return false;
  if (x.get_mpzclass_b() != 0) return false;
  if (x.get_mpzclass_negative() != 0) return false;
 
  return true;
}
 
bool test24() {
  std::cout << "test24" << std::endl;
  QZ::mpz_class a1(0);
  a1.dump();
  if (a1.get_mpzclass_n() != 1) return false;
  if (*a1.get_mpzclass_b() != 0) return false;
  if (a1.get_mpzclass_negative() != 0) return false;
  QZ::mpz_class a2(1);
  a2.dump();
  if (a2.get_mpzclass_n() != 1) return false;
  if (*a2.get_mpzclass_b() != 1) return false;
  if (a2.get_mpzclass_negative() != 0) return false;
  QZ::mpz_class a3(2);
  a3.dump();
  if (a3.get_mpzclass_n() != 1) return false;
  if (*a3.get_mpzclass_b() != 2) return false;
  if (a3.get_mpzclass_negative() != 0) return false;
  QZ::mpz_class a4(4);
  a4.dump();
  if (a4.get_mpzclass_n() != 1) return false;
  if (*a4.get_mpzclass_b() != 4) return false;
  if (a4.get_mpzclass_negative() != 0) return false;
  QZ::mpz_class a5(8);
  a5.dump();
  if (a5.get_mpzclass_n() != 2) return false;
  if (*a5.get_mpzclass_b() != 0) return false;
  if (*(a5.get_mpzclass_b() + 1) != 1) return false;
  if (a5.get_mpzclass_negative() != 0) return false;
 
  std::cout << "test24:-1" << std::endl;
  QZ::mpz_class a6(-1);
  a6.dump();
  if (a6.get_mpzclass_n() != 1) return false;
  if (*a6.get_mpzclass_b() != 1) return false;
  if (a6.get_mpzclass_negative() != 1) return false;
 
  std::cout << "test24:-2" << std::endl;
  QZ::mpz_class a7(-2);
  a7.dump();
  if (a7.get_mpzclass_n() != 1) return false;
  if (*a7.get_mpzclass_b() != 2) return false;
  if (a7.get_mpzclass_negative() != 1) return false;
 
  std::cout << "test24:-4" << std::endl;
  QZ::mpz_class a8(-4);
  a8.dump();
  if (a8.get_mpzclass_n() != 1) return false;
  if (*a8.get_mpzclass_b() != 4) return false;
  if (a8.get_mpzclass_negative() != 1) return false;
 
  std::cout << "test24:-8" << std::endl;
  QZ::mpz_class a9(-8);
  a9.dump();
  if (a9.get_mpzclass_n() != 2) return false;
  if (*a9.get_mpzclass_b() != 0) return false;
  if (*(a9.get_mpzclass_b() + 1) != 1) return false;
  if (a9.get_mpzclass_negative() != 1) return false;
 
  return true;
}
 
bool test25() {
  std::cout << "test25" << std::endl;
  QZ::mpz_class a;
  QZ::mpz_class b = a;
  b.dump();
  if (b.get_mpzclass_n() != 0) return false;
  if (b.get_mpzclass_b() != 0) return false;
  if (b.get_mpzclass_negative() != 0) return false;
 
  QZ::mpz_class c = 8;
  QZ::mpz_class d = c;
  d.dump();
  if (d.get_mpzclass_n() != 2) return false;
  if (*d.get_mpzclass_b() != 0) return false;
  if (*(d.get_mpzclass_b() + 1) != 1) return false;
  if (b.get_mpzclass_negative() != 0) return false;
 
  QZ::mpz_class e = -8;
  QZ::mpz_class f = e;
  f.dump();
  if (f.get_mpzclass_n() != 2) return false;
  if (*f.get_mpzclass_b() != 0) return false;
  if (*(f.get_mpzclass_b() + 1) != 1) return false;
  if (f.get_mpzclass_negative() != 1) return false;
 
  return true;
}
 
bool test26() {
  std::cout << "test26" << std::endl;
 
  QZ::mpz_class a;
  QZ::mpz_class b;
  b = a;
  a.dump();
  b.dump();
  if (b.get_mpzclass_n() != 0) return false;
  if (b.get_mpzclass_b() != 0) return false;
  if (b.get_mpzclass_negative() != 0) return false;
 
  QZ::mpz_class c = 1;
  c.dump();
  QZ::mpz_class d;
  d = c;
  d.dump();  
  if (d.get_mpzclass_n() != 1) return false;
  if (*d.get_mpzclass_b() != 1) return false;
  if (d.get_mpzclass_negative() != 0) return false;
 
  QZ::mpz_class e = -1;
  e.dump();
  QZ::mpz_class f;
  f = e;
  f.dump();  
  if (f.get_mpzclass_n() != 1) return false;
  if (*f.get_mpzclass_b() != 1) return false;
  if (f.get_mpzclass_negative() != 1) return false;
 
  return true;
}
 
bool test27() {
  std::cout << "test27:1" << std::endl;
  QZ::mpz_class a = 1;
  QZ::mpz_class b = 1;
  if (!(a == b)) return false;
 
  std::cout << "test27:100" << std::endl;
  QZ::mpz_class x = 100;
  QZ::mpz_class y = 100;
  if (!(x == y)) return false;  
 
  std::cout << "test27:0" << std::endl;
  QZ::mpz_class u;
  QZ::mpz_class v;
  if (!(u == v)) return false;  
  QZ::mpz_class w = 0;
  if (!(u == w)) return false;  
 
  std::cout << "test27:-100" << std::endl;
  QZ::mpz_class i = -100;
  QZ::mpz_class j = -100;
  if (!(i == j)) return false;  
  QZ::mpz_class k = 100;
  if (i == k) return false;  
 
  return true;
}
 
bool test28() {
  std::cout << "test28" << std::endl;
  QZ::mpz_class a = 0;
  QZ::mpz_class b = -1;
  QZ::mpz_class c = -1;
 
  if (!(a != b)) return false;
  if (b != c) return false;
  if (a == b) return false;
  if (!(b == c)) return false;
 
  return true;
}
 
bool test29() {
  /* operator-() */
  std::cout << "test29" << std::endl;
  QZ::mpz_class x = 1;
  QZ::mpz_class y = -x;
  if (y != -1) return false;
  x = QZ::mpz_class(-1);
  y = -x;
  if (y != 1) return false;
  return true;
}
 
bool test30() {
  std::cout << "test30" << std::endl;
  QZ::mpz_class x = -1;
  std::cout << "x = " << x << std::endl;
  x = -x;
  std::cout << "x = " << x << std::endl;
  if (x.get_mpzclass_n() != 1) return false;
  if (*x.get_mpzclass_b() != 1) return false;
  if (x.get_mpzclass_negative() != false) return false;
 
  QZ::mpz_class y = -100;
  std::cout << "y = " << y << std::endl;
  y = -y;
  std::cout << "y = " << y << std::endl;
  if (x.get_mpzclass_negative() != false) return false;
 
  return true;
}
 
bool test31() {
  std::cout << "test31" << std::endl;
  std::cout << "3+5=8" << std::endl;
  QZ::mpz_class a = 3;
  QZ::mpz_class b = 5;
  QZ::mpz_class c = 8;
  if (a + b != c) return false;
  std::cout << "-------------" << std::endl;
  std::cout << "-3+(-5)=-8" << std::endl;
  a = QZ::mpz_class(-3);
  b = QZ::mpz_class(-5);
  c = QZ::mpz_class(-8);
  if (a + b != c) return false;
  std::cout << "-------------" << std::endl;
  std::cout << "-3+5=2" << std::endl;
  a = QZ::mpz_class(-3);
  b = QZ::mpz_class(5);
  c = QZ::mpz_class(2);
  if (a + b != c) return false;
  std::cout << "-------------" << std::endl;
  std::cout << "-3+1=-2" << std::endl;
  a = QZ::mpz_class(-3);
  b = QZ::mpz_class(1);
  c = QZ::mpz_class(-2);
  if (a + b != c) return false;
  std::cout << "-------------" << std::endl;
  std::cout << "5+(-3)=+2" << std::endl;
  a = QZ::mpz_class(5);
  b = QZ::mpz_class(-3);
  c = QZ::mpz_class(2);
  if (a + b != c) return false;
  std::cout << "-------------" << std::endl;
  std::cout << "5+(-8)=-3" << std::endl;
  a = QZ::mpz_class(5);
  b = QZ::mpz_class(-8);
  c = QZ::mpz_class(-3);
  if (a + b != c) return false;  
  std::cout << "-------------" << std::endl;
  return true;
}
 
bool test32() {
  std::cout << "test32" << std::endl;
  for (int i = -10; i <= +10; i++) {
    for (int j = -10; j <= +10; j++) {
      QZ::mpz_class z1 = i + j;
      QZ::mpz_class x(i);
      QZ::mpz_class y(j);      
      QZ::mpz_class z2 = x + y;
//      std::cout << "z1 = " << i + j << std::endl;
      if (z1 != z2) {
        std:: cout << "i = " << i << ", j = " << j << std::endl;
        std:: cout << "not equal!!" << std::endl;
        return false;
      }
    }
  }
  return true;
}
 
bool test33() {
  std::cout << "test33" << std::endl;
  for (int i = -10; i <= +10; i++) {
    for (int j = -10; j <= +10; j++) {
      QZ::mpz_class z1 = i - j;
      QZ::mpz_class x(i);
      QZ::mpz_class y(j);      
      QZ::mpz_class z2 = x - y;
//      std::cout << "z1 = " << i - j << std::endl;
      if (z1 != z2) {
        std:: cout << "i = " << i << ", j = " << j << std::endl;
        std:: cout << "not equal!!" << std::endl;
        return false;
      }
    }
  }
  return true;
}
bool test34() {
  std::cout << "test34" << std::endl;
  for (int i = -10; i <= 10; i++) {
    for (int j = -10; j <= 10; j++) {
      QZ::mpz_class x = i;
      QZ::mpz_class y = j;
 
//      std::cout << "i=" << i << ",j=" << j << ",x=" << x << ",y=" << y << std::endl;      
//      std::cout << i << "==" << j << ": " << (i==j) << std::endl;
//      std::cout << x << "==" << y << ": " << (x==y) << std::endl;
      if ((i == j) ^ (x == j)) { std::cout << "i==j" << std::endl; return false; }
 
//      std::cout << i << "!=" << j << ": " << (i!=j) << std::endl;
//      std::cout << x << "!=" << y << ": " << (x!=y) << std::endl;
      if ((i != j) ^ (x != y)) { std::cout << "i!=j" << std::endl; return false; }
 
      if ((i < j) ^ (x < y))   { std::cout << "i<j" << std::endl; return false; }
      if ((i <= j) ^ (x <= y)) { std::cout << "i<=j" << std::endl; return false; }
      if ((i > j) ^ (x > y))   { std::cout << "i>j" << std::endl; return false; }
      if ((i >= j) ^ (x >= y)) { std::cout << "i>=j" << std::endl; return false; }
    }
  }
  return true;
}
 
bool test35() {
  std::cout << "test35" << std::endl;
  for (int i = -10; i <= +10; i++) {
    for (int j = -10; j <= +10; j++) {
//      std::cout << "i = " << i << ", j = " << j << std::endl;
      QZ::mpz_class z1 = i * j;
      QZ::mpz_class x(i);
      QZ::mpz_class y(j);      
//      std::cout << "z1 = " << i * j << std::endl;
      QZ::mpz_class z2 = x * y;
//      std::cout << "z2 = " << z2 << std::endl;
 
      if (z1 != z2) {
        std:: cout << "i = " << i << ", j = " << j << std::endl;
        std:: cout << "not equal!!" << std::endl;
        return false;
      }
    }
  }
  return true;
}
 
int const n11 = 1000;
bool test36() {
  std::cout << "test36" << std::endl;
  srand(seed);
  for (int i = 0; i < n11; i++) {
    int a, b;
    a = (rand() >> 16);
    b = (rand() >> 16);
    if (rand() % 2 == 1) a = -a;
    if (rand() % 2 == 1) b = -b;
    QZ::mpz_class x(a);
    QZ::mpz_class y(b);
    QZ::mpz_class z = x * y;
    // std::cout << "x = " << x << std::endl;
 
    if (z != a * b) {
      std::cout << "i = " << i << std::endl;
      std::cout << "NOT EQUAL: x = " << x << ", y = " << y << ", a = " << a << ", b = " << b << ", a * b = " << a * b << std::endl;
      std::cout << "z = " << z << std::endl;
      z.dump();
      return false;
    }
  }
  return true;
}
 
int const n12 = 50;
bool test37() {
  std::cout << "test37" << std::endl;
  for (int i = -n12; i <= +n12; i++) {
    for (int j = -n12; j <= +n12; j++) {
//      std::cout << "i = " << i << ", j = " << j << std::endl;
      if (j == 0) continue;
      QZ::mpz_class q1 = i / j;
      QZ::mpz_class r1 = i % j;
      QZ::mpz_class x(i);
      QZ::mpz_class y(j);      
//      std::cout << "q1 = " << i / j << std::endl;
      QZ::mpz_class q2 = x / y;
//      std::cout << "q2 = " << q2 << std::endl;
//      std::cout << "r1 = " << i % j << std::endl;
      QZ::mpz_class r2 = x % y;
//      std::cout << "r2 = " << r2 << std::endl;
 
      if (q1 != q2 || r1 != r2) {
        std:: cout << "i = " << i << ", j = " << j << std::endl;
        std:: cout << "not equal!!" << std::endl;
        return false;
      }
    }
  }
  return true;
}
 
int const n14 = 1000;
bool test38() {
  std::cout << "test38" << std::endl;
  srand(seed);
  for (int i = 0; i < n14; i++) {
    QZ::mpz_class x(rand());
    QZ::mpz_class y(rand());
    if (rand() % 2 == 1) x = -x;
    if (rand() % 2 == 1) y = -y;
//    std::cout << "x = " << x << std::endl;
    QZ::mpz_class q = x / y;
    QZ::mpz_class r = x % y;
    if (!(q * y + r == x)) {
      std::cout << "x = " << x << ",y = " << y << ",q = " << q << ",r = " << r << std::endl;
      std::cout << "q * y = " << q * y << std::endl;
      std::cout << "q * y + r = " << q * y + r << std::endl;
      std::cout << "x =         " << q * y + r << std::endl;
      std::cout << "not equal!" << std::endl;
      return false;
    }
  }
  return true;
}
 
bool test39() {
  std::cout << "test39" << std::endl;
  QZ::mpz_class t = 2;
  QZ::mpz_class s = 3;
  t += s;
  std::cout << "t = " << t << std::endl;
  if (t != 5) return false;
 
  int n = 5;
  int d = 7;
  t = QZ::mpz_class(5);
  for (; n < 100; n += d, t += d) {
    std::cout << "n = " << n << ", t = " << t << std::endl;
    if (n != t) {
      std::cout << "n = " << n << ", t = " << t << std::endl;
      return false;
    }
  }
 
  return true;
}
 
bool test40() {
  std::cout << "test40" << std::endl;
 
  int n = 1;
  QZ::mpz_class t = 1;
  for (int i = 0; i < 10; i++) {
    int m = n << i;
    QZ::mpz_class s = t << i;
    std::cout << "i = " << i << ", m = " << m << ", s = " << s << std::endl;
    if (m != s) {
      std::cout << "bad!" << std::endl;
      return false;
    }
  }
 
  n = 0x1000;
  t = QZ::mpz_class(n);
  for (int i = 0; i < 10; i++) {
    int m = n >> i;
    QZ::mpz_class s = t >> i;
    std::cout << "i = " << i << ", m = " << m << ", s = " << s << std::endl;
    if (m != s) {
      std::cout << "bad!" << std::endl;
      return false;
    }
  }
  return true;
}
 
bool test41() {
  std::cout << "test41" << std::endl;
  QZ::mpz_class n;
  int m;
  n = QZ::mpz_class(1);
  m = n.bitLength();
  if (m != 1) return false;
  n = QZ::mpz_class(2);
  m = n.bitLength();
  if (m != 2) return false;
  n = QZ::mpz_class(3);
  m = n.bitLength();
  if (m != 2) return false;
  n = QZ::mpz_class(4);
  m = n.bitLength();
  if (m != 3) return false;
  n = QZ::mpz_class(8);
  m = n.bitLength();
  if (m != 4) return false;
  n = QZ::mpz_class(16);
  m = n.bitLength();
  if (m != 5) return false;
  n = QZ::mpz_class(32);
  m = n.bitLength();
  if (m != 6) return false;
  n = QZ::mpz_class(64);
  m = n.bitLength();
  if (m != 7) return false;
  n = QZ::mpz_class(128);
  m = n.bitLength();
  if (m != 8) return false;
  n = QZ::mpz_class(256);
  m = n.bitLength();
  if (m != 9) return false;
  return true;
}
 
bool test42() {
  std::cout << "test42" << std::endl;
  QZ::mpz_base_class r(4 + 256);
  r.test42();
  int m = r.bitLength();
  std::cout << "r = " << r << std::endl;
  std::cout << "m = " << m << std::endl;
  if (m != 3) return false;
  return true;
}
 
void test() {
  if (test00() == true) std::cout << "00 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
  if (test01() == true) std::cout << "01 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
  if (test02() == true) std::cout << "02 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
  if (test03() == true) std::cout << "03 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
  if (test04() == true) std::cout << "04 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
  if (test05() == true) std::cout << "05 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
  if (test06() == true) std::cout << "06 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
  if (test07() == true) std::cout << "07 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
  if (test08() == true) std::cout << "08 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
  if (test09() == true) std::cout << "09 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
  if (test10() == true) std::cout << "10 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
  if (test11() == true) std::cout << "11 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
  if (test12() == true) std::cout << "12 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
  if (test13() == true) std::cout << "13 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
  if (test14() == true) std::cout << "14 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
  if (test15() == true) std::cout << "15 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
  if (test16() == true) std::cout << "16 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
  if (test17() == true) std::cout << "17 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
  if (test18() == true) std::cout << "18 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
  if (test19() == true) std::cout << "19 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
  if (test20() == true) std::cout << "20 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
  if (test21() == true) std::cout << "21 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
  if (test22() == true) std::cout << "22 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
  if (test23() == true) std::cout << "23 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
  if (test24() == true) std::cout << "24 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
  if (test25() == true) std::cout << "25 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
  if (test26() == true) std::cout << "26 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
  if (test27() == true) std::cout << "27 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
  if (test28() == true) std::cout << "28 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
  if (test29() == true) std::cout << "29 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
  if (test30() == true) std::cout << "30 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
  if (test31() == true) std::cout << "31 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
  if (test32() == true) std::cout << "32 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
  if (test33() == true) std::cout << "33 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
  if (test34() == true) std::cout << "34 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
  if (test35() == true) std::cout << "35 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
  if (test36() == true) std::cout << "36 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
  if (test37() == true) std::cout << "37 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
  if (test38() == true) std::cout << "38 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
  if (test39() == true) std::cout << "39 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
  if (test40() == true) std::cout << "40 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
  if (test41() == true) std::cout << "41 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
  if (test42() == true) std::cout << "42 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
  return;
}
 
int main() {
//  xmalloccancel();
  test();
  xmallocdump();
  return 0;
}
/* end */