Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2009-02-08

bignumライブラリの自作

| 16:40 | bignumライブラリの自作 - naoya_t@topcoder を含むブックマーク はてなブックマーク - bignumライブラリの自作 - naoya_t@topcoder bignumライブラリの自作 - naoya_t@topcoder のブックマークコメント

  • bignum同士の加減乗算(※除算は未実装)
  • bignumに(signed)intを足したり引いたり掛けたり割ったり
  • bignumと文字列との間の変換(基数指定可)

とか。とりあえず、昨日のMedium問題が解ける程度まで実装できたので晒します。

内部では65536進法で演算しています。2^32進法だと(bignum同士の加算や乗算をする際に)キャリーの計算が面倒くさいかなと思っての愚行です。

ご利用は計画的に。

//
// bignum library ver 0.1 by naoya_t - 使うなら自己責任で
//
#include <string>
#include <vector>
#include <stack>
#include <sstream>
#include <iostream>
using namespace std;

class bignum {
  int sign;
  int size;
  vector<int> values;

  int default_radix_;
  int remainder_;

 public:
  bignum(int val=0){set(val);default_radix_=10;}
  bignum(string val, int radix=10){set(val,default_radix_=radix);}
  bignum(const bignum& num){set(num);}
  bignum(int sg,const vector<int> &vals,int radix=0){set(sg,vals,radix);}

  void operator=(int val){set(val);}
  void operator=(string val){set(val,default_radix_);}
  void operator=(const bignum& num){set(num);}

  void set(int val);
  void set(string val, int radix=10);
  void set(const bignum& num);
  void set(int sg,const vector<int> &vals,int radix=0);

 private:
  bool is_zero() const { return (size==1 && values[0]==0)? true : false; };
  void set_zero();
  void normalize();

  char enc(int n) const { return n<10 ? '0'+n : 'A'+(n-10); }
  int dec(int ch) const { return ch<='9' ? ch-'0' : 10+ch-'A'; }

 public:
  void set_default_radix(int radix){default_radix_=radix;}
  int get_default_radix(){return default_radix_;}

  string sdump() const;
  void dump() { cout << sdump(); }

  bignum abs() const;
  bignum minus() const;

  int cmp(const bignum &n) const;
  int cmp_abs(const bignum &n) const;

  int to_i();
  string to_s(int radix=10) const;

  bignum operator+(const bignum& rop){ bignum num(*this); num += rop; return num; }
  bignum operator-(const bignum& rop){ bignum num(*this); num += rop.minus(); return num; }
  bignum operator*(const bignum& rop){ bignum num(*this); num *= rop; return num; }

  bignum operator+(int rop){
    bignum num(*this); num += rop; return num; }
  bignum operator-(int rop){
    bignum num(*this); num -= rop; return num; }
  bignum operator*(int rop){
    bignum num(*this); num *= rop; return num; }
  bignum operator/(int rop){
    bignum num(*this); num /= rop; return num; }

  bool operator==(const bignum& rop) const { return cmp(rop)==0; }
  bool operator!=(const bignum& rop) const { return cmp(rop)!=0; }
  bool operator>(const bignum& rop) const { return cmp(rop)>0; }
  bool operator>=(const bignum& rop) const { return cmp(rop)>=0; }
  bool operator<(const bignum& rop) const { return cmp(rop)<0; }
  bool operator<=(const bignum& rop) const { return cmp(rop)<=0; }

  void operator+=(const bignum& num);
  void operator-=(const bignum& num){ operator+=(num.minus()); }
  void operator*=(const bignum& num);
  //void operator/=(const bignum& num);

  void operator+=(int n);
  void operator-=(int n){ operator+=(-n); }
  void operator*=(int n);
  void operator/=(int n);
  //void operator%=(int n);
  int remainder(){ return remainder_; }

  bignum add(const bignum& n){ bignum num(*this); num += n; return num; }
  bignum sub(const bignum& n){ bignum num(*this); num += n.minus(); return num; }
  bignum mul(const bignum& n){ bignum num(*this); num *= n; return num; }
  //bignum div(const bignum& n){ bignum num(*this); num /= n; return num; }

  bignum add(int n){ bignum num(*this); num += n; return num; }
  bignum sub(int n){ bignum num(*this); num += (-n); return num; }
  bignum mul(int n){ bignum num(*this); num *= n; return num; }
  bignum div(int n){ bignum num(*this); num /= n; return num; }
};

void bignum::set(int val){
  if (val == INT_MIN) {
    values.resize(size = 2);
    sign = -1;
    values[0] = 0; values[1] = 0x8000;
  } else {
    if (val < 0) { sign = -1; val = -val; } else sign = 1;
    if (val >= 65536) {
      values.resize(size = 2);
      values[0] = val % 65536; values[1] = val >> 16;
    } else {
      values.resize(size = 1);
      values[0] = val;
    }
  }
}

void bignum::set_zero(){
  values.resize(size = 1);
  size = 1; sign = 1; values[0] = 0;
}

void bignum::set(const bignum& num){
  values.assign(num.values.begin(), num.values.end());
  sign = num.sign; size = num.size; default_radix_ = num.default_radix_;
}

void bignum::set(int sg,const vector<int> &vals,int radix){
  if (radix == 0) {
    size=1;
    for(int i=0,s=vals.size();i<s;i++) if (vals[i]>0) size=i+1;
    values.assign(vals.begin(), vals.begin()+size);
    sign = is_zero()? 1 : sg;
  } else {
    set_zero();
  }
}

int bignum::to_i() {
  switch(size){
    case 1:
      return sign * values[0];
    case 2:
      if (values[1]<=0x7fff)
        return sign * ((values[1]<<16) | values[0]);
      else if (values[1]==0x8000 && values[0]==0 && sign==-1)
        return INT_MIN;
      else
        ; // else ; thru
    default:
      return INT_MAX+1;
  }
}

string bignum::sdump() const {
  stringstream ss;
  ss << ((sign > 0) ? "+" : "-") << hex << uppercase;
  for (int i=0;i<size;i++) {
    if (i>0) ss << ":";
    ss << values[size-i-1];
  }
  ss << "<" << size << ">";
  return ss.str();
}

bignum bignum::abs() const {
  bignum num(*this);
  num.sign = 1;
  return num;
}

bignum bignum::minus() const {
  bignum num(*this);
  if (!is_zero()) num.sign = -num.sign;
  return num;
}

int bignum::cmp(const bignum &n) const {
  if(sign != n.sign) return (sign - n.sign)/2;
  return sign * cmp_abs(n);
}

int bignum::cmp_abs(const bignum &n) const {
  if(size!=n.size)
    return size - n.size;
  for(int i=size-1;i>=0;i--)
    if(values[i]!=n.values[i]) return values[i] - n.values[i];
  return 0;
}

void bignum::operator+=(const bignum &n){
  if(n.is_zero()) return;
  if(sign == n.sign) {
    if(size < n.size) {
      values.resize(n.size);
      for(int i=size;i<n.size;i++) values[i]=0;
      size = n.size;
    }
    // simple addition
    for(int i=0;i<n.size;i++) values[i] += n.values[i];
  } else {
    if(cmp_abs(n) >= 0) {
      for(int i=0;i<n.size;i++) {
        if (values[i] >= n.values[i]) {
          values[i] -= n.values[i];
        } else {
          int pl=i+1;
          for(int j=i+1;j<n.size;j++) if(values[j]>0){ pl=j; break; }
          for(int j=pl;j>i;j--) { values[j]--; values[j-1]+=65536; }
          values[i] -= n.values[i];
        }
      }
    } else {
      bignum t(n);
      set(t + *this);
    }
  }
  normalize();
}

void bignum::operator*=(const bignum &n){
  if(is_zero()) return;
  if(n.is_zero()){ set_zero(); return; }
  sign *= n.sign;

  vector<int> tmp(size + n.size, 0);
  for(int i=n.size-1;i>=0;i--){
    int ni = n.values[i];
    for(int j=size-1;j>=0;j--){
      unsigned int ij = (unsigned int)ni * values[j];
      tmp[i+j] += ij % 65536;
      tmp[i+j+1] += ij >> 16;
    }
  }
  values.assign(tmp.begin(), tmp.end());
  size += n.size;
  normalize();
}

void bignum::operator+=(int n){
  if (n==0) return;
  if (sign*n<0){
    int m=this->to_i();
    if (m!=INT_MAX+1){
      set(m + n);
      return;
    }
  }
  if(sign==-1) n=-n;
  values[0] += n;
  normalize();
}

void bignum::operator*=(int n){
  if(n==0){ set_zero(); return; }
  if(n==1){ return; }
  if(n==-1){ sign=-sign; return; }
  if(n<0){ sign=-sign; n=-n; }
  for(int i=0;i<size;i++) values[i]*=n;
  normalize();
}

void bignum::operator/=(int n){
  if(n==0){ set_zero(); return; } // NaN
  if(n==1){ return; }
  if(n==-1){ sign=-sign; return; }
  if(n<0){ sign=-sign; n=-n; }
  int r = 0;
  for(int i=size-1; i>=0; i--){
    int v = (r << 16) + values[i];
    r = v % n;
    values[i] = v / n;
  }
  normalize();
  remainder_ = r;
}

void bignum::normalize(){
  unsigned int overflown=0;
  int sz=1;
  for(int i=0;i<size;i++){
    if (values[i]>0) sz=i+1;
    if (values[i]<0) {
      if (i==size-1) {
        // underflow
        sign=-sign;
        values[i]=-values[i];
        for (int j=i-1;j>=0;j--){
          //...
        }
      } else {
        // borrowable
        int b=-values[i];
        values[i+1] -= (b >> 16);
        if (b&0xffff){
          values[i+1]--;
          values[i] = 65536 - b;
        } else {
          values[i] = 0;
        }
      }
    }
    if (values[i]>=65536){
      if (i==size-1) overflown = values[i] >> 16;
      else values[i+1] += values[i] >> 16;
      values[i] %= 65536;
    }
  }
  if (overflown == 0) {
    if (sz<size) values.resize(size=sz);
    if (is_zero()) sign=1;
  } else if (overflown < 65536){
    values.resize(size+1);
    values[size++] = overflown;
  } else {
    values.resize(size+2);
    values[size++] = overflown % 65536;
    values[size++] = overflown >> 16;
  }
}

string bignum::to_s(int radix) const {
  if (is_zero()) return "0";
  if (radix < 2 || 36 < radix) return "?";

  stack<char> s;
  bignum tmp(*this);
  while(!tmp.is_zero()){
    tmp /= radix;
    s.push(enc(tmp.remainder()));
  }
  stringstream ss;
  if (sign == -1) ss << "-";
  while(!s.empty()){
    ss << s.top();
    s.pop();
  }
  return ss.str();
}

void bignum::set(string val, int radix){
  set_zero();
  if (radix < 2 || 36 < radix) return;
  default_radix_ = radix;

  int l=val.size();
  int start=0, sg=1;
  if(val[0]=='-'){ sg = -1; start++; }
  else if(val[0]=='+') start++;
  for(int i=start,s=val.size();i<s;i++){
    operator*=( radix );
    operator+=( dec(val[i]) );
  }
  normalize();
  sign = sg;
}

googletestつけとくよ

using namespace std;

// #include "bignum.cc"
#include <gtest/gtest.h>

TEST(BignumTest, sdump)
{
  bignum num; vector<int> v(1,0);
  num.set(1,v); EXPECT_EQ("+0<1>", num.sdump());
  num.set(-1,v); EXPECT_EQ("+0<1>", num.sdump());
  
  v[0]=1;
  num.set(1,v); EXPECT_EQ("+1<1>", num.sdump());
  num.set(-1,v); EXPECT_EQ("-1<1>", num.sdump());

  v[0]=65535;
  num.set(1,v); EXPECT_EQ("+FFFF<1>", num.sdump());
  num.set(-1,v); EXPECT_EQ("-FFFF<1>", num.sdump());

  v.resize(2);
  v[0]=v[1]=0;
  num.set(1,v); EXPECT_EQ("+0<1>", num.sdump());
  num.set(-1,v); EXPECT_EQ("+0<1>", num.sdump());
  v[0]=65535; v[1]=1;
  num.set(1,v); EXPECT_EQ("+1:FFFF<2>", num.sdump());
  num.set(-1,v); EXPECT_EQ("-1:FFFF<2>", num.sdump());
  v[1]=65535;
  num.set(1,v); EXPECT_EQ("+FFFF:FFFF<2>", num.sdump());
  num.set(-1,v); EXPECT_EQ("-FFFF:FFFF<2>", num.sdump());

  v.resize(3);
  v[2]=1;
  num.set(1,v); EXPECT_EQ("+1:FFFF:FFFF<3>", num.sdump());
  num.set(-1,v); EXPECT_EQ("-1:FFFF:FFFF<3>", num.sdump());
  v[2]=65535;
  num.set(1,v); EXPECT_EQ("+FFFF:FFFF:FFFF<3>", num.sdump());
  num.set(-1,v); EXPECT_EQ("-FFFF:FFFF:FFFF<3>", num.sdump());
}

TEST(BignumTest, to_i)
{
  bignum num; EXPECT_EQ(0, num.to_i());
  num=1; EXPECT_EQ(1, num.to_i());
  num=2; EXPECT_EQ(2, num.to_i());
  num=-1; EXPECT_EQ(-1, num.to_i());
  num=-2; EXPECT_EQ(-2, num.to_i());

  num=65535; EXPECT_EQ(65535, num.to_i());
  num=-65535; EXPECT_EQ(-65535, num.to_i());
  num=65536; EXPECT_EQ(65536, num.to_i());
  num=-65536; EXPECT_EQ(-65536, num.to_i());
  num=65537; EXPECT_EQ(65537, num.to_i());
  num=-65537; EXPECT_EQ(-65537, num.to_i());
  
  num=INT_MAX; EXPECT_EQ(INT_MAX, num.to_i());
  num=-INT_MAX; EXPECT_EQ(-INT_MAX, num.to_i());
  num=INT_MIN; EXPECT_EQ(INT_MIN, num.to_i());
  // overflow case
  //...
}

TEST(BignumTest, ctor_from_signed_int)
{
  bignum num; EXPECT_EQ(0, num.to_i()); EXPECT_EQ("+0<1>", num.sdump());
  bignum num0(0); EXPECT_EQ(0, num0.to_i()); EXPECT_EQ("+0<1>", num0.sdump());

  bignum num1(1); EXPECT_EQ(1, num1.to_i()); EXPECT_EQ("+1<1>", num1.sdump());
  bignum num2(2); EXPECT_EQ(2, num2.to_i()); EXPECT_EQ("+2<1>", num2.sdump());
  bignum num_1(-1); EXPECT_EQ(-1, num_1.to_i()); EXPECT_EQ("-1<1>", num_1.sdump());
  bignum num_2(-2); EXPECT_EQ(-2, num_2.to_i()); EXPECT_EQ("-2<1>", num_2.sdump());

  bignum numIMAX(INT_MAX); EXPECT_EQ(INT_MAX, numIMAX.to_i()); EXPECT_EQ("+7FFF:FFFF<2>", numIMAX.sdump());
  bignum num_IMAX(-INT_MAX); EXPECT_EQ(-INT_MAX, num_IMAX.to_i()); EXPECT_EQ("-7FFF:FFFF<2>", num_IMAX.sdump());
  bignum numIMIN(INT_MIN); EXPECT_EQ(INT_MIN, numIMIN.to_i()); EXPECT_EQ("-8000:0<2>", numIMIN.sdump());
}

TEST(BignumTest, assign_signed_int)
{
  bignum num;
  num=0; EXPECT_EQ(0, num.to_i()); EXPECT_EQ("+0<1>", num.sdump());
  num=1; EXPECT_EQ(1, num.to_i()); EXPECT_EQ("+1<1>", num.sdump());
  num=2; EXPECT_EQ(2, num.to_i()); EXPECT_EQ("+2<1>", num.sdump());
  num=-1; EXPECT_EQ(-1, num.to_i()); EXPECT_EQ("-1<1>", num.sdump());
  num=-2; EXPECT_EQ(-2, num.to_i()); EXPECT_EQ("-2<1>", num.sdump());
  num=1000000; EXPECT_EQ(1000000, num.to_i()); EXPECT_EQ("+F:4240<2>", num.sdump());
  num=-1000000; EXPECT_EQ(-1000000, num.to_i()); EXPECT_EQ("-F:4240<2>", num.sdump());
  num=INT_MAX; EXPECT_EQ(INT_MAX, num.to_i()); EXPECT_EQ("+7FFF:FFFF<2>", num.sdump());
  num=-INT_MAX; EXPECT_EQ(-INT_MAX, num.to_i()); EXPECT_EQ("-7FFF:FFFF<2>", num.sdump());
  num=INT_MIN; EXPECT_EQ(INT_MIN, num.to_i()); EXPECT_EQ("-8000:0<2>", num.sdump());
}

TEST(BignumTest, abs)
{
  bignum num; EXPECT_EQ(0, num.abs().to_i()); EXPECT_EQ("+0<1>", num.abs().sdump());
  num=1; EXPECT_EQ(1, num.abs().to_i()); EXPECT_EQ("+1<1>", num.abs().sdump());
  num=2; EXPECT_EQ(2, num.abs().to_i()); EXPECT_EQ("+2<1>", num.abs().sdump());
  num=-1; EXPECT_EQ(1, num.abs().to_i()); EXPECT_EQ("+1<1>", num.abs().sdump());
  num=-2; EXPECT_EQ(2, num.abs().to_i()); EXPECT_EQ("+2<1>", num.abs().sdump());

  num=INT_MAX; EXPECT_EQ(INT_MAX, num.abs().to_i()); EXPECT_EQ("+7FFF:FFFF<2>", num.abs().sdump());
  num=-INT_MAX; EXPECT_EQ(INT_MAX, num.abs().to_i()); EXPECT_EQ("+7FFF:FFFF<2>", num.abs().sdump());
  num=INT_MIN; EXPECT_EQ(INT_MIN, num.abs().to_i()); EXPECT_EQ("+8000:0<2>", num.abs().sdump());

  vector<int> v(2,65535);
  num.set(1,v); EXPECT_EQ("+FFFF:FFFF<2>", num.abs().sdump());
  num.set(-1,v); EXPECT_EQ("+FFFF:FFFF<2>", num.abs().sdump());
}

TEST(BignumTest, minus)
{
  bignum num; EXPECT_EQ(0, num.abs().to_i()); EXPECT_EQ("+0<1>", num.minus().sdump());
  num=1; EXPECT_EQ(-1, num.minus().to_i()); EXPECT_EQ("-1<1>", num.minus().sdump());
  num=2; EXPECT_EQ(-2, num.minus().to_i()); EXPECT_EQ("-2<1>", num.minus().sdump());
  num=-1; EXPECT_EQ(1, num.minus().to_i()); EXPECT_EQ("+1<1>", num.minus().sdump());
  num=-2; EXPECT_EQ(2, num.minus().to_i()); EXPECT_EQ("+2<1>", num.minus().sdump());

  num=INT_MAX; EXPECT_EQ(-INT_MAX, num.minus().to_i()); EXPECT_EQ("-7FFF:FFFF<2>", num.minus().sdump());
  num=-INT_MAX; EXPECT_EQ(INT_MAX, num.minus().to_i()); EXPECT_EQ("+7FFF:FFFF<2>", num.minus().sdump());
  num=INT_MIN; EXPECT_EQ(INT_MAX+1, num.minus().to_i()); EXPECT_EQ("+8000:0<2>", num.minus().sdump());

  vector<int> v(2,65535);
  num.set(1,v); EXPECT_EQ("-FFFF:FFFF<2>", num.minus().sdump());
  num.set(-1,v); EXPECT_EQ("+FFFF:FFFF<2>", num.minus().sdump());
}

TEST(BignumTest, to_s)
{
  bignum num; EXPECT_EQ("0", num.to_s());
  num=1; EXPECT_EQ("1", num.to_s());
  num=2; EXPECT_EQ("2", num.to_s());
  num=-1; EXPECT_EQ("-1", num.to_s());
  num=-2; EXPECT_EQ("-2", num.to_s());
  num=INT_MAX; EXPECT_EQ("2147483647", num.to_s());
  num=-INT_MAX; EXPECT_EQ("-2147483647", num.to_s());
  num=INT_MIN; EXPECT_EQ("-2147483648", num.to_s());

  num=15;
  EXPECT_EQ("15", num.to_s());
  EXPECT_EQ("1111", num.to_s(2));
  EXPECT_EQ("F", num.to_s(16));
  num=100;
  EXPECT_EQ("100", num.to_s());
  EXPECT_EQ("64", num.to_s(16));

  num=35;
  EXPECT_EQ("35", num.to_s());
  EXPECT_EQ("100011", num.to_s(2));
  EXPECT_EQ("23", num.to_s(16));
  EXPECT_EQ("Z", num.to_s(36));

  num=65537;
  EXPECT_EQ("65537", num.to_s());
  EXPECT_EQ("10000000000000001", num.to_s(2));
  EXPECT_EQ("10001", num.to_s(16));

  num=1; for(int i=0;i<30;i++) num*=10;
  EXPECT_EQ("1000000000000000000000000000000", num.to_s());
  num=1; for(int i=0;i<30;i++) num*=16;
  EXPECT_EQ("1000000000000000000000000000000", num.to_s(16));
}

TEST(BignumTest, add_eq_signed_int) // testing operator +=
{
  bignum num;
  num=0; num+=2; EXPECT_EQ("+2<1>", num.sdump());
  num=0; num+=-2; EXPECT_EQ("-2<1>", num.sdump());

  num=1; num+=2; EXPECT_EQ("+3<1>", num.sdump());
  num=1; num+=-2; EXPECT_EQ("-1<1>", num.sdump());
  num=-1; num+=2; EXPECT_EQ("+1<1>", num.sdump());
  num=-1; num+=-2; EXPECT_EQ("-3<1>", num.sdump());

  num=50000; num+=50000;
  EXPECT_EQ(100000, num.to_i()); EXPECT_EQ("+1:86A0<2>", num.sdump());
  num=50000; num+=-50000;
  EXPECT_EQ(0, num.to_i()); EXPECT_EQ("+0<1>", num.sdump());
  num=-50000; num+=50000;
  EXPECT_EQ(0, num.to_i()); EXPECT_EQ("+0<1>", num.sdump());
  num=-50000; num+=-50000;
  EXPECT_EQ(-100000, num.to_i()); EXPECT_EQ("-1:86A0<2>", num.sdump());

  num=567890; num+=432100;
  EXPECT_EQ(999990, num.to_i()); EXPECT_EQ("+F:4236<2>", num.sdump());
  num=567890; num+=-432100;
  EXPECT_EQ(135790, num.to_i()); EXPECT_EQ("+2:126E<2>", num.sdump());
  num=-567890; num+=432100;
  EXPECT_EQ(-135790, num.to_i()); EXPECT_EQ("-2:126E<2>", num.sdump());
  num=-567890; num+=-432100;
  EXPECT_EQ(-999990, num.to_i()); EXPECT_EQ("-F:4236<2>", num.sdump());
  
  num=567890; num+=567889;
  EXPECT_EQ(1135779, num.to_i()); EXPECT_EQ("+11:54A3<2>", num.sdump());
  num=567890; num+=-567889;
  EXPECT_EQ(1, num.to_i()); EXPECT_EQ("+1<1>", num.sdump());
  num=-567890; num+=567889;
  EXPECT_EQ(-1, num.to_i()); EXPECT_EQ("-1<1>", num.sdump());
  num=-567890; num+=-567889;
  EXPECT_EQ(-1135779, num.to_i()); EXPECT_EQ("-11:54A3<2>", num.sdump());

  num=432100; num+=567890; EXPECT_EQ("+F:4236<2>", num.sdump());
  num=432100; num+=-567890; EXPECT_EQ("-2:126E<2>", num.sdump());
  num=-432100; num+=567890; EXPECT_EQ("+2:126E<2>", num.sdump());
  num=-432100; num+=-567890; EXPECT_EQ("-F:4236<2>", num.sdump());
}

TEST(BignumTest, sub_eq_signed_int) // testing operator -=
{
  bignum num;
  num=0; num-=2; EXPECT_EQ("-2<1>", num.sdump());
  num=0; num-=-2; EXPECT_EQ("+2<1>", num.sdump());

  num=1; num-=2; EXPECT_EQ("-1<1>", num.sdump());
  num=1; num-=-2; EXPECT_EQ("+3<1>", num.sdump());
  num=-1; num-=2; EXPECT_EQ("-3<1>", num.sdump());
  num=-1; num-=-2; EXPECT_EQ("+1<1>", num.sdump());

  num=50000; num-=50000; EXPECT_EQ("+0<1>", num.sdump());
  num=50000; num-=-50000; EXPECT_EQ("+1:86A0<2>", num.sdump());
  num=-50000; num-=50000; EXPECT_EQ("-1:86A0<2>", num.sdump());
  num=-50000; num-=-50000; EXPECT_EQ("+0<1>", num.sdump());

  num=567890; num-=432100; EXPECT_EQ("+2:126E<2>", num.sdump());
  num=567890; num-=-432100; EXPECT_EQ("+F:4236<2>", num.sdump());
  num=-567890; num-=432100; EXPECT_EQ("-F:4236<2>", num.sdump());
  num=-567890; num-=-432100; EXPECT_EQ("-2:126E<2>", num.sdump());

  num=567890; num-=567889; EXPECT_EQ("+1<1>", num.sdump());
  num=567890; num-=-567889; EXPECT_EQ("+11:54A3<2>", num.sdump());
  num=-567890; num-=567889; EXPECT_EQ("-11:54A3<2>", num.sdump());
  num=-567890; num-=-567889; EXPECT_EQ("-1<1>", num.sdump());

  num=432100; num-=567890; EXPECT_EQ("-2:126E<2>", num.sdump());
  num=432100; num-=-567890; EXPECT_EQ("+F:4236<2>", num.sdump());
  num=-432100; num-=567890; EXPECT_EQ("-F:4236<2>", num.sdump());
  num=-432100; num-=-567890; EXPECT_EQ("+2:126E<2>", num.sdump());
}

TEST(BignumTest, mul_eq_signed_int) // testing operator *=
{
  bignum num;
  num=0; num*=2; EXPECT_EQ("+0<1>", num.sdump());
  num=0; num*=-2; EXPECT_EQ("+0<1>", num.sdump());

  num=1; num*=2; EXPECT_EQ("+2<1>", num.sdump());
  num=1; num*=-2; EXPECT_EQ("-2<1>", num.sdump());
  num=-1; num*=2; EXPECT_EQ("-2<1>", num.sdump());
  num=-1; num*=-2; EXPECT_EQ("+2<1>", num.sdump());

  num=3; num*=5; EXPECT_EQ("+F<1>", num.sdump());
  num=3; num*=-5; EXPECT_EQ("-F<1>", num.sdump());
  num=-3; num*=5; EXPECT_EQ("-F<1>", num.sdump());
  num=-3; num*=-5; EXPECT_EQ("+F<1>", num.sdump());

  num=1000; num*=1000; EXPECT_EQ("+F:4240<2>", num.sdump());
  num=1000; num*=-1000; EXPECT_EQ("-F:4240<2>", num.sdump());
  num=-1000; num*=1000; EXPECT_EQ("-F:4240<2>", num.sdump());
  num=-1000; num*=-1000; EXPECT_EQ("+F:4240<2>", num.sdump());
}

TEST(BignumTest, div_eq_signed_int) // testing operator /=
{
  bignum num;
  num=0; num/=2;
  EXPECT_EQ("+0<1>", num.sdump()); EXPECT_EQ(0, num.remainder());
  num=0; num/=-2;
  EXPECT_EQ("+0<1>", num.sdump()); //EXPECT_EQ(0, num.remainder());

  num=1; num/=2;
  EXPECT_EQ("+0<1>", num.sdump()); EXPECT_EQ(1, num.remainder());
  num=1; num/=-2;
  EXPECT_EQ("+0<1>", num.sdump()); //EXPECT_EQ(1, num.remainder());
  num=-1; num/=2;
  EXPECT_EQ("+0<1>", num.sdump()); //EXPECT_EQ(1, num.remainder());
  num=-1; num/=-2;
  EXPECT_EQ("+0<1>", num.sdump()); //EXPECT_EQ(1, num.remainder());

  num=13; num/=5;
  EXPECT_EQ("+2<1>", num.sdump()); EXPECT_EQ(3, num.remainder());
  num=13; num/=-5;
  EXPECT_EQ("-2<1>", num.sdump()); //EXPECT_EQ(3, num.remainder());
  num=-13; num/=5;
  EXPECT_EQ("-2<1>", num.sdump()); //EXPECT_EQ(3, num.remainder());
  num=-13; num/=-5;
  EXPECT_EQ("+2<1>", num.sdump()); //EXPECT_EQ(3, num.remainder());

  num=1000000; num/=1000;
  EXPECT_EQ("+3E8<1>", num.sdump()); EXPECT_EQ(0, num.remainder());
  num=1000000; num/=-1000;
  EXPECT_EQ("-3E8<1>", num.sdump()); EXPECT_EQ(0, num.remainder());
  num=-1000000; num/=1000;
  EXPECT_EQ("-3E8<1>", num.sdump()); EXPECT_EQ(0, num.remainder());
  num=-1000000; num/=-1000;
  EXPECT_EQ("+3E8<1>", num.sdump()); EXPECT_EQ(0, num.remainder());
}

TEST(BignumTest, add_eq_bignum) // +=
{
  bignum a, b;

  a=0, b=0; a+=b; EXPECT_EQ(0, a.to_i());
  a=0, b=2; a+=b; EXPECT_EQ(2, a.to_i());
  a=2, b=0; a+=b; EXPECT_EQ(2, a.to_i());

  a=1, b=2; a+=b; EXPECT_EQ(3, a.to_i());
  a=1, b=-2; a+=b; EXPECT_EQ(-1, a.to_i());
  a=-1, b=2; a+=b; EXPECT_EQ(1, a.to_i());
  a=-1, b=-2; a+=b; EXPECT_EQ(-3, a.to_i());

  a=50000, b=50000; a+=b; EXPECT_EQ(100000, a.to_i());
  a=50000, b=-50000; a+=b; EXPECT_EQ(0, a.to_i());
  a=-50000, b=50000; a+=b; EXPECT_EQ(0, a.to_i());
  a=-50000, b=-50000; a+=b; EXPECT_EQ(-100000, a.to_i());

  a=567890, b=432100; a+=b; EXPECT_EQ(999990, a.to_i());
  a=567890, b=-432100; a+=b; EXPECT_EQ(135790, a.to_i());
  a=-567890, b=432100; a+=b; EXPECT_EQ(-135790, a.to_i());
  a=-567890, b=-432100; a+=b; EXPECT_EQ(-999990, a.to_i());

  a=567890, b=567889; a+=b; EXPECT_EQ(1135779, a.to_i());
  a=567890, b=-567889; a+=b; EXPECT_EQ(1, a.to_i());
  a=-567890, b=567889; a+=b; EXPECT_EQ(-1, a.to_i());
  a=-567890, b=-567889; a+=b; EXPECT_EQ(-1135779, a.to_i());

  a=432100, b=567890; a+=b; EXPECT_EQ(999990, a.to_i());
  a=432100, b=-567890; a+=b; EXPECT_EQ(-135790, a.to_i());
  a=-432100, b=567890; a+=b; EXPECT_EQ(135790, a.to_i());
  a=-432100, b=-567890; a+=b; EXPECT_EQ(-999990, a.to_i());
}

TEST(BignumTest, mul_eq_bignum) // testing operator *=
{
  bignum a, b;

  a=0; b=0; a*=b; EXPECT_EQ(0, a.to_i());
  a=0; b=2; a*=b; EXPECT_EQ(0, a.to_i());
  a=2; b=0; a*=b; EXPECT_EQ(0, a.to_i());
  a=1; b=1; a*=b; EXPECT_EQ(1, a.to_i());
  a=1; b=2; a*=b; EXPECT_EQ(2, a.to_i());
  a=2; b=1; a*=b; EXPECT_EQ(2, a.to_i());
  a=2; b=2; a*=b; EXPECT_EQ(4, a.to_i());
  a=3; b=-2; a*=b; EXPECT_EQ(-6, a.to_i());
  a=-3; b=2; a*=b; EXPECT_EQ(-6, a.to_i());
  a=-3; b=-2; a*=b; EXPECT_EQ(6, a.to_i());

  a=10000; b=10000; a*=b; EXPECT_EQ(100000000, a.to_i());
  a=100000000; b=100000000; a*=b; EXPECT_EQ("10000000000000000", a.to_s());
  a=65535; b=65535; a*=b; EXPECT_EQ("FFFE0001", a.to_s(16));
  a=65536; b=65536; a*=b; EXPECT_EQ("100000000", a.to_s(16));
}

TEST(BignumTest, add) // +
{
  bignum a, b;

  a=0, b=0; EXPECT_EQ(0, (a+b).to_i());
  a=0, b=2; EXPECT_EQ(2, (a+b).to_i());
  a=2, b=0; EXPECT_EQ(2, (a+b).to_i());

  a=1, b=2; EXPECT_EQ(3, (a+b).to_i()); EXPECT_EQ(1, a.to_i()); EXPECT_EQ(2, b.to_i());
  a=1, b=-2; EXPECT_EQ(-1, (a+b).to_i());
  a=-1, b=2; EXPECT_EQ(1, (a+b).to_i());
  a=-1, b=-2; EXPECT_EQ(-3, (a+b).to_i());

  a=50000, b=50000; EXPECT_EQ(100000, (a+b).to_i());
  a=50000, b=-50000; EXPECT_EQ(0, (a+b).to_i());
  a=-50000, b=50000; EXPECT_EQ(0, (a+b).to_i());
  a=-50000, b=-50000; EXPECT_EQ(-100000, (a+b).to_i());

  a=567890, b=432100; EXPECT_EQ(999990, (a+b).to_i());
  a=567890, b=-432100; EXPECT_EQ(135790, (a+b).to_i());
  a=-567890, b=432100; EXPECT_EQ(-135790, (a+b).to_i());
  a=-567890, b=-432100; EXPECT_EQ(-999990, (a+b).to_i());

  a=567890, b=567889; EXPECT_EQ(1135779, (a+b).to_i());
  a=567890, b=-567889; EXPECT_EQ(1, (a+b).to_i());
  a=-567890, b=567889; EXPECT_EQ(-1, (a+b).to_i());
  a=-567890, b=-567889; EXPECT_EQ(-1135779, (a+b).to_i());

  a=432100, b=567890; EXPECT_EQ(999990, (a+b).to_i());
  a=432100, b=-567890; EXPECT_EQ(-135790, (a+b).to_i());
  a=-432100, b=567890; EXPECT_EQ(135790, (a+b).to_i());
  a=-432100, b=-567890; EXPECT_EQ(-999990, (a+b).to_i());
}

TEST(BignumTest, sub) // -
{
  bignum a, b;

  a=0, b=0; EXPECT_EQ(0, (a-b).to_i());
  a=0, b=2; EXPECT_EQ(-2, (a-b).to_i());
  a=2, b=0; EXPECT_EQ(2, (a-b).to_i());

  a=1, b=2; EXPECT_EQ(-1, (a-b).to_i()); EXPECT_EQ(1, a.to_i()); EXPECT_EQ(2, b.to_i());
  a=1, b=-2; EXPECT_EQ(3, (a-b).to_i());
  a=-1, b=2; EXPECT_EQ(-3, (a-b).to_i());
  a=-1, b=-2; EXPECT_EQ(1, (a-b).to_i());

  a=50000, b=50000; EXPECT_EQ(0, (a-b).to_i());
  a=50000, b=-50000; EXPECT_EQ(100000, (a-b).to_i());
  a=-50000, b=50000; EXPECT_EQ(-100000, (a-b).to_i());
  a=-50000, b=-50000; EXPECT_EQ(0, (a-b).to_i());

  a=567890, b=432100; EXPECT_EQ(135790, (a-b).to_i());
  a=567890, b=-432100; EXPECT_EQ(999990, (a-b).to_i());
  a=-567890, b=432100; EXPECT_EQ(-999990, (a-b).to_i());
  a=-567890, b=-432100; EXPECT_EQ(-135790, (a-b).to_i());

  a=567890, b=567889; EXPECT_EQ(1, (a-b).to_i());
  a=567890, b=-567889; EXPECT_EQ(1135779, (a-b).to_i());
  a=-567890, b=567889; EXPECT_EQ(-1135779, (a-b).to_i());
  a=-567890, b=-567889; EXPECT_EQ(-1, (a-b).to_i());

  a=432100, b=567890; EXPECT_EQ(-135790, (a-b).to_i());
  a=432100, b=-567890; EXPECT_EQ(999990, (a-b).to_i());
  a=-432100, b=567890; EXPECT_EQ(-999990, (a-b).to_i());
  a=-432100, b=-567890; EXPECT_EQ(135790, (a-b).to_i());

  a.set("H",36); b.set("H",36); EXPECT_EQ("0", (a-b).to_s(36));
  a.set("HZ",36); b.set("HE",36); EXPECT_EQ("L", (a-b).to_s(36));
  a.set("HZL",36); b.set("HEL",36); EXPECT_EQ("L0", (a-b).to_s(36));
  a.set("HZLO",36); b.set("HELO",36); EXPECT_EQ("L00", (a-b).to_s(36));
  a.set("HZLLO",36); b.set("HELLO",36); EXPECT_EQ("L000", (a-b).to_s(36));
}

TEST(BignumTest, mul) // *
{
  bignum a, b;

  a=0; b=0; EXPECT_EQ(0, (a*b).to_i());
  a=0; b=2; EXPECT_EQ(0, (a*b).to_i());
  a=2; b=0; EXPECT_EQ(0, (a*b).to_i());
  a=1; b=1; EXPECT_EQ(1, (a*b).to_i());
  a=1; b=2; EXPECT_EQ(2, (a*b).to_i());
  a=2; b=1; EXPECT_EQ(2, (a*b).to_i());
  a=2; b=2; EXPECT_EQ(4, (a*b).to_i());
  a=3; b=-2; EXPECT_EQ(-6, (a*b).to_i());
  a=-3; b=2; EXPECT_EQ(-6, (a*b).to_i());
  a=-3; b=-2; EXPECT_EQ(6, (a*b).to_i());

  a=10000; b=10000; EXPECT_EQ(100000000, (a*b).to_i());
  a=100000000; b=100000000; EXPECT_EQ("10000000000000000", (a*b).to_s());
  a=65535; b=65535; EXPECT_EQ("FFFE0001", (a*b).to_s(16));
  a=65536; b=65536; EXPECT_EQ("100000000", (a*b).to_s(16));
}

TEST(BignumTest, comparison) // == != < <= > >=
{
  bignum a, b;

  a= 0, b= 0;
  EXPECT_TRUE(a==b); EXPECT_FALSE(a!=b);
  EXPECT_FALSE(a>b); EXPECT_TRUE(a>=b); EXPECT_FALSE(a<b); EXPECT_TRUE(a<=b);
  a= 1, b= 1;
  EXPECT_TRUE(a==b); EXPECT_FALSE(a!=b);
  EXPECT_FALSE(a>b); EXPECT_TRUE(a>=b); EXPECT_FALSE(a<b); EXPECT_TRUE(a<=b);
  a=-1, b=-1;
  EXPECT_TRUE(a==b); EXPECT_FALSE(a!=b);
  EXPECT_FALSE(a>b); EXPECT_TRUE(a>=b); EXPECT_FALSE(a<b); EXPECT_TRUE(a<=b);
  a= 1, b=-1;
  EXPECT_FALSE(a==b); EXPECT_TRUE(a!=b);
  EXPECT_TRUE(a>b); EXPECT_TRUE(a>=b); EXPECT_FALSE(a<b); EXPECT_FALSE(a<=b);
  a=-1, b= 1;
  EXPECT_FALSE(a==b); EXPECT_TRUE(a!=b);
  EXPECT_FALSE(a>b); EXPECT_FALSE(a>=b); EXPECT_TRUE(a<b); EXPECT_TRUE(a<=b);
  a=1, b=0;
  EXPECT_FALSE(a==b); EXPECT_TRUE(a!=b);
  EXPECT_TRUE(a>b); EXPECT_TRUE(a>=b); EXPECT_FALSE(a<b); EXPECT_FALSE(a<=b);
  a=10000000, b=0;
  EXPECT_FALSE(a==b); EXPECT_TRUE(a!=b);
  EXPECT_TRUE(a>b); EXPECT_TRUE(a>=b); EXPECT_FALSE(a<b); EXPECT_FALSE(a<=b);
}

TEST(BignumTest, assign_by_string)
{
  bignum num;
  num.set(""); EXPECT_EQ(0, num.to_i());
  num.set("0"); EXPECT_EQ(0, num.to_i());

  num.set("1"); EXPECT_EQ(1, num.to_i());
  num.set("-1"); EXPECT_EQ(-1, num.to_i());

  num.set("111"); EXPECT_EQ(111, num.to_i());
  num.set("111",2); EXPECT_EQ(7, num.to_i());
  num.set("-111"); EXPECT_EQ(-111, num.to_i());
  num.set("-111",2); EXPECT_EQ(-7, num.to_i());

  num.set("12"); EXPECT_EQ(12, num.to_i());
  num.set("-12"); EXPECT_EQ(-12, num.to_i());

  num.set("12",16); EXPECT_EQ(18, num.to_i());
  num.set("-12",16); EXPECT_EQ(-18, num.to_i());

  num.set("ZZ",36); EXPECT_EQ(1295, num.to_i());
  num.set("-ZZ",36); EXPECT_EQ(-1295, num.to_i());
}

int main(int argc, char** argv)
{
  testing::InitGoogleTest(&argc, argv);

  return RUN_ALL_TESTS();
}
トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/n4_t/20090208